Paul Khuong mostly on Lisp

rss feed

Mon, 25 Jun 2007


Common Cold's special forms

The central element in serialising continuations are serialisable closures. They are created by the macros slambda (serialisable lambda) and sfunction (serialisable function), which can be used exactly like the lambda and function special forms, except that slambda may not be the car of an expression (or inside a function form), and that sfunction can only be given a function's name as argument. These macros will globally register the information needed to serialise and deserialise the closures at compile-time, in a serialisable format.

For example, a serialisable adder could be created this way

(defun make-adder (inc)
  (flet ((adder (x)
           (+ x inc)))
    (sfunction adder)))
or that way
(defun make-adder (inc)
  (slambda (x)
    (+ x inc)))

Note that there is no need to annotate local variables or functions. Highly unportable environment access is used to regenerate information about the lexical scope surrounding an slambda or sfunction form. Unfortunately, it means that it may also interact badly with codewalked extensions.

Something close to Administrative-Normal Form (ANF, or monadic style) is then used to expose enough structure to macros for them to be able to easily save continuations. (bind (var val) expr) binds the value of val to var in expr, adding expr to val's continuation. dbind is the same thing, but binds to special (dynamically scoped) variables instead of lexical ones. This is enough to make explicit the order in which operations will be executed, which is exactly what is needed to implement continuations. There is no need for a monadic return: we use dynamically scoped constructs (catch and throw), so values need not be wrapped specially.

ANF is much less painful to use than CPS, but it's still far from ideal. Common Cold offers several macros to emulate common CL values binding forms. Instead of let*, one should use mlet* (to bind to lexical variables) or mdlet* (to bind to special variables). For example:

(mlet* ((x (get-x))
        (y (get-y))
        (dist (sqrt (+ (* x x)
                       (* y y)))))
  (fn dist))
or, if we want fn to have access to x and y as special variables:
(mdlet* ((*x* (get-x))
         (*y* (get-y)))
  (fn (sqrt (+ (* *x* *x*)
               (* *y* *y*)))))

Note that normal CL lexical binding forms (e.g., let or let*) may be freely mixed with CC's forms, as long as the execution of the value expressions ((get-x), (get-y), ... here) does not capture continuations. CL dynamic binding forms (e.g. with (declare (special...))), however, should only be used when the execution of both the value expressions and the body of the forms (the dynamic extent of the bindings) does not capture continuations. mlet (for lexical bindings) and mdlet (for dynamic ones) offer a behaviour like that of CL's let, where the bindings are only established once all the bound values have been computed.

Creating serialisable closures and continuations establishes copies of the lexical bindings. Assignment to lexical variables is thus not recommended, at least not when slambda or sfunction forms are in the lexical scope, or continuation-capturing code in the dynamic scope. Dynamic bindings, on the other hand, are linked to the dynamic environment, and not to continuation frames or closures. Thus, it makes sense to capture them with the rest of the dynamic environment — at least, as much of it — in continuations. Capturing continuations will also save (copy) the values of all the bindings at the time of the capture, so assignment to special variables is meaningful... without continuations making it harder to reason about them.

Common Lisp's non-local exit forms (e.g., throw or tagbody) all have a dynamic extent, which means they are useless after the capture and later invocation of a continuation. Common Cold duplicates some of these forms in order to be able to restore them when invoking continuations. mcatch may be used exactly like catch, returning to it with a normal throw. mblock (which, like block, establishes a lexical non-local exit environment), on the other hand, must be matched with mreturn-from or mreturn (which act like return-from and return). Returning to a CL block with mreturn-from, or to an mblock with return-from will result in erroneous code. Fortunately, they are lexically scoped constructs, so using them correctly should be easy (checkable locally).

Finally, to execute several operations in sequence, one should use mprogn, which acts like progn. However, most of the special forms above have implicit mprogn (when their CL counterparts have implicit progn).

posted at: 00:00 | /Lisp/CommonCold | permalink

Made with PyBlosxom Contact me by email: