Deploy Hope to Europe — Rod Burstall 🏴󠁧󠁢󠁳󠁣󠁴󠁷 (University of Edinburgh), the Language That Invented Algebraic Data Types on EU Infrastructure in 2026

Every time a Rust programmer writes match, every time a Haskell programmer pattern-matches on a constructor, every time a Scala programmer uses a case class, every time an OCaml programmer destructures a variant, they are using an idea that was first implemented in a programming language designed in Edinburgh in 1980. That language was Hope.

Hope was not widely deployed. It was not a production language. It did not ship in a commercial product or achieve mainstream adoption. What it did was invent two things that have since become fundamental to the entire landscape of modern typed programming: algebraic data types and exhaustive pattern matching on type constructors. These two ideas, first realised together in Hope, are now present in virtually every language that takes type safety seriously — from Haskell to OCaml, from F# to Rust, from Scala to Kotlin, from Swift to Elm. The language is a footnote. The ideas are everywhere.

Hope was created at the University of Edinburgh by Rod Burstall 🏴󠁧󠁢󠁳󠁣󠁴󠁷, Dave MacQueen, and Don Sannella 🏴󠁧󠁢󠁳󠁣󠁴󠁷, working in the Laboratory for Foundations of Computer Science (LFCS). The language was described in a 1980 paper presented at the ACM LISP and Functional Programming (LFP) conference: "HOPE: An Experimental Applicative Language." Experimental was the right word. The designers were not trying to create a production system. They were working out what a language that took types seriously — types as a tool for expressing the structure of data and ensuring programs were correct — might actually look like. The answer they found has shaped programming language design for forty years.

Edinburgh and the Laboratory for Foundations of Computer Science

The University of Edinburgh was, in the 1970s and 1980s, one of the two or three most important centres of programming language research in the world. The other was Cambridge, where Robin Milner 🏴󠁧󠁢󠁳󠁣󠁴󠁷 had developed ML and the first type inference algorithm (and where Milner himself had spent time before moving back to Edinburgh). Edinburgh and Cambridge — separated by four hundred miles of Scottish and English road — constituted the axis of British programming language theory, and through ML, Haskell, and the entire tradition of statically typed functional programming, the axis of much of modern programming language design worldwide.

The LFCS at Edinburgh brought together theorists and implementors with a shared commitment to understanding computation formally — through types, through proof, through the mathematics of programs. Rod Burstall arrived at Edinburgh in the 1960s after completing his PhD at Birmingham, and spent his career at LFCS building some of the most important tools in the field: the interactive theorem prover Edinburgh LCF (Logic for Computable Functions, co-designed with Robin Milner), the specification language Clear, and — in 1980, with MacQueen and Sannella — Hope.

Rod Burstall 🏴󠁧󠁢󠁳󠁣󠁴󠁷 was born in Aberdeen, Scotland, and educated at the University of Birmingham. He is a Fellow of the Royal Society (FRS) and a Fellow of the Royal Society of Edinburgh (FRSE), recognitions that place him among the most significant scientists Britain has produced. His contributions span programming language semantics, type theory, program transformation, and the foundations of functional programming. He was the intellectual force behind Hope's design — the person who saw most clearly what it meant for a language to have a type system powerful enough to express the structure of data, and a pattern-matching mechanism that enforced complete analysis of that structure.

Don Sannella 🏴󠁧󠁢󠁳󠁣󠁴󠁷 (born Glasgow) spent his career at Edinburgh LFCS, working on algebraic specification languages and formal software development. His work on the specification language Extended ML and on algebraic specifications — rigorous mathematical descriptions of what programs should do — built directly on Hope's type system and influenced how EU software engineering standards think about formal correctness.

Dave MacQueen brought the practical implementation perspective that turned Burstall's theoretical insights into a working interpreter. MacQueen later moved to Bell Labs (Murray Hill, New Jersey) where he became a central figure in the design of Standard ML — the international standard for the ML family of languages, which Hope had directly inspired.

What Hope Invented: Algebraic Data Types

Before Hope, the concept of a user-defined type in most programming languages meant a record — a product type. You could define a Point as a record with two integer fields, or an Employee as a record with a name and salary. What you could not do, in any mainstream language of the late 1970s, was define a type that had multiple, mutually exclusive representations — what logicians call a sum type or disjoint union, and what Hope called an algebraic data type.

