LISP and Symbolic Computation, 1(2)147-164
Code Optimizations for Lazy EvaluationAdrienne Bloss, Department of Computer Science, Yale University, New Haven, CT 06520
Paul Hudak, Department of Computer Science, Yale University, New Haven, CT 06520
Jonathan Young, Department of Computer Science, Yale University, New Haven, CT 06520
| Abstract: Implementations of lazy evaluation for nonstrict functional languages usually involve the notion of a delayed representation of the value of an expression, which we call a thunk. We present several techniques for implementing thunks and formalize a class of optimizations that reduce both the space and time overhead of these techniques. The optimizations depend on a compile-time inferencing strategy called path analysis, a generalization of strictness analysis that uncovers order-of-evaluation information. Although the techniques in this paper are focused on the compilation of a nonstrict functional language for a conventional architecture, they are directly applicable to most of the virtual machines commonly used for implementing such languages. The same techniques also apply to other forms of delayed evaluation such as futures and promises. |
[local copy]
![[picture of journal cover]](../LISP.JPG)