📘
📘
📘
📘
Notes
Programming Languages
Search
⌃K

# SML/NJ

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
• 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) = ; (* error - list representation hidden *)
(* Transparent ascription *)
structure Set2 : SetSignature = Set;
Set2.aux ; (* error - component hiding *)
Set2.singleton (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);