Assignment 5: Core ML

Due Friday, March 24th at 11:59PM.

The purpose of this assignment is to get you acclimated to programming in ML:

• On your own, you will write many small exercises.
• Possibly working with a partner, you will make a small change to the μScheme interpreter that is written in ML (in Chapter 5).

By the time you complete this assignment, you will be ready to tackle serious programming tasks in core ML.

Setup

For this assignment, you should use Moscow ML, which is in /usr/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.

Dire warnings

There are some functions and idioms that you must avoid. Code violating any of these guidelines will earn No Credit.

• When programming with lists, it is rarely necessary or desirable to use the length function. The entire assignment can and should be solved without using length.
• Use pattern matching to define functions. Do not use the functions null, hd, and tl.
• Do not define auxiliary functions at top level. Use local or let instead.
• Do not use open; if needed, use one-letter abbreviations for common structures.
• Do not use any imperative features unless the problem explicitly says it is OK.

Proper ML style

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:

• The course supplement to Ullman
• Harper, part II (with examples)
• The voluminous Style Guide for Standard ML Programmers

Individual Problems (90%)

Working on your own, please solve the exercises A, B, C, D, E, F, G, H, I, J, and K described below.

Higher-order programming

A. The function compound is somewhat like fold, but it works on binary operators.

1. Define the function

   val compound : ('a * 'a -> 'a) -> int -> 'a -> 'a
   

   that ``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.

2. Use the compound function to define a Curried function for integer exponentiation

   val exp : int -> int -> int
   

   so 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:

• Fixity is a property of an identifier, not of a value.
• If <$> is an infix identifier, then x <$> y is syntactic sugar for <$> applied to a pair containing x and y, which can also be written as op <$> (x, y).

Patterns

B. Write a function 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.

C. Write the function 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.

Lists

D. foldl and foldr are predefined with type

('a * 'b -> 'b) -> 'b -> 'a list -> 'b

They are like the μScheme versions except the ML versions are Curried.

1. Implement rev (the function known in μScheme as "reverse") using foldl or foldr.
2. Implement 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.

Do not use recursion in any of your solutions.

E. Implement foldl and foldr using recursion. Do not create unnecessary cons cells. Do not use if.

F. Define a function

val pairfoldr : ('a * 'b * 'c -> 'c) -> 'c -> 'a list * 'b list -> 'c

that applies a three-argument function to a pair of lists of equal length, using the same order as foldr.
Use pairfoldr to implement zip.

G. Define a function

val flatten : 'a list list -> 'a list

which 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 list
     

To get full credit for this problem, your function should use no unnecessary cons cells.

Exceptions

H. Write a (Curried) function

val nth : int -> 'a list -> 'a

to 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.)
I expect you to implement nth yourself and not simply call List.nth.

Environments

I.

1. Define a type 'a env and functions

   
   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 = (* ... *)
   

   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.

2. Do the same, except make type 'a env = string -> 'a, and let

   
   fun lookup (name, rho) = rho name
   

3. Write a function

   val isBound : string * 'a env -> bool
   

   that 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.
   

4. Write a function

   val extendEnv : string list * 'a list * 'a env -> 'a env
   

   that 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 should put these functions in the same file; don't worry about the later ones shadowing the earlier ones.

Algebraic data types

J. Search trees.
ML can easily represent binary trees containing arbitrary values in the nodes:

datatype 'a tree = NODE of 'a tree * 'a * 'a tree 
                 | LEAF

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

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
    end

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,

datatype 'a set = SET of ('a * 'a -> order) * 'a tree
fun nullset cmp = SET (cmp, LEAF)

• Write a function

  val addelt : 'a * 'a set -> 'a set
  

  that adds an element to a set.
• Write a function

  val treeFoldr : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b
  

  that 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 -> 'b
  

  The function setFold should visit every element of the set exactly once, in an unspecified order.

An immutable, persistent alternative to linked lists

K. This problem asks you to define your own representation of a new abstraction: the list with finger. A list with finger is a nonempty sequence of values, together with a ``finger'' that points at one position in the sequence. The abstraction provides constant-time insertion and deletion at the finger.

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.

1. Define a representation for type '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.

2. Define function

   val singletonOf : 'a -> 'a flist
   

   which returns a sequence containing a single value, whose finger points at that value.

3. Define function

   val atFinger : 'a flist -> 'a
   

   which returns the value that the finger points at.

4. Define functions

     val fingerLeft  : 'a flist -> 'a flist
     val fingerRight : 'a flist -> 'a flist
   

   Calling 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.

5. Define functions

     val deleteLeft  : 'a flist -> 'a flist
     val deleteRight : 'a flist -> 'a flist
   

   Calling 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.

6. Define functions

     val insertLeft  : 'a * 'a flist -> 'a flist
     val insertRight : 'a * 'a flist -> 'a flist
   

   Calling 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".)

7. Define functions

     val ffoldl : ('a * 'b -> 'b) -> 'b -> 'a flist -> 'b
     val ffoldr : ('a * 'b -> 'b) -> 'b -> 'a flist -> 'b
   

   which 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.

Pair Problem (10%)

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 to read Section 5.10 in your textbook. This problem appears in Ramsey’s book as exercise 2 on page 375, and you’ll solve it in a prelude and four parts:

• The prelude is to go to your copy of the book code and copy the file bare/uscheme-ml/mlscheme.sml to your working directory. (This code contains all of the interpreter from Chapter 5.) Then make another copy and name it mlscheme-improved.sml. You will edit mlscheme-improved.sml.

• The first part is to implement the free-variable predicate

  val freeIn : exp -> name -> bool.

  This predicate tells when a variable appears free in an expression. It implements the proof rules in section 5.10 of the book, which starts on page 368..
  I recommend that you compile early and often using

       /usr/sup/bin/mosmlc -c mlscheme-improved.sml
  

• The second part is to write a function that takes a pair consisting of a 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, in exercise 1 starting on page 374, 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

• The third part is to use improve in the evaluation case for LAMBDA, which appears in the book on page 357b. 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))
                                  )
  

