CS223, 5/10/2010
Lecture 16

Reading:
1. Paulson: Sections 2.20 - 2.22 (pp. 59-64),
            Chapter 7 (pp. 257-312)
2. Tofte: Essentials of Standard ML Modules
   (pdf link on course web page. This is somewhat
    old and out of date, but still useful.)


Modules in SML: Functors
========================

Problem: to generalize the ordered alist implementation for keys other than strings.

Observe: the key type has to be ordered (i.e. there needs to be a compare operation
for it, and of course this operation should define a linear ordering on keys).

In Haskell, we could require that the type have an instance of the Ord class defined
for it.

In SML, we have two possibilities:

1. Pass the compare operation as an additional parameter to all functions that need
to do comparison on keys.

structure Alist4 =
struct
  type ('k,'a) alist = ('k * 'a) list

  exception Unbound

  val empty : ('k, 'a) alist = []

  fun insert compare (k, v, []) = [(k,v)]
    | insert compare (k, v, alist as ((k',v')::alist')) =
      (case compare(k,k')
         of (LESS | EQUAL) => (k,v)::alist
          | GREATER => (k',v')::(insert compare (k,v,alist')))

  fun bind compare (k: 'k, v: 'a, alist: ('k,'a) alist) = 
      insert compare (k, v, alist)

  fun lookup compare (k: 'k, nil: ('k,'a) alist) = raise Unbound
    | lookup compare (k, (k',v)::alist) = 
      (case compare(k,k')
         of LESS => raise Unbound
          | EQUAL => v 
          | GREATER => lookup compare (k,alist))
end;

This would match the signature

signature ALIST4 =
sig
  type ('a,'b) alist
  exception Unbound
  val empty : ('a,'b) Alist4.alist
  val bind : ('a * 'a -> order)
             -> 'a * 'b * ('a,'b) alist -> ('a,'b) alist
  val lookup : ('a * 'a -> order) -> 'a * ('a,'b) alist -> 'b
end

We could specialize these generalized alists to the case where
the key type is string as follows:

type 'a stringAlist = (string, 'a) Alist4.alist

- val bind = (fn x => Alist4.bind String.compare x);
val bind = fn : string * 'a * (string,'a) alist -> (string * 'a) list
- val lookup = (fn x => Alist4.lookup String.compare x);
val lookup = fn : string * (string * 'a) list -> 'a

- val al = bind("x", 2, bind("y", 3, empty));
val al = [("x",2),("y",3)] : (string * int) list

------------------------------------------
Digression -- the Value Restriction

Note that the definitions of the specialized string
versions of bind and lookup above use an "eta-expanded"
form (\x.Mx rather than M where M is a function
valued expression that is not syntactically a
function abstraction. In this case M = Alist4.bin String.compare).

This is because of the potential unsoundness in the SML
type system illustrated by the following example:

let val r = ref []
 in r := [1];
    if hd(!(r)) then 1 else 3
end;

If the normal rules of type checking are applied to the
local definition of r, we asign r the polymorphic type

   r : 'a list ref

and then the two occurrences of r in the body both type
check with the instance types:

   [r := [1]]  => r : int list ref
   [if (hd(!r)) ...]  => r : bool list ref

but this is clearly unsound, since it causes us to treat
the integer 1 as a boolean value. 

We prevent this unsoundness by not allowing polymorphic
generalizations for variable bindings where the rhs
definition is not a "value" expression.  Value expressions
include constants, variables, and function abstractions,
but not applications like "ref []".

The value restriction doesn't allow us to generalize the
type of r at its definition, so we get

  r : Y list ref

for some unification variable Y. The first occurrence
of r in the body causes Y to be instantiated to int,
so the type of hd(!r) will then be int, which will give
rise to a type error when typing the conditional expression.

At top level, e.g.

  - val r = ref [];
  stdIn:1.5-1.15 Warning: type vars not generalized because of
      value restriction are instantiated to dummy types (X1,X2,...)
  val r = ref [] : ?.X1 list ref

the compiler eliminates the ungeneralized unification variable
Y by instantiating it to a fresh tycon X1 (which prints as
"?.X1" because it has never been declared, so its nonexistant
name binding will not be in scope).

------------------------------------------

2. Functors

Having each individual function take compare as an extra argument
is cumbersome, and it gets more so when the parameter type (here key)
needs several functions, and the abstraction we are defining
involves many functions (not just two: bind and lookup, as for alists).

We can parameterize the abstraction "wholesale" by defining a
module function (or "functor" for short) whose parameter specifies
the types we want to parameterize over, and their associateed
interface of functions.

signature ORD =
sig
  type t
  val compare : t * t -> order
end

functor AlistFn (Key: ORD) =
struct
 
  type key = Key.t

  type 'a alist = (key * 'a) list

  exception Unbound

  val empty : 'a alist = []

  fun insert (k: key, v: 'a, []: 'a alist) = [(k,v)]
    | insert (k, v, alist as (k',v')::alist') =
      (case Key.compare(k,k')
         of (LESS | EQUAL) => (k,v)::alist
          | GREATER => (k',v')::(insert(k,v,alist')))

  fun bind (k: key, v: 'a, alist: 'a alist) = 
      insert (k, v, alist)

  fun lookup (k: key, []: 'a alist) = raise Unbound
    | lookup (k, (k',v)::alist) = 
      (case Key.compare(k,k')
         of LESS => raise Unbound
          | EQUAL => v 
          | GREATER => lookup(k,alist))
end;


Now we can define alists with string keys by applying the
Alist5 functor:

structure StringOrd: ORD =
struct
  type t = string
  val compare = String.compare
end;

structure AlistString = AlistFn(StringOrd);


The Alist structures produced by the AlistFn could be
given the following signature:

signature ALIST5 =
  sig
    type key
    type 'a alist
    exception Unbound
    val empty : 'a alist
    val bind : key * 'a * 'a alist -> 'a list
    val lookup : key * 'a alist -> 'a
  end;

and we could use this in the functor definition to
opaquely ascribe it to the functor result, making
the alist type constructor abstract:

functor AlistFn (Key: ORD) :> ALIST5 =
struct
  ...
end;

But unfortunately this also makes the key type abstract,
which prevents us from building any alists (as discussed
in class).  We could fix this problem by expanding
out the ALIST5 defintion and using a definitional spec
for the key type:

functor AlistFn (Key: ORD) :>
 sig
    type key = Key.t
    type 'a alist
    exception Unbound
    val empty : 'a alist
    val insert : key * 'a * 'a alist -> 'a list
    val bind : key * 'a * 'a alist -> 'a list
    val lookup : key * 'a alist -> 'a
  end =
struct
  ...
end;

But we have a way of doing this by modifying or
qualifying the ALIST5 signature with a "where type"
clause:

functor AlistFn (Key: ORD) :> ALIST5 where type key = Key.t  =
struct
  ...
end;

Here the where clause "where type key = Key.t" adds a 
definition of the key type in ALIST5 "after the fact",
as though the signature had been expanded in place and
modified as in the example just above. This allows us
to avoid duplicating the code of the signature.

--------------------------
Another example parameterizing by ORD: Sorting

In Homework 3, Problem 1 (sol3.txt) we saw several
list sorting algorithms in Haskell.  These were
polymorphic over types of class Ord. Here is the
equivalent example in SML, where we express the
parameterization using a functor.

  signature SORT =
  sig
    type elem
    val sort : elem list -> elem list
  end;

  functor MergeSort(X: ORD) : SORT = 
  struct
    type elem = X.t

    (* merge : elem list -> elem list -> elem list *)
    fun merge ([], ys) = ys
      | merge (xs, []) = xs
      | merge (xs' as (x::xs), ys' as (y::ys)) = 
	case X.compare(x,y)
	  of LESS => x :: merge(xs,ys')
	   | _ => y :: merge(xs',ys)

    (* sort : elem list -> elem list *)
    fun sort [] = []
      | sort [x] = [x]
      | sort xs =
	let val half = length xs div 2
	    val xs' = List.take(xs, half)
	    val ys' = List.drop(xs, half)
	 in merge (sort xs', sort ys')
	end  
  end;

Now to sort strings, we create a structure StringSort
by applying the MergeSort functor.

  structure StringSort = MergeSort(StringOrd);

Further Examples:

Many of the utility library modules in the SML/NJ Library
are functors.  Paulson, Chapter 7 also provides a number
of examples. See also Homework 5, Problem 2, in which
a Unify functor is defined.

-----------------------------------------------------
Sharing.

Here is an artificial and hypothetical example, but
it provides a simple illustration of a fairly common
issue.

  signature S1 =
  sig
    type t
    val f : t -> int
  end;

  signature S2 =
  sig
    type s
    val g : string -> s
  end;

  functor F(structure X: S1  structure Y: S2) =
  struct
    val a: int = X.f(Y.g "abc")
  end;


Here the expression X.f(Y.g "abc") will not typecheck,
because we don't know that X.t == Y.s. To use these
formal structures together we must relate their types
(essentially telling the compiler explicity to assume
X.t == Y.s.  We can do this with a "where type" clause
modifying S2:

  functor F(structure X: S1
            structure Y: S2 where type s = X.t) =
  struct
    val a: int = X.f(Y.g "abc")
  end;

This where clause specifies sharing of types between
the two formal parameter structures X and Y.

Where clauses were introduced in SML 97. The original
version of the language, SML 90, used "sharing specs"
for the same purpose. Using sharing specs, our functor
would look like:

  functor F(structure X: S1
            structure Y: S2
            sharing type Y.s = X.t) =
  struct
    val a: int = X.f(Y.g "abc")
  end;


----------------------------------------------------
Notation:

A functor with a parameter spec that looks like
the body of a signature, such as:

  functor F(structure X: S1
            structure Y: S2 where type s = X.t) =
  struct
    val a: int = X.f(Y.g "abc")
  end;

is an abbreviation for the more explicit form where
there is a single structure parameter. E.g. in this
case:

  functor F(Z: sig
                 structure X: S1
                 structure Y: S2 where type s = X.t
               end) =
  struct
    val a: int = Z.X.f(Z.Y.g "abc")
  end;
----------------------------------------------------