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.
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)
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.
~50 * ((22 mod 4) * (22 div 4)) * (5 - 9) + ((9 - 5) * 2)
(fn y => fn z => y z) (fn y => y * (y+1)) 6
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
As discussed in lecture,
foldr take both an operator and an initial accumulator as arguments. Supply operator
f and the initial accumulator
in stub file part2.sml to solve the following problems using
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.
[fn x => x + 1, fn x => x - 1, fn x => x * ~1, fn x => x*x]returns 2.
foldrto return the original list, reversed, with each element duplicated, e.g. input
[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
fun reverseDuplicate(l:int list) = let val f = fn (x,y) => x::x::y val a =  in foldl f a l end
foldrto return a list of every suffix of a list; e.g., input
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:
||Initializes the stack to empty. This is always the first command and never appears again.|
||Pushes the integer n on the top of the stack. This command is always parenthesized with its argument.|
||Removes the top element from the stack.|
||Pops the two top elements and pushes their sum.|
||Pops the two top elements and pushes their product.|
||Pops the top element, elt, and if elt is positive, pops elt more elements|
||Duplicates the top element and pushes it.|
||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 haltevaluates 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 , and raise the provided
if a command cannot be performed on the current stack, e.g. the
add in the program
start add halt.
Hint: The stub file part3.sml
shows how to implement
halt. Fill in the rest of the
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:
Plus(Int 2, Int 3). Calling
typeCheckon this returns
#3 (5,6,7,8), which evaluates to 7, is represented as
Proj(3,Tup[Int 5, Int 6, Int 7, Int 8])), which type-checks as
typeCheck(Tup [Int 4, Int 5])results in
typeCheck(Let("x",MyInt, Plus(Int 3, Int 6), Plus(Var "x", Var "x")))returns
Implement static scoping for variable resolution (HINT: Define
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]).
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
length-1 tuples, return the type of their one element; e.g.,
typeCheck(Tup[Int 3]) returns