Note [Call SubDemand vs. evaluation Demand]
Although both evaluation Demands and Call SubDemands carry a (Card,SubDemand)
pair, their interpretation is quite different. Example:
f x = fst x * snd x
f :: <SP(1L,1L)>, because 1P(1L,A)+1P(A,1L) = SP(1L,1L)
g x = fst (x 1) * snd (x 2)
g :: <SC(S,P(ML,ML))>, because 1C(1,P(1L,A))+1C(1,P(A,1L)) = SC(S,P(ML,ML))
The point about this example is that both demands have P(A,1L)/P(1L,A) as
sub-expressions, but when these sub-demands occur
1. under an evaluation demand, we combine with `plusSubDmd`
2. whereas under a Call sub-demand, we combine with `lubSubDmd`
And thus (1) yields a stricter demand on the pair components than (2).
In #21717 we saw that we really need lub in (2), because otherwise we make an
unsound prediction in `g (\n -> if n == 1 then (1,1) else (bot,2))`; we'd say
that the `bot` expression is always evaluated, when it clearly is not.
Operationally, every call to `g` gives back a potentially distinct,
heap-allocated pair with potentially different contents, and we must `lubSubDmd`
over all such calls to approximate how any of those pairs might be used.
That is in stark contrast to f's argument `x`: Operationally, every eval of
`x` must yield the same pair and `f` evaluates both components of that pair.
The theorem "every eval of `x` returns the same heap object" is a very strong
MUST-alias property and we capitalise on that by using `plusSubDmd` in (1).
And indeed we *must* use `plusSubDmd` in (1) for sound upper bounds in an
analysis that assumes call-by-need (as opposed to the weaker call-by-name) for
let bindings. Consider
h x = fst x * fst x
h :: <SP(SL,A)>
And the expression `let a=1; p=(a,a)} in h p`. Here, *although* the RHS of `p`
is only evaluated once under call-by-need, `a` is still evaluated twice.
If we had used `lubSubDmd`, we'd see SP(1L,A) and the 1L unsoundly says "exactly
once".
If the analysis had assumed call-by-name, it would be sound to say "a is used
once in p": p is used multiple times and hence so would a, as if p was a
function. So using `plusSubDmd` does not only yield better strictness, it is
also "holding up the other end of the bargain" of the call-by-need assumption
for upper bounds.
(To SG's knowledge, the distinction between call-by-name and call-by-need does
not matter for strictness analysis/lower bounds, thus it would be sound to use
`lubSubDmd` all the time there.) References 0
This Note does not link to any other.
Referenced by 2
- SubDemand denotes at least one evaluation GHC.Types.Demand
- GHC.Types.Demand call site