(This post is discussed in episode 15 of the Haskell Weekly Podcast.)
Chapter 27 of Haskell Programming from first principles (by Christopher Allen and Julie Moronuki) is about the evaluation system of Haskell, with a focus on non-strictness. In the section Preventing sharing on purpose, they write you want to prevent sharing the result of a function call when it would mean storing some big data just to calculate a small result. Two examples are provided to demonstrate the alternatives. In the first, the result of g _ is not shared but calculated twice:
Prelude> f x = (x 3) + (x 10)
Prelude> g' = \_ -> trace "hi g'" 2
Prelude> f g'
hi g'
hi g'
4
In the second, the result of g _ is shared, i.e. calculated only once and the result is stored:
Prelude> g = const (trace "hi g" 2)
Prelude> f g
hi g
4
(Edited to add:) In practice, sharing is usually achieved with a let expression or a where construct.
(Note that this latter is called a “point-free” definition.)
The authors conclude that
functions aren’t shared when there are named arguments but are when the arguments are elided, as in pointfree. So, one way to prevent sharing is adding named arguments.
(Quoted from version 1.0RC4 of the book.)
In this post I analyze the runtime differences between point-free and pointful definitions.
Behind the scenes
As Tom Ellis describes, the definitions of g and f translate to the following (in a close approximation to the “Core” language used during compilation):
f = \x -> let {x3 = x 3; x10 = x 10} in (+) x3 x10
g = let {tg = trace "hi g" 2} in \y -> const tg y
g' = \_ -> trace "hi g'" 2
(Calling f g with these definitions does not result in the same trace in GHCi 8.6.5 as with the original definitions. However, the code has the expected behavior if loaded into GHCi from a source file like that below.)
Two things to point out here. First, every function definition is a lambda. Second, g was turned into a let expression because we can only apply functions to variables or literals (in Core), not to function calls. Edited to add: It would be reasonable to ask why g = const (trace "hi g" 2) doesn’t translate to \y -> let {tg = trace "hi g" 2} in const tg y (similar to f), to which the pragmatic answer is that apparently the order is the following:
- not-fully-applied functions are turned into lambdas,
- parameters that are function calls are turned into named variables, and
- named function arguments from the left-hand side of
=are moved to the right as a lambda.
Evaluation with sharing
This is what happens during the evaluation of f g:
ans = f g
ans is a function call, so its evaluation proceeds with substituting g for the argument of f:
ans = let {x3 = g 3; x10 = g 10} in (+) x3 x10
ans is a let expression, so we put the following thunks for x3 and x10 on the heap under some unique name:
-- Heap:
ans_x3 = g 3
ans_x10 = g 10
…and then proceed with evaluating the in part:
ans = (+) ans_x3 ans_x10
During the evaluation of this function call, ans_x3 will be evaluated (or potentially ans_x10 first, or both in parallel). ans_x3 is a function call, so first we evaluate g to a lambda. As g is a let expression, we create a closure for trace "hi g" 2 on the heap, and then continue with the in part of g (\y -> const tg y). This is a lambda now, meaning it’s in weak head normal form, so the heap contents for g is overwritten with that:
-- Heap:
g_tg = trace "hi g" 2
g = \y -> const g_tg y
Back to ans_x3, now the argument 3 is substituted in the definition of g:
ans_x3 = const g_tg 3
This is a function call, with const already a lambda \x _ -> x, so the arguments can now be substituted in the body, leaving us with
-- Heap:
ans_x3 = g_tg -- (Pointer to the same address as g_tg.)
During the evaluation of g_tg, the magic printout happens (hi g on stdout), and its value is resolved to be 2, so the heap is updated as such:
-- Heap:
g_tg = 2
And ans_x3 is a pointer to the same memory content 2.
Analogously, the evaluation of ans_x10 proceeds as such:
ans_x10 = const g_tg 10
ans_x10 = g_tg
-- let ans_x10 points to the memory location of g_tg:
ans_x10 = 2
Finally, ans = (+) ans_x3 ans_x10, which evaluates to ans = 4.
Evaluation without sharing
In contrast, the evaluation of f g' proceeds as follows:
ans' = f g'
ans' = let {x3 = g' 3; x10 = g' 10} in (+) x3 x10
-- Heap:
ans_x3' = g' 3
ans_x10' = g' 10
ans' = (+) ans_x3' ans_x10'
ans_x3' = trace "hi g'" 2
Now hi g' is printed, and the heap is updated:
-- Heap:
ans_x3' = 2
When evaluating ans_x10', we again print hi g', and store the result of the trace under a different thunk:
-- Heap:
ans_x10' = 2
Now ans' evaluates to (+) 2 2, i.e. 4.
Attempt at verifying my translated definitions
I attempted to verify what I was saying above about the definitions of f, g, g' in Core, using the -ddump-simpl compiler flag of GHCi, but it didn’t fulfil my expectations.
module Sharing where
import Debug.Trace
f x = (x (3::Int)) + (x 10) :: Int
g = const (trace "hi g" (2::Int)) -- share
g' = \_ -> trace "hi g'" (2::Int) -- don't share
g'' = let {tg = trace "hi g" (2::Int)} in \y -> const tg y -- share (equivalent to g)
In GHCi:
Prelude> :set -ddump-simpl -dsuppress-all -Wno-missing-signatures
Prelude> :l Sharing
[1 of 1] Compiling Sharing ( Sharing.hs, interpreted )
==================== Tidy Core ====================
Result size of Tidy Core
= {terms: 52, types: 39, coercions: 0, joins: 0/0}
f = \ x_a1Fl -> + $fNumInt (x_a1Fl (I# 3#)) (x_a1Fl (I# 10#))
g = \ @ b_a1Gi -> const (trace (unpackCString# "hi g"#) (I# 2#))
g' = \ @ p_a1G6 -> \ _ -> trace (unpackCString# "hi g'"#) (I# 2#)
tg_r1F4 = trace (unpackCString# "hi g"#) (I# 2#)
g'' = \ @ b_a1FJ -> \ y_a1Fn -> const tg_r1F4 y_a1Fn
... and some more stuff
Nonetheless, as a SO answer describes, we can see that a function application in Core is defined as Expr Atom, where Atom is var | Literal. I attempted to install ghc-core but the build failed, so further analysis is put on the shelf.
Conclusions
So, what’s the essential difference between g and g'?
g = const (trace "hi g" 2) is a function application where the argument is a function application, which is treated as a let expression. When you evaluate g (), the auxiliary variable introduced by the let – i.e.,tg = trace "hi g" 2 – is evaluated to a literal and its value is stored on the heap. On subsequent calls, some other argument can be applied to the const tg function, but its first argument tg is already evaluated.
In contrast, g' = \_ -> trace "hi g'" 2 is a lambda, so it is already fully evaluated, and nothing in it can be simplified further. If we apply g' first to the argument (), the expression g' () will evaluate to the body of g' with the unused parameter discarded, i.e. trace "hi g'" 2. If we later evaluate g' [], then it again results in the (same) body after the (dummy) function application. Nowhere during this process did we store the value of trace "hi g'" 2: in particular, we didn’t update the definition of g' to \_ -> 2, simply because that is not the definition of g'. (But could we have updated it? Even though functions are always pure, I think the answer is generally no: sometimes the result of a function is bigger than the definition, and the result is not needed often enough to warrant this speed–memory tradeoff.)
Recall the original wording:
functions aren’t shared when there are named arguments but are when the arguments are elided, as in pointfree.
As we saw, functions themselves are never shared. Rather, if g is a partially applied function whose argument is a function application fun arg, then g is equivalent to a let expression, and after its first evaluation g will change to a lambda with fun arg already evaluated.
As a generally-okay heuristic, point-free definitions allow sharing inner function calls, whereas nothing in a lambda (or a function with all arguments on the left-hand side) is shared.
Further resources
More details on similar behavior are given by Tom Ellis in his talk Haskell programs: how do they run? (free registration required to watch the talk).
The talk of David Luposchainsky (a.k.a. quchen) goes into more depth – down to the Core –, in which he uses his own implementation of the spineless tagless graph reduction machine (STG), to visualize the evaluation of any given Haskell code (link to repo).