Discussion:
how is Haskell not robust?
(too old to reply)
raould
2009-05-27 00:34:01 UTC
Permalink
cf. thread in which i take it Haskell is described as being perhaps
not something you want to use in production. (http://groups.google.com/
group/comp.lang.functional/msg/2e3da091a4f912dd)

why is that? because laziness might rear its ugly performance head
unexpectedly at some arbitrary time after making the code live? or
some other reason(s) e.g. it just hasn't been stress tested in the
real world enough, so there are probably dangerous bugs in the
runtime?

thanks.
Adrian Hey
2009-05-27 08:26:41 UTC
Permalink
Hello Raould,
Post by raould
cf. thread in which i take it Haskell is described as being perhaps
not something you want to use in production. (http://groups.google.com/
group/comp.lang.functional/msg/2e3da091a4f912dd)
why is that? because laziness might rear its ugly performance head
unexpectedly at some arbitrary time after making the code live? or
some other reason(s)
From a reliability POV, any program that makes use of dynamic memory
allocation should be viewed with suspicion (whether or not it uses
automatic garbage collection). But the problem is far worse with lazy
languages than with strict languages IMO. People naturally reason about
values and in a strict language you can rely on the basic intuition that
"big values" use a lot of memory and "little values" don't use much
memory. With lazy evaluatuation this intuition is useless (even a simple
counter can be the source of a serious space leak if you're not
careful).

The standard advice is that all these problems re. space behaviour
should be investigated and fixed using profiling. Personally I think
it's rather unsatisfactory to rely on empirical (and hence unreliable)
testing for this important property of programs. It doesn't seem like
a good solution, considering Haskellers generally seek static guarantees
of correctness.

But even having identified a space leak, my problems don't end there.
I have to fix it, often by changing strictness properties of some
function somewhere. Haskell provides no modular way to do this, so
if I need more strictness in some code that I don't "own" (someone
elses library say) what do I do? Fork the library? Beg the maintainer
for a special just for me?

As a library author I have in the past tried to anticipate such problems
and provide users with multiple versions of essentially the same
function that differ only slightly in strictness properties. This is
quite tiresome, results in API bloat and is also contrary the DRY
principle. I seem to be in a minority by doing this though. AFAICT most
other Haskell lib implementors value simplicity and "elegance" most of
all and give little or no thought to strictness control.

But my problems still aren't over. Even having a identified *and* fixed
my space leaks, because none of the analyses and optimisations used are
standardised I still have no guarantee that the same program will give
acceptable space behaviour with a different compiler, or even different
versions of the same compiler, or even different optimisation settings
for the same compiler version.

I don't want to sound like I'm too down on Haskell as I know these are
very difficult research problems and the Haskell compiler folks have
limited resources at their disposal. Just think folk should be aware of
the downside of current state of the art if they're serious about
reliability.

Hume looks looks like a serious attempt to address the reliability
issues..
http://www-fp.cs.st-andrews.ac.uk/hume/index.shtml
http://www.embounded.org/

David Turners work on total functional progamming also interests me
a lot.
Post by raould
e.g. it just hasn't been stress tested in the
real world enough, so there are probably dangerous bugs in the
runtime?
Well if we're talking about ghc compiler specifically (rather than
the Haskell language) then there certainly have been bugs in it in the
past and no doubt there will be in future. Also ghc's stack management
is currently somewhat less than ideal IMO ..

http://hackage.haskell.org/trac/ghc/ticket/2090

This has some unfortunate consequences practice, such as the famed
"light weight" threads might in reality not be nearly as light weight as
advertised. You also sometimes have to adopt a less efficient and more
awkward continuation passing coding style to keep stack use small (or
just live dangerously and deal with stack "overflow" when and if it
occurs). Of course this isn't all you need to do to avoid stack
overflows. You need to ensure you don't end up building deep unevaluated
"strict thunk chains" too for example (which is often easier said than
done for reasons indicated above).

Regards
--
Adrian Hey
raould
2009-05-29 00:03:30 UTC
Permalink
Post by Adrian Hey
Hume looks looks like a serious attempt to address the reliability
issues..
also, i hope DDC continues on to be something of an in-production-
viable system.
http://www.haskell.org/haskellwiki/DDC

as an aside, i wonder if laziness in Concurrent Clean is as much of an
issue as it seems to be in Haskell. i mean, i would expect that if it
is confusing it would be so in general.

sincerely.
Adrian Hey
2009-05-30 08:10:33 UTC
Permalink
Hello Raould
Post by raould
also, i hope DDC continues on to be something of an in-production-
viable system.
http://www.haskell.org/haskellwiki/DDC
That does look interesting. I haven't looked at it seriously because it
prolly doesn't run on Windows (yet) and doesn't have any real
documentation (we've got to wait for Bens thesis).
Post by raould
as an aside, i wonder if laziness in Concurrent Clean is as much of an
issue as it seems to be in Haskell. i mean, i would expect that if it
is confusing it would be so in general.
Yes, Clean has does have more or less the same problems in principle,
but I think Clean semantics are more precise as they're defined directly
in terms of graph rewriting, not lambda calculus (as in Haskell). So
(assuming graph rewriting is the underlying implementation in both
cases) Clean gives more control over issues like sharing and space leaks
than Haskell does.

eg. If at the top level I have something like this..

-- The list of all primes in ascending order
primes :: [Integer]
primes = <some cute expression>

In a Haskell implementation this is likely a constant graph (and
probably a space leak). I forget the precise Clean syntax, but Clean
gives you the choice of having primes as a constant graph or as a
"function of zero arity". In the latter case you get a new list of
primes every time the value of primes is demanded.

The other old example I'm reminded of is the power set function (set of
all subsets):

-- Huge space leak, even if result is consumed and discarded as a lazy
-- list.
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = xss ++ map (x:) xss
| where xss = powerset xs

-- No huge space leak *provided* the result is consumed and discarded as
-- a lazy list. Otherwise slower and even more memory hungry.
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)

This example is interesting in that it shows that that often there is no
single obvious "best" definition of some function. Bestness is a non
local property and depends on context of use. So this kind of implies
whole program (or whole something) analysis is needed for a smart
compiler to synthesise the "best" implementation.

Also as the whole issue of sharing is somewhat ambiguous in Haskell
there's no guarantee that common sub-expression elimination will not
transform the second into the first in any case (though I believe no
current implementation would actually do this).

Regards
--
Adrian Hey
Ertugrul Söylemez
2009-05-30 11:01:46 UTC
Permalink
Post by Adrian Hey
Post by raould
as an aside, i wonder if laziness in Concurrent Clean is as much of
an issue as it seems to be in Haskell. i mean, i would expect that
if it is confusing it would be so in general.
Yes, Clean has does have more or less the same problems in principle,
but I think Clean semantics are more precise as they're defined
directly in terms of graph rewriting, not lambda calculus (as in
Haskell). So (assuming graph rewriting is the underlying
implementation in both cases) Clean gives more control over issues
like sharing and space leaks than Haskell does.
It gives more control over sharing, yes, but whether and where space
leaks occur in Haskell is totally predictable. The semantics are
simple.
Post by Adrian Hey
eg. If at the top level I have something like this..
-- The list of all primes in ascending order
primes :: [Integer]
primes = <some cute expression>
In a Haskell implementation this is likely a constant graph (and
probably a space leak). I forget the precise Clean syntax, but Clean
gives you the choice of having primes as a constant graph or as a
"function of zero arity". In the latter case you get a new list of
primes every time the value of primes is demanded.
I'm unable to come up with "some cute expression" in Haskell, which
would make up a space leak, unless you use something fancy like an
infinite sieve of Eratosthenes, like some tutorials suggest, but this
problem is not Haskell-specific.

What really makes Clean better in some places is uniqueness types.
While from an elegance and flexibility standpoint I would always prefer
monads, uniqueness types allow you to give the compiler a hint as to how
a value is used, like: "this value can be changed in-place in memory".
In Haskell you would have to use an ST monad for the same behaviour.

However, in practical code, this is almost always irrelevant. I have
yet to see a case (other than sieving primes), where this would be
useful.
Post by Adrian Hey
The other old example I'm reminded of is the power set function (set
-- Huge space leak, even if result is consumed and discarded as a lazy
-- list.
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = xss ++ map (x:) xss
| where xss = powerset xs
-- No huge space leak *provided* the result is consumed and discarded as
-- a lazy list. Otherwise slower and even more memory hungry.
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
This example is interesting in that it shows that that often there is
no single obvious "best" definition of some function. Bestness is a
non local property and depends on context of use. So this kind of
implies whole program (or whole something) analysis is needed for a
smart compiler to synthesise the "best" implementation.
As frequently noted, Haskell compilers don't do CSE, so the second
definition is always the best. They are never equivalent and the latter
is always more lazy.
Post by Adrian Hey
Also as the whole issue of sharing is somewhat ambiguous in Haskell
there's no guarantee that common sub-expression elimination will not
transform the second into the first in any case (though I believe no
current implementation would actually do this).
Wrong. See above.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Adrian Hey
2009-05-30 16:16:27 UTC
Permalink
Hello Ertugrul,
Post by Ertugrul Söylemez
Post by Adrian Hey
Post by raould
as an aside, i wonder if laziness in Concurrent Clean is as much of
an issue as it seems to be in Haskell. i mean, i would expect that
if it is confusing it would be so in general.
Yes, Clean has does have more or less the same problems in principle,
but I think Clean semantics are more precise as they're defined
directly in terms of graph rewriting, not lambda calculus (as in
Haskell). So (assuming graph rewriting is the underlying
implementation in both cases) Clean gives more control over issues
like sharing and space leaks than Haskell does.
It gives more control over sharing, yes, but whether and where space
leaks occur in Haskell is totally predictable.
Not by reasoning at the local level of function or module definitions,
as the powerset example shows. If the sharing semantics were specified
then yes it might be possible that someone with a brain the size of
planet could predict any programs space behaviour by doing mental whole
program analysis. But I certainly can't do that and I seriously doubt
that you can either :-)
Post by Ertugrul Söylemez
The semantics are simple.
The graph rewriting semantics are not even specified anywhere that I'm
aware of (certainly not in the H98 standard). The best that might be
said is that there's an informal understanding among Haskell
implementors (both of them :-) about what the semantics should be, if
only someone took the time to write them down.
Post by Ertugrul Söylemez
Post by Adrian Hey
eg. If at the top level I have something like this..
-- The list of all primes in ascending order
primes :: [Integer]
primes = <some cute expression>
In a Haskell implementation this is likely a constant graph (and
probably a space leak). I forget the precise Clean syntax, but Clean
gives you the choice of having primes as a constant graph or as a
"function of zero arity". In the latter case you get a new list of
primes every time the value of primes is demanded.
I'm unable to come up with "some cute expression" in Haskell, which
would make up a space leak, unless you use something fancy like an
infinite sieve of Eratosthenes, like some tutorials suggest, but this
problem is not Haskell-specific.
It doesn't matter what the cute expression is. What matters is that
the expression defines the list of *all* primes. So if this is used
elsewhere to define a function which computes the nth prime (say) then
computing the millionth prime will result in a great gob of memory being
consumed that will probably never be recovered by GC (certainly not
while the nth prime function is still referenced).

It is Haskell-specific IMO, though I guess you could say Haskell
predecessors like Miranda share the problem. Clean provides the
opportunity to define primes as a zero arity function. David Turners
total functional programming proposal deliberately makes a semantic
distinction between data and codata (primes would be a colist).
Post by Ertugrul Söylemez
As frequently noted, Haskell compilers don't do CSE,
So why does ghc provide -fcse and -fno-cse flags? According to the
manual -fcse (turn on common sub-expression elimination) is implied
by -O.

http://www.haskell.org/ghc/docs/latest/html/users_guide/flag-reference.html

That said, I'm sure I can remember SPJ saying ghc didn't do CSE, so what
you say may well be true of ghc. But even if it is, the mere presence of
these flags indicates some confusion and ambiguity re. this in Haskell
land.
Post by Ertugrul Söylemez
so the second definition is always the best. They are never equivalent
and the latter is always more lazy.
Unless I'm mistaken, if the entire evaluated powerset is retained
memory (for whatever reason) the the first definition "only" requires
O(2^N) memory whereas the second definition requires O(N*(2^N)) memory
(N being the size of the input set). So I don't think you can say the
second definition is always the best. You just can't tell which is
best unless you know how it's going to be used (which typically you
don't if you're implementing a library).
Post by Ertugrul Söylemez
Post by Adrian Hey
Also as the whole issue of sharing is somewhat ambiguous in Haskell
there's no guarantee that common sub-expression elimination will not
transform the second into the first in any case (though I believe no
current implementation would actually do this).
Wrong. See above.
I'd rather see a reference to a document that defines the sharing
semantics. :-)

Regards
--
Adrian Hey
Ertugrul Söylemez
2009-05-31 03:18:45 UTC
Permalink
Post by Adrian Hey
Post by Ertugrul Söylemez
Post by Adrian Hey
Post by raould
as an aside, i wonder if laziness in Concurrent Clean is as much
of an issue as it seems to be in Haskell. i mean, i would expect
that if it is confusing it would be so in general.
Yes, Clean has does have more or less the same problems in
principle, but I think Clean semantics are more precise as they're
defined directly in terms of graph rewriting, not lambda calculus
(as in Haskell). So (assuming graph rewriting is the underlying
implementation in both cases) Clean gives more control over issues
like sharing and space leaks than Haskell does.
It gives more control over sharing, yes, but whether and where space
leaks occur in Haskell is totally predictable.
Not by reasoning at the local level of function or module definitions,
as the powerset example shows. If the sharing semantics were specified
then yes it might be possible that someone with a brain the size of
planet could predict any programs space behaviour by doing mental
whole program analysis. But I certainly can't do that and I seriously
doubt that you can either :-)
Why? The powerset example was totally predictable to me. I knew how it
would use space by just looking at it. Also the difference between your
two variants were also totally clear. The first is memoizing, thus less
lazy in favor of being more efficient as a whole. The second is not
memoizing, thus preferring laziness.
Post by Adrian Hey
Post by Ertugrul Söylemez
The semantics are simple.
The graph rewriting semantics are not even specified anywhere that I'm
aware of (certainly not in the H98 standard). The best that might be
said is that there's an informal understanding among Haskell
implementors (both of them :-) about what the semantics should be, if
only someone took the time to write them down.
There are thunks. Those are either evaluated or not. There is demand.
Demand makes thunks get evaluated. That's it. I'm not sure in what
words the H98 standard specifies this, though. It doesn't mention the
term 'graph' anywhere, but that's also not necessary.
Post by Adrian Hey
Post by Ertugrul Söylemez
Post by Adrian Hey
eg. If at the top level I have something like this..
-- The list of all primes in ascending order
primes :: [Integer]
primes = <some cute expression>
In a Haskell implementation this is likely a constant graph (and
probably a space leak). I forget the precise Clean syntax, but
Clean gives you the choice of having primes as a constant graph or
as a "function of zero arity". In the latter case you get a new
list of primes every time the value of primes is demanded.
I'm unable to come up with "some cute expression" in Haskell, which
would make up a space leak, unless you use something fancy like an
infinite sieve of Eratosthenes, like some tutorials suggest, but
this problem is not Haskell-specific.
It doesn't matter what the cute expression is. What matters is that
the expression defines the list of *all* primes. So if this is used
elsewhere to define a function which computes the nth prime (say) then
computing the millionth prime will result in a great gob of memory
being consumed that will probably never be recovered by GC (certainly
not while the nth prime function is still referenced).
Wrong. Proof:

isPrime :: Integral i => i -> Bool
isPrime n = all (\d -> n `rem` d /= 0) . takeWhile (\p -> p*p <= n) $ primes

primes :: Integral i => [i]
primes = 2 : filter isPrime [3..]

Uses O(1) memory, no matter which prime you pick by index (!!).
Post by Adrian Hey
It is Haskell-specific IMO, though I guess you could say Haskell
predecessors like Miranda share the problem. Clean provides the
opportunity to define primes as a zero arity function. David Turners
total functional programming proposal deliberately makes a semantic
distinction between data and codata (primes would be a colist).
Luckily your opinion doesn't count. Haskell's evaluation semantics are
totally predictable and controllable. The only advantage Clean gives
over Haskell is uniqueness types.
Post by Adrian Hey
Post by Ertugrul Söylemez
As frequently noted, Haskell compilers don't do CSE,
So why does ghc provide -fcse and -fno-cse flags? According to the
manual -fcse (turn on common sub-expression elimination) is implied by
-O.
Because CSE can change semantics drastically, it is only performed where
it is guaranteed to make no semantical difference, i.e. almost nowhere.
Post by Adrian Hey
http://www.haskell.org/ghc/docs/latest/html/users_guide/flag-reference.html
That said, I'm sure I can remember SPJ saying ghc didn't do CSE, so
what you say may well be true of ghc. But even if it is, the mere
presence of these flags indicates some confusion and ambiguity
re. this in Haskell land.
Have a look at this:

http://haskell.org/haskellwiki/GHC_optimisations#Common_subexpression_elimination

