12 Dec 11:20
Genuine shift/reset in Haskell98
From: <oleg <at> okmij.org>
Subject: Genuine shift/reset in Haskell98
Newsgroups: gmane.comp.lang.haskell.general
Date: 2007-12-12 10:23:52 GMT
Subject: Genuine shift/reset in Haskell98
Newsgroups: gmane.comp.lang.haskell.general
Date: 2007-12-12 10:23:52 GMT
This message announces the Haskell98 implementation of Asai and Kameyama's polymorphic delimited continuations, with effect typing, full soundness (well-typed terms don't give any run-time exceptions), answer-type modification and polymorphism. Thanks to parameterized monads the implementation is the straightforward translation of the rules of the calculus. Parameterized monads seem to have proven their claim for syntactic sugar. http://okmij.org/ftp/Haskell/ShiftResetGenuine.hs Delimited control operators shift/reset are, fortunately, becoming popular. Alas, all widely available implementations suffer deficiencies: for example, the type system does not prevent attempts to execute shift outside the dynamic scope of reset, which leads to a run-time error. Furthermore, the implementations do not permit modifications of the answer-type, and so make impossible many elegant applications of shift/reset such as fully typed sprintf. In particular, shift id (or, shift return, in the monadic form), so often used in linguistics, are not typeable in any widely available implementation of delimited continuations. Related to the first issue, implemented calculi of delimited continuations are not strongly normalizing. That fact has been known for some time; it has been shown recently that the calculus of multi-prompt delimited continuations -- the DC calculus of the DDBinding paper, implemented in the DelimCC Haskell library -- expresses the fix-point combinator and emulates general recursive types, and so is, in fact, Turing complete. http://okmij.org/ftp/Computation/Continuations.html#delimcc-rectype Back in 1989 Danvy and Filinski recognized that ensuring strong type soundness (aka, control decency: no naked shift) requires a(Continue reading)
RSS Feed