CS 394P: Partial Evaluation Exercise
Due: March 7, 2005.
The goal of this exercise is to gain experience with partial evaluation
and to see examples of its use.
- Examine the code in the file /projects/cs394p/mix.lsp and
understand how the mix function works. Try the first few
examples at the top of the file, and some of your own.
- Try specializing the power function to form the
specialized function cube for the case where the desired power is
(fnmix 'power '(x 3))
(specialize 'power '(x 3) 'cube) ; cube(x) = power(x,3)
(fndef 'cube) ; specialized code
(cube 4) ; try it
(fnmix 'power '(x 22)) ; a larger example
Trace the function mix while specializing the cube function
and compare it to Lisp evaluation. A Lisp evaluator for Common
Lisp is lispinlisp.lsp, and a trace on the factorial function is
in lispinlisp.trace .
(m-defun power (x n) ...) ; same but use m-defun
(m-defun square (x) (* x x))
(trace m-eval m-apply)
(m-eval '(power 4 3) nil)
- The Consel and Danvy paper uses as an example a formatted printing
function similar to format in Lisp or printf in C.
Most uses of these functions have a constant formatting string.
Try specializing the simplified formatting function printfn
for a constant formatting string:
(specialize 'printfn '('(F D C) lst) 'myprint)
(myprint (list 3.14 77 #\!))
- The first Futamura projection states that specialization of an
interpreter with respect to a constant source program is equivalent
to compilation. Examine the function interp, which interprets an
arithmetic expression in Lisp, assuming a stack machine as the underlying
CPU. Demonstrate that specialization of this interpreter with respect
to a constant expression compiles a program to compute the expression
on the stack machine. Try some other expressions that you make up.
(topinterp '(* 3 (+ 4 5))) ; interpret this expr
(specialize 'topinterp ; specialize topinterp
'('(* a (+ b c))) ; for this expression
'expr1 ; to form this function
'(a b c)) ; with these arguments
(fndef 'expr1) ; look at compiled code
(expr1 3 4 5) ; see if it works
- Try specializing the functions mysubst, myequal,
match, and interpc with constant arguments.
The function match will specialize to a large amount of code;
also try the version in the file match.lsp . Execute each of the
specialized functions with appropriate arguments to verify that it works.
- Write a function of your choice and specialize it with one or
more constant arguments. Partial evaluation is most effective on functions
where some arguments are tested by if statements, and those arguments
tend to be constant when the function is used.
patmatch.lsp Pattern Matcher
patm.lsp Pattern Matcher
match.lsp Alternative version of Pattern Matcher
mix.lsp Partial Evaluator