Add the following functions to the package:
- toSeq converts a Gofer list into a Seq with
exactly the same elements in the same order.
The Seq should be "perfectly balanced", that is,
the "tree" represented by every Cat should be of minimal height.
- fromSeq converts a Seq into a
Gofer list with exactly the same elements in the same order.
- delSeq takes a value and a Seq of the same type
and returns the Seq with the value removed.
- For an extra challenge beyond the basic assignment, modify all the
functions in the package so that they only return Seq "trees" that
satisfy the AVL balancing criteria.
(Look this up in a book on data or structures.)
- Format, document, and submit your work a s described in
Assignment #1 above.
Assignment #5, Due Tuesday, 5 December, 9:30 a.m.
Note that the assignment is now due 5 days later than originally
scheduled.
I made corrections to this on Monday, 6 November.
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 normal uppercase font.
Terminal symbols are in lowercase "typewriter" font.
The symbols |, [ ], ^*, and ::= are part of the extended BNF
metalanguage. The ^* is the superscript asterisk character denoting
zero or more repetitions of the element.
The start symbol is COMMAND.
COMMAND ::= EXPR | ASSIGN | quit
ASSIGN ::= ( set VAR EXPR )
EXPR ::= VAL
| VAR
| ( OPTR EXPR EXPR )
OPTR ::= + | - | * | /
VAL ::= [ - ] 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.
- 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.
- VALs and VARs extend as far to the right as possible.
- Spaces may occur anywhere in the COMMAND line except within VALs,
VARs, OPTRs, and the keywords "set" and "quit".
Semantics.
A value is assigned to a syntactic element as follows:
- A VAL i has the integer value denoted by the
string of DIGITs i interpreted as a decimal constant in the
usual format.
- A VAR v has the integer value associated with the
variable name v in the "current environment".
An environment is 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.
If variable v does not occur in the current environment,
then the value of v is undefined.
- An EXPR of the form (op l r) has the value computed by
applying the operation op to the values of the left and right
operand expressions, l and r.
The arithmetic operator symbols have their usual meanings.
- An ASSIGN of the form (set v exp) has the
value of the expression exp.
It also "changes" the value of the variable v in the
environment to have the value of the expression exp.
Tasks.
Implement the following Gofer functions:
- eval com env evaluates command
com with respect to environment env
and returns a pair (val,env')
where
- val is a value from an appropriate user-defined
type.
When 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 has an undefined value), val
should encode an appropriate error condition.
- 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.
Here are a few examples.
The constructors Ok and Err are
shown for illustration purposes. You may define your own type.
- 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 11,[("x",11),("y",2)].
- eval "(set x (+ x (* 3 y)))" [("x",5)]
evaluates to (Err,[("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 for next COMMAND
Read COMMAND line com
Test your functions extensively.
Format and document your program source code appropriately.
Submit source code and listings as with previous
assignments.
I plan one more assignment that involves proofs and/or
reduction techniques.
That assignment will overlap with this one.
Assignment #6, Due Thursday, 7 December, 9:30 a.m.
- Do exercises 1, 2, 5, and 13 from section 11.7 of the
Notes on Functional Programming with Gofer.
- Do one additional exercise from the same section of the Notes.
UP to CSCI 555 root document?
Last modified: 19 December 1995.