Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
338 lines (268 sloc) 14.2 KB

How to use a codewalking macro to implement a lexically scoped delay in Emacs Lisp

Vincent Toups

Lazyness is all the rage in these days of Haskell and Clojure, and it comes in many forms. Haskell is lazy by default, clojure supports laziness extensively, but it is still voluntary. Some scheme implimentations provide promises, which are delayed computations, and almost every high level programming language provides the basic building block of laziness via closures and anonymous functions.

We might, for instance, implement laziness in Scheme with a macro which transforms:

(delay expr1 ... exprN) 


(lambda () expr1 ... exprN)

and then force is simply implemented as a function call:

(define (force thunk) (thunk))

Something which I think is a key insight here is that lambda is intelligent quotation. I'm not a programming language theorist, so I don't know if this constitutes a particularly novel insight, but to me it was a crucial step towards understanding the semantics underlying most programming languages. What does "lambda is intelligent quotation" mean, though? Well, we can imagine writing a very primitive delay macro thusly (in some kind of lisp):

(defmacro (delay . args) `(quote (begin ,@args)))

and then force is just eval:

(define force eval)

While this certainly "gets the job done" for expressions containing only atoms, it doesn't work on any expression containing variables. Depending on how your Lisp works, and when you call force, you can get anything from a straight up error to a mysterious result. If you use a lambda instead, however, you tell your language "quote this expression, but make sure all the symbols in the expression refer to the values described by the lexical context."

So here is a question: if we want to implement delay and force in emacs lisp, how do we do it? An extremely naive guess would be just to use lambda:

(defmacro delay (&rest body) `(lambda () ,@body))

Force is still:

(defun force (thunk) (funcall thunk))

But this doesn't quite work as we expect.

(let ((thunk 
  (let ((x 10))
    (delay (+ x x)))))
      (force thunk))

This will produce an error - that x is undefined. This is because, vexingly, Emacs Lisp is an old Lisp and has dynamic scope. That means x in the lambda created by delay refers to whatever the outermost x binding is, which, by the time we've arrived at the force is just nothing.

"Fear not," I hear you say! "I've read that Emacs Lisp has lexical closures via the cl.el package. Why don't we just use those?"

The item in question is cl.el's lexical-let form. Lexical-let lets you do things like

(funcall (lexical-let ((x 10))
           (lambda () (+ x 101)))) ; -> 111

It uses some trickery which I frankly haven't gotten too deeply into to simulate a lexical closure so that lambda grabs the right variable in the body of a lexical-let. However, note that we have to enumerate the variables we'd like to close over. We could write a macro to the effect of delay-with which had a body and a list of variables to close over, but can we do better?

We can, in fact, do better with a codewalking macro. Most macros which take a "body" do something simple. A good example is emacs lisp's save-excursion, which basically just inserts code to save and restore the current editing state around an unmodified body.

A codewalking macro takes a set of lisp forms, walks over them, inspecting and transforming, and finally generates a perhaps radically transformed new set of lisp expressions. We can write a codewalking macro to implement delay. All it has to do is walk over the body of the code and collect all the symbols and functions that are lexically free in it, and then lexically close around these symbols. Then, as if by magic, delay becomes a "smart" quotation.

So if our body is something like (+ x y z), then our job is pretty easy: x, y, and z are obviously free variables in the expression, so our macro takes:

(delay (+ x y z))


(lexical-let ((x x)
              (y y)
              (z z))
  (lambda () (+ x y z)))

If we put this in context:

(setq thunk (let ((x 10) (y 11) (z 12))
              (delay (+ x y z))))
(force thunk) ; -> 33

Note that above the let expression forms a dynamic scope, but our delay macro calculates the free variables and lexically closes over them before the dynamic values are popped of the stack. Then, when thunk is called, everything works out all right.

A couple of objections ought to be appearing in your mind right now. One of them focuses on the fact that lisp expressions are not as simple as just function calls, and that, in particular, a variety of lisp expressions introduce variable bindings which influence nested expressions. Most obviously,

(setq thunk (let ((y 1001) 
                  ((x 10)))
            (delay (let ((x (+ x 100)))
                  (+ x y)))))
(force thunk)

involves some thinking about what values we should close over. Rather obviously we need to capture the lexical binding of y, but what about x. Within the body of the inner let expression, x will be dynamically bound, but the value it takes depends on the non-lexically bound outer x. If we traversed the code tree, just counting x occurences, we might miss the fact that let treats the symbol part of its binding expressions differently than the value parts. Not only that, but we have to consider the dynamic and lexical binding of function applications, which are treated separately in emacs lisp because it is a lisp-2. This problem is tractable, however, because emacs lisp has a small number of simple fundamental expression types. We can, therefore, hope to write a parser which traverses arbitrary lisp code, collecting information about which variables are locally bound or lexically free within an expression.

Here comes the second objection, however. It is true that lisp defines only a small number of fundamental special forms, but any arbitrary piece of lisp code may be peppered with a variety of user defined special forms created via macros. It may be within our capabilities to parse a lisp expression containing only fundamental forms, but can we reasonably expect ourselves to parse the binding information contained in the clauses of a loop expression, much less any unique, ad-hoc, user created macro? The good news is that we don't have to - we can call macroexpand-all on the body before parsing it, guaranteeing that we will have only naked lisp to parse.

Now that those objections are out of the way, we can begin to tackle the problem formally. We'd like to write a function which reads a piece of lisp code and and records the number of times a symbol is used without a binding, either as a function or as a value. Once we have this list we can wrap up our expanded body in lexical-let and labels forms, to provide local definitions of functions and values which are lexically scoped.

