Assignment 9: ParentheC Interpreter

Your task is to transform the interpreter below into a language that can be automatically converted to C. 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. Please read the entire assignment carefully, taking note of the special notes at the end of the assignment.

Read the ParentheC/PC paper, Using ParentheC to Transform Scheme Programs to C or How to Write Interesting Recursive Programs in a Spartan Host (Program Counter), which is posted with the ParentheC code on the Notes/Examples page.
Download ParentheC.ss and pc2c.ss.

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_throw <expr> <expr>)              
              |   (exp_lambda <expr>)
              |   (exp_app <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.

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

    > (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))

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

(define-union exp
  (const n)
  (var v)
  (if test conseq alt)
  (mult rand1 rand2)
  (sub1 rand)
  (zero rand)
  (letcc body)
  (throw vexp kexp)
  (lambda body)
  (app rator rand))

(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))))]
      [(throw vexp kexp)
       ((value-of kexp env) (value-of vexp env))]
      [(lambda body) (clos_closure body env)]
      [(app rator rand)
       (apply-proc (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) (error 'pc "unbound variable")]
      [(extend arg env)
       (if (zero? num)
           arg
           (apply-env env (sub1 num)))])))

(define-union clos
  (closure code env))

(define apply-proc
  (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 throw...should evaluate to 24.
(pretty-print
 (value-of (exp_mult (exp_const 2)
              (exp_letcc
                (exp_mult (exp_const 5)
                          (exp_throw (exp_mult (exp_const 2) (exp_const 6))
                                     (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.

Warning: 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 a C program 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 your continuations representation independent.
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. Remove parens from all non-simple tail calls and add calls to mount-trampoline and dismount-trampoline. dismount-trampoline.
9. Verify that everything works in Scheme.
10. Load pc2c.ss, generate C code for your interpreter, and run the C program, verifying that you see the correct output.
In order to avoid frustration on this assignment, save a new copy of your interpreter after you finish every step. You will often need to go back to an older version of your interpreter and will save a lot of time if you have kept copies of all of them.
You should turn in a file named interp.pc that contains the exact Scheme code you used to generate your C program.
You will be required to schedule time with one of the AIs to demo your program. For full credit, you should do this during the week after the assignment is due. Submissions after the due date and demos occurring more than one week after the due date will be subject to grade reductions. The AIs will be available for demos during their normal office hours, and you may e-mail either of them if you would prefer to present your program at a different time.
You may find this tutorial on compiling ParentheC files from a windows machine to be useful: Using SSH Secure Shell for Workstations to Remotely Compile ParentheC Files. This document is designed to help you compile ParentheC programs on the steel machine, and is outdated; the version of Chez Scheme installed on steel is behind the current version. Instead, you should obtain an account for the Burrow machines. The information in this document applies to the Burrow as well, except that the address of the Burrow machines is burrow.cs.indiana.edu instead of steel.ucs.indiana.edu. If you do not have a Burrow account, you may obtain one by filling out a request form in LH201.

Remember: this assignment is required