Over the past couple of weeks I've been experimenting with a restricted form of metaprogramming that supports user-defined control structures and binding constructs such as pattern matching and let statements without the need for full Lisp-like macros. By restricting macros slightly, it is possible to reason about them statically, without giving up most of the power that full macros provide.
The key idea is to make bindings explicit. This basically means explicitly distinguishing between using a variable and binding a value to it. Whenever a variable x is used, it is simply written as x, but when a variable is meant to be bound to a value (which can happen in a lambda expression, in a let statement, as part of pattern matching or anything else we could come up with) it is prefixed with a single quote and written as 'x.
f(x) // the variables f and x are used, no quote necessary
'x => { g(x) } // the lambda binds the variable x in the body g(x)The alternatives to explicitly distinguishing uses and bindings are to either privilege some control structures or binding constructs as core syntax that cannot be redefined (which is what most languages do), so that for example variables always need to be declared using “=”, or to add support for macros, which can operate on the syntactic structure of a program before variables are resolved, so that a macro can decide whether to treat the variable x in f(x) as a variable (and resolve it) or just a symbol (and bind it).
The problem with macros is that while they are powerful, they make it hard (for humans and compilers) to reason about a program before a macro is expanded: Just seeing an expression such as f(2 + 2) in the source code does not guarantee that it is equivalent to f(4), because f could be a macro and thus treat 2 + 2 differently from 4. By exposing all of the syntactic structure of a program, macros have to be used sparingly and/or expanded before it is possible reason about equivalent expressions.
This observation dates back at least to papers by Mitchell and Wand in the context of Lisp fexprs instead of macros. Both fexprs and macros operate on unevaluated operands (instead of evaluated arguments), they can thus observe the syntactic structure of their operands, but they differ in what and when they return: Fexprs return a value and can potentially run at run time, whereas macros produce an output expression, a syntax tree that is inserted into the program at compile time. While it might technically be true that it is possible to reason about equivalent expressions after macro expansion (which is harder for fexprs that might be evaluated at runtime), let's instead look at a restricted form of macros, using explicit bindings, that supports equational reasoning without the need to expand any macros.
Let's take a step back and first look at how fexprs work in John Shutt's Kernel language, then restrict them by using explicit bindings.
In a nutshell, fexprs are functions that do not evaluate their arguments by default. An argument such as “2 + 2” remains an abstract syntax tree until it is explicitly evaluated in an environment. An fexpr is free to never evaluate any of its arguments or it can evaluate all of its arguments before use, in which case it acts like a regular function. Kernel calls fexprs that do not evaluate their arguments operatives, while functions that do evaluate their arguments are called applicatives. An operative is more fundamental than an applicative, since an applicative can be built by wrapping an operative in such a way that arguments are evaluated and then passed to the operative.
One thing to point out is that operatives do not evaluate anything by default, all evaluation has to happen explicitly. This is why it is impossible for a compiler to replace an expression like f(2 + 2) with f(4) until it knows whether f is an operative or an applicative. In Kernel, this is by design, because operatives are meant to be a semantic abstraction, which does not rely on a phase separatiion between run time and compile time. In contrast, macros are a syntactic abstraction, because they are expanded exclusively at compile time. Macros thus rely on the phase separation between run time and compile time, but they do not place other restrictions on how evaluation takes place.
By introducing explicit bindings of the form 'x, which distinguish between variables-to-be-used and variables-to-be-bound, Kernel-style operatives can be restricted in such a way that they become a syntactic abstraction (like macros), but can run either at run time or compile time (like Kernel-style operatives) and can be reasoned about statically without any evaluation or macro expansion (unlike Kernel-style operatives or Lisp macros).
The idea is simple: Any expression is evaluated by default (just like in regular functions) unless it contains a quoted variable such as 'x, in which case it remains unevaluated and its syntactic structure can be observed (just like in Kernel operatives).
f(2 + 2) // no explicit bindings, can be replaced with f(4)
f('x) // 'x is a binding, so x remains unevaluated
f('x, y + z) // y + z will be evaluated, but x remains unevaluatedIt is thus syntactically clear when and where evaluation happens: A compiler can safely optimize any expression that does not contain explicit bindings.
To resolve unquoted variables statically, the scope of variables must be statically tracked. The goal of explicit bindings is to make it possible to define and re-define binding constructs, but there needs to be some built-in syntax for block scope so that it is clear when and where bindings are introduced. This can be done using special syntax for lambda bindings or by statically associating explicit bindings with blocks where they are used, so that in f('x, { x + y }) the block { x + y } is statically guaranteed to be a lambda abstraction with one variable x (because 'x appears as an argument to f).
To be clear, making bindings explicit and syntactic marks a loss of power compared to Kernel-style fexprs, which is made even more evident by the fact that a lambda abstraction in Kernel can be built out of an operative, whereas some form special of block syntax is necessary with explicit bindings. This is by design, because these syntactic restrictions make it possible to reason about macro-like metaprogramming statically. This makes it possible to implement explicit bindings purely syntactically and translate everything into a normal call-by-value lambda calculus.
Here is a sketch of how this looks like: As mentioned, there needs to be some kind of lambda or block syntax which gets translated into normal lambda abstractions during parsing. More interesting is how to translate other expressions in such a way that they can be evaluated in a call-by-value lambda calculus while retaining the ability to observe their syntactic structure in macros. To do this, all expressions are translated as follows:
This is merely a rough sketch and I need to experiment more with the resulting language, but the direction seems interesting. Making bindings explicit is only a slight departure from traditional syntax, but might unlock 80% of the common uses of macros without introducing a full-blown macro system.