GHC can do CSE, but generally doesn't.
Post by Adrian Hey
Post by Ertugrul Söylemez
so the second definition is always the best. They are never
equivalent and the latter is always more lazy.
Unless I'm mistaken, if the entire evaluated powerset is retained
memory (for whatever reason) the the first definition "only" requires
O(2^N) memory whereas the second definition requires O(N*(2^N)) memory
(N being the size of the input set). So I don't think you can say the
second definition is always the best. You just can't tell which is
best unless you know how it's going to be used (which typically you
don't if you're implementing a library).
In Haskell the second definition _is_ always the best. This is because
of semantics. It will also use O(2^n) memory. This "retaining in
memory" is called memoizing in Haskell. Values with names are always
kept, as long as they are in scope and there is still some reference to
it. In this case 'xss' (which is a value with the name 'xss') is
memoized.
Post by Adrian Hey
Post by Ertugrul Söylemez
Post by Adrian Hey
Also as the whole issue of sharing is somewhat ambiguous in Haskell
there's no guarantee that common sub-expression elimination will
not transform the second into the first in any case (though I
believe no current implementation would actually do this).
Wrong. See above.
I'd rather see a reference to a document that defines the sharing
semantics. :-)
There is no implicit sharing. Sharing is always done through
memoization. I repeat: Haskell's semantics are very simple, even
though for some reason you just don't want to believe it.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Adrian Hey
2009-05-31 13:58:56 UTC
Permalink
Post by Ertugrul Söylemez
The powerset example was totally predictable to me. I knew how it
would use space by just looking at it.
The point I'm making is that nobody can predict it's space behaviour
without knowing the context in which it's used (which we don't).
Post by Ertugrul Söylemez
Also the difference between your
two variants were also totally clear. The first is memoizing, thus less
lazy in favor of being more efficient as a whole. The second is not
memoizing, thus preferring laziness.
The difference in *possible* space behaviours of the two variants might
well be clear, but you still can't know the actual space behaviour of
either in the absence of context information.
Post by Ertugrul Söylemez
There are thunks. Those are either evaluated or not. There is demand.
Demand makes thunks get evaluated. That's it. I'm not sure in what
words the H98 standard specifies this, though.
It doesn't AFAICS. I think you're describing ghc here, not Haskell.
Post by Ertugrul Söylemez
It doesn't mention the
term 'graph' anywhere, but that's also not necessary.
Only if we don't care about space behaviour.
Post by Ertugrul Söylemez
isPrime :: Integral i => i -> Bool
isPrime n = all (\d -> n `rem` d /= 0) . takeWhile (\p -> p*p <= n) $ primes
primes :: Integral i => [i]
primes = 2 : filter isPrime [3..]
Uses O(1) memory, no matter which prime you pick by index (!!).
main :: IO ()
main = print (primes !! 1000000) >> print (primes !! 1000000)

Compiling (with -fno-cse just to be sure) and running gives..

<A long pause and about 23 GiB heap allocation later..>
15485867
<Then "immediately"..>
15485867

So it sure looks like the entire list of the first 1000001 primes has
been retained between the two calls (as one would expect even from
informal semantics you described above). Also if I comment out the
second print I still get 23 GiB heap allocation (not half this).
I also get about 16 MiB heap residency in each case.

Have I misunderstood what you mean by "Uses O(1) memory, no matter which
prime you pick"?
Post by Ertugrul Söylemez
In Haskell the second definition _is_ always the best. This is because
of semantics. It will also use O(2^n) memory.
Not according to my maths. Recalling the definition..

powerset [] = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)

If C(N) is the number of "cons cells" needed to retain the entire result
then the recurrence relation we need to solve is:

C(0) = 1
C(N) = 2*C(N-1) + 2^(N-1)

The exact solution of which is: C(N) = (N+2)*(2^(N-1))
C(N) is O(N*(2^N)) IOW.
Post by Ertugrul Söylemez
This "retaining in memory" is called memoizing in Haskell.
This seems to be a rather non-standard use of the term "memoizing", but
I know what you mean, you know what I mean, so let's not argue about it.
Post by Ertugrul Söylemez
Values with names are always
kept, as long as they are in scope and there is still some reference to
it.
Indeed. So how do reconcile this with your earlier assertion that primes
"uses O(1) memory, no matter which prime you pick by index"?

If primes is still referenced it uses (retains) O(N) memory where N is
in the number of primes less than or equal to the largest prime that
has been demanded so far.

Or maybe that should be O(N*LOG(N)) memory if we include the growth of
bits needed to actually represent ever increasing primes. Or something
like that..
Post by Ertugrul Söylemez
There is no implicit sharing. Sharing is always done through
memoization. I repeat: Haskell's semantics are very simple, even
though for some reason you just don't want to believe it.
That isn't what I said.

(sub-graph) sharing semantics are not specified, but let's assume that
if they were specified they would indeed be very simple. It does not
follow that the space behaviour of real programs is at all simple to
understand. Newtons law of gravitation is very simple, but a solution to
the N-body problem is far from simple for N>2.

If you say that you understand the space behaviour of all your Haskell
programs, then fine. But I think the rest of us mere mortals will have
to continue living in ignorance or tinkering about with heap profilers
and wotnot.

Regards
--
Adrian Hey
Ertugrul Söylemez
2009-06-01 11:06:53 UTC
Permalink
Post by Adrian Hey
Post by Ertugrul Söylemez
The powerset example was totally predictable to me. I knew how it
would use space by just looking at it.
The point I'm making is that nobody can predict it's space behaviour
without knowing the context in which it's used (which we don't).
That's a good point actually. But there are actually two variants:
lazy and strict. In general, lazy is assumed. If that's not the case,
the documentation should state it.
Post by Adrian Hey
Post by Ertugrul Söylemez
Also the difference between your two variants were also totally
clear. The first is memoizing, thus less lazy in favor of being
more efficient as a whole. The second is not memoizing, thus
preferring laziness.
The difference in *possible* space behaviours of the two variants
might well be clear, but you still can't know the actual space
behaviour of either in the absence of context information.
In the worst case the function uses O(2^n) memory.
Post by Adrian Hey
Post by Ertugrul Söylemez
There are thunks. Those are either evaluated or not. There is
demand. Demand makes thunks get evaluated. That's it. I'm not
sure in what words the H98 standard specifies this, though.
It doesn't AFAICS. I think you're describing ghc here, not Haskell.
AFAIK there is really a clear specification of what 'non-strict
semantics' are. GHC implements it in this way. Even if the actual
implementation is different, you can still use these terms.
Post by Adrian Hey
Post by Ertugrul Söylemez
It doesn't mention the term 'graph' anywhere, but that's also not
necessary.
Only if we don't care about space behaviour.
I think the above definition lets you derive space behaviour as well.
Post by Adrian Hey
Post by Ertugrul Söylemez
isPrime :: Integral i => i -> Bool
isPrime n = all (\d -> n `rem` d /= 0) . takeWhile (\p -> p*p <= n) $ primes
primes :: Integral i => [i]
primes = 2 : filter isPrime [3..]
Uses O(1) memory, no matter which prime you pick by index (!!).
main :: IO ()
main = print (primes !! 1000000) >> print (primes !! 1000000)
Compiling (with -fno-cse just to be sure) and running gives..
<A long pause and about 23 GiB heap allocation later..>
15485867
<Then "immediately"..>
15485867
So it sure looks like the entire list of the first 1000001 primes has
been retained between the two calls (as one would expect even from
informal semantics you described above). Also if I comment out the
second print I still get 23 GiB heap allocation (not half this). I
also get about 16 MiB heap residency in each case.
Have I misunderstood what you mean by "Uses O(1) memory, no matter
which prime you pick"?
Okay, forget that example. It uses O(1) memory, if you enable
optimization (-O), otherwise the list fusion optimization doesn't take
place. Also memoizing keeps the entire list in memory, not just the
element calculated. But you could replace 'primes' by a recursive
function, though. In fact, the space leak is the correct behaviour.

The reason why it doesn't use twice 23 GiB heap is simple: 'primes' is
memoized. Remember that it's not a function, but a value. Your
indexing with 'primes !! 1000000' doesn't parameterize 'primes', but it
parameterizes (!!).

What I don't understand is that it uses this huge amount of memory. It
used only a few MiB for me.
Post by Adrian Hey
Post by Ertugrul Söylemez
In Haskell the second definition _is_ always the best. This is
because of semantics. It will also use O(2^n) memory.
Not according to my maths. Recalling the definition..
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
If C(N) is the number of "cons cells" needed to retain the entire
C(0) = 1
C(N) = 2*C(N-1) + 2^(N-1)
The exact solution of which is: C(N) = (N+2)*(2^(N-1))
C(N) is O(N*(2^N)) IOW.
Well, I didn't count individual cells. Also there is only one sublist
that really takes 'n' cells. However, this is worst case behaviour,
which happens, when the entire powerset list is used. Otherwise you
have list fusion optimization, which can reduce memory usage to O(2^n)
with respect to individual cells.
Post by Adrian Hey
Post by Ertugrul Söylemez
This "retaining in memory" is called memoizing in Haskell.
This seems to be a rather non-standard use of the term "memoizing",
but I know what you mean, you know what I mean, so let's not argue
about it.
Post by Ertugrul Söylemez
Values with names are always kept, as long as they are in scope and
there is still some reference to it.
Indeed. So how do reconcile this with your earlier assertion that
primes "uses O(1) memory, no matter which prime you pick by index"?
If primes is still referenced it uses (retains) O(N) memory where N is
in the number of primes less than or equal to the largest prime that
has been demanded so far.
Or maybe that should be O(N*LOG(N)) memory if we include the growth of
bits needed to actually represent ever increasing primes. Or something
like that..
Yes, that's expected behaviour. As noted earlier, I have picked a bad
example, because I had list fusion optimization in mind. Replacing
'primes' by a function would solve that problem.
Post by Adrian Hey
Post by Ertugrul Söylemez
There is no implicit sharing. Sharing is always done through
memoization. I repeat: Haskell's semantics are very simple, even
though for some reason you just don't want to believe it.
That isn't what I said.
(sub-graph) sharing semantics are not specified, but let's assume that
if they were specified they would indeed be very simple. It does not
follow that the space behaviour of real programs is at all simple to
understand. Newtons law of gravitation is very simple, but a solution
to the N-body problem is far from simple for N>2.
If you say that you understand the space behaviour of all your Haskell
programs, then fine. But I think the rest of us mere mortals will have
to continue living in ignorance or tinkering about with heap profilers
and wotnot.
At some point I learned it. Since then the behaviour of my programs
seems natural to me. I think everybody can learn it. Of course
Haskell's semantics are harder than C's semantics, but so what? If it
pays off, I learn it.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Jon Harrop
2009-06-01 15:58:41 UTC
Permalink
The powerset example was totally predictable to me.  I knew how it
would use space by just looking at it.
...
What I don't understand is that it uses this huge amount of memory.
...
At some point I learned it. Since then the behaviour of my programs
seems natural to me. I think everybody can learn it.
...
Hmm.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Adrian Hey
2009-06-01 16:49:47 UTC
Permalink
Hello Jon,
Post by Ertugrul Söylemez
The powerset example was totally predictable to me. I knew how it
would use space by just looking at it.
...
What I don't understand is that it uses this huge amount of memory.
...
At some point I learned it. Since then the behaviour of my programs
seems natural to me. I think everybody can learn it.
...
Hmm.
:-)

It had crossed my mind to yank Ertugruls chain over the apparent
contradictions his views. But I decided that wouldn't be fair as the
huge amount of memory he's talking about is dynamic heap useage (heap
allocation rate) rather than the static heap useage. I.E. actual size of
non-garbage graph at any point in time (residency).

The 23 GiB is dynamic heap use, which depends a lot on whether or not
certain deforestation/fusion optimisations can be (and have been)
performed. The 16 MiB or so residency seems about right for a list of
the first 1000001 primes.

Regards
--
Adrian Hey
Ertugrul Söylemez
2009-06-01 21:35:57 UTC
Permalink
The powerset example was totally predictable to me.  I knew how it
would use space by just looking at it.
...
What I don't understand is that it uses this huge amount of memory.
...
At some point I learned it. Since then the behaviour of my programs
seems natural to me. I think everybody can learn it.
...
Hmm.
What's wrong with that? It works as expected for me. Or do you blame
C, when GCC produces bad code, because you compiled without
optimizations turned on?


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Jon Harrop
2009-06-02 11:15:42 UTC
Permalink
Post by Ertugrul Söylemez
The powerset example was totally predictable to me.  I knew how it
would use space by just looking at it.
...
What I don't understand is that it uses this huge amount of memory.
...
At some point I learned it. Since then the behaviour of my programs
seems natural to me. I think everybody can learn it.
...
Hmm.
What's wrong with that?
You labored the point that you could trivially predict the memory
consumption of Haskell programs only to make an incorrect assertion about
the memory consumption of your own trivial program.
Post by Ertugrul Söylemez
It works as expected for me.
No, it didn't. Hence you said "I don't understand" when your prediction
turned out to be completely wrong.

Don't feel bad though: *nobody* can predict the memory consumption of
Haskell programs and it is probably the single biggest problem with the
language.
Post by Ertugrul Söylemez
Or do you blame C, when GCC produces bad code, because you compiled
without optimizations turned on?
The asymptotic memory consumption of my C programs does not depend upon
compiler optimizations.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Ertugrul Söylemez
2009-06-02 11:25:52 UTC
Permalink
Post by Jon Harrop
Post by Ertugrul Söylemez
Post by Ertugrul Söylemez
The powerset example was totally predictable to me. I knew how it
would use space by just looking at it.
...
What I don't understand is that it uses this huge amount of memory.
...
At some point I learned it. Since then the behaviour of my programs
seems natural to me. I think everybody can learn it.
...
Hmm.
What's wrong with that?
You labored the point that you could trivially predict the memory
consumption of Haskell programs only to make an incorrect assertion about
the memory consumption of your own trivial program.
Post by Ertugrul Söylemez
It works as expected for me.
No, it didn't. Hence you said "I don't understand" when your prediction
turned out to be completely wrong.
It did work for me. I didn't understand why it didn't work for Adrian.
I don't compile without optimizations.
Post by Jon Harrop
Don't feel bad though: *nobody* can predict the memory consumption of
Haskell programs and it is probably the single biggest problem with the
language.
Ah, your usual "wisdom".
Post by Jon Harrop
Post by Ertugrul Söylemez
Or do you blame C, when GCC produces bad code, because you compiled
without optimizations turned on?
The asymptotic memory consumption of my C programs does not depend upon
compiler optimizations.
And now it may happen to you as well that you get proven wrong, because
you missed something. This doesn't say anything about C. We're humans
after all. Also I've picked a simple language. OCaml is more likely to
produce behaviour that you don't understand. My Haskell code works as
expected for me, so does your OCaml code for you (probably), as long as
you don't disable optimizations.

Although you have to learn semantics first in Haskell to predict its
memory behaviour, the code produces correct results in most cases, even
if you're leaking space. Bugs are very rare. What I hate much more
about languages is when they produce random behaviour altogether. My
current problem with F# is an example of this (see the thread 'State
monads in F#'). You may be more productive by sharing your OCaml/F#
wisdom there, rather than beating on a language you don't like.


Greets,
Ertugrul.
Jon Harrop
2009-06-02 18:30:39 UTC
Permalink
Post by Ertugrul Söylemez
Post by Jon Harrop
The asymptotic memory consumption of my C programs does not depend upon
compiler optimizations.
And now it may happen to you as well that you get proven wrong, because
you missed something.
I am more than happy to test my falsifiable hypothesis.
Post by Ertugrul Söylemez
OCaml is more likely to produce behaviour that you don't understand.
OCaml performs fewer and simpler optimizations than most C compilers, e.g.
it does not do CSE. Hence it is *very* predictable. That is one of the main
reasons I choose to work with OCaml and not Haskell.
Post by Ertugrul Söylemez
My Haskell code works as
expected for me, so does your OCaml code for you (probably), as long as
you don't disable optimizations.
All OCaml code has the same predictable behaviour whether you enable
optimizations or not. The same is not true of Haskell: it is fundamentally
unpredictable and people (like you) write code that will only run provided
certain sets of optimisations are performed by the compiler and enabled.
That is obviously a really bad idea.
Post by Ertugrul Söylemez
Although you have to learn semantics first in Haskell to predict its
memory behaviour, the code produces correct results in most cases, even
if you're leaking space. Bugs are very rare. What I hate much more
about languages is when they produce random behaviour altogether. My
current problem with F# is an example of this (see the thread 'State
monads in F#').
Your code example never compiles due to a type error. That is not "random
behaviour".
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Ertugrul Söylemez
2009-06-02 19:53:32 UTC
Permalink
Post by Jon Harrop
Post by Ertugrul Söylemez
OCaml is more likely to produce behaviour that you don't understand.
OCaml performs fewer and simpler optimizations than most C compilers,
e.g. it does not do CSE. Hence it is *very* predictable. That is one
of the main reasons I choose to work with OCaml and not Haskell.
I wasn't referring to optimizations, but to the language itself. It is
obviously more complicated than C, like most high level languages are.
Post by Jon Harrop
Post by Ertugrul Söylemez
My Haskell code works as expected for me, so does your OCaml code
for you (probably), as long as you don't disable optimizations.
All OCaml code has the same predictable behaviour whether you enable
optimizations or not. The same is not true of Haskell: it is
fundamentally unpredictable and people (like you) write code that will
only run provided certain sets of optimisations are performed by the
compiler and enabled. That is obviously a really bad idea.
My Haskell code probably depends on a set of optimizations, yes. It
also usually depends on a set of language extensions, so I should say
that I write GHC/Hugs (probably some others, too) code rather than
Haskell 98 code. However, I see no problem with that. How this is
"obviously a really bad idea" is not clear to me.
Post by Jon Harrop
Post by Ertugrul Söylemez
Although you have to learn semantics first in Haskell to predict its
memory behaviour, the code produces correct results in most cases,
even if you're leaking space. Bugs are very rare. What I hate much
more about languages is when they produce random behaviour
altogether. My current problem with F# is an example of this (see
the thread 'State monads in F#').
Your code example never compiles due to a type error. That is not
"random behaviour".
I figured. The choice of uncurried style for all computation
expression-related functions is pure nonsense to me.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
raould
2009-06-04 21:51:35 UTC
Permalink
Post by Ertugrul Söylemez
Although you have to learn semantics first in Haskell to predict its
memory behaviour, the code produces correct results in most cases, even
if you're leaking space. Bugs are very rare.
thanks to all for the thoughts about this subject.

