Behavioural equivalence via modalities for algebraic effects

A Simpson, N Voorneveld - ACM Transactions on Programming …, 2019 - dl.acm.org
A Simpson, N Voorneveld
ACM Transactions on Programming Languages and Systems (TOPLAS), 2019dl.acm.org
The article investigates behavioural equivalence between programs in a call-by-value
functional language extended with a signature of (algebraic) effect-triggering operations.
Two programs are considered as being behaviourally equivalent if they enjoy the same
behavioural properties. To formulate this, we define a logic whose formulas specify
behavioural properties. A crucial ingredient is a collection of modalities expressing effect-
specific aspects of behaviour. We give a general theory of such modalities. If two conditions …
The article investigates behavioural equivalence between programs in a call-by-value functional language extended with a signature of (algebraic) effect-triggering operations. Two programs are considered as being behaviourally equivalent if they enjoy the same behavioural properties. To formulate this, we define a logic whose formulas specify behavioural properties. A crucial ingredient is a collection of modalities expressing effect-specific aspects of behaviour. We give a general theory of such modalities. If two conditions, openness and decomposability, are satisfied by the modalities, then the logically specified behavioural equivalence coincides with a modality-defined notion of applicative bisimilarity, which can be proven to be a congruence by a generalisation of Howe’s method. We show that the openness and decomposability conditions hold for several examples of algebraic effects: nondeterminism, probabilistic choice, global store, and input/output.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果