Code Optimizations for Lazy Evaluation

Authors:

Adrienne Bloss, Paul Hudak, and Jonathan Young

Abstract:

Implementations of lazy evaluation for non-strict 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 non-strict 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.

Bibtex:

 @article{blos88
    ,key={blosshudak}
    ,author={Bloss, A. and Hudak, P. and Young, J.}    
    ,title={Code Optimizations for Lazy Evaluation}
    ,journal={Lisp and Symbolic Computation: An International Journal}
    ,year=1988
    ,volume=1
    ,number=2
    ,month=Sep
    ,pages={147-164}
    } 

Links:

LaSC-1-2-pp147-164.pdf