Assignment 9: ParentheC Interpreter

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

Introduction

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.

Preliminaries

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

Assignment

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.

  1. Add the four programs to the file containing your interpreter, and make sure it successfully runs these test programs.
  2. 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.
  3. 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.
  4. 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.
  5. 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)).
  6. 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.
  7. 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.
  8. Change all of your (define name (lambda () …)) statements to use define-label.
  9. Define your program counter at the top of the program.
  10. 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.
  11. Comment out the lines #lang racket, (require “parentheC.rkt”), and your invocation of main, and save a copy of this file named interp.pc.
  12. 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.

Just Dessert

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.

 

assignment-9.txt · Last modified: 2015/03/23 20:16 by jhemann