boyland@sequoia.Berkeley.EDU (John B. Boyland) (05/10/91)
I'm looking for a general purpose Common Lisp partial evaluator; a function which evaluates pure Lisp code if all values are known: Examples: (partial-eval '(let ((x 5)) x)) === (values 5 t) (partial-eval '(let ((x 5)) y)) === (values nil nil) (the second value indicates success/failure) I could write one, but it seems like such a standard tool, that someone must have done it already. John Boyland (boyland@sequoia.berkeley.edu)
barmar@think.com (Barry Margolin) (05/10/91)
In article <13521@pasteur.Berkeley.EDU> boyland@sequoia.Berkeley.EDU (John B. Boyland) writes: >I'm looking for a general purpose Common Lisp partial evaluator; >a function which evaluates pure Lisp code if all values are known: The following should work in a Common Lisp that includes the condition system: (defun partial-eval (form) (handler-case () (values (eval form) t) ((or unbound-variable undefined-function) (values nil nil)))) Actually, I would suggest a macro form, so that the form would be evaluated in the correct lexical context: (defmacro partial-eval (&body body) `(handler-case () (progn .,body) ((or unbound-variable undefined-function) (values nil nil)))) This is similar to the definition of WITHOUT-ERRORS, except that it only catches certain errors. Another difference in this version is that it returns all the values of the body in the non-error case. If the application needs to distinguish the error from non-error case, then it must make sure that NIL, NIL is not a valid set of values of the body. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
ram+@cs.cmu.edu (Rob MacLachlan) (05/11/91)
The CMU Common Lisp compiler (Python) does partial evaluation as part of its
suite of optimizations. Unfortunately, Python doesn't really do
source-to-source transformation (it optimizes a lower-level flow-graph
representation), so you can't easily separate out the code that does this
optimization.
Actually, as I understand the terminology, what you want to do might well be
called "constant folding", since you are only interested in whether an
expression is completely evaluable. In partial evaluation, the optimizer
evaluates constant portions of the program at compile time even when they
are nested within a non-constant computation.
I would warn you that although barmar's suggestion may meet your need, it is
not usable in a compiler, since a compiler can't blithely assume that any
variable or function definition present in the compile-time environment will
have the same value in the run-time environment. It also ignores the
possiblity that the form may have side-effects that are being relied upon.
One of the more important uses of partial evaluation in Python is the the
optimization of inline-expanded functions. Consider this definition of the
Common Lisp member function:
(declaim (inline member))
(defun member (item list &key
(key #'identity)
(test #'eql testp)
(test-not nil notp))
(do ((list list (cdr list)))
((null list) nil)
(let ((car (car list)))
(if (cond
(testp
(funcall test item
(funcall key car)))
(notp
(not
(funcall test-not item
(funcall key car))))
(t
(funcall test item
(funcall key car))))
(return list)))))
Once inline-expanded, this call is simplified to the obvious code:
(member a l :key #'foo-a :test #'char=) ==>
(do ((list list (cdr list)))
((null list) nil)
(let ((car (car list)))
(if (char= item (foo-a car))
(return list))))
Robert MacLachlan (ram+@cs.cmu.edu)