Standard ML: Functional Programming Foundations

Standard ML (SML) is a statically‑typed, functional programming language that has quietly powered research, compilers, and even some production systems for decades. Its clean syntax, powerful type inference, and robust module system make it an excellent playground for mastering functional programming fundamentals. In this article we’ll unpack SML’s core ideas, walk through a couple of hands‑on examples, and explore where the language shines in the real world.

What Is Standard ML?

SML belongs to the ML family, a lineage that introduced concepts like polymorphic type inference and pattern matching. Unlike some dynamically‑typed functional languages, SML catches type errors at compile time while still letting you write concise code without explicit type annotations.

The language is defined by a formal specification, which means any compliant implementation behaves identically. This predictability is a huge advantage for teaching, research, and building reliable libraries.

Key Characteristics

• Strong, static typing with Hindley‑Milner inference.
• Immutable data structures by default, encouraging pure functions.
• Pattern matching for deconstructing values elegantly.
• First‑class functions and higher‑order capabilities.
• Module system (structures, signatures, functors) for large‑scale code organization.

Core Concepts: Types, Pattern Matching, and Functions

At the heart of SML is its type system. Types are inferred, but you can also annotate them for clarity or to guide the compiler. For instance, the identity function can be written in two ways:

fun id x = x          (* No explicit type *)
fun id (x : 'a) = x   (* Explicit polymorphic type annotation *)

Notice the use of 'a to denote a generic type variable. The compiler will infer that id works for any type.

Pattern matching lets you destructure data directly in function definitions. Consider a simple list sum:

fun sum [] = 0
  | sum (x::xs) = x + sum xs

The first clause matches an empty list, while the second extracts the head x and tail xs. This style eliminates boilerplate loops and makes intent crystal clear.

Immutable Data and Records

SML encourages immutability, but you can still model complex data using tuples and records. A record is similar to a named tuple:

type person = {name : string, age : int}
val alice = {name = "Alice", age = 30}
val bob = {alice with age = 31}   (* Record update, creates a new value *)

The with syntax produces a copy of alice with a modified age, preserving immutability while keeping code readable.

Higher‑Order Functions and Currying

Functions are first‑class citizens, meaning you can pass them around just like any other value. A classic higher‑order function is map, which applies a function to each element of a list:

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

val squares = map (fn n => n * n) [1,2,3,4]   (* Result: [1,4,9,16] *)

The anonymous function fn n => n * n is passed directly to map. Because SML functions are curried by default, you can partially apply them:

fun add x y = x + y
val add5 = add 5          (* add5 : int -> int *)
val result = add5 10      (* result = 15 *)

Currying enables elegant composition and reuse, especially when combined with the op keyword for infix operators.

Composing Functions

While SML doesn’t ship with a built‑in composition operator, it’s trivial to define one:

fun compose f g x = f (g x)
val inc = fn n => n + 1
val double = fn n => n * 2
val incThenDouble = compose double inc
val out = incThenDouble 3   (* out = 8 *)

This pattern appears frequently in functional pipelines, making code both modular and expressive.

Modules and Functors

When your codebase grows, the module system becomes indispensable. A structure groups related values and types, while a signature defines an interface. Here’s a tiny stack implementation:

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

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

The signature declares the abstract type 'a t and the operations you can perform. The structure ListStack provides a concrete list‑based implementation while hiding the underlying representation from users.

Functors are modules that take other modules as parameters, enabling reusable, parameterized libraries. A functor that adds logging to any stack might look like this:

functor LoggingStack (S : STACK) = struct
  open S
  fun push (x, s) = (print ("Pushing " ^ Int.toString x ^ "\n"); S.push (x, s))
  fun pop s =
    case S.pop s of
        NONE => (print "Pop on empty stack\n"; NONE)
      | SOME (x, s') => (print ("Popped " ^ Int.toString x ^ "\n"); SOME (x, s'))
end

structure LoggedStack = LoggingStack(ListStack)

Now LoggedStack behaves exactly like ListStack but with side‑effects for debugging, all without touching the original implementation.

