Programming Languages: Optional Homework Assignment

G22.2110

Notes:

Due on Tuesday April 25 2000, 6:00pm (late homeworks will not be accepted).
Electronic submissions only. To be sent by email to crutcher@cs.nyu.edu.
Send only a single text (ASCII) file as an email message.
You are required to include a printout of a session showing a run of your program(s) on some general test data.

This homework is optional, and is for extra credit, used to complement your mid-term grade. You will get as extra credit for your mid-term, half the part of this homework's grade which is over 50%. The resulting mid-term grade cannot be above 100%.

To make things clearer, the following SML function could be used to compute new mid-term grades.


fun newMidGrade (oldMidGrade,hwopt) =
      Real.min (1.0, (oldMidGrade + Real.max(0.0, ((hwopt - 0.5) / 2.0))));

The SML type for Core-ML abstract syntax trees, given in class, is:

datatype corexpr =
  Int of int
| Ident of string
| Fun of string * corexpr
| App of corexpr * corexpr
| Let of string * corexpr * corexpr;

The types for Core-ML values is defined as:

datatype coreval =
  IntVal of int
| FunVal of string * coreexpr * ((string * coreval) list);

The type for environments could be abbreviated as:

type env = (string * coreval) list;

The type for evaluation results is defined as:

datatype coreres =
  Val of coreval
| Error;

You may define and use the following exception:

exception CoreFailure of string;

Raising that exception could be done with, for instance,

raise (CoreFailure "a useful message")

Problem 1 Define a function lookup of type


(string * env) -> coreval

which returns the value associated with a Core-ML identifier, or fails.

Problem 2 Program an interpreter for the Core-ML expression language, given in class. The interpreter must behave the same as the natural semantics given in class.

Its type should be:


env -> coreexp -> coreres

Your main function must therefore take an environment and (the abstract syntax tree of) an expression, and return a coreres.

You'll need auxiliary functions for looking up an environment (previous problem), and possibly a few other things. Your main functions will be an implementation of the semantic rules.

It is possible (and both easier and simpler) to avoid ML imperative features in these kinds of programs.

Problem 3 Extend your Core-ML interpreter with any (reasonable) feature you want. For each of your extensions, describe its behaviour in English, and give its natural semantics rules.

Well-described simple extensions will be more appreciated than obscure complex ones. (The emphasis is on the clarity and precision of the description and implementation.) You may of course use existing features of ML as inspiration.

This document was translated from L^AT_EX by H^EV^EA.