In Hope, you could write:

data Nat == zero ++ succ(Nat);

data Tree(alpha) == leaf ++ node(Tree(alpha), alpha, Tree(alpha));

The first definition says: a Nat is either zero (a constant) or succ applied to another Nat. These are the Peano natural numbers — the inductive definition of the natural numbers that mathematicians use. The type captures the structure of the data exactly: there are exactly two ways to be a Nat, and they are mutually exclusive.

The second definition says: a Tree of values of type alpha is either a leaf (an empty tree) or a node with a left subtree, a value, and a right subtree. The (alpha) makes this a polymorphic type — a Tree(num) is a tree of numbers, a Tree(string) is a tree of strings, but the structure is the same.

This was new. No language before Hope had combined user-defined sum types, product types, recursive types, and polymorphic types in this way. The combination created something qualitatively different from what had existed before: a type system expressive enough to model the structure of data precisely, without requiring the programmer to reach for C's untagged unions or dynamically typed languages' unstructured flexibility.

Modern equivalents:

Rust:

enum Nat {
    Zero,
    Succ(Box<Nat>),
}

enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

Haskell:

data Nat = Zero | Succ Nat

data Tree a = Leaf | Node (Tree a) a (Tree a)

OCaml:

type nat = Zero | Succ of nat

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

The syntax differs. The semantics — algebraic data types with sum types, product types, recursive types, and parametric polymorphism — is Hope's, unchanged.

What Hope Invented: Pattern Matching

Algebraic data types are half the invention. The other half is pattern matching on type constructors — the ability to define a function by specifying its behaviour for each possible constructor of the input type, with the compiler verifying that all cases are handled.

In Hope:

dec length : list(alpha) -> num;
--- length(nil)      <= 0;
--- length(x::rest)  <= 1 + length(rest);

This defines length for lists. nil is the empty-list constructor. x::rest is the cons-cell constructor — a list whose head is x and whose tail is rest. The definition says: the length of an empty list is 0; the length of a non-empty list is 1 plus the length of the rest. The two cases are exhaustive: every list is either nil or a cons, and both cases are handled.

dec depth : Tree(alpha) -> num;
--- depth(leaf)          <= 0;
--- depth(node(l, x, r)) <= 1 + max(depth(l), depth(r));

Here depth is defined for trees. leaf is the base case; node(l, x, r) destructures the node into its left subtree, value, and right subtree. The compiler knows the definition of Tree — it knows there are exactly two constructors — and it can verify that both are handled.

This was the crucial innovation. Prior functional languages (LISP, ISWIM) had cond expressions and structural recursion, but the connection between the type's constructors and the function's cases was informal — the programmer could forget a case and the compiler would not notice. Hope made the connection formal: define a type's constructors and you have defined the complete set of patterns that functions on that type must handle.

The practical consequence is exhaustiveness checking: if you add a new constructor to an algebraic data type in a language with pattern matching, the compiler will find every function in your codebase that needs to be updated. This is one of the most valuable features of modern statically typed functional languages, and it originates entirely in Hope.

Modern equivalents:

Rust:

fn depth<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node(l, _, r) => 1 + depth(l).max(depth(r)),
    }
}

OCaml:

let rec depth = function
  | Leaf -> 0
  | Node (l, _, r) -> 1 + max (depth l) (depth r)

Haskell:

depth :: Tree a -> Int
depth Leaf = 0
depth (Node l _ r) = 1 + max (depth l) (depth r)

The pattern syntax differs. The semantics — exhaustive matching on algebraic data type constructors, with compiler verification — is Hope's.

The Lineage: From Hope to Every Modern Typed Language

The direct path from Hope to modern programming languages runs through three institutions, all in the British Isles and France.

Edinburgh → ML → Standard ML: Robin Milner 🏴󠁧󠁢󠁳󠁣󠁴󠁷 created ML at Edinburgh in 1973 — originally as the meta-language for the Edinburgh LCF theorem prover (which Burstall co-designed with Milner). ML had type inference from the beginning, and Milner's Hindley-Milner type inference algorithm (1978) became the standard approach to type inference in functional languages. When Burstall, MacQueen, and Sannella added algebraic data types and pattern matching to produce Hope in 1980, they completed the picture: ML acquired proper algebraic types, and the result was Standard ML (SML), designed by a committee including MacQueen, Milner, and Harper starting in 1983 and standardised in 1990.