i think i get it that laziness can lead to big space usage. and i
guess there is some debate about how easy it is for programmers to see
"oh this code right here could lead to a space leak!"

so, how could/do people see that something could be a space leak? is
there anything about it that could be automated?

thanks.
raould
2009-06-04 22:00:44 UTC
Permalink
Post by raould
so, how could/do people see that something could be a space leak? is
there anything about it that could be automated?
hmmm

http://users.aber.ac.uk/afc/stricthaskell.html
Jon Harrop
2009-06-04 22:14:21 UTC
Permalink
Post by raould
i think i get it that laziness can lead to big space usage. and i
guess there is some debate about how easy it is for programmers to see
"oh this code right here could lead to a space leak!"
There is no debate. I asked Simon Peyton-Jones about this in person and he
confirmed that unpredictable memory consumption is one of the biggest
practical issues with Haskell. Ertugrul claimed he knew better but proved
himself wrong.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Manlio Perillo
2009-06-04 23:36:21 UTC
Permalink
Post by Jon Harrop
i think i get it that laziness can lead to big space usage. and i guess
there is some debate about how easy it is for programmers to see "oh
this code right here could lead to a space leak!"
There is no debate. I asked Simon Peyton-Jones about this in person and
he confirmed that unpredictable memory consumption is one of the biggest
practical issues with Haskell. Ertugrul claimed he knew better but
proved himself wrong.
Since I like lazy data structutes (IMHO, they are a nice generalization
over generators), is it possible to obtain something similar in strict
languages like OCaml?


Thanks Manlio
raould
2009-06-05 00:01:54 UTC
Permalink
Post by Manlio Perillo
Since I like lazy data structutes (IMHO, they are a nice generalization
over generators), is it possible to obtain something similar in strict
languages like OCaml?
OTish: you might be interested in looking at Clojure (and possibly
Scala).

sincerely.
Jon Harrop
2009-06-05 00:31:07 UTC
Permalink
Post by Manlio Perillo
Post by Jon Harrop
i think i get it that laziness can lead to big space usage. and i guess
there is some debate about how easy it is for programmers to see "oh
this code right here could lead to a space leak!"
There is no debate. I asked Simon Peyton-Jones about this in person and
he confirmed that unpredictable memory consumption is one of the biggest
practical issues with Haskell. Ertugrul claimed he knew better but
proved himself wrong.
Since I like lazy data structutes (IMHO, they are a nice generalization
over generators), is it possible to obtain something similar in strict
languages like OCaml?
Varies depending upon the kind of lazy data structure in question.

For example, you have on-demand sequences like the Seq module from F# (or
IEnumerable in .NET) or streams in OCaml. They can make life easier in some
circumstances, e.g. examining the first few results from a database query
without forcing the evaluation of all results. That is easy and very
common. However, they can expose impurity (e.g. Seq in F# and streams in
OCaml) and have different semantics (e.g. computed results are not
automatically remembered).

Alternatively, you may be referring to genuine purely functional data
structures like the catenable lists described by Okasaki. Those are not
common in strict languages like OCaml. To hazard a guess, because they are
so inefficient compared to imperative data structures. Laziness also
inhibits parallelism by introducing mutation everywhere.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Aatu Koskensilta
2009-06-05 14:15:43 UTC
Permalink
Post by Manlio Perillo
Since I like lazy data structutes (IMHO, they are a nice
generalization over generators), is it possible to obtain something
similar in strict languages like OCaml?
Coinductive datatypes are the obvious alternative. Given the importance
of coinduction in computer science (in various guises) it's a bit odd
it's received so little attention (in relative terms).
--
Aatu Koskensilta (***@uta.fi)

"Wovon mann nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Marshall
2009-06-07 07:51:20 UTC
Permalink
Post by Aatu Koskensilta
Coinductive datatypes are the obvious alternative. Given the importance
of coinduction in computer science (in various guises) it's a bit odd
it's received so little attention (in relative terms).
Can you recommend some good introductory/intermediate
material? I have a modest amount of familiarity with stream
databases, aggregate functions, etc. but have not
encountered them with any sort of formalism attached,
and I feel the lack.


Marshall
Paul Rubin
2009-06-07 09:35:30 UTC
Permalink
Post by Aatu Koskensilta
Coinductive datatypes are the obvious alternative. Given the importance
of coinduction in computer science (in various guises) it's a bit odd
it's received so little attention (in relative terms).
Can you recommend some good introductory/intermediate material?
http://en.wikipedia.org/wiki/Coinduction

and its references are an obvious place to start. Turner's well-known
article on total functional programming might be another:

http://www.jucs.org/jucs_10_7/total_functional_programming
raould
2009-06-05 00:03:28 UTC
Permalink
Post by Jon Harrop
There is no debate. I asked Simon Peyton-Jones about this in person and he
confirmed that unpredictable memory consumption is one of the biggest
practical issues with Haskell. Ertugrul claimed he knew better but proved
himself wrong.
no problem, i wasn't trying to get into that debate. i am just
wondering what anybody can do about the unpredictableness. what causes
it? what, if anything, can be done to alleviate it? i mean in Haskell
-- saying "well, use a strict language" isn't what i'm looking for.
not that i don't think that is a fine answer. i'm just curious what
could be done specifically for Haskell. :-)

many thanks.
Paul Rubin
2009-06-05 02:26:04 UTC
Permalink
Post by raould
no problem, i wasn't trying to get into that debate. i am just
wondering what anybody can do about the unpredictableness. what causes
it? what, if anything, can be done to alleviate it? i mean in Haskell
-- saying "well, use a strict language" isn't what i'm looking for.
not that i don't think that is a fine answer. i'm just curious what
could be done specifically for Haskell. :-)
I've been thinking it would be nice to have some better runtime
diagnostic tools, e.g. some hack in the garbage collector that checks
the depth of closure nesting at each value node once in a while.
You'd run the program with a small input set, and see where the large
piles of closures occurred. Right now, at least for non-experts,
detecting the presence of space leaks is easy, but finding their exact
location is rather difficult. Experts also sometimes write code with
space leaks, but it does seem to me that they are able to locate and
fix them without much fuss. It's not clear to me at this point how
they do it.
Ertugrul Söylemez
2009-06-05 07:11:21 UTC
Permalink
Post by Jon Harrop
Post by raould
i think i get it that laziness can lead to big space usage. and i
guess there is some debate about how easy it is for programmers to see
"oh this code right here could lead to a space leak!"
There is no debate. I asked Simon Peyton-Jones about this in person and he
confirmed that unpredictable memory consumption is one of the biggest
practical issues with Haskell. Ertugrul claimed he knew better but proved
himself wrong.
SPJ is certainly more knowledgable than I am, but in this regard I
disagree (if he really confirmed that in this form). What is a problem
in Haskell is 'unpredicted' space behaviour, because you didn't consider
the non-strict semantics, but not "unpredictable" space behaviour. If
it was such "unpredictable" as you claim, I'd have a very hard time
writing Haskell code.

Also even if a space leak occurs, what's wrong with that? In most cases
the cause is obvious, so just correct your code. If you have done that
a few times, at some point you simply 'get it' and don't produce such
leaking code anymore.

What you are certainly right about is that Haskell depends on a set of
optimizations. I see no problem with that, since they are there. I'd
like to add that you usually use a set of language extensions, too.
Most of the popular extensions will end up as part of the language in
the next Haskell standard.


Greets,
Ertugrul.
George Neuner
2009-06-05 18:20:34 UTC
Permalink
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by raould
i think i get it that laziness can lead to big space usage. and i
guess there is some debate about how easy it is for programmers to see
"oh this code right here could lead to a space leak!"
There is no debate. I asked Simon Peyton-Jones about this in person and he
confirmed that unpredictable memory consumption is one of the biggest
practical issues with Haskell. Ertugrul claimed he knew better but proved
himself wrong.
SPJ is certainly more knowledgable than I am, but in this regard I
disagree (if he really confirmed that in this form). What is a problem
in Haskell is 'unpredicted' space behaviour, because you didn't consider
the non-strict semantics, but not "unpredictable" space behaviour. If
it was such "unpredictable" as you claim, I'd have a very hard time
writing Haskell code.
You can write code forever without seeing a problem iff you never run
the programs with data sets that leak enough to break the system.
Post by Ertugrul Söylemez
Also even if a space leak occurs, what's wrong with that? In most cases
the cause is obvious, so just correct your code.
In some cases it is obvious. In some it is not.
Post by Ertugrul Söylemez
If you have done that a few times, at some point you simply 'get it'
and don't produce such leaking code anymore.
The problem is that even the experts still don't 'get it'.

George
Jon Harrop
2009-06-05 22:04:50 UTC
Permalink
Post by George Neuner
The problem is that even the experts still don't 'get it'.
Indeed, the complete lack of information on this critically-important
subject was a deal breaker for me. There's no way I'm going to devote years
to writing another book only to have to do the original research on how to
address these core issues with Haskell myself.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
toby
2009-06-06 15:47:04 UTC
Permalink
Post by Jon Harrop
Post by George Neuner
The problem is that even the experts still don't 'get it'.
Indeed, the complete lack of information on this critically-important
subject was a deal breaker for me. There's no way I'm going to
Well, I dunno, wouldn't that just make it a more valuable (if more
difficult) book?
Post by Jon Harrop
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/?u
Jon Harrop
2009-06-06 18:22:13 UTC
Permalink
Post by toby
Post by Jon Harrop
Post by George Neuner
The problem is that even the experts still don't 'get it'.
Indeed, the complete lack of information on this critically-important
subject was a deal breaker for me. There's no way I'm going to
Well, I dunno, wouldn't that just make it a more valuable (if more
difficult) book?
I do not believe I could recover the costs because the Haskell market is
just not commercially viable yet. Moreover, this is a chicken and egg
problem: many people will not invest any serious effort in Haskell until
these fundamental problems are addressed and they will not be addressed by
industry because it is not commercially viable to do so. Furthermore, the
academics are not likely to address such problems because it does not
constitute compelling research.

In other words, Haskell has not reached critical mass. IMHO, it never will.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Ertugrul Söylemez
2009-06-07 01:41:02 UTC
Permalink
Post by Jon Harrop
I do not believe I could recover the costs because the Haskell market
is just not commercially viable yet. Moreover, this is a chicken and
egg problem: many people will not invest any serious effort in Haskell
until these fundamental problems are addressed and they will not be
addressed by industry because it is not commercially viable to do
so. Furthermore, the academics are not likely to address such problems
because it does not constitute compelling research.
In other words, Haskell has not reached critical mass. IMHO, it never will.
Well, in the last few years, Haskell development progressed quickly. If
new standards could be created quicker and there were more libraries,
then it could well get commercially viable. As a language it definitely
has the potential.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Jon Harrop
2009-06-07 19:18:51 UTC
Permalink
Post by Ertugrul Söylemez
Post by Jon Harrop
I do not believe I could recover the costs because the Haskell market
is just not commercially viable yet. Moreover, this is a chicken and
egg problem: many people will not invest any serious effort in Haskell
until these fundamental problems are addressed and they will not be
addressed by industry because it is not commercially viable to do
so. Furthermore, the academics are not likely to address such problems
because it does not constitute compelling research.
In other words, Haskell has not reached critical mass. IMHO, it never will.
Well, in the last few years, Haskell development progressed quickly.
In what sense? They're partway to catching up with OCaml as far as IDE
support is concerned but they're still a decade behind F#. They've invested
a lot of time in their own proprietary package system and have a thousand
packages but still poor support for mainstream package systems like apt and
their libraries don't even include a decent hash table implementation. The
core of GHC is not only buggy (e.g. the hash table problem) but even has
serious design flaws that nobody knows how to address. I cannot even see
any evidence that anyone is even attempting to address them.

There has certainly been a lot of noise surrounding Haskell but virtually no
progress, IMHO.
Post by Ertugrul Söylemez
If new standards could be created quicker and there were more libraries,
Lack of documentation and interoperability are much bigger problems, IMHO.
Post by Ertugrul Söylemez
then it could well get commercially viable. As a language it definitely
has the potential.
Perhaps it might become viable for specific domains but I cannot see a
language with such poor support for large-scale programming garnering any
serious traction in industry.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Adrian Hey
2009-06-09 15:50:16 UTC
Permalink
Hello Jon,
Post by Jon Harrop
Post by Ertugrul Söylemez
Well, in the last few years, Haskell development progressed quickly.
In what sense? They're partway to catching up with OCaml as far as IDE
support is concerned but they're still a decade behind F#. They've invested
a lot of time in their own proprietary package system and have a thousand
packages but still poor support for mainstream package systems like apt and
their libraries don't even include a decent hash table implementation.
I think Ertugrul was probably talking about the language in general and
ghc in particular. Though I too have my doubts about Haskell (the
language), I don't think these critisisms of the state general Haskell
related infrastructure (or lack thereof) are entirely fair.

Well they don't reflect on the language at least, IMO. ghc is not a
commercial product and the manpower available to work on it is
relatively tiny. All this infrastructure stuff is something that the
wider community should be working on (those that still care at least
:-)
Post by Jon Harrop
The
core of GHC is not only buggy (e.g. the hash table problem) but even has
serious design flaws that nobody knows how to address. I cannot even see
any evidence that anyone is even attempting to address them.
What bugs and design flaws are you talking about specifically (the ones
that noone is attempting to address)?

Regards
--
Adrian Hey
Jon Harrop
2009-06-09 19:15:16 UTC
Permalink
Post by Adrian Hey
Post by Jon Harrop
Post by Ertugrul Söylemez
Well, in the last few years, Haskell development progressed quickly.
In what sense? They're partway to catching up with OCaml as far as IDE
support is concerned but they're still a decade behind F#. They've
invested a lot of time in their own proprietary package system and have a
thousand packages but still poor support for mainstream package systems
like apt and their libraries don't even include a decent hash table
implementation.
I think Ertugrul was probably talking about the language in general and
ghc in particular. Though I too have my doubts about Haskell (the
language), I don't think these critisisms of the state general Haskell
related infrastructure (or lack thereof) are entirely fair.
Well they don't reflect on the language at least, IMO.
You mean in a purely theoretical sense, disregarding implementations?
Post by Adrian Hey
ghc is not a
commercial product and the manpower available to work on it is
relatively tiny.
The manpower available to work on our products is a fraction of that devoted
to either GHC or OCaml yet we do not suffer from these problems. They do
not arise due a lack of manpower, they arise partly due to undisciplined
development (the people writing this software do not care about real
problems so they make no attempt to facilitate their solution, let alone
solve them: FFIs being the most obvious example) and partly because they
even have contempt for industrialists. For example, the developers of OCaml
at INRIA devoted precious time they had to making it *harder* for third
parties to build upon their work because they want to commercialize it
whilst living off the tax payer and not standing on their own feet in
industry. That obviously does more harm than good and it is killing OCaml.
Post by Adrian Hey
All this infrastructure stuff is something that the
wider community should be working on (those that still care at least
:-)
The wider community need a core implementation that is friendly to such
development (and developers) first. For example, I submitted a fix for a
trivial bug in OCaml's standard library that caused segfaults and stack
overflows only to have to wait over 2 years for my own fix to filter back
to me in an official release because the academics force themselves to
reimplement non-French submissions in order to retain copyright in case
anyone wants to buy their dated language implementation.
Post by Adrian Hey
Post by Jon Harrop
The
core of GHC is not only buggy (e.g. the hash table problem) but even has
serious design flaws that nobody knows how to address. I cannot even see
any evidence that anyone is even attempting to address them.
What bugs and design flaws are you talking about specifically (the ones
that noone is attempting to address)?
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was told
to fix it myself. Rather than fixing the bug, they write factually
incorrect statements about the performance of hash tables in their book
Real World Haskell (!). That is seriously damaging, of course.

