Isn't this tail recursive?
For practice, I'm playing with reimplementing the solution to the word count problem on the Great Computer Language Shootout (www.bagley.org/~doug/shootout). My current solution looks tail recursive to me: --- snip --- -- wc-luke.hs -- Reimplimentation of the Haskell word count program for the Great -- Computer Language Shootout -- Luke Maurer -- jyrinx@mindspring.com module Main where import IO data CharKind = Normal | White | Newline charKind :: Char -> CharKind charKind c = case c of '\n' -> Newline ' ' -> White '\t' -> White _ -> Normal countAll :: String -> (Int, Int, Int) countAll str = countAll' str 0 0 0 0 where countAll' [] _ nl nw nc = (nl, nw, nc) countAll' (c:cs) newWord nl nw nc = case charKind c of -- The following should all be tail calls ... right? Normal -> countAll' cs 0 nl (nw + newWord) (nc + 1) White -> countAll' cs 1 nl nw (nc + 1) Newline -> countAll' cs 1 (nl + 1) nw (nc + 1) main = do -- We need a 4K buffer, as per the rules hSetBuffering stdin (BlockBuffering (Just 4096)) file <- getContents let (l, w, c) = countAll file putStrLn ((show l) ++ " " ++ (show w) ++ " " ++ (show c)) --- snip --- In the case expression at the end of countAll, each of the values looks to me like a recursive tail call - I should think (hope?) that it would be optimized by GHC into a goto statement (a la Scheme). Instead, my program eats up memory (I've got 256 MB) until the RTS whines about a stack overflow. Am I wrong about the tail call? Is there some optimization I should be aware of (I'm compiling with -O2)? Is this a flaw in GHC? (BTW, as a beginner, I'd be glad to hear general commentary on my code ...) Thanks! Jyrinx jyrinx_list at mindspring dot com
I don't think it's an issue of it being a tail call; i think it's just too lazy.
Normal -> countAll' cs 0 nl (nw + newWord) (nc + 1) White -> countAll' cs 1 nl nw (nc + 1) Newline -> countAll' cs 1 (nl + 1) nw (nc + 1)
make this something like ... Normal -> nw' `seq` nc' `seq` countAll' cs 0 nl nw' nc' White -> nc' `seq` countAll' cs 1 nl nw nc' Newline-> nl' `seq` nc` `seq` countAll' cs 1 nl' nw nc' where nw' = nw + newWord nc' = nc + 1 nl' = nl + 1 ... or something. I'm not entirely sure but it's worth a shot. - Hal
Normal -> countAll' cs 0 nl (nw + newWord) (nc + 1) White -> countAll' cs 1 nl nw (nc + 1) Newline -> countAll' cs 1 (nl + 1) nw (nc + 1)
make this something like
...
Normal -> nw' `seq` nc' `seq` countAll' cs 0 nl nw' nc' White -> nc' `seq` countAll' cs 1 nl nw nc' Newline-> nl' `seq` nc` `seq` countAll' cs 1 nl' nw nc' where nw' = nw + newWord nc' = nc + 1 nl' = nl + 1
Cool! That did the trick ... (runs on very little memory *and* time now ... very cool) I've read through the other responses (thanks all!), and I'm still not exactly sure what's going on ... I'm relatively new to Haskell, and my understanding of laziness is hardly rigorous; in general, how should I know where I need to use seq, and what I need to use it on? Is there a paper I should read? (I've got Hudak's book, but it does everything lazily IIRC) Jyrinx jyrinx_list@mindspring.com
Here's the basic idea. Suppose we have the function:
sum [] acc = acc sum (x:xs) acc = sum xs (acc+x)
This is tail recursive, but not strict in the accumulator argument. What this means is that the computation will be performed lazily, so sum [4,5,8,10,14,20] 0 will go like this:
sum [4,5,8,10,14,20] 0 = sum [5,8,10,14,20] (0+4) = sum [8,10,14,20] ((0+4)+5) = sum [10,14,20] (((0+4)+5)+8) = sum [14,20] ((((0+4)+5)+8)+10) = sum [20] (((((0+4)+5)+8)+10)+14) = sum [] ((((((0+4)+5)+8)+10)+14)+20) = ((((((0+4)+5)+8)+10)+14)+20)
this computation in the accumulator argument won't be evaluated until you try to print it or something, which will reduce it and perform the computation. this means that for a list of length n, the the sum computation will grow in size O(n). what you need is to make sure that the computation is done strictly and that is done using seq or $!, as in:
sum2 [] acc = acc sum2 (x:xs) acc = sum2 xs $! (acc+x)
this means that "acc+x" will be computed at each step, so the accumulator will hold only the integer (or whatever type) and not the thunk (the computation). the type of "$!" is the same as "$":
$! :: (a -> b) -> a -> b
the sematics of $! are:
f $! a = f a
but the difference is that $! causes "a" to be reduced completely, so it won't build a huge thunk. at least that's my understanding; i'm willing to be corrected :) - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On 11 Mar 2002, Jyrinx wrote:
Normal -> countAll' cs 0 nl (nw + newWord) (nc + 1) White -> countAll' cs 1 nl nw (nc + 1) Newline -> countAll' cs 1 (nl + 1) nw (nc + 1)
make this something like
...
Normal -> nw' `seq` nc' `seq` countAll' cs 0 nl nw' nc' White -> nc' `seq` countAll' cs 1 nl nw nc' Newline-> nl' `seq` nc` `seq` countAll' cs 1 nl' nw nc' where nw' = nw + newWord nc' = nc + 1 nl' = nl + 1
Cool! That did the trick ... (runs on very little memory *and* time now ... very cool) I've read through the other responses (thanks all!), and I'm still not exactly sure what's going on ... I'm relatively new to Haskell, and my understanding of laziness is hardly rigorous; in general, how should I know where I need to use seq, and what I need to use it on? Is there a paper I should read? (I've got Hudak's book, but it does everything lazily IIRC)
Jyrinx jyrinx_list@mindspring.com
Oops, I made a false statement:
f $! a = f a
but the difference is that $! causes "a" to be reduced completely, so it won't build a huge thunk.
This isn't true. $! will only perform one reduction, so for instance:
id $! (a+1,b+1)
will not cause a+1 and b+1 to be calculated; it will only perform the computation which creates the tuple. similarly,
id $! [a+5]
will not cause a+5 to be calculated, it will only result in the list being created (i.e., reduced from a computation which will compute [a+5] to simply the value [a+5]). if you want what i was talking about, use the DeepSeq module (http://www.isi.edu/~hdaume/haskell/Util/DeepSeq.hs) and then you can write:
id $!! [a+5]
which will actually perform the calculation. - Hal
On Tue, 12 Mar 2002, Hal Daume III wrote:
Here's the basic idea. Suppose we have the function:
sum [] acc = acc sum (x:xs) acc = sum xs (acc+x)
This is tail recursive, but not strict in the accumulator argument. What this means is that the computation will be performed lazily, so sum [4,5,8,10,14,20] 0 will go like this:
sum [4,5,8,10,14,20] 0 = sum [5,8,10,14,20] (0+4) = sum [8,10,14,20] ((0+4)+5) = sum [10,14,20] (((0+4)+5)+8) = sum [14,20] ((((0+4)+5)+8)+10) = sum [20] (((((0+4)+5)+8)+10)+14) = sum [] ((((((0+4)+5)+8)+10)+14)+20) = ((((((0+4)+5)+8)+10)+14)+20)
this computation in the accumulator argument won't be evaluated until you try to print it or something, which will reduce it and perform the computation. this means that for a list of length n, the the sum computation will grow in size O(n). what you need is to make sure that the computation is done strictly and that is done using seq or $!, as in:
sum2 [] acc = acc sum2 (x:xs) acc = sum2 xs $! (acc+x)
this means that "acc+x" will be computed at each step, so the accumulator will hold only the integer (or whatever type) and not the thunk (the computation).
the type of "$!" is the same as "$":
$! :: (a -> b) -> a -> b
the sematics of $! are:
f $! a = f a
but the difference is that $! causes "a" to be reduced completely, so it won't build a huge thunk.
I hate to say it, but my understanding of it is that it isnt so simple (which could be good or bad depending upon your view). I guess he best i can describe it is that it will force a to weak head normal form (which is the same as being reduced completely for expressions with only integers, or whatever...) For instance, forcing x=(map f) $! [1..] will essentially force [1.. to (1: (thunk generating [2..]) just before the (map f) is applied. I think. Ok maybe that was a bad example but I can't really think of a good one right now. You might add something that it isn't the (+) operator thats generating the thunks. It is the fact (and only this!) that (+) isn't being forced. I always got confused how (+) could be strict in both arguments, at least for the primitives Float, Integer, and the like, yet still apparently generate a bunch of thunks, like in your expression ((((((0+4)+5)+8)+10)+14)+20). Appearances can be deceiving. But, once that outermost expression is forced, the forcing moves down toward the innermost expression and then the whole expression implodes into a value. I guess the confusion was I somehow conjectured that the application of a strict function to a value would cause haskell to apply that function strictly, when in fact it should not and does not and I was plainly wrong. Here is a short "proof" bottom::[Int] bottom=bottom --bottom = _|_ y = const 3 -- const v = \x -> v main=print (y (head bottom)) If my conjecture was right, main would not terminate. (head is a strict function being applied to _|_ ). However we know that since y = \x -> 3, y will not force x, therefore main will print 3. However... all one needs to do is to change the above to. main=print (y $! (head bottom)) _|_ should be, propagated to main by the following deductions: head _|_ = _|_, y $! _|_ = _|_, print _|_ = _|_. thus main = _|_. Ooh, interesting. I tried that in ghc 5.00 and in fact ghc is smart enough to detect bottom here! It says
[jay@localhost haskell]$ ./a.out
Fail: <<loop>>
awesome! I feel like I am rambling to no end. alright. I hope I haven't been too confusing here. All in all I do like your explanation though. Oh, and after I went to the trouble to write this, I see that you did correct yourself. All my work all for naught! Maybe somebody will get something from my ramblings. Thanks, Jay Cox
Aha! Gotcha. Thanks for the explanation. I suppose that, in general, for tail recursion to work right, the accumulator has to be evaluated strictly (as is how my code was fixed)? Jyrinx jyrinx_list@mindspring.com On Tue, 2002-03-12 at 09:34, Hal Daume III wrote:
Here's the basic idea. Suppose we have the function:
sum [] acc = acc sum (x:xs) acc = sum xs (acc+x)
This is tail recursive, but not strict in the accumulator argument. What this means is that the computation will be performed lazily, so sum [4,5,8,10,14,20] 0 will go like this:
sum [4,5,8,10,14,20] 0 = sum [5,8,10,14,20] (0+4) = sum [8,10,14,20] ((0+4)+5) = sum [10,14,20] (((0+4)+5)+8) = sum [14,20] ((((0+4)+5)+8)+10) = sum [20] (((((0+4)+5)+8)+10)+14) = sum [] ((((((0+4)+5)+8)+10)+14)+20) = ((((((0+4)+5)+8)+10)+14)+20)
this computation in the accumulator argument won't be evaluated until you try to print it or something, which will reduce it and perform the computation. this means that for a list of length n, the the sum computation will grow in size O(n). what you need is to make sure that the computation is done strictly and that is done using seq or $!, as in:
sum2 [] acc = acc sum2 (x:xs) acc = sum2 xs $! (acc+x)
this means that "acc+x" will be computed at each step, so the accumulator will hold only the integer (or whatever type) and not the thunk (the computation).
the type of "$!" is the same as "$":
$! :: (a -> b) -> a -> b
the sematics of $! are:
f $! a = f a
but the difference is that $! causes "a" to be reduced completely, so it won't build a huge thunk.
at least that's my understanding; i'm willing to be corrected :)
- Hal
-- Hal Daume III
"Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
On 11 Mar 2002, Jyrinx wrote:
Normal -> countAll' cs 0 nl (nw + newWord) (nc + 1) White -> countAll' cs 1 nl nw (nc + 1) Newline -> countAll' cs 1 (nl + 1) nw (nc + 1)
make this something like
...
Normal -> nw' `seq` nc' `seq` countAll' cs 0 nl nw' nc' White -> nc' `seq` countAll' cs 1 nl nw nc' Newline-> nl' `seq` nc` `seq` countAll' cs 1 nl' nw nc' where nw' = nw + newWord nc' = nc + 1 nl' = nl + 1
Cool! That did the trick ... (runs on very little memory *and* time now ... very cool) I've read through the other responses (thanks all!), and I'm still not exactly sure what's going on ... I'm relatively new to Haskell, and my understanding of laziness is hardly rigorous; in general, how should I know where I need to use seq, and what I need to use it on? Is there a paper I should read? (I've got Hudak's book, but it does everything lazily IIRC)
Jyrinx jyrinx_list@mindspring.com
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Hal Daume III:
Here's the basic idea. Suppose we have the function:
sum [] acc = acc sum (x:xs) acc = sum xs (acc+x)
This is tail recursive, but not strict in the accumulator argument. ...
Just a nitpick here. sum is indeed strict in its second argument (given that (+) is strict in its first argument). That is, sum l _|_ = _|_ for all possible lists l. It is of course possible that the compiler you use does not detect this and generates nonstrict code. But I think a decent strictness analyzer should detect this. Can the problem be that + is overloaded in Haskell, so the compiler cannot assume any semantical properties like strictness for it? Björn Lisper
On Wed, 13 Mar 2002, Bjorn Lisper wrote:
Hal Daume III:
Here's the basic idea. Suppose we have the function:
sum [] acc = acc sum (x:xs) acc = sum xs (acc+x)
This is tail recursive, but not strict in the accumulator argument. ...
Just a nitpick here. sum is indeed strict in its second argument (given that (+) is strict in its first argument). That is, sum l _|_ = _|_ for all possible lists l.
Do you really know that? all you know is (+):: Num a => a -> a -> a therefore sum :: Num a => [a] -> a -> a now, for any conceivable sum, you generally need both arguments to compute it (or am I wrong?), so i guess you could say (+) should probably be strict for both arguments. But how would you tell the compiler that? oh wait. . o O 0 church numerals... peano numerals.... data Peano = Zero | Succ (Peano) sumpeano blah (Succ x) = sumpeano (Succ blah) x sumpeano blah Zero = blah sumpeano not strict on first argument. define instance Num for Peano. I dont even know if you could talk about strictness in either argument with church numerals. (and I'm to lazy to remind myself what a church numeral looks like precisely so that I could find out.) Perhaps what could be done about this strictness business is to make a kind of strictness annotation. Perhaps something that says (force the second argument of function F before every call to F (including any time F calls itself)). Then perhaps one could define a strict_foldl = foldl but the strictness annotations basically "inserts" the proper seq expression or $! into the redefinition of foldl. here's a rough example. !a mean !a will be forced at its application (for not knowing proper language to call it). strict_foldl :: (a -> b -> a) -> !a -> [b] -> a strict_foldl = foldl of course, there has to be a number of things that must be propagated whence you start adding these things. like for instance. if f:: !a ->b ->c f x y = .... then (flip f) should have type b ->!a ->c and then there might be times when you want to ah, lazify, a strict function. maybe that would be taken care of by giving the type without the strictness annotation (explicitly giving the type but removing all "!") How about it? Has there been any other proposals? (like maybe going as far as a "Strictness Type" system?) Thanks, Jay Cox P.S. I do wonder if my message will even get to Björn Lisper. His mailserver apparently dumps anything sent with a yahoo.com in the From: header. (and unfortunately given how much spam comes from yahoo I can see why).
[Jay Cox <sqrtofone@yahoo.com>]
(+):: Num a => a -> a -> a therefore sum :: Num a => [a] -> a -> a now, for any conceivable sum, you generally need both arguments to compute it (or am I wrong?), so i guess you could say (+) should probably be strict for both arguments. But how would you tell the compiler that?
oh wait. . o O 0 church numerals... peano numerals....
data Peano = Zero | Succ (Peano)
sumpeano blah (Succ x) = sumpeano (Succ blah) x sumpeano blah Zero = blah
sumpeano not strict on first argument. define instance Num for Peano.
I dont even know if you could talk about strictness in either argument with church numerals. (and I'm to lazy to remind myself what a church numeral looks like precisely so that I could find out.)
i suppose this is getting a bit off-topic, but for any instance of Num with an additive identity, (+) probably doesn't need to be strict for both arguments, right? consider: sum 0 x = x sum x y = x + y if the first argument is 0, we don't need to inspect the second argument at all. if i'm correct, this just reinforces your point... m -- matt hellige matt@immute.net http://matt.immute.net
matt hellige writes (to the haskell mailing list):
[..] consider: sum 0 x = x sum x y = x + y
if the first argument is 0, we don't need to inspect the second argument at all.
But sum returns its second argument, so it's still strict in that argument. Cheers, Ronny Wichers Schreur
Alright. I know the haskell community probably gets tired of my long winded posts. I This post probably shouldn't even be on haskell@haskell.org (more like on haskell-cafe). I also realize that these posts may not mean much to you; many of you may have figured out most of this strictness business long, long ago and you are long bored of me. But I do feel strictness misconceptions and such are a potentially big problem with using haskell. I even at one time decided haskell might not be worth learning (more) about because it seemed like it might be too hard to analyze memory usesage and the like to create efficient programs. I think I may eventually attempt to write a haskell lazyness/strictness FAQ. I feel a bit underqualified for the job, so I'm probably going to need help in verification of what I may say in it. If anything, I hope for some help so that i will not embarass the haskell community! Or, at the very least, I may eventially add something to the haskell wiki. I'm not sure which. Any critique is welcome. On Fri, 15 Mar 2002, Ronny Wichers Schreur wrote:
matt hellige writes (to the haskell mailing list):
[..] consider: sum 0 x = x sum x y = x + y
if the first argument is 0, we don't need to inspect the second argument at all.
But sum returns its second argument, so it's still strict in that argument.
Oh boy. You are right. sum 0 _|_ = _|_, since obviously x = x. but what about sum x _|_? assuming (+) for integers, (+) is strict on both arguments. thus sum x _|_ = x + _|_ = _|_ Thus that definition of sum is strict on both arguments. (Apologies to Matt Hellige for incorrect analysis in private message). That also means my sumpeano isn't just strict on the second argument. data Peano = Zero | Succ (Peano) sumpeano blah (Succ x) = sumpeano (Succ blah) x sumpeano blah Zero = blah If the initial second argument of sumpeano is Zero, then sumpeano IS strict on the second argument, by the same reasoning above. But if it is not, then sumpeano _|_ (Succ x) = sumpeano (Succ _|_) x. When sumpeano finally reaches Zero in the second argument (for a initial non-Zero argument) the result will be a cascade of Succ applications like (Succ.) (Succ.) (Succ.) (Succ.) _|_ which, well, is not equivalent to _|_ (nor will it be unless all applications have been forced.. Therefore sumpeano is, CONDITIONALLY strict in the first argument! (The reader may wonder why I chose the "(Succ.)" notation. I wanted to give pause to the fact that sumpeano is generating Succ "thunks" which will generate Succ (Succ (Succ ...))) etc, and not the actual structure. perhaps I'm trying to be overly accurate for this argument.) In all the literature I've read (which, by the way, is not much) I've never seen such a phrase as conditionaly strict or conditionally lazy. Is such a conseption as being conditionally strict or conditionally lazy fairly useful? Or is this where the phrase "non-strict" comes in? Hmmm, redefining sumpeano in terms of functions of 1 argument, (and switching around the arguments around for the sake of argument) May also give some insight. Either (sumpeano z) is a strict function, or, it isn't. sumpeano' Zero = id -- id _|_ = _|_ sumpeano' (Succ x) = \blah -> (sumpeano' x) (Succ blah) Yet of course there are functions in common use which one could say have arguments which are fully lazy. take the definiton of map. map f [] = [] map f (x:xs) = f x : map f xs f can be bottom easily. take length $ map _|_ [1..5] for example. (for your pretend bottom, you could use error, as in bottom = error "I'm _|_!") This is quite intriguing. I've learned something today. I hope my post proves usefull to somebody else.
Cheers,
Ronny Wichers Schreur
Thanks, Jay Cox
On 10 Mar 2002, Jyrinx wrote:
In the case expression at the end of countAll, each of the values looks to me like a recursive tail call - I should think (hope?) that it would be optimized by GHC into a goto statement (a la Scheme). Instead, my program eats up memory (I've got 256 MB) until the RTS whines about a stack overflow.
It is tail recusive. unfortunately, that's not the problem. apparently ghc is not smart enough to realize that countAll' should really be strict in basically all arguments. (hell, I'm not quite sure I can claim to be smart enough to say that!) One way you could fix it up would be to do as Hal did and sprinkle seq and/or $! throughout your code. That would have been my solution as well, but I then realized this happens just too often to have been ignored by the haskell literati. I decided to muck around in the haskell manual and I think I may have found another way. Never fear, -fall-strict is here! Anyway compiling with that ghc option seams to make the problem go away. I just ran your code compiled with it over a 47M file and the heap size hits a max of 16 and stays constant throughout execution. I wish I knew more about what -fall-strict really means. The ghc 5.00 manual hardly explains it. It doesn't have the semantics I would have thought it should have. for instance: main = print foo where foo = let a = error "do I happen?" b = 3 in "foo" ++ show b I would have thought that the execution of that code compiled with the all-strict flag would have raised the error. a strict language would do that, right? Perhaps it is something to do purely with function application. I dont know. Anyway, I guess a fix would be to put in a pragma into your code to quote Malcolm Wallace <Malcolm.Wallace@cs.york.ac.uk>
ghc and nhc98 already support this. ghc's mechanism is {-# OPTIONS -fglasgow-exts ... etc #-} at the top of the file - but there are quite a few restrictions on what flags are accepted in that pragma. nhc98's mechanism is {-# OPTIONS_COMPILE -nkpat ... etc #-} anywhere in the file, which has no restrictions on the options it accepts - you can use anything that can appear on the commandline.
o just maybe you could exchange -fall-strict for -fglasgow-exts and pray to the haskell gods that it happens to be an acceptable option? Jay Cox
Another way to evaluate the accumulating counts in each call is to combine them in a data type and use strictness flags for the individual count fields. (See <http://www.haskell.org/onlinereport/decls.html#sect4.2.1>, "Strictness Flags") For example (untested): data Counts = Counts !Int !Int !Int countAll :: String -> Counts countAll str = countAll' str 0 (Counts 0 0 0) // shouldn't this be 1 (start with new word)? where countAll' [] _ counts = counts countAll' (c:cs) newWord (Counts nl nw nc) = case charKind c of Normal -> countAll' cs 0 (Counts nl (nw+newWord) (nc+1)) White -> countAll' cs 1 (Counts nl nw (nc+1)) Newline -> countAll' cs 1 (Counts (nl+1) nw (nc+1)) The function countAll' is now strict in its counts argument. Because of the strictness flags in Counts, each count is evaluated. I think this looks nicer than using local calls to `seq`. Cheers, Ronny Wichers Schreur
participants (7)
-
Bjorn Lisper -
Hal Daume III -
Jay Cox -
Jyrinx -
matt hellige -
Ronny Wichers Schreur -
Wolfgang Jeltsch