CSci 555: Functional Programming
Spring Semester 2001

OPTIONAL Assignment #6
Due 4 May 2001 (Revised)

The purpose of this assignment is to develop an interpreter for the simple language described below. Syntactically, the language is similar to the language Lisp.

Syntax. The following extended BNF grammar describes the commands that a user can enter into the interpreter. Nonterminal symbols are shown in uppercase. Terminal symbols are in lowercase. The symbols |, [ ], ^*, and ::= are part of the extended BNF metalanguage. The ^* is the superscript asterisk character denoting zero or more repetitions of the element (i.e., star-closure). The start symbol is COMMAND.

COMMAND  ::=  EXPR  |  ASSIGN  |  quit 
ASSIGN   ::=  ( set VAR EXPR )
EXPR     ::=  VAL
           |  VAR
           |  ( OPTR EXPR EXPR )
OPTR     ::=  +  |  -  |  *  |  /
VAL      ::=  [ - ] UNSIGNED
UNSIGNED ::=  DIGIT DIGIT^*
VAR      ::=  ALPHA ALPHANUM^*

• Each COMMAND is a separate line of text typed in response to an interpreter prompt. The input to the interpreter during a session is a sequence of COMMANDs ending with a quit command.

• In the grammar, EXPR represents an expression to be evaluated, VAR represents a variable name, and VAL represents an optionally signed value.

• A DIGIT is one of the numerals 0, 1, ..., 9. An ALPHA is either an uppercase or lowercase alphabetic character. An ALPHANUM is either an ALPHA or a DIGIT.

• UNSIGNEDs and VARs extend as far to the right as possible. That is, "1234abc+" (which is not a legal command) would consist of the UNSIGNED "1234", followed by the VAR "abc", followed by the operator symbol "+".

• Spaces may occur anywhere in the COMMAND line except within the UNSIGNEDs, VARs, OPTRs, and the keywords set and quit.

Semantics. A value is assigned to a syntactic element as follows:

• An UNSIGNED c denotes a nonnegative "integer" value; it has the value denoted by the string of DIGITs c interpreted as a decimal constant in the usual format. A VAL denotes an integer value that may be either positive or negative. That is, the value of the string of digits "37" is the integer 37 and the value of the string "-98" represents the integer -98.

  Note: In the Haskell program described below, you will need a user-defined type to encode these integer values instead of using the built-in primitive type Int.

• A VAR v denotes a variable named v; it has the value associated with the variable v in the current environment. If variable v does not occur in the current environment, then the value of v is undefined.

  An environment is a mapping from variable names to their values; it can be represented as a list of pairs (two-tuples) in which the first component is a variable name and the second component is the variable's current value.

• An EXPR is an arithmetic expression with the form (op l r); it has the value computed by applying the operation op to the values of the left and right operand expressions, l and r, respectively. The arithmetic operator symbols have their usual meanings.

• An ASSIGN is an assignment command with the form (set v exp), where v is a (possibly undefined) variable and exp is an expression. The command has the same value as the expression exp. The command also changes (i.e., "sets") the value of the variable v in the environment to have the value of the expression exp.

• The quit command terminates evaluation of commands by the interpreter.

Tasks. Implement the following Haskell functions:

• eval com env evaluates the command string com with respect to environment env and returns a pair (val,env') where:

  • val is a value from an appropriate user-defined type. When the string com is successfully evaluated, val should encode the integer value of the expression. When an evaluation error occurs (e.g., the command is not valid syntactically or a variable within the expression has an undefined value), val should encode an appropriate error indicator.

  • env' is the new environment after execution of command com. If com is an EXPR, then env' is the same as env. If com is an ASSIGN of the form (set v exp), then env' is the same as env except that the value of variable v is now mapped to the value of expression exp. A set of a previously undefined variable causes a new entry to be added to env'.

  Here are a few examples. The constructors Ok and Err are shown for illustration purposes. You may define your own type and appropriate messages.

  • eval "(+ x (* 3 y))" [("x",5),("y",2)]
    evaluates to (Ok 11,[("x",5),("y",2)]

  • eval "(set x (+ x (* -3 y)))" [("x",5),("y",2)]
    evaluates to (Ok 1,[("x",1),("y",2)]

  • eval "(set x (+ x (* -3 y)))" [("x",5)]
    evaluates to (Err "Undefined variable",[("x",5)]

  Hint: It should be possible to use a simple recursive descent parser to recognize the COMMAND syntax.

• interpret e implements an interpreter for the language described above. The interpreter should implement the algorithm stated below in imperative pseudo-code.

  Let env be the current environment, initially same as the argument e
  Prompt user for a COMMAND 
  Read COMMAND line com (from stdin) 
  While com not equal to "quit" 
      Execute eval com env to get return (val,env')
      If an error occurred
          Display an appropriate error message 
      Else 
          Display the integer value of the expression
          Update env to be same as env' 
      Prompt user for next COMMAND  
      Read COMMAND line com
  

Test your functions appropriately and thoroughly. Please format and document your program source code appropriately.

When this assignment is complete, submit a paper listing of your program source code and the screen outputs from executing the program. Be sure that all items submitted are clearly labeled with your name and the assignment number.

Also submit your program source code using MESH at URL http://www.cherry.cs.olemiss.edu/mesh/.

UP to CSCI 555 assignments document?