Listlessness is Better than Laziness

CMU-CS-85-171

Philip Lee Wadler

August 1984 - Thesis

This thesis is about a style of applicative programming, and a program transformation method that makes programs written in the style more efficient. It concentrates on a single, important source of clarity and inefficiency in applicative programs: the use of structures to communicate between components of a program.

One means of increasing clarity is to divide a program into independent components. In listful style these components communicate by passing intermediate data structures. Usually, but not always, these structures are lists: hence the name. Listful programs are typically composed out of standard list-manipulating functions, such as map , which applies a function to each element of a list to form a new list. Several researchers have advocated a programming style using such functions, but few have emphasized the importance of intermediate lists.

Unfortunately, listful style can be very inefficient. This is due to the space required to store the intermediate lists, and the time required to traverse them. Transforming a program into listless form , in which no intermediate lists or other structures are allowed, eliminates all inefficiency caused by listful style. The transformation method is an algorithm for applying Burstall and Darlington style transformations, based on a simple case analysis. This listless transformer is completely automatic. It might be incorporated as part of an optimizing compiler, or as part of a more sophisticated transformation system.

Several researchers have advocated the use of lazy evaluation with applicative languages. Lazy evaluation makes it possible to write certain elegant programs that would be undefined or impractical under eager normal evaluation. However, because of its high overhead cost, lazy evaluation is seldom used. Among other things, the listless transformer converts programs with lazy evaluation semantics into programs that can be executed by an eager evaluator. This "lazy evaluation at compile-time" makes available the advantages of lazy evaluation without the costs. Thus, when it is applicable, the listless transformer is superior to lazy evaluation.

However, the listless transformer is not always applicable. Given a function definition, the transformer will succeed in finding an equivalent definition in listless form if and only if the original definition can be evaluated using bounded intermediate storage. If the function cannot be converted to listless form, the user may annotate the program to indicate places where intermediate structures may appear.

214 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu