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 definition(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);