EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Mechanising Denotational Semantics in Agda

Peter D. Mosses, Jesper Cockx, Bernhard Reus

Electronic Notes in Theoretical Informatics and Computer Science · 04.11.2026 · Volume 6: Proceedings of MFPS...

DOI: 10.46298/entics.19668 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Electronic Notes in Theoretical Informatics and Computer Science, online erschienen am 04.11.2026. Verfasst von Peter D. Mosses und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Mosses, P. D., Cockx, J., & Reus, B. (2026). Mechanising Denotational Semantics in Agda. Electronic Notes in Theoretical Informatics and Computer Science, Volume 6: Proceedings of MFPS.... https://doi.org/10.46298/entics.19668

Vancouver

Mosses PD, Cockx J, Reus B. Mechanising Denotational Semantics in Agda. Electronic Notes in Theoretical Informatics and Computer Science. 2026;Volume 6: Proceedings of MFPS.... doi:10.46298/entics.19668

BibTeX
@article{Mosses2026,
  author = {Mosses, Peter D. and Cockx, Jesper and Reus, Bernhard},
  title = {Mechanising Denotational Semantics in Agda},
  journal = {Electronic Notes in Theoretical Informatics and Computer Science},
  year = {2026},
  volume = {Volume 6: Proceedings of MFPS...},
  doi = {10.46298/entics.19668}
}
Kostenlos starten →