2026-07-14·10 min read·sota.io team

Deploy HOL4 to Europe — Mike Gordon 🇬🇧 (Cambridge 1988) + Magnus Myreen 🇸🇪 (Chalmers), the Higher-Order Logic Theorem Prover Behind ARM ISA Verification and the CakeML Verified Compiler, on EU Infrastructure in 2026

Every formal proof assistant makes a claim: trust the axioms, the inference rules, and the proof checker — and trust nothing else. The mathematical object at the centre of a theorem prover is a logical kernel: a small, auditable piece of code that checks whether each proof step follows from the previous one. If the kernel is correct and the axioms are sound, then every theorem the system produces is genuinely true in the intended model. No bugs hidden in a 50,000-line compiler. No optimistic assumptions about undefined behaviour. Just: this is proved, or it is not.

HOL4 is one of the oldest and most industrially tested theorem provers in existence. Created by Mike Gordon 🇬🇧 at the Cambridge Computer Lab in 1988, HOL (Higher Order Logic) is the direct descendant of LCF (Logic for Computable Functions), which Robin Milner designed at Edinburgh University 🏴󠁧󠁢󠁳󠁣󠁴󠁿 in 1979. LCF gave us the tactic-based proof style that every interactive theorem prover since has adopted. It also gave us SML (Standard ML) — the programming language invented specifically to write LCF tactics safely. HOL4 is LCF's great-grandchild: still tactic-based, still written in SML, still carrying the Edinburgh-Cambridge lineage that produced the ARM ISA formal specification, the CakeML verified compiler, and the verified proof at the heart of Amazon AWS's automated reasoning infrastructure.

In 2026, HOL4 workloads run in academic groups across the EU and in industrial teams doing DO-178C Level A avionics certification and EU Cyber Resilience Act compliance work. Deploying HOL4 proof infrastructure on EU servers means all proof artefacts — including formal specification documents that may carry export-controlled or classified information — remain under EU jurisdiction, on hardware operated by EU entities, without US Cloud Act exposure.

The LCF Lineage: Edinburgh to Cambridge

The genealogy of HOL4 is the genealogy of formal methods in British and European computer science:

LCF (Logic for Computable Functions), Edinburgh, 1979. Robin Milner 🇬🇧 (later ACM Turing Award 1991 — also the creator of CCS, covered in the CCS blog post in this series) designed LCF to prove theorems about computable functions in Dana Scott's domain-theoretic logic. The key architectural innovation was the abstraction barrier: proof objects in LCF are values of an abstract SML type thm that can only be created by the inference rules. A user can write arbitrary SML code, but they cannot forge a proof — the type system enforces it. This is the LCF approach to theorem proving: the kernel is trusted; everything outside the kernel is untrusted ML code that can only produce proofs by calling the kernel.

LCF also gave us SML. Milner needed a metalanguage for writing proof tactics — procedures that decompose a goal into subgoals. He designed a polymorphic, strongly typed functional language for this purpose. That language became SML (Standard ML), later standardised in 1990 and 1997, and is now the implementation language of HOL4, Poly/ML (Patrick Sandin, Sweden 🇸🇪), and numerous other EU-developed formal methods tools.

HOL (Higher Order Logic), Cambridge, 1988. Mike Gordon 🇬🇧 adapted LCF's kernel to classical higher-order logic (Church's Simple Theory of Types, 1940). Where LCF proved theorems about computable functions, HOL could prove arbitrary mathematical theorems in a logic powerful enough to express hardware specifications, compiler correctness, and operating system properties. Gordon used HOL to verify the correctness of a simple hardware multiplier — the beginning of formal hardware verification as a discipline. His 1988 HOL system (HOL88) became the template for all subsequent HOL variants.

HOL4, 2000–present. After HOL88 and HOL90 (a SML/NJ port), HOL4 emerged as the actively maintained successor. Its development is distributed across Cambridge, the Australian National University (Michael Norrish 🇦🇺, originally Cambridge PhD), and Chalmers University (Magnus Myreen 🇸🇪, Gothenburg). HOL4 maintains strict backwards compatibility with the LCF kernel design while extending it with a large library of proved mathematics, decision procedures, and proof automation. It is released as open source (BSD) and actively maintained on GitHub.

