# Standard ML notes

## Basics

### Comments

```
(* SML comment *)
```

### Variable bindings and Expressions

```
val x = 34;
(* static environment: x : int *)
(* dynamic environment: x --> 34 *)
val y = x + 1;
(* Use tilde character instead of minus to reprsent negation *)
val z = ~1;
(* Integer Division *)
val w = y div x
```

Strings:

```
(* `\n`のようなエスケープシーケンスが利用できる *)
val x = "hello\n";
(* 文字列の連結には'^'を使う *)
val y = "hello " ^ "world";
```

An ML program is a sequence of bindings. Each binding gets **type-checked** and then **evaluated**.
What type a binding has depends on a static environment. How a binding is evaluated depends on a dynamic environment.
Sometimes we use just `environment`

to mean dynamic environment and use `context`

as a synonym for static environment.

- Syntaxs : How to write it.
- Semantics: How it type-checks and evaluates
- Value: an expression that has no more computation to do

### Shadowing

**Bindings are immutable** in SML. Given `val x = 8 + 9;`

we produce a dynamic environment where x maps to 17.
In this environment x will always map to 17; there is no “assignment statement” in ML for changing what x maps to.
You can have another binding later, say `val x = 19;`

, but that just creates a differnt environment
where the later binding for x **shadows** the earlier one.

### Function Bindings

```
fun pow (x:int, y:int) = (* correct only for y >= 0 *)
if y = 0
then 1
else x * pow(x, y-1);
fun cube (x : int) =
pow(x, 3);
val ans = cube(4);
(* The parentheses are not necessary if there is only one argument
val ans = cube 4; *)
```

- Syntax:
`fun x0 (x1 : t1, ..., xn : tn) = e`

- Type-checking:
`t1 * ... * tn -> t`

- The type of a function is “argument types” -> “reslut types”

- Evaluation:
- A function is a value
- The environment we extends arguments with is that “was current” when the function was defined, not the one where it is being called.

### Pairs and other Tuples

```
fun swap (pr : int*bool) =
(#2 pr, #1 pr);
fun sum_two_pairs (pr1 : int * int, pr2 : int * int) =
(#1 pr1) + (#2 pr1 ) + (#1 pr2) + (#2 pr2);
fun div_mod (x : int, y: int) =
(x div y, x mod y);
fun sort_pair(pr : int * int) =
if (#1 pr) < (#2 pr) then
pr
else
(#2 pr, #1 pr);
```

ML supportstuplesby allowing any number of parts. Pairs and tuples can be nested however you want. For example, a 3-tuple (i.e., a triple) of integers has type int*int*int. An example is (7,9,11) and you retrieve the parts with #1 e, #2 e, and #3 e where e is an expression that evaluates to a triple.

```
val a = (7, 9, 11) (* int * int * int *)
val x = (3, (4, (5,6))); (* int * (int * (int * int)) *)
val y = (#2 x, (#1 x, #2 (#2 x))); (* (int * (int * int)) * (int * (int * int)) *)
val ans = (#2 y, 4); (* (int * (int * int)) * int *)
```

### Lists

```
val x = [7,8,9];
5::x; (* 5 consed onto x *)
6::5::x;
[6]::[[1,2],[3,4];
```

To append a list t a list, use list-append operator `@`

:
Reference：# The Standard ML Basis Library

Interface:

val@:‘alist *‘alist->‘alist

```
val x = [1,2] @ [3,4,5]; (* [1,2,3,4,5] *)
```

Accessing:

```
val x = [7,8,9];
null x; (* False *)
null []; (* True *)
hd x; (* 7 *)
tl x; (* [8, 9] *)
```

### List Functions

```
fun sum_list(xs : int list) =
if null xs
then 0
else hd xs + sum_list(tl xs);
fun list_product(xs : int list) =
if null xs
then 1
else hd xs * list_product(tl xs);
fun countdown(x : int) =
if x = 0
then []
else x :: countdown(x - 1);
fun append (xs : int lisst, ys : int list) =
if null xs
then ys
else (hd xs) :: append((tl xs), ys);
fun sum_pair_list(xs : (int * int) list) =
if null xs
then 0
else #1 (hd xs) + #2 (hd xs) + sum_pair_list(tl xs);
fun firsts (xs : (int * int) list) =
if null xs
then []
else (#1 (hd xs)) :: firsts(tl xs);
fun seconds (xs : (int * int) list) =
if null xs
then []
else (#2 (hd xs)) :: seconds(tl xs);
fun sum_pair_list2 (xs : (int * int) list) =
(sum_list(firsts xs)) + (sum_list(seconds xs));
```

