Recursion and Sequentiality in Categories of Sheaves

Cristina Matache, Sean Moss, Sam Staton

TL;DR

Researchers at the University of Oxford have developed a new mathematical model for functional programming languages that perfectly matches program behavior (a property called "full abstraction"). By using sheaf theory, they treat recursion and sequentiality as modular components that can be combined, offering a more flexible alternative to traditional domain theory.

What Problem Does This Paper Address?

In the world of programming language theory, denotational semantics seeks to map code to mathematical objects (like sets and functions). The "Holy Grail" is a fully abstract model: one where two pieces of code are mathematically equal if and only if they behave identically in every possible program context.

Traditional models often use CPOs (Complete Partial Orders). However, CPOs have a persistent flaw: they are often "too large." They might contain mathematical functions for parallel processing that the programming language itself cannot express (a lack of sequentiality). Furthermore, recursion is usually baked into these models as a fundamental requirement rather than a modular feature.

This paper tackles the challenge of building a fully abstract model for a call-by-value version of PCF (Programming Computable Functions)—a benchmark functional language—while treating recursion and sequentiality as distinct, combinable building blocks.

Methods

The authors move away from standard set theory and into Topos Theory, specifically using categories of sheaves.

  1. Modular Sites: Instead of one giant mathematical space, they define "sites" (small categories that generate sheaves). They use a specific site ($V$) to handle recursion and a different class of sites based on Structural Systems of Partitions (SSP) to handle sequentiality.
  2. Summing Sites: The core technical innovation is a method for "summing" these different sites together. This allows them to build a model that inherits recursion from one component and sequentiality from another.
  3. Orthogonality for Recursion: They define recursion abstractly using "orthogonality." This allows them to interpret Tarski’s fixed-point theorem (the mathematical basis for recursion) in a general categorical setting without relying on specific partial orders.
  4. Truncated Definability: To bridge the gap between the countable nature of code and the uncountable nature of mathematical models, they use a technique inspired by Robin Milner: they consider "truncated" versions of the language where numbers above a certain limit cause the program to crash, then combine these limits to cover the full language.

Datasets

As this is a theoretical paper in mathematical logic and computer science, no empirical datasets were used. The "data" consists of the formal rules of the PCFv language and the axioms of category theory.

Key Insights and Ideas

  • Recursion as a Plugin: The paper demonstrates that recursion doesn't have to be a global property of a model. By using the "vertical natural numbers" sheaf, recursion becomes a feature you can "plug in" to a category.
  • Internal vs. External Views: Sheaf categories provide two useful perspectives. Externally, they look like sets with complex logical relations (Kripke structures). Internally, they behave like a universe of "intuitionistic set theory," where every function is automatically continuous.
  • Preserving Concreteness: A major hurdle in sheaf theory is that categories of sheaves aren't always "concrete" (meaning they don't always behave like sets and functions). The authors developed a specific "sum" construction for sites that ensures the resulting model remains concrete, which is vital for proving that the model matches the language's operational logic.

Key Results

  • Theorem 5.5 (Soundness and Adequacy): The authors prove that their initial model ($vSet$) correctly reflects the execution of the language—if the model says a program terminates, it actually does.
  • Theorem 7.7 (Full Abstraction): This is the paper's crowning achievement. They prove that in their final, combined sheaf model ($\mathcal{G}$), mathematical equality is exactly equivalent to contextual equivalence in the programming language.
  • Modular Construction: They successfully demonstrated a "principled approach" to building models by combining modular components, rather than building a monolithic structure from scratch.

Limitations and Future Work

  • Non-Well-Pointed Phenomena: The authors note that while they focused on "concrete" sites for this paper, future work could use non-concrete sheaves to model more exotic programming behaviors where the "context lemma" doesn't hold.
  • Expanding the Language: The current model handles a basic functional language. The authors suggest that this sheaf-based approach could be extended to more complex features like concurrency, differentiable programming, and quantum computing.
  • Polymorphism: One known limitation of sheaf categories is their difficulty in supporting "small complete categories," which are typically needed to model advanced polymorphism (like System F). The authors acknowledge this as a boundary for the current technique.

Summary updated

Abstract

We present a fully abstract model of a call-by-value language with higher-order functions, recursion and natural numbers, as an exponential ideal in a topos. Our model is inspired by the fully abstract models of O'Hearn, Riecke and Sandholm, and Marz and Streicher. In contrast with semantics based on cpo's, we treat recursion as just one feature in a model built by combining a choice of modular components.
BibTeX
@inproceedings{matache2021recursion,
  author = {Cristina Matache and Sean Moss and Sam Staton},
  title = {{Recursion and Sequentiality in Categories of Sheaves}},
  booktitle = {Fscd},
  year = {2021},
  doi = {10.4230/lipics.fscd.2021.25},
}
Figure