Problem Set 2 – Substituting, Folding, Stacking, and Typing

Due February 13, 2008.

Instructions

This problem set has multiple parts. Write your solution to each part in a separate file. To get you started, we have provided in CMS a stub file for each part. You should download and edit these files. Please write your name and NetID as a comment at the top of each file. Once you have finished, submit your solution using CMS.

Updates/corrections

Look for changes to the problem set highlighted in red.

The stub file for PS3 has been updated with more of the implementation to get you started. Any implementation based on the original stub file will also be fine. (Monday, Feb. 11)

Three important things to watch out for:

  1. Compile errors: All programs that you submit must compile. We reserve the right to give programs that do not compile a zero. If you are having trouble getting your assignment to compile, please visit consulting hours. If you run out of time, it is better to comment out the parts that do not compile and hand in a file that compiles, rather than handing in a more complete file that does not compile.
  2. Missing functions: We will be using an automatic grading script, so it is crucial that you name your functions and order their arguments according to the problem set instructions, and that you place the functions in the correct files. Do not break this rule. It would be unfortunate if you to not receive credit for a properly written function simply because our grading script couldn't find it.
  3. Code style: Finally, please pay attention to style. Refer to the CS 312 style guide and lecture notes. Programs that compile and execute correctly will not receive full credit if they are poorly written. Take time to think about the problems and find elegant solutions before coding.

Part 1: Evaluation

Before starting to code for real, practice your pencil-and-paper evaluation skills by evaluating the following code segments using the substitution model. Be sure to show all intermediate reductions.

  1. ~50 * ((22 mod 4) * (22 div 4)) * (5 - 9) + ((9 - 5) * 2)
  2. (fn y => fn z => y z) (fn y => y * (y+1)) 6 
  3. let
  val x = fn f => fn (x,y,z) => (f x) * (f y) * (f z)
  val y = fn x => 2 * x
in
  x y (3,1,13)
end

Part 2: Folding

As discussed in lecture, foldl and foldr take both an operator and an initial accumulator as arguments. Supply operator f and the initial accumulator a in stub file part2.sml to solve the following problems using foldl (or foldr where specified). If necessary, it is permitted to return a tuple with the desired answer, so long as the answer is the first element of the tuple.

  1. Compute the product of all elements in the list e.g. input [1,2,3,4,5] returns 120
  2. Return a pair of lists (L1, L2), where L1 contains the elements from the odd-numbered positions of L, and L2 contains the elements from the even-numbered positions; e.g., input [1,2,3,4,5] gives result ([1,3,5],[2,4]).
  3. Return the number of functions in the list which when applied twice to -1 (applied once and then applied to this result) return a positive number; e.g., input [fn x => x + 1, fn x => x - 1, fn x => x * ~1, fn x => x*x] returns 2.
  4. Use foldr to return the original list, reversed, with each element duplicated, e.g. input [1,2,3,4,5] returns [5,5,4,4,3,3,2,2,1,1]. The use of the list concatenation operator @ is not permitted. Note that this task is much easier if implemented with foldl: 
    fun reverseDuplicate(l:int list) =
  let
    val f = fn (x,y) => x::x::y
    val a = []
  in
    foldl f a l
  end
  5. Lastly, use foldr to return a list of every suffix of a list; e.g., input [1,2,3,4] returns [[1,2,3,4],[2,3,4],[3,4],[4],[]].

Part 3: Stack Language

In this part you will use higher-order functions to implement a simple stack language that computes on integers. Note: this is tricky! The commands in this language are:

start Initializes the stack to empty. This is always the first command and never appears again.
(push n) Pushes the integer n on the top of the stack. This command is always parenthesized with its argument.
pop Removes the top element from the stack.
add Pops the two top elements and pushes their sum.
mul Pops the two top elements and pushes their product.
npop Pops the top element, elt, and if elt is positive, pops elt more elements
dup Duplicates the top element and pushes it.
halt Terminates execution. This is always the last command.

Remarkably, we can implement each of the commands as SML functions, in a way that lets us write a series of stack-language commands directly as SML expressions. The value of the SML expression should be the final stack configuration. For example, the following series of commands: 

start (push 2) (push 3) (push 4) mul mul halt
evaluates to a stack with one element, 24.

Your task is to implement all of the commands in this language. Use a list to implement the stack such that the previous example returns the stack [24], and raise the provided StackException if a command cannot be performed on the current stack, e.g. the command add in the program start add halt.

Hint: The stub file part3.sml shows how to implement start and halt. Fill in the rest of the implementation.

Part 4: Type checking

In this part, you will consider how one might type-check SML expressions, by implementing a simple type-checking algorithm for a subset of SML. The language is defined as follows: 

datatype mytype =
  MyInt                  (* Represents the type int *)
| MyTuple of mytype list (* The type of a tuple. MyTuple(t1,...,tn)
                          * corresponds to the type t1*...*tn. *)
| MyUnit                 (* The type of an empty tuple (). *)

datatype exp =
  Int of int             (* An integer constant. *)
| Tup of exp list        (* A tuple expression. Tup[e1,...,en] represents
                          * (e1,...,en). Note: Tup [] represents () and
			  * Tup [e] represents (e) = e. *)
| Proj of int * exp      (* Tuple projection. Proj(n,e) evaluates to the
                          * nth element of tuple e, with element indices
		          * starting from 1. *)
| Plus of exp * exp      (* Adds two integers. *)
| Let of string * mytype * exp * exp 
       (* Let(s,t,e1,e2) defines a variable with the name s, type t,
	* and value of e1 and uses this new variable when evaluating e2. *)
| Var of string
       (* Var(s) represents a variable named s, which should be
	* defined earlier in a Let *)

Complete the function: 

fun typeCheck (e : exp): mytype = ...
which takes an expression of type exp, and returns the expected type of the value produced by this expression.

A few examples:

Implement static scoping for variable resolution (HINT: Define a type environment that records the types of bound variables in an association list).

Some expressions cannot be type-checked, e.g., Plus(Int 2, Tup[Int 3, Int 4]). Raise Fail with a useful description of the error in cases where the expression does not type-check.

There is a bit of awkwardness caused by our use of SML lists in defining tuples, since lists can be length 0 and 1, but tuples cannot. Length-0 tuples should be of type MyUnit, so that typeCheck(Tup[]) returns MyUnit. For length-1 tuples, return the type of their one element; e.g., typeCheck(Tup[Int 3]) returns MyInt.