CS442: Assignment 2

The purpose of this assignment is to implement an interpreter for a simple functional programming language with ML-style let-polymorphism.

The grammar for the language is as follows:

   <exp> ::= <id> 
           | <num>
           | ( <exp> <exp> )
           | lambda <id>.<exp>
           | lazy <id>.<exp>
           | rec <id>.<exp>
           | let <id>=<exp> in <exp> end

The <id> and <num> symbols in the grammar denote identifiers (strings starting with a letter followed by letters and digits) and non-negative integer numerals (strings of digits), respectively. None of the keywords mentioned in the above grammar may be used as an identifier. You may relax the syntax for application to allow "

(<exp> <exp>
    ... <exp>)

" to stand for "

( ... (<exp>
    <exp>) ... <exp>)

", as long as all the valid strings in the original grammar parse correctly.

The "lambda" and "lazy" abstractions allow forming functions that, when applied, evaluate their arguments eagerly and lazily, respectively. The "rec" abstraction allows forming recursive abstractions, and the "let ... in ... end" allows local polymorphic declarations (let-polymorphism). The types considered are as follows:

   <type> ::= int | bool | ( <type> -> <type> )

To facilitate operations on built-in types (integers and booleans), certain identifiers denote built-in functions as follows:

plus: int->(int->int) is the integer addition,
neg: int->int is the integer complementation,
eq: int->(int->bool) is the equality on integers,
lt: int->(int->bool) is the "less-than" comparison of integers, and
if: bool->('a->('a->'a)) is the conditional.

The completed assignment should read a sequence of semicolon-terminated strings in the above grammar from standard input and, for valid programs, print out the type of the expression and the value resulting from evaluation the expression. The program should terminate when "end-of-file" is detected. For example, the following is a typical interaction with the interpreter (computer responses italicized):

   1;  
   1:int
   ((plus 2) 3);
   5:int
   lambda x.((plus 1) x);
   fn:(int->int)
   lambda x.x;
   fn:('a0->'a0)
   let mult = rec f.lambda m.lambda n.
              (((if ((eq m) 0)) 0) ((plus n) ((f ((plus m) (neg 1))) n)))
   in 
       ((mult 3) 4) 
   end;
   12:int
   let mult = rec f.lambda m.lambda n.
              (((if ((eq m) 0)) 0) ((plus n) ((f ((plus m) (neg 1))) n) ))
   in
   let fact = rec f.lambda n.
              (((if ((eq n) 0)) 1) ((mult n) (f ((plus n) (neg 1))) ))
   in 
      (fact 10)
   end end;
   3628800:int
   let fib = rec f.lambda n.
              (((if ((eq n) 1)) 1)  
               (((if ((eq n) 2)) 1) 
                ((plus (f ((plus n) (neg 2))))
                       (f ((plus n) (neg 1))))))
   in
      (fib 8)
   end;
   21:int
   (plus ((eq 1) 2));
   Type: cannot unify (int->(int->int))
                 with (bool->'a2)
   lambda x.(x x);
   Type error: cannot unify 'a1
                       with ('a1->'a2)

The deliverable of this assignment is a source code for the complete interpreter, consisting of a lexical analyzer (tokenizer), a parser, a type inference module, and an evaluator. Both the later two modules should also be able to print out the results (i.e., type annotations and values) in a format comparable to the above example.

Assessment:

The completed assignment will be assessed by running tests exercising functionality of the interpreter and its ability to detect incorrect programs (i.e., syntactic and typing errors).

Bonus:

There are several extensions of the assignment that will be considered toward extra bonus marks (listed here in the order of difficulty):

adding products (pairs of arbitrary types; easy),
adding lists (of arbitrary type; easy)
adding variant types (medium)
adding named records (hard)
adding inductive types (datatype; hard)