ps4
Folders and files
Name | Name | Last commit date | ||
---|---|---|---|---|
parent directory.. | ||||
Your job for this assignment is to implement a compiler that maps Scish, a subset of Scheme, down to Cish. I have extended Cish with four new things: *exp -- reads the word at the address denoted by exp. The address must be word-aligned. *exp1 = exp2 -- places the value of exp2 in memory at the address denoted by exp1 and returns the value of exp2 as the result. The address must be word aligned exp(exp1,...,expn) -- function names are now first-class values. For instance, you can assign a function name such as "fact" to a local variable x and then invoke the function via x(n). malloc(n) -- allocate n bytes worth of storage, and return a (word-aligned) pointer to the storage. I would encourage you to extend your Cish compilers to support these new constructs. (it's not very hard) but you do not need to do this now. Instead, you can use the Cish interpreter (see cish_eval.ml). Alternatively, you can change the pretty-printer for Cish to spit out valid C code and use a standard C compiler to test things out. The file scish_ast.ml gives the abstract syntax for Scish programs, and the files scish_lex.mll and scish_parse.mly provide a rudimentary lexer and parser for Scish. Finally, the file scish_eval.ml provides a direct interpreter for Scish, based on the environment and closure approach discussed in class. You are to complete the function compile_exp in scish_compile.ml. This function takes in a Scish expression and produces a Cish program. An example input is in sample_input.scish and the output generated by my compiler is in sample_output.scish. Recall that compiling a lambda expression should (a) generate a new Cish function f that takes one parameter---the environment (b) produce as a value a closure which is a pair of the function name f and the current environment. Compiling an application (e1 e2) should cause both e1 and e2 to evaluate to values v1 and v2, and v1 should be a closure. Extract the function pointer and environment of the closure, extend the closure's environment by adding in v2, and then finally invoke the function with the extended environment. To compile a variable, you'll need to generate code which looks up the variable's value in the environment. There are a number of ways to handle this as discussed in class. The cish_eval interpreter includes some rudimentary debugging support to enable you to trace through the execution of a program. In particular, setting the debug_flag to true will cause the interpreter to print out the result of evaluating each expression in the program, as well as the contents of (allocated) memory. Feel free to extend the evaluator with additional debugging support as you see fit. Running make in the current directory will generate 2 executables ps4_scish and ps4_cish that can be used to test your compiler. The former expects a scish file and emits cish code. The latter reads in a stream of cish code from stdin and evaluates it using cish_eval.ml. Thus, to test your compiler, you can run something like: ps4_scish test.scish | ps4_cish to quicky get an evaluated answer. Feel free to change how this works ( by modifying cish.ml and scish.ml) if you want to test your compiler differently. For the interested, you can copy in your cish-to-mips compiler from the previous assignment and compile from scish to mips. ****************************************************************** Extra Credit: ------------- As defined, Scish provides no direct support for writing recursive functions (though you can achieve this by using a Y-combinator.) Add direct support for recursion through a new expression form: (letrec ID ( ID ) EXP) For example, I should be able to write a recursive factorial function as: (letrec fact ( n ) (if (< n 1) 1 (* n (fact (- n 1)))))