Lazy evaluation

From CS 61A Wiki
Jump to: navigation, search

Lazy evaluation is the idea that expressions should be evaluated only when their values are needed. This technique makes it possible to store infinite or very large sequences in a finite amount of space.

Python

In Python, the Iterator interface provides the means for lazy evaluation: an iterator only releases one element at a time, and each successive element can be computed using the next function. Iterators are guaranteed to have a method supporting next as part of the interface. Unlike with streams, the elements are lost unless stored in a separate data structure, but sometimes this is an advantage: for instance, storing all the permutations of a 15-number sequence is too memory-intensive. One can just process each sequence one-by-one and discard the sequence once finished.

Scheme

Scheme supports lazy evaluation with the Stream built-in data structure. Streams are lazily-evaluated linked lists. Operations from regular list processing in Scheme such as car, cdr, and cons have similar counterparts stream-car, stream-cdr, and cons-stream for streams.

Streams have an additional element of laziness: once a new element is computed for a stream, that value will get saved. In other words, stream values are memoized. If one tries to access the element again, the element is not re-computed: the old value is returned.