Functions that make and us lists are almost always recursice becasue a list has an unknown length. To write a recursive function the thought process involves two steps:

- think about the
*base case* - think about the
*recursive case*

### Let Expressions

- Syntax:
`let b1 b2 ... bn in e end`

- Each
`bi`

is any binding an`e`

is any expression

- Each

```
let val x = 1
in
(let val x = 2 in x+1 end) + (let val y = x+2 in y+1 end)
end
fun countup_from1 (x:int) =
let fun count (from:int) =
if from=x
then x::[]
else from :: count(from+1)
in
count(1)
end
```

### Options

An option value has either 0 or 1 thing: `None`

is an option value carrying nothing whereas `SOME e`

evaluates e to a value v and becomes the option carrying the one value v. The type of `NONE`

is `'a option`

and the type of `SOME e`

is `t option`

if e has type t.

We have:

`isSome`

which evaluates to false if its argument is NONE`valOf`

to get the value carried by`SOME`

(raising exception for`NONE`

)

```
fun max1( xs : int list) =
if null xs
then NONE
else
let val tl_ans = max1(tl xs)
in
if isSome tl_ans andalso valOf tl_ans > hd xs
then tl_ans
else SOME (hd xs)
end;
```

## Some More Expressions

Boolean operations:

`e1 andalso e2`

- if result of e1 is false then false else result of e2

`e1 orelse e2`

`not e1`

**※Syntax && and || don’t exist in ML and ! means something different.**

**※ andalso and orelse are just keywords. not is a pre-defined function.**

Comparisons:

`=`

`<>`

`>`

`<`

`>=`

`<=`

`=`

and`<>`

can be used with any “equality type” but not with real

## Build New Types

To Create a compound type, there are really only three essential building blocks:

**Each-of**: A compound type t describes values that contain each of values of type`t1`

`t2`

…`tn`

**One-of**: A compound type t describes values that contain a value of one of the types`t1`

`t2`

…`tn`

**Self-refenence**: A compound type t may refer to itself in its definition in order to describe recursive data structures like lists and trees.

### Records

Record types are “each-of” types where each component is a named field. The order of fields never matters.

```
val x = {bar = (1+2,true andalso true), foo = 3+4, baz = (false,9) }
#bar x (* (3, true) *)
```

Tupels are actually syntactic sugar for records. `#1 e`

, `#2 e`

, etc. mean: get the contents of the field named 1, 2, etc.

```
- val x = {1="a",2="b"};
val x = ("a","b") : string * string
- val y = {1="a", 3="b"};
val y = {1="a",3="b"} : {1:string, 3:string}
```

### Datatype bindings

```
datatype mytype = TwoInts of int*int
| Str of string
| Pizza;
val a = Str "hi"; (* Str "hi" : mytype *)
val b = Str; (* fn : string -> mytype *)
val c = Pizza; (* Pizza : mytype *)
val d = TwoInts(1+2, 3+4); (* TwoInts (3,7) : mytype *)
val e = a; (* Str "hi" : mytype *)
```

The example above adds four things to the environment:

- A new type mytype that we can now use just like any other types
- Three constructors
`TwoInts`

,`Str`

,`Pizza`

We can also create a type synonmy which is entirely interchangeable with the existing type.

```
type foo = int
(* we can write foo wherever we write int and vice-versa *)
```

## Case Expressions

To access to datatype values, we can use a case expression:

```
fun f (x : mytype) =
case x of
Pizza => 3
| Str s => 8
| TwoInts(i1, i2) => i1 + i2;
f(Str("a")); (* val it = 8 : int *)
```

We separate the branches with the `|`

character. Each branch has the form `p => e`

where p is a pattern and e is an expression. Patterns are used to match against the result of evaluating the case’s first expression. This is why evaluating a case-expression is called pattern-matching.

