Patrick Bahr
Beyond Trees: Calculating Graph-Based Compilers (Functional Pearl)
Bahr, Patrick; Hutton, Graham
Abstract
Bahr and Hutton recently developed an approach to compiler calculation that allows a wide range of compilers to be derived from specifications of their correctness. However, a limitation of the approach is that it results in compilers that produce tree-structured code. By contrast, realistic compilers produce code that is essentially graph-structured, where the edges in the graph represent jumps that transfer the flow of control to other locations in the code. In this article, we show how their approach can naturally be adapted to calculate compilers that produce graph-structured code, without changing the underlying calculational methodology, by using a higher-order abstract syntax representation of graphs.
Citation
Bahr, P., & Hutton, G. (2024). Beyond Trees: Calculating Graph-Based Compilers (Functional Pearl). Proceedings of the ACM on Programming Languages, 8(ICFP), 370-394. https://doi.org/10.1145/3674638
Journal Article Type | Article |
---|---|
Acceptance Date | Jun 18, 2024 |
Online Publication Date | Aug 15, 2024 |
Publication Date | 2024-08 |
Deposit Date | Jun 28, 2024 |
Publicly Available Date | Aug 27, 2024 |
Journal | Proceedings of the ACM on Programming Languages |
Electronic ISSN | 2475-1421 |
Publisher | Association for Computing Machinery (ACM) |
Peer Reviewed | Peer Reviewed |
Volume | 8 |
Issue | ICFP |
Pages | 370-394 |
DOI | https://doi.org/10.1145/3674638 |
Public URL | https://nottingham-repository.worktribe.com/output/36576878 |
Publisher URL | https://dl.acm.org/doi/10.1145/3674638 |
Files
Beyond Trees: Calculating Graph-Based Compilers (Functional Pearl)
(277 Kb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by/4.0/
You might also like
Calculating Compilers Effectively (Functional Pearl)
(2024)
Presentation / Conference Contribution
Quotient Haskell: Lightweight Quotient Types for All
(2024)
Journal Article
Programming language semantics: It’s easy as 1,2,3
(2023)
Journal Article
Monadic compiler calculation (functional pearl)
(2022)
Journal Article
Calculating dependently-typed compilers (functional pearl)
(2021)
Journal Article
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search