Today I prepared slides for Friday’s presentation. I always find it helpful to a dry run the day before, I’m told magic happens when you sleep on it.
I was happy to draw a line connecting SICP to Haskell, and it’s a good periodic reminder when delving into functional programming. What's new is I feel pulled into a lot of theory (lambda calculus, type theory, category theory, proofs), discover this is normal, and spending time on all this doesn’t even cover what the compiler does in practice.
Re: compiler, I was previously under the impression that lazy evaluation can be inefficient because you’re doing the same calculation more than once. For example, in calculating `square (1 + 2)`, you have to do `(1 + 2)` twice in `((1 + 2) * (1 + 2))` instead of just once when do the sum first before you square. This is from CIS 194 lecture notes.
In particular, GHC uses a technique called graph reduction, where the expression being evaluated is actually represented as a graph, so that different parts of the expression can share pointers to the same subexpression.
My read is Haskell builds abstractions that doesn’t translate as naturally to what the processor does and has to do heavy lifting for performance reasons. The code still runs fast, but maybe you’ll need to know the compiler a bit better when you’re trying to reason about your program or diagnose bottlenecks. This theme came up in the FP study group, on the topic of additional 'bookkeeping' that Clojure does to ensure your dictionaries are immutable under the hood.
In any case I tried running locally the left fold vs right fold example
here. This involves concatenating a 100mm integers and summing them up (I didn’t get a stack overflow like in the post, which is impressive heavy lifting!). This is for the right fold.
stack exec cis194-exe 2.27s user 0.85s system 116% cpu 2.672 total
Now the left.
stack exec cis194-exe 13.14s user 2.97s system 101% cpu 15.849 total
That's 6x! Reminder to self to
read up more on the weak-head normal form (WHNF). My understanding so far is that left folds are more expensive here because you need to expand everything out, whereas in right folds you get to keep things in WHNF until the eval happens.
One of the best memories at work was about Python code my previous manager wrote in more functional style using `functools`. On discovering that it actually runs slower than writing it in idiomatic Python, another colleague said "It's harder to read, it's slower, so we're writing it this way for funsies?". Everyone laughed. My stomach hurt. It was amazing.