## Lists and Options are Datatypes too

`SOME`

and `NONE`

are actually constructors. So you can use them in a case like:

```
fun inc_or_zero intoption =
case intoption of
NONE => 0
| SOME i => i+1;
```

As for list, `[]`

and `::`

are also constructors. `::`

is a little unusual because it is an infix operator so when in patterns:

```
fun sum_list xs =
case xs of
[] => 0
| x::xs' => x + sum_list xs';
fun append(xs, ys) =
case xs of
[] => ys
| x::xs' => x :: append(xs', ys);
```

## Pattern-matching

Val-bindings are actually using pattern-matching.

```
val (x, y, z) = (1,2,3);
(*
val x = 1 : int
val y = 2 : int
val z = 3 : int
*)
```

When defining a function, we can also use pattern-matching

```
fun sum_triple (x, y, z) =
x + y + z;
```

Actually, all functions in ML takes one tripple as an argument. There is no such thing as a mutli-argument function or zero-argument function in ML.
The binding `fun () = e`

is using the unit-pattern `()`

to match against calls that pass the unit value `()`

, which is the only value fo a pre-defined datatype `unit`

.

The definition of patterns is recursive. We can use nested patterns instead of nested cae expressions.

We can use wildcard pattern `_`

in patterns.

```
fun len xs =
case xs of
[] => 0
| _::xs' => 1 + len xs';
```

### Function Patterns

In a function binding, we can use a syntactic sugar instead of using case expressions:

```
fun f p1 = e1
| f p2 = e2
...
| f pn = en
```

for example

```
fun append ([], ys) = ys
| append (x::xs', ys) = x :: append(xs', ys);
```

## Exceptions

To create new kinds of exceptions we can use exception bindings.

```
exception MyUndesirableCondition;
exception MyOtherException of int * int;
```

Use `raise`

to raise exceptions. Use `handle`

to catch exceptions.

```
fun hd xs =
case xs of
[] => raise List.Empty
| x::_ => x;
(* The type of maxlist will be int list * exn -> int *)
fun maxlist(xs, ex) =
case xs of
[] => raise ex
| x::[] => x
| x::xs' => Int.max(x, maxlist(xs', ex));
(* e1 handle ex => e2 *)
val y = maxlist([], MyUndesirableCondition)
handle MyUndesirableCondition => 42;
```

## Tail Recursion

There is a situation in a recursive call called **tail call**:

when f makes a recursive call to f, there is nothing more for the caller to do after the callee returns except return the callee’s result.

Consider a sum function:

```
fun sum1 xs =
case xs of
[] => 0
| i::xs' => i + sum1 xs'
```

When the function runs, it will keep a call-stack for each recursive call . But if we change a little bit using tail call :

```
fun sum2 xs =
let fun f (xs,acc) =
case xs of
[] => acc
| i::xs' => f(xs',i+acc)
in
f(xs,0)
end
```

we use a local helper `f`

and a accumulator `acc`

so that the return value of `f`

is just the return value of `sum2`

. As a result, there is no need to keep every call in stack, just the current `f`

is enough. And that’s ML and most of other functional programming languages do.
Another example: when reversing a list:

```
fun rev1 lst =
case lst of
[] => []
| x::xs => (rev1 xs) @ [x]
fun rev2 lst =
let fun aux(lst,acc) =
case lst of
[] => acc
| x::xs => aux(xs, x::acc)
in
aux(lst,[])
end
```

`rev1`

is `O(n^2)`

but rev2 is almost as simple as `O(n)`

.

To make sure which calls are tail calls, we can use a recursive defination of **tail position** like:

- In
`fun f(x) = e`

,`e`

is in tail position. - If an expression is not in tail position, then none of its subexpressions are
- If
`if e1 then e2 else e3`

is in tail position, then`e2`

and`e3`

are in tail position (but not`e1`

). (Case-expressions are similar.) - If
`let b1 ... bn in e end`

is in tail position, then e is in tail position (but no expressions in the bindings are). - Function-call arguments are not in tail position.

## First-class Functions

The most common use of first class functions is passing them as arguments to other functions.