Practical Example: Expression Evaluator

Let’s build a tiny arithmetic expression evaluator to see SML’s concepts in action. First, we define an abstract syntax tree (AST):

datatype expr =
    Const of int
  | Add   of expr * expr
  | Mul   of expr * expr
  | Neg   of expr

Next, a recursive evaluator using pattern matching:

fun eval (Const n)   = n
  | eval (Add (e1,e2)) = eval e1 + eval e2
  | eval (Mul (e1,e2)) = eval e1 * eval e2
  | eval (Neg e)       = ~ (eval e)   (* Unary minus *)

Because the function is total and pure, the compiler can guarantee termination for all finite ASTs. Let’s test it:

val expr1 = Add (Const 3, Mul (Const 2, Const 5))   (* 3 + (2*5) = 13 *)
val result1 = eval expr1   (* result1 = 13 *)

val expr2 = Neg (Add (Const 4, Const 1))            (* -(4+1) = -5 *)
val result2 = eval expr2   (* result2 = ~5 *)

The evaluator is only 10 lines of code, yet it handles arbitrarily nested expressions. Adding new operators (e.g., division or exponentiation) is a matter of extending the datatype and adding a clause to eval—no boilerplate needed.

Extending with a Visitor Pattern

If you need to perform multiple passes over the AST (e.g., pretty‑printing, optimization), a higher‑order “visitor” function keeps the logic DRY:

fun foldExpr fConst fAdd fMul fNeg expr =
  case expr of
      Const n   => fConst n
    | Add (e1,e2) => fAdd (foldExpr fConst fAdd fMul fNeg e1,
                          foldExpr fConst fAdd fMul fNeg e2)
    | Mul (e1,e2) => fMul (foldExpr fConst fAdd fMul fNeg e1,
                          foldExpr fConst fAdd fMul fNeg e2)
    | Neg e       => fNeg (foldExpr fConst fAdd fMul fNeg e)

Now you can implement a printer without touching eval:

fun toString expr =
  foldExpr (fn n => Int.toString n)
           (fn (l,r) => "(" ^ l ^ " + " ^ r ^ ")")
           (fn (l,r) => "(" ^ l ^ " * " ^ r ^ ")")
           (fn e => "(-" ^ e ^ ")")
           expr

val s = toString (Add (Const 2, Neg (Const 3)))   (* "(2 + (-3))" *)

Real‑World Use Cases

Compilers and language tools. Many academic compilers (e.g., the original MLton, the SML/NJ compiler itself) are written in SML because its pattern matching and strong type system make syntax tree transformations concise and safe.

Formal verification. The HOL (Higher‑Order Logic) theorem prover is built on SML, leveraging its ability to encode logical inference rules as pure functions.

Financial modeling. Some quantitative finance teams use SML for prototyping pricing algorithms. The language’s immutable data structures help avoid subtle bugs in concurrent calculations.

Embedded systems. SML’s small runtime and ability to generate efficient native code (via SML/NJ or MLton) make it suitable for low‑resource devices where predictability is paramount.

Pro Tips

Tip 1: Use the REPL (SML/NJ or MLton’s interactive mode) to experiment with type inference. Type errors are often more informative than you expect.

Tip 2: When defining large modules, keep signatures minimal. Expose only the operations you truly need; this encourages encapsulation and makes refactoring painless.

Tip 3: Embrace pattern matching over explicit if statements. Not only does it reduce boilerplate, it also forces you to consider all data constructors, eliminating hidden bugs.

Conclusion

Standard ML packs a powerful functional core, a sophisticated module system, and a type inference engine that together form a solid foundation for any programmer eager to master functional concepts. By exploring its immutable data structures, pattern matching, higher‑order functions, and modular design, you gain tools that translate directly to modern languages like OCaml, F#, and even functional features in JavaScript or Python.

Whether you’re building a compiler, a theorem prover, or a simple expression evaluator, SML’s clarity and rigor will help you write code that is both expressive and provably correct. Dive into the REPL, experiment with the examples above, and let Standard ML become the cornerstone of your functional programming journey.