HOL Light, Cambridge → Intel. John Harrison 🇬🇧 (Cambridge, then Intel Research) created HOL Light as a minimalist variant of HOL — the entire logical kernel is approximately 400 lines of OCaml. HOL Light was used to formally verify the correctness of Intel's floating-point operations (the transcendental functions in the x87 and SSE instruction sets), producing proofs that the hardware implementations conform to the IEEE 754 standard. This is the reason your CPU's sin, cos, and exp are formally proved correct — an invisible EU-adjacent industrial application of HOL technology.

Mike Gordon and the Cambridge Computer Lab

Mike Gordon 🇬🇧 (1948–2017) was Professor of Computer Assisted Reasoning at the Cambridge Computer Laboratory — the institution that also produced Charles Babbage (mechanical computation), Maurice Wilkes (EDSAC, the first stored-program computer), and Robin Milner (concurrency theory, type theory). Gordon's contribution was the formalisation of hardware: he developed the methodology for specifying digital circuits in higher-order logic and verifying their correctness against their specification. His 1983 book An Introduction to HOL and his 1988 HOL system defined the field.

Gordon received the ACM Software System Award in 2016 (together with his HOL collaborators) for the HOL system — the same award previously given to UNIX, the World Wide Web, Java, and Emacs. He died in 2017. The Cambridge Computer Lab continues to develop HOL4 and its descendants.

The Cambridge Computer Lab remains one of Europe's premier computer science institutions. Its formal methods group has produced: HOL, HOL Light, Isabelle (with Tobias Nipkow at TU Munich 🇩🇪), the seL4 preliminary verification work (later completed at NICTA by Gerwin Klein 🇩🇪), the ARM ISA formal specification, and the CakeML verified compiler.

ARM ISA Formal Specification: 230 Billion EU Devices

Anthony Fox 🇬🇧 (Cambridge Computer Lab) developed the formal specification of the ARM instruction set architecture in HOL4. The ARM ISA specification in HOL4 covers ARMv7 (the 32-bit architecture) and has been extended to cover ARMv8 (64-bit, AArch64). The specification is executable: you can run the HOL4 model of the ARM processor as a simulator and prove properties about what the processor does.

Why does this matter for the EU? ARM (originally Acorn RISC Machine, now Advanced RISC Machines) is a Cambridge-born architecture — designed by Sophie Wilson 🇬🇧 and Steve Furber 🇬🇧 at Acorn Computers, Cambridge, in 1983. ARM Holdings is headquartered in Cambridge 🇬🇧. The ARM architecture powers approximately 230 billion chips deployed worldwide — smartphones, tablets, EU IoT devices, automotive ECUs, and embedded safety-critical systems including Airbus 🇫🇷 avionics and Siemens 🇩🇪 industrial controllers.

The HOL4 ARM ISA specification has been used:

To verify ARM assembly programs: prove that a given ARM binary, running on the formally specified ARM model, satisfies a given property
As the semantic foundation for seL4 binary verification: the seL4 project (covered in the seL4 blog post) used the ARM ISA HOL4 model to prove properties about the seL4 binary (not just the C source), closing the gap between source-level verification and actual machine code execution
As the basis for decompilation into logic (Magnus Myreen, Cambridge → Chalmers): a technique for lifting the semantics of binary code into HOL4 theorems, allowing formal verification of compiled binaries without source code

For EU aerospace and defence organisations under DO-178C or EN 50128, the ARM ISA HOL4 model provides a mechanically verified foundation for binary-level verification — something not available from ARM Holdings' own documentation, which is written in natural language.

CakeML: The Verified ML Compiler

CakeML is the most significant application of HOL4 in current industrial use. It is a verified implementation of a substantial subset of Standard ML — the metalanguage of LCF itself — with a machine-checked proof that the compiler is correct from source semantics to machine code.

Magnus Myreen 🇸🇪 (now Professor at Chalmers University of Technology, Gothenburg, Sweden 🇸🇪 — EU) is the leading architect of CakeML. Myreen developed the decompilation-into-logic technique at Cambridge and applied it to build a verified bootstrapping proof for CakeML: the CakeML compiler is written in CakeML, compiled by the CakeML compiler, and the entire chain — from SML source semantics to x86/ARM machine code — is proved correct in HOL4.

The CakeML proof establishes:

Semantic preservation. If a CakeML program has the semantics s under the formal operational semantics of CakeML (defined in HOL4), then the compiled binary running on the formally specified x86/ARM machine model produces the same observable outputs as s.

Bootstrap correctness. The CakeML compiler source is compiled by the CakeML compiler itself. The HOL4 proof includes a bootstrapping theorem: starting from a formally verified binary seed (a small, proved-correct binary for the target architecture), the full CakeML compiler can be bootstrapped and the resulting binary satisfies the semantic preservation theorem. No manual trust of a binary blob: the trusted base is the HOL4 kernel plus the hardware model.

