Although the book-keeping associated with the eduction of even a simple program can appear voluminous, it is worth following to its conclusion, as it eventually reduces down to a simple set of required tasks. We will start with the assumption that nothing has been executed -- there are no stream elements (other than constants) defined. The eduction of the expanded program (see Fig. 8) begins with a demand for a stream fragment, say [ x=10+100, y=10+100 ]10, of the ImageOut stream.
If all the stream elements demanded of a stream are already defined, the demand is satisfied. If demanded stream elements are undefined, the task sourcing of the stream (if it has one) needs to be executed. The ImageOut stream is output by a select task. The demand for the task output ``translates'' first into a demand for [ r=0+3 ] of the level stream. If such an operator ``control'' input is unavailable the required computation is scheduled, and the eduction of the second demand deferred pending its availability. In this case, it is readily available as it has been pre-defined as a program constant. The second demand is for [ x=10+100, y=10+100, d=1 ] of PyrLevel. The mcond operator sourcing PyrLevel has a simple set of conditions, comparing a constant (the context operator) against another constant. It may be completely evaluated when a demand is made. As this demand is for stream elements with a non-zero position along the d dimension, it becomes a demand on NewLevel for [ x=10+100, y=10+100, d=1 ]
The NewLevel stream is sourced by a resample task, which is decimating its input by a factor of two along the y dimension. The demand on its input stream, Low2, is [ x=10+100, y=10+200/2, d=1 ]. This stream is generated by filtering temp2 from which [ x=10+100, y=9+200, d=1 ] is demanded. A demand is also made of gaussian for the filter kernel [ f=0+3 ].
We now repeat these operations, applying them over the x dimension instead: The resample task sourcing temp2 requires [ x=10+200/2, y=9+200, d=1 ] of Low1. This in turn requires [ x=9+200, y=9+200, d=1 ] of temp1, and [ f=0+3 ] of gaussian again.
The source of temp1 is a prev operation (implemented using resample) applied along the d dimension. It transforms the demand into one for [ x=9+200, y=9+200, d=0 ] of PyrLevel. As discussed above, its source is an mcond task. In this case, a demand is made for [ x=9+200, y=9+200 ] of the ImageIn stream.
After all those demands have been calculated, the actual work required can be identified. In this case, there are only four tasks that will actually be executed (shown in Table 1), and only three streams (ImageIn, Low1, and Low2) are actually utilized. Any stream which is sourced by a conditional or intensional operator (e.g. mcond, select, or resample) will probably be used only for eduction, and then ignored along with the associated operator during execution. Such a stream will not have any stream elements defined at runtime.