Re: [Haskell-cafe] Ocaml for Haskellers tutorial
On Fri, Apr 16, 2010 at 8:35 PM, C K Kashyap ckkash...@gmail.com wrote: I am a little surprised by the shortcomings of Haskell mentioned in the thread. I was under the impression that Haskell was closest to Nirvana on the usefulness vs safety graph. In the paper Why FP matters - Laziness is stated as one of the two key features of FP that allows conceptual modularity! If I understand right, Laziness is not a first class stuff in OCaml - is that not right? That's right. You can simulate laziness in OCaml. OCaml compilers cannot assume code is pure and lazy so many very useful optimizations are not performed by the OCaml compiler. And some syntactic and stylist things are not available. See for example Ganesh's comment about combinators earlier in this thread. If I understand correctly - Not allowing side-effects allow for equational reasoning - which in turn allows you to reason about the program better. If I understand right - OCaml allows side effects right? Right. Jeff, could you please expand on the tail recursion bit - what do you mean when you say, in OCaml, one has to write tail recursively in OCaml? Tail recursive functions do not need to maintain a stack for their recursive calls and the optimizer may replace them with a loop. In strict functional languages such as OCaml this means that by writing your recursive functions to be tail recursive you won't run out of stack space. Many recursive functions can be transformed to be tail recursive by adding an accumulator argument and building up the return value there. In a lazy language if you write something to be tail recursive, then each time the function recurses it will add to the accumulator. Because it's tail recursive it typically also won't evaluate this accumulator. This means that in memory you have to build up the unevaluated representation, or thunk. This thunk keeps getting bigger and bigger until something demands the value. This means that if you need to write a recursive function in haskell which has an accumulator, you often want to make the function strict in the accumulator. Meaning the strict function will evaluate the accumulator as it goes. One place where lazy accumulators is bad are the left folds. There is the lazy foldl and the version which is strict in the accumulator, foldl'. Try summing big lists of integers, let's use ghci and limit the heap to 1 meg: ghci +RTS -M1M Prelude foldl (+) 0 [1..1000] Heap exhausted; Current maximum heap size is 6291456 bytes (6 MB); use `+RTS -Msize' to increase it. ghci +RTS -M1M Prelude :m + Data.List Prelude Data.List foldl' (+) 0 [1..1000] 500500 Haskell lets us choose the evaluation strategy here. After programming in both Haskell and Common Lisp for several years each I can tell you that Haskell's way of dealing with evaluation strategies and letting the user pick the desired one is easier to manage and deal with. I would expect OCaml less nice than Haskell here as well. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ocaml for Haskellers tutorial
On Sat, Apr 17, 2010 at 8:22 AM, Jason Dagit da...@codersbase.com wrote:
...
One place where lazy accumulators is bad are the left folds. There is the
lazy foldl and the version which is strict in the accumulator, foldl'. Try
summing big lists of integers, let's use ghci and limit the heap to 1 meg:
ghci +RTS -M1M
Prelude foldl (+) 0 [1..1000]
Heap exhausted;
Current maximum heap size is 6291456 bytes (6 MB);
use `+RTS -Msize' to increase it.
If we define foldl as:
foldl :: (b - a - b) - b - [a] - b
foldl f z [] = z
foldl f z (x:xs) = let z' = f z x
in foldl f z' xs
and:
sum :: [Int] - Int
sum = foldl (+) 0
Then the program: 'sum 100' will indeed use a lot of heap space
(and will run out of it if you limit the heap to 1MB). The reason for
this is explained in [1]. In short: foldl will start allocating thunks
on your heap which each add an element of the list to a previous thunk
as in:
let z1 = 0 + 1
z2 = z1 + 2
z3 = z2 + 3
z4 = z3 + 4
...
z97 = z96 + 97
z98 = z97 + 98
z99 = z98 + 99
z10 = z99 + 100
in z100
This can be visualized if we generate a heap profile:
$ ghc --make FoldlProfile.hs -o foldlProfile -O2 -prof
$ ./foldlProfile 100 +RTS -hy
Stack space overflow: current size 8388608 bytes.
$ hp2ps -c foldlProfile.hp
$ ps2pdf foldlProfile.ps
Result: http://bifunctor.homelinux.net/~bas/foldlProfile.pdf
You clearly see that this program allocates well over 22MB of heap
space! This is not a problem if you can give the program a big enough
heap. However have you noticed the more serious problem?
The problem starts when we finally evaluate z100:
Note that z100 = z99 + 100. So 100 is pushed on the
stack. Then z99 is evaluated.
Note that z99 = z98 + 99. So 99 is pushed on the
stack. Then z98 is evaluated:
Note that z98 = z97 + 98. So 98 is pushed on the
stack. Then z97 is evaluated: So ...
...your limited stack will eventually run full when you evaluate a
large enough chain of (+)s. This then triggers a stack overflow
exception!
Interestingly, when we define foldl as:
foldl :: (b - a - b) - b - [a] - b
foldl f = foldl_f
where
foldl_f z [] = z
foldl_f z (x:xs) = let z' = f z x
in foldl_f z' xs
then both the heap and stack overflow problems go away.
(this is how foldl is actually implemented[2] in GHC)
I don't know why the heap and stack overflow problems go away. So lets
look at the core output of the latter program:
$ ghc-core -- -O2 FoldlProfile.hs
$wsum :: [Int] - Int#
$wsum = \ (w_s1rS :: [Int]) - $wfoldl_f 0 w_s1rS
$wfoldl_f :: Int# - [Int] - Int#
$wfoldl_f =
\ (ww_s1rK :: Int#) (w_s1rM :: [Int]) -
case w_s1rM of _ {
[] - ww_s1rK;
: x_aeb xs_aec -
case x_aeb of _ { I# y_aUb -
$wfoldl_f (+# ww_s1rK y_aUb) xs_aec
}
}
Apparently, because of the latter foldl definition, GHC is able to
optimize the foldl for uboxed ints.
But why doesn't the recursive call:
$wfoldl_f (+# ww_s1rK y_aUb) xs_aec
allocate (+# ww_s1rK y_aUb) on the heap? Are unboxed values always
evaluated strictly?
For reference, this is the core output of the former foldl:
sum :: [Int] - Int
sum = foldl @ Int @ Int plusInt main3
main3 = I# 0
foldl :: forall b_aer a_aes.
(b_aer - a_aes - b_aer) - b_aer - [a_aes] - b_aer
foldl =
\ (@ b_afF)
(@ a_afG)
(f_aet :: b_afF - a_afG - b_afF)
(z_aeu :: b_afF)
(ds_drS :: [a_afG]) -
case ds_drS of _ {
[] - z_aeu;
: x_aex xs_aey -
foldl @ b_afF @ a_afG f_aet (f_aet z_aeu x_aex) xs_aey
}
regards,
Bas
[1] http://haskell.org/haskellwiki/Foldr_Foldl_Foldl'
[2]
http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/src/GHC-List.html#foldl
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ocaml for Haskellers tutorial
Bas van Dijk schrieb:
I don't know why the heap and stack overflow problems go away. So lets
look at the core output of the latter program:
$ ghc-core -- -O2 FoldlProfile.hs
$wsum :: [Int] - Int#
$wsum = \ (w_s1rS :: [Int]) - $wfoldl_f 0 w_s1rS
$wfoldl_f :: Int# - [Int] - Int#
$wfoldl_f =
\ (ww_s1rK :: Int#) (w_s1rM :: [Int]) -
case w_s1rM of _ {
[] - ww_s1rK;
: x_aeb xs_aec -
case x_aeb of _ { I# y_aUb -
$wfoldl_f (+# ww_s1rK y_aUb) xs_aec
}
}
Apparently, because of the latter foldl definition, GHC is able to
optimize the foldl for uboxed ints.
But why doesn't the recursive call:
$wfoldl_f (+# ww_s1rK y_aUb) xs_aec
allocate (+# ww_s1rK y_aUb) on the heap? Are unboxed values always
evaluated strictly?
I think so.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ocaml for Haskellers tutorial
Hi Ocaml's a fine alternative to Haskell, you could be 'forced' to use say PHP, now that wouldn't be quite so nice... For instance, I have heard that Ocaml is only fast when one uses loops instead of folds, but I wonder if this is an overstatement. Maybe this notion is from the standard library not being optimized for long lists? http://ocaml.janestreet.com/?q=node/71 http://groups.google.com/group/fa.caml/msg/01e80aadf16837d6 There isn't much on performance in the O'Reilly book, but otherwise it is pretty comprehensive: http://caml.inria.fr/pub/docs/oreilly-book/ I suspect the difference between the ML module system vs. typeclasses will be as important as lazy vs. strict. As a style point, Ocaml programmers don't seem too prone to combinator mania - so I think golf is a bit less popular over there. One tip - sometimes you might see Ocaml code with the revised syntax (particularly Gerard Huet's work, which whilst described as 'Pidgin ML' is a subset of the Caml revised syntax) - this can be translated automatically to regular syntax with camlp4. Not knowing this tripped me up for a couple of days at the end of last year. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Ocaml for Haskellers tutorial
Stephen Tetley wrote: I suspect the difference between the ML module system vs. typeclasses will be as important as lazy vs. strict. As a style point, Ocaml programmers don't seem too prone to combinator mania - so I think golf is a bit less popular over there. Both the lack of laziness and the value restriction can sometimes force combinator definitions to be eta-expanded, which I think makes this style of programming much less attractive. Cheers, Ganesh === Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html === ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ocaml for Haskellers tutorial
forced to switch to Ocaml That like saying that you broke up with Miss America and started going out with the runner-up. Sucks to be you :) I experimented with Ocaml for a little while and among other things I found that technology stack that comes with GHC (compared to Ocaml) is quite a bit nicer. It is much easier to deploy/install apps and dependencies. And on the whole libraries seem to be a lot more mature on the Haskell side. Lazy/strict, modules/typeclasses aside this made a big difference to me. -deech ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ocaml for Haskellers tutorial
Hello, One major thing I haven't seen explicitly mentioned yet in this thread is tail recursion. You have to write tail recursively in OCaml (or any strict language) or you will blow the stack. While tail recursion is often wrong (in terms of efficiency) in Haskell, it is always right in OCaml. -Jeff ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ocaml for Haskellers tutorial
I am a little surprised by the shortcomings of Haskell mentioned in the thread. I was under the impression that Haskell was closest to Nirvana on the usefulness vs safety graph. In the paper Why FP matters - Laziness is stated as one of the two key features of FP that allows conceptual modularity! If I understand right, Laziness is not a first class stuff in OCaml - is that not right? If I understand correctly - Not allowing side-effects allow for equational reasoning - which in turn allows you to reason about the program better. If I understand right - OCaml allows side effects right? Jeff, could you please expand on the tail recursion bit - what do you mean when you say, in OCaml, one has to write tail recursively in OCaml? Please note, I am still a Haskell (FP) learner - My questions above are only meant for me to understand things better. Regards, Kashyap On Sat, Apr 17, 2010 at 7:12 AM, jeff p mutj...@gmail.com wrote: Hello, One major thing I haven't seen explicitly mentioned yet in this thread is tail recursion. You have to write tail recursively in OCaml (or any strict language) or you will blow the stack. While tail recursion is often wrong (in terms of efficiency) in Haskell, it is always right in OCaml. -Jeff ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
