[Haskell-cafe] On finding the right exposition...

[Joachim Durchholz]

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 
performance traps.
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 
about.
See https://github.com/quchen/stgi .

Regards,
Jo