The latest paper on GHC described some really serious bugs in the run-time
that arise because laziness is very multicore unfriendly and, consequently,
GHC's run-time can leak memory indefinitely and in an almost entirely
unpredictable way. This latter bug is worse because there is no known
solution, i.e. it is really a design flaw.

I have no doubt that F# will gain serious traction when it sees its first
full release next year. The F# market is already at least as commercially
viable as the OCaml and Haskell markets. There is no theoretical reason why
an open source FPL implementation could not achieve equivalent success but,
sadly, nobody is working towards this. I had hoped to do it myself via HLVM
but the recession is forcing me to work on money-making products right now.
Whatever happens, I do not believe a production quality solution will ever
fall out of academia (e.g. OCaml) or indutrial research (e.g. GHC). To be
honest, I suspect Linux will see a brain drain as people migrate to
Microsoft's far superior technology before it is possible for anyone to
create a viable competitor for Linux.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Adrian Hey
2009-06-09 21:21:57 UTC
Permalink
Hello Jon,
Post by Jon Harrop
Post by Adrian Hey
Well they don't reflect on the language at least, IMO.
You mean in a purely theoretical sense, disregarding implementations?
Yes I guess that's what I mean. Just think we should be clear about
whether any alleged problems are in the language design itself or just
particular implementations.
Post by Jon Harrop
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was told
to fix it myself. Rather than fixing the bug, they write factually
incorrect statements about the performance of hash tables in their book
Real World Haskell (!). That is seriously damaging, of course.
So what's the bug? Is it the GC problem I seem to remember or something
else?

IIRC Jan-Willem Maessen did something with the Hash tables a while ago.
I don't know what he did or if it ever made a difference and got used in
the end.
Post by Jon Harrop
The latest paper on GHC described some really serious bugs in the run-time
that arise because laziness is very multicore unfriendly and, consequently,
GHC's run-time can leak memory indefinitely and in an almost entirely
unpredictable way. This latter bug is worse because there is no known
solution, i.e. it is really a design flaw.
Which paper are you talking about? Do you have a link?

Regards
--
Adrian Hey
Jon Harrop
2009-06-10 14:21:36 UTC
Permalink
Post by Adrian Hey
Post by Jon Harrop
Post by Adrian Hey
Well they don't reflect on the language at least, IMO.
You mean in a purely theoretical sense, disregarding implementations?
Yes I guess that's what I mean. Just think we should be clear about
whether any alleged problems are in the language design itself or just
particular implementations.
Fair enough.
Post by Adrian Hey
Post by Jon Harrop
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was
told to fix it myself. Rather than fixing the bug, they write factually
incorrect statements about the performance of hash tables in their book
Real World Haskell (!). That is seriously damaging, of course.
So what's the bug? Is it the GC problem I seem to remember or something
else?
Writing a value of a reference type into an array dirties the whole array so
the GC traverses the whole array again at the next minor collection. In
essence, writing one element to such an array is O(n) instead of O(1). That
is a core operation for hash tables and many other important data
structures.
Post by Adrian Hey
IIRC Jan-Willem Maessen did something with the Hash tables a while ago.
I don't know what he did or if it ever made a difference and got used in
the end.
Other people have worked around the problem by using the FFI to essentially
implement a hash table in C using manual memory management.
Post by Adrian Hey
Post by Jon Harrop
The latest paper on GHC described some really serious bugs in the
run-time that arise because laziness is very multicore unfriendly and,
consequently, GHC's run-time can leak memory indefinitely and in an
almost entirely unpredictable way. This latter bug is worse because there
is no known solution, i.e. it is really a design flaw.
Which paper are you talking about? Do you have a link?
IIRC, it was this one:

http://www.haskell.org/~simonmar/papers/multicore-ghc.pdf
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Stephen J. Bevan
2009-06-10 06:18:18 UTC
Permalink
Post by Jon Harrop
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was told
to fix it myself.
One has to wonder why you want to use a hash table in any language,
let alone one where immutability is encouraged; your own O'Caml test
programs show that the worst case performance is abysmal even when
mutable.
Post by Jon Harrop
Rather than fixing the bug, they write factually incorrect
statements about the performance of hash tables in their book Real
World Haskell (!). That is seriously damaging, of course.
What are the factually incorrect statements?
Larry Coleman
2009-06-10 12:50:43 UTC
Permalink
Post by Stephen J. Bevan
Post by Jon Harrop
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was told
to fix it myself.
One has to wonder why you want to use a hash table in any language,
let alone one where immutability is encouraged; your own O'Caml test
programs show that the worst case performance is abysmal even when
mutable.
Dr. Harrop knows that hash tables aren't commonly used in Haskell. I
discussed the matter with him myself in a different thread.
Jon Harrop
2009-06-10 14:35:49 UTC
Permalink
Post by Stephen J. Bevan
Post by Jon Harrop
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was
told to fix it myself.
One has to wonder why you want to use a hash table in any language,
Performance. Hash tables are usually 10x faster than any tree-based
alternative.
Post by Stephen J. Bevan
let alone one where immutability is encouraged; your own O'Caml test
programs show that the worst case performance is abysmal even when
mutable.
What?
Post by Stephen J. Bevan
Post by Jon Harrop
Rather than fixing the bug, they write factually incorrect
statements about the performance of hash tables in their book Real
World Haskell (!). That is seriously damaging, of course.
What are the factually incorrect statements?
"Compared to a hash table, a well-implemented purely functional tree data
structure will perform competitively. You should not approach trees with
the assumption that your code will pay a performance penalty."

This is simply wrong. The best-implemented purely functional trees are
typically 10x slower than a hash table. You should approach trees with the
assumption that you will pay a whopping performance penalty.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Stephen J. Bevan
2009-06-11 03:46:02 UTC
Permalink
Post by Jon Harrop
Post by Stephen J. Bevan
Post by Jon Harrop
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was
told to fix it myself.
One has to wonder why you want to use a hash table in any language,
Performance. Hash tables are usually 10x faster than any tree-based
alternative.
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Post by Jon Harrop
Post by Stephen J. Bevan
let alone one where immutability is encouraged; your own O'Caml test
programs show that the worst case performance is abysmal even when
mutable.
What?
In message <***@dnsalias.com> less than two months ago I
tested the O'Caml programs provided by you and plotted the following
graphs of the results :-

$ cat plot
set terminal dumb
set logscale y
set logscale x
plot "hashtbl_insert.dat"
plot "map_insert.dat"
$ gnuplot plot

1e+07 ++---+--+-+-++++++----+--+-++-+++++----+-+--++-++++----+--+-+-++++++
+ + + "hashtbl_insert.dat" A +
| |
+ A +
1e+06 ++ A ++
+ +
| A |
+ A +
100000 ++ ++
+ A +
| A |
+ A +
10000 ++ A A AA AA ++
+ A AAA AA AAAAA A AAAAA AAA +
| A A A A A A AAAAAA A AAAAA AAAAA A |
+ A A A A A A +
1000 ++ ++
+ A AAAAAAAAAAAAA +
| A A AAAAAAAAAAAAAAAAAAAA |
A A A A AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +
100 ++---+--+-+-++++++----+--+-++-+++++----+-+--++-++++----+--+A+-++++++
1 10 100 1000 10000


100000 ++---+--+-+-++++++----+--+-++-+++++----+-+--++-++++----+--+-+-++++++
+ + + "map_insert.dat" A +
+ +
+ +
| |
+ +
| AAAAAAAAA |
10000 ++ AA AAAAAAAAAAAAA ++
+ AA AAAAAAAAAAAAAAAAAAAA +
+ A A AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +
+ A AA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA A +
+ A A A A AAAAA A AA AAAAAAA AA A AAAAAAAAAAAA +
| A A A AA A AAAAAAAAAAAAA |
1000 ++ AAAAAAAAAAAAAAAAA ++
+ AAAAAAAAAAAAAAAAAA +
+ AAAAAAAAAAAAAA +
+ A AAAAA AAAAAAAAAAAAAAA AA A +
+ A A A AAAAAAA AAAAAAAAAAAAAAAA +
+ A AAA AA A A AAA +
A + + + +
100 ++---+--+-+-++++++----+--+-++-+++++----+-+--++-++++----+--+-+-++++++
1 10 100 1000 10000

For <= 100 the worst case of a hash table is still less than that of a
an immutable tree. However, for points past that the worst case of
the hash table begins it dramatic deviation from the worst case for a
a tree such that by the time we get to 4096 the hash table is 100x
worse and the trend just keeps getting worse.
Post by Jon Harrop
Post by Stephen J. Bevan
Post by Jon Harrop
Rather than fixing the bug, they write factually incorrect
statements about the performance of hash tables in their book Real
World Haskell (!). That is seriously damaging, of course.
What are the factually incorrect statements?
"Compared to a hash table, a well-implemented purely functional tree data
structure will perform competitively. You should not approach trees with
the assumption that your code will pay a performance penalty."
This is simply wrong. The best-implemented purely functional trees are
typically 10x slower than a hash table. You should approach trees
with the assumption that you will pay a whopping performance
penalty.
We'll if we are going to call the Haskell quote factually incorrect
then I'd class your statement as factually incorrect too since it
completely overstates the case for hash tables and completely ignores
the worst case performance.

You should approach trees knowing that you'll get consistent
worst-case performance regardless of size. You should approach hash
tables knowing that depending on the size and data that the best case
can be significantly faster than trees but the worst case can be
significantly slower than trees and that the best/worst range is not
symmetric, the worst case can, for large enough values of n, be be
orders of magnitude worst than the best case.

So, given that I'd pick a tree by default and only change to a hash
table if and when profiling shows that the tree is a performance
bottleneck for the application.
Jon Harrop
2009-06-11 04:30:21 UTC
Permalink
Post by Stephen J. Bevan
Post by Jon Harrop
Post by Stephen J. Bevan
Post by Jon Harrop
The bug in the run-time behind the hash table problem was reported many
years ago but was never addressed. I raised it again recently and was
told to fix it myself.
One has to wonder why you want to use a hash table in any language,
Performance. Hash tables are usually 10x faster than any tree-based
alternative.
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Real-time apps can use an incrementally-resized hash table implementation.
Post by Stephen J. Bevan
Post by Jon Harrop
This is simply wrong. The best-implemented purely functional trees are
typically 10x slower than a hash table. You should approach trees
with the assumption that you will pay a whopping performance
penalty.
We'll if we are going to call the Haskell quote factually incorrect
then I'd class your statement as factually incorrect too since it
completely overstates the case for hash tables and completely ignores
the worst case performance.
You should approach trees knowing that you'll get consistent
worst-case performance regardless of size...
Your response is certainly strictly worse that mine. I said "usually". I do
not regard insertion into a large hash table in a real-time app as "usual".
However, your last statement quoted here is disproven by the existence of
splay trees so it is certainly wrong.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Paul Rubin
2009-06-11 08:51:29 UTC
Permalink
Post by Jon Harrop
Post by Stephen J. Bevan
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Real-time apps can use an incrementally-resized hash table implementation.
How is resizing going to help with O(n) worst case access time?
Jon Harrop
2009-06-11 18:25:03 UTC
Permalink
Post by Paul Rubin
Post by Jon Harrop
Post by Stephen J. Bevan
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Real-time apps can use an incrementally-resized hash table
implementation.
How is resizing going to help with O(n) worst case access time?
Paul's data refers only to the worse case amortized O(n) cost of insertion
when a dynamically-resized hash table is resized. Not to worst case O(n)
access due to collisions.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Florian Weimer
2009-06-14 10:02:44 UTC
Permalink
Post by Paul Rubin
Post by Jon Harrop
Post by Stephen J. Bevan
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Real-time apps can use an incrementally-resized hash table implementation.
How is resizing going to help with O(n) worst case access time?
Randomized hashing can make that case sufficiently unlikely, even with
deliberate attacks.
Paul Rubin
2009-06-14 11:57:23 UTC
Permalink
Post by Florian Weimer
Randomized hashing can make that case sufficiently unlikely, even with
deliberate attacks.
http://www.cs.rice.edu/~scrosby/hash/ states:

Tim Peters and Solar Designer have claimed that it may be possible to
force collisions even in the case of keyed cryptographic or universal
hashing, by statistically attempting to identify, due to detectable
processing latency, whether two items collide or not. If this attack
is possible, it would probably require a signifigant number of probes,
perhaps greater than the cost of the attack itself, but would have the
potential to attack any hash table that didn't have its key altered
regularily. It is unknown if this attack is practical.

Further down it says:

I highly reccomend not using ad-hoc colutions or simple keying of the
existing hash function. The security landscape is littered with broken
cryptographic operations and protocols. We suggest that if you do not
use universal hashing, you use a trusted reliable algorithm borrowed
from someone else rather than reimplement something likely to be
broken. I wouldn't invent my own hash function; I advise the same of
almost everyone else.

Using balanced trees instead of hashing nicely sidesteps this whole issue.
Stephen J. Bevan
2009-06-11 13:33:24 UTC
Permalink
Post by Jon Harrop
Post by Stephen J. Bevan
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Real-time apps can use an incrementally-resized hash table implementation.
I agree re-sizing improves the average case but it cannot guarantee to
improve the worst case.
Post by Jon Harrop
Post by Stephen J. Bevan
You should approach trees knowing that you'll get consistent
worst-case performance regardless of size...
Your response is certainly strictly worse that mine. I said
"usually". I do not regard insertion into a large hash table in a
real-time app as "usual".
The reader has no idea what you consider to be usual and instead will
be reading with an eye to applying it to their domain. I avoided
"usually" and stated the performance spectrum. Quite how this can be
strictly worse given that it is more accurate is not clear to me
unless ...
Post by Jon Harrop
However, your last statement quoted here is disproven by the existence of
splay trees so it is certainly wrong.
My last quote sentence is "You should approach trees knowing that
you'll get consistent worst-case performance regardless of size..."
and I assumed it was clear that we are talking about balanced trees in
this context but given your reference to a splay tree it would appear
not. So, if that is why you consider the statement to be strictly
worse then let's remove the ambiguity so that it reads as "You should
approach balanced trees knowing that you'll get consistent worst-case
performance regardless of size..."
Jon Harrop
2009-06-11 20:30:35 UTC
Permalink
Post by Stephen J. Bevan
Post by Jon Harrop
Post by Stephen J. Bevan
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Real-time apps can use an incrementally-resized hash table
implementation.
I agree re-sizing improves the average case but it cannot guarantee to
improve the worst case.
On the contrary, the sole purpose of incremental resizing is to guarantee
non-amortized O(1) worst case complexity.
Post by Stephen J. Bevan
Post by Jon Harrop
Post by Stephen J. Bevan
You should approach trees knowing that you'll get consistent
worst-case performance regardless of size...
Your response is certainly strictly worse that mine. I said
"usually". I do not regard insertion into a large hash table in a
real-time app as "usual".
The reader has no idea what you consider to be usual and instead will
be reading with an eye to applying it to their domain.
Regardless, the problem is not an issue in most domains and is a solved
problem in those where it would otherwise be an issue.
Post by Stephen J. Bevan
I avoided
"usually" and stated the performance spectrum. Quite how this can be
strictly worse given that it is more accurate...
Your statement was strictly worse because it was wrong.
Post by Stephen J. Bevan
Post by Jon Harrop
However, your last statement quoted here is disproven by the existence of
splay trees so it is certainly wrong.
My last quote sentence is "You should approach trees knowing that
you'll get consistent worst-case performance regardless of size..."
and I assumed it was clear that we are talking about balanced trees in
this context but given your reference to a splay tree it would appear
not.
Fair enough. I assumed we were talking about all hash tables and not just
whatever OCaml happens to implement.
Post by Stephen J. Bevan
So, if that is why you consider the statement to be strictly
worse then let's remove the ambiguity so that it reads as "You should
approach balanced trees knowing that you'll get consistent worst-case
performance regardless of size..."
That's what Real World Haskell should have said, IMHO.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Paul Rubin
2009-06-11 22:38:13 UTC
Permalink
Post by Jon Harrop
On the contrary, the sole purpose of incremental resizing is to guarantee
non-amortized O(1) worst case complexity.
How does it guarantee that?
Post by Jon Harrop
Regardless, the problem is not an issue in most domains and is a solved
problem in those where it would otherwise be an issue.
I think you don't get to decide what domain any particular application
is in, or what the probability distribution of domains are. Most of
the problems plaguing us in the real world are because someone thought
a worst case scenario was much less likely than it actually turned out
to be.
Jon Harrop
2009-06-12 00:34:02 UTC
Permalink
Post by Paul Rubin
Post by Jon Harrop
On the contrary, the sole purpose of incremental resizing is to guarantee
non-amortized O(1) worst case complexity.
How does it guarantee that?
You just perform part of the resizing every time you insert.
Post by Paul Rubin
Post by Jon Harrop
Regardless, the problem is not an issue in most domains and is a solved
problem in those where it would otherwise be an issue.
I think you don't get to decide what domain any particular application
is in, or what the probability distribution of domains are. Most of
the problems plaguing us in the real world are because someone thought
a worst case scenario was much less likely than it actually turned out
to be.
Sure.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Paul Rubin
2009-06-12 02:06:02 UTC
Permalink
Post by Jon Harrop
Post by Paul Rubin
Post by Jon Harrop
On the contrary, the sole purpose of incremental resizing is to guarantee
non-amortized O(1) worst case complexity.
How does it guarantee that?
You just perform part of the resizing every time you insert.
Ok, that's about the complexity of resizing, not the complexity of
lookups or updates.
Jon Harrop
2009-06-12 15:26:04 UTC
Permalink
Post by Paul Rubin
Post by Jon Harrop
Post by Paul Rubin
Post by Jon Harrop
On the contrary, the sole purpose of incremental resizing is to
guarantee non-amortized O(1) worst case complexity.
How does it guarantee that?
You just perform part of the resizing every time you insert.
Ok, that's about the complexity of resizing, not the complexity of
lookups or updates.
Yes, this thread has only been about the complexity of insertion so far.

