Memoryful Geometry of Interaction II: Recursion and Adequacy
A recently introduced general framework of Memoryful Geometry of Interaction (mGoI) provides a sound translation of lambda-terms (on the high-level) to their realizations by stream transducers (on the low-level), where the internal states of the latter (called memories) are exploited for accommodating algebraic effects of Plotkin and Power. The translation is compositional, hence “denotational,” where transducers are inductively composed using an adaptation of Barbosa’s coalgebraic component calculus.
However, to the current authors’ best knowledge, there has not been any systematic treatment of recursion in this mGoI framework. This is the goal of the current paper. We introduce two new fixed-point operators in the coalgebraic component calculus. The two follow the previous work on recursion in GoI and are called Girard style and Mackie style: the former obviously exhibits some nice domain-theoretic properties, while the latter gives simple construction of resulting transducers. Their equivalence is established on the categorical (or, traced monoidal) level of abstraction, and is therefore generic with respect to the choice of algebraic effects. Our main result is an adequacy theorem of our mGoI translation, against Plotkin and Power’s operational semantics for algebraic effects.
Fri 22 JanDisplayed time zone: Guadalajara, Mexico City, Monterrey change
14:20 - 15:35
Track 2: Foundations of Model CheckingResearch Papers at Grand Bay South
Chair(s): Alexandra Silva Radboud University Nijmegen
|Lattice-Theoretic Progress Measures and Coalgebraic Model Checking|
Ichiro Hasuo University of Tokyo, Shunsuke Shimizu University of Tokyo, Corina Cirstea University of SouthamptonMedia Attached
|Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components|
Krishnendu Chatterjee IST Austria, Amir Kafshdar Goharshady , Rasmus Ibsen-Jensen , Andreas PavlogiannisMedia Attached
|Memoryful Geometry of Interaction II: Recursion and Adequacy|
Koko Muroya University of Tokyo, Naohiko Hoshino Kyoto University, Ichiro Hasuo University of TokyoMedia Attached