CS 6983 Special Topics: The Technology of Lambda Olin Shivers Homework 1 Due 2025/1/18 midnight by email This assignment has you go forth and try out the nanopass compiler framework on an easy, warmup project, before we get to work doing lambda-calculus languages with it. So the emphasis is on learning the details of the infrastructure, as opposed to the problem we are solving with it. * Read up on nanopass --------------------- See the Racket doc at https://docs.racket-lang.org/nanopass/index.html Read the nanopass papers posted on the course web site. Figure out how to access the nanopass machinery from within Racket. * Compiling Calc ---------------- The big picture is playing with a compiler that goes from a calculator language, which we'll call Calc, to a stack language, which we'll call Third (because it's a little bit less than Forth -- which you can look up on Wikipedia). Calc includes at least +, *, -, / and numeric constants All concrete grammar (source, target and intermediate languages) should be in s-exp form of the kind from which nanopass can parse and to which it can unparse. An example Calc term: (* (- 4 2) (+ (* 4 3 2) 2 (- 15 10))) Note that multiplication and addition are n-ary, as shown in the example above. (+) => 0 0-ary -- 0 arguments. Produce identity. (+ 3) => 3 1-ary -- 1 argument. Produce that. (+ 3 2) => 5 (+ 3 2 1) => 6 Minus is unary or binary: (- (* -2 3)) => 6 Unary -- 1 argument (- 3 5) => -2 Binary -- 2 arguments Encode your design for Calc as a language in nanopass. * Calc to Calc2 --------------- Next, implement a pass that transforms a Calc program to an intermediate language Calc2, which is exactly Calc, but the addition and multiplication operators take exactly two arguments. * Simplifier ------------ Add a simple simplifier pass that walks a Calc2 tree looking for local simplifications. For example: (* 0 e) => 0 (+ 0 e) => e (* 1 e) => e But don't do constant folding, else you'll have nothing left to execute! * Third language ---------------- Third is a stack language. Here's an example: (begin 2 ; ... 2 3 ; ... 2 3 4 ; ... 2 3 4 (*) ; ... 2 12 (+)) ; ... 14 A program is a sequence of commands that operate on a stack. If a command is a numeric constant, it is pushed on the stack. Operators pop their arguments off the stack, then push their results. Details: - Subtraction, being non-associative, works like this: ... n m => ... m-n where m is the value on the top of the stack, and n is the underneath. - The machine halts with an error condition to handle dynamic errors. - (-) is the command for binary subtraction. (neg) is the command for unary negation. 1. Define Third as a nanopass language 2. Write an interpreter in Racket that takes a Third program and an initial stack, executes the program, and returns the resulting stack. * Calc2 to Third ----------------- Write a pass in nanopass that maps a Calc2 program to a Third program. * End-to-end -- RCRP loop ------------------------- Write a calculator with a read-compile-run-print loop: read an s-expression, compile it to Third, execute the Third code in your interpreter with an initial empty stack, print out the answer, then loop. No sophisticated error handling required; feel free to error out on syntax errors in the compiler, or dynamic errors in your Third interpreter. * Extensions ------------ Do one or two more things. I am deliberately avoiding suggestions. ------ OK, here's one. How could you add conditionals to the calculator language? E.g., (* 3 (if (< 3 (+ 10 7)) 8 2)) Add a "higher order" feature to Third. The CODE command (CODE cmd ...) pushes a code block with the given commands on the stack as a value. The EXEC command (EXEC) pops a block of code off the top of the stack and adds it to the front of the program currently being executed. Add the (SELECT) command, which pops three values off the stack ... test then else where ELSE is the top-of-stack value. If TEST is the number zero, push ELSE; if a non-zero number, push THEN; otherwise error halt. So here's the above program in Third: 3 3 10 7 (+) (<) (code 8) (code 2) (select) (exec) (*) ------ Add boolean expressions to the grammar of Calc as a separate non-terminal from numeric expressions: AND, OR, NOT, <, >, <=, >=, =. Now you have a language with two non-terminals, which you can use to further explore nanopass a little bit. You can combine this with the above conditional extension, of course. ----- Add a LET form to CALC, and a "register bank" to the Third machine mapping natural numbers to values to the Third machine & language, say with commands (GET ) ; Push the value of register (SET ) ; Pop a value and store into register . The register bank holds an arbitrary number of registers. Now you will need to augment Calc-to-Third passes to pass down a symbol table as you walk the Calc term, so you can exercise this feature of nanopass. ------ Don't get too carried away with your linguistic extensions; the point is really just to try out features of nanopass.