July 2007 - Haskell-Cafe

Haskell's "currying" versus Business Objects Gem Cutter's "burning"
by peterv 04 Jul '07

04 Jul '07

In Haskell, currying can only be done on the last (rightmost) function arguments. So foo x y can be curried as foo x but not as foo ? y where ? would be a "wilcard" for the x parameter. In Haskell, one must write a new function foo2 y x = foo x y and then one can curry the x parameter like foo2 y In Gem Cutter - which is a visual programming language - on can "burn" any input argument (which is like putting the ? for any argument in the foo function). See http://resources.businessobjects.com/labs/cal/gemcutter-techpaper.pdf This burning looks more general to me, but cannot be done using the textual approach? Does this reasoning make any sense? Thanks, Peter

9 8

Playing with delimited continuations
by Dan Doel 04 Jul '07

04 Jul '07

Hello, My interest was recently caught reading some of Oleg Kiselyov's material on delimited continuations, and so I decided to look into them a little closer. Don Stewart also mentioned in passing on #haskell that'd it'd be nice to have support for delimited continuations either in the standard library, or in some other easily installable package. So, I thought I'd see what such a beast might look like, and dug up the Dybvig, Petyon-Jones, Sabry paper[1] on the subject that I'd read long ago, but probably not understood much. :) After a day or so of hacking, I have (what I think is) a proper implementation of the monad and transformer, along with a suitable typeclass, and instances for the various transformers in the MTL. However, I have by no means tested it extensively (as I don't have a lot of ideas off hand for monad stacks involving delimited continuations), and I'm not totally thrilled with the results I have, so I thought I'd ask for advice/commentary here. Code is attached. First, I guess, should come an example of code using the delimited continuations: > pop = do (h:t) <- get > put t > return h > abortP p e = withSubCont p (\_ -> e) > loop 0 _ = return 1 > loop n p = do i <- pop > if i == 0 > then abortP p (return 0) > else do r <- loop (n-1) p > return (i*r) > test1 n l = runDelCont > (runStateT (newPrompt >>= \p -> > pushPrompt p (loop n p)) l) > test2 n l = runState > (runDelContT (newPrompt >>= \p -> > pushPrompt p (loop n p))) l So, loop finds the product of the first n numbers stored in a list in the state, but aborts immediately if it sees a 0. test1 and test2 stack the monads in the opposite order, but the results are the same in this case (it isn't a very sophisticated example). Another example, from the paper, is that you can think of normal continuations as delimited continuations with a global prompt p0 that denotes the end of the computation. You can emulate this using the reader monad to store the prompt: > type Continue r b a = ReaderT (Prompt.Prompt r b) (DelCont r) a > runContinue :: (forall r. Continue r b b) -> b > runContinue ct = runDelCont (newPrompt >>= \p -> > pushPrompt p (runReaderT ct p)) > callCC' f = withCont (\k -> pushSubCont k (f (reify k))) > where > reify k v = abort (pushSubCont k (return v)) > abort e = withCont (\_ -> e) > withCont e = ask >>= \p -> withSubCont p (\k -> pushPrompt p (e k)) > loop2 l = callCC' (\k -> loop' k l 1) > where > loop' _ [] n = return (show n) > loop' k (0:_) _ = k "The answer must be 0." > loop' k (i:t) n = loop' k t (i*n) So, the loop computes the product of a list of numbers, returning a string representation thereof, but aborts with a different message if it sees 0. Again, nothing special, but it seems to work. However, this is where I started to run into some uglines that followed from my design choices. Most flows from the typeclass: class (Monad m) => MonadDelCont p s m | m -> p s where newPrompt :: m (p a) pushPrompt :: p a -> m a -> m a withSubCont :: p b -> (s a b -> m b) -> m a pushSubCont :: s a b -> m a -> m b So, 'm' is the delimited control monad in question, 'p' is the type of prompts associated with said monad, and 's' is the associated type of subcontinuations that take an 'a', and produce a 'b'. Those four functions are the generalizations of the four control operators from the paper. The crux of the matter is the way the prompts and subcontinuations are typed. A prompt 'p a' can have values of type 'a' returned through it, which is fine in the vanilla DelCont monad. However, in a monad transformed by a StateT, a computation 'm a' isn't returning an 'a' through the prompt. It's actually returning an '(a,s)', due to the state threading. And the same is an issue with the subcontinuation. So, I came up with a couple wrappers: newtype PairedPrompt s p a = PP { unPP :: p (a, s) } newtype PairedSubCont s k a b = PSC { unPSC :: k (a, s) (b, s) } And then you can declare instances like so: instance (MonadDelCont p s m) => MonadDelCont (PairedPrompt t p) (PairedSubCont t s) (StateT t m) where ... Where the declarations not only lift the delimited control actions, but wrap and unwrap the prompts and subcontinuations appropriately. However, this has two issues: 1) It seems kind of kludgy at first glance, although maybe that's just me. 2) It doesn't always work correctly. Consider the following code: > loop3 l = callCC' (\k -> loop' k l 1) > where > loop' _ [] n = return n > loop' k (0:_) _ = k 0 > loop' k (i:t) n = tell [n] >> loop' k t (i*n) It does almost the same thing as loop2, only it has some writer output, too. And we'd like to write: > test3 l = runContinue (runWriterT (loop3 l)) but we can't, because that's a type error, because the prompt is created outside of runWriterT, where it will have type 'Prompt r (a, w)', but used inside runWriterT, where it needs to have type 'PairedPrompt w (Prompt r) a'. Instead, we have to write: > test3 l = runDelCont > (runReaderT > (runWriterT > (newPrompt >>= \p -> > pushPrompt p (local (const p) $ loop3 l))) > undefined) So that the prompt is created and used in the same monadic context. This is hardly ideal. So, I suppose my first question is if anyone can see a better way of generalizing the types of the control operators to work with the arbitrarily nested monad stacks typically used in MTL. Nothing's come to my mind immediately, but I've stopped thinking about it very hard for the time being, and I'm sure there are people here who are much better acquainted with the theory of this sort of thing than I am. I suppose my other issues have to do with the original implementation itself, although I don't really feel very qualified to criticize it, and I can see why all the things were done the way that they were... First, the prompt module needs to use unsafeCoerce, or something equivalent. Prompts are, internally, just Ints, but they have a phantom type (I think that's the right term) denoting the type of value that can be returned through them. Then we eventually want to split the call stack using a prompt of type 'Prompt r a', but there be many prompts on the stack, which will have type 'Prompt r b' for some b (and the actual type of b is forgotten by the stack, I believe, as it's an existential type). However, since the internal Ints are unique identifiers, when we find that the identifiers match, 'a' and 'b' must be the same. So, the implementation uses unsafeCoerce to forge evidence that they are. But, of course, unsafeCoerce feels dirty to me, and it'd be nice if some cool type system hackery could be used instead of going around the type system. But I've really no idea whether there's any substitute for unsafeCoerce here, so I thought I'd ask some of the experts here. Second is a minor point. There's a sequence datatype in the paper that represents the delimited stack: > data Seq s r a b ... Which represents a sequence of frames that take a value of type 'a' to a value of type 'b'. The paper mentions that the empty constructor should have type 'Seq s r a a', but that it's impossible to do that, so they instead have it take a function that provides evidence of the equivalence between a and b, using 'id' and a smart constructor to have the same effect. But, with GADTs, it's now possible to have a constructor with the right type directly, so I did that in my implementation. However, after saying that in the paper, they go on to use the empty constructor with the coerced evidence functions produced above to produce empty sequences of type 'Seq s r a b' where we have some evidence that 'a' and 'b' are the same. So, using the GADT approach, where in the original paper there'd be a single EmptyS constructor, there is now required an extra coercion constructor on top of it in most cases where empty sequences are used. So, I suppose my second question is whether there is any sense in restricting the type to 'Seq s r a a' at all, since it just seems to require extra baggage? I suppose this might tie in with the above question, as the coercions of types Haskell's type system can't prove equal are what's being used. Third, just as a general question, is the paper I'm using the most definitive and recent on the subject of implementing delimited continuations in Haskell? I did some quick google searches, but nothing much turned up besides this paper, and some papers using the implementation in examples of using delimited continuations. It's also the implementation Oleg uses in his recent zipper file system, so I assume there haven't been any particularly radical developments since it was written (which wasn't that long ago, I suppose). Anyhow, I'd appreciate any discussion or thoughts anyone had on the above, or on delimited continuations in haskell in general, as it's a topic that's interested me lately. The attached code is certainly in no shape to be put in a library yet, but perhaps if the issues above can be fixed, or it's decided that they don't matter, it could pave the way. Apologies for the length, and I hope I'm posting to the right place (this didn't seem formal enough for haskell@...). Cheers, Dan Doel [1]: http://research.microsoft.com/Users/simonpj/papers/control/control.pdf

1 0

Re: [Haskell-cafe] The Garbage Collector Ate My Homework
by Tim Chevalier 04 Jul '07

04 Jul '07

[I assume this was meant to go to the list as well, so I'm adding it back to the CCs] On 7/3/07, Thomas Conway <drtomc(a)gmail.com> wrote: > It occurs to me that tweaking the GC parameters can probably make a > big difference: is starting with a bigger heap likely to help, or more > generations? My generation hypothesis is that more generations will > encourage the cached data to drop down out of generation 0, reducing > the GC load. > Starting with a bigger heap is likely to help, since it means that GCs will be needed less often. I'm not sure I buy your generation hypothesis, because even with two generations, you would expect to see some of the cached data move to generation 1. Lots of data in generation 0 implies your code continues to allocate many objects as it goes on running. On the other hand, you could still try and see if it helps. Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "The illegal we do immediately. The unconstitutional takes a little longer." -- Henry Kissinger

1 0

The Garbage Collector Ate My Homework
by Thomas Conway 04 Jul '07

04 Jul '07

Well, not quite, but look at the following: 118,342,689,824 bytes allocated in the heap 144,831,738,780 bytes copied during GC (scavenged) 335,086,064 bytes copied during GC (not scavenged) 255,257,516 bytes maximum residency (42 sample(s)) 222884 collections in generation 0 (3891.90s) 42 collections in generation 1 (153.99s) 536 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 233.66s (776.99s elapsed) GC time 4045.89s (4251.52s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 4279.55s (5028.52s elapsed) %GC time 94.5% (84.5% elapsed) Alloc rate 506,470,897 bytes per MUT second Productivity 5.5% of total user, 4.6% of total elapsed Can anyone offer general suggestions for how to fix this! T. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

3 2

Getting debugging/logging info?
by Hugh Perkins 03 Jul '07

03 Jul '07

In imperative languages we can do this type of thing: SystemLogging.LogInfo("About to do something..."); DoSomething(); SystemLogging.LogInfo("Did Something"); SystemLogging.LogInfo("x is " + x ); How can we do something similar in Haskell?

5 7

Re: [Haskell-cafe] Haskell's currying and partial application
by Peter Verswyvelen 03 Jul '07

03 Jul '07

Duh, I made a typo in my previous emails, I did mean a -> (b -> c) and not a -> (b,c). But you guys quickly corrected that IMHO when reading http://haskell.org/haskellwiki/Currying a newbie like me cannot see the difference between currying and partial application... I quote the text: -------------------- "Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed. In Haskell, all functions are considered curried: that is, all functions in Haskell take just single arguments. This is mostly hidden in notation, and so may not be apparent to a new Haskeller. Let's take the function div :: Int -> Int -> Int which performs integer division. The expression div 11 2 unsurprisingly evaluates to 5. But there's more that's going on than immediately meets the untrained eye. It's a two-part process. First, div 11 is evaluated and returns a function of type Int -> Int" -------------------- But that is partial application, not currying no... Later in the text tuples are mentioned, but the real definition of currying being -- Hope I get it right this time... curry :: ((a, b) -> c) -> a -> b -> c is not really clear from the article to me... >----- Oorspronkelijk bericht ----- >Van: Henning Thielemann [mailto:lemming@henning-thielemann.de] >Verzonden: dinsdag, juli 3, 2007 01:48 PM >Aan: 'Peter Verswyvelen' >CC: Haskell-Cafe(a)haskell.org >Onderwerp: Re: [Haskell-cafe] Haskell's currying and partial application > > >On Tue, 3 Jul 2007, Peter Verswyvelen wrote: > >> Ah, thanks for the correction. So if I understand it correctly, this is currying: > >See also: > http://haskell.org/haskellwiki/Currying > http://haskell.org/haskellwiki/Partial_application > >and more generally: > http://haskell.org/haskellwiki/Category:Glossary > >

3 4

Before
by Andrew Coppin 03 Jul '07

03 Jul '07

What were monads like before they became a Haskell language construct? Is Haskell's idea of a "monad" actually anywhere close to the original mathematical formalism? Just being randomly curiose...

4 7

Re: [Haskell-cafe] Haskell's
by Peter Verswyvelen 03 Jul '07

03 Jul '07

Ah, thanks for the correction. So if I understand it correctly, this is currying: when f :: (a,b) -> c then g :: a -> (b,c) is the curried form of f? So currying has to do with tuples? And partial application is just leaving away some tail arguments? >----- Oorspronkelijk bericht ----- >Van: Jules Bean [mailto:jules@jellybean.co.uk] >Verzonden: dinsdag, juli 3, 2007 12:19 PM >Aan: 'peterv' >CC: Haskell-Cafe(a)haskell.org >Onderwerp: Re: [Haskell-cafe] Haskell's "partial application" (not currying!) versus Business Objects Gem Cutter's "burning" > >peterv wrote: >> In Haskell, currying can only be done on the last (rightmost) function >> arguments. > > >You are talking about partial application, not currying. > >> foo x y >> >> can be curried as >> >> foo x >> >> but not as >> >> foo ? y >> >> where ? would be a “wilcard” for the x parameter. > >(\x -> foo x y) > >[snip] > >> This burning looks more general to me, but cannot be done using the >> textual approach? > >Well, it can be done, but basically there are two issues: > >1. You need to demarquate the 'scope' of the ?. What 'lump' of >expression is the partially evaluated part. An obvious way to do this is >with parentheses, but you have to be careful. > >2. If you have more than one ?, you need to remember which is which. >Think of nested expressions, nested ?s. What if you want to use the >'same' ? more than once? > >The solution that haskell chooses to (2) is to 'label' the ?s with >names. The solution to (1) is to mark the scope with a \, and the list >of names bound: > >\x z -> foo (foo x y) z > >Jules > > > >

4 4

Re: [Haskell-cafe] Re: Parsers are monadic?
by Gregory Propf 03 Jul '07

03 Jul '07

Right, I read more about it and found this out. The 'main' function is apparently magical at runtime and allows you to break the with pure functionality just once but since it can call other functions this allows for useful programs to be written. ----- Original Message ---- From: Jules Bean <jules(a)jellybean.co.uk> To: Gregory Propf <gregorypropf(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Sent: Monday, July 2, 2007 1:40:09 AM Subject: Re: [Haskell-cafe] Re: Parsers are monadic? Gregory Propf wrote: > Thanks, that was helpful. I didn't realize that there were pure > functional monads. Actually, it's stronger than that. All monads are pure functional, even IO. Haskell is an entirely 100% pure functional language[*]. The IO monad allows you to build up, in a pure, referentially transparent way, an object call an 'IO action' which you have no way of actually executing, per se. Fortunately, this isn't as useless as it sounds since the runtime system contains the support to "actually run" the special IO action called 'main', which bootstraps the whole setup. Jules [*] non-functions like unsafePerformIO are not technically part of the haskell language! ____________________________________________________________________________________ Never miss an email again! Yahoo! Toolbar alerts you the instant new Mail arrives. http://tools.search.yahoo.com/toolbar/features/mail/

3 2

Re: [Haskell-cafe] Very simple parser
by Gregory Propf 02 Jul '07

02 Jul '07

OK, I get the reference to currying now. A function of 2 variables can be seen as a function of one that returns another function of one. So a function of one variable can be seen as a function of no variables that returns a function of one. Very nice. ----- Original Message ---- From: Tim Chevalier <catamorphism(a)gmail.com> To: Gregory Propf <gregorypropf(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Sent: Monday, July 2, 2007 5:37:41 PM Subject: Re: [Haskell-cafe] Very simple parser On 7/2/07, Gregory Propf <gregorypropf(a)yahoo.com> wrote: > > > > This was a bit baffling too. It appears that there's an implied argument to runTick. This also works and makes it more explicit. I suppose the compiler just works out that the only place to put the 'n' is after tick. > > runTick :: Int -> (String,Int) > runTick n = runState tick n > Not exactly. Look up "currying". (Writing out the same definition with the argument "n" specified explicitly like you did is called "eta-expansion", by the way.) Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "My writing is all completely autobiographical. That's why I write lesbian vampire stories." -- Jewelle Gomez ____________________________________________________________________________________ Got a little couch potato? Check out fun summer activities for kids. http://search.yahoo.com/search?fr=oni_on_mail&p=summer+activities+for+kids&…

1 0