COS 320, Spring 2000. Programming Assignment
Programming Assignment 1: A Fun Intermediate Language
You may do this assignment in pairs, if you wish. If you do the assignment
in pairs, please create and submit a README file that contains the names of both
Getting started with ML:
- 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
at Bell Labs.
- Edit your .cshrc or equivalent so that your path contains
- Make a new directory as1 for this assignment.
- Copy the files *.sml *.sig and *.cm from
directory /u/cos320/chap1/ into as1.
- Please, familiarize yourself with the code that is already there. Pay
special attention to how it is divided into separate structures.
- You may find the
ML Basis documentation handy.
- Run sml.
- Inside the running ML session invoke CM.make(); to compile
- 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.
- 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).
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
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.
- 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
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.
- 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
- 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
- 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.