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.

1. 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.

2. 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)
   

3. 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 #\!))
   

4. 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
   

5. 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.

6. 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.

Files:

patmatch.lsp    Pattern Matcher
patm.lsp        Pattern Matcher
match.lsp       Alternative version of Pattern Matcher
mix.lsp         Partial Evaluator