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, 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,2,3,4,5]
returns 120
[1,2,3,4,5]
gives result ([1,3,5],[2,4])
.
[fn x => x + 1, fn x => x - 1, fn x => x * ~1, fn x => x*x]
returns 2.
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
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],[]]
.
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 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 [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.
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 typeCheck
on this returns MyInt
.
#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 MyInt
.
typeCheck(Tup [Int 4, Int 5])
results in
MyTuple[MyInt, MyInt]
.
typeCheck(Let("x",MyInt, Plus(Int 3, Int 6),
Plus(Var "x", Var "x")))
returns MyInt
.
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
typeCheck(Tup[])
returns MyUnit
. For
length-1 tuples, return the type of their one element; e.g.,
typeCheck(Tup[Int 3])
returns MyInt
.