Model Checking Higher-Order Programs

34 concepts32 papers1 proposal

In first-order programs (like traditional C or Java), function calls follow a strict Last-In, First-Out (LIFO) order. When function A calls B, and B calls C, an execution context is pushed onto a stack. When C and B finish, they are popped off in reverse order. A standard pushdown automaton (PDA)—which is simply a finite state machine equipped with a single LIFO stack—perfectly mirrors this execution behavior, making it a foundational tool for automated program verification.

However, modern functional programming languages allow higher-order functions: functions that can accept other functions as arguments or return them as results. As noted by Naoki Kobayashi et al. in their overview of Automated techniques for higher-order program verification, traditional program analysis models break down here because they cannot accurately track the execution contexts of these higher-order calls.

When a higher-order function invokes a functional parameter, it does not just jump to a static block of code. Instead, it evaluates a closure that carries its own hidden lexical environment. The control flow can suddenly jump back to a deeply nested context that was active long ago, violating the simple LIFO assumptions of a standard stack.

To verify these programs automatically, computer scientists had to reinvent the machinery of model checking, developing new automata, game-theoretic semantics, and higher-order logics.

Tracking Lexical Context via Collapsible Pushdown Automata

To model the control flow of a higher-order program, we can abstract away its concrete data types and represent it as a Higher-Order Recursion Scheme (HORS). A HORS is essentially a grammar that generates an infinite tree representing every possible execution path of a functional program.

The breakthrough in verifying these infinite structures came from mapping them to a more powerful class of machines: Collapsible Pushdown Automata (CPDA).

To understand why a CPDA works, consider an order-2 program where a function $F$ creates a local function $G$, and then passes $G$ down through a long chain of other function calls. When $G$ is eventually invoked deep in the execution tree, it must execute within the lexical scope of $F$, meaning it needs access to $F$'s local variables. A standard stack cannot handle this because $F$'s context is buried deep beneath the functions called after it.

A CPDA solves this by using a nested stack structure (a stack of stacks) and a mechanism called a collapse pointer:

  1. Stack of Stacks: An order-2 CPDA operates on a stack of stacks. When a new context is generated, the automaton can duplicate the entire current stack structure.
  2. The Creator Pointer: When a higher-order function (like $G$) is pushed onto the stack, the CPDA attaches a pointer to that stack symbol. This pointer remembers the exact state of the stack-of-stacks at the moment $G$ was defined.
  3. The Collapse Operation: When $G$ is finally called, the CPDA does not just pop the top element. It triggers a collapse operation, which follows the attached pointer and instantly restores the stack-of-stacks to the exact historical state it was in when $G$ was created, discarding all intermediate contexts.

Christopher H. Broadbent et al. proved in On Global Model Checking Trees Generated by Higher-Order Recursion Schemes that properties expressed in the modal $\mu$-calculus over HORS-generated trees are fully decidable using these automata. By leveraging this architecture, Matthew Hague et al. provided a definitive solution to the backwards-reachability problem for higher-order systems (Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems), showing that the set of configurations that can reach a target error state is regular and computable.

Game Semantics as an Operational Bridge

While HORS and CPDA excel at analyzing pure control flow, real-world programs are rarely pure; they utilize mutable local state, pointers, and concurrency. To verify properties like observational equivalence—proving that two different implementations of a higher-order function behave identically in any possible software environment—we need a way to model external interactions.

This is achieved through Game Semantics. Instead of tracking explicit memory states, game semantics models program execution as a formal game between two players:

  • Player (P): The program fragment being verified.
  • Opponent (O): The external environment or context running the program.

When a program executes, the interaction proceeds as a dialogue of "moves" (Questions and Answers). For example, if the program calls an external function passed to it as an argument, Player poses a Question. When the external function returns a value, Opponent provides an Answer.

  Player (Program)                      Opponent (Environment)
        |                                         |
        | --- Question: Call external func ---->  |
        |                                         |
        | <--- Question: Callback from env ------ |
        |                                         |
        | --- Answer: Return from callback -----> |
        |                                         |
        | <--- Answer: Return from ext func ----- |

This dialogue generates a sequence of moves called a trace. By analyzing the language of valid traces, we can completely characterize a program's behavior without knowing the code of the environment.

The authors of Third-order Idealized Algol with iteration is decidable (Andrzej S Murawski et al.) demonstrated that for third-order imperative programs, these trace languages can be modeled using visibly pushdown automata. This insight enabled the creation of practical verification tools like HOMER (David Hopkins et al.), the first model checker capable of soundly and completely determining observational equivalence for third-order programs by compiling their game semantics into automata.

The Decidability Ceiling

Game semantics also exposes the fundamental limits of what automated tools can verify. As a program's function order increases, the complexity of the interaction space grows exponentially.

Conrad Cotton-Barratt et al. (Fragments of ML Decidable by Nested Data Class Memory Automata) and Nikos Tzevelekos et al. (Full Abstraction for Reduced ML) mapped out these boundaries precisely. They showed that while equivalence is decidable for third-order fragments, it becomes strictly undecidable at the fourth order or when recursive first-order functions are combined with unconstrained local state. At that point, the Opponent can exploit higher-order callbacks to simulate an unbounded Turing machine tape within the trace history.

Logical Unification: Higher-Order Fixpoint Logics

Rather than building separate, bespoke model checkers for reachability, termination, or safety, modern verification frameworks unify these problems by translating higher-order programs into expressive logical systems.

A premier example is Higher-Order Modal Fixpoint Logic (HFL). In traditional model checking, we evaluate a simple property against a complex model. Naoki Kobayashi et al. flipped this paradigm in Higher-Order Program Verification via HFL Model Checking. They demonstrated that a higher-order program can be encoded directly as a complex formula in HFL, while the property to be verified is treated as a simple model.

Because HFL natively supports higher-order predicates (functions that take other predicates as arguments), it can directly mirror the abstraction level of functional programs. This allows a single HFL solver to verify reachability, termination, and temporal properties uniformly, even for programs operating on infinite data domains like integers.

To bridge this with industrial automated theorem provers (SMT solvers), C.-H. Luke Ong et al. introduced HoCHC (HoCHC: a Refutationally-complete and Semantically-invariant System of Higher-order Logic Modulo Theories), which extends standard Constrained Horn Clauses to higher-order logic. This provides a clean mathematical language that allows automated tools to reason about unknown higher-order functions without losing the well-behaved properties of first-order logic.

The Alternative: Defunctionalization

Instead of lifting the verification logic to match the higher-order program, can we lower the program to match existing first-order verifiers?

This is the strategy behind the HMC (Hindley-Milner-Cousots) algorithm proposed by Rupak Majumdar et al. (HMC: Verifying Functional Programs Using Abstract Interpreters). HMC automatically defunctionalizes higher-order programs, translating closures and functional parameters into first-order imperative structures. This allows developers to immediately leverage highly optimized, off-the-shelf abstract interpreters and numeric SMT solvers to verify complex safety properties (like array bounds) in functional languages without requiring manual annotations.

Key Foundational Work

Third-order Idealized Algol with iteration is decidable (2008) — contributed 2 concept elements to this direction.
Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems (2008) — contributed 1 concept elements to this direction.
Semantics of Separation-Logic Typing and Higher-order Frame Rules for Algol-like Languages (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_higher_order_program_verification_532932e4,
  title = {higher-order program verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/higher-order-program-verification/rdr_532932e4b05d4c6b9c7fee1f5f4bf45e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_higher_order_program_verification_532932e4_v1,
  title = {higher-order program verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/higher-order-program-verification/rdr_532932e4b05d4c6b9c7fee1f5f4bf45e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake