CS223, 5/5/2010
Lecture 15

Review of Midterm
-----------------

Modules in SML
==============

1. Structures

A module is a set of declarations delineated by keywords "struct" and
"end", and given a name in a "structure declaration". ("structure"
is the SML name for a basic module).

structure A =
struct
  type t = int
  val x = 3
end;

The declarations of t and x form the "body" of this example structure,
named A in the declaration.

To access the components of the structure, we used the familiar
"dot notation":  A.t denotes the "type component" t of A, which is identical
to the type int.

   A.t == int

A.x denotes the "value component" x of A, which is the same as the
integer 3 (i.e. it is an alias for 3).

   A.x = 3

You could think of structures as a generalization of records, where
the fields can contain types as well as values (and also nested
structures, as we will see later).  The dot notation is then
consistent with the dot notation for record field selection used in many
languages (C, Pascal derivatives), though not with the #a notation used
in SML.

There is a special declaration form for "opening" a structure and 
making all its components directly visible in the current environment:

open A

   -- now t refers to A.t and x refers to A.x

val y : t = x     -- y is an int, its value is 3

The open declaration is useful, can easily be overused. For instance,
in the body of structure that uses (depends on, imports) a dozen other
structures, we might find ourselves opening all the imported
structures:

structure MyModule =
struct
  (* uses structures A,B,C,D,E,F,G,H,I,J,K,L *)
  open A B C D E F G H I J K L
  -- now refer to functions, values, types from all these modules by
  -- their simple names
  ... body definitions ...
end

The problem is that opening all these modules might introduce, say,
200 names into the environment, and it can be difficult to remember
which imported module was the source of any given name.  It may also
be the case that a given function name (say foo) is defined in more
than one of the imported structures (say B, E, K), and the one that foo
is bound to after opening all the structures is the last one in the
order opened (in this case, foo will reference K.foo). You then have
to remember to use B.foo and E.foo if you need to use the other
versions of foo.


Example: alists as an implementation of finite maps (over strings)

(* Alist - association lists over strings *)
structure Alist =
struct
  type 'a alist = (string * 'a) list

  exception Unbound

  val empty = []

  fun bind (s,v,alist) = (s,v)::alist

  fun lookup (s, nil) = raise Unbound
    | lookup (s, (s',v)::alist) = if s = s' then v else lookup(s,alist)

end;

This module defines the basic functionality for polymorphic
association lists, which gives one possible implementation of finite
maps (i.e. finite functions) from strings to some range type 'a
to be determined by how they are used.

For instance, a finite map from strings to integers can be constructed
as follows:

val arity : Alist.bind("x",0,
              Alist.bind("f", 1,
                Alist.bind("y",0,Alist.empty)));
val arity : int Alist.alist

Alist.lookup ("y", arity) : int  ==>  0


2. Signatures

SML is a typed language, and just as values have types, structures
have their own version of types

signature ALIST =
sig
  type 'a alist
  exception Unbound
  val empty : 'a alist
  val bind : string * 'a * 'a alist -> 'a alist
  val lookup : string * 'a alist -> 'a
end;

A signature has a structure analogous to a structure, but its body
contains component "specifications" rather than declarations.