Your task in this assignment is to implement a complete interpreter
for our extended calculator language (call it ECL), again
with if
statements, while
statements, and both int
and real
types.
We are providing you with starter code
that builds an abstract syntax tree.
The provided code also includes the skeleton of a possible solution
that (1) transforms the AST into a typechecked, annotated tree and
(2) walks the transformed tree to effect the interpretation.
You are of course free to adopt a different skeleton if you
prefer.
Since this one has been excised from a complete working solution,
however, you may find it a good place to start.
To make it easier for the instructor to build new versions of the
project, the provided code includes a complete LL(1) parser generator,
parser driver, and parse tree builder (this was, in fact, the core of
the table_gen
tool for the second projec).
You are encouraged to read this code to get a sense of how it works
and to see examples of OCaml idioms that may be useful to you.
The entry point for the already-working part of the code is function
ecg_ast
. It takes a single argument—a string
representing the program to be scanned, parsed, and converted to an
AST. The two main skeleton routines, which you need to flesh
out, are typecheck
and interpret
.
The typecheck
function takes a single argument—an
AST—and returns a four-tuple: a transformed AST, a list of
static semantic errors, and counts of the number of distinct
real
and int
variables in the calculator
program. The interpret
function takes four
parameters—the transformed AST, the two counts, and the input to
the calculator program—and returns the program’s
output.
Both typecheck
and interpret
are the roots
of a hierarchy of mutually recursive functions that traverse and
manipulate AST fragments. This is the code that will take most
of your time to develop. The typecheck
hierarchy
also makes use of a symbol table structure (symtab
), which
keeps track of the names and types of variables declared in
each scope (each statement list—this includes the bodies of
while
loops, then
blocks, and
else
blocks). Part of the code for the symbol
table lookup routine has been redacted; you’ll need to flesh
this out as well.
Your typechecker must catch the following static semantic errors before reading input or running the calculator program
int
argument provided to float
.
real
argument provided to trunc
.
You should arrange for the scope of a variable to extend from its declaration to the end of the current statement list. If the declaration shadows (hides) a declaration in an outer scope, then (as in C) the outer declaration should remain visible in the portion of the inner scope prior to the inner declaration. You should also avoid cascading error messages. In particular, if a subexpression contains an error, you should announce that error but not complain when the subexpression is subsequently combined (by a binary operator, comparator, or assignment) with another subexpression.
Your interpreter must catch the following dynamic semantic errors:
real
input when read
ing a variable
of type real
.
int
input when read
ing a variable
of type int
.
Note that the input processing mechanism assumes that numbers are
separated by white space, so 12.34 on the input is an error when an
int
is expected.
Putting the pieces together, the provided code includes an
ecg_run
routine:
let ecg_run (prog : string) (inp : string) : string = let (tree, errs, num_rs, num_is) = typecheck (ecg_ast prog) in if errs <> [] (* deep comparison *) then String.concat "\n" errs else begin print_string "typecheck completed successfully\n"; interpret tree num_rs num_is inp end
If you are working in the REPL (ocaml
or
utop
—I recommend the latter), ecg_run
will serve as your “main” routine. When you think
you have it all working, you can compile the interpreter with
ocamlc -o ecl -I +str str.cma ecl.ml
The compiled version will run a main
routine that differs
from ecg_run
only in that (1) it expects, as a command-line argument, the
name of a file containing a calculator program and (2) it scans,
parses, and typechecks the program before attempting to read input
from stdin
.
If you place the prime-generating program from project 2 in file
primes.ecl
, you can type
./ecl primes.ecl 10and see
2 3 5 7 11 13 17 19 23 29as output. Note that the input-processing mechanism is quite simplistic: it requires you to enter all input and type
^D
before it
does anything—it is not interactive (and in fact, if your
program takes no input at all, you must still type ^D
).
If you put the number 10 in a file named input
, you
could repeat the above run by typing
./ecl primes.ecl < input
In addition to (incomplete) starter code, we are providing an
already-compiled solution to the assignment, which you can run to
get a sense of the output we’re expecting—and in
particular to see how you might respond to semantic errors.
You can find this solution in ~cs254/bin/ecl
on the
csug
network.
Given that your instructor is not a a perfect programmer,
it’s possible that the provided solution and/or the starter code
has bugs. If you find one, please report it ASAP and
we’ll try to release a fix.
Note that your interpreter does not have to produce exactly the same
error messages as the provided solution (feel free to do better!),
so long as it meets the requirements described on this page.
Warning: with the exception of updates to the
mem
arrays during calls to
interpret
, your
program must not take advantage of any
imperative features in OCaml. You may perform I/O
and run the while
loops in main
as
described above, and you can of course do whatever you want while
debugging, but the main logic of your final typechecking and
and interpretation routines must be purely functional.
The starter source code is about
1340 lines of OCaml. The first 860 lines can be used as-is.
The remaining skeleton has comments (search for YOUR CODE
HERE
) that suggest where you need to make changes.
You should read through all of it, focusing your attention on the part
you’re going to need to modify.
The full working version, from which the starter code was extracted, is
about 1450 lines.
For most of the assignment, it will probably be easiest to use the
ocaml
interpreter or its utop
wrapper.
You’ll want to keep
reloading your source code (#use "ecl.ml"
) as you
go along, so you catch syntax and type errors early.
On occasion, you may also want to try compiling your program with
ocamlc
, to create a stand-alone executable.
Note that the code we have given you uses functions (regexp
and split
) from the Str
library, which
is not visible to either the interpreter or the compiler by
default.
In the REPL, you will need to say
#load "str.cma";;(in
ocaml
) or
#require "Str";;(in
utop
)
before you #use
your source code.
(Once is enough; you don’t have to re-#load/require
in order to re-#use
.)
When compiling, you’ll need to include the str
library in the call to ocamlc
, as shown above.
The provided source includes code for several ECL programs
(sum-and-ave
, primes
, gcd
,
sqrt
).
You may want to put these into separate files, so they can be executed
by the compiled version of your interpreter.
You will undoubtedly want to write additional tests.
We will be grading your assignment using
/usr/bin/ocamlc
on the csug
machines. You can
download your own
copy for Windows, MacOS, or Linux, but please be
sure to check that your code works
correctly on the csug
installation.
To help you visualize your ASTs, the starter code includes
pp_p
and pp2_p
functions to
“pretty-print” the original and transformed ASTs.
These may be useful debugging aids when working in the REPL; they
aren’ called by anything else in the code.
You may find the following helpful.
As in most assignments this semester, you may work alone or in teams of
two. If you choose to work in pairs, I strongly encourage
you to read each others’ code, to make sure you have a full
understanding of semantic analysis.
The most obvious division of labor is for one team member to write
typecheck
(including the stab_lookup
routine) and the other to write interpret
,
but the former is probably harder than the latter, so you may want to
consider other options.
Be sure to follow all the rules on the Grading page. As with all assignments,
use the turn-in script:
~cs254/bin/TURN_IN
. Put your write-up in a
README.txt
, README.md
, or
README.pdf
file in the directory in
which you run the script (only one README
required per
team). Be sure to describe any features
of your code that the TAs might not immediately notice.
for
loops,
or functions. Several of these are likely to introduce new
semantic rules that you will want to check.
interpret
routines to make the
inp
parameter a lazy list of strings (a
stream), so calculator programs can be interactive.
typecheck
.
This includes 15 points for generating transformed ASTs (for
syntactically correct ECL programs) and 15 points for correctly
identifying all static semantic errors (without cascading errors).
camlp5
pretty-printer.)
Before end of day on Friday, March 21, each student should complete the T3 trivia assignment found on Blackboard.
Warning: start now! A3 is at least as hard as A2, and likely harder. When writing the sample solution, there were several times when I needed to stop, think for a day, and come back to it. You will need to do the same; don’t procrastinate.