Abstract
The article bridges between two major paradigms in computation, the functional, at basis computation from input to output, and the interactive, where computation reacts to its environment while underway. Central to any compositional theory of interaction is the dichotomy between a system and its environment. Concurrent games and strategies address the dichotomy in fine detail, very locally, in a distributed fashion, through distinctions between Player moves (events of the system) and Opponent moves (those of the environment). A functional approach has to handle the dichotomy more ingeniously, via its blunter distinction between input and output. This has led to a variety of functional approaches, specialised to particular interactive demands. Through concurrent games we can see what separates and connects the differing paradigms, and show how:
•to lift functions to strategies; how to turn functional dependency to causal dependency and so exploit functional techniques.
•several approaches of functional programming and logic arise naturally as full subcategories of concurrent games, including stable domain theory; nondeterministic dataflow; geometry of interaction; the dialectica interpretation; lenses and optics, and their extensions to containers in dependent lenses and optics.
•the enrichments of strategies (e.g. to probabilistic, quantum or real-number computation) specialise to the functional cases.
•to lift functions to strategies; how to turn functional dependency to causal dependency and so exploit functional techniques.
•several approaches of functional programming and logic arise naturally as full subcategories of concurrent games, including stable domain theory; nondeterministic dataflow; geometry of interaction; the dialectica interpretation; lenses and optics, and their extensions to containers in dependent lenses and optics.
•the enrichments of strategies (e.g. to probabilistic, quantum or real-number computation) specialise to the functional cases.
Original language | English |
---|---|
Title of host publication | 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
Subtitle of host publication | Proceedings |
Editors | Igor Walukiewicz |
Place of Publication | Piscataway, NJ |
Publisher | IEEE |
Pages | 1-14 |
Number of pages | 14 |
ISBN (Electronic) | 9798350335873 |
ISBN (Print) | 9798350335880 |
DOIs | |
Publication status | Published - 14 Jul 2023 |
Keywords
- function
- strategy
- computation