Syntax and Semantics for Operations with Scopes

Maciej Piróg, Tom Schrijvers, Nicolas Wu, Mauro Jaskelioff

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

6 Citations (Scopus)
272 Downloads (Pure)

Abstract

Motivated by the problem of separating syntax from semantics in programming with algebraic effects and handlers, we propose a categorical model of abstract syntax with so-called scoped operations. As a building block of a term, a scoped operation is not merely a node in a tree, as it can also encompass a whole part of the term (a scope). Some examples from the area of programming are given by the operation catch for handling exceptions, in which the part in the scope is the code that may raise an exception, or the operation once, which selects a single solution from a nondeterministic computation. A distinctive feature of such operations is their behaviour under program composition, that is, syntactic substitution. Our model is based on what Ghani et al. call the monad of explicit substitutions, defined using the initial-algebra semantics in the category of endofunctors. We also introduce a new kind of multi-sorted algebras, called scoped algebras, which serve as interpretations of syntax with scopes. In generality, scoped algebras are given in the style of the presheaf formalisation of syntax with binders of Fiore et al. As the main technical result, we show that our monad indeed arises from free objects in the category of scoped algebras. Importantly, we show that our results are immediately applicable. In particular, we show a Haskell implementation together with practical, real-life examples.

Original languageEnglish
Title of host publicationProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
PublisherAssociation for Computing Machinery (ACM)
Pages809-818
Number of pages10
ISBN (Electronic)9781450355834
DOIs
Publication statusPublished - 9 Jul 2018
Event33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 - Oxford, United Kingdom
Duration: 9 Jul 201812 Jul 2018

Conference

Conference33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
CountryUnited Kingdom
CityOxford
Period9/07/1812/07/18

Fingerprint Dive into the research topics of 'Syntax and Semantics for Operations with Scopes'. Together they form a unique fingerprint.

Cite this