SML/NJ

Lecture slide: click here​
Pattern matching, type inference, data types, pattern matching, continuations.
Readings: Ullman, ch 1-4, 5 (optional)
​Syntax in SML: SML syntax fast loop-up book
SML Help: SML tutorial written by TAs at CMU.
Overview
Functional: functions as first-class values
Garbage collected
Strict evaluation (applicative order)
No coercion
Strong and static typing
parametric polymorphism
structural equivalence
all with type inference
Advanced module system
Exceptions
Miscellaneous features
datatypes (merge of enumerated literals and variant records)
pattern matching
ref type constructor (like const pointers)
(* Comments *)val k = 5;
List operations
1::[2,3];
=> val it = [1, 2, 3] : int list
​
(* whether empty or not *)
null [1, 2];
=> val it = false : bool
​
hd [1, 2, 3];
=> val it = 1 : int
​
tl [1, 2, 3];
=> val it = [2,3] : int list
​
(* concatenation of lists *)
[1, 2, 3] @ [2, 3, 4];
=> val it = [1,2,3,2,3,4] : int list
Functions
(* named *)
fun abs x = if x >= 0.0 then x else ~x;
​
(* anonymous *)
fn x => if x >= 0.0 then x else ~x;
​
(* pattern-matching style *)
fun length []      = 0
  | length (x::xs) = 1 + length xs;
​
​
(* multiple arguments *)
fun add (a, b) = a + b; (* pass a tuple *)
fun add a b = a + b; (* currying *)
Type notation α → β → δ means α → (β → δ)
let local scope
fun findroot (a, x, acc) =
  let val nextx = (a / x + x) / 2.0
  in
    if abs (x - nextx) < acc * x
    then nextx
    else findroot (a, nextx, acc)
  end
Records
Type declaration
type vec = {x: real, y: real};
Variable declaration
val v = {x=2.3, y=4.1};
Field selection: #x v
Pattern matching in a function:
fun dist {x, y} =
  sqrt (pow (x, 2.0) + pow (y, 2.0));
Tuples
Tuples are actually records:
("I", "Love", "Programming", "Languages");
is actually:
{1="I", 2="Love", 3="Programming", 4="Languages"}
Index starting from 1.
Datatypes
For example:
datatype tree = Leaf of int
              | Node of tree * tree;
tree is a type constructor.
Leaf and Node are data constructors:
Leaf : int → tree
Node : tree * tree → tree
Pattern matching for datatypes
We can define functions by pattern matching:
fun sum (Leaf t)        = t
  | sum (Node (t1, t2)) = sum t1 + sum t2;
or
fun sum x = case x of Leaf t => t
             | Node (t1, t2) => sum t1 + sum t2;
Functions accepting data constructors as arguments must provide an exhaustive deﬁnition(cover every data constructor for the datatype).
Parameterized datatypes (with type variables)
datatype 'a gentree =
    Leaf of 'a
  | Node of 'a gentree * 'a gentree;
​
val names = Node (Leaf "this", Leaf "that");
Common idiom: option
option is a built-in datatype:
datatype 'a option = NONE | SOME of 'a;
A lookup function using option:
fun lookup eq key []           = NONE
  | lookup eq key ((k,v)::kvs) =
      if eq (key, k)
      then SOME v
      else lookup eq key kvs;
Type of lookup is (α1*α2→bool) → α1 → (α2*β)list → βoption.
Signature and structures
An ML signature specifies an interface for a module.
signature STACKS =
sig
  type stack
  exception Underflow
  val empty : stack
  val push : char*stack->stack
  val pop : stack->char*stack
  val isEmpty : stack->bool
end
A structure implementing it would be:
structure Stacks : STACKS =
struct
  type stack = char list
  exception Underflow
  val empty=[]
  val push=op::
  fun pop (c::cs) = (c, cs)
    | pop []      = raise Underflow
  fun isEmpty [] = true
    | isEmpty _  = false
end
Signature ascription
Opaque ascription (:>) hides the identity of types beyond that which is conveyed in the signature. That is, additional type information provided by the structure will be considered abstract.
Transparent ascription (:) exposes the identity of types beyond that conveyed in the signature. That is, additional type information provided by the structure will augment the signature.
both prohibit the introduction of identifiers not already present in the signature. This is component hiding.
both permit types (in structures) which are broader than the signature.
Examples:
signature SetSignature =
sig
  type ’a set
  val empty : ’’a set
  val singleton : ’’a -> ’’a set
end;
​
structure Set =
struct
  type ’a set = ’a list;
  val empty = [];
  fun singleton a = [a]
  val aux = [];
end;
​
(* Opaque ascription *)
structure Set2 :> SetSignature = Set;
Set2.aux ; (* error - component hiding *)
Set2.singleton (2) = [2]; (* error - list representation hidden *)
​
(* Transparent ascription *)
structure Set2 : SetSignature = Set;
Set2.aux ; (* error - component hiding *)
Set2.singleton (2) = [2]; (* okay *)
Functor
A functor creates a structure from a structure.
signature TOTALORDER =
sig
  type element;
  val lt : element * element -> bool;
end ;
​
functor MakeBST (Lt : TOTALORDER):
sig
  type ’label btree;
  exception EmptyTree;
  val create : Lt.element btree;
  val lookup : Lt.element * Lt.element btree -> bool ;
  val insert : Lt.element * Lt.element btree -> Lt.element btree;
  val deletemin : Lt.element btree -> Lt.element * Lt.element btree;
  val delete : Lt.element * Lt.element btree -> Lt.element btree;
end =
struct
  open Lt ;
  datatype ’label btree = Empty |
        Node of ’label * ’label btree * ’label btr...
  val create = Empty;
  fun lookup (x, Empty) = ...;
  fun insert (x, Empty) = ...;
  exception EmptyTree;
  fun deletemin (Empty) = ...;
  fun delete (x , Empty) = ...;
end;
Invoke the functor:
structure String : TOTALORDER =
struct
  type element = string ;
  fun lt (x, y) =
    let
      fun lower (nil) = nil |
          lower (c::cs ) =
            (Char.toLower c)::lower(cs);
    in
      implode(lower(explode(x))) <
      implode(lower(explode(y)))
    end ;
end ;
​
structure StringBST = MakeBST (String);
Data Types
Last modified 1yr ago