Assignment 3:  Interpretation

Your task in this assignment is to implement a complete interpreter for an extended version of the calculator language, with if and while statements.  You will write your interpreter in Scheme.  We are providing you with a parser generator and driver that build an explicit parse tree. 
NEW (7 Oct.): The provided code now includes the skeleton of a possible solution.

The main entry point of the provided code is

  (define parse (lambda grammar program) ...
This normally returns a syntax tree.  You’ll want to print some out to see what they look like.  If the grammar is malformed, you may get unhelpful error messages from the parser generator (it isn’t very robust).  If the program has syntax errors, parse will print an error message and return #f

The grammar takes the form of a list of productions, each of which is a 2-element list containing the LHS symbol and a list of the symbols on the RHS.  The extended calculator language looks like this: 

  (define x-calc-gram
    '(("P"  ("SL" "$$"))
      ("SL" ("S" "SL") ())
      ("S"  ("id" ":=" "E") ("read" "id") ("write" "E")
            ("if" "C" "SL" "end") ("while" "C" "SL" "end"))
      ("C"  ("E" "rn" "E"))
      ("rn" ("==") ("!=") ("<") (">") ("<=") (">="))
      ("E"  ("T" "TT"))
      ("T"  ("F" "FT"))
      ("TT" ("ao" "T" "TT") ())
      ("FT" ("mo" "F" "FT") ())
      ("ao" ("+") ("-"))
      ("mo" ("*") ("/"))
      ("F"  ("id") ("num") ("(" "E" ")"))
      ))

A program takes the form of a simple list: 

  (define sum-and-ave '(read a
                        read b
                        sum := a + b
                        write sum
                        write sum / 2
                        $$))
Note the difference:  symbols in the grammar are quoted character strings; symbols in the input are Scheme atoms. 

Your work will proceed in two steps: 

  1. Translate the parse tree into a syntax tree: 
          (define ASTize-P (lambda (P) ...
    where P is a parse tree generated by function parse.  The exact format of the AST is up to you.  You can get ideas from the text, but what’s there is incomplete; you’ll have to flesh it out. 

  2. Walk the syntax tree to determine its behavior on a given input: 
          (define interpret-AST (lambda (ast input) ...
    where ast is a syntax tree generated by function ASTize-P.  The return value of the function should be a list of the values written by the interpreted program. 
You can put the pieces together with the following. 
  (define interpret
    (lambda (grammar program input)
      (interpret-AST (ASTize-P (parse grammar program)) input)))
If you run
  (interpret x-calc-gram primes '(10))
you should see the output
  (2 3 5 7 11 13 17 19 23 29)

For the (extended) calculator language there are no static semantic errors; everything is checked at run time.  You should catch (and produce a reasonable error message for)

Hints

The initial source code is a little more than 500 lines of Scheme.  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 :-). 

Your program should not take advantage of any imperative features (no functions or special forms with names ending in !).  You may use display for error messages and debugging; all other output should result from the interpreter printing the return values of your top-level functions. 

You will want to pass the (remaining) input, the output so far, and the current symbol table to and from the routines that walk the AST.  You can keep the current values of variables in the symbol table.  Note that the routine that evaluates a while statement will need to be (tail) recursive. 

We will be grading your assignment using the “Dr. Scheme” interpreter:  /u/cs254/bin/drscheme, set at the “R5RS” language level.  You can download your own GUI version of Dr. Scheme for Windows, MacOS, or Linux, but please be sure to set the language level correctly, and check that your code works correctly on the csug installation. 

My (not necessarily great) implementation of ASTize-P is just over 50 lines of code.  My version of interpret-AST is just over 130 lines. 

You may find the following helpful. 

Division of labor and writeup

As in all 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. 

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 or README.pdf file in the directory in which you run the script.  Be sure to describe any features of your code that the TA might not immediately notice. 

Extra Credit Suggestions

  1. Extend the calculator grammar in other interesting ways.  You might, for example, implement separate integer and floating-point types, arrays, for loops, nested scopes, or functions.  Several of these are likely introduce rules that you will want to check statically. 

  2. Write a routine to turn the AST into C code, so you can compile and then execute the output. 

  3. Generate warning messages at the end of execution for any values that were assigned into a variable and then never used. 

  4. Add syntax error recovery. 

Trivia Assignment

Before the beginning of class on Thursday, October 2, send e-mail to to cs254 containing answers to the following questions: 

  1. Are you working alone or in a team?  If a team, who is your partner? 

  2. For the following programs, what is the output when parsing with our calculator grammar? 
        read a
        read b
        read c
        sum := ( ( a * b ) + ( b * c ) + ( c * a ) ) / 3
        write sum
        $$
        read a b
        read c
        sum := ( ( a * b ) + ( b * c ) + ( c * a ) ) / 3
        write sum
        $$

  3. Write a program in the calculator language that reads a number n, reads n additional numbers (this will need a while loop), and prints the average of those additional numbers.  Test your program using the provided parser generator. 

  4. Write a Scheme function that given inputs n and k computes the binomial coefficient
    ( n )  =  n! / (k! × (nk)!)
    k
    You’ll probably want to write a separate (recursive) factorial function. 

MAIN DUE DATE: 

Monday October 13, at 11:59 pm; no extensions. 
Last Change:  07 October 2008 / Michael Scott's email address