The skeleton to collect the symbol usage information is, thus;

(defun* collect-usage-info (form &optional (global-info (alist>>))
                                 (local-info (alist>>)))
"(collect-usage-info FORM &optional GLOBAL-INFO LOCAL-INFO)

Collects information about the usage of variables and functions in the form FORM.
When called recursively, it may be appropriate to provide GLOBAL-INFO, an alist 
describing the collected information so far, and LOCAL-INFO, an alist describing
the binding information of variables locally.  

GLOBAL-INFO is returned.  It is an alist of the form;
    (<symbol> (<n-bound-symbol-usages>

LOCAL-INFO is recursively defined, but is of the form
    (<symbol> (<bound-as-symbol>

  Where bound-as-(function/symbol) are either t or nil."
   ((symbolp form)
    (cond ((eq 't form) global-info)
          ((eq 'nil form) global-info)
           (dlet [[bound-s bound-f] (symbol-binding-info form local-info)
                  [s-count f-count s-unbound-count f-unbound-count] (symbol-bind-counts form global-info)]
             (alist>> global-info form (list 
                                        (if bound-s (+ 1 s-count) s-count)
                                        (if (not bound-s) (+ 1 s-unbound-count) s-unbound-count)
   ((listp form)
     ((quotep form)
     ((prog-like form)
      (collect-usage-info-prog-like form global-info local-info))
     ((letp form)
      (collect-usage-info-let form global-info local-info))
     ((let*p form)
      (collect-usage-info-let* form global-info local-info))
     ((function-formp form)
      (collect-usage-info-function form global-info local-info))
     ((ifp form)
      (collect-usage-info-if form global-info local-info))
     ((condp form)
      (collect-usage-info-cond form global-info local-info))
     ((defunp form)
      (collect-usage-info-defun form global-info local-info))
     ((setqp form)
      (collect-usage-info-setq form global-info local-info))
     (t ; function application
      (collect-usage-info-prog-like (cdr form)
                                    (collect-usage-info-function `(function ,(car form)) global-info local-info)

Anyone familiar with SICP will recognize this pattern. We have a case statement which determines what sort of expression we are looking at, and then dispatches handling of that expression type to a specific handler, which may call collect-usage-info recursively. The base cases are symbols and atoms. Atoms are ignored, whereas symbols, when encountered, are counted appropriately depending on the information in local-info. You can see all the details in the source code, available at my git-hub, but to give you an idea of how this works, lets look at the case of the let expression.

We detect a let-expression with the letp predicate;

(defun letp (form) 
   (and (non-empty-listp form)
        (eq (car form) 'let)))

(all these predicate functions are defined in macro-utils.el.)

Handling a let form is relatively simple. We will read each binding clause, count the variable usage in the expression providing the value thereof, and then collect all the symbols bound in the expression. We then call collect-usage-info-prog-like on the body, providing an augmented local-info which indicates that the variables described in the let expression now have bindings. collect-usage-info-prog-like simply folds collect-usage-info over the forms in the body.

This idea is repeated for all forms in the basic emacs-lisp language. Using this function we can finally define our delay macro thusly:

(defmacro* delay (&body body)
  (let* ((expanded (macroexpand-all `(progn ,@body)))
         (info (collect-usage-info expanded))
         (unbound-symbols (get-unbound-symbols-list info))
         (unbound-functions (get-unbound-function-symbols-list info))
           (loop for f in unbound-functions collect (gensym (format "%s-old-" f)))))
           `(lexical-let ,(loop for s in unbound-symbols collect `(,s ,s))
                          (labels ,(loop for old-f in temporary-function-names 
                                          and f in unbound-functions collect 
                                          (let ((arglist (gensym "arglist")))
                                            `(,old-f (&rest ,arglist) (apply #',f ,arglist))))
                                   (labels ,(loop for f in unbound-functions 
                                                   and old-f in temporary-function-names collect 
                                                   (let ((arglist (gensym "arglist")))
                                                     `(,f (&rest ,arglist) (apply #',old-f ,arglist))))
                                            (lambda () ,expanded))))))

As promised, there isn't much by way of magic here. We expand the body as a progn-like form, collect the information about variable binding from it, and then create the appropriate lexical closures. The only wrinkle is in the precise use of the labels form. Functions introduced in a labels form are allowed to be mutually and self recursive, so we can't just do the equivalent of:

(let ((x 10))
   (lexica-let ((x x))
       (+ x x)))

which is,

(flet ((f (q) (+ q 1)))
  (labels ((f (&rest arglist) (apply #'f arglist)))
      (f 1)))

Because the labels form above introduces a recursive function f which calls itself indefinitately. There are several possible solutions to the problem. The simplest, but perhaps not the best, is to use two independent labels forms, the first of which creates new bindings for the functions, and the second of which creates the lexical bindings with the correct names. Perhaps the ultimate solution is to pick new names, and walk the code, replacing each function application with the new name. This is probably overkill for this example.

So we've finally arrived! Now we can delay and force to our heart's content, and emacs will do its best to pretend it is a lexically scoped language:

(let ((x 10))
   (setq thunk (delay (+ x 1))))
(force thunk) ;-> 11 
x ;-> undefined variable 

As an exercise to the reader, you can try to implement two functions which are provided in the source code, but not reproduced here: lexical-lambda and lexical-defun. They have the following behaviors.

  (let ((x 10))
    (lexical-lambda (y) (+ y x)))
  100) ; -> 110

(let ((x 10))
  (lexical-defun f (y) (+ x y)))

(f 10) ;-> 20 
Something went wrong with that request. Please try again.