Skip to content

Latest commit

 

History

History
 
 

ps4

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