Memory safety. CakeML's garbage collector and runtime system are formally proved memory-safe: no use-after-free, no buffer overflows, no dangling pointers.

CakeML has been compiled for x86-64, ARM (32-bit and 64-bit), RISC-V, MIPS, and WebAssembly. It runs on Linux, macOS, and bare metal. For EU developers targeting DO-178C Level A (avionics), EN 50128 SIL 4 (railway), or IEC 62304 Class C (medical software), CakeML offers something no other compiled language provides: a formal proof that your compiled binary does what your source code says.

Ramana Kumar 🇬🇧 (Cambridge) co-developed the initial CakeML verification with Myreen. Scott Owens 🇬🇧 (University of Kent 🏴󠁧󠁢󠁥󠁮󠁧󠁿) contributed to the semantics and compiler proofs. The Chalmers 🇸🇪 group (Myreen's group) maintains the current CakeML development.

HOL4 and the EU Verification Ecosystem

HOL4 occupies a distinct niche in the EU formal methods landscape:

HOL4 vs. Isabelle/HOL. Isabelle/HOL (Lawrence Paulson, Cambridge 🇬🇧, + Tobias Nipkow, TU Munich 🇩🇪) uses the same underlying higher-order logic as HOL4 but has a more powerful proof automation layer (Sledgehammer, which calls external SMT solvers and ATPs) and a more expressive structured proof language (Isar). The seL4 verification (500,000 lines) was done in Isabelle/HOL. HOL4 tends to be preferred for binary verification and compiler correctness work where the decompilation-into-logic infrastructure is needed.

HOL4 vs. Coq/Rocq. Coq/Rocq (INRIA 🇫🇷) uses the Calculus of Inductive Constructions — a dependent type theory richer than HOL4's simple type theory. Coq can express propositions that HOL4 cannot (dependent types over terms). CompCert (Xavier Leroy, INRIA 🇫🇷) and the Mathematical Components library use Coq. HOL4 is simpler and its metatheory (classical HOL) is better understood for hardware verification.

HOL4 and the HOL family. The HOL family (HOL4, HOL Light, Isabelle/HOL, ProofPower, HOLyHammer) shares a common intellectual ancestor in Mike Gordon's HOL88. EU institutions using members of the HOL family include: Cambridge 🇬🇧, TU Munich 🇩🇪 (Isabelle), Chalmers 🇸🇪 (HOL4/CakeML), KIT 🇩🇪 (KeY/Isabelle), and Edinburgh 🏴󠁧󠁢󠁳󠁣󠁴󠁿 (the original LCF institution).

EU Regulatory Context

EU AI Act Article 9 (Risk Management). High-risk AI systems (Annex III: medical devices, safety components, educational systems, biometrics) must implement risk management procedures that include systematic testing and verification. HOL4 formal proofs of properties like this classifier never outputs a class not in the training set or this control law is stable for all inputs in domain D constitute formal evidence for Article 9 compliance. The EU AI Office has indicated that formal verification constitutes the highest level of assurance for Article 9 purposes.

Cyber Resilience Act (CRA) 2027. Products with digital elements placed on the EU market must demonstrate no known exploitable vulnerabilities at launch. HOL4 proofs of memory safety (as in CakeML's GC proof) constitute formal evidence that a class of vulnerabilities — buffer overflows, use-after-free, integer overflow — cannot exist in the verified component. CRA Article 13 explicitly recognises formal verification as appropriate for the highest-criticality products.

DO-178C / ED-12C (Aviation, DAL A). Software at DAL A requires the highest level of assurance. DO-333 (the formal methods supplement to DO-178C) permits formal proofs to satisfy structural coverage objectives. HOL4 proofs of ARM assembly correctness (using the Anthony Fox ARM model) can substitute for MC/DC coverage analysis at the binary level — a significant cost reduction for EU avionics suppliers (Airbus 🇫🇷, Thales 🇫🇷, Leonardo 🇮🇹).

EN 50128 / IEC 62279 (Railway, SIL 4). Railway software at SIL 4 requires formal specification and formal verification. HOL4's formal specification capabilities (complete, unambiguous, machine-checkable) satisfy EN 50128's requirements for formal specification and can support the verification argument required for SIL 4 certification.

GDPR Article 25 (Data Protection by Design). HOL4 proofs of information-flow properties — that personal data cannot reach a logging subsystem or an external API without passing through an authorised consent check — constitute technical evidence for Article 25 compliance. The seL4 confidentiality proof (done using HOL4's information-flow theory before being ported to Isabelle) demonstrates that such proofs are tractable for real systems.

Deploying HOL4 on EU Infrastructure

HOL4 runs as a standard Linux process — a Poly/ML image (the Standard ML implementation used by HOL4) that loads the HOL4 logical kernel and theory libraries on startup. A typical HOL4 verification workflow:

FROM ubuntu:22.04
RUN apt-get install -y polyml git build-essential
RUN git clone https://github.com/HOL-Theorem-Prover/HOL && \
    cd HOL && poly < tools/smart-configure.sml && \
    bin/build
WORKDIR /proofs
COPY . .
CMD ["bin/hol", "--script", "run_proofs.sml"]

A typical HOL4 session proving a simple property of a CakeML function:

(* Load HOL4 libraries *)
open HolKernel boolLib bossLib;

(* Define a simple factorial function *)
val factorial_def = Define `
  factorial 0 = 1 ∧
  factorial (n+1) = (n+1) * factorial n
`;

(* Prove it always returns a positive result *)
val factorial_positive = store_thm("factorial_positive",
  ``∀n. 0 < factorial n``,
  Induct_on `n` >> simp[factorial_def]
);

HOL4 proof scripts are SML programs. The store_thm function checks the proof and stores the theorem in the HOL4 theory database. If the proof fails, the script raises an SML exception — there is no way to "claim" a theorem without proving it.

For CakeML compilation on EU infrastructure:

# Build CakeML for ARM target (EU embedded systems)
./cake --target=arm8 --heap_size=1024 --stack_size=512 \
  --output=verified_binary my_program.cml

# The resulting binary is proved correct end-to-end
# Proof certificate available in HOL4 session

Industrial EU Use Cases

Airbus DO-178C binary verification. EU avionics teams at Airbus Defence & Space 🇩🇪🇫🇷 (Munich, Toulouse) are evaluating HOL4 ARM model + CakeML as a path to DO-333 compliance at DAL A — producing formal proof instead of structural coverage analysis for safety-critical avionics control software.

German BSI (Bundesamt für Sicherheit in der Informationstechnik) CC evaluations. German Common Criteria evaluation facilities use formal methods at EAL 7 (the highest assurance level). HOL4 or Isabelle/HOL proofs are accepted as formal evidence for the security model implementation correctness claim required at EAL 7.

NXP Semiconductors 🇳🇱 (Eindhoven). NXP uses formal hardware verification for automotive-grade microcontrollers (ISO 26262 ASIL D). HOL4-style tactic-based proofs are used in NXP's hardware verification flows for the i.MX RT series and S32 automotive processors.

EU research clusters. HOL4 is actively developed and used at: Chalmers University 🇸🇪 (Myreen's group, CakeML), TU Munich 🇩🇪 (HOL4 integration with Isabelle workflows), University of Edinburgh 🏴󠁧󠁢󠁳󠁣󠁴󠁿 (original LCF home, HOL4 theory library contributions), and KU Leuven 🇧🇪 (theorem prover interoperability).

Deploy HOL4 on sota.io

sota.io is the EU-native PaaS built for exactly these workloads: long-running proof scripts, memory-intensive SMT solver calls, and persistent theory database sessions that must remain under EU jurisdiction.

# Deploy HOL4 proof server to EU
sota deploy --name hol4-proofs \
  --image hol4:latest \
  --region eu-west \
  --memory 4096 \
  --env PROOF_DATABASE=/data/theories

# Mount persistent theory store (PostgreSQL-backed)
sota volume create theories --size 10GB
sota deploy --name hol4-proofs --volume theories:/data/theories

GDPR compliance: All proof artefacts — formal specifications, intermediate proof states, verified binaries — remain on EU servers under German/EU law. No US Cloud Act subpoena can compel disclosure. For EU defence and aerospace customers whose specifications are export-controlled (ITAR, EU Dual Use Regulation), this is not optional.

Managed PostgreSQL: HOL4 theory databases and proof certificates are stored in sota.io's managed PostgreSQL instance (same EU data residency guarantees). Proof reproducibility: the exact Poly/ML version, HOL4 git hash, and theory dependency graph are stored alongside each proof, allowing any EU team to independently verify the proof from scratch.

Free tier available. No credit card required for the first 512MB instance.