Difference between revisions of "Lazy evaluation"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(Added lazy evaluation article)
 
m (Added start class)
Line 1: Line 1:
 +
{{Start-class}}
 
'''Lazy evaluation''' is the idea that [[expression]]s 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.
 
'''Lazy evaluation''' is the idea that [[expression]]s 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.
  

Revision as of 14:40, 8 August 2014

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 built-in data structure Stream. Streams are lazily-evaluated linked lists. Operation 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.