4 Search Results for "Johnstone, Adrian"

Document
DOI: 10.4230/LIPIcs.STACS.2026.65
Demystifying Codensity Monads via Duality

Authors: Fabian Lenke, Nico Wittrock, Stefan Milius, and Henning Urbat

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Codensity monads provide a universal method to generate complex monads from simple functors. Recently, a wide range of important monads in logic, denotational semantics, and probabilistic computation, such as several incarnations of the ultrafilter monad, the Vietoris monad, and the Giry monad, have been presented as codensity monads, using complex arguments. We propose a unifying categorical approach to codensity presentations of monads, based on the idea of relating the presenting functor to a dense functor via a suitable duality between categories. We prove a general presentation result applying to every such situation and demonstrate that most codensity presentations known in the literature emerge from this strikingly simple duality-based setup, drastically alleviating the complexity of their proofs and in many cases completely reducing them to standard duality results. Additionally, we derive a number of novel codensity presentations using our framework, including the first non-trivial codensity presentations for the filter monads on sets and topological spaces, the lower Vietoris monad on topological spaces, and the expectation monad on sets.
Cite as

Fabian Lenke, Nico Wittrock, Stefan Milius, and Henning Urbat. Demystifying Codensity Monads via Duality. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lenke_et_al:LIPIcs.STACS.2026.65,
  author =	{Lenke, Fabian and Wittrock, Nico and Milius, Stefan and Urbat, Henning},
  title =	{{Demystifying Codensity Monads via Duality}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{65:1--65:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.65},
  URN =		{urn:nbn:de:0030-drops-255549},
  doi =		{10.4230/LIPIcs.STACS.2026.65},
  annote =	{Keywords: Codensity, Monad, Duality}
}
Document
DOI: 10.4230/OASIcs.SLATE.2025.11
Bridging Language Barriers: A Comparative Review and Empirical Evaluation of Source-To-Source Transpilers

Authors: André Freitas, Tiago Baptista, and Pedro Rangel Henriques

Published in: OASIcs, Volume 135, 14th Symposium on Languages, Applications and Technologies (SLATE 2025)

Abstract
Source-to-source transpilation plays a pivotal role in modern software engineering by enabling code migration, feature adoption, and cross-language interoperability without sacrificing semantic integrity. The contributions discussed in this paper can be split into two. The first is a comprehensive literature review that aims at defining what transpilers are, traces their historical evolution from early Fortran/COBOL preprocessors to more recent tools like Babel and TypeScript, and examines key parsing methodologies, AST representations, and transformation strategies. The second is an experimental investigation which assesses several popular transpilers - selected by GitHub popularity and unique language-pair capabilities, when applied to an equivalent code snippet designed to sum even numbers and identify the maximum element. The metrics evaluated were the execution time, CPU, memory consumption, output accuracy and usability.
Cite as

