Assignment 3:  Interpretation

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

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:

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
    10
and see
  2 3 5 7 11 13 17 19 23 29
as 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. 

Hints

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. 

Division of labor and writeup

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. 

Extra Credit Suggestions

  1. Extend the calculator language in other interesting ways.  You might, for example, implement arrays, strings, for loops, or functions.  Several of these are likely to introduce new semantic rules that you will want to check. 

  2. Modify the interpret routines to make the inp parameter a lazy list of strings (a stream), so calculator programs can be interactive.

  3. Implement simple forms of code improvement via transformations of the AST.  A good place to start would be constant folding, which collapses arithmetic and logical operations on constants during typechecking or a separate pre-execution pass over the tree.  More ambitiously, you might (1) perform copy propagation, which tracks when variables are guaranteed to have the same value, so one can be used in place of the other without the need for an actual assignment, or (2) identify common subexpressions in separate expressions, which could be computed only once and kept in a temporary. 

  4. Write a routine to turn the AST into C or assembly code, so you can compile/assemble and then execute the output. 

  5. Add syntax error recovery. 

Grading Rubric

Trivia Assignment

Before end of day on Friday, March 21, each student should complete the T3 trivia assignment found on Blackboard. 

MAIN DUE DATE: 

Wednesday April 9, by end of day; no extensions. 

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. 


Last Change:  16 March 2025 / Michael Scott's email address