main.pdf (258.21 kB)
A geometry of interaction machine for Gödel's System T
Gödel’s System T is the simply typed lambda calculus extended with numbers and an iterator. The higher-order nature of the language gives it enormous expressive power—the language can represent all the primitive recursive functions and beyond, for instance Ackermann’s function. In this paper we use System T as a minimalistic functional language. We give an interpretation using a data-flow model that incorporates ideas from the geometry of interaction and game semantics. The contribution is a reversible model of higher-order computation which can also serve as a novel compilation technique.
History
Publication status
- Published
File Version
- Accepted version
Journal
Proceedings of the 24th International Workshop on Logic, Language, Information, and Computation; London, UK; 18-21 July 2017ISSN
9783662553855Publisher
Springer VerlagExternal DOI
Volume
10388Page range
229-241ISBN
0302-9743Series
Lecture notes in computer scienceDepartment affiliated with
- Informatics Publications
Research groups affiliated with
- Foundations of Software Systems Publications
Full text available
- Yes
Peer reviewed?
- Yes
Editors
Juliette Kennedy, Ruy J G B de QueirozLegacy Posted Date
2017-07-17First Open Access (FOA) Date
2017-07-17First Compliant Deposit (FCD) Date
2017-07-17Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC