TY - GEN

T1 - Monads in action

AU - Filinski, Andrzej

N1 - Conference code: 37

PY - 2010

Y1 - 2010

N2 - In functional programming, monadic characterizations of computational effects are normally understood denotationally: they describe how an effectful program can be systematically expanded or translated into a larger, pure program, which can then be evaluated according to an effect-free semantics. Any effect-specific operations expressible in the monad are also given purely functional definitions, but these definitions are only directly executable in the context of an already translated program. This approach thus takes an inherently Church-style view of effects: the nominal meaning of every effectful term in the program depends crucially on its type.We present here a complementary, operational view of monadic effects, in which an effect definition directly induces an imperative behavior of the new operations expressible in the monad.  This behavior is formalized as additional operational rules for only the new constructs; it does not require any structural changes to the evaluation judgment.  Specifically, we give a small-step operational semantics of a prototypical functional language supporting programmer-definable, layered effects, and show how this semantics naturally supports reasoning by familiar syntactic techniques, such as showing soundness of a Curry-style effect-type system by the progress+preservation method.

AB - In functional programming, monadic characterizations of computational effects are normally understood denotationally: they describe how an effectful program can be systematically expanded or translated into a larger, pure program, which can then be evaluated according to an effect-free semantics. Any effect-specific operations expressible in the monad are also given purely functional definitions, but these definitions are only directly executable in the context of an already translated program. This approach thus takes an inherently Church-style view of effects: the nominal meaning of every effectful term in the program depends crucially on its type.We present here a complementary, operational view of monadic effects, in which an effect definition directly induces an imperative behavior of the new operations expressible in the monad.  This behavior is formalized as additional operational rules for only the new constructs; it does not require any structural changes to the evaluation judgment.  Specifically, we give a small-step operational semantics of a prototypical functional language supporting programmer-definable, layered effects, and show how this semantics naturally supports reasoning by familiar syntactic techniques, such as showing soundness of a Curry-style effect-type system by the progress+preservation method.

U2 - 10.1145/1707801.1706354

DO - 10.1145/1707801.1706354

M3 - Article in proceedings

SN - 978-1-60558-479-9

SP - 483

EP - 494

BT - POPL'10

PB - Association for Computing Machinery

T2 - 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

Y2 - 17 January 2010 through 23 January 2010

ER -