Categorical combinatorics of scheduling and synchronization in game semantics
Categorical combinatorics of scheduling and synchronization in game semantics
复制标题
游戏语义中调度和同步的分类组合
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Paul
中科院分区：
文献类型：
--
作者：
Paul
游戏语义学是将类型解释为游戏，将程序解释为在空间和时间上与环境交互的策略的艺术。为了反映程序的交互行为，策略需要遵循特定的调度策略。通常，在纯顺序编程语言的情况下，程序（播放器）和它的环境（对手）将以严格交替的方式一个接一个地播放。另一方面，在并发语言的情况下，玩家和对手将被允许以非交替的方式连续玩几步。在这两种情况下，调度策略的设计都非常仔细，以确保策略正确同步，并在插入时很好地组合。一个长期存在的概念性问题是理解给定的调度策略何时以及为什么起作用，并且在这个意义上是组合的。在本文中，我们展示了一些简单的和基本的组合结构，确保一个给定的调度策略编码为同步模板定义了一个对称的monoidal封闭（实际上是星自治）bicategory的游戏，策略和模拟。为了这个目的，我们选择在一个非常一般的水平上工作，并说明我们的方法，通过构建两个模板的线性逻辑的游戏模型，不同的口味（交替和非交替）使用相同的分类组合，在小类别的类别。作为一个整体，本文可以被看作是一个赞美诗同步，同步代数的概念在进程演算的基础上，并顺利适应编程语言的语义，结合游戏语义和范畴代数的融合点的想法。
Game semantics is the art of interpreting types as games and programs as strategies interacting in space and time with their environment. In order to reflect the interactive behavior of programs, strategies are required to follow specific scheduling policies. Typically, in the case of a purely sequential programming language, the program (Player) and its environment (Opponent) will play one after the other, in a strictly alternating way. On the other hand, in the case of a concurrent language, Player and Opponent will be allowed to play several moves in a row, in a non-alternating way. In both cases, the scheduling policy is designed very carefully in order to ensure that the strategies synchronize properly and compose well when plugged together. A longstanding conceptual problem has been to understand when and why a given scheduling policy works and is compositional in that sense. In this paper, we exhibit a number of simple and fundamental combinatorial structures which ensure that a given scheduling policy encoded as synchronization template defines a symmetric monoidal closed (and in fact star-autonomous) bicategory of games, strategies and simulations. To that purpose, we choose to work at a very general level, and illustrate our method by constructing two template game models of linear logic with different flavors (alternating and non-alternating) using the same categorical combinatorics, performed in the category of small categories. As a whole, the paper may be seen as a hymn in praise of synchronization, building on the notion of synchronization algebra in process calculi and adapting it smoothly to programming language semantics, using a combination of ideas at the converging point of game semantics and of categorical algebra.