COMP 105 Assignment: Core ML

Due Sunday, October 23, 2016 at 11:59 PM

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.

Setup

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 full
as your interactive top-level loop, mosml will automatically load almost everything you might want from the standard basis.

Dire warnings

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

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:

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

  1. 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:

Patterns

  1. 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 described in Ullman, page 13.

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

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

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

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

  4. 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,
    <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.

Exceptions

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

  2. Environments
    1. Define a type '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 = (* ... *)
      
      Defines bindVar, 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.

    2. Do the same, except make type 'a env = string -> 'a, and let
      <sample>+= [<-D->]
      fun lookup (name, rho) = rho name
      
      Defines lookup (links are to index).

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

Algebraic data types

  1. Search trees.
    ML can easily represent binary trees containing arbitrary values in the nodes:
    <sample>+= [<-D->]
    datatype 'a tree = NODE of 'a tree * 'a * 'a tree 
                     | LEAF
    
    Defines tree (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 *)
    
    Defines order (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
    
    Defines insert (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)
    
    Defines nullset, set (links are to index).

An immutable, persistent alternative to linked lists

  1. 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 look at Section 5.10 in your textbook.

You'll solve the problem in a prelude and four parts:

Hints:

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

Extra credit


VARARGS

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

  1. Implement this new feature inside of mlscheme.sml. I recommend that you begin by changing the definition of lambda on page 356 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.

  2. As a complement to the varargs lambda, write a new 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.

  3. Demonstrate these utilities by writing a higher-order function 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
    
  4. Rewrite the APPLY-CLOSURE rule to account for the new abstract syntax and behavior. To help you, simplified LaTeX for the original rule is online.

What to submit: Individual Problems

You should submit two or three files, depending upon whether you did the extra credit:

How to submit: Individual Problems

When you are ready, run submit105-ml-solo to submit your work. Note you can run this script multiple times; we will grade the last submission.

What to submit: Pair Problem

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.

How to submit: Pair Problems

When you are ready, run submit105-ml-pair to submit your work. Note you can run this script multiple times; we will grade the last submission.

Hints

Avoid common mistakes

Here is a list of common mistakes to avoid:

How your work will be evaluated

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

Index and cross-reference

Back to the class home page