excl:ensuring-compiled-body: a new macro
Introduction
The new macro ensuring-compiled-body works like progn in that it executes its body forms sequentially, returning the result of the final form. But it first ensures the forms are compiled. Making sure that the forms are compiled in the correct environment is not a trivial problem. We describe how it is done in this note.
All Common Lisp implementations are required to have compiled execution -- Common Lisp was defined as an idiomatically compiled language. But there are reasons that interpreted execution might still be useful, even though interpreted execution can run an order of magnitude or more slower. So many Common Lisp implementations feature both compiled and interpreted code execution in a single Lisp execution. The ANS permits this, provided both kinds of executions implement and obey the semantics specified in the ANS.
It is well known that in a compiled-only implementation, EVAL would be implemented something like this:
(defun my-eval (form) (funcall (compile nil `(lambda () nil ,form))))
(The reason for the nil in the lambda body is to guarantee a declare form will be treated as an illegal form, rather than being taken as a declaration at the start of a null body.)
Now, even in an implementation like ACL with both compiled and interpreted execution, we could define a simple macro that ensures that its code body is executed compiled.
(defmacro ensure-compilation (&body body) `(funcall (compile nil (lambda () nil ,@body)))) (define-compiler-macro ensure-compilation (&body body) `(progn ,@body))
Assuming the implementation uses compiler macros, this wrapper does
nothing in compiled code, but compiles the body when executed in
interpreted code. In Allegro CL the compiler is sufficiently fast,
and compiled code sufficiently faster than interpreted, that in
certain vary rare and obscure circumstances this can be a winning
strategy. Usually, for instance in the read-eval-print loop, one
would just cause each entire top-level form to be compiled. (In
Allegro CL this can be done by
setting tpl:*eval*
to 'my-eval defined above.) But interpreted code is
sometimes better for debugging, or (in very very obscure circumstance)
where it is desired to insert dynamically generated forms inside a
lexical environment. It isn't the purpose of this article to discuss
these obscure circumstances. (Some arise in conjunction with using
Prolog as an embedded language.) The problem of compiling code within
an existing interpreted environment is itself an interesting study in
the semantics of Common Lisp and the (semi)portable environment
facility in
Allegro, Environments
support in Allegro Common Lisp.
The problem with the above ensure-compilation definition, of course, is that eval evaluates a form and compile creates a function in the null lexical environment. We'd like to be able to compile a code body so that it can refer to the surrounding interpreted lexical environment. The new ensuring-compiled-body macro does just this. How does it work?
How can a body of interpreted code, defined in an interpreted lexical environment, be changed to compiled code defined within that same interpreted environment? The dynamic environment is not at issue -- it is equally available to both compiled and interpreted code. But everything in the lexical environment that is accessible to code must be known when the code -- a tree of conses -- is closed and becomes a function. Indeed, the work "closure" implies that the function is in some way sealed.
The lexical environment consists of five components, four of which function as separate namespaces. These four are
- variable names (lexical variables and symbol macros)
- operator names (functions and macros)
- block names
- go tags
The fifth contains information about any surrounding declarations that do not concern names in the four namespaces above.
An environment is represented by a first-class environment object, and the namespaces can be queried with the functions sys:variable-information, sys:function-information, sys:block-information, sys:tag-information, and sys:declaration-information. In addition, there are functions sys::map-over-environment-variables, sys:map-over-environment-functions, sys::map-over-environment-blocks, and sys:map-over-environment-tags which map over all lexically visible (unshadowed) definitions in the particular namespace.
What remains is to decide how to wrap a code body in forms that will make available bindings in these four namespaces to the compiled code. Each kind of surrounding lexical binding can be handled straightforwardly, although some might be slightly inefficient. Here follows examples for each of the environment components. None of these examples are in any way practical examples -- they have been composed simply to illustrate the rewriting.
Lexical variables
These are the simplest. Lexical variables in interpreted execution are stored in the car of a cons which serving as a locative. sys:variable-information returns that cons. The compiled code body captures that cons as a constant and a symbol-macrolet transparently rewrites references to that variable inside the compiled body. Thus, this form
(symbol-macrolet ((limit (+ 5 (random 4))))
(let ((numbers (loop for i from 1 to 10 collect i)))
(ensuring-compiled-body
(setf numbers (remove-if (lambda (x) (> x limit)) numbers)))
numbers))
which has both a symbol macro and a lexical variable in the environment would be rewritten to capture both as symbol macros:
(symbol-macrolet ((limit (+ 5 (random 4))))
(let ((numbers (loop for i from 1 to 10 collect i)))
(funcall
(compile nil
'(lambda nil
(symbol-macrolet ((numbers (car '((1 2 3 4 5 6 7 8 9 10))))
(limit (+ 5 (random 4))))
(progn (setf numbers
(remove-if (lambda (x) (> x limit))
numbers)))))))))
The symbol macro for limit is simply replicated around the body of the lambda expression to be compiled. The lexical variable numbers is replaced by a symbol macro that accesses the locative for the outer variable. The quoted cons that is the argument to car is the locative. The car of that cons is the current value of the outer numbers variable.
Note that this symbol macro relies on the fact that car does not do compile-time constant folding in Allegro CL. If it did, the compiled code body might capture the initial value of the outer numbers variable instead of capturing the locative for the variable.
Lexical operators (flet, labels, and macrolets)
These can be made available by wrapping the code body in a flet or macrolet. For example, code like the following
(flet ((f (x) (+ 2 x)))
(macrolet ((m (x) `(1- ,x)))
(ensuring-compiled-body
(let ((y (m (f pi))))
(print y)))))
would be rewritten approximately this way
(flet ((f (x) (+ 2 x)))
(macrolet ((m (x) `(1- ,x)))
(funcall
(compile nil
'(lambda nil
(flet ((f (&rest rest)
(declare (dynamic-extent rest))
(apply #<Interpreted Function (flet () f) @ #x208ab322> rest)))
(macrolet ((m (&whole whole &environment env &body body)
(declare (ignore body))
(funcall #<Interpreted Closure m @ #x208ab8e2> rest)))
whole
#<Augmentable interpreter env 1 1> rest)))
)))
(progn (let ((y (m (f pi)))) (print y))))))))))
The two opaque functions captured in the rewritten code are the two surrounding flet function and macrolet expander function. These remain interpreted functions if and when they are called inside the inner compiled code body. Both outer flet and labels functions are accessed by inner flet functions -- that an outer labels function can call itself is a property of that outer lexical function and there is no distinction for these inner functions that simply funcall the outer functions.
Block names
block and return-from are lexical constructs, but when transfer must cross a lambda boundary even in compiled code they must be rewritten in terms of catch and throw, which are dynamic constructs. Interpreted execution always does this transformation, so the following interpreted code
(block compute (ensuring-compiled-body (return-from compute (* 2 pi))))
would be rewritten as
(catch '(compute)
(funcall
(compile nil
(lambda nil
(block #:g18
(throw '(compute)
(block compute
(return-from #:g18
(progn (return-from compute (* 2 pi)))))))))))
where the two paired '(compute) catch tags and the two #:g18 gensyms are eq.
Unfortunately, establishing a catch has a small runtime cost, but this cannot be avoided unless the code body to be compiled were walked to determine whether it contains a return from that block. Doing so would be possible but would add complexity.
Tagbody tags
tagbody and go tags are also lexical constructs, similar to block names. They need similarly to be rewritten in terms of catch and throw. Interpreted execution already rewrites tagbody tags and go using catch and throw, so we need only [sic] wrap the whole lambda body in a tagbody, and add each of the visible tagbody tags into that tagbody with a throw that throws out to the proper catcher. This form
(let ((ret nil))
(dotimes (i 10 (nreverse ret))
(ensuring-compiled-body
(when (evenp i) (go skip))
(push (* i i) ret))
skip))
is rewritten as the following. It is a little complex, but see the added comments.
(let ((ret nil))
(dotimes (i 10 (nreverse ret))
(funcall
(compile nil
(lambda nil
(symbol-macrolet ((ret (car '(nil))) (i (car '(0))))
(block #:g689
(tagbody
(return-from #:g689 ; This executes if none of the go
; to outer tags are executed and
; the block completes normally.
(block #:g688
(throw '(nil) ; This is just noise provided by
; the implicit block nil
; established by the dotimes, to be
; used if anything in the dotimes
; body did a return. It is not the
; same catch tag as the one a few
; lines below.
(block nil
(return-from #:g688
(progn (when (evenp i) (go skip))
(push (* i i) ret)))))))
skip
(throw '(skip) ; The catch tag '(skip) is the tag
; used internally by interpreted
; execution to implement go tags.
; Its target is the "skip" in the
; interpreted dotimes tagbody
; below.
'nil)
(go skip) ; This just silences any unused tag
; warnings from the compiler.
))))))
skip))
Caching
Although the Allegro CL compiler is fast, compiling is only advantageous if compilation takes less time than the time gained by compiled execution. (This would never be the case for the trivial examples above.) In addition, compilation is invoked each time an ensuring-compiled-body form is executed. This would be extremely expensive inside a loop, so there is a primitive caching facility for the compiled functions created the macro. If the environment and the code body are both is the same, the previously-compiled function is reused. An environment is the same if no binding contours have been entered or exited for any of the four lexical environment components. Thus, the following form would call compile three times, not fifteen times.
(let (r)
(dotimes (i 3 (nreverse r))
(dotimes (j 5)
(ensuring-compiled-body (push (* (1+ i) (1+ j)) r)))))
Each time the inner dotimes is first entered, there is a new binding of j, but on each iteration there is no new binding.
Conclusion
This is a new experimental facility that is not intended to have wide applicability. But its workings are an interesting study in Common Lisp semantics and how code-rewriting macros can do powerful (if not entirely portable) things.
If you have any questions about the interface or suggestions, please email us at support@franz.com.
| Copyright © 2023 Franz Inc., All Rights Reserved | Privacy Statement | 
|
|
|
|
|
|