how is Haskell not robust?
raould
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
raould wrote:
> 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.
> 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
Ertugrul Söylemez
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
wrote:
> 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).
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
>> 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/
>
>> -- 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
wrote:
>George Neuner schrieb:
>>> 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/
>>
>>> -- 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.
>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
raould
> 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.
raould
> strict programmers coming from the Haskell world get stack overflows.
it is very interesting to think about which is the lesser evil.
sincerely.
raould
hey, i learn something new every day
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.
>> 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
> 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.
> 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.
> 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.
>> 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.
> 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.
> Finally Parsec, the Haskell parser combinator library, is very fast.
Do you have any evidence to substantiate that?
> 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
> Ertugrul Sï¿œylemez wrote:
>> 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.)
> 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
> Jon Harrop <j...@ffconsultancy.com> schrieb:
>> 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.
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> 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.
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].
> > 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. =)
> Other errors include conflicts in the grammar, which are debugged by
> yacc-like parser generators but silently ignored by parser combinator
> libraries.
True -- currently.
> > 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.
> >> 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. =)
> > 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.
> > Finally Parsec, the Haskell parser combinator library, is very fast.
>
> Do you have any evidence to substantiate that?
Benchmark it.
> > 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.
Jon Harrop
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).
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> wrote:
>> > 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.
>> > 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.
>> > 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.
>> > 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".
> 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.
George Neuner
wrote:
>George Neuner schrieb:
>
>>> 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.
>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.
>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
George Neuner
wrote:
>Jon Harrop <j...@ffconsultancy.com> schrieb:
>> Ertugrul S�ylemez wrote:
>
>>> 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.
>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.
>> 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
Adrian Hey
raould wrote:
> 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).
> 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
Adrian Hey
George Neuner wrote:
> 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
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.
> 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.
> >> 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.
That's fine then. Doesn't invalidate my statement. It merely says that
camlp4 is equally comprehensible.
> >>> 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.
> > 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.
Ertugrul Söylemez
> > 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.
> 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.
> 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.
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.
> 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.
Jon Harrop
> This is infantile beating on numbers...
Or "science" as we like to call it.
Adrian Hey
Ertugrul S�ylemez wrote:
> Adrian Hey <ah...@NoSpicedHam.iee.org> wrote:
>
>>> 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 :-)
> 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.
>> 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).
> 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.
> 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).
>> 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
Erik de Castro Lopo
> Hello Raould
>
> raould wrote:
> > 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/
Ertugrul Söylemez
> >>> 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.
> > 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.
> >> 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 (!!).
> 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.
> > 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.
> 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.
> > 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.
> >> 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.
Adrian Hey
Well when in doubt try it out..
Adrian Hey wrote:
> Ertugrul S�ylemez wrote:
>> 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
Adrian Hey
> 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).
> 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.
> 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.
> It doesn't mention the
> term 'graph' anywhere, but that's also not necessary.
Only if we don't care about space behaviour.
> 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"?
> 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.
> 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.
> 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..
> 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
fft1976
> 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
Or "learning" as it is otherwise known. :-)
Erik de Castro Lopo
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 :-).
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.
> > 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.
> > 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.
> > 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.
> > 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.
> > 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.
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.
> > 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.
>
> > 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.
> > 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.
Jon Harrop
> 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.
George Neuner
Oops! You're right ... Happy has its own combinator library. Sorry
for the confusion.
George
Adrian Hey
Jon Harrop wrote:
> Ertugrul Söylemez wrote:
>> 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
> > 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?
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> wrote:
>> > 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.
> 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.
> 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.
Ertugrul Söylemez
> Ertugrul Söylemez wrote:
>> Jon Harrop <j...@ffconsultancy.com> wrote:
>>>> 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.
>
>> 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.
> 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".
>> 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
> Jon Harrop schrieb:
>> 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.
> 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.
> 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.
> 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".
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.
> > 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.
> > 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.
raould
> 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
> there anything about it that could be automated?
hmmm
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.
Manlio Perillo
> raould wrote:
>> 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
> 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.
raould
> 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.
Jon Harrop
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.
Paul Rubin
> 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.
Paul Rubin
> 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.
Dirk Thierbach
> 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.
> 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).
> 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").
> 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)
Ertugrul Söylemez
>> 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.
Aatu Koskensilta
> 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 (aatu.kos...@uta.fi)
"Wovon mann nicht sprechen kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
George Neuner
wrote:
>Jon Harrop schrieb:
>>> 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.
>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.
>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
> 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.
toby
> George Neuner wrote:
> > 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?
Jon Harrop
> On Jun 5, 6:04 pm, Jon Harrop <j...@ffconsultancy.com> wrote:
>> George Neuner wrote:
>> > 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.
Ertugrul Söylemez
> 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.
Marshall
>
> 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
> > 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:
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> wrote:
>> 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.
> If new standards could be created quicker and there were more libraries,
Lack of documentation and interoperability are much bigger problems, IMHO.
> 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.
Adrian Hey
Dirk Thierbach wrote:
> 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.
> 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 :-)
> 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
> Dirk Thierbach wrote:
>> 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.
> 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"?
> 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.
> 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".
> 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.
>> 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 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.
> 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.
> 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 :-)
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).
>> 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.
> 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.
> 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.
> 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
> Adrian Hey <ah...@nospicedham.iee.org> wrote:
>> Dirk Thierbach wrote:
>>> 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?
>> 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.
> 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?
> 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.
>> 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?
> 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?
>>> 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.
>> 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.
> 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?
>> 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?
>> 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 :-)
>
> 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?
> Space usage is dependent on the evaluation strategy, and has little to
> with the "pure functional" vs. "imperative" approach.
They are related.
> 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?
> 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.
Paul Rubin
> 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
Dirk Thierbach wrote:
> 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 :-(
>> 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
Adrian Hey
Jon Harrop wrote:
> Ertugrul Söylemez wrote:
>> 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
:-)
> 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
Paul Rubin
> 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
Paul Rubin wrote:
> 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
Jon Harrop
> Jon Harrop wrote:
>> Ertugrul Söylemez wrote:
>>> 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?
> 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.
> 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.
>> 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.
Adrian Hey
Jon Harrop wrote:
> Adrian Hey wrote:
>> 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.
> 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.
> 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
Stephen J. Bevan
> 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.
> 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
wrote:
> Jon Harrop <j...@ffconsultancy.com> writes:
> > 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
> Jon Harrop wrote:
>> Adrian Hey wrote:
>>> 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.
>> 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.
> 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.
>> 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
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> writes:
>> 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.
> 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?
>> 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.
Ertugrul Söylemez
> >> 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.
> 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.
> > 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.
> > 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.
Jon Harrop
>> 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.
>> 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. :-)
>> > 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.
> 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...
Stephen J. Bevan
> Stephen J. Bevan wrote:
>> Jon Harrop <j...@ffconsultancy.com> writes:
>>> 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.
>> 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 <87hc0jj...@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.
>>> 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
> Jon Harrop <j...@ffconsultancy.com> writes:
>> Stephen J. Bevan wrote:
>>> Jon Harrop <j...@ffconsultancy.com> writes:
>>>> 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.
>> 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.
Paul Rubin
> > 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?
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.
>> 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 ...
> 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
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.
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> writes:
>>> 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.
>>> 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.
> 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.
>> 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.
> 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.
Paul Rubin
> On the contrary, the sole purpose of incremental resizing is to guarantee
> non-amortized O(1) worst case complexity.
How does it guarantee that?
> 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
> Jon Harrop <j...@ffconsultancy.com> writes:
>> 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.
>> 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.
Paul Rubin
> >> 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.
Stephen J. Bevan
>> 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.
>> 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.
>> 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.
>>> 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?
>> 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
> > 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.
Jon Harrop
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.
Paul Rubin
> 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
Exactly.
George Neuner
wrote:
>Stephen J. Bevan wrote:
>> Jon Harrop <j...@ffconsultancy.com> writes:
>>>> 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.
>
>>>> 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
Florian Weimer
Randomized hashing can make that case sufficiently unlikely, even with
deliberate attacks.
Paul Rubin
> 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.
David Formosa (aka ? the Platypus)
> Ertugrul S�ylemez wrote:
>> Jon Harrop <j...@ffconsultancy.com> wrote:
>>> > 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
> 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