A Syntactic View of Computational Adequacy
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Authors
Colleges, School and Institutes
Abstract
When presenting a denotational semantics of a language with recursion, it is necessary to show that the semantics is computationally adequate, i.e. that every divergent term denotes the “bottom” element of a domain. We explain how to view such a theorem as a purely syntactic result. Any theory (congruence) that includes basic laws and is closed under an infinitary rule that we call “rational continuity” has the property that every divergent term is equated with the divergent constant. Therefore, to prove a model adequate, it suffices to show that it validates the basic laws and the rational continuity rule. While this approach was inspired by the categorical, ordered framework of Abramsky et. al., neither category theory nor order is needed. The purpose of the paper is to present this syntactic result for call-bypush-value extended with term-level recursion and polymorphic types. Our account begins with PCF, then includes sum types, then moves to call-by-push-value, and finally includes polymorphic types.
Details
Original language | English |
---|---|
Title of host publication | Foundations of Software Science and Computation Structures (FOSSACS 2018) |
Subtitle of host publication | 21st International Conference, FOSSACS 2018 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018 Thessaloniki, Greece, April 14–20, 2018 Proceedings |
Editors | Christel Baier, Ugo Dal Lago |
Publication status | Published - 14 Apr 2018 |
Event | 21st International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2018) - Thessaloniki, Greece Duration: 14 Apr 2018 → 20 Apr 2018 |
Publication series
Name | Lecture Notes in Computer Science - Advanced Research in Computing and Software Science |
---|---|
Publisher | Springer |
Volume | 10803 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 21st International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2018) |
---|---|
Country | Greece |
City | Thessaloniki |
Period | 14/04/18 → 20/04/18 |