📘
📘
📘
📘
Notes
Programming Languages
Search
⌃K
Links

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);
Last modified 1yr ago