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

In this assignment, you will finish the project of building an interpreter that runs on a low-level machine. You will transform your interpreter from A10 to a low-level language such as C, and run the test program provided.

This assignment relies on your successful completion of A10. Before you start this assignment, you must finish A10. Save a copy of your interpreter code after each step. 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 scheduled meeting is a required part of the assignment and must take place on or before April 18. During your demonstration, we will expect you to have all of the intermediate files containing your interpreter code after each step of A10 and A11.

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.

Assignment

Below are the steps you will need to accomplish. As in A10, 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. Download parenthec.rkt and put it in the same folder as your a11.rkt. Don’t use “Save Page As” or “Save As”; use “Save Link As” or “Download Linked File” in your Web browser. If you can’t find the command, try right-clicking or two-finger-tapping or long-pressing.

   Below #lang racket, add the line (require "parenthec.rkt")

   Add this union definition for expressions to your file:

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

   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 the following test program to the bottom of your file:

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

   Make sure your interpreter returns 120 when you invoke (main)

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

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

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

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

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

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

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

9. Comment out the lines

   #lang racket

   (require "parentheC.rkt")

   and your invocation of main (that is (main)) if you added it to your file.

   Save a copy of this file with the name interp.pc

10. 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! Download

    • pc2c.rkt (for generating C code) OR

    • pc2py.rkt (for generating Python code) OR

    • pc2j.rkt (for generating Java code, tested with Java 17) OR

    • pc2ts.rkt (for generating TypeScript code and by extension JavaScript code) OR

    • pc2rs.rkt (for generating Rust code)

    and put it in the same folder as your a11.rkt. Don’t use “Save Page As” or “Save As”; use “Save Link As” or “Download Linked File” in your Web browser. If you can’t find the command, try right-clicking or two-finger-tapping or long-pressing.

11. • For C

      Open and run pc2c.rkt. This should load without errors. In the Interactions window, 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 Interactions window, 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 the Python 3.10 installation file for your operating system from here. If you like to use virtual environments, you can do that too.

      In the Python 3.10 environment, you need to install the greenlet library package 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 Interactions window, 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 to use it and let us 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; 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.

      With Java installed, run the following two 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 Interactions window, 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; for Linux, you can find it on your favorite package installer’s repositories.

      With Node installed, you need to install the 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

      With Node and ts-node installed, run the following command 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

      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 Interactions window, 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!).

1. Our language already has catch, which is like let/cc in Racket. Add to our language a special form that is like call/cc in Racket:

   (define-union expr

   ...

   (callcc))

   For instance, (expr_app (expr_callcc) (expr_callcc)) in your interpreter should work like (call/cc call/cc) in Racket. Change the test program to one that uses this new form. Send your changes in an email to your grader.

2. Choose your favorite language other than C, Python, Java, TypeScript, and Rust, then implement a ParentheC translator from the interp.pc step above to that language. The implementation for pc2c.rkt and pc2rs.rkt should be a good reference to start.