Abstract:
Culprit Tracking is a technique to make lazy evaluation in a programming language even
lazier. We sought to develop such a technique after noting poorly-distributed performance
characteristics of graphical user interfaces (GUIs) programmed in lazy languages. A
characteristic aspect of GUI programs is the intensive screen I/O. These programs are
generally highly interactive and very visually oriented. We noted that significant
computation time can be spent to maintain values of cells that either do not contribute to the
output, or cannot possibly have changed at the given time step. We sought a pay-as-you-go
implementation technique that would allow users to better specify which values they
were interested in and only pay when those values could possibly change. Our
breakthrough came when we made the observation that the mouse can only be at one
location on the screen at any one time. When a user event occurs, it occurs at one and only
one location on the screen; the system can therefore safely assume that other locations on
the screen received no new event. This seemingly obvious fact allowed us to arrive at a
new implementation technique we call culprit tracking.
Culprit tracking combines the desirable properties of two other techniques, eager evaluation
and lazy marking, to achieve our stated cost distribution requirement that the cost of
executing a program should be distributed such that the user pays for computing currently
active values that are of interest to the user, and not for computing inactive values or values
not of interest to the user. It is the first such technique to do so.
