Part A – Foundations in ML

Expressions, Bindings, and Immutability

An ML program is a sequence of bindings. Each binding is checked in the static environment (types of earlier bindings) and evaluated in the dynamic environment (values of earlier bindings). The most basic binding form is

val x = e

Once bound, x is immutable; later bindings may shadow the name but never mutate the original value. There is no assignment statement.

Primitive expressions

• Integers: 42, ~7 (negation uses ~)
• Booleans: true, false
• Arithmetic: e1 + e2, e1 - e2, e1 * e2, e1 div e2, e1 mod e2
• Comparisons: e1 = e2, e1 < e2, e1 <> e2
• Conditionals: if e1 then e2 else e3 (both branches must have the same type)

Functions

fun square (n:int) = n * n

Functions are values. A call square 5 evaluates in the caller’s environment, but the body of square is evaluated in the enviroment where it was defined—lexical scoping.

Compound Data

• Tuples: (3, true, "hi") has type int * bool * string. Access via pattern matching: val (x,y,z) = t.
• Records: {name = "Ada", age = 42}. Field order is irrelevant; access by label: #name r.
• Lists: [] (empty), h::t (cons), [1,2,3] (syntactic sugar). Homogeneous: all elements share the same type.
• Options: NONE or < some value SOME v of type t option.

Pattern Matching

fun length xs =
    case xs of
        []      => 0
      | x::xs'  => 1 + length xs'

Patterns may be nested and may contain wildcards (_) or constants.

Let-expressions

let val y = x + 1
    fun helper z = z + y
in helper 5
end

Introduces local bindings whose scope is the body e.

Datatypes

datatype shape = Circle of real
               | Rectangle of real * real
               | Point

Introduces a new type shape with constructors Circle, Rectangle, and Point. Values with pattern matching:

fun area s =
    case s of
        Circle r        => Math.pi * r * r
      | Rectangle(w,h)  => w * h
      | Point           => 0.0

Polymorphism & Type Inference

ML infers the most general type:

fun id x = x           (* 'a -> 'a *)
fun map f xs = ...     (* ('a -> 'b) -> 'a list -> 'b list *)

No annotations are required unless inference is ambiguous.

Part B – Higher-Order Functions & Closures

Functions as Values

val inc = fn x => x + 1
val twice = fn f => fn x => f (f x)
val add3 = twice inc   (* fn x => x + 3 *)

Currying

fun add x y = x + y    (* int -> int -> int *)
val add5 = add 5       (* int -> int *)

Map, Filter, Fold

fun map f []      = []
  | map f (x::xs) = f x :: map f xs

fun filter pred []      = []
  | filter pred (x::xs) = if pred x then x :: filter pred xs
                          else filter pred xs

fun foldl f acc []      = acc
  | foldl f acc (x::xs) = foldl f (f(acc,x)) xs

Closures

A closure is a function paired with the environment in which it was created.

val x = 10
val addX = fn y => y + x   (* addX is a closure capturing x *)

Using Closures for Callbacks

val callbacks : (int -> unit) list ref = ref []
fun register cb = callbacks := cb :: !callbacks
fun onKey k = List.app (fn f => f k) (!callbacks)

Part C – Modules & Abstraction

Structures & Signatures

signature STACK =
sig
    type 'a stack
    val empty : 'a stack
    val push  : 'a * 'a stack -> 'a stack
    val pop   : 'a stack -> 'a * 'a stack option
end

structure ListStack :> STACK =
struct
    type 'a stack = 'a list
    val empty = []
    fun push (x,s) = x::s
    fun pop []      = NONE
      | pop (x::xs) = SOME (x,xs)
end

The signature STACK hides the representation; clients cannot see that stacks are implemented as lists.

Abstract Types

signature RATIONAL =
sig
    type t
    val make : int * int -> t
    val add  : t * t -> t
    val toString : t -> string
end

Only the operations listed in the signature are visible; the internal representation (datatype or int*int) is hidden.

Equivalence & Refactoring

Because clients cannot depend on hidden details, implementations may be refactored freely while preserving observable behavior—an essential principle for software evolution.