Haskell-Cafe

Download

haskell-cafe@haskell.org

September 2010

292 participants
262 discussions

Three new implementations of multi-prompt delimited control
by oleg＠okmij.org 01 Sep '10

01 Sep '10

The monadic framework for delimited continuations described in the paper by Dybvig, Peyton Jones and Sabry (JFP 2007) has found many applications, for example, fair backtracking search, final zippers, direct-style web programming, direct-style code generation, and probabilistic programming. The extensive experience suggested improvements in efficiency and, mainly, programmer's convenience. The three new libraries are novel implementations of the enhanced framework. Prompts, for instance, can now be bound to top-level identifiers and do not have to be passed around explicitly or through the extra Reader monad. The new libraries benefited from the experience of implementing delimited control on several platforms. All three libraries provide monad transformers, with basic operations to capture and reinstall delimited continuations: pushPrompt, shift, shift0, control, takeSubCont/pushSubCont. All three libraries support multiple, typed prompts. All three libraries are quite distinct from the original implementation in Dybvig, Peyton Jones, Sabry's paper. For instance, none of the new libraries use unsafeCoerce. All three implementations are derived from the specification of delimited control: from the reduction semantics or from the definitional interpreter. The new libraries differ in -- performance -- ease of understanding -- constraints on the base monad or the prompt types -- flavors of prompts and support for global prompts The libraries are named CCRef, CCExc and CCCxe. The complete code of the libraries along with the regression test suite are publicly available at http://okmij.org/ftp/continuations/CCmonad/ The directory includes sample code (Generator1.hs and Generator2.hs), implementing generators like those of Python. A more extensive example is the porting of the LogicT library (of fair backtracking monad transformers), from the old CC implementation to CCExc/CCCxe: http://okmij.org/ftp/Haskell/LogicT.tar.gz One of the sample applications of LogicT, of a computer playing 5x5 tic-tac-toe against itself, was used as a macro-benchmark of the libraries. The end of the file TicTacToe.hs summarizes the results. The new libraries are faster (so the reader who may wish to play will have less time to think). The library CCRef is closest to the interface of Dybvig, Peyton Jones and Sabry. CCRef is derived from the definitional interpreter using the implementation techniques described and justified in the FLOPS 2010 paper. The monad transformer CC implemented by CCRef requires the base monad to support reference cells. In other words, the base monad must be a member of the type class Mutable: that is, must be IO, ST, STM or their transformer. CCRef adds to the original interface the frequently used function abortP as a primitive. As one may notice from their names, the libraries CCExc and CCCxe are closely related. CCCxe is derived as a CPS version of CCExc. CCCxe is sometimes more efficient; it is always less perspicuous. Both libraries provide the identical interface and are interchangeable. It seems that CCExc is faster at delimited control but imposes more overhead on the conventional code; CCCxe is dual. It pays to use CCCxe in code with long stretches of determinism punctuated by fits and restarts. We now explain new features of CCExc. It is the most direct implementation of the bubble-up (bottom-up) reduction semantics of multi-prompt delimited control, described on PDF page 57 of http://okmij.org/ftp/gengo/CAG-talk.pdf Unlike all other implementations of delimited control in Haskell, CCExc is _not_ based on the continuation monad. Rather, the monad of CCExc is an extension of the Error monad: a monad for restartable exceptions. CCExc offers not one monad transformer but a family (CC p), parameterized by the prompt flavor p. The library defines several prompt flavors; the users are welcome to define their own. Prompt flavors are inherently like exception flavors (the FLOPS 2010 paper even calls prompts `exception types' or `exception envelopes'). Control.Exception defines singular global exceptions such as BlockedOnDeadMVar. There are global exceptions like ErrorCall, parameterized by the error string. There are closed global variants, such as ArithException, with the fixed number of alternatives. There are also open variants, SomeException, with any number of potential alternatives. Users may define their own exception types, whose visibility may be restricted to a module or a package. Finally, one may even generate distinct expression types dynamically, although that is seldom needed. The libraries CCExc and CCCxe support all these flavors. On one end is the prompt flavor (PS w). There is only one prompt of that flavor, which is globally defined and does not have to be passed around. The monad transformer (CC (PS w)) then is the monad transformer for regular, single-prompt delimited continuations, for the answer-type w. Danvy/Filinski test, which looks in Scheme as > (display (+ 10 (reset (+ 2 (shift k (+ 100 (k (k 3)))))))) appears as follows in Haskell: > test5 = (print =<<) . runCC $ > incr 10 . pushPrompt ps $ > incr 2 . shiftP ps $ \sk -> incr 100 $ sk =<< (sk 3) where > incr :: Monad m => Int -> m Int -> m Int > incr n = ((return . (n +)) =<<) [A reader might wish to try to predict the result of test5.] The global identifier ps is defined in CCExc. One should read the operator (=<<), the flipped bind, as a ``call-by-value application'', akin to the application in CBV languages such as Scheme. That is, "f =<< e" is the application that first evaluates the argument e, performing its effects. The value is passed to f, which is evaluated in turn. The application "sk 3" is an optimized version of "sk =<< (return 3)". The appearance of print tells us that test5 is the IO computation. If we rather had the result of test5 as a pure value (an integer), we merely need to pass the result of the runCC expression to runST. The file Generator1.hs shows one example of using PS; the file SRReifT.hs of the LogicT is a larger example. The file Generator2.hs demonstrates why we may need more than one prompt (perhaps with different types). The library offers several flavors of multiple prompts: closed unions (P2) and open unions (PP, PM, PD). The open unions are like SomeException. The prompt flavor PD carries an extra integer identifier to further distinguish prompts of the same type. It becomes possible therefore to dynamically generate an arbitrary number of PD prompts, which was required in Dybvig, Peyton Jones and Sabry's framework. We close by juxtaposing the Python code that uses generators to traverse a binary tree in-order >>> def inorder(t): ... if t: ... for x in inorder(t.left): ... yield x ... yield t.label ... for x in inorder(t.right): ... yield x with the corresponding Haskell code (excerpted from Generator1.hs) > in_order :: (Monad m) => Tree -> CC (P m Label) m () > in_order Leaf = return () > in_order (Node label left right) = do > in_order left > yield label > in_order right In Python, 'yield' is a keyword and generators are built-in. In Haskell, yield is a regular, small, user-defined function, and generators are programmed-in.

1 0

Quick Question for QuickCheck2
by Sebastian Höhn 01 Sep '10

01 Sep '10

Hello, perhaps I am just blind or is it a difficult issue: I would like to generate Char values in a given Range for QuickCheck2. There is this simple example from the haskell book: instance Arbitrary Char where arbitrary = elements (['A'..'Z'] ++ ['a' .. 'z'] ++ " ~!@#$%^&*()") This does not work in QuickCheck2 since the instance is already defined. How do I achieve this behaviour in QC2? Thanks for helping. Sebastian

6 13

Jump to page: