Proceedings of the ACM on Programming Languages · 2019 · 46 citations · 40 references
Language StudiesComputer ScienceProgramming LanguagesSemanticsSyntaxSyntactic AnalysisSyntax-semantics InterfaceType SystemsEffect SemanticsLambda Calculus SemanticsLexical ScopeStatic Type CheckingType-level Programming
Handlers of algebraic effects aspire to be a practical and robust programming construct that allows one to define, use, and combine different computational effects. Interestingly, a critical problem that still bars the way to their popular adoption is how to combine different uses of the same effect in a program, particularly in a language with a static type-and-effect system. For example, it is rudimentary to define the “mutable memory cell” effect as a pair of operations, put and get , together with a handler, but it is far from obvious how to use this effect a number of times to operate a number of memory cells in a single context. In this paper, we propose a solution based on lexically scoped effects in which each use (an “instance”) of an effect can be singled out by name, bound by an enclosing handler and tracked in the type of the expression. Such a setting proves to be delicate with respect to the choice of semantics, as it depends on the explosive mixture of effects, polymorphism, and reduction under binders. Hence, we devise a novel approach to Kripke-style logical relations that can deal with open terms, which allows us to prove the desired properties of our calculus. We formalise our core results in Coq, and introduce an experimental surface-level programming language to show that our approach is applicable in practice.
40
Notions of computation and monads
Eugenio Moggi · Information and Computation · 1991 · 1.7K citations
Philip Wadler · 1990 · 575 citations · Full text
Monad transformers and modular interpreters
Sheng Liang, Paul Hudak, Mark P. Jones · 1995 · 504 citations · Full text
Jan Lucassen, David K. Gifford · 1988 · 480 citations