Game semantics for higher-order concurrency

被引:0
|
作者
Laird, J. [1 ]
机构
[1] Univ Sussex, Dept Informat, Brighton BN1 9RH, E Sussex, England
来源
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, Proceedings | 2006年 / 4337卷
关键词
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We describe a denotational (game) semantics for a call-by-value functional language with multiple threads of control, which may communicate values of general type on locally declared channels. This develops previous work which interpreted freshly generated names in a category of games acted upon by the group of natural number automorphisms, by showing how names may be associated with "dependent arenas" in which interaction between strategies, corresponding to asynchronous communication on named channels, may occur. We describe a model of the call-by-value A-calculus (a closed Freyd category) based on these arenas, and use this as the basis for interpreting our language. We prove that the semantics is fully abstract with respect to may-testing using a correspondence between channel and function types based on the "triggering" representation of procedure-passing in terms of name-passing.
引用
收藏
页码:417 / 428
页数:12
相关论文
共 50 条
  • [1] Game semantics approach to higher-order complexity
    Feree, Hugo
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 87 : 1 - 15
  • [2] Higher-Order Concurrency for Microcontrollers
    Sarkar, Abhiroop
    Krook, Robert
    Svensson, Bo Joel
    Sheeran, Mary
    PROCEEDINGS OF THE 18TH ACM SIGPLAN INTERNATIONAL CONFERENCE ON MANAGED PROGRAMMING LANGUAGES AND RUNTIMES (MPLR '2021), 2021, : 26 - 35
  • [3] Leafy automata for higher-order concurrency
    Dixon, Alex
    Lazic, Ranko
    Murawski, Andrzej S.
    Walukiewicz, Igor
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2021, 2021, 12650 : 184 - 204
  • [4] Higher-order concurrency in Java']Java
    Demaine, ED
    PARALLEL PROGRAMMING AND JAVA, 1997, 50 : 34 - 47
  • [5] Higher-order semantics and extensionality
    Benzmüller, C
    Brown, CE
    Kohlhase, M
    JOURNAL OF SYMBOLIC LOGIC, 2004, 69 (04) : 1027 - 1088
  • [6] First-order reasoning for higher-order concurrency
    Koutavas, Vasileios
    Hennessy, Matthew
    COMPUTER LANGUAGES SYSTEMS & STRUCTURES, 2012, 38 (03) : 242 - 277
  • [7] Verifying higher-order concurrency with data automata
    Dixon, Alex
    Lazic, Ranko
    Murawski, Andrzej S.
    Walukiewicz, Igor
    2021 36TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2021,
  • [8] Relational semantics for higher-order programs
    Aboul-Hosn, Kamal
    Kozen, Dexter
    MATHEMATICS OF PROGRAM CONSTRUCTION, 2006, 4014 : 29 - 48
  • [9] SEMANTICS OF HIGHER-ORDER RECURSION SCHEMES
    Adamek, Jiri
    Milius, Stefan
    Velebil, Jiri
    LOGICAL METHODS IN COMPUTER SCIENCE, 2011, 7 (01)
  • [10] Semantics of Higher-Order Recursion Schemes
    Adamek, Jiri
    Milius, Stefan
    Velebil, Jiri
    ALGEBRA AND COALGEBRA IN COMPUTER SCIENCE, PROCEEDINGS, 2009, 5728 : 49 - +