Edinburgh/Cambridge → Haskell: The Haskell language was designed at the FPCA 1987 conference (Functional Programming and Computer Architecture) in Portland, Oregon. The committee was formed specifically because Miranda (David Turner 🇬🇧, University of Kent Canterbury — see our Miranda post) was proprietary and the research community needed an open standard. Many of Haskell's designers were at Edinburgh or Glasgow: Philip Wadler 🇬🇧 (at Glasgow, later Edinburgh, later Carnegie Mellon) contributed monads and the Hindley-Milner extension to type classes; Simon Peyton Jones 🇬🇧 (at Glasgow, later Microsoft Research Cambridge) led the GHC implementation. Haskell's algebraic types and pattern matching are Hope's, extended and standardised.

Edinburgh → OCaml → INRIA 🇫🇷: The Caml language family was developed at INRIA (Institut National de Recherche en Informatique et en Automatique) in France, starting from SML. Gérard Huet 🇫🇷 (INRIA Rocquencourt, see our Rocq/Coq post) led the early Caml work. Xavier Leroy 🇫🇷 (INRIA Paris) designed OCaml (Objective Caml) in 1996, the production functional language that powers Jane Street's quantitative finance infrastructure (London and Paris), the Mirage OS unikernel (Cambridge), and the Hack type checker at Meta. OCaml is Hope's algebraic types and pattern matching, in production use across European financial infrastructure.

Cambridge → F#: Don Syme 🇬🇧 designed F# at Microsoft Research Cambridge in 2002, directly influenced by OCaml. F# is now a first-class .NET language, used in financial services (including trading firms across London and Amsterdam), and ships as part of Visual Studio and the .NET SDK. Its algebraic types and pattern matching — the match expression, discriminated unions, active patterns — all trace through OCaml to SML to Hope.

Edinburgh/Glasgow → Rust: The influence is less direct but clear. The Rust type system was designed with explicit reference to ML and Haskell, and Rust's enum and match are algebraic types and pattern matching. Rust is now the dominant systems programming language for EU infrastructure software — used at Cloudflare (London), Arm (Cambridge), and as the second officially supported language in the Linux kernel.

EU Regulatory Angles

GDPR Art. 25 — Data Protection by Design and by Default: Algebraic data types enforce complete, explicit modelling of all data states. A type system that requires you to handle Some(value) and None separately — that makes it a compile-time error to treat a possibly-absent value as always-present — is a type system that prevents a class of data processing errors before they can occur. This is privacy by design in the most literal sense: the programming language makes it structurally harder to write programs that mishandle data. Hope invented this.

GDPR Art. 5(1)(d) — Data Accuracy: Pattern-matching exhaustiveness means that when data formats change — when a new type of personal data record is added, when a new state in a processing pipeline is introduced — every function that processes that data must be explicitly updated to handle the new case. The compiler refuses to proceed until all cases are addressed. In a GDPR context where incorrect processing of personal data can constitute a breach, exhaustiveness checking is a technical safeguard with direct regulatory relevance.

EU AI Act Art. 9 — Risk Management Systems: The EU AI Act requires that high-risk AI systems implement risk management processes, including measures to address known risks. Algebraic data types and pattern matching provide a formal mechanism for expressing and statically verifying that all defined risk states are handled: if a risk assessment produces a discriminated union with three levels (LOW | MEDIUM | HIGH), the type system can enforce that every downstream function handles all three explicitly. Hope's innovation is directly applicable to the formal correctness requirements of AI Act compliance.

NIS2 — Resilience of Critical Infrastructure Software: The exhaustiveness guarantee of pattern matching reduces the class of defects that can arise from incomplete case analysis — a common source of vulnerabilities in C and C++ code. Languages descended from Hope (particularly Rust and OCaml) are increasingly preferred for critical infrastructure software precisely because their type systems eliminate categories of errors at compile time. The NIS2 Directive's requirements for resilient critical infrastructure software are better met by languages whose type systems enforce correctness by construction.

Scottish-EU Heritage: Scotland was an EU member nation until Brexit (2020). The University of Edinburgh's computing department operated within the EU framework for the entirety of Hope's development and its influence on the ML and Haskell lineages. Rod Burstall 🏴󠁧󠁢󠁳󠁣󠁴󠁷 conducted his career at Edinburgh — a Scottish research institution whose computing contributions were European in their funding and in their orientation toward the European computing community. OCaml, the most direct industrial descendant of Hope, is French (INRIA 🇫🇷) and remains the backbone of EU quantitative finance infrastructure.