You can address the worst case complexity during collisions by using a
different data structure for your buckets. However, if that is an issue in
practice then you're doing something wrong and are not benefitting from
hash tables anyway.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Paul Rubin
2009-06-12 15:38:07 UTC
Permalink
Post by Jon Harrop
You can address the worst case complexity during collisions by using a
different data structure for your buckets. However, if that is an issue in
practice then you're doing something wrong and are not benefitting from
hash tables anyway.
The worst case for collisions is that all keys hash to the same hash
code, so only one bucket ever gets used. Yes, that means you're not
benefiting from hash tables. What you've done wrong is used a hash
table when it doesn't work. You can address this by using something
like balanced trees in the buckets, but you might as well have just
used them in the first place.
Jon Harrop
2009-06-12 20:11:19 UTC
Permalink
Post by Paul Rubin
Post by Jon Harrop
You can address the worst case complexity during collisions by using a
different data structure for your buckets. However, if that is an issue
in practice then you're doing something wrong and are not benefitting
from hash tables anyway.
The worst case for collisions is that all keys hash to the same hash
code, so only one bucket ever gets used. Yes, that means you're not
benefiting from hash tables. What you've done wrong is used a hash
table when it doesn't work. You can address this by using something
like balanced trees in the buckets, but you might as well have just
used them in the first place.
Exactly.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Stephen J. Bevan
2009-06-12 04:26:09 UTC
Permalink
Post by Jon Harrop
Post by Stephen J. Bevan
I agree re-sizing improves the average case but it cannot guarantee to
improve the worst case.
On the contrary, the sole purpose of incremental resizing is to guarantee
non-amortized O(1) worst case complexity.
Do you mean the complexity of insert/search or the complexity of
something else. If you mean insert/search then do you have a citation
for or could you sketch the proof? If you mean something else then we
are not talking about the same thing, I'm interested in the complexity
of insert/search.
Post by Jon Harrop
Post by Stephen J. Bevan
The reader has no idea what you consider to be usual and instead will
be reading with an eye to applying it to their domain.
Regardless, the problem is not an issue in most domains and is a
solved problem in those where it would otherwise be an issue.
Since you are just re-stating your point we clearly aren't going to
agree on this so we can agree to disagree on the merits of qualifiers
like "usually" and "most" when giving advice about performance.
Post by Jon Harrop
Post by Stephen J. Bevan
I avoided
"usually" and stated the performance spectrum. Quite how this can be
strictly worse given that it is more accurate...
Your statement was strictly worse because it was wrong.
The context for this is "well-implemented trees" since that's the
quote from the Haskell book. I don't know what the authors meant but
that but my interpretation is balanced trees and so I didn't see the
need to write "well-implemented" or "balanced" given the context. I
should have realised that it does not pay to assume context in this
discussion and so should have spelled it out in full.
Post by Jon Harrop
Post by Stephen J. Bevan
Post by Jon Harrop
However, your last statement quoted here is disproven by the existence of
splay trees so it is certainly wrong.
My last quote sentence is "You should approach trees knowing that
you'll get consistent worst-case performance regardless of size..."
and I assumed it was clear that we are talking about balanced trees in
this context but given your reference to a splay tree it would appear
not.
Fair enough. I assumed we were talking about all hash tables and not just
whatever OCaml happens to implement.
What O'Caml happens to implement is what you chose to use as the basis
for your measurements in your O'Caml book. You can pick other hash
tables but unless they use some other technique for collision handling
then the results will be have the same big-O characteristics. Clearly
it is possible to use other techniques, a straightforward one is to
use a balanced tree instead of a link list. Should one therefore
criticise language implementations that only come with hash tables
that use linked lists?
Post by Jon Harrop
Post by Stephen J. Bevan
So, if that is why you consider the statement to be strictly
worse then let's remove the ambiguity so that it reads as "You should
approach balanced trees knowing that you'll get consistent worst-case
performance regardless of size..."
That's what Real World Haskell should have said, IMHO.
They wrote "well-implemented trees" which I agree is ambigous. I read
it as "balanced" since to me that ia a reasonable interpetation that
makes the claim true (for worst-case performance which is what I am
primarily interested in).
Paul Rubin
2009-06-12 04:48:12 UTC
Permalink
Post by Stephen J. Bevan
Post by Jon Harrop
Fair enough. I assumed we were talking about all hash tables and
not just whatever OCaml happens to implement.
What O'Caml happens to implement is what you chose to use as the basis
for your measurements in your O'Caml book.
If arbitrary implementations are allowed then we should consider
cache-oblivious balanced trees. It wouldn't surprise me if they can
beat hash tables even in the average case, under the sorts of wishful
assumptions usually made when analyzing the performance of hash
tables. Of course we already know what happens in the absence of
those assumptions.
George Neuner
2009-06-13 21:00:47 UTC
Permalink
Post by Jon Harrop
Post by Stephen J. Bevan
Post by Jon Harrop
Post by Stephen J. Bevan
That's great if you don't care about things going to hell if you hit
the worst case performance which can be 100x slower for hash tables
as your own test programs show below.
Real-time apps can use an incrementally-resized hash table
implementation.
I agree re-sizing improves the average case but it cannot guarantee to
improve the worst case.
On the contrary, the sole purpose of incremental resizing is to guarantee
non-amortized O(1) worst case complexity.
Post by Stephen J. Bevan
Post by Jon Harrop
Post by Stephen J. Bevan
You should approach trees knowing that you'll get consistent
worst-case performance regardless of size...
Your response is certainly strictly worse that mine. I said
"usually". I do not regard insertion into a large hash table in a
real-time app as "usual".
Jon, have you ever done any real time programming? And I'm not
talking about GUIs or other human interaction programming where, apart
from an annoyance factor, it really doesn't matter whether a function
takes 30ns or 30 seconds.

Talking about non-amortized complexity is totally misleading. A RT
program MUST consider any runtime costs associated with using a data
structure. Even talking about amortized cost in the context of RT
programming is misleading because the focus in RT is always on the
worst case.

HRT programs never use dynamic allocation - if they need any kind of
flexible data structure the space is always pre-allocated and any
dynamic links (pointer chains, etc.) are arranged to be deterministic.
A tree, for example, if used, will never be rebalanced.

SRT programs may use dynamic allocation. However you still can't
ignore the resize because if the table is resized atomically it will
either steal cycles from other tasks or be unavailable for the
duration of the operation. If resized incrementally, the worst case
search time doubles because you need to search both tables to be sure
an entry is not found.

Talking about O(1) vs O(whatever) is also misleading. For RT
programming the theoretical order of a computation is irrelevant ...
all that matters is the expected worst case running time. [Obviously
you'd try to use the most efficient algorithm possible, but in the end
it's only the running time that matters. For example, you might
deliberately choose to use a mergesort rather than a quicksort because
the mergesort has better worst case behavior even though the constant
multiplier is higher.]

With closed hash tables, you also have to consider the complexity of
the different hash functions - is the rehash the same as the initial
hash and how many times might the rehash be called. When resizing,
the new functions have to be considered. For a HRT program, the
difference between a hash function that takes 1ns to compute and a
function that takes 2ns may be important.

George
Ertugrul Söylemez
2009-06-11 01:53:31 UTC
Permalink
Post by Jon Harrop
Post by Ertugrul Söylemez
Post by Jon Harrop
I do not believe I could recover the costs because the Haskell
market is just not commercially viable yet. Moreover, this is a
chicken and egg problem: many people will not invest any serious
effort in Haskell until these fundamental problems are addressed
and they will not be addressed by industry because it is not
commercially viable to do so. Furthermore, the academics are not
likely to address such problems because it does not constitute
compelling research.
In other words, Haskell has not reached critical mass. IMHO, it never will.
Well, in the last few years, Haskell development progressed quickly.
In what sense? They're partway to catching up with OCaml as far as IDE
support is concerned but they're still a decade behind F#. They've
invested a lot of time in their own proprietary package system and
have a thousand packages but still poor support for mainstream package
systems like apt and their libraries don't even include a decent hash
table implementation. The core of GHC is not only buggy (e.g. the hash
table problem) but even has serious design flaws that nobody knows how
to address. I cannot even see any evidence that anyone is even
attempting to address them.
It's a sad truth that Haskell has not made it into the commercial market
yet. If anyone would make money with the language or a compiler
package, then it would progress much faster, I think. It has worked for
Linux as well, which has been a nerdy tech toy in its early ages.

The language itself is great IMO, because it's concise, elegant and
interesting. Currently I'm using F# at work, but I'd love to switch to
Haskell.
Post by Jon Harrop
There has certainly been a lot of noise surrounding Haskell but
virtually no progress, IMHO.
A few years ago, GHC produced much slower code and there were only a
handful libraries, most of which were incomplete or very limited. This
has changed. Although still most libraries are incomplete, there are
much more useful libraries by now.
Post by Jon Harrop
Post by Ertugrul Söylemez
If new standards could be created quicker and there were more libraries,
Lack of documentation and interoperability are much bigger problems, IMHO.
The documentation is there. It's rather that there is actually too much
documentation available, particularly about monads, and most of it is
either redundant or badly written. Beginners don't know where to start.
Real World Haskell is a first step, but as far as I've seen it needs a
lot of improvement.
Post by Jon Harrop
Post by Ertugrul Söylemez
then it could well get commercially viable. As a language it
definitely has the potential.
Perhaps it might become viable for specific domains but I cannot see a
language with such poor support for large-scale programming garnering
any serious traction in industry.
I don't think that language-level support is poor. It's actually quite
good. What's really missing is a package manager, which better
interoprerates with system-level package management, FFIs for more
languages and better support for dynamic linking.

I'd also like to see explicit OOP support together with FFIs to common
OOP languages.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Jon Harrop
2009-06-11 03:21:16 UTC
Permalink
Post by Ertugrul Söylemez
Post by Jon Harrop
In what sense? They're partway to catching up with OCaml as far as IDE
support is concerned but they're still a decade behind F#. They've
invested a lot of time in their own proprietary package system and
have a thousand packages but still poor support for mainstream package
systems like apt and their libraries don't even include a decent hash
table implementation. The core of GHC is not only buggy (e.g. the hash
table problem) but even has serious design flaws that nobody knows how
to address. I cannot even see any evidence that anyone is even
attempting to address them.
It's a sad truth that Haskell has not made it into the commercial market
yet. If anyone would make money with the language or a compiler
package, then it would progress much faster, I think. It has worked for
Linux as well, which has been a nerdy tech toy in its early ages.
You need more than money. Indeed, I would not even put money high on the
list. The main problem that stifles development of these languages is that
the core people involved have no motivation to make it a good language for
real users. They are all researchers. Combine that with the fact that many
members of the community are extremely anti-industry and anti-evolution and
you've got a recipe for disaster. I was shouted down on the caml-list just
for trying to discuss how OCaml might be improved.

Frankly, I think the future is bleak for Linux. Five years ago it had a
selection of really decent languages and implementations. Today, none of
the standalone FPL implementations have a performant multicore-capable
run-time and nobody is even working on building a suitable VM. Sun's JVM
had some promise but apparently the JVM is never likely to see tail calls
despite a working implementation in MLVM, due to political issues.
Post by Ertugrul Söylemez
Post by Jon Harrop
Lack of documentation and interoperability are much bigger problems, IMHO.
The documentation is there. It's rather that there is actually too much
documentation available, particularly about monads, and most of it is
either redundant or badly written. Beginners don't know where to start.
Real World Haskell is a first step, but as far as I've seen it needs a
lot of improvement.
I meant good documentation, of course. :-)
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
then it could well get commercially viable. As a language it
definitely has the potential.
Perhaps it might become viable for specific domains but I cannot see a
language with such poor support for large-scale programming garnering
any serious traction in industry.
I don't think that language-level support is poor. It's actually quite
good. What's really missing is a package manager, which better
interoprerates with system-level package management, FFIs for more
languages and better support for dynamic linking.
Use apt.
Post by Ertugrul Söylemez
I'd also like to see explicit OOP support together with FFIs to common
OOP languages.
That's a really tall order and another solved problem on .NET...
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Dirk Thierbach
2009-06-05 06:05:31 UTC
Permalink
Post by raould
i think i get it that laziness can lead to big space usage.
BTW, sometimes too much strictness can also be the cause. IIRC some
examples were discussed on the Haskell mailing list.
Post by raould
and i guess there is some debate about how easy it is for programmers
to see "oh this code right here could lead to a space leak!"
I know that many people today call that a "space leak", but personally
I still don't like that expression -- it doesn't "leak" in the original
sense, i.e. there's no allocated memory which isn't reclaimed. It's
just a pile of computations that are evaluated too late (or sometimes
too early).
Post by raould
so, how could/do people see that something could be a space leak?
Do profiling (e.g. with GHC). The strictness analyzer of the compiler
can also often help (so compile with -O in GHC). There are also some
typical "bad patterns" one can watch out for, e.g. left fold vs. right
fold. I think there are also a number of "good patterns", but
I suppose I use them mostly unconsciously, so I couldn't make them
explicit or put my finger on some critical characteristic.

There's a number of strategies to avoid unnecessary space usage,
e.g. to unbox "primitive" values (numbers) in data structures when
appropriate. Or to use bang patterns or "False guards" to force
evaluation (that's usually more readable than "seq").
Post by raould
is there anything about it that could be automated?
One idea that came up on comp.lang.haskell was that it would be nice
if the compiler could infer some asymptotic space bounds, at least for
some arguments. Or if the programmer could specify his/her expectations
about these bounds, and then let the compiler check it. There are
research papers about type systems which can enforce space bounds, so
in theory this is possible. But it hasn't been tried for Haskell yet,
AFAIK.

And just for the record, IMO space usage is not a question of
"robustness". For me, "robustness" means "correct behaviour even in
unusual circumstances". Which is something Haskell is very good at.

There's plenty of imperative algorithms that have really bad
asymptotic space behaviour, so one could also claim using the same
reasoning that "C is not robust". It would be more to the point to
say that Haskell offers *less direct control* over space usage. Which
is certainly something that could be improved.

- Dirk (with EOT on the "robust" part)
Adrian Hey
2009-06-08 07:20:24 UTC
Permalink
Hello Dirk,
Post by Dirk Thierbach
And just for the record, IMO space usage is not a question of
"robustness". For me, "robustness" means "correct behaviour even in
unusual circumstances". Which is something Haskell is very good at.
Apart from the (un?)usual circumstances of running out of memory :-)

I'm afraid your definition of robustness would be unacceptable even for
most ordinary industrial uses, let alone safety critical applications.

It's not really very satisfactory for "bucket loads of RAM + swap space"
server/workstation/desktop apps either IMO, but you can probably get
away with it here as occasional crashes seem to be regarded as normal
and acceptable program behaviour anyway.

But if you're designing a (hardware) product of any kind you need a
definite figure for the minimum memory needed by any embedded s/w in
order to make a reliable product. Alternatively the embedded s/w
designers know the memory constraints they're working with and
proceed accordingly.
Post by Dirk Thierbach
There's plenty of imperative algorithms that have really bad
asymptotic space behaviour, so one could also claim using the same
reasoning that "C is not robust".
I don't think so, because you would either know their space behaviour
and budget accordingly or avoid the use of such algorithms altogether.

The trouble with Haskell isn't so much that the space behaviour is
good/bad, the trouble is that it's unknown and unpredictable.

C certainly sucks in many ways, but (as JH pointed out) the one good
thing about it is that the space behaviour of a given C program will be
uniform across all platforms/compilers/optimisation settings (at worst
differing only in known constant factors).

There's a thread about this issue right now on the ghc-users mailing
list:
http://www.haskell.org/pipermail/glasgow-haskell-users/2009-June/017359.html

