First-class (run-time) macros and meta-circular evaluation
First-class macros are macros that can be bound to variables, passed as arguments and returned from functions. First-class macros expand and evaluate syntax at run-time. Meta-circular evaluators support a concise implementation of first-class macros. In fact, first-class macros are easier to implement than traditional compile-time macros. A meta-circular evaluator is an interpreter which (1) can evaluate itself and (2) implements each language construct in terms of itself. This article and the attached implementation explain how to implement first-class macros in a meta-circular evaluator.
You might also be interested in:
- Paul Graham's posts on Arc, the first place I saw first-class macros.
- John McCarthy's original meta-circular evaluator for Lisp
- Chapter 4 of the MIT textbook Structure and Interpretation of Computer Programs (SICP), which popularized meta-circular evaluation.
With classical Lisp macros, you could define
and in terms of
(define-macro (and a b) `(if ,a ,b #f))
With first-class (a.k.a. run-time) macros, you would write
(define and (macro (lambda (a b) `(if ,a ,b #f))))
One advantage of the first-class form is that the programmer can pass first-class macros as arguments to procedures; passing a compile-time macro to a procedure causes a compile-time error.
Because of their first-class nature, first-class macros make it easy to add or simulate any degree of laziness.
Of course, run-time macros incur a run-time overhead. Fortunately, my research in static analysis leads me to believe that we will be able to erase that overhead for the common case--where first-class macros are used to do the job of compile-time macros.
The structure of interpretation
SICP teaches (and preaches) the eval/apply model of interpretation.
In this model, interpretation toggles between two functions,
eval : exp × env → value
apply : value × value* → value
expcontains expressions, such as numerals, variable references, applications and lambda terms. The type
envmaps variables to values:
env = variable → value
eval function evaluates an expression in the context of an environment for its free variables.
apply function applies a procedure to a list of arguments.
The foundational principle of Lisp that makes macros so elegant is the unification of code and data through S-Expressions, so that:
eval : s-exp × env → s-exp
apply : s-exp × s-exp* → s-exp
Clearly, if this approach is to work, then the definition of S-Expressions must also include semantic values like closures; that is, there will be S-Expressions with no literal form.
A meta-circular evaluator with first-class macros differs mostly in the structure of its
eval procedure for a meta-circular evaluator looks something like:
(define (eval exp env) (cond ((symbol? exp) (env-lookup env exp)) ((number? exp) exp) ((boolean? exp) exp) ((string? exp) exp) ((quote? exp) (eval-quote exp env)) ((if? exp) (eval-if exp env)) ((cond? exp) (eval-cond exp env)) ((or? exp) (eval-or exp env)) ((and? exp) (eval-and exp env)) ((lambda? exp) (eval-lambda exp env)) ((let? exp) (eval (let->app exp) env)) ((let*? exp) (eval (let*->let exp) env)) ((letrec? exp) (eval (letrec->lets+sets exp) env)) ((begin? exp) (eval-begin exp env)) ((set!? exp) (eval-set! exp env)) ((app? exp) (apply (eval (app->fun exp) env) (map (lambda (arg) (eval arg env)) (app->args exp))))))
A first-class macro
eval procedure in an implementation with first-class macros is shorter:
(define (eval exp env) (cond ((symbol? exp) (env-lookup env exp)) ((number? exp) exp) ((boolean? exp) exp) ((string? exp) exp) ; 3D-syntax is invoked to produce a captured value: ((procedure? exp) (exp)) ((app? exp) (perform-apply (eval (app->fun exp) env) exp env))))
With first-class macros, the core syntactic forms are not privileged; rather, they are defined in the initial environment:
(define initial-environment-amap (list (list 'apply apply) (list '+ +) (list 'not not) (list 'display display) (list 'newline newline) (list 'cons cons) (list 'car car) (list 'cdr cdr) (list 'cadr cadr) (list 'caadr caadr) (list 'cadar cadar) (list 'cddr cddr) (list 'cdddr cdddr) (list 'list list) (list 'null? null?) (list 'pair? pair?) (list 'list? list?) (list 'number? number?) (list 'string? string?) (list 'symbol? symbol?) (list 'procedure? procedure?) (list 'eq? eq?) (list '= =) (list 'gensym gensym) (list 'void void) (list 'quote (list 'syntax-primitive eval-quote)) (list 'if (list 'syntax-primitive eval-if)) (list 'cond (list 'syntax-primitive eval-cond)) (list 'and (list 'syntax-primitive eval-and)) (list 'or (list 'syntax-primitive eval-or)) (list 'let (list 'syntax-primitive eval-let)) (list 'let* (list 'syntax-primitive eval-let*)) (list 'letrec (list 'syntax-primitive eval-letrec)) (list 'begin (list 'syntax-primitive eval-begin)) (list 'set! (list 'syntax-primitive eval-set!)) (list 'lambda (list 'syntax-primitive eval-lambda)) (list 'macro (list 'syntax-primitive eval-macro))))
Interpretation-level primitives are actually bound directly as their meta-level primitives.
perform-apply procedure must check whether the operator to be applied is a syntactic primitive, a macro or a procedure:
(define (perform-apply fun app-exp env) (let ((args (app->args app-exp))) (cond ((macro? fun) (eval (apply (macro->proc fun) args) env)) ((syntax-prim? fun) ((syntax-primitive->eval fun) app-exp env)) (else (let ((arg-values (eval* args env))) (apply fun arg-values))))))
3D-syntax and hygiene
Some constructs, such as
letrec, are desugared into other
constructs, such as
set!; for example:
(let ((var exp) ...) body)
((lambda (var ...) body) exp ...)
This sort of expansion can cause a problem if we use a
let construct in a context where
has been redefined.
For example, we might define a function to compute the energy of a photon:
(define (energy lambda) (let ((c speed-of-light) (h plancks-constant)) (/ (* c h) lambda)))
let form expands into
lambda-application this code, the
lambda is no longer bound to the syntactic
lambda; rather, it is bound to some numeral
When the evaluator tries to evaluate this code, it will throw a
particularly cryptic error about trying to apply a non-function value.
This kind of capture is one of the two kinds of "hygiene" violations
that Lisp systems worry about, and it is the only one that cannot be
The provided implementation solves this hygiene problem through 3D syntax.
An expression is 3D if a programmer cannot write it down.
In other words, it is an expression that must have come from a special syntactic expansion.
In Lisp, raw procedures are 3D, because there is no way to write down
a literal that the
read procedure will pull in as a
If you examine the
eval procedure for the first-class macros implementation, you will find a case not
present in the ordinary evaluator:
When the evaluator hits a procedure, it assumse it takes no arguments
and then evaluates it, directly returning whatever that procedure
This behavior provides a way to pass protected values out of
first-class macros, since they will be evaluated in whatever scope
there was when the closure was born.
let from in my implementation (effectively) expands into:
((,(lambda () 3d-lambda) ,@var ,@body) ,@exp)
3d-lambda is bound to the syntactic primitive for