The Hope Interpreter on EU Infrastructure

Hope's primary implementation is the original Edinburgh interpreter, available in source form and buildable on any modern Linux system. For deployment in a container on EU infrastructure:

FROM debian:12-slim AS builder

RUN apt-get update && apt-get install -y \
    build-essential \
    git \
    && rm -rf /var/lib/apt/lists/*

# Build Hope interpreter from source
RUN git clone https://github.com/bnoordhuis/hope /hope-src
WORKDIR /hope-src
RUN make

FROM debian:12-slim
COPY --from=builder /hope-src/hope /usr/local/bin/hope

WORKDIR /app
COPY *.hope ./

CMD ["hope", "main.hope"]

A complete Hope functional program demonstrating algebraic types and pattern matching:

data list(alpha) == nil ++ alpha :: list(alpha);

dec length : list(alpha) -> num;
--- length(nil)     <= 0;
--- length(x::rest) <= 1 + length(rest);

dec map : (alpha -> beta) # list(alpha) -> list(beta);
--- map(f, nil)     <= nil;
--- map(f, x::rest) <= f(x) :: map(f, rest);

dec filter : (alpha -> truval) # list(alpha) -> list(alpha);
--- filter(p, nil)     <= nil;
--- filter(p, x::rest) <=
    if p(x) then x :: filter(p, rest)
            else filter(p, rest);

dec foldr : (alpha # beta -> beta) # beta # list(alpha) -> beta;
--- foldr(f, z, nil)     <= z;
--- foldr(f, z, x::rest) <= f(x, foldr(f, z, rest));

dec sum : list(num) -> num;
--- sum(xs) <= foldr(lambda x # acc => x + acc, 0, xs);

! sum(1::2::3::4::5::nil)    ! outputs: 15
! length(1::2::3::nil)       ! outputs: 3

The data declaration defines the list type with two constructors: nil (empty list) and :: (cons cell, an infix constructor). Every function is defined by exhaustive pattern matching on these constructors — the compiler verifies that no case is missing.

Deploy Hope on sota.io

sota.io's container-based deployment model supports any language that builds on Linux. A Hope application deployed on sota.io runs on EU infrastructure (Hetzner, Germany or Scaleway, France) with managed PostgreSQL and GDPR-compliant data processing:

sota deploy --region eu-west

The platform provisions EU infrastructure, injects managed PostgreSQL credentials as environment variables, configures TLS termination, and assigns a .sota.io subdomain. All data stays within the European Economic Area.

For a Hope service with database access, the standard approach is to use a thin C wrapper that calls libpq and exposes results to the Hope interpreter, or to use Hope for the data processing logic and a lightweight HTTP layer written in C:

FROM debian:12-slim AS builder

RUN apt-get update && apt-get install -y \
    build-essential git libpq-dev \
    && rm -rf /var/lib/apt/lists/*

RUN git clone https://github.com/bnoordhuis/hope /hope-src
WORKDIR /hope-src && RUN make

FROM debian:12-slim
RUN apt-get update && apt-get install -y libpq5 ca-certificates && rm -rf /var/lib/apt/lists/*
COPY --from=builder /hope-src/hope /usr/local/bin/hope

WORKDIR /app
COPY *.hope ./
EXPOSE 8080

CMD ["hope", "server.hope"]

The language that Rod Burstall 🏴󠁧󠁢󠁳󠁣󠁴󠁷 and his colleagues designed at Edinburgh in 1980 — that introduced algebraic data types and pattern matching to the world — never achieved the adoption of the languages it inspired. But every Rust enum, every Haskell data, every OCaml type, every F# discriminated union, every Scala sealed trait, every Kotlin sealed class, every Swift enum with associated values is Hope's invention, implemented in a new syntax, carrying forward the same mathematical clarity that Burstall, MacQueen, and Sannella worked out in the Laboratory for Foundations of Computer Science at the University of Edinburgh forty-four years ago.

sota.io is the EU-native platform-as-a-service for developers who need European infrastructure, GDPR compliance by default, and managed PostgreSQL without the operational overhead. Deploy your Hope application to EU servers in minutes at sota.io.