Interestingly Simon M states that "GHC will happily combine them with
CSE and possibly also lift them to the top-level; both transformations
might have a big impact on space behaviour." Yet more confusion and
ambiguity re. CSE and similar transformations :-)
Post by Dirk Thierbach
It would be more to the point to
say that Haskell offers *less direct control* over space usage. Which
is certainly something that could be improved.
It's difficult to see how this could ever be done with Haskell, for
cultural reasons mainly (not technical reasons). I think we need to
get back in touch with the imperative realities of life and recognise
that whatever benefits "pure functions" may offer as mathematical
abstractions, ultimately any real computation on any real machine (even
"pure" expression evaluation) is an *act* that does have real world
observable side effects that must be understood and controlled.

I don't believe that most in the Haskell community would even accept
that a language that did address these issues properly was "purely
functional". e.g. given the controversy that surrounds the earlier
mentioned (and IMO very conservative) top level <- bindings proposal.

Regards
--
Adrian Hey
Dirk Thierbach
2009-06-08 17:35:20 UTC
Permalink
Post by Adrian Hey
Post by Dirk Thierbach
And just for the record, IMO space usage is not a question of
"robustness". For me, "robustness" means "correct behaviour even in
unusual circumstances". Which is something Haskell is very good at.
Apart from the (un?)usual circumstances of running out of memory :-)
Nearly every program for a non-trivial problem will sooner or later run out
of memory, given a large enough input.
Post by Adrian Hey
I'm afraid your definition of robustness would be unacceptable even for
most ordinary industrial uses, let alone safety critical applications.
But "acceptable for industrial uses" or "acceptable for safety critical
applications" is not the same as "robust". "Robustness" is just one
criterion. There are other criteria like for example "real-time
capable" or "memory bounded".

Of course you're free to use "robust" in any way you like. I just
wanted to point out that at least I use the word differently, and if
you insist using it your way, that can lead to confusion. Which is bad
for communication. And given the question of the original poster, it
looks like I'm not the only one.

Is it really too much to ask to use "bad at controlling space usage" or
something like that instead of "robust"?
Post by Adrian Hey
It's not really very satisfactory for "bucket loads of RAM + swap
space" server/workstation/desktop apps either IMO, but you can
probably get away with it here as occasional crashes seem to be
regarded as normal and acceptable program behaviour anyway.
I don't know what kind of Haskell programs you write, but my Haskell
programs don't have "occasional crashes". And it's certainly not
acceptable to have them. OTOH, there's no question that Haskell is not
suitable for, say, embdedded systems. And no one says it ought to.
Post by Adrian Hey
But if you're designing a (hardware) product of any kind you need a
definite figure for the minimum memory needed by any embedded s/w in
order to make a reliable product.
Yes. So, for embedded systems, Haskell is out. As are probably all
garbage collected languages. But that doesn't mean that those languages
are not "robust".
Post by Adrian Hey
Alternatively the embedded s/w designers know the memory constraints
they're working with and proceed accordingly.
Yes, of course. But we're not talking about embedded systems.
Post by Adrian Hey
Post by Dirk Thierbach
There's plenty of imperative algorithms that have really bad
asymptotic space behaviour, so one could also claim using the same
reasoning that "C is not robust".
I don't think so, because you would either know their space behaviour
and budget accordingly or avoid the use of such algorithms altogether.
The point was not that one can avoid to use a specific algorithm
(which is only possible probably if you're doing "trivial" stuff, like
for embdedded systems), the point was that it's not legitimate
to conclude from "there are programs that have bad space usage"
that "this language is not robust".
Post by Adrian Hey
The trouble with Haskell isn't so much that the space behaviour is
good/bad, the trouble is that it's unknown and unpredictable.
It's certainly not "unknown"; given a fixed compiler, it's actually
completely determined. It's also not completely unpredictable: with a
bit of experience, one can usually say in advance in many cases what
the space usage is going to be. Even across compilers.

What IS bad is that this doesn't work always. There can be surprises,
and cases where the algorithm is difficult enough to make predictions
about space usage hard, or cases where you have to jump through hoops
to get space usage down. But that's not really news, it has been like
this for a long time, and one can still write Haskell programs that
are quite useful in spite of that.

So it's not really like this white/black picture that you're trying
to paint.
Post by Adrian Hey
C certainly sucks in many ways, but (as JH pointed out) the one good
thing about it is that the space behaviour of a given C program will be
uniform across all platforms/compilers/optimisation settings (at worst
differing only in known constant factors).
Yes. So C is a good language for embedded systems, while Haskell is not.
OTOH, Haskell is a good language for complicated algorithms, while C
is not.

Use the right tool for the job. Not all programming languages are
equally suited for all applications. That's the reason there are different
languages in the first place.
Post by Adrian Hey
There's a thread about this issue right now on the ghc-users mailing
http://www.haskell.org/pipermail/glasgow-haskell-users/2009-June/017359.html
Interestingly Simon M states that "GHC will happily combine them with
CSE and possibly also lift them to the top-level; both transformations
might have a big impact on space behaviour." Yet more confusion and
ambiguity re. CSE and similar transformations :-)
Yes. And that's a direct consequence, again, that a Haskell program
specifies in the first place "what" to do, and only indirectly (if at
all) "how" to do it (i.e., which reduction strategy to use). On the one
hand, that is good, because it gives the compiler for freedom to apply
optimizations. On the other hand, it's bad, because there is no
*guarantee* about secondary characteristics like space and time complexity.

That's why I really like the idea of *additionally* specifying
those complexities. And then let the compiler figure out if it can
automatically meet these requirements by choosing the correct evaluation
strategy (maybe with a few more hints in the right places).
Post by Adrian Hey
Post by Dirk Thierbach
It would be more to the point to say that Haskell offers *less
direct control* over space usage. Which is certainly something that
could be improved.
It's difficult to see how this could ever be done with Haskell, for
cultural reasons mainly (not technical reasons).
I don't consider myself qualified to speculate about "cultural reasons"
and "the" Haskell community. Maybe you do, but I don't.
Post by Adrian Hey
I think we need to get back in touch with the imperative realities
of life and recognise that whatever benefits "pure functions" may
offer as mathematical abstractions, ultimately any real computation
on any real machine (even "pure" expression evaluation) is an *act*
that does have real world observable side effects that must be
understood and controlled.
And I think that this misses the point of this discussion completely.
The "observable side effects" (unless you mean by that space usage
only) are better be dealt with the appropriate abstractions, say,
monads.

Space usage is dependent on the evaluation strategy, and has little to
with the "pure functional" vs. "imperative" approach. With a strict
evaluation strategy, space usage is much easier to figure out. OTOH,
sometimes lazy algorithms are much more elegant and a pleasure to
write (which is what I miss most when programming in, say, OCaml).

So, again, it's not black vs. white. Experience has shown that
sometimes (not always) strict evaluation is necessary, and also that
the current instruments Haskell has to deal with it are not simple
enough to use. So that's the problem that has to be fixed. And Haskell
is still enough of a research language to try out new ideas.

But there's no need to throw out the child with the bathwater, and
complain that "all this lazy pure functional stuff is nonsense,
and we should go back to use imperative, simple programs". Nobody
forces you to use Haskell. Nobody says that Haskell should be the one
and only language. If I was to write a program for an embdedded system,
I would use C (or maybe Forth), and not Haskell.
Post by Adrian Hey
I don't believe that most in the Haskell community would even accept
that a language that did address these issues properly was "purely
functional".
Huh? There is already research about purely functional languages
in combination with "type and effect systems", or, as I mentioned, the
type systems that give bounds for space usage. That doesn't make the core
language any less purely functional.
Post by Adrian Hey
e.g. given the controversy that surrounds the earlier
mentioned (and IMO very conservative) top level <- bindings proposal.
I don't really understand why you are so worked up about the top level
bindings either, but this posting is already long enough.

I think I'll EOT soon, as all this is more about philosophy and opinion
than about useful practical stuff, and discussing opinions isn't really
that interesting.

I mainly wanted to point out that it has been long known and
acknowledged that controlling space usage in Haskell can be hard, that
there are nevertheless ways to deal with that and in many cases it
isn't really a problem, and that I found the idea of additionally
specifying the complexity an interesting one. That's all.

- Dirk
Jon Harrop
2009-06-08 19:35:30 UTC
Permalink
Post by Dirk Thierbach
Post by Adrian Hey
Post by Dirk Thierbach
And just for the record, IMO space usage is not a question of
"robustness". For me, "robustness" means "correct behaviour even in
unusual circumstances". Which is something Haskell is very good at.
Apart from the (un?)usual circumstances of running out of memory :-)
Nearly every program for a non-trivial problem will sooner or later run
out of memory, given a large enough input.
How is that relevant to this discussion about predictability?
Post by Dirk Thierbach
Post by Adrian Hey
I'm afraid your definition of robustness would be unacceptable even for
most ordinary industrial uses, let alone safety critical applications.
But "acceptable for industrial uses" or "acceptable for safety critical
applications" is not the same as "robust". "Robustness" is just one
criterion...
If software does not meet that one criterion then it is not acceptable.
Post by Dirk Thierbach
Of course you're free to use "robust" in any way you like. I just
wanted to point out that at least I use the word differently...
In what context?
Post by Dirk Thierbach
Is it really too much to ask to use "bad at controlling space usage" or
something like that instead of "robust"?
Unpredictable means "will randomly break" which is synonymous with "not
robust". That is way beyond "bad" and well into "unusable", IMHO.
Post by Dirk Thierbach
Post by Adrian Hey
It's not really very satisfactory for "bucket loads of RAM + swap
space" server/workstation/desktop apps either IMO, but you can
probably get away with it here as occasional crashes seem to be
regarded as normal and acceptable program behaviour anyway.
I don't know what kind of Haskell programs you write, but my Haskell
programs don't have "occasional crashes".
What programs?
Post by Dirk Thierbach
And it's certainly not
acceptable to have them. OTOH, there's no question that Haskell is not
suitable for, say, embdedded systems. And no one says it ought to.
Is Haskell suitable for any programming?
Post by Dirk Thierbach
Post by Adrian Hey
Post by Dirk Thierbach
There's plenty of imperative algorithms that have really bad
asymptotic space behaviour, so one could also claim using the same
reasoning that "C is not robust".
I don't think so, because you would either know their space behaviour
and budget accordingly or avoid the use of such algorithms altogether.
The point was not that one can avoid to use a specific algorithm
(which is only possible probably if you're doing "trivial" stuff, like
for embdedded systems), the point was that it's not legitimate
to conclude from "there are programs that have bad space usage"
that "this language is not robust".
The observation was that Haskell programs have *unpredictable* space usage.
Hence the conclusion is entirely valid.
Post by Dirk Thierbach
Post by Adrian Hey
The trouble with Haskell isn't so much that the space behaviour is
good/bad, the trouble is that it's unknown and unpredictable.
It's certainly not "unknown"; given a fixed compiler, it's actually
completely determined.
You mean it is theoretically possible to quantify the space consumption from
the program and compiler internals?

If you honestly believe that then you must also believe that a C compiler
than generates code that will unpredictably leak memory only fails to
be "robust" if the internal algorithm that determines whether or not there
is a leak is deterministic.
Post by Dirk Thierbach
So it's not really like this white/black picture that you're trying
to paint.
Other languages are predictable but Haskell is not. What is not black and
white about that?
Post by Dirk Thierbach
Post by Adrian Hey
C certainly sucks in many ways, but (as JH pointed out) the one good
thing about it is that the space behaviour of a given C program will be
uniform across all platforms/compilers/optimisation settings (at worst
differing only in known constant factors).
Yes. So C is a good language for embedded systems, while Haskell is not.
OTOH, Haskell is a good language for complicated algorithms, while C
is not.
What are unpredictable languages good for?
Post by Dirk Thierbach
Post by Adrian Hey
There's a thread about this issue right now on the ghc-users mailing
http://www.haskell.org/pipermail/glasgow-haskell-users/2009-June/017359.html
Post by Dirk Thierbach
Post by Adrian Hey
Interestingly Simon M states that "GHC will happily combine them with
CSE and possibly also lift them to the top-level; both transformations
might have a big impact on space behaviour." Yet more confusion and
ambiguity re. CSE and similar transformations :-)
Yes. And that's a direct consequence, again, that a Haskell program
specifies in the first place "what" to do, and only indirectly (if at
all) "how" to do it (i.e., which reduction strategy to use). On the one
hand, that is good, because it gives the compiler for freedom to apply
optimizations. On the other hand, it's bad, because there is no
*guarantee* about secondary characteristics like space and time complexity.
That's why I really like the idea of *additionally* specifying
those complexities. And then let the compiler figure out if it can
automatically meet these requirements by choosing the correct evaluation
strategy (maybe with a few more hints in the right places).
How would that be any better than today's impure FPLs?
Post by Dirk Thierbach
Space usage is dependent on the evaluation strategy, and has little to
with the "pure functional" vs. "imperative" approach.
They are related.
Post by Dirk Thierbach
So, again, it's not black vs. white. Experience has shown that
sometimes (not always) strict evaluation is necessary, and also that
the current instruments Haskell has to deal with it are not simple
enough to use. So that's the problem that has to be fixed.
Do you believe the problems can be fixed?
Post by Dirk Thierbach
I mainly wanted to point out that it has been long known and
acknowledged that controlling space usage in Haskell can be hard, that
there are nevertheless ways to deal with that and in many cases it
isn't really a problem...
But it could be a showstopper if Haskell were used in a production
environment.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Paul Rubin
2009-06-09 05:54:52 UTC
Permalink
Post by Dirk Thierbach
Yes. So, for embedded systems, Haskell is out. As are probably all
garbage collected languages. But that doesn't mean that those
languages are not "robust".
Hedgehog Lisp (search for it) is rather nice for midsized embedded
systems (mobile phones etc) and has a generational gc. Javacard is
the only language I know of that is running on BILLIONS of embedded
computers (e.g. inside the SIM card of every GSM phone, iirc) and at
least some configurations of it (including some with quite small
amounts of ram, like 6 kb in the old Java rings) have garbage
collection. But I don't know if the version running in most phones
have gc.
Adrian Hey
2009-06-09 15:19:44 UTC
Permalink
Hello Dirk,
Post by Dirk Thierbach
Is it really too much to ask to use "bad at controlling space usage" or
something like that instead of "robust"?
Yes, I'm afraid so :-)

By "robust" I mean under *no circumstances whatsoever* (short of
hardware failure possibly) will a program ever fail in an uncontrolled
manner (IOW "crash", as we say). If it is allowed to fail at all, it
is a failure to provide some non-critical service, in a controlled
manner that does not impact on the provision of critical services.

