Difference between revisions of "Lazy evaluation"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
m (Added start class)
m (Scheme: Fixed typo)
 
Line 6: Line 6:
  
 
== Scheme ==
 
== 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 <code>car</code>, <code>cdr</code>, and <code>cons</code> have similar counterparts <code>stream-car</code>, <code>stream-cdr</code>, and <code>cons-stream</code> for streams.
+
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 <code>car</code>, <code>cdr</code>, and <code>cons</code> have similar counterparts <code>stream-car</code>, <code>stream-cdr</code>, and <code>cons-stream</code> 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 [[Memoization|memoized]]. If one tries to access the element again, the element is not re-computed: the old value is returned.
 
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 [[Memoization|memoized]]. If one tries to access the element again, the element is not re-computed: the old value is returned.

Latest revision as of 14:41, 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 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.