The purpose of this assignment is to get you acclimated to programming in ML:
By the time you complete this assignment, you will be ready to tackle serious programming tasks in core ML.
For this assignment, you should use Moscow ML, which is in /usr/sup/bin/mosml.
You should make extensive use of the
Standard ML Basis Library.
Jeff 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 "lib";
at the mosml interactive prompt.
If you use
ledit mosml -P fullas your interactive top-level loop, mosml will automatically load almost everything you might want from the standard basis.
There are some functions and idioms that you must avoid. Code violating any of these guidelines will earn No Credit.
length
function.
The entire assignment can and should be solved without using length
.
null
, hd
, and tl
.
local
or let
instead.
open
; if needed, use one-letter abbreviations for common structures.
Ullman provides a gentle introduction to ML, and his book is especially good for programmers whose primary experience is in C-like languages. But, to put it politely, Ullman's ML is not idiomatic. Much of what you see in Ullman should not be imitated. Ramsey's textbook is a better guide to what ML should look like. We also direct you to these resources:
Working on your own, please solve the exercises A, B, C, D, E, F, G, H, I, J, and K described below.
compound
is somewhat like 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 x
is 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.
Don't get confused by infix vs prefix operators. Remember this:
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 decribed 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 the module Int
uses 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
.
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 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,
<sample>+= [<-D->] - flatten [[1], [2, 3, 4], [], [5, 6]]; > val it = [1, 2, 3, 4, 5, 6] : int list
To 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
<sample>+= [<-D->] type 'a env = (* you fill in this part with a suitable list type *) exception NotFound of string val emptyEnv : 'a env = (* ... *) val bindVar : string * 'a * 'a env -> 'a env = (* ... *) val lookup : string * 'a env -> 'a = (* ... *)
DefinesbindVar
,emptyEnv
,env
,lookup
,NotFound
(links are to index).
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
<sample>+= [<-D->] fun lookup (name, rho) = rho name
Defineslookup
(links are to index).
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.
You shoud put these functions in the same file; don't worry about the later ones shadowing the earlier ones.
<sample>+= [<-D->] datatype 'a tree = NODE of 'a tree * 'a * 'a tree | LEAF
Definestree
(links are to index).
To 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
<sample>+= [<-D->] datatype order = LESS | EQUAL | GREATER (* do not include me in your code *)
Definesorder
(links are to index).
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.,
<sample>+= [<-D->] 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 end
Definesinsert
(links are to index).
This 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
I'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,
<sample>+= [<-D->] datatype 'a set = SET of ('a * 'a -> order) * 'a tree fun nullset cmp = SET (cmp, LEAF)
Definesnullset
,set
(links are to index).
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.
This is a challenge problem. The other problems on the homework all involve old wine in new bottles. To solve this problem, you have to think of something new.
'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.)
Document your representation by saying, in a short comment,
what sequence is
meant by any value of type '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.
Please think of these functions as "moving the finger", but remember no mutation is involved. Instead of changing an existing list, each function creates a new list.
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.
Hints: The key is to come up with a good representation for "list with finger." Once you have a good representation, the code is easy: over half the functions can be implemented in one line each, and no function requires more than two lines of code.
You may work with a partner on this problem.
The goal of this problem is to give you practice working with an algebraic data type that plays a central role in programming languages: expressions. In the coming month, you will write many functions that consume expressions; this problem will help you get off to a good start. It will also give you a feel for the kinds of things compiler writers do.
This problem asks you to explore the fact 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 you will want the handout on free variables, which is also available as Section 6.10 in your textbook.
You'll solve the problem in a prelude and four parts:
mlscheme-improved.sml
.
You will edit mlscheme-improved.sml
.
val freeIn : exp -> name -> bool
.
This predicate tells when a variable appears free in an expression.
It implements the proof rules on page 224 of the
handout.
I recommend that you compile early and often using
/usr/sup/bin/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 handout, on page 225, this environment is explained as the
restriction of the environment to the free variables.)
You should call this function improve
and 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 349.
You simply apply improve
to the pair that is already there, so
your improved interpreter looks like this:
(* more alternatives for ev
for ((mlscheme)) 349c *)
| ev (LAMBDA (xs, e)) = ( errorIfDups ("formal parameter", xs, "lambda")
; CLOSURE (improve ((xs, e), rho))
)
mlton -verbose 1 -output mlscheme mlscheme.sml mlton -verbose 1 -output mlscheme-improved mlscheme-improved.sml(If plain
mlton
doesn't work, try /usr/sup/bin/mlton
.)
I have provided a script that you can use to measure the improvement. I also recommend that you compare the performance of the ML code with the performance of the C code in the course directory.
time run-exponential-arg-max 22 ./mlscheme
time run-exponential-arg-max 22 ./mlscheme-improved
time run-exponential-arg-max 22 /comp/105/bin/uscheme
Hints:
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.
The implementation of freeIn
in the solutions is 21 lines of ML.
Extend μScheme to support procedures with a variable number of arguments.
Do so by giving the name ...
(three dots) special significance when it appears
as the last formal parameter in a lambda.
For example:
-> (val f (lambda (x y ...)) (+ x (+ x (foldl + 0 ...))) -> (f 1 2 3 4 5) ; inside f, rho = { x |-> 1, y |->, ... |-> '(3 4 5) } 15
In this example, it is an error for f
to get fewer than two arguments.
If f
gets at least two arguments, any additional arguments are placed into
an ordinary list, and the list is used to initialize the location of the
formal parameteter associated with ...
.
lambda
on
page 344 to
and lambda = name list * { varargs : bool } * exp
The type system will tell you what other code you have to change. For the parser, you may find the following function useful:
fun newLambda (formals, body) = case rev formals of "..." :: fs' => LAMBDA (rev fs', {varargs=true}, body) | _ => LAMBDA (formals, {varargs=false}, body)
The type of this function is
name list * exp -> name list * {varargs : bool} * exp
;
thus it is designed exactly for you to adapt old syntax to new syntax;
you just drop it into the parser wherever LAMBDA
was used.
call
primitive such that
(call f '(1 2 3))
is equivalent to
(f 1 2 3)
Sadly, you won't be able to use PRIMITIVE
for this;
you'll have to invent a new kind of thing that has access to the
internal eval
.
cons-logger
that
counts cons calls in a private variable. It should
operate as follows:
-> (val cl (cons-logger)) -> (val log-cons (car cl)) -> (val conses-logged (cdr cl)) -> (conses-logged) 0 -> (log-cons f e1 e2 ... en) ; returns (f e1 e2 ... en), incrementing ; private counter whenever cons is called -> (conses-logged) 99 ; or whatever else is the number of times cons is called ; during the call to log-cons
You should submit two or three files, depending upon whether you did the extra credit:
(***** 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:
% /usr/sup/bin/mosmlc -c warmup.sml %
You should submit one file: mlscheme-improved.sml
. You should include
the output of the commands listed in part (4) in comments in this file.
<patterns>= [D->] [] [x] [x, y] [a, b, c]
and also these patterns, which match lists of at least 0, 1, 2, or 3 elements:
<patterns>+= [<-D] xs x::xs x1::x2::xs a::b::c::xs
When using these patterns, remember that function application has higher precedence than any infix operator! This property is as true in patterns as it is anywhere else.
μScheme ML val val define fun lambda fn
<sample>+= [<-D] (* 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 *)
Definesaddelt
,atFinger
,bindVar
,compound
,deleteLeft
,deleteRight
,emptyEnv
,exp
,extendEnv
,ffoldl
,ffoldr
,fib
,fingerLeft
,fingerRight
,firstVowel
,flatten
,foldl
,foldr
,insertLeft
,insertRight
,isBound
,listOfSeq
,lookup
,minlist
,nth
,null
,pairfoldr
,rev
,sappend
,scons
,seqOfList
,setFold
,singletonOf
,ssnoc
,treeFoldr
,unzip
,zip
(links are to index).
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.
Here is a list of common mistakes to avoid:
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.
Back to the class home page