Demand analysis is the process of deciding when to compute the value of a suspended computation in a language which supports suspended computation.
Determining When To Force
As Enso supports dynamic dispatch for methods, we cannot always (even in the presence of a typechecker), statically determine whether or not the function that will eventually be called at any given call site. This means that we have to come up with a more efficient way to handle suspended arguments.
This is done by making the function application responsible for determining when a value passed to it should be evaluated. It works as follows:
- All function arguments are passed suspended.
- The function application is provided with knowledge of its argument declarations.
- As a result, the application is responsible for deciding which arguments should be evaluated up front, and which should be deferred.
- In conjunction with this, the suspended arguments to the application need to be explicitly forced at their use sites in the function body.
Avoiding Pathological Force-Thunk Chains
The above approach does, when done naively, result in a severe performance pathology when passing suspended arguments into functions also expecting suspended arguments. Without intervention, the suspended argument gets wrapped in a chain of thunks that has a significant performance cost to resolve, when necessary.
In order to avoid this issue, we do the following:
- Where a suspended argument is passed into a function, we pass it without explicitly forcing it.
- All other uses of that argument are forced.
The Demand Analysis Algorithm
The algorithm for performing demand analysis on Enso code is as follows.
for (node <- ir): if (node is a usage): if (node is not used in a function application): node = force(node)
This, however, is not entirely sufficient to support codegen. At the time of generating truffle code, we want to know whether a given usage in an argument to a function application needs to be wrapped in a suspension or left alone (as is the case for a suspended term passed to a function).
To this end, we instead explicitly mark the arguments to the application with whether or not they should be suspended during codegen.