Home Schedule Lecture notes PLP CS Other resources Policies Grading Assignments Blackboard announcements discussion grades

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, do/check statements, and both int and real types.  We are providing you with a parser generator and driver that build an explicit parse tree.  The provided code also includes the skeleton of a possible solution that converts the parse tree to a syntax tree and then recursively “walks” that tree to effect the interpretation.  You are of course welcome 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. 

The provided code has two main entry points:

  get_parse_table : grammar -> parse_table = ...
  parse : parse_table -> string -> parse_tree = ...

The grammar takes the form of a list of production sets, each of which is a pair containing the LHS symbol and k right-hand sides, each of which is itself a list of symbols.  The extended calculator language looks like this: 

  let ecg : grammar =
  [ ("P",  [["SL"; "$$"]])
  ; ("SL", [["S"; "SL"]; []])
  ; ("S",  [ ["int"; "id"; ":="; "E"]; ["real"; "id"; ":="; "E"]
           ; ["id"; ":="; "E"]; ["read"; "TP"; "id"]; ["write"; "E"]
           ; ["if"; "C"; "SL"; "fi"]; ["do"; "SL"; "od"]; ["check"; "C"]
           ])
  ; ("TP", [["int"]; ["real"]; []])
  ; ("C",  [["E"; "RO"; "E"]])
  ; ("RO", [["=="]; ["!="]; ["<"]; [">"]; ["<="]; [">="]])
  ; ("E",  [["T"; "TT"]])
  ; ("TT", [["AO"; "T"; "TT"]; []])
  ; ("T",  [["F"; "FT"]])
  ; ("FT", [["MO"; "F"; "FT"]; []])
  ; ("F",  [["id"]; ["i_num"]; ["r_num"]; ["("; "E"; ")"]
           ; ["trunc"; "("; "E"; ")"]; ["float"; "("; "E"; ")"]])
  ; ("AO", [["+"]; ["-"]])
  ; ("MO", [["*"]; ["/"]])
  ];;

A program is just a string: 

  let sum_ave_prog =
  " read int a read int b int sum := a + b
    write sum write float(sum) / 2.0 ";;

Your work will proceed in two steps: 

1. Translate the parse tree into a syntax tree: 

     let rec ast_ize_prog (p:parse_tree) : ast_sl = ...

   where the single argument is a parse tree generated by function parse.  We have provided a complete description of the ast_sl (abstract syntax tree for a statement list) type, though you are free to modify this if you prefer a different format. 

2. Walk the syntax tree to determine its behavior on a given input: 

     let rec interpret (ast:ast_sl) (full_input:string) : string = ...

   where the first argument is a syntax tree, as generated by function ast_ize_prog, the second argument is the input string to be read by the interpreted program, and the return value is the program output (the concatenation of values from write statements), possibly ending with an error message. 

   You are required to catch the following semantic errors:

   • Use of an undeclared variable.
   • Redeclaration of a variable in the same scope.
   • Non-integer provided to float.
   • Non-real provided to trunc.
   • Type clash in binary expression, comparison, or assignment.
   • check statement not inside a loop.
   • Non-numeric input, unexpected end of input, int read when real is expected, or real read when int is expected.  (Unlike the scanner, the input processing mechanism assumes that numbers are separated by white space, so 12.34 on the input, when an int is expected, should be an immediate error.)
   • Division by zero.

   You should treat each statement list as a separate scope.  So a variable declared inside an if or do statement can have the same name as a variable declared outside (and will hide the outer variable in the remainder of the nested statement list).  Note that while a declaration inside a do loop enters a name into the symbol table only once, the read or assignment that initializes that variable occurs on every iteration. 

  let ecg_parse_table = get_parse_table ecg;;
  let ecg_ast prog =
    ast_ize_prog (parse ecg_parse_table prog);;
  let ecg_run prog inp =
    interpret (ecg_ast prog) inp;;

  % ocamlc -o ecl str.cma interpreter.ml
  % ./ecl primes.ecl
  10

  2 3 5 7 11 13 17 19 23 29

  % ./ecl primes.ecl < input

In addition to (incomplete) starter code, we are also 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. 

Because the solution was written quickly (and your instructor is definitely 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 I’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: 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 syntax tree construction and interpretation routines must be purely functional. 

Hints

The initial source code is about 1060 lines of OCaml.  You should read most of it carefully to understand how it works (you can skip the details of parse table construction if you like, though I think it’s kind of cool :-). 

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 "interpreter.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.  This library is not visible to either the interpreter or the compiler by default.  In ocaml, you will need to say

  #load "str.cma";;

  ocamlc -o ecl str.cma interpreter.ml

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. 

My (not necessarily great) implementation of the full set of ast_ize_ functions is about 70 lines of code.  My version of the full set of interpret_ functions is about 150 lines, not counting the provided code for memory and values. 

You may find the following helpful. 

• OCaml system documentation—includes the language definition; manuals for the interpreter, compilers, and debugger; standard library references; and other resources. 
• Tutorials on various aspects of the language. 
• OCaml for the Skeptical—an alternative, arguably more accessible introduction to the language from the University of Chicago. 
• Developing Applications with Objective Caml—a book-length online introduction to functional programming and everything OCaml. 

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 ast_ize_prog and the other to write interpret, but the former is probably easier 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, for loops, nested scopes, or functions.  Several of these are likely to introduce new semantic rules that you will want to check. 

2. Implement a separate pre-pass over the AST to enforce static semantics.  In particular, you should be able to find the first six kinds of errors above before your ECL program executes. 

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 in a pre-execution pass over the tree.  More ambitiously, you might look for 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 code, so you can compile and then execute the output. 

5. Add syntax error recovery. 

Grading Rubric

• 25 points for creating correct ASTs (for syntactically correct ECL programs). 
• 35 points for interpreting the AST correctly.  This includes correct output for semantically correct ECL programs (20 points) and correct error messages for semantically incorrect ECL programs (15 points).
• 20 points for programming style.  As indicated on the grading page, “your code should have well designed abstraction boundaries and variable names; declarations for all constants; and a judicious number of helpful comments.”  Please do your best to write idiomatic OCaml. 
• 20 points for the README file.  In addition to the usual guidelines, you should explain the tests you ran to check your code.  You might also want to comment on the coding experience in OCaml. 
• Extra Credit: up to 25 points total. Up to 15 points for static analysis; up to 15 points for generating equivalent C code; other options at graders’ discretion. 

Trivia Assignment

Before the start of class on Wednesday, October 11, each student should complete the T3 trivia assignment found on Blackboard. 

MAIN DUE DATE: 

Warning: start now!  A3 is significantly harder than A2.  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:  11 October 2023 /