Fall 99, CSE 520: Assignment 4

Distributed: Published on the web on October 28.
Due: Nov 9 (in class).
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with PCF, interpretation of functional languages, and ML programming

Definition of a ML interpreter for Lazy PCF

The exercise of this assignment is to define in ML the eval function for Lazy PCF enriched with streams (see Lecture Notes 13 and 15). Namely, the syntax should be based on the following grammar:

   Term ::= Var| \Var.Term | Term Term        % lambda terms 
          | Num | true | false                % numerical and boolean constants
          | Term Op Term                      % numerical ops and comparison
          | cons(Term,Term)                   % stream constructor
          | head Term | tail Term             % stream selectors
          | if Term then Term else Term       % conditional
          | let Var = Term in Term            % term with a local declaration 
          | fix Term                          % the fixpoint operator

The interpreter should be environment-based (see Lecture Notes 16 and 17), and treat the scope correctly, i.e. it should have static scope.

Testing the interpreter

Additionally to the function eval, please define a term Primes representing the result of the "Sieve of Eratosthenes", namely the stream of all prime numbers starting from 2 generated with the method of Eratosthenes (see Lecture Notes 13 and 15).

Furthermore, please define a term Test_lazy representing the PCF term

   \x y z. if x then y else z

Finally, please define a term Test_static representing the PCF term

   \s. let n = 1 
       in  let s1 = cons(0,cons(n,s)) 
           in  let n = 2 
               in  s1

Please use ML val declaration to give these definitions, i.e.

   val Primes = < ML expression of type term, representing the sieve of Eratosthenes >
   val Test_lazy  = < ML expression of type term, representing \x y z. if x then y else z >
   val Test_static  = < ML expression of type term, representing \s. let n = 1 ... >

These definitions will be tested by us in contexts of the form

   eval head(tail(tail(...(tail(Primes))...))) emptyenv
   eval (app(app(app(Test_lazy,M),N),P)) emptyenv
   eval (head(tail(...(app(Test_static,S))...) emptyenv   
     (* (head(tail(app(Test_static,S)))) should give 1 *)

Use of the code in the Lecture Notes

You are welcome to use the interpreter for Eager PCF given in Lecture Notes 16 and 17 as a basis for developing your solution. In particular, please use the same definition of the datatype term (enriched with the representation of streams) and the same definition of the type environment of the Lecture Notes. This will help us checking your homework. Also, please use the name "eval" for the interpreter.

What to submit, and how

The solution of the assignment should contain the following code:

The definition of the datatype term
The definition of the type environment, and the functions emptyenv and update
The definition of the function eval for lazy PCF
The definition of the terms Primes, Test_lazy, and Test_static

Plus, any auxiliary function and type that you may find helpful to use, and comments and explanations that can help us to understand and evaluate your solution.

Please submit a hard-copy of the code by the deadline, as usual. In addition, please submit the electronic version (for testing purposes) by sending an email to cg520@cse.psu.edu by the deadline.

Recommendation

Since this is a programming assignment, you better start working at it well before the deadline. Don't let it sit until the last minute! It always takes a while to debug a program. Computers are not as flexible as instructors or TAs. You cannot convince them to accept a code with errors by saying "Com'on, I agree it's badly written, but the intention is so clear ..." :-)

Office hours

On Tuesday 16 November and Tuesday 23 November the office hours will be in the afternoon from 3:30 to 4:30 instead than in the morning.

I will be busy teaching two other classes on MWF in the last three weeks of November. Hence, it's unlikely that you find me in my office without appointment. Please try to come during the office hours. If you can't come during office hours, please send email for appoinment, or (better) send your questions by email.

Well, that's all... I hope you will have fun with this interpreter! Good luck, -Catuscia