Homework 3

Assigned: Monday March 24, 2008.
Due: on or before 11:59 PM on Monday April 7, 2008.

When doing this homework, first create a directory named HW3 somewhere in your home directory (e.g. as a subdirectory of a cse305 directory). Place your solution to each question in a file or set of files, as indicated, in the HW3 directory. When you're ready to submit, zip up the HW3 directory and its contents, and use the submit_cse305 command to submit your HW3.zip file. You can do this easily as follows. First, make sure your current directory is the directory that contains the HW3 directory. Next, issue the following command:

zip -r HW3 HW3

It is very important that you pay close attention to the naming conventions for files and directories for you homework submissions in this course. Having uniform names for all student submissions makes grading submissions much easier. If you do not adhere to the naming conventions, grading of your work will be delayed, or it may simply be returned to you ungraded for you to correct the names.

Question: (100 points - 35 points each for C# and Prolog, 30 points for ML)

Your interactive Scheme interpreter must provide a read-eval-print loop (RELP) which prompts for an expression, evaluates the expression (if well formed), prints either the value of the expression (if it was well-formed) or an error message (if it was not well-formed), and loops back to prompt for another expression.

In each language, use "> " as the REPL prompt. In C#, your program should start up the REPL right away. In ML, name the main function in your program scheme, a function of type unit->unit. In Prolog, name the main predicate in your program scheme, a predicate of arity zero (i.e. taking zero arguments).

The REPL must be able to evaluate the following kinds of expressions:

• integers - integers are interpreted in base 10
• names - names are evaluated by looking them up in an environment, starting with the current environment, following static links, until the name is found. If it is not found, an error occurs. Names must consist of only letters, and cannot be either "define" or "exit".
• (define <name> <expression>) is evaluated by first evaluating , and binding, in the current environment, the name to the that value. As discussed in class, binding a name to a value in an environment should work the way it does in ML: entering multiple bindings for a name in a given environment does not overwrite existing bindings, but new bindings must be found before older ones.

  The value of a define is the value assigned to the variable(i.e. the value of <expression>. If <expression> is not well-formed, the value of the define is Invalid (see below), and no binding takes place.

• (exit) is evaluated by terminating the REPL. An exit does have a value (Invalid) but for practical purposes it doesn't matter (since the interpreter exits as a result or evaluating it).

• arithmetic expressions - expressions involving +, -, * and / (integer division) of the typical scheme form, for example (+ x y).

Suggestion

Build up the appropriate abstractions first! For example, you will need an environment abstraction. You should also define a disjoint union of expression types. Because getting the types right in ML might be a bit challenging, here are some code snippets you can use.

Expression type (a disjoint union)

datatype Expression = Invalid of string | Number of int | Name of string | Define of string * Expression;

Expression to string conversion

fun expression2string(Invalid(msg)) = msg
  | expression2string(Number(x)) = Int.toString(x)
  | expression2string(Name(str)) = str
  | expression2string(Define(str,exp2)) = 
        str ^ " bound to value of " ^ expression2string(exp2);

Using String.tokens to parse input
Read basis library documentation for more information on String.tokens

fun space(#" ") = true
  | space(x) = false;

fun parse(str) = 
    let
	val tokens = String.tokens space str
    in
        (* DO YOUR PARSING HERE *)
    end;

Environment to string conversion
Assuming an environment is represented as a list of key-value tuples (an association list), this function returns a string representation given an environment.

fun environment2string([]) = ""
  | environment2string((k,v)::rest) = 
        "("^k^","^expression2string(v)^")"^environment2string(rest);

Name lookup in an environment

fun lookup(str,[]) = NONE
  | lookup(str,(k,v)::rest) = 
      if (String.compare(str,k)=EQUAL) then SOME(v) else lookup(str,rest);