Computer Science 6220
Fall 1999
Homework Exercise 4

The assignment

Write an interpreter for a similar language, but in Astarte. Make your interpreter simple and elegant. Write comments to make it readable.

The subset should include the following forms.

const i

This is a constant, given by the integer i.

unary f

This is a function given by f. Here, f must be a function that takes an integer and produces an integer. For example f might be the built-in negation function, (-).

binary f

This is a function given by f. Here, f must be a binary function that takes a pair of integers and produces an integer. For example, f might be the addition function (+).

**x

This is a variable. The name of the variable is x. Here, x should be a string. (This is function ** applied to string x. A short name is used to make expressions easier to write.)

a ==> (b,c)

This is a conditional. If a is 0, then its value is c. If a is nonzero, its value is b. Here, ==> is a binary operator.

bind (x,e) v

This is a binding (a let). It binds variable x to e, and then evaluates v. Here, x should be a string that is the name of a variable, and e and v should be expressions.

lambda x v

This is a function lambda x.v. Here, x is a string that is the name of a variable, and v is an expression.

u @@ v

This is the result of applying function u to argument v. Here u and v are expressions, and @@ is a binary operator.

Here are some examples of expressions.

1. (binary +) @@ (const 4) @@ (const 6) This expression is applying the + function to 4 and 6. Its value is (const 10). Each time you apply a function, you must use operator @@.

2. (lambda "r" ((binary +) @@ **"r" @@ **"r")) @@ (const 7) This applies a function lambda r.r+r to the number 7. It should produce value (const 14). Notice that uses of variable "r" must be preceded by **.

3. Suppose you define function predicate by

        Let predicate(?f) = binary(?x => If f(x) then 1 else 0 %If).
     

   Then ((predicate >) @@ (const 3) @@ (const 5)) ==> (8,20) yields value 20, since 3 is not greater than 5.

4. bind ("z", (binary +) @@ (const 4) @@ (const 5)) ((binary *) @@ **"z" @@ **"z") evaluates to 81, since it binds z to 4+5 and then computes z*z.

You will want auxiliary forms of expressions that represent intermediate results.

closure (f, env)

This is a function closure. It represents function f, where the values of free variables in f are given by environment env.

binaryClosure (f, v)

This is the result of applying a built-in binary operator f to a value v. This is a function that is waiting for its next argument before it can run.

errorExpression

This is the value of an expression that has encountered an error, such as applying a basic unary function to a value that is not a constant integer.

Using types

  Operator @@(_opL9_). 
  Extension
    Abbrev Environment = [(String,Expression)].

    Species Expression =
      | errorExpression
      | const         Integer
      | unary         Integer -> Integer
      | binary        (Integer, Integer) -> Integer
      | **            String
      | bind'         (String, Expression, Expression)
      | lambda'       (String, Expression)
      | closure       (Expression,Environment)
      | binaryClosure ((Integer,Integer) -> Integer, Integer)

      | Expression @@ Expression
      | Expression ==> (Expression, Expression)
    %Species
  %Extension

   Let bind (?x,?e) ?v = bind' (x,e,v).
   Let lambda ?x ?v = lambda'(x,v).

You can begin writing your interpreter as follows. The value of an expression is another expression, but one reduced to simplest (normal) form.

  Lazylet eval by
    case eval (const ?i) ?     = (const i)
    case eval (** ?x)    ?env  = assoc x env
    ...
  %Lazylet

Test your interpreter. When you want to print an expression, use function $.

Hand in the interpreter by emailing it to me. Include a tester.