What languages give you access to the AST to modify during compilation?

Question

Are there any languages which allow you to get access to the AST during compile time, to use some part of the AST to generate code, or to possibly rewrite the code/AST to optimize it in a heuristic way?

I just found out about Rust's derive (procedural macros), which gives you the AST that you have to implement a handler for, like in this example from the diesel crate.

pub fn derive_insertable(input: TokenStream) -> TokenStream {
    insertable::derive(parse_macro_input!(input))
        .unwrap_or_else(syn::Error::into_compile_error)
        .into()
}

I also feel like I remember reading somewhere in the Julia language documentation that you could get the AST at compile time and rewrite it to get further optimizations, but maybe I misread and I can't find the link.

I am in particular wondering what could be done if you could get access to the AST at compile time, and what that might look like. Are there any other examples of languages doing this? If so, what do they allow you to do (and what is a quick example)?

For the (imperative/object oriented) language I'm working on, I am imagining potentially taking the definition of a recursive function and rewriting that using a flat iterative/stack based approach for optimizations. But not necessarily build this into the main compiler; somehow make it pluggable so you could write your own "function optimizer" and swap it out with a new one, or something like that. I am imagining like how ESLint for JavaScript allows you to rewrite the AST, maybe there is something like that but for compilers. And how would that look, what an API example might look like.

But main thing I'm wondering about this in summary:

• What are the major examples of languages giving you access to the AST at compile time?
• What might be an API example of how you would use it (and what might be a use case)?

I would also be curious as to your perspective on if this would be valuable or a problematic complicated mess of a feature, but perhaps you can leave a comment on that if you've thought about it before or tried this before without success, or otherwise just know that it would be impractical.

Answer 1

Accessing the original AST is a type of metaprogramming, and it is customary to call this ability the macro.

But the word macro is overused, often used to refer to something completely different, like VBA macros, C++ macros, Rust macros, etc. None of this is the kind of macro you want.

To avoid ambiguity, I use the term quasiquote here.

---

In metaprogramming, quasiquote is a feature that allows you to perform template-based code generation.

Lisp family (e.g. Common Lisp, Scheme, Racket)

