> For the complete documentation index, see [llms.txt](https://notes.dizy.cc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://notes.dizy.cc/programming-languages/sml-nj.md).

# SML/NJ

Lecture slide: [click here](https://www.kdocs.cn/p/107488041032)

Pattern matching, type inference, data types, pattern matching, continuations.\
Readings: Ullman, ch 1-4, 5 (optional)

[Syntax in SML](http://rigaux.org/language-study/syntax-across-languages-per-language/SML.html): SML syntax fast loop-up book\
[SML Help](https://smlhelp.github.io/book/index.html): 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)

```smlnj
(* Comments *)val k = 5;
List operations
```

```smlnj
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

```sml
(* 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

```sml
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

```sml
type vec = {x: real, y: real};
```

Variable declaration

```sml
val v = {x=2.3, y=4.1};
```

Field selection: `#x v`

Pattern matching in a function:

```sml
fun dist {x, y} =
  sqrt (pow (x, 2.0) + pow (y, 2.0));
```

### Tuples

Tuples are actually records:

```sml
("I", "Love", "Programming", "Languages");
```

is actually:

```sml
{1="I", 2="Love", 3="Programming", 4="Languages"}
```

Index starting from `1`.

### Datatypes

For example:

```sml
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:

```sml
fun sum (Leaf t)        = t
  | sum (Node (t1, t2)) = sum t1 + sum t2;
```

or

```sml
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)

```sml
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:

```sml
datatype 'a option = NONE | SOME of 'a;
```

A lookup function using option:

```sml
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.

```sml
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:

```sml
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:

```sml
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.

```sml
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:

```sml
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);
```