Mechanising Denotational Semantics in Agda
summary
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…
In short
The authors embed Scott–Strachey denotational semantics into Agda to automatically check wellformedness and type correctness of embedded definitions. They postulate Agda notation for domain constructors and operations, allowing the system to verify that semantic definitions compute expected values through automated proof checking.
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 used across episodes
This episode discusses
- Mechanising Denotational Semantics in Agda · Paper Radio
- Guarded Dependent Type Theory with Coinductive Types
- Greatest HITs: Higher inductive types in coinductive definitions via induction under clocks
The paper
Mechanising Denotational Semantics in Agda · Read on arXiv
Department of Software Technology, Delft University of Technology · Faculty of Science and Engineering, Swansea University · School of Engineering and Informatics, University of Sussex
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.
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.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game