Some functional programming languages are lazy, meaning that an expression will not be evaluated unless its value is needed. This approach seems to be a very sensible one: the language implementation is attempting to optimize the execution of programs by avoiding any unnecessary computation. Perhaps surprisingly, this evaluation strategy will not always improve the efficiency of programs since it may involve some extra work in managing the delayed evaluation of expressions.
Lazy programming languages are difficult to implement efficiently (see [PJL92]) and economically ([Jon92] describes the `space leaks' which occur in lazy languages when dynamically allocated memory is lost, never to be reclaimed). There are also the pragmatic difficulties with lazy programming which are mentioned in Robin Milner's ``How ML Evolved'': the difficulty of debugging lazy programs and the difficulty of controlling state-change or (perhaps interactive) input and output in lazy languages which are not purely functional. Because of some of these difficulties and the desire to include imperative features in the language, Standard ML uses a call-by-value evaluation strategy: expressions are evaluated irrespective of whether or not the result is ever needed. The lazy evaluation of expressions is then achieved by the programmer rather than by the language. We now discuss techniques for implementing the lazy evaluation of expressions.