I know what you say is probably representative what most of the Haskell
community would say. So I don't want to say to much in response to most
of your post, other than to state for the record that I disagree with
just about everything you wrote, but a blow by blow response to
every sentence would just be too long and boring :-(
Post by Dirk Thierbach
Post by Adrian Hey
I think we need to get back in touch with the imperative realities
of life and recognise that whatever benefits "pure functions" may
offer as mathematical abstractions, ultimately any real computation
on any real machine (even "pure" expression evaluation) is an *act*
that does have real world observable side effects that must be
understood and controlled.
And I think that this misses the point of this discussion completely.
The "observable side effects" (unless you mean by that space usage
only) are better be dealt with the appropriate abstractions, say,
monads.
I think that you've missed the point of this discussion completely.
I *am* talking about memory useage primarily, but also cpu time usage
and latency too for example. No real computation is entirely free of
side effects. They matter, even if they are not "semantically
observable" in the ordinary sense. The only reason they are not
semantically observable is that the language semantics don't (currently)
address these issues. But a program crash because of an exhausted heap
or a "stack overflow" is still an observable side effect to it's users.

Regards
--
Adrian Hey
Paul Rubin
2009-06-09 16:44:58 UTC
Permalink
Post by Adrian Hey
By "robust" I mean under *no circumstances whatsoever* (short of
hardware failure possibly) will a program ever fail in an uncontrolled
manner (IOW "crash", as we say). If it is allowed to fail at all, it
is a failure to provide some non-critical service, in a controlled
manner that does not impact on the provision of critical services.
There are services whose correctness is critical and services whose
availability is critical. Something like realtime avionics code
better not, er, crash. It is better for it to give an incorrect
answer that causes the plane to fly a few mph too fast or something
like that.

Something like a compiler, on the other hand, better not produce
incorrect code (which could then run on an airplane and kill people).
It is best that the compiler produce correct code, of course. But if
the compiler fails to produce any code at all (such as by running out
of memory), that's not so bad. It just causes a development snag, a
mere annoyance by comparison to producing incorrect code.

I think some compilers for safety or security critical critical
languages have been written in Haskell and deployed into production.
That seems to me to be a very sensible approach.
Adrian Hey
2009-06-09 18:42:49 UTC
Permalink
Hello Paul,
Post by Paul Rubin
Something like a compiler, on the other hand, better not produce
incorrect code (which could then run on an airplane and kill people).
It is best that the compiler produce correct code, of course. But if
the compiler fails to produce any code at all (such as by running out
of memory), that's not so bad. It just causes a development snag, a
mere annoyance by comparison to producing incorrect code.
I think some compilers for safety or security critical critical
languages have been written in Haskell and deployed into production.
That seems to me to be a very sensible approach.
This was my original point about what Haskell was currently good for,
really. But I suspect Haskells designers aspire to greater things,
not just the file munger niche.

Regards
--
Adrian Hey
Paul Rubin
2009-06-05 02:22:03 UTC
Permalink
Post by Ertugrul Söylemez
Although you have to learn semantics first in Haskell to predict its
memory behaviour, the code produces correct results in most cases, even
if you're leaking space. Bugs are very rare.
If the space leak makes your program crash instead of finishing, which
it often does, that is an incorrect result.
Adrian Hey
2009-05-31 07:17:53 UTC
Permalink
Hello folks,

Well when in doubt try it out..
Post by Adrian Hey
Post by Ertugrul Söylemez
As frequently noted, Haskell compilers don't do CSE,
So why does ghc provide -fcse and -fno-cse flags? According to the
manual -fcse (turn on common sub-expression elimination) is implied
by -O.
http://www.haskell.org/ghc/docs/latest/html/users_guide/flag-reference.html
That said, I'm sure I can remember SPJ saying ghc didn't do CSE, so what
you say may well be true of ghc. But even if it is, the mere presence of
these flags indicates some confusion and ambiguity re. this in Haskell
land.
It does indeed appear to be the case that ghc does not do CSE (in
this case at least) even with -O and/or -fcse. As it seems like this
is probably about as easy case as one could imagine it looks to me like
ghc will never do CSE, despite the flags and what the manual says (which
is probably just as well).

Regards
--
Adrian Hey
Erik de Castro Lopo
2009-05-31 01:26:32 UTC
Permalink
Post by Adrian Hey
Hello Raould
Post by raould
also, i hope DDC continues on to be something of an in-production-
viable system.
http://www.haskell.org/haskellwiki/DDC
That does look interesting. I haven't looked at it seriously because it
prolly doesn't run on Windows (yet) and doesn't have any real
documentation (we've got to wait for Bens thesis).
Its also quite buggy at the moment :-(.

Ben has just handed his thesis to his supervisor and is also deep in
the middle of porting GHC to Sparc, but he has said that when all that
is done, he hopes to find some time to work on DDC.

Erik
--
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/
fft1976
2009-05-31 18:38:20 UTC
Permalink
Post by Erik de Castro Lopo
Ben has just handed his thesis to his supervisor and is also deep in
the middle of porting GHC to Sparc,
Grad students are always very busy wasting time.
Jon Harrop
2009-06-01 00:02:58 UTC
Permalink
Post by fft1976
Post by Erik de Castro Lopo
Ben has just handed his thesis to his supervisor and is also deep in
the middle of porting GHC to Sparc,
Grad students are always very busy wasting time.
Or "learning" as it is otherwise known. :-)
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Erik de Castro Lopo
2009-06-01 00:16:24 UTC
Permalink
Post by fft1976
Post by Erik de Castro Lopo
Ben has just handed his thesis to his supervisor and is also deep in
the middle of porting GHC to Sparc,
Grad students are always very busy wasting time.
Ben's 'porting GHC to Sparc' thing is actually a paid gig and earning
money so that one can eat should really not be considered wasting
time :-).

Erik
--
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/
Ertugrul Söylemez
2009-05-27 21:11:59 UTC
Permalink
Post by raould
cf. thread in which i take it Haskell is described as being perhaps
not something you want to use in
production. (http://groups.google.com/
group/comp.lang.functional/msg/2e3da091a4f912dd)
why is that? because laziness might rear its ugly performance head
unexpectedly at some arbitrary time after making the code live? or
some other reason(s) e.g. it just hasn't been stress tested in the
real world enough, so there are probably dangerous bugs in the
runtime?
I think, this is a topic, which you could discuss forever. That's why I
stopped responding at some point. Some of the points against Haskell
are valid, but laziness definitely isn't. It is a great virtue and
follows simple semantics, which any programmer can learn. Failing to
learn the semantics of the language, of course you write code the wrong
way following inappropriate design patterns. Some people don't get this
and blame laziness for their own incompetence.

If you have learned it, then memory leaks are much less likely than
forgetting to free memory or close a file handle in imperative
languages.

View it from this perspective: At work I'm stuck with C#. I often
found myself writing code with laziness in mind, which lead to quite
some nasty bugs. One of the most frequent such bugs happened when
trying to build a data structure lazily. Something like this:

static Blah xyz = () => ... xyz() ...

This is useful with tree structures or parsers (since I haven't found
any parser class in C# I had to write my own -- and yes, it's monadic).
Of course today I know the language semantics (again) and these bugs
have become very rare, but the point is: I was programming with Haskell
in mind, so naturally I made mistakes. I didn't expect xyz() to get
evaluated immediately, because with my Haskell-influenced intuition that
just seems unnatural to me.

Where Haskell programmers coming from the strict world get memory leaks,
strict programmers coming from the Haskell world get stack overflows.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
George Neuner
2009-05-28 01:56:37 UTC
Permalink
Post by Ertugrul Söylemez
static Blah xyz = () => ... xyz() ...
This is useful with tree structures or parsers (since I haven't found
any parser class in C# I had to write my own
http://www.antlr.org/
Post by Ertugrul Söylemez
-- and yes, it's monadic).
Antlr's parser's are not. But they are useful nonetheless. And
unlike most home spun parsers, they have the advantage of solid theory
behind them. [Your's might also, but I don't know that.]

George
Ertugrul Söylemez
2009-05-28 12:05:17 UTC
Permalink
Post by George Neuner
Post by Ertugrul Söylemez
static Blah xyz = () => ... xyz() ...
This is useful with tree structures or parsers (since I haven't found
any parser class in C# I had to write my own
http://www.antlr.org/
Post by Ertugrul Söylemez
-- and yes, it's monadic).
Antlr's parser's are not. But they are useful nonetheless. And
unlike most home spun parsers, they have the advantage of solid theory
behind them. [Your's might also, but I don't know that.]
When looking for a parser library I found that project myself, but what
I always disliked about parser generators is that they need extra
programs for compilation, you need to learn a separate parser language,
which makes the whole thing a lot more fragile etc. Elegance suffers a lot.

I like monadic parsers because of their elegance, simplicity and because
they help a lot against bugs (just like every monadic language). Of
course in C# they are not as fast and elegant as in Haskell or F# with
their syntactic sugar for monads, but nonetheless I still prefer them
over parser generators.


Greets,
Ertugrul.
George Neuner
2009-05-28 19:30:47 UTC
Permalink
Post by Ertugrul Söylemez
Post by George Neuner
Post by Ertugrul Söylemez
static Blah xyz = () => ... xyz() ...
This is useful with tree structures or parsers (since I haven't found
any parser class in C# I had to write my own
http://www.antlr.org/
Post by Ertugrul Söylemez
-- and yes, it's monadic).
Antlr's parser's are not. But they are useful nonetheless. And
unlike most home spun parsers, they have the advantage of solid theory
behind them. [Your's might also, but I don't know that.]
When looking for a parser library I found that project myself, but what
I always disliked about parser generators is that they need extra
programs for compilation, you need to learn a separate parser language,
which makes the whole thing a lot more fragile etc. Elegance suffers a lot.
It's true that you need to learn the parser generator tool. However,
unless you are talking about increasing software build complexity, I
think your comment about fragility is way off ... parser generators
are, in general, solid technology based on solid theory and create
parsing code that is much more robust than anything most programmers
are capable of rolling themselves.

If you have routine parsing needs that are more than a few simple
regex expressions, then you probably should be investing in a tool.

Of course, there are any number of generators available that are
somebody's pet project, but if you stick with well known, well
supported programs like Bison, Antlr, JavaCC, etc. or commercial
products like Yacc++ you are pretty certain to get a good result.
Post by Ertugrul Söylemez
I like monadic parsers because of their elegance, simplicity and because
they help a lot against bugs (just like every monadic language). Of
course in C# they are not as fast and elegant as in Haskell or F# with
their syntactic sugar for monads, but nonetheless I still prefer them
over parser generators.
I have nothing against monadic parsing libraries ... I just believe
that parsing is a function that is both critically important and
usually in need of high performance, so it is best left to experts to
implement. The average programmer's involvement should be only to
specify what to look for and what to do when it's found.

Haskell has a monadic parser generator. There's one for Lisp also.
Offhand, I'm not away of any others ... but many people do like (at
least in theory) monadic parsing so I'm sure somebody somewhere is
working on decent generators for other capable languages.

George
Ertugrul Söylemez
2009-05-29 07:00:10 UTC
Permalink
Post by George Neuner
Post by Ertugrul Söylemez
When looking for a parser library I found that project myself, but what
I always disliked about parser generators is that they need extra
programs for compilation, you need to learn a separate parser language,
which makes the whole thing a lot more fragile etc. Elegance suffers a lot.
It's true that you need to learn the parser generator tool. However,
unless you are talking about increasing software build complexity, I
think your comment about fragility is way off ... parser generators
are, in general, solid technology based on solid theory and create
parsing code that is much more robust than anything most programmers
are capable of rolling themselves.
If you have routine parsing needs that are more than a few simple
regex expressions, then you probably should be investing in a tool.
Of course, there are any number of generators available that are
somebody's pet project, but if you stick with well known, well
supported programs like Bison, Antlr, JavaCC, etc. or commercial
products like Yacc++ you are pretty certain to get a good result.
Of course you get a good result with established and well tested
software. The point is that Parser combinators (be them monadic or
through continuations) give you good results even if they are homemade
and not tested. Consider that almost all errors are catched at compile
time in a type-safe language.

Parser generators on the other hand create an additional layer, for
which management has to be established first. That makes parser
generators inherently complex and error-prone.
Post by George Neuner
Post by Ertugrul Söylemez
I like monadic parsers because of their elegance, simplicity and because
they help a lot against bugs (just like every monadic language). Of
course in C# they are not as fast and elegant as in Haskell or F# with
their syntactic sugar for monads, but nonetheless I still prefer them
over parser generators.
I have nothing against monadic parsing libraries ... I just believe
that parsing is a function that is both critically important and
usually in need of high performance, so it is best left to experts to
implement. The average programmer's involvement should be only to
specify what to look for and what to do when it's found.
Haskell has a monadic parser generator. There's one for Lisp also.
Offhand, I'm not away of any others ... but many people do like (at
least in theory) monadic parsing so I'm sure somebody somewhere is
working on decent generators for other capable languages.
You seem to be confusing something here. Parser _generators_ are
programs, which you use to create a grammar parser, so a separately
parsed and lexed parser language needs to be built first, which is then
translated to regular code.

Parser _combinators_ (like parser monads or continuation-based parsers)
are used right in the host language. They form a so-called
domain-specific language (DSL). Unlike parser generators, parser
combinators are usually a real library, not a compiler for a third-party
parser language.

The big difference is that a monadic parser combinator library can be
written in a matter of 100-200 lines of Haskell code, compared to which
a parser generator is an extremely complex product. This conciseness
gives you much more comprehensible code, which has the advantage of
exploiting the host language's type system to guarantee safety.

Finally Parsec, the Haskell parser combinator library, is very fast. It
sacrifices some speed for generality, though. If you're not happy with
that, you can use attoparsec, which is specifically optimized for fast
ByteStrings.

About theory: There are two kinds or rather layers of theory involved
here. The outer layer is about expressing the parser. Parser
generators use a theory about how to transform one language to another
safely. Parser combinators use a theory about how to combine simple
primitives to larger constructs elegantly. This comes from the fact
that in a parser combinator library you have a bunch of parsers you
combine through combinators to more complex parsers. Note how the first
seeks safety while in the second safety is given for free. The inner
theory is about the parsing method, which is the same for both.


Greets,
Ertugrul.
Jon Harrop
2009-05-29 14:53:59 UTC
Permalink
Post by Ertugrul Söylemez
Of course you get a good result with established and well tested
software. The point is that Parser combinators (be them monadic or
through continuations) give you good results even if they are homemade
and not tested.
No they don't. Even the most highly optimized monadic parser combinator
libraries are still several times slower that a decent parser generator.
Homegrown libraries are typically orders of magnitude slower.
Post by Ertugrul Söylemez
Consider that almost all errors are catched at compile time in a type-safe
language.
No they aren't. The most common error with parser combinators is failing to
factor your representation of the grammar in order to avoid infinite
recursions. The type system does nothing to help. Parser generators
automate the process, eliminating the source of error.

Other errors include conflicts in the grammar, which are debugged by
yacc-like parser generators but silently ignored by parser combinator
libraries.
Post by Ertugrul Söylemez
Parser generators on the other hand create an additional layer, for
which management has to be established first. That makes parser
generators inherently complex and error-prone.
Then choose mature tools.
Post by Ertugrul Söylemez
Post by George Neuner
Haskell has a monadic parser generator. There's one for Lisp also.
Offhand, I'm not away of any others ... but many people do like (at
least in theory) monadic parsing so I'm sure somebody somewhere is
working on decent generators for other capable languages.
You seem to be confusing something here. Parser _generators_ are
programs, which you use to create a grammar parser, so a separately
parsed and lexed parser language needs to be built first, which is then
translated to regular code.
Parser _combinators_ (like parser monads or continuation-based parsers)
are used right in the host language. They form a so-called
domain-specific language (DSL). Unlike parser generators, parser
combinators are usually a real library, not a compiler for a third-party
parser language.
That has not been true for decades. Parser generators often run in-line
today. Look at camlp4, for example.
Post by Ertugrul Söylemez
The big difference is that a monadic parser combinator library can be
written in a matter of 100-200 lines of Haskell code, compared to which
a parser generator is an extremely complex product. This conciseness
gives you much more comprehensible code, which has the advantage of
exploiting the host language's type system to guarantee safety.
Parsers written with parser combinator libraries are *less* comprehensible,
IME.
Post by Ertugrul Söylemez
Finally Parsec, the Haskell parser combinator library, is very fast.
Do you have any evidence to substantiate that?
Post by Ertugrul Söylemez
About theory: There are two kinds or rather layers of theory involved
here. The outer layer is about expressing the parser. Parser
generators use a theory about how to transform one language to another
safely. Parser combinators use a theory about how to combine simple
primitives to larger constructs elegantly. This comes from the fact
that in a parser combinator library you have a bunch of parsers you
combine through combinators to more complex parsers. Note how the first
seeks safety while in the second safety is given for free. The inner
theory is about the parsing method, which is the same for both.
That is the real difference. Parser combinators do not have the same
limitations and can be used to parse far more general data such as trees
instead of just sequences.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Florian Kreidler
2009-05-29 18:05:06 UTC
Permalink
Post by Jon Harrop
Post by Ertugrul Söylemez
Consider that almost all errors are catched at compile time in a type-safe
language.
No they aren't. The most common error with parser combinators is failing to
factor your representation of the grammar in order to avoid infinite
recursions. The type system does nothing to help. Parser generators
automate the process, eliminating the source of error.
It shouldn't be hard to spot and eliminate left recursive rules in
a grammar.

A serious problem with parser combinators is that non-deterministic
rules can lead to exponential runtime when they are implemented in
a naive way. (At least in simple libraries like Haskell's Parsec.
I'm sure there are more advanced approaches around.)
Post by Jon Harrop
Other errors include conflicts in the grammar, which are debugged by
yacc-like parser generators but silently ignored by parser combinator
libraries.
I see this as an advantage of combinator-based parsers: They solve
conflicts in favor of the first matching rule, so they just do what
the author wants, and there is no need to dive into parsing theory
in order to resolve conflicts.
Jon Harrop
2009-05-29 18:34:39 UTC
Permalink
Post by Florian Kreidler
Post by Jon Harrop
Other errors include conflicts in the grammar, which are debugged by
yacc-like parser generators but silently ignored by parser combinator
libraries.
I see this as an advantage of combinator-based parsers: They solve
conflicts in favor of the first matching rule, so they just do what
the author wants, and there is no need to dive into parsing theory
in order to resolve conflicts.
Many parser generators also resolve shift-reduce conflicts in favor of
earlier rules. My point was that they give you warnings whereas the parser
combinators (that I have used) did not.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Florian Kreidler
2009-05-29 18:45:45 UTC
Permalink
Post by Jon Harrop
Post by Florian Kreidler
Post by Jon Harrop
Other errors include conflicts in the grammar, which are debugged by
yacc-like parser generators but silently ignored by parser combinator
libraries.
I see this as an advantage of combinator-based parsers: They solve
conflicts in favor of the first matching rule, so they just do what
the author wants, and there is no need to dive into parsing theory
in order to resolve conflicts.
Many parser generators also resolve shift-reduce conflicts in favor of
earlier rules. My point was that they give you warnings whereas the parser
combinators (that I have used) did not.
Yes, and my points were that combinators solve ambiguities that
would otherwise lead to shift/reduce-conflicts or even
reduce/reduce-conflicts, and that the concept of 'conflicts' does
not apply to this kind of parsers - as a technical artefact of
table-based parsers it should be hidden from the user in favor of a
simpler concept, like, for example, the first-match-rule of combinator
based parsers.
Jon Harrop
2009-05-30 00:13:36 UTC
Permalink
Post by Florian Kreidler
Post by Jon Harrop
Post by Florian Kreidler
Post by Jon Harrop
Other errors include conflicts in the grammar, which are debugged by
yacc-like parser generators but silently ignored by parser combinator
libraries.
I see this as an advantage of combinator-based parsers: They solve
conflicts in favor of the first matching rule, so they just do what
the author wants, and there is no need to dive into parsing theory
in order to resolve conflicts.
Many parser generators also resolve shift-reduce conflicts in favor of
earlier rules. My point was that they give you warnings whereas the
parser combinators (that I have used) did not.
Yes, and my points were that combinators solve ambiguities that
would otherwise lead to shift/reduce-conflicts or even
reduce/reduce-conflicts, and that the concept of 'conflicts' does
not apply to this kind of parsers - as a technical artefact of
table-based parsers it should be hidden from the user in favor of a
simpler concept, like, for example, the first-match-rule of combinator
based parsers.
Sure, the processing is the same. My point is that parser generators can
provide warnings where parser combinators do not and that can be valuable
(if you expected no warnings).
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
George Neuner
2009-05-30 01:55:29 UTC
Permalink
Post by Florian Kreidler
Post by Jon Harrop
Post by Ertugrul Söylemez
Consider that almost all errors are catched at compile time in a type-safe
language.
No they aren't. The most common error with parser combinators is failing to
factor your representation of the grammar in order to avoid infinite
recursions. The type system does nothing to help. Parser generators
automate the process, eliminating the source of error.
It shouldn't be hard to spot and eliminate left recursive rules in
a grammar.
Actually it can be difficult depending on the complexity of the
grammar - you need to consider long recursions as well as short ones.
LR tools can handle left recursion without factoring.
Post by Florian Kreidler
A serious problem with parser combinators is that non-deterministic
rules can lead to exponential runtime when they are implemented in
a naive way. (At least in simple libraries like Haskell's Parsec.
I'm sure there are more advanced approaches around.)
Non-determinism is another point in favor of parser generators.
Although there are limits, as long as the conflict can be resolved
eventually by continued reading, a GLR parser will handle it very
efficiently (GLR parsers can follow multiple paths through the grammar
simultaneously).

If you're willing to backtrack, LL(k) [with sufficient k] or LL(*)
parsers will also handle non-determinism automatically. There are
some backtracking LR parsers as well, but better to use GLR if you
can. Or better yet, get rid of the non-determinism.
Post by Florian Kreidler
Post by Jon Harrop
Other errors include conflicts in the grammar, which are debugged by
yacc-like parser generators but silently ignored by parser combinator
libraries.
I see this as an advantage of combinator-based parsers: They solve
conflicts in favor of the first matching rule, so they just do what
the author wants, and there is no need to dive into parsing theory
in order to resolve conflicts.
You don't need theory to debug grammars - just a working knowledge of
the tool. Modern parsing tools include explicit conflict resolution
in the form of conditional rules, backtracking or multiple path
parsing.

George
Ertugrul Söylemez
2009-05-29 23:16:10 UTC
Permalink
Post by Jon Harrop
Post by Ertugrul Söylemez
Of course you get a good result with established and well tested
software. The point is that Parser combinators (be them monadic or
through continuations) give you good results even if they are
homemade and not tested.
No they don't. Even the most highly optimized monadic parser
combinator libraries are still several times slower that a decent
parser generator. Homegrown libraries are typically orders of
magnitude slower.
So what? I said good results, not best results. "Several times slower"
is a lot exaggerated anyway. Also look at the latest Parsec, which is
version 3.0.0. It's very fast especially with its new support for
ByteStrings. Older Parsecs are (practically) limited to [Char].
Post by Jon Harrop
Post by Ertugrul Söylemez
Consider that almost all errors are catched at compile time in a
type-safe language.
No they aren't. The most common error with parser combinators is
failing to factor your representation of the grammar in order to avoid
infinite recursions. The type system does nothing to help. Parser
generators automate the process, eliminating the source of error.
Ah, so parser generators solve the halting problem. =)
Post by Jon Harrop
Other errors include conflicts in the grammar, which are debugged by
yacc-like parser generators but silently ignored by parser combinator
libraries.
True -- currently.
Post by Jon Harrop
Post by Ertugrul Söylemez
Parser generators on the other hand create an additional layer, for
which management has to be established first. That makes parser
generators inherently complex and error-prone.
Then choose mature tools.
Parser combinators are mature without the complexity.
Post by Jon Harrop
Post by Ertugrul Söylemez
Post by George Neuner
Haskell has a monadic parser generator. There's one for Lisp also.
Offhand, I'm not away of any others ... but many people do like (at
least in theory) monadic parsing so I'm sure somebody somewhere is
working on decent generators for other capable languages.
You seem to be confusing something here. Parser _generators_ are
programs, which you use to create a grammar parser, so a separately
parsed and lexed parser language needs to be built first, which is then
translated to regular code.
Parser _combinators_ (like parser monads or continuation-based parsers)
are used right in the host language. They form a so-called
domain-specific language (DSL). Unlike parser generators, parser
combinators are usually a real library, not a compiler for a third-party
parser language.
That has not been true for decades. Parser generators often run in-line
today. Look at camlp4, for example.
Then either the same speed issues or inherent safety problems will hold
for them. Of course your notion of "often" suggests that your world may
be limited to OCaml. =)
Post by Jon Harrop
Post by Ertugrul Söylemez
The big difference is that a monadic parser combinator library can
be written in a matter of 100-200 lines of Haskell code, compared to
which a parser generator is an extremely complex product. This
conciseness gives you much more comprehensible code, which has the
advantage of exploiting the host language's type system to guarantee
safety.
Parsers written with parser combinator libraries are *less*
comprehensible, IME.
Yes, IYE. I disagree here. No new language to learn, no new syntax to
learn, just learn how to stick together some parsers. An 'a' followed
by a 'b'? char 'a' >> char 'b'. Either an 'a' or a 'b'? char 'a' <|>
char 'b'. Easy.
Post by Jon Harrop
Post by Ertugrul Söylemez
Finally Parsec, the Haskell parser combinator library, is very fast.
Do you have any evidence to substantiate that?
Benchmark it.
Post by Jon Harrop
Post by Ertugrul Söylemez
About theory: There are two kinds or rather layers of theory
involved here. The outer layer is about expressing the parser.
Parser generators use a theory about how to transform one language
to another safely. Parser combinators use a theory about how to
combine simple primitives to larger constructs elegantly. This
comes from the fact that in a parser combinator library you have a
bunch of parsers you combine through combinators to more complex
parsers. Note how the first seeks safety while in the second safety
is given for free. The inner theory is about the parsing method,
which is the same for both.
That is the real difference. Parser combinators do not have the same
limitations and can be used to parse far more general data such as
trees instead of just sequences.
It's an advantage, but not a big one. The real advantage is elegance
and generality about what you can parse. They can be used to parse
anything you want from strings over binary data to more complicated
structures. Also you can utilize the full power of the host language
without ugly wrappers or escaping.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Jon Harrop
2009-05-30 00:32:56 UTC
Permalink
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
Consider that almost all errors are catched at compile time in a
type-safe language.
No they aren't. The most common error with parser combinators is
failing to factor your representation of the grammar in order to avoid
infinite recursions. The type system does nothing to help. Parser
generators automate the process, eliminating the source of error.
Ah, so parser generators solve the halting problem. =)
Left recursion is not the halting problem.
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
Parser generators on the other hand create an additional layer, for
which management has to be established first. That makes parser
generators inherently complex and error-prone.
Then choose mature tools.
Parser combinators are mature without the complexity.
The nearest thing to a major parser combinator library is Parsec and it is
nowhere near as mature as mainstream parser generators.
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
The big difference is that a monadic parser combinator library can
be written in a matter of 100-200 lines of Haskell code, compared to
which a parser generator is an extremely complex product. This
conciseness gives you much more comprehensible code, which has the
advantage of exploiting the host language's type system to guarantee
safety.
Parsers written with parser combinator libraries are *less*
comprehensible, IME.
Yes, IYE. I disagree here. No new language to learn, no new syntax to
learn, just learn how to stick together some parsers. An 'a' followed
by a 'b'? char 'a' >> char 'b'. Either an 'a' or a 'b'? char 'a' <|>
char 'b'. Easy.
Here is a calculator parser written using the parser generator camlp4:

