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 a constant.(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`.(load "/projects/cs394p/lispinlisp.lsp") (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) (fndef '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