11 Assignment 11: ParentheC Interpreter
"Code should run as fast as necessary, but no faster; something important is always traded away to increase speed."
——Richard Pattis
Preliminaries
This assignment relies on your successful completion of A10. If you haven’t successfully completed A10 and maintained the versions of your code along the way, please complete this before starting this assignment. 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.
Once you’ve done the assignment, you must meet with one of the Instructors to demonstrate your knowledge of your code. This meeting is a required part of the assignment and must take place on or before April 18.
Consider reading the ParentheC paper, Using ParentheC to Transform Scheme Programs to C or How to Write Interesting Recursive Programs in a Spartan Host. It is slightly out of date viz. registerization, but can still prove a useful resource.
Download by right clicking on a file name below and choose "Save Link As..." in your browser.
Download parenthec.rkt.
Hint: Place both these files in the same folder as your a11.rkt
You will also need to use the following define-union for expressions and main program:
(define-union expr (const cexp) (var n) (if test conseq alt) (mult nexp1 nexp2) (sub1 nexp) (zero nexp) (catch body) (throw kexp vexp) (let exp body) (lambda body) (app rator rand)) (define main (lambda () (value-of-cps (expr_let (expr_lambda (expr_lambda (expr_if (expr_zero (expr_var 0)) (expr_const 1) (expr_mult (expr_var 0) (expr_app (expr_app (expr_var 1) (expr_var 1)) (expr_sub1 (expr_var 0))))))) (expr_mult (expr_catch (expr_app (expr_app (expr_var 1) (expr_var 1)) (expr_throw (expr_var 0) (expr_app (expr_app (expr_var 1) (expr_var 1)) (expr_const 4))))) (expr_const 5))) (empty-env) (empty-k))))
Notice that this test program is not quoted data. The test program corresponds to the following program:
(let ([f (lambda (f) (lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n))))))]) (* (catch k ((f f) (throw k ((f f) 4)))) 5))
Assignment
Your assignment is to complete the transformation of your interpreter from A10 to a version we can translate to C. When your interpreter is complete, turn it into C programs using pc2c, and run the test program 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.
Below #lang racket, add the line (require "parenthec.rkt") Next add the expr define-union to your file, change the match-expression in value-of-cps to instead be a union-case-expression. Consult the ParentheC paper or the example from class to see how to do this. Make sure to remove the backquotes and commas in the patterns of what was your match expression. Add main (from Preliminaries) to the bottom of your file, and make sure it returns 120 when you invoke it.
Rename the formal parameters of serious calls to the same name surrounded by asterisks; for example, v becomes *v*. Then transform all your serious function calls to our A-normal form style, by adding let* above your serious calls. Ensure 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 will become set! expressions, and the body becomes 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.
Transform your closure constructor to a define-union with the name clos, change the match in apply-closure to instead use union-case, and ensure that your constructor invocations are preceded 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 the patterns in what was your match expression.
Transform your environment constructors to a define-union with the name envr, change the match in apply-env to instead use union-case, and ensure all constructor invocations are preceded 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 the patterns in what was your match expression.
Transform your continuation constructors to a define-union with the name kt, change the match in apply-k to instead use union-case, and ensure all constructor invocations are preceded 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 the patterns in what was your match expression.
Change all of your (define name (lambda () ...)) statements to instead use define-label. Define your program counter at the top of the program using define-program-counter.
Convert all label invocations into assignments to the program counter, and then add calls to mount-trampoline and dismount-trampoline. Note this will require modifying empty-k in your kt union, and the empty-k clause in the union-case inside apply-k. Remember to invoke the main label with no arguments at the bottom of your file. On the last line of main, print the register containing the final value of the program, e.g. (printf "Fact 5: ~s\n" *v*) See the parentheC document for notes on these steps.
Comment out the lines,
#lang racket (require "parentheC.rkt") and your invocation of main (that is (main)) if you added it to your file.
At this point you need to choose which runtime and language you want to use for the compilation of this ParentheC/Pyrantasys/Java/Typescript/Rust code. Yes, you read it right, we have five choices!
Now save a copy of this file with the name interp.pc depending on your choice and follow the steps below.
For C
Open and run pc2c.rkt. This should load without errors. In the associated Racket REPL with no other files loaded, type(pc2c "interp.pc" "a11.c" "a11.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. If you’re on Windows, try TCC. If you’re on Mac, try running clang from your terminal, as it should come with your system. Alternately, you could use an online C compiler.Run the resulting executable, verifying that you see the correct output. Note: Mac users need to add a "#include <time.h>" at the top of their generated .c file to avoid getting an error.
For Python
Open and run pc2py.rkt. This should load without errors. In the associated Racket REPL with no other files loaded, type(pc2py "interp.pc" "a11.py")
which will generate Python 3.10 code from your interpreter.You need to have Python 3.10 installed on your machine and on your path. If you don’t have it get Python 3.10 installation file for your operating system from here.
If you like to use virtual environments you can do that too. You need to install the following packages in the "Python 3.10" environment
greenlet library by using pip3 install greenlet
Run the resulting Python file using python3 a11.py and verify that you see the correct output.
For JAVA
Open and run pc2j.rkt. This should load without errors. In the associated Racket REPL with no other files loaded, type(pc2j "interp.pc" "interp.java")
which will generate JAVA code from your interpreter.You will need to have JAVA 17 SDK installed on your system. If you have an older JAVA version, you can try running it and let the team know.
If you don’t have JAVA you can get it from here, select your operating system and download the installer/archive for the JAVA SDK and Runtime. On MacOS and Windows you can use the installers and for Linux you can simply extract it and use the <extracted-folder>/bin/java and <extracted-folder>/bin/javac from there. Otherwise, java and javac commands will be in your system path.
After you are done run the following lines of commands one by one in your interp.pc directory-
javac interp.java
java interp
The first command compiles your JAVA program, and the next will run your resulting JAVA file, which is where you can verify if you get the correct output.
For TypeScript
Open and run pc2ts.rkt. This should load without errors. In the associated Racket REPL with no other files loaded, type(pc2ts "interp.pc" "interp.ts")
which will generate TypeScript code from your interpreter.You will need to have Node and npm installed on your system.
If you don’t have Node and npm you can get it from here, select your operating system and download the installer/archive. On MacOS and Windows you can use the installers and for Linux you can find it on your favourite package installer’s repositories.
After this step you need to install ts-node command for running TypeScript directly in Node. Use the following command (You may need ‘sudo‘ privileges):
npm install -g ts-node typescript @types/node
After you are done run the following lines of commands one by one in your interp.pc directory-
ts-node interp.ts
This should compile your TypeScript program and run it. Verify that you get the correct output.
For Rust
Note: ParentheC for Rust is still in its early stage. If you find any bug when using this tool, send an email to yafyang@iu.edu.
Open and run pc2rs.rkt. This should load without errors. In the associated Racket REPL with no other files loaded, type(pc2rs "interp.pc" "interp.rs")
which will generate Rust code from your interpreter.You will need to have Rust installed on your system.
If you don’t have Rust you can get it from here. If you follow the steps in this link, components like the package manager cargo, the code formatter rustfmt, etc. will also be installed.
Then in a terminal, you can enter the directory where "interp.pc" is put, then compile and run "interp.rs" in the following way:
cargo new --edition 2021 interp mv interp.rs interp/src/main.rs cd interp cargo add rand cargo run This should compile and run your program. You can ignore the warnings during compilation. Verify that you get the correct output.
Just Dessert
This time you have two choices for the dessert. Choose either to get bonus (or if you want more, do both of them!).
Add a call/cc form to your interpreter that behaves like Racket’s call/cc. Change the test program to one that uses call/cc and send this, along with any other required changes, in an email to your grader.
Choose your favourite language other than C, Python, Java, Typescript, and Rust, then implement a parentheC translator from the last step of a11 to that language. The implementation for pc2c.rkt and pc2rs.rkt should be a good reference to start.