Hints:

• Focus on function 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)
  

• The code for 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
  

• It's easier to write 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.

• If you can apply what you have learned on the scheme and hofs assignments, you should be able to write improve on one line, without using any explicit recursion.

• Let the compiler help you: compile early and often.

The implementation of freeIn in the solutions is 21 lines of ML.

What to submit

There is no README file for this assignment.

• For your individual work, please submit the file warmup.sml

      turnin -c cs456 -p ml-solo warmup.sml
  

  In 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.
• For your joint work, please submit mlscheme-improved.sml

      turnin -c cs456 -p ml-pair mlscheme-improved.sml
  

How your work will be evaluated

The criteria are essentially the same as for the scheme and hofs assignments, but subject to the voluminous Style Guide for Standard ML Programmers.

Hints

• Some useful list patterns include the following patterns that match lists of exactly 0, 1, 2, or 3 elements:

  
  []
  [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::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.
• The following table may help you transfer your knowledge of μScheme to ML:

  μScheme	ML
  val	val
  define	fun
  lambda	fn

• Make sure your solutions have the right types. On this assignment, it is a very common mistake to define functions of the wrong type. You can protect yourself a little bit by loading declarations like the following after loading your solution:

  
  (* 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.

Avoid common mistakes

Here is a list of common mistakes to avoid:

• If you redefine a type that is already in the initial basis, code will fail in baffling ways. (If you find yourself baffled, exit the interpreter and restart it.)
• Redefining a function at the top-level is fine unless that function captures one of your own functions in its closure. Example:

        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.
• Never put a semicolon after a definition.
  You should have a semicolon only if you are deliberately using imperative features.
• It's a common mistake to become very confused about where you need to use op. Ullman covers op in Section 5.4.4, page 165.
• It's a common mistake to include redundant parentheses in your code. To avoid this mistake, follow the directions in the course supplement to Ullman.

How your work will be evaluated

The criteria are analogous to those for the scheme and hofs assignments.