-- 15-212B Recitation 8: Modules
-- March 14, 2001
-- Joshua Dunfield (www.cs.cmu.edu/~joshuad)
-- Carnegie Mellon University

Admin.:
  a. Hand back hw3's
  b. "notes for this rec are online"

Outline:
  1. Functors for sets; transparent vs. opaque vs. opaque + "where type"
  2. Multi-argument functors and sharing constraints
 [3. `open' and `include']


_Functors_ are parameterized structures.  Given that we have
signatures and structures, functors ought to be called functures ;-)
Next thing you know SML/NJ will tell you:
  26.23-29: incompatible morphisms
But I digress.

Example: sets.

    signature SET = sig
      type set
      type elem
      val empty : set
      val incl : elem -> set -> set
      val excl : elem -> set -> set
      val has : set -> elem -> bool
    [ val toString : set -> string ]  omit at first
    end

No 'a or ''a anywhere (unlike the multisets that were on the midterm);
we're going to functorize.

    functor ListFn (Eq : EQ) : SET  =
    struct
      type elem = Eq.t
      type set = elem list
	(* invariant: no element occurs more than once *)

      val empty = []
      fun incl x s = if has s x then s else x::s
      fun excl x [] = []
	| excl x (y::s) = if Eq.eq(x,y) then s else y::(excl x s)
      fun has s x = List.exists (fn y => Eq.eq(x,y)) s
    end

where

    signature EQ = sig
      type t
      val eq : t * t -> bool
    end

Property we'd like to have hold:  for all x, s of appropriate types,
has (excl x s) x = false.

Is this enough?  No, have to apply the functor:
structure IntList = ListFn(IntEq)

and to do that, we have to write IntEq:

    structure IntEq : EQ = struct
      type t = int
      fun eq (a,b) = (a = b)
    end

If we want types other than int, have to write StringEq, etc.

What's wrong with the above?  Well, this is legal:

(outside the body of ListFn)
  s, s' : IntFn.set
  val u = s @ s'
Now has(excl x s) x could be true, if x is in both s and s'!

(...based on a true story.)

OK, so let's be smart and use opaque ascription to hide
the implementation of the `set' type

  functor ListFn (Eq : EQ) :> SET  =

This is legal, but useless!  Why?  We've also made the
`elem' type opaque.  We can't build any non-empty sets!

This is why "where type" was invented.  (Earlier versions
of SML lacked "where type".)  "where type" lets us _selectively_
make one or more types transparent.

  functor ListFn (Eq : EQ) :> SET where type elem = Eq.t
  = struct ...

You may be thinking the now-opaque ascription is a bit inconvenient
for debugging, since SML will just print "val it = - : IntList.set".
OK, but a better long term solution is to add a toString function
to the structure.  Here's how.

First we add a toString to the signature SET:
signature SET = sig ... val toString : set -> string end

If we start implementing toString inside ListFn, we'll soon
discover we don't have a way of getting the string representation
of each element!  Without this, we have no chance to survive.
Let's do the same thing we did for equality.

We write a new signature PRINTABLE similar to EQ,
and change the functor to take two arguments.

Unfortunately, the syntax for multi-argument functors is
a tad ugly:

[BB OVERWRITE]
functor ListFn (structure Eq : EQ
                structure Pr : PRINTABLE) :> SET
where type elem = Eq.t
= ...

Now we apply the functor thus:

  structure IntList = ListFn(structure Eq = IntEq
                           structure Pr = IntPr)

Does this work?  Nope!  SML doesn't know that
Eq.t = Pr.u, so we'll get a type mismatch when we 
try to apply Pr.toString to an element of the set.

We want the equation  elem = Eq.t = Pr.u.
The first part, elem = Eq.t, we get via "where type".
The second we get by writing a "sharing constraint":

  functor ListFn (structure Eq : EQ
                  structure Pr : PRINTABLE
                  sharing type Eq.t = Pr.u) :> SET
  where type elem = Eq.t
  = ...

Now everything works.  If we want something other than
ints, we could write appropriate structures ascribing to
EQ and PRINTABLE.

   (Code for toString is on the web.)



Recall that we can `open up' a structure:

   open IntList

This has several effects:
   + We don't have to say IntList.incl, we can just say incl
   - If we have both IntList and StringList (say), it's useless
     to open both because of shadowing 
   - It's not obvious where "incl", etc. were defined

One good compromise is to write
   structure IL = IntList
   structure SL = StringList

You still have to write IL. and SL. before incl and excl,
but it's more concise and readable.

Another compromise is to "open by hand" and
write val declarations for things you need to
refer to often:

  val incl = IntList.incl
  val excl = IntList.excl

There's an analogue of `open' that operates on
signatures instead of structures: include.
For example, we might extend the PRINTABLE signature
with a function that returns strings in Unicode:

   [Note: I hate this example.]

 signature PRINTABLE' = sig
    include PRINTABLE
    val toUnicode : u -> unicode_string    (* unicode_string def.'d elsewhere *)
 end

This is shorthand for writing

    signature PRINTABLE' = sig
      type u
      val toString : u -> string
      val toUnicode : u -> unicode_string
    end

Consequently, any structure (perhaps the result of a functor)
ascribing to PRINTABLE' can be used anywhere a structure ascribing to
PRINTABLE is needed.  You'll do something similar in hw4.


Additional reading:

  Paulson chapter 7
  Bob Harper's notes