The purpose of this assignment is to help you get acclimated to programming in ML:
You will be more effective if you are aware of the
Standard ML Basis Library.
Ullman's text (Chapter 9) describes the 1997 basis, but today's
compilers use the 2004 basis, which is a standard. You will find a few
differences in I/O, arrays, and elsewhere; the most salient difference is
in TextIO.inputLine
.
The most convenient guide to the basis is the Moscow ML help system; type
- help "";at the mosml interactive prompt.
length
function. The entire assignment can and should be
solved without using length
.
Solutions that use length
will earn No Credit.
null
, hd
,
and tl
; use patterns instead.
Code using hd
or tl
will earn No Credit.
local
or let
.
Problems defining auxiliary functions at top level will earn No Credit.
open
;
if needed, use one-letter abbreviations for common structures.
Code using open
may earn No Credit for your entire assignment.
[] [x] [x, y] [a, b, c]and also these patterns, which match lists of at least 0, 1, 2, or 3 elements:
xs x::xs x1::x2::xs a::b::c::xsWhen using these patterns, remember that function application has higher precedence than any infix operator! This is as true in patterns as it is anywhere else.
Use the standard basis extensively. Moscow ML's help
"lib";
will tell you all about the library. And if you use
rlwrap mosml -P fullas your interactive top-level loop, it will automatically load almost everything you might want from the standard basis.
All the sample code we show you is gathered in one place online.
As you learn ML, this table may help you transfer your knowledge of μScheme:
μScheme ML val val define fun lambda fn
Put all your solutions in one file: warmup.sml. (If separate files are easier, combine them with cat.) At the start of each problem, please label it with a short comment, like
(***** Problem A *****)To receive credit, your warmup.sml file must compile and execute in the Moscow ML system. For example, we must be able to compile your code without warnings or errors:
% mosmlc -c warmup.smlPlease remember to put your name and the time you spent in the warmup.sml file.
fold
,
but it works on binary operators.
val compound : ('a * 'a -> 'a) -> int -> 'a -> 'athat "compounds" a binary operator
rator
so that
compound rator n xis
x
if n=0
, x rator x
if n = 1
, and in
general x rator (x rator (... rator x))where
rator
is applied exactly n
times.
compound rator
need not behave well when applied to negative
integers.
compound
function to define a Curried function for
integer exponentiation val exp : int -> int -> intso that, for example,
exp 3 2
evaluates to 9.
Hint: take note of the description of op
in Ullman
S5.4.4, page 165.
(x::y::zs, w)
. For
each of the following expressions, tell whether the pattern matches the
value denoted. If the pattern matches, say what values are bound to the
four variables x
, y
, zs
,
and w
. If it does not match, explain why not.
([1, 2, 3], ("COMP", 105))
(("COMP", 105), [1, 2, 3])
([("COMP", 105)], (1, 2, 3))
(["COMP", "105"], true)
([true, false], 2.718281828)
if
. Calling fib n
should
return the n
th Fibonacci number, e.g,. fib 0
is 0, fib 1
is 1, fib 4
is 3.
Taking exponential time is OK.
firstVowel
that takes a
list of lower-case letters and returns true
if the first
character is a vowel (aeiou) and false
if the first character
is not a vowel or if the list is empty. Use the wildcard
symbol _
whenever possible, and avoid if
.
Remember that the ML character syntax is #"x"
,
as described in Ullman, page 13.
null
, which when applied
to a list tells whether the list is empty. Avoid if
, and
make sure the function takes constant time. Make sure your function has
the same type as the null
in the Standard Basis.
foldl
and foldr
are predefined
with type ('a * 'b -> 'b) -> 'b -> 'a list -> 'bThey are like the μScheme versions except the ML versions are Curried.
rev
(the function known in μScheme as
"reverse
") using foldl
or foldr
.
minlist
, which returns the smallest element
of a non-empty list of integers. Your solution should work regardless
of the representation of integers (e.g., it should not matter how many
bits are used to represent integers). Your solution can fail (e.g.,
by raise Match
) if given an empty list of integers.
Use foldl
or foldr
.
foldl
and foldr
using
recursion. Do not create unnecessary cons cells. Do not
use if
.
zip: 'a list * 'b list -> ('a * 'b) listthat takes a pair of lists (of equal length) and returns the equivalent list of pairs. If the lengths don't match, raise the exception
Mismatch
, which
you will have to define.
val pairfoldr : ('a * 'b * 'c -> 'c) -> 'c -> 'a list * 'b list -> 'cthat applies a three-argument function to a pair of lists of equal length, using the same order as
foldr
.
pairfoldr
to implement zip
.
val unzip : ('a * 'b) list -> 'a list * 'b listthat turns a list of pairs into a pair of lists. This one is tricky; here's a sample result:
- unzip [(1, true), (3, false)]; > val it = ([1, 3], [true, false]) : int list * bool listHint: Try defining an auxiliary function, using
let
, that
takes one or more accumulating parameters. And be prepared to
use rev
.
val flatten : 'a list list -> 'a listwhich takes a list of lists and produces a single list containing all the elements in the correct order. For example,
- flatten [[1], [2, 3, 4], [], [5, 6]]; > val it = [1, 2, 3, 4, 5, 6] : int listTo get full credit for this problem, your function should use no unnecessary cons cells.
val nth : int -> 'a list -> 'ato return the nth element of a list. (Number elements from 0.) If
nth
is given arguments on which it is not defined, raise a
suitable exception. You may define one or more suitable exceptions or you may
choose to use an appropriate one from the initial basis. (If you have
doubts about what's appropriate, play it safe and define an exception of your
own.)
nth
yourself and
not simply call List.nth.
'a env
and functions
type 'a env = (* you fill in this part *) exception NotFound of string val emptyEnv : 'a env = (* ... *) val bindVar : string * 'a * 'a env -> 'a env = (* ... *) val lookup : string * 'a env -> 'a = (* ... *)such that you can use
'a env
for a type environment or a value
environment. On an attempt to look up an identifier that doesn't exist, raise
the exception NotFound
. Don't worry about efficiency.
type 'a env = string -> 'a
, and let
fun lookup (name, rho) = rho name
val isBound : string * 'a env -> boolthat works with both representations of environments. That is, write a single function that works regardless of whether environments are implemented as lists or as functions. You will need imperative features, like sequencing (the semicolon). Don't use
if
.
val extendEnv : string list * 'a list * 'a env -> 'a envthat takes a list of variables and a list of values and adds the corresponding bindings to an environment. It should work with both representations. Do not use recursion. Hint: you can do it in two lines using the higher-order list functions defined above.
datatype 'a tree = NODE of 'a tree * 'a * 'a tree | LEAFTo make a search tree, we need to compare values at nodes. The standard idiom for comparison is to define a function that returns a value of type
order
. As discussed in Ullman,
page 325, order
is predefined by
datatype order = LESS | EQUAL | GREATER (* do not include me in your code *)Because
order
is predefined, if you include it in your program,
you will hide the predefined version (which is in the initial basis) and
other things may break mysteriously. So don't include it.
We can use the order
type to define a higher-order insertion
function by, e.g.,
fun insert cmp = let fun ins (x, LEAF) = NODE (LEAF, x, LEAF) | ins (x, NODE (left, y, right)) = (case cmp (x, y) of LESS => NODE (ins (x, left), y, right) | GREATER => NODE (left, y, ins (x, right)) | EQUAL => NODE (left, x, right)) in ins endThis higher-order insertion function accepts a comparison function as argument, then returns an insertion function. (The parentheses around
case
aren't actually necessary here, but
we've included them because if you leave them out when they
are needed, you will be very confused by the
resulting error messages.)
We can use this idea to implement polymorphic sets in which we store the comparison function in the set itself. For example,
datatype 'a set = SET of ('a * 'a -> order) * 'a tree fun nullset cmp = SET (cmp, LEAF)
val addelt : 'a * 'a set -> 'a setthat adds an element to a set.
val treeFoldr : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'bthat folds a function over every element of a tree, rightmost element first. Calling
treeFoldr op :: [] t
should return the elements
of t
in order. Write a similar function
val setFold : ('a * 'b -> 'b) -> 'b -> 'a set -> 'bThe function
setFold
should visit every element of the set
exactly once, in an unspecified order.
A sequence is either empty, or it is a singleton sequence containing one element x, or it is one sequence followed by another sequence.
'a seq
that
corresponds to this definition of sequences. As always, your definition
should contain one value constructor for each alternative.
scons : 'a * 'a seq -> 'a seq
that adds a
single element to the front of a sequence, using constant time and
space.
ssnoc : 'a * 'a seq -> 'a seq
that adds a
single element to the back of a sequence, using constant time
and space.
ssnoc (x, xs)
, x
follows xs
.
(The arguments are the way they are so that ssnoc
can be used
with foldl
and foldr
.)
sappend : 'a seq * 'a seq -> 'a seq
that
appends two sequences, using constant time and space.
listOfSeq : 'a seq -> 'a list
that
converts a sequence into a list containing the same elements in the same
order.
Your function must allocate only as much space as
is needed to hold the result.
seqOfList : 'a list -> 'a seq
that converts an ordinary
list to a sequence containing the same elements in the same order.
'a flist
. (Before you can
define a representation, you will want to study the rest of the parts of
this problem, plus the test cases.)
'a flist
.
val singletonOf : 'a -> 'a flistwhich returns a sequence containing a single value, whose finger points at that value.
val atFinger : 'a flist -> 'awhich returns the value that the finger points at.
val fingerLeft : 'a flist -> 'a flist val fingerRight : 'a flist -> 'a flistCalling
fingerLeft xs
creates a new list that is
like xs
, except the finger is moved one position to the left.
If the finger belonging to xs
already points to the
leftmost position, then fingerLeft xs
should raise the same
exception that the Basis Library raises for array access out of bounds.
Function fingerRight
is similar. Both functions must run
in constant time and space.
val deleteLeft : 'a flist -> 'a flist val deleteRight : 'a flist -> 'a flistCalling
deleteLeft xs
creates a new list that is
like xs
, except the value x
to the left
of the finger has been removed. If the finger points to the leftmost
position, then deleteLeft
should raise the same exception that
the Basis Library raises for array access out of bounds.
Function deleteRight
is similar. Both functions must run
in constant time and space. As before, no mutation is
involved.
val insertLeft : 'a * 'a flist -> 'a flist val insertRight : 'a * 'a flist -> 'a flistCalling
insertLeft (x, xs)
creates a new list that is
like xs
, except the value x
is inserted
to the left of the finger. Function insertRight
is similar.
Both functions must run in constant time and space.
As before, no mutation is involved. (These functions are related to
"cons".)
val ffoldl : ('a * 'b -> 'b) -> 'b -> 'a flist -> 'b val ffoldr : ('a * 'b -> 'b) -> 'b -> 'a flist -> 'bwhich do the same thing as
foldl
and foldr
, but
ignore the position of the finger.
Here is a simple test case, which should produce a list containing the
numbers 1 through 5 in order. You can use ffoldr
to
confirm.
val test = singletonOf 3 val test = insertLeft (1, test) val test = insertLeft (2, test) val test = insertRight (4, test) val test = fingerRight test val test = insertRight (5, test)You'll want to test the delete functions as well.
In this problem we will observe that a compiler doesn't need to store an entire environment in a closure; it only needs to store the free variables of its lambda expression. For the details see Section 5.9 on page 225 of Ramsey. (The exercise is Exercise 2 from Section 5.10 on page 227 of the book.)
You'll solve the problem in a prelude and several parts:
mlscheme-improved.sml
. You
will edit mlscheme-improved.sml
.
val freeIn : exp -> name -> boolThis predicate tells when a variable appears free in an expression, and it implements the proof rules on page 226 of the book.
During this part I recommend that you compile early and often using
mosmlc -c mlscheme-improved.sml
LAMBDA
body and an environment, and returns a better pair
containing the same LAMBDA
body paired with an environment that
contains only the free variables of the LAMBDA
. (In the book,
on page 227, this environment is explained as the
restriction of the environment to the free variables.) We recommend
that you call this function improve
, and that you give it the
type
val improve : (name list * exp) * 'a env -> (name list * exp) * 'a env
improve
in the evaluation case
for LAMBDA
, which appears in the book on page 218b. You simply
apply improve
to the pair that is already there, so your improved
interpreter looks like this:
(* more alternatives for [[ev]] ((mlscheme)) 218b *) | ev (LAMBDA l) = CLOSURE (improve (l, rho))
freeIn
. This is the only recursive function
and the only function that requires case analysis on expressions. And it is
the only function that requires you to understand the concept of free
variables. You will be using all of these concepts on future
assignments.
In Standard ML, the μScheme function exists?
is
called List.exists
. You'll have lots of opportunities to use it.
If you don't use it, you're making extra work for yourself.
In addition to List.exists
, you may have a use
for map
, foldr
, foldl
,
or List.filter
.
You might also have a use for these functions:
fun fst (x, y) = x fun snd (x, y) = y fun member (y, []) = false | member (y, z::zs) = y = z orelse member (y, zs)
LETSTAR
is gnarly, and writing it adds little to the
experience.
Here are two algebraic laws which may help:
freeIn (LETX (LETSTAR, [], e)) y = freeIn e y freeIn (LETX (LETSTAR, b::bs, e)) y = freeIn (LETX (LET, [b], LETX (LETSTAR, bs, e))) y
freeIn
if you use nested functions. Mostly
the variable y doesn't change, so you needn't pass it everywhere.
You'll see the same technique used in the eval
and ev
functions in the chapter.
improve
on
one line, without using any explicit recursion.
freeIn
is 21 lines of ML.
(* first declaration for sanity check *) val compound : ('a * 'a -> 'a) -> int -> 'a -> 'a = compound val exp : int -> int -> int = exp val fib : int -> int = fib val firstVowel : char list -> bool = firstVowel val null : 'a list -> bool = null val rev : 'a list -> 'a list = rev val minlist : int list -> int = minlist val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b = foldl val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b = foldr val zip : 'a list * 'b list -> ('a * 'b) list = zip val pairfoldr : ('a * 'b * 'c -> 'c) -> 'c -> 'a list * 'b list -> 'c = pairfoldr val unzip : ('a * 'b) list -> 'a list * 'b list = unzip val flatten : 'a list list -> 'a list = flatten val nth : int -> 'a list -> 'a = nth val emptyEnv : 'a env = emptyEnv val bindVar : string * 'a * 'a env -> 'a env = bindVar val lookup : string * 'a env -> 'a = lookup val isBound : string * 'a env -> bool = isBound val extendEnv : string list * 'a list * 'a env -> 'a env = extendEnv val addelt : 'a * 'a set -> 'a set = addelt val treeFoldr : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b = treeFoldr val setFold : ('a * 'b -> 'b) -> 'b -> 'a set -> 'b = setFold val scons : 'a * 'a seq -> 'a seq = scons val ssnoc : 'a * 'a seq -> 'a seq = ssnoc val sappend : 'a seq * 'a seq -> 'a seq = sappend val listOfSeq : 'a seq -> 'a list = listOfSeq val seqOfList : 'a list -> 'a seq = seqOfList val singletonOf : 'a -> 'a flist = singletonOf val atFinger : 'a flist -> 'a = atFinger val fingerLeft : 'a flist -> 'a flist = fingerLeft val fingerRight : 'a flist -> 'a flist = fingerRight val deleteLeft : 'a flist -> 'a flist = deleteLeft val deleteRight : 'a flist -> 'a flist = deleteRight val insertLeft : 'a * 'a flist -> 'a flist = insertLeft val insertRight : 'a * 'a flist -> 'a flist = insertRight val ffoldl : ('a * 'b -> 'b) -> 'b -> 'a flist -> 'b = ffoldl val ffoldr : ('a * 'b -> 'b) -> 'b -> 'a flist -> 'b = ffoldr (* last declaration for sanity check *)I don't promise to have all the functions and their types here. Making sure that every function has the right type is your job, not mine.
length
, hd
, and tl
. Instant
No Credit.
fun f x = ... stuff that is broken ... fun g (y, z) = ... stuff that uses 'f' ... fun f x = ... new, correct version of 'f' ...You now have a situation where
g
is broken, and the
resulting error is very hard to detect. Stay out of this
situation; instead, load fresh definitions from a file using
the use
function.
op
.
Ullman covers op
in Section 5.4.4, page 165.
warmup.sml
turnin -c cs456 -p ml-solo warmup.smlIn comments at the top of your
warmup.sml
file, please include
your name, the names of any collaborators, and the number of hours you spent
on the assignment.
mlscheme-improved.sml
turnin -c cs456 -p ml-pair mlscheme-improved.sml