Programming Assignment 1: A Fun Intermediate Language

Getting started with ML:

1. Use CIT Sparc machines (arizona.princeton.edu). If you have a PC running Linux, then you should also be able to install ML there. You can grab a copy of the compiler from the official server at Bell Labs.
2. Edit your .cshrc or equivalent so that your path contains /u/cos320/ml.
3. Make a new directory as1 for this assignment.
4. Copy the files *.sml *.sig and *.cm from directory /u/cos320/chap1/ into as1.
5. Please, familiarize yourself with the code that is already there. Pay special attention to how it is divided into separate structures.
6. You may find the ML Basis documentation handy.
7. Run sml.
8. Inside the running ML session invoke CM.make(); to compile your code.
9. When you start modifying the code, you'll make some mistakes.  Observe the compiler's messages and fix the problems that are reported. It may be a good idea to have the ML session in a separate xterm window. You can keep a running ML session while you are debugging. Simply type CM.make(); again when you think you have fixed the problem. This procedure saves a lot of time, because you avoid starting ML over and over again.
10. Play around some more.  The more the better.  Write a file of your own and import it and test it in the top-level environment.  To quit the top-level environment, type ctrl-D (ctrl-Z if using SML under Windows).

Assignment:

Your main job, aside from familiarizing yourself with SML, is to implement an interpreter for a small part of the Fun language we will be compiling as a part of this course.  Normally, an interpreter (or a compiler) will read in a program that is expressed a pretty programmer-friendly concrete syntax from a text file and translate the pretty syntax into the abstract syntax used by the main loop of the interpreter or compiler.  The representation of a program in abstract syntax is easier for the compiler to use than a representation as, say, a single, very long string.  The process of converting concrete syntax into abstract syntax is called parsing.  Parsing is fairly complicated and since we have not covered it yet (we'll come to this topic in the following weeks), we will write programs directly in the abstract syntax for the Fun language.  The abstract syntax is described by a number of ML datatypes.  Look at the interface fun.sig and in particular at the types oper, exp, fundec and prog which describe the simple primitive operations (printing, addition, subtraction, etc.), the structured operations (if statements, call expressions, etc) function declarations and whole programs respectively.

We write an expression in the language by applying a bunch of the data constructors.  For example, supposed to want to write the expression 3 + (2 - 1).  We do so as follows:

Op(Add, [Int 3, Op(Sub, [Int 2, Int 1])])

To write a function that adds 1 to its argument x we might write:

(Id.freshid "add", Id.freshid "x", Op(Add, [Id x, Int 1]))

Notice that we use the function freshid from the Id module to create new identifiers with the given string name. 

1. Look at the function in test.sml called sizeexp.  Right now, it returns 0.  Modify the size of the function so that it computes the size of an expression.  The size of an expression is equal to the number of abstract syntax nodes for expressions.  The first expression above has size 5 (counting 1 for each of the three integers, the add operation and the sub operation).  Do not count any position nodes in the size (but do count the subexpression).  For example, when p1 and p2 are any positions:

   Op(Add, [Pos (p1, Int 3), Pos(p2, Int 2)]) 

   has size 3 not 5.

    

2. Implement the function eval_prog in the file fun.sml.  This is intended to be an interpreter (evaluator) for the Fun language.  There are some comments in the file fun.sig that explain the meaning of each of the operations in the Fun language.  While test.sml provides you with a few test cases, you will definitely want to create many more test cases to ensure that your evaluator works properly.  If you have questions about how the evaluator should work in certain circumstances, feel free to send e-mail to the COS 320 mailing list.  Also, if you find any bugs in the infrastructure that we provide you, please let us know.
3. Submit by executing submit 1 test.sml fun.sml README on one of the CIT Sparc machines.  Please indicate the authors of the assignment in the README file.  
4. Once you are done, to further familiarize yourself with ML and with simple interpreters you may want to spend some time extending the language and your interpreter. For example, you might want to try extending the language with C-style "enums" and a switch statement.  A more challenging extension would be to augment the language with simple exceptions (raise () raises the exception -- don't assume exceptions have different names unless you are really adventuresome!; catch e1 with e2 runs the expression e2 if e1 raised an exception.).  This does not give you extra credit immediately, but it could help you get up to speed on programming with ML, which will be very valuable in future assignments.  Another thing to try is to implement a more efficient version of the "environments" used in the evaluator for fun.  Instead using lists, use a balanced tree, for instance.  When you change the Env structure, there should be no need to change the evaluator you have already written (that's the benefit of well-designed SML structures).  Alternatively, look through the SML basis library to find an efficient library that has already been implemented for you and reimplement Env using that library.