Lisp was one of the first languages to introduce quasiquote, which is implemented through backquote (`) and comma (,).

Backticks are used to quote structures, while comma are used to interpolate variable values.

@Bbrk24 reminds me that there are more on JVM, such as Clojure, ABCL.

Template Haskell

Quasiquote blocks are represented by [| ... |].

In Quasiquote blocks, $ can be used to interpolate variables.

Julia

Quasiquote blocks are followed by : and $(expression) can be used as interpolate variables.

---

Some languages also allow access to AST, but the code generation part is relatively primitive, such as concatenating strings.

eg. C# ISourceGenerator

Some languages are implemented through third-party libraries.

eg. Rust syn + quote

These methods are difficult to check and analyze, and bring greater difficulty to the implementation of IDE/LSP.

If possible, it is better to analyze it with built-in quasiquote within language itself.

Answer 2

I'd like to elaborate some more on LISP's capabilities (in addition to Aster's answer).

LISP is special in that its source code can be understood as being the AST (expressed as nested list structures, written in the generic text syntax for lists).

It has macros in the very generic sense that a "macro-calling" expression gets replaced by some other expression at some stage the compilation process. This is also true for e.g. the good old C language preprocessor macros.

But while C language preprocessor macros are nothing more than text patterns, knowing nothing about the C language syntax, the LISP macros are defined in LISP code themselves. They get the full expression of the "macro call", in form of the list-structured AST, can analyze and modify anything they want about that expression using every available feature of LISP, and finally emit an expression (a list-structured new AST) that is to be compiled instead of the original one.

In fact, most of the control structures in LISP (e.g. loops) really are macros that typically take some body expressions and wrap them into a different outer expression, one using low-level language features. Sometimes they also look into the body and do replacements there as well. But all this is up to the macro definition, and can be implemented with the full flexibility of the LISP language.

As far as I understand your question, this very much matches what you asked for.

Answer 3

R Language

In R, function arguments aren't evaluated until they are used, and more importantly, they can be quoted (converted into their syntax tree) using substitute. Once quoted, the argument's syntax tree can be manipulated, and then evaluated in R using eval or interpreted in an entirely different way (e.g. deparse to turn it into a string).

sentence <- function(expr) {
  ast <- substitute(expr)
  literal <- deparse(ast)
  # here we substitute x = 10 and y = 5 in expr
  replace <- function(ast, substs) {
    # switch is an example of a function which takes advantage of fexprs
    # (argument names are interpreted as strings, and only the matched case is evaluated)
    switch(
      typeof(ast),
      language = as.call(lapply(ast, function(child) replace(child, substs))),
      symbol = if (!is.null(substs[[ast]])) {
        substs[[ast]]
      } else {
        ast
      },
      ast
    )
  }
  answer <- eval(replace(ast, list(x = 10, y = 5)))
  paste(literal, "is:", answer)
}

sentence(x * 50 + y) # [1] "x * 50 + y is: 505"
sentence(x * x + y * y) # "x * x + y * y is: 125"

These kinds of functions (ones which don't necessarily evaluate their arguments) are known as fexprs. They aren't quite macros because the body is just regular R code and the arguments aren't just syntax (they are lazy R expressions, if you assign them they get evaluated normally). But they aren't quite regular functions because, well, the arguments don't necessarily get evaluated and can be quoted.

Fexprs are really powerful, because they work like regular functions 90% of the time, but come in handy the 10% of the time you actually want lazy evaluation or metaprogramming. You can implement all of R's control constructs such as if, while, and <- (assign) using fexprs; in fact, all of R's syntax is just syntactic sugar over fexprs, and you can override almost any of the builtin language constructs*.

old_if <- `if`
# evil if
`if` <- function(cond, then, otherwise) {
  old_if(cond, otherwise, then)
}

if (2 + 2 == 4) {
  print("obviously")
} else {
  print("WHAT")
}

Fexprs are used in most of R's popular libraries, like ggplot (see cheatsheet) and dplyr (see cheatsheet). Another example is in the "translation" section of Advanced R, it uses this mechanism to create an HTML and a LaTeX DSL.

To learn more, check out Advanced R's metaprogramming section and the Non-standard evaluation section of the first edition. Do note that Advanced R uses a lot of libraries but they're not necessary, all the quoting functionality is in base R. Also check out R's documentation for definitions and examples of common functions, including ones mentioned above as well as quote, enquote, expression, as.expression, call, as.call, and more.

* Actually, the R interpreter / JIT compiler uses hardcoded implementations of the builtins unless they're overridden. Also, byte-compiled packages won't be affected by any changes to the builtin functions, because they are already compiled with the hardcoded variants.

Answer 4

Groovy allows you to edit the AST, but only to the degree the built in annotations allow. For example, you can add an annotation to inherit constructors, or for creating a data class. See this link for more info.

Answer 5

In Java, an annotation processor can inspect the AST and generate new code.

Unfortunately, its API is rather painful to use, and therefore not used often, but several popular metaprogramming libraries use this to add new syntactic sugar to the Java language.

While the annotation processing API is not intended to modify the AST, most compilers pass their actual AST elements to annotation processors, and with some ugly type casting, a processor can modify the AST. One library which does this is Lombok.

Answer 6

OCaml has a mechanism called PPX to handle transform ASTs. Note that it as a now-disfavored Cpp-style preprocessor to modify the code itself Cppo.

There are two OCaml ASTs, parsetree and typedtree, and PPXs work on the former.

You can automatically derive useful utilities like printers or equality operators like

type expr =
  Val of int
| Add of expr * expr [@@deriving sexp, compare, show]

and these are called PPX derivers that generates code from items like type declarations, expressions, etc.

Another form of PPX deals with extension nodes, which are directly rewritten. These are extenders. For example, we can add monadic let-bindings

let rec eval = function
  | Val n -> [ n ]
  | Add (x, y) ->
      let open List.Let_syntax in
      let%bind n = eval x in
      let%bind m = eval y in
      return (n + m)

These PPXs work with extension points, which allows for adding syntax extensions in the AST level.

More useful explanations are provided here.

Answer 7

Attached Swift macros, which are still in beta, give you access to the AST of the node they are attached to. That is, you can read the AST of the variable, function, or object declaration, and return new additions; you can't change the code that's there. There are also freestanding macros, where you return an AST but only receive the AST of the macro itself. I'd say they're pretty powerful overall, but can get very complicated very quickly as you have to crawl the AST for everything.

Applications are many and varied; I've done a handful for things like adding initializers, adding protocol conformance, even a couple macros to help make other macros.

You can read detailed design docs (Guiding vision document; expression, attached macros, freestanding macros, conformance vs. extension (currently in active review)), see the discussions linked in the proposals, and read a great deal more discussion on the subject on the Swift evolution forum.

As an example, here's a macro to add an unknown case to a string-based enum:

public struct OpenMacro {}

extension OpenMacro: MemberMacro {
    public static func expansion(
        of node: AttributeSyntax,
        providingMembersOf declaration: some DeclGroupSyntax,
        in context: some MacroExpansionContext
    ) throws -> [DeclSyntax] {
        guard let decl = declaration.as(EnumDeclSyntax.self) else {
            throw OpenError.notAnEnum
        }
        let members = decl.memberBlock.members
        let rawType = "String"
        let caseDecls = members.compactMap { $0.decl.as(EnumCaseDeclSyntax.self) }
        let elements = caseDecls.flatMap { $0.elements }

        let nonnullableInitializer = try InitializerDeclSyntax("init(_ rawValue: \(raw: rawType))") {
            try SwitchExprSyntax("switch rawValue") {
                for element in elements {
                    SwitchCaseSyntax(
                        """
                        case \(raw: element.rawStringValue):
                            self = .\(element.identifier)
                        """
                    )
                }
                SwitchCaseSyntax("default: self = .unknown(rawValue)")
            }
        }

        let rawValueDecl = try VariableDeclSyntax("var rawValue: \(raw: rawType)") {
            try CodeBlockItemListSyntax {
                try SwitchExprSyntax("switch self") {
                    for element in elements {
                        SwitchCaseSyntax(
                            """

                            case .\(element.identifier.trimmed):
                                return \(raw: element.rawStringValue)
                            """
                        )
                    }
                    SwitchCaseSyntax("\ncase .unknown(let rawValue): return rawValue")
                }
            }
        }

        return [
            "case unknown(\(raw: rawType))",
            "init?(rawValue: \(raw: rawType)) { self.init(rawValue) }",
            DeclSyntax(nonnullableInitializer),
            DeclSyntax(rawValueDecl),
        ]
    }
}

extension OpenMacro: ConformanceMacro {
    public static func expansion(
        of node: AttributeSyntax,
        providingConformancesOf declaration: some DeclGroupSyntax,
        in context: some MacroExpansionContext
    ) throws -> [(TypeSyntax, GenericWhereClauseSyntax?)] {
        return [("RawRepresentable", nil)]
    }
}