oleg | 12 Dec 11:20

Genuine shift/reset in Haskell98


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)


Gmane