André Freitas, Tiago Baptista, and Pedro Rangel Henriques. Bridging Language Barriers: A Comparative Review and Empirical Evaluation of Source-To-Source Transpilers. In 14th Symposium on Languages, Applications and Technologies (SLATE 2025). Open Access Series in Informatics (OASIcs), Volume 135, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{freitas_et_al:OASIcs.SLATE.2025.11,
  author =	{Freitas, Andr\'{e} and Baptista, Tiago and Henriques, Pedro Rangel},
  title =	{{Bridging Language Barriers: A Comparative Review and Empirical Evaluation of Source-To-Source Transpilers}},
  booktitle =	{14th Symposium on Languages, Applications and Technologies (SLATE 2025)},
  pages =	{11:1--11:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-387-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{135},
  editor =	{Baptista, Jorge and Barateiro, Jos\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2025.11},
  URN =		{urn:nbn:de:0030-drops-236911},
  doi =		{10.4230/OASIcs.SLATE.2025.11},
  annote =	{Keywords: Source-to-source translation, Code transformation, Parsing, Lexical analysis, Syntax analysis, Semantic analysis, Transpilation}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.23
Analysing the SML97 Definition: Lexicalisation

Authors: Elizabeth Scott and Adrian Johnstone

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
The specification of the syntax and semantics for Standard ML have been designed to support the generation of a compiler front end, but actual implementations have required significant modification to the specification. Since the specification was written there have been major advances in the development of language analysis systems that can handle general syntax specifications. We are revisiting the SML specification to consider to what extent, using modern tooling, it can be implemented exactly as originally written. In this short paper we focus on the lexical specification.
Cite as

Elizabeth Scott and Adrian Johnstone. Analysing the SML97 Definition: Lexicalisation. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 23:1-23:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{scott_et_al:OASIcs.EVCS.2023.23,
  author =	{Scott, Elizabeth and Johnstone, Adrian},
  title =	{{Analysing the SML97 Definition: Lexicalisation}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{23:1--23:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.23},
  URN =		{urn:nbn:de:0030-drops-177936},
  doi =		{10.4230/OASIcs.EVCS.2023.23},
  annote =	{Keywords: SML, language specification, lexicalisation, parsing, ambiguity}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.31
Comparing Bottom-Up with Top-Down Parsing Architectures for the Syntax Definition Formalism from a Disambiguation Standpoint

Authors: Jurgen J. Vinju

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
Context-free general parsing and disambiguation algorithms are threaded throughout the research and engineering career of Eelco Visser. Both our Ph.D. theses featured the study of "disambiguation." Disambiguation is the declarative definition of choices among different parse trees, derived using the same context-free grammar, for the same input sentence. This essay highlights the differences between syntactic disambiguation for context-free general parsing in a top-down architecture and a bottom-up architecture. The differences between top-down and bottom-up are mainly observed as practical aspects of the software architecture and software implementation. Eventually, the concept of data-dependent context-free grammar brings all engineering perspectives of disambiguation back into a conceptual (declarative) framework independent of the parsing architecture. The novelty in this essay is the juxtaposition of three general parsing architectures from a disambiguation point of view: SGLR, SGLL, and DDGLL. It also motivates design decisions in the parsing architectures for SDF{1,2} and Rascal with previously unpublished detail. The essay falls short of a literature review and a tool evaluation since it does not investigate the disambiguation methods of the many other parser generator tools that exist. The fact that only the implementation algorithms are different between the compared parsing architectures, while the syntax definition formalisms have practically the same formal semantics for historical reasons, nicely "isolates the variable" of interest. We hope this essay lives up to the enormous enthusiasm, curiosity, and drive for perfection in syntax definition and parsing that Eelco always radiated. We dearly miss him.
Cite as

Jurgen J. Vinju. Comparing Bottom-Up with Top-Down Parsing Architectures for the Syntax Definition Formalism from a Disambiguation Standpoint. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vinju:OASIcs.EVCS.2023.31,
  author =	{Vinju, Jurgen J.},
  title =	{{Comparing Bottom-Up with Top-Down Parsing Architectures for the Syntax Definition Formalism from a Disambiguation Standpoint}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{31:1--31:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.31},
  URN =		{urn:nbn:de:0030-drops-178018},
  doi =		{10.4230/OASIcs.EVCS.2023.31},
  annote =	{Keywords: parser generation, context-free grammars, GLR, GLL, algorithms, disambiguation}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 2 2023

  • Refine by Author
  • 1 Baptista, Tiago
  • 1 Freitas, André
  • 1 Henriques, Pedro Rangel
  • 1 Johnstone, Adrian
  • 1 Lenke, Fabian
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 3 OASIcs

  • Refine by Classification
  • 2 Software and its engineering → Syntax
  • 1 General and reference → Empirical studies
  • 1 General and reference → Surveys and overviews
  • 1 Software and its engineering → Interpreters
  • 1 Software and its engineering → Parsers
  • Show More...

  • Refine by Keyword
  • 1 Code transformation
  • 1 Codensity
  • 1 Duality
  • 1 GLL
  • 1 GLR
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact