Mechanising Denotational Semantics in Agda
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Mechanising Denotational Semantics in Agda".
Jane: Here's the gist of the paper. Mechanisation of denotational semantics in Agda allows for checking wellformedness and type correctness of embedded definitions with minimal reformulation The authors focus on embedding Scott–Strachey denotational definitions into the Agda language to support their development and testing Embedding Strategy The approach minimizes effort by embedding conventional Scott–Strachey denotational definitions in Agda with almost no changes to λ-notation or domain equations The authors developed a collection of Agda modules with postulated types for commonly used domain constructors and their associated operations They illustrate this approach through mechanisations of three denotational definitions: a model of the untyped λ-calculus, Plotkin’s denotational semantics of PCF, and a semantics of a sublanguage of Scheme Domain Postulation The paper postulates Agda notation for domain constructors and associated functions to support the embedding Domains are embedded as elements of the type Domain, with a carrier type ⟨⟨ D ⟩⟩: Set, which always contains an element ⊥ called bottom They postulate basic properties of some associated operations to support proofs that denotations compute the expected values Illustrative Examples The paper presents three illustrative examples of the shallow embedding of denotational semantics in Agda: an untyped λ-calculus, Plotkin’s denotational semantics of PCF, and a sublanguage Scm of Scheme The λ-calculus example was particularly simple to mechanise due to the ease of postulating recursive domains as bijections The PCF example demonstrated how dependent types formalize Plotkin’s verbal explanation of the syntax of an intrinsically typed language Mechanising Domain Theory The authors explore the possibility of mechanising synthetic domain theory (SDT) in Agda, suggesting that it might be consistent with an interpretation in a higher-order intuititionistic logic They consider axiomatising the relevant part of domain theory rather than developing it fully as a mathematical theory The mechanisation supports checking wellformedness and can be used to test whether denotations compute expected values The paper concludes that the approach eliminates drawbacks from previous versions, such as the lack of Agda support for conventional concise definition of abstract syntax by context-free grammars Future work may involve mechanising Simpson’s setup of constructive set theory with a few axioms in a prover like Agda The paper also notes that the lack of Agda support for conventional concise definition of abstract syntax by context-free grammars is an awkwardness The authors chose a shallow embedding to minimize effort, accepting disadvantages compared to a deep embedding The paper concludes that the mechanisation of the PCF semantics has not previously been published.
Tom: Illustrative Tests The paper includes illustrative tests that show automatic proof by the Agda type-checker that denotations compute expected values These tests depend on the imported rewrite rules for postulated properties The success of these tests indirectly checks that the rewrite rules preserve denotations.
Jane: The authors leave development of significant tests for the Scm language to future work.
Title and authors: Tom: So, this paper is called "Mechanising Denotational Semantics in Agda", and it’s basically about taking these very old mathematical definitions—the denotational semantics for programming languages—and putting them into the Agda language. Jane That sounds really abstract, Tom. Can you explain what that means for someone who isn't deep into formal language theory?
Tom: Well, it means they’re using Agda, which is this very powerful proof assistant, to automatically check if the definitions of how programs work are actually sound and well-formed. Jane So instead of a human having to manually check every step in these complex mathematical descriptions, the computer does that verification for them?
Lu: Exactly. The core idea here is using Agda’s type-checker as an automated quality control system for these semantic definitions eighteen <ref:2610.14898#pg2>. It tackles the problem that manual checking large formal definitions is really error-prone.
Meng: I guess from my side, it means if we define how a piece of code should behave mathematically, Agda will flag if we’ve made a mistake in the structure or the types before anyone tries to actually build anything on top of it.
Lalam: It suggests that these definitions can be embedded with almost no changes to the original notation, which is huge because it means you don't have to completely rewrite your existing mathematical models just to make them checkable in Agda eighteen <ref:2610.14898#pg2>.
The paper's summary: Tom: The paper summarizes their approach by focusing on embedding conventional Scott–Strachey denotational definitions into Agda with almost no changes to the notation itself. Jane So, they aren't trying to reinvent the wheel for how these languages are described; they’re just finding a way to make existing descriptions work inside Agda.
Lu: They developed a collection of Agda modules that postuate types for common domain constructors and their associated operations eighteen <ref:2610.14898#pg2>. This is key because it sets up the mathematical environment so that the definitions have something concrete to check against.
Meng: So, they are basically building a specialized library inside Agda for these domain concepts, like functions or tuples, so when someone writes a denotation, Agda knows what those things mean mathematically.
Lalam: And they show this off through three examples: the untyped lambda calculus, Plotkin’s denotational semantics of PCF, and even a sublanguage of Scheme eighteen <ref:2610.14898#pg2>. That shows it can handle different kinds of language structures.
Tom: The point is that if Agda rejects the embedding, the error location in Agda usually points back to where the mistake was made in the original mathematical definition, which makes debugging much clearer.
Jane: It’s a practical tool for developers who are trying to formally verify code or semantic models; it moves verification from a manual, tedious process into an automated check.
The paper's improvements: Tom: They suggest that the main improvement is minimizing the effort required for embedding by sticking almost verbatim to the original notation, with only minor lexical changes eighteen <ref:2610.14898#pg2,with only minor lexical changes>. Jane That’s smart, because if you have to rewrite everything, you introduce new mistakes.
Lu: They also explore mechanising synthetic domain theory, which is this area of mathematics that deals with how these recursive structures behave in a more intuitive way. They suggest it might be consistent with an interpretation in higher-order intuitionistic logic eighteen <ref:2610.14898#pg2>.
Meng: Mechanizing synthetic domain theory sounds ambitious. If they can automate checking the recursive parts of domains without hitting non-termination issues during type checking, that would save a ton of time when we're dealing with complex AI models that have recursive structures.
Lalam: The paper also looks at how to mechanize synthetic domain theory by axiomatising only the relevant part rather than developing the whole theory, which is a much more manageable scope eighteen <ref:2610.14898#pg2>.
Tom: So the improvement isn't just checking wellformedness; it’s providing a path to automate the verification of recursive structures in these definitions.
Jane: It’s about making sure that when we move from an informal mathematical idea to a formal Agda definition, the translation process is as faithful as possible.
Conclusion: Tom: So, to wrap up on "Mechanising Denotational Semantics in Agda," the authors show that they can check wellformedness and type correctness of these embedded definitions with minimal reformulation eighteen <ref:2610.14898#pg2>. Jane It seems like a really solid way to bridge the gap between high-level mathematical theory and practical programming language semantics.
Lu: The main implication is that this approach eliminates drawbacks from previous versions, specifically the lack of Agda support for conventionally concise definitions using context-free grammars eighteen <ref:2610.14898#pg2>.
Meng: For production systems, it means we can be much more confident in the semantic layer because we have an automated check confirming things compute what they are supposed to.
Lalam: And they conclude that mechanising the PCF semantics hasn't been done before, which is a significant contribution to this specific area eighteen <ref:2610.14898#pg2>.
Tom: Yeah, so it’s about making these complex semantic checks automatic and less error-prone. That’s what this paper achieves with the work on "Mechanising Denotational Semantics in Agda". Jane It gives us a cleaner way to handle the translation process for formal semantics.
Department of Software Technology, Delft University of Technology · Faculty of Science and Engineering, Swansea University · School of Engineering and Informatics, University of Sussex
cs.PL
Submitted: 2026-10-10
Updated: 2026-11-02
Comments: 23 pages, excl. references. To be published in Proceedings of MFPS 2026
Code: https://github.com/agda/agda
Project page: https://achimjungbham.github.io/pub/papers/handy1.pdf
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 79/100
The gist: Mechanisation of denotational semantics in Agda allows for checking wellformedness and type correctness of embedded definitions with minimal reformulation The authors focus on embedding…
Key concepts
- Embedding Strategy
- The authors minimized effort by embedding conventional Scott–Strachey denotational definitions into Agda with minimal changes to standard notation. They created Agda modules with postulated types for common domain constructors, focusing on practical mechanization rather than deep mathematical reformulations.
- Domain Postulation
- Domains are modeled as elements of a type Domain, which always includes a bottom element (⊥). The authors postulate basic properties for associated operations. These postulates serve to allow proofs that the denotations correctly compute the expected values, ensuring soundness within the Agda framework.
- Mechanising Domain Theory
- The paper explores mechanizing synthetic domain theory (SDT) in Agda, suggesting consistency with higher-order intuitionistic logic. The focus is on axiomatizing relevant parts of domain theory rather than developing the entire mathematical theory, aiming to support recursive structures.
- Illustrative Tests
- The work includes tests that use imported rewrite rules for postulated properties. These tests automatically prove that denotations yield expected results, indirectly verifying that the rewrite rules preserve the original denotations. This confirms the mathematical soundness of the semantic transformations.
Terminology
Summary
Mechanisation of denotational semantics in Agda allows for checking wellformedness and type correctness of embedded definitions with minimal reformulation The authors focus on embedding Scott–Strachey denotational definitions into the Agda language to support their development and testing
Embedding Strategy
The approach minimizes effort by embedding conventional Scott–Strachey denotational definitions in Agda with almost no changes to λ-notation or domain equations The authors developed a collection of Agda modules with postulated types for commonly used domain constructors and their associated operations They illustrate this approach through mechanisations of three denotational definitions: a model of the untyped λ-calculus, Plotkin’s denotational semantics of PCF, and a semantics of a sublanguage of Scheme
Domain Postulation
The paper postulates Agda notation for domain constructors and associated functions to support the embedding Domains are embedded as elements of the type Domain, with a carrier type ⟨⟨ D ⟩⟩: Set, which always contains an element ⊥ called bottom They postulate basic properties of some associated operations to support proofs that denotations compute the expected values
Illustrative Examples
The paper presents three illustrative examples of the shallow embedding of denotational semantics in Agda: an untyped λ-calculus, Plotkin’s denotational semantics of PCF, and a sublanguage Scm of Scheme The λ-calculus example was particularly simple to mechanise due to the ease of postulating recursive domains as bijections The PCF example demonstrated how dependent types formalize Plotkin’s verbal explanation of the syntax of an intrinsically typed language
Mechanising Domain Theory
The authors explore the possibility of mechanising synthetic domain theory (SDT) in Agda, suggesting that it might be consistent with an interpretation in a higher-order intuititionistic logic They consider axiomatising the relevant part of domain theory rather than developing it fully as a mathematical theory
Conclusion and Future Work
The mechanisation supports checking wellformedness and can be used to test whether denotations compute expected values The paper concludes that the approach eliminates drawbacks from previous versions, such as the lack of Agda support for conventional concise definition of abstract syntax by context-free grammars Future work may involve mechanising Simpson’s setup of constructive set theory with a few axioms in a prover like Agda The paper also notes that the lack of Agda support for conventional concise definition of abstract syntax by context-free grammars is an awkwardness The authors chose a shallow embedding to minimize effort, accepting disadvantages compared to a deep embedding The paper concludes that the mechanisation of the PCF semantics has not previously been published.
Illustrative Tests
The paper includes illustrative tests that show automatic proof by the Agda type-checker that denotations compute expected values These tests depend on the imported rewrite rules for postulated properties The success of these tests indirectly checks that the rewrite rules preserve denotations. The authors leave development of significant tests for the Scm language to future work. p. 1 Mosses, Cockx, Reus
It has been widely adopted in theoretical studies of programming language semantics, and presented in
many textbooks. A significant drawback for potential users of denotational semantics is the current lack of an IDE to
support development and testing of denotational definitions.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Mechanize denotational semantics for programming languages by embedding them in Agda to automatically detect wellformedness and type correctness issues during development. This allows AI systems to formally verify that their generated code or semantic definitions adhere precisely to established mathematical models, minimizing errors in complex logic derivations.
-
Develop formal verification of recursive domain definitions by postulating relevant parts of synthetic domain theory (SDT) axioms in Agda rather than fully developing the underlying mathematics. This capability enables AI systems to handle recursive structures inherent in advanced computation without encountering non-termination issues during type checking, ensuring the soundness of their semantic interpretations.
-
Formalize and check the semantics of intrinsically typed programming languages like PCF by exploiting Agda's support for dependent types to represent language syntax directly. This allows AI systems to rigorously translate and verify the meaning of complex, context-sensitive code structures based on formal definitions rather than relying on informal descriptions.
-
Implement automated testing for semantic functions using postulated properties as rewrite rules in Agda to automatically prove that denotations compute expected values. This capability ensures that the AI's generated semantic transformations are mathematically sound and match the formal specifications of the language semantics, confirmed by proofs like refl.
Abstract
Mechanisation of a mathematical definition (also referred to as formalisation) has many benefits. Here, we focus on mechanising denotational semantic definitions of programming languages by embedding them in the Agda language. The Agda type-checker detects and reports any issues with the wellformedness and type correctness of the embedded definitions. To minimise the effort required, and to facilitate correlation of the original definition with its Agda embedding, mechanisation should not involve significant reformulation or extension. Here, we show how to embed conventional Scott-Strachey denotational definitions in Agda with almost no changes to λ-notation or domain equations. Agda notation for definitions of types and functions corresponds closely to the conventional meta-notation of denotational semantics. We have developed a collection of Agda modules with postulated types for commonly used domain constructors and their associated operations. We illustrate our approach with mechanisations of three denotational definitions: a model of the untyped λ-calculus, Plotkin's denotational semantics of PCF, and a semantics of a sublanguage of Scheme. In previous work, similar mechanisations in Agda have revealed several unsuspected wellformedness issues in published denotational definitions. Some of the postulated properties of our definitions are inconsistent with a classical set-theoretic interpretation of Agda. We conjecture that they would be consistent with an interpretation of Agda in a higher-order intuititionistic logic, such as that used by Simpson in his work on synthetic domain theory. After recalling previous work on mechanising domain theory, we consider the possibility of mechanising synthetic domain theory in Agda.
Sources
- Guarded Dependent Type Theory with Coinductive Types
- Greatest HITs: Higher inductive types in coinductive definitions via induction under clocks
Related papers
- Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA
- Fuss-free cumulative universes: theory and practice
- High-Level Synthesis of Efficient Pipelines with Visibility Control
- Model Checking Probabilistic Multiparty Session Types
- A Type System for Communication-Safe Hardware Design
- RECURSUM: Automated Code Generation for Recurrence Relations Exceeds Expert Optimization via LayeredCodegen