- Haskell-Cafe - Haskell.org

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

Fourth (and Fifth) GhentFPG Meeting: Date and Call for Talks
by Jeroen Janssen 31 Aug '10

31 Aug '10

(apologies if you receive multiple copies) Dear all, We would like to announce that the fourth meeting of the Ghent Functional Programming Group will be held on Thursday, October 7th at 19h. The location will again be the Technicum building of Ghent University (Sint-Pietersnieuwstraat 41, 9000 Gent). Anyone is free to give a talk, so if you feel like giving one, just contact jejansse(a)gmail.com. The final program will be announced in a few weeks. Finally, we would also like to remind you that GhentFPG is organizing BelHac, a Haskell hackathon on 5-7 November 2010. More details can be found at http://www.haskell.org/haskellwiki/Ghent_Functional_Programming_Group/BelHac The fifth GhentFPG meeting will take place at this hackathon, so if you plan on going, and feel like giving a talk at this fifth meeting, just contact me. We would be more than happy to have some international speakers at our meeting! Hope to see you then, The GhentFPG Organizing Committee.

1 0

ANNOUNCE: iteratee-compress 0.1
by Maciej Piechotka 31 Aug '10

31 Aug '10

Iteratee-compress provides compressing and decompressing enumerators. Currently only gzip is provided but at least bzip is planned. Additionally more fine-control over stream (i.e. flushing) is planned. ---- Library currently depends on zlib haskell library only for sharing parameters data. However no zlib function is called (the needed functions are not exported) and the symbols it uses from necessity are deprecated. Would it be better to copy the parameters from zlib and drop the dependency? Please note also that the library do not bundle zlib (C) as zlib (Haskell) do.

2 1

Arrow transformers: how to make them wright?
by Permjacov Evgeniy 31 Aug '10

31 Aug '10

A Control.Arrow in base package introduces an arrow type, and ghc have good support for arrow notation. Many things, avaible in monads, are avaible in arrows as well. There is an arrows package, that introduces some arrow classes : state, reader, writer and so on. However, it does not introduce systematic lifting of arrow classes operations. Arrows are generalisation of monads. There are libraries, that introduces systematic lifting of operations from monad classes. So, the quesions are: what operations should be in arrow transformer class? Captain Obvious says, it should look at least like: class ArrowTrans t where lift :: ( Arrow a, Arrow (t a) ) => a b c -> t a b c what laws arrow transformers must obey? C.O. says, at least lift a b c >>> lift a c d == lift ( a b c >> a c d ) how to perform lifting of actions for classes like this: class Arrow a => ArrowError a e| a-> e where raise :: a e () handle :: a e c -> a b c -> a b c class Arrow a => ArrowReader a e | a -> e where look :: a () e local :: a b c -> a (b,e) c The answers lies somewhere in category theory, C.O. says. Of course, such answer is not satisfactory.

3 2

ANNOUNCE: Darcs hacking sprint (15-17 Oct, Orleans)
by Eric Kow 31 Aug '10

31 Aug '10

Hello Haskellers! The Darcs Team will soon be hosting its fifth hacking sprint this October. We would be delighted if you could join us. http://wiki.darcs.net/Sprints/2010-10 Details ------- When: 15-17 October 2010 Where: Orleans, France Who Anybody who wants to hack on Darcs (or Camp, Focal, etc) Beginners especially welcome! Why: Darcs aims to have bi-annual hacking sprints so that we can get together on a regular basis, hold design discussions, hack up a storm and have a lot fun. What: We'll be starting work on the next release after the upcoming Darcs 2.5. Could we see a much fast darcs over networks? Friendlier darcs annotate? Exciting times ahead... We intend to set aside at least one Darcs hacker for mentoring beginners, so if you're new to Haskell or to Darcs hacking, here's a good chance to plunge in and start working on a real world project. How: Email me <kowey(a)darcs.net> to let me know you're interested! Keep in mind that we do have funds to help pay for travel expenses; just let me know if you'd like to come :-) Thanks ------ Thanks to team Florent Becker and University of Orleans for generously offering to host this event! Thanks also to donors from the fundraising drive this year. We'll be using that money to help Darcs hackers get to Orleans Supporting Darcs ---------------- Darcs is a very happy member of the Software Freedom Conservancy. Among other things, the Software Freedom Conservancy makes it easy for open source projects to raise funds and hold assets (as part of a legal entity). For more information on supporting Darcs, see http://darcs.net/donations.html See you there! -- Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow> For a faster response, please try +44 (0)1273 64 2905.

17 21

Searching for Haskell (was: [Haskell-cafe] Slightly humorous: Headhunters toolbox (example for Germany))
by Henk-Jan van Tuyl 31 Aug '10

31 Aug '10

