Assignment 9: ParentheC Interpreter

“Code should run as fast as necessary, but no faster; something important is always traded away to increase speed.”

Your task is to transform the interpreter below into a language that can be automatically converted to C and Java. We will be using ParentheC for this task, so you'll be CPSing and registerizing the interpreter below before making final modifications to make it ready for ParentheC.

You cannot receive a grade for this course until you complete this assignment and demonstrate your understanding with one of the instructors. See the end of this page for more details.

EDIT: A couple of persons pointed out possible improvements in our pc2j file. I've implemented an number of those and uploaded a new version. Let me know if you encounter any difficulties.

• If you haven't done so already, read the ParentheC paper, Using ParentheC to Transform Scheme Programs to C or How to Write Interesting Recursive Programs in a Spartan Host (Program Counter).
• Download parentheC.ss, pc2c.ss, and pc2j.scm.

The language we will be using for the interpreter in the assignment is characterized by the grammar here:

          <expr>   ::=  (exp_const <integer>)
                    |   (exp_var <integer>)
                    |   (exp_if <expr> <expr> <expr>)
                    |   (exp_mult <expr> <expr>)
                    |   (exp_sub1 <expr>)
                    |   (exp_zero <expr>)
                    |   (exp_letcc <expr>)
                    |   (exp_abort-with <expr> <expr>)
                    |   (exp_let <expr> <expr>)              
                    |   (exp_lambda <expr>)
                    |   (exp_app <expr> <expr>)
                    |   (exp_abort-case <expr> <expr> <expr>)

This is quite simple, and identical to the other languages that we have written interpreters for. However, we now explicitly tag all language constructs. When we refer to a variable (using exp_var) we refer to the variable's lexical address.

We provide a parser that will convert normal Scheme-like syntax into the language we are using on this assignment. For example,

> (load "parser.ss")
> (parse '((lambda (a b c) (* a c)) 5 6 7))
 
          (exp_app
            (exp_app
              (exp_app
                (exp_lambda
                  (exp_lambda
                    (exp_lambda (exp_mult (exp_var 2) (exp_var 0)))))
                (exp_const 5))
              (exp_const 6))
            (exp_const 7))

Use this to generate tests for your program. Notice that the output is curried for you. Note also that our parser produces quoted output, but your value-of will not take quoted expressions as input.

Here is a fully-functioning interpreter that implements this language for us. It uses the ParentheC union type to represent the language.

(load "parenthec.ss")
 
(define-union exp
  (const n)
  (var v)
  (if test conseq alt)
  (mult rand1 rand2)
  (sub1 rand)
  (zero rand)
  (letcc body)
  (abort-with vexp kexp)
  (let vexp body)
  (lambda body)
  (app rator rand)
  (abort-case vexp k1exp k2exp))
 
(define value-of
  (lambda (expr env)
    (union-case expr exp
      [(const n) n]
      [(var v) (apply-env env v)]
      [(if test conseq alt)
       (if (value-of test env)
	   (value-of conseq env)
	   (value-of alt env))]
      [(mult rand1 rand2) (* (value-of rand1 env) (value-of rand2 env))]
      [(sub1 rand) (- (value-of rand env) 1)]
      [(zero rand) (zero? (value-of rand env))]
      [(letcc body)
       (call/cc
	(lambda (k)
	  (value-of body (envr_extend k env))))]
      [(abort-with vexp kexp)
       ((value-of kexp env) (value-of vexp env))]
      [(abort-case vexp k1exp k2exp) (let ((v (value-of vexp env)))
				       (if (zero? v)
					   ((value-of k1exp env) v)
					   ((value-of k2exp env) v)))]
      [(let vexp body)
       (value-of body (envr_extend (value-of vexp env) env))]
      [(lambda body) (clos_closure body env)]
      [(app rator rand)
       (apply-closure (value-of rator env) (value-of rand env))])))
 
(define-union envr
  (empty)
  (extend arg env))
 
(define apply-env
  (lambda (env num)
    (union-case env envr
      [(empty) (errorf 'env "unbound variable")]
      [(extend arg env)
       (if (zero? num)
	   arg
	   (apply-env env (sub1 num)))])))
 
(define-union clos
  (closure code env))
 
(define apply-closure
  (lambda (c a)
    (union-case c clos
      [(closure code env)
       (value-of code (envr_extend a env))])))
 
 
					; Factorial of 5...should be 120.
(pretty-print
 (value-of (exp_app
	    (exp_lambda
	     (exp_app
	      (exp_app (exp_var 0) (exp_var 0))
	      (exp_const 5)))
	    (exp_lambda
	     (exp_lambda
	      (exp_if (exp_zero (exp_var 0))
		      (exp_const 1)
		      (exp_mult (exp_var 0)
				(exp_app
				 (exp_app (exp_var 1) (exp_var 1))
				 (exp_sub1 (exp_var 0))))))))
	   (envr_empty)))
 
					; Test of letcc and abort-with...should evaluate to 24.
(pretty-print
 (value-of
  (exp_mult (exp_const 2)
	    (exp_letcc
	     (exp_mult (exp_const 5)
		       (exp_abort-with (exp_mult (exp_const 2) (exp_const 6))
				       (exp_var 0)))))
	   (envr_empty))) 
 
;; (let ([fact (lambda (f)                                                      
;;               (lambda (n)                                                    
;;                 (if (zero? n)                                                
;;                     1                                                        
;;                     (* n ((f f) (sub1 n))))))])                              
;;   ((fact fact) 5))                                                           
 
(pretty-print
 (value-of (exp_let
	    (exp_lambda
	     (exp_lambda
	      (exp_if
	       (exp_zero (exp_var 0))
	       (exp_const 1)
	       (exp_mult
		(exp_var 0)
		(exp_app
		 (exp_app (exp_var 1) (exp_var 1))
		 (exp_sub1 (exp_var 0)))))))
	    (exp_app (exp_app (exp_var 0) (exp_var 0)) (exp_const 5)))
	   (envr_empty)))
 
;; first abort-case test
(pretty-print
 (value-of (exp_letcc
	    (exp_mult
	     (exp_const 2)
	     (exp_letcc
	      (exp_abort-case (exp_const 0) (exp_var 1) (exp_var 0)))))
	   (envr_empty)))
 
;; second abort-case test
(pretty-print
 (value-of (exp_letcc
	    (exp_mult
	     (exp_const 2)
	     (exp_letcc
	      (exp_abort-case (exp_const 1) (exp_var 1) (exp_var 0)))))
	   (envr_empty)))

Note that the programs we pass to value-of do not have a quote in front of them. Why is this? Because the programs are no longer lists. We are actually passing a series of nested unions created by calling these tagged constructors.

Note: ParentheC does not support the pretty-print command, so you will need to use printf in your main function to display the results of the execution.

Your assignment is to turn this interpreter into C and Java programs using ParentheC, and run the factorial and letcc test programs. Here are the steps you will need to accomplish:

1. CPS this interpreter.
2. Make the interpreter representation-independent with respect to continuations (using functional reps).
3. Make your continuations be data structures (tagged lists).
4. Make your continuations be ParentheC unions.
5. Registerize the interpreter.
6. Change all of your (define name (lambda () …)) statements to use define-label.
7. Add a function main (of no arguments) that does whatever computation you want your program to accomplish.
8. Convert non-simple tail calls to assignments to the program counter, and then add calls to mount-trampoline and dismount-trampoline.
9. Verify that everything works in Scheme.
10. In a fresh Scheme process with no other files loaded, load pc2c.ss, generate C code for your interpreter, compile the C program, and run the resulting executable, verifying that you see the correct output. (If you don't know how to do this step, check with the AIs for help.)
11. In a fresh Scheme process with no other files loaded, load pc2j.scm, generate Java code for your interpreter, compile the Java program, and run the resulting executable, verifying that you see the correct output. For instructions on using pc2j, see the comments at the top of the file.

Save a new copy of your interpreter after you finish every step. We will expect you to have all of these intermediate files available during your demonstration. Also, you will often need to go back to an older version of your interpreter and having copies of all of them will save a lot of time.

• You should turn in a file named interp.pc that contains the exact Scheme code you used to generate your C and Java programs.
• This assignment is due on Wednesday, March 27th at 11:59 p.m. Once you've done the assignment, you must meet with one of the AIs to demonstrate your knowledge of your code. This meeting is a required part of the assignment and must take place on or before Friday, April 5th.
• Remember: this assignment is required in order to receive a grade for this course. For assignments handed in after the due date, credit is reduced proportionally to lateness.

Add a callcc form to your interpreter that behaves like Scheme's call/cc. Include at least one test program, as well as any necessary changes to the parser or other files in an email to your instructor.