expr:
[ [ x = expr; "+"; y = expr -> x + y
| x = expr; "-"; y = expr -> x - y ]
| [ x = expr; "*"; y = expr -> x * y
| x = expr; "/"; y = expr -> x / y ]
| [ x = INT -> int_of_string x ] ];

As you can see, there is no new "language" and no new "syntax" by your
definitions.
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
Finally Parsec, the Haskell parser combinator library, is very fast.
Do you have any evidence to substantiate that?
Benchmark it.
I'll take that as a "no".
Post by Ertugrul Söylemez
It's an advantage, but not a big one. The real advantage is elegance
and generality about what you can parse. They can be used to parse
anything you want from strings over binary data to more complicated
structures. Also you can utilize the full power of the host language
without ugly wrappers or escaping.
Ugly wrappers and escaping are not universal among parser generators.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Ertugrul Söylemez
2009-05-30 10:22:39 UTC
Permalink
Post by Jon Harrop
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
Consider that almost all errors are catched at compile time in a
type-safe language.
No they aren't. The most common error with parser combinators is
failing to factor your representation of the grammar in order to
avoid infinite recursions. The type system does nothing to
help. Parser generators automate the process, eliminating the
source of error.
Ah, so parser generators solve the halting problem. =)
Left recursion is not the halting problem.
Probably. I don't know. But you may want to show me a case of infinite
recursion -- in Parsec, that is.
Post by Jon Harrop
The nearest thing to a major parser combinator library is Parsec and
it is nowhere near as mature as mainstream parser generators.
It's mature enough for most purposes. The matureness of mainstream
parser generators comes from features, not from better design.
Post by Jon Harrop
Post by Ertugrul Söylemez
Post by Jon Harrop
Parsers written with parser combinator libraries are *less*
comprehensible, IME.
Yes, IYE. I disagree here. No new language to learn, no new syntax
to learn, just learn how to stick together some parsers. An 'a'
followed by a 'b'? char 'a' >> char 'b'. Either an 'a' or a 'b'?
char 'a' <|> char 'b'. Easy.
[ [ x = expr; "+"; y = expr -> x + y
| x = expr; "-"; y = expr -> x - y ]
| [ x = expr; "*"; y = expr -> x * y
| x = expr; "/"; y = expr -> x / y ]
| [ x = INT -> int_of_string x ] ];
As you can see, there is no new "language" and no new "syntax" by your
definitions.
That's fine then. Doesn't invalidate my statement. It merely says that
camlp4 is equally comprehensible.
Post by Jon Harrop
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
Finally Parsec, the Haskell parser combinator library, is very fast.
Do you have any evidence to substantiate that?
Benchmark it.
I'll take that as a "no".
Feel free to. This is infantile beating on numbers and I don't feel
like wasting my time proving this to you. Parsec is fast, take it or
leave it. Whether or not it's a millisecond faster than mainstream
parser generators is another story.
Post by Jon Harrop
Post by Ertugrul Söylemez
It's an advantage, but not a big one. The real advantage is
elegance and generality about what you can parse. They can be used
to parse anything you want from strings over binary data to more
complicated structures. Also you can utilize the full power of the
host language without ugly wrappers or escaping.
Ugly wrappers and escaping are not universal among parser generators.
Nothing besides parsing something is universal among parser generators.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
Jon Harrop
2009-05-30 15:07:27 UTC
Permalink
This is infantile beating on numbers...
Or "science" as we like to call it.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
David Formosa (aka ? the Platypus)
2009-06-22 23:16:32 UTC
Permalink
Post by Jon Harrop
Post by Ertugrul Söylemez
Post by Jon Harrop
Post by Ertugrul Söylemez
Consider that almost all errors are catched at compile time in a
type-safe language.
No they aren't. The most common error with parser combinators is
failing to factor your representation of the grammar in order to avoid
infinite recursions. The type system does nothing to help. Parser
generators automate the process, eliminating the source of error.
Ah, so parser generators solve the halting problem. =)
Left recursion is not the halting problem.
I recall reading a paper on how it was possable to use memoization to
detect left recursion in combinator parsers. It doesn't seem the be
implemented in libaries yet.
Chung-chieh Shan
2009-06-23 00:13:12 UTC
Permalink
Post by David Formosa (aka ? the Platypus)
I recall reading a paper on how it was possable to use memoization to
detect left recursion in combinator parsers. It doesn't seem the be
implemented in libaries yet.
You might be thinking of:

Mark Johnson. 1995. Memoization of top-down parsing. Computational
Linguistics 21(3):405-417.
http://arxiv.org/abs/cmp-lg/9504016
http://www.aclweb.org/anthology/J95-3005
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
We want our revolution, and we want it now! -- Marat/Sade
We want our revolution, and we'll take it at such time as
you've gotten around to delivering it -- Haskell programmer
George Neuner
2009-05-30 01:55:29 UTC
Permalink
Post by Ertugrul Söylemez
Post by George Neuner
Post by Ertugrul Söylemez
I like monadic parsers because of their elegance, simplicity and because
they help a lot against bugs (just like every monadic language). Of
course in C# they are not as fast and elegant as in Haskell or F# with
their syntactic sugar for monads, but nonetheless I still prefer them
over parser generators.
I have nothing against monadic parsing libraries ... I just believe
that parsing is a function that is both critically important and
usually in need of high performance, so it is best left to experts to
implement. The average programmer's involvement should be only to
specify what to look for and what to do when it's found.
Haskell has a monadic parser generator. There's one for Lisp also.
Offhand, I'm not away of any others ... but many people do like (at
least in theory) monadic parsing so I'm sure somebody somewhere is
working on decent generators for other capable languages.
You seem to be confusing something here. Parser _generators_ are
programs, which you use to create a grammar parser, so a separately
parsed and lexed parser language needs to be built first, which is then
translated to regular code.
Parser _combinators_ (like parser monads or continuation-based parsers)
are used right in the host language. They form a so-called
domain-specific language (DSL). Unlike parser generators, parser
combinators are usually a real library, not a compiler for a third-party
parser language.
I know the difference. My point is that using a tool which can
analyze the grammar and point out conflicts is a Good Thing(TM).
Conflicts in the grammar are points of potential confusion to human
users as well as to parsers.
Post by Ertugrul Söylemez
The big difference is that a monadic parser combinator library can be
written in a matter of 100-200 lines of Haskell code, compared to which
a parser generator is an extremely complex product. This conciseness
gives you much more comprehensible code, which has the advantage of
exploiting the host language's type system to guarantee safety.
Finally Parsec, the Haskell parser combinator library, is very fast. It
sacrifices some speed for generality, though. If you're not happy with
that, you can use attoparsec, which is specifically optimized for fast
ByteStrings.
Haskell has a parser _generator_, called Happy, which uses Parsec.
Post by Ertugrul Söylemez
About theory: There are two kinds or rather layers of theory involved
here. The outer layer is about expressing the parser. Parser
generators use a theory about how to transform one language to another
safely. Parser combinators use a theory about how to combine simple
primitives to larger constructs elegantly. This comes from the fact
that in a parser combinator library you have a bunch of parsers you
combine through combinators to more complex parsers. Note how the first
seeks safety while in the second safety is given for free. The inner
theory is about the parsing method, which is the same for both.
I have never seen a (G)LR or LL(*) combinator library. All the ones I
am aware of are limited to LL(k) for small k - which is fine for some
uses but not for all.

George
Adrian Hey
2009-05-30 08:21:45 UTC
Permalink
Hello George,
Post by George Neuner
Haskell has a parser _generator_, called Happy, which uses Parsec.
I don't think that's true (Happy doesn't use Parsec AFAIK).

FWIW, I like parser combinators too. Not because I think they're
technically better (just don't know). I just find them easier to
understand and more convenient. (At least in an FPL, if I was using
C or something I might feel differently.)

Regards
--
Adrian Hey
George Neuner
2009-06-01 16:40:03 UTC
Permalink
On Sat, 30 May 2009 09:21:45 +0100, Adrian Hey
Post by Adrian Hey
Hello George,
Post by George Neuner
Haskell has a parser _generator_, called Happy, which uses Parsec.
I don't think that's true (Happy doesn't use Parsec AFAIK).
FWIW, I like parser combinators too. Not because I think they're
technically better (just don't know). I just find them easier to
understand and more convenient. (At least in an FPL, if I was using
C or something I might feel differently.)
Regards
Oops! You're right ... Happy has its own combinator library. Sorry
for the confusion.

George
raould
2009-05-29 00:04:12 UTC
Permalink
Post by Ertugrul Söylemez
Where Haskell programmers coming from the strict world get memory leaks,
strict programmers coming from the Haskell world get stack overflows.
it is very interesting to think about which is the lesser evil.

sincerely.
raould
2009-05-29 00:10:12 UTC
Permalink
re: laziness

hey, i learn something new every day

http://www.haskell.org/haskellwiki/Lazy_vs._non-strict
Continue reading on narkive:
Loading...