On Tue, 31 Aug 2010 13:57:42 +0200, Alberto G. Corona <agocorona(a)gmail.com> wrote: > Entering "haskell language" instead of "haskell" the ambiguity > dissapears. Then, Jamaica no longer appears in the crude reality . The > weigth of USA is hides all other country here. > > I think that a more appropriate term to look for haskell interest is > "monad" although it may catch some crazy philosophers too. The result is > interesting, > You can still get things like a page titled "Ben Haskell - Language Technologies Institute - Carnegie Mellon", and of course, not all pages about the programming language contain the word "language". To get proper results you would need a good semantic search engine, but these search engines seem to be in early research stage. Regards, Henk-Jan van Tuyl -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html --

1 0

combinators in the syb lib -- or generic heterogeneous traversals that fold
by Carter Schonwald 31 Aug '10

31 Aug '10

Hello All, In the course of some code I've been working on, I found I needed generic foldl / foldr over heterogeneous data structures, where I can easily pick whether I want top down left right, botom up left right, and ___ right left traversals, and to in tandem sensibly approach if a parent node should be included altogether What i'm wondering is if i'm somehow overlooking some simpler ways of writing such or if my attached code for the foldl case (the foldr analogue is easy to see from the example code). code with example follows --- my "foldl" that is abstracted from traversal order travL :: (b -> a -> b)-> GenericQ (Maybe a) -> (Maybe a -> b ->(b -> a -> b)->(b->b)-> b) -> GenericQ (b ->b) travL f qry merge x nil = merge (qry x) nil f (\nl-> foldl (flip ($)) nl $ gmapQ (travL f qry merge) x ) --travR could be written as --- travR f qry merge x nil = foldl (flip f) nil $ travL (flip (:)) qry merge x [] -- example usage -- takes the integers in some datastructure, and puts them in a list -- example: flipList :: Data a => a -> [Integer] flipList x = travL (flip (:) ) (mkQ Nothing (Just :: Integer -> Maybe Integer) ) (\ v nl f k -> maybe (k nl) (\y -> k $! f nl y) v ) x [] I suppose that i could simplify it to travL :: GenericQ (Maybe a) -> (Maybe a -> b ->(b->b)-> b) -> GenericQ (b ->b) and have the operand *f* of the fold work within the *merge* parameter, but that doesn't address the important bit in my mind, namely that while its pretty clear to me that I can write the *synthesize*and *everything* combinators using my "travL/R" stuff, its not clear to me that the converse or something close to it is the case. Anyways, what're everyone's thoughts? thanks! -Carter

1 1

Ed Lambda: Functional programming meetup in Edinburgh
by Ollie Saunders 31 Aug '10

31 Aug '10

Hi guys, I'm running a meetup for functional programming in Edinburgh. The first one will be on the 13th of September at Malone's Irish Bar (14 Forrest Road) and will continue every 2nd monday of each month. For the first meetup I think we'll just be having a chat and getting to know each other but I hope to be able to expand it to talks and coding dojos once we have some regular numbers. For more details: http://meetup.com/ed-lambda/ And we're on Twitter: http://twitter.com/ed_lambda

2 1

Support for lock-free/wait-free programming?
by Gregory Collins 30 Aug '10

30 Aug '10

Hello all, Does GHC expose any primitives for things like atomic compare-and-swap? I can't seem to find anything in the docs. I'm wondering if it's possible, for example, to implement things like the wait-free concurrent queue from [1] or a lock-free wait-free hash table like the Azul people are doing [2]. In network servers, we often have a large number of clients fighting over shared resources -- even simple stuff like "which threads are scheduled to timeout?" and "which threads are currently active, so I can kill them if I need to?". Shared mutable collections seem to be a fact of life here. Under load, pure data structures behind MVars don't perform well because of lock contention, and in my experience atomicModifyIORef is marginally better but still suffers from contention issues (probably related to thunk blackholing). Recently I got a ~35% speedup on a benchmark by switching one of these tables from a Map behind an IORef to a hashmap using a striped-locking scheme (see [3] if you're interested.) I think there's a need for high-concurrency data structures like this, and I don't see much on Hackage that addresses it. As much as we like to say that we have a handle on concurrency issues, from what I can see java.util.concurrent.* has us soundly thrashed in this department, especially as it relates to exposing atomic wait-free CPU primitives like the ones in java.util.concurrent.atomic.* [4]. Speaking as a partisan, this cannot be allowed to stand, can it? Cheers, G. ------------------------------------------------------------------------------ [1] Maged M. Michael and Michael L. Scott, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms": http://www.cs.rochester.edu/u/michael/PODC96.html [2] http://www.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf [3] http://github.com/snapframework/snap-server/blob/master/src/Data/HashMap/Co… [4] http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/At… -- Gregory Collins <greg(a)gregorycollins.net>

4 11