Representing layered monads Export

@inproceedings{citeulike:1368, abstract = {There has already been considerable research on constructing modular, monad-based specifications of computational effects (state, exceptions, nondeterminism, etc.) in programming languages. We present a simple framework in this tradition, based on a Church-style effect-typing system for an ML-like language. The semantics of this language is formally defined by a series of monadic translations, each one expanding away a layer of effects. Such a layered specification is easy to reason about, but its direct implementation (whether by parameterized interpretation or by actual translation) is often prohibitively inefficient. By exploiting deeper semantic properties of monads, however, it is also possible to derive a vastly more efficient implementation: we show that each layer of effects can be uniformly simulated by continuation-passing, and further that multiple such layers can themselves be simulated by a standard semantics for call/cc and mutable state. Thus, even multi-effect programs can be executed in Scheme or SML/NJ at full native speed, generalizing an earlier single-effect result. As an example, we show how a simple resumptionbased semantics of concurrency allows us to directly simulate a shared-state program across all possible dynamic interleavings of execution threads.}, address = {New York, NY, USA}, author = {Filinski, Andrzej}, booktitle = {POPL '99: Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, citeulike-article-id = {1368}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=292557}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/292540.292557}, doi = {10.1145/292540.292557}, isbn = {1-58113-095-3}, keywords = {continuations, functional-programming, ml, monads, scheme, side-effects, types}, location = {San Antonio, Texas, United States}, pages = {175--188}, posted-at = {2005-11-02 06:25:37}, priority = {2}, publisher = {ACM}, title = {Representing layered monads}, url = {http://dx.doi.org/10.1145/292540.292557}, year = {1999} }

TY - CONF ID - citeulike:1368 L3 - citeulike-article-id:1368 N2 - There has already been considerable research on constructing modular, monad-based specifications of computational effects (state, exceptions, nondeterminism, etc.) in programming languages. We present a simple framework in this tradition, based on a Church-style effect-typing system for an ML-like language. The semantics of this language is formally defined by a series of monadic translations, each one expanding away a layer of effects. Such a layered specification is easy to reason about, but its direct implementation (whether by parameterized interpretation or by actual translation) is often prohibitively inefficient. By exploiting deeper semantic properties of monads, however, it is also possible to derive a vastly more efficient implementation: we show that each layer of effects can be uniformly simulated by continuation-passing, and further that multiple such layers can themselves be simulated by a standard semantics for call/cc and mutable state. Thus, even multi-effect programs can be executed in Scheme or SML/NJ at full native speed, generalizing an earlier single-effect result. As an example, we show how a simple resumptionbased semantics of concurrency allows us to directly simulate a shared-state program across all possible dynamic interleavings of execution threads. CY - San Antonio, Texas, United States SN - 1-58113-095-3 AD - New York, NY, USA EP - 188 TI - Representing layered monads PB - ACM T2 - POPL '99: Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages SP - 175 KW - continuations KW - functional-programming KW - ml KW - monads KW - scheme KW - side-effects KW - types AU - Filinski, Andrzej PY - 1999/// UR - http://dx.doi.org/10.1145/292540.292557 ER -