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

**This assignment relies on your successful completion of a7.**

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

- If you haven't done so, you might consider reading the ParentheC paper,
*Using ParentheC to Transform Scheme Programs to C or How to Write Interesting Recursive Programs in a Spartan Host (Program Counter)*. It is slightly out of date viz. registerization, but can still prove a useful resource. - Download pc2c.rkt, and if you haven't already, also download parenthec.rkt.
- You will also need to make use of the following test programs.

(printf "Simple lambda calculus test: ~s\n" (value-of-cps (exp_app (exp_app (exp_lambda (exp_lambda (exp_var 1))) (exp_const 5)) (exp_const 6)) (empty-env) (empty-k)) ; Factorial of 5...should be 120. (printf "Fact 5: ~s\n" (value-of-cps (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)))))))) (empty-env) (empty-k)) ; Test of capture and return...should evaluate to 24. (printf "Capture/return test: ~s\n" (value-of-cps (exp_mult (exp_const 2) (exp_capture (exp_mult (exp_const 5) (exp_return (exp_var 0) (exp_mult (exp_const 2) (exp_const 6)))))) (empty-env) (empty-k)) ;; (let ([fact (lambda (f) ;; (lambda (n) ;; (if (zero? n) ;; 1 ;; (* n ((f f) (sub1 n))))))]) ;; ((fact fact) 5)) (printf "Other fact 5: ~s\n" (value-of-cps (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))) (empty-env) (empty-k)))

Your assignment is to complete the transformation of your interpreter from a7 to a version we can translate to C. When your interpreter is complete, turn it into C programs using ParentheC, and run the four test programs provided. Here are the steps you will need to accomplish. 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.

- Add the four programs to the file containing your interpreter, and make sure it successfully runs these test programs.
- Transform your closure constructor to a
`define-union`

, change the`match`

in`apply-closure`

to instead use`union-case`

, and ensure that your constructor invocations are preceeded with`clos_`

, or something other than`clos`

if you use a different name for your union. Make sure to remove the backquotes and commas in what was your`match`

expression. - Transform your environment constructors to a
`define-union`

, change the`match`

in`apply-env`

to instead use`union-case`

, and ensure all constructor invocations are preceeded with`envr_`

, or something other than`envr`

if you use a different name for your union. Make sure to remove the backquotes and commas in what was your`match`

expression. - Transform your closure constructors to a
`define-union`

, change the`match`

in`apply-k`

to instead use`union-case`

, and ensure all constructor invocations are preceeded with`kt_`

, or something other than`kt`

if you use a different name for your union. Make sure to remove the backquotes and commas in what was your`match`

expression. - Add a function
`main`

(of no arguments, whose body is a single`(begin …)`

) block (no nested begins) that executes in sequence your four test programs. At the bottom of your file, invoke main (i.e.`(main)`

). - Transform all your serious function calls to our A-normal form style, by adding
`let*`

above your serious calls, and ensuring that the names of the actual parameters to the serious calls are exactly the names of the formal parameters in the definition. - Registerize the interpreter. Turn each
`let*`

expression to a`begin`

block, the former`let*`

bindings to`set!`

expressions, and whose body is the invocation of a function of no arguments. Change all serious functions to be functions of no arguments. Define your global registers using`define-registers`

at the top of the program. - Change all of your
`(define name (lambda () …))`

statements to use`define-label`

. - Define your program counter at the top of the program.
- Convert all label invocations into assignments to the program counter, and then add calls to
`mount-trampoline`

and`dismount-trampoline`

. Not this will require modifying`empty-k`

in your`kt`

union, and the`empty-k`

clause in the`union-case`

inside`apply-k`

. - Comment out the lines
`#lang racket`

,`(require “parentheC.rkt”)`

, and your invocation of`main`

, and save a copy of this file named`interp.pc`

. - In a
**fresh**Racket REPL with**no**other files loaded,`(require “pc2c.rkt”)`

. This should load without errors. Then, you should be able to type`(pc2c “interp.pc” “a9.c” “a9.h”)`

, which will generate C code from your interpreter. Compile the C program with the C compiler of your choice. The SOIC linux machines have`gcc`

installed, and you can find here binaries for many different systems. Run the resulting executable, verifying that you see the correct output.

Save a new copy of your interpreter after you finish each 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 programs. - This assignment is due on
**Wednesday, March 25th 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 3rd**. - You must book an appt in advance (at least 1 day in advance).
**Make sure you get an email confirming your appointment.**

- Remember: successful completion of this assignment and code review 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.