Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!udel!rochester!pt.cs.cmu.edu!o.gp.cs.cmu.edu!ram
From: ram+@cs.cmu.edu (Rob MacLachlan)
Newsgroups: comp.lang.lisp
Subject: Re: Partial evaluator sought
Message-ID: <1991May10.171712.6284@cs.cmu.edu>
Date: 10 May 91 17:17:12 GMT
References: <13521@pasteur.Berkeley.EDU>
Sender: netnews@cs.cmu.edu (USENET News Group Software)
Organization: School of Computer Science, Carnegie Mellon
Lines: 54


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)