[Haskell-cafe] On finding the right exposition...
jo at durchholz.org
Sun Sep 19 09:30:31 UTC 2021
Am 19.09.21 um 01:20 schrieb Chris Smith:
> I don't think it quite makes sense to say that Haskell shares the
> evaluation model with lambda calculus, because I don't think it's fair
> to say that lambda calculus has any specific evaluation model at all.
> Do you mean substitution, for example? But that's only one way to
> implement lambda calculus, and not one that is shared by any widely used
> Haskell implementation.
Actually substitution *is* the evaluation model of lambda calculus.
And the tagless spineless machine did in fact do substitutions - not on
text but on a graph-transformed version of the text, and it had
optimizations to avoid doing the same substitutions a second time, but
yes it was substituting.
Of course, today's GHC does not use the STG machine anymore (or not
prominently anyway), as more efficient ways to execute Haskell have been
implemented. I see that at roughly the same level as C compilers which
reorder, rewrite, or eliminate code blocks, deviating pretty far from
C's standard sequential execution model. I.e. other execution models are
okay as long as they're semantically equivalent to the original - but
for explanations to novices, you use "the" standard model, and *maybe*
drop a hint or two how they can expect optimizations to happen (some of
the typical optimizations are so important that they shape coding style,
and knowing these early prevents them from "optimizing" stuff just to
find out they just slowed down their code because it became so
unidiomatic that GHC does not know how to optimize it properly).
> But I do agree there's a point here. There's a simplicity that the
> purely functional fragment of Haskell shares with the lambda calculus,
> which I wish were easier to get across to new Haskell programmers. That
> simplicity is precisely what allows the lambda calculus, as well as the
> purely functional fragment of Haskell, to have a meaning
> /without/ answering the question of how it is evaluated. (Even in more
> complex programming languages, the notion of evaluation that is used to
> define the language is often not the same one that's used by
> implementations, of course. But nevertheless these languages must be
> defined in terms of some model of evaluation, where the purely
> functional fragment of Haskell doesn't.)
The good news is: Of course Haskell has an evaluation model, just like
the lambda calculus.
> I struggle with this. In some very real ways, I consider it the most
> important point of learning Haskell for many programmers. But it's also
> not a prerequisite to using Haskell for practical purposes.
That's true. I have seen some disturbingly "imperative" discussions
about Haskell's behaviour here. Though it's hard to judge whether that's
because the participants didn't grok the language concepts, or because
they have internalized the language concepts so well that they can
afford a lax terminology without getting misunderstood. (The discussions
I saw were mostly about optimizing memory performance, and these aspects
are so far ahead of my Haskell knowledge that I couldn't tell.)
> New Python programmers don't write
> idiomatic or perfect Python, either!
Hmm... I think it's not that easy.
Unidiomatic Python code still works and has reasonable performance.
Unidiomatic Haskell code could have orders-of-magnitude performance
hits, as seen in an ICFP contest where the difference between fastest
and slowed program was a factor of 10,000.
Not that I think that a learner should be expected to perfectly adapt to
all idioms. But you need to teach them enough that they don't fall to
Which means you do have to talk about foldl and foldr, for example - and
about the underlying evaluation model, in particular the "avoids
evaluating unneeded subexpressions" part, and that foldl and foldr are
telling the compiler which side of the overall expression is going to be
more likely to be required.
One thing I found was a visualisation of the STG (Spineless Tagless G
Machine). If this thing has merit, then it might be exactly the tool
people have been asking for to "see" (grok) what Haskell's evaluation is
See https://github.com/quchen/stgi .
More information about the Haskell-Cafe