foldl, whose seed parameter can be made strict so long as the binary function used for the fold is also strict.
Can we do better? Maybe, but I can't think of a clean solution. Here, I'll sketch out an algorithm that doesn't quite work. Note that there is a runtime cost for implementing such an approach, but I believe the runtime cost can be made less than the cost of unnecessarily allocating a thunk on the heap - which requires at the very least a handful of instructions.
Before giving the algorithm, let's be clear about the goal: the goal of perfect strictness analysis is to avoid allocating a thunk for any argument that could be made strict without altering the callee's semantics. We don't care whether this determination can be done statically or whether it must wait until runtime.
In the case that it must wait until runtime, here is a sketch of an algorithm that seems like it might work, but doesn't. I'm going to loosely assume a stack-based machine, in which we push a function then its arguments onto a stack, then either call the function or create a thunk:
- Each function stores (at runtime) an annotation indicating which arguments to it are strict, or, more generally, how the strictness of each argument is dependent on the strictness of other arguments.
- Rather than building thunks bottom up, we build them top-down: when creating a thunk, we first push the callee onto a stack.
- Before building a thunk for an argument to the callee, we ask the callee whether it is strict in that argument. If it is, we evaluate the argument. Note that the callee may examine its caller, recursively, to determine strictness, or it may examine other arguments that are being passed to the callee. In the case that the information is not yet known or the callee is lazy in that argument, we drop back to building a thunk for that argument.
foldlagain, and see how this would work. Recall the definition for
I'll assume we can perform some analysis to determine that
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f s  = s
foldl f s (h:t) = foldl f (f s h) t
foldlis strict in its third parameter (since we must always evaluate the third parameter to distinguish between the empty list case and the non-empty list case), lazy in its first parameter (since we won't necessarily apply that function to any arguments), and strict in its second parameter iff the first parameter is a binary function strict in both its arguments. Notice that the strictness of
factually depends not just on the type of the third argument, but on its runtime value - if the list is empty,
fwill not be evaluated; if it is nonempty,
fwill be evaluated. This is going to cause problems, as we'll see in a moment.
In the recursive call,
foldl f (f s h) t, we would push
foldlonto a stack. Now we are at the point where we are passing the first argument to
foldl, so we would ask
foldlwhether it is strict in this argument. It responds 'no', so we leave
funevaluated. Next we are at the point we we are about to pass the second argument to
foldl. We again query
foldl, asking if it is strict in its second argument.
foldlchecks its first argument - except if
fis unevaluated, its strictness is unknown, so we have to fall back to thunking the second argument. We're back where we started - the strictness of the function f won't become known until we reach the end of the list, so we end up with the same behavior as before. Ouch! Note that if
fwere already evaluated,
foldlwould be able to determine that the second parameter could be evaluated before being supplied.
It seems we would need another level of analysis to determine that the first parameter,
f, can be made strict if the list being folded over is nonempty. In principle, I don't see why we couldn't do this sort of analysis, but this is starting to get ugly. In addition, we have the problem that when we go to supply
foldl, the list argument hasn't been supplied yet, so we can't inspect the list to determine if it is nonempty. This might not be a fundamental problem since we obviously have a reference to the list even if we haven't formally supplied to
foldlyet. But still, this is getting a lot more complex than I'd initially hoped.