```
fun n_times (f, n, x) =
if n=0
then x
else f (n_times(f, n-1,x))
```

The function `n_times`

is called higher-order funciton. Its type is:

```
fn : ('a -> 'a) * int * 'a -> 'a
```

`'a`

means they can be any type. This is called *parametric polymorphism* , or *generic types* .

Instead, consider a function that is not polymorphic:

```
(* (int -> int) * int -> int *)
fun times_until_zero (f, x) =
if x = 0
then 0
else 1 + times_until_zero(f, f x)
```

### Anonymous Functions

```
fun triple_n_times (n, x) =
n_times((fn x => 3*x), n, x)
```

Maps:

```
(* ('a -> 'b) * 'a list -> 'b list *)
fun map (f, xs) =
case xs of
[] => []
| x::xs' => (f x)::(map(f, xs'));
```

Filters:

```
(* ('a -> bool) * 'a list -> 'a list *)
fun filter (f, xs) =
case xs of
[] => []
| x::xs' => if f x
then x::(filter (f, xs'))
else filter (f, xs');
```

### Lexical scope VS dynamic scope

### Combining Functions

```
fun sqrt_of_abs i = (Math.sqrt o Real.fromInt o abs) i;
```

Use our own infix operator to define a left-to-right syntax.

```
infix |>
fun x |> f = f x;
fun sqrt_of_abs i = i |> abs |> Real.fromInt |> Math.sqrt;
```

### Currying

```
(* fun sorted(x, y z) = z >= y andalso y >= x *)
val sorted = fn x => fn y => fn z => z >= y andalso y >= x;
(* just syntactic sugar for code above *)
fun sorted_nicer x y z = z >= y andalso y >= x;
```

when calling curried the function:

```
(* ((sorted_nicer x) y) z *)
(* or just: *)
sorted_nicer x y z
```

```
```

## Type Inference

Key steps in ML:

- Determine types of bindings in order
- For each val of fun binding:
- Analyze definition for all necessary facts
- Type erro if no way for all facts to hold

- Use type variables like
`'a`

for any unconstrained type - Enforce the value restriction

One example:

```
(*
compose : T1 * T2 -> T3
f : T1
g : T2
x : T4
body being a function has type T3=T4->T5
from g being passed x, T2=T4->T6 for some T6
from f being passed the result of g, T1=T6->T7
from call to f being body of anonymous function, T7 = T5
all together, (T6->T5) * (T4->T6) -> (T4->T5)
so ('a->'b) * ('c->'a) -> ('c->'b)
*)
fun compose (f, g) = fn x => f (g x)
```

### Value restriction

A variable-binding can have a polymorphic type only if the expression is a variable or value:

```
val r = ref NONE
val _ = r := SOME "hi"
val i - 1 + valOf (!r)
```

If there is is no value-restriction, the code above will type check, which shouldn’t. With value restriction, ML will give a warning when type-checking:

```
- val r = ref NONE;
stdIn:2.5-2.17 Warning: type vars not generalized because of
value restriction are instantiated to dummy types (X1,X2,...)
val r = ref NONE : ?.X1 option ref
```

## Mutual Recursion

Mutual recursion allows `f`

to call `g`

and `g`

to call `f`

.
In ML, There is an `and`

keyword to allow that:

```
fun p1 = e1
and p2 = e2
and p3 = p3
```

## Modules

```
structure MyMathLib =
struct
fun fact x = x
val half_pi = Math.pi / 2.0
fun doubler x = x * 2
end
```

### Signatures

A signature is a type for a module.

```
signature SIGNAME =
sig types-for-bindings
end
```

Ascribing a signature to a module:

```
structure myModule :> SIGNAME =
struct bindings end;
```

Anything not in the signature cannot be used outside the module.

```
signature MATHLIB =
sig
val fact : int -> int
val half_pi : real
(* make doubler unaccessable outside the MyMathLib *)
(* val doubler : int -> int *)
end
structure MyMathLib :> MATHLIB =
struct
fun fact x = x
val half_pi = Math.pi / 2.0
fun doubler x = x * 2
end
```

### Signature matching

## Equivalence

- PL Equivalence
- Asymptotic equivalence
- System equivalence