Delayed evaluation lets you work with infinite sequences. Streams are lazy lists: cons-stream delays the cdr. You get the modularity of sequences without the cost of computing everything upfront.
Streams are delayed lists
cons-stream pairs a value with a promise to compute the rest. stream-car returns the value; stream-cdr forces the promise. Only the elements you actually request get computed.
Scheme
; Streams: delay/force for lazy evaluation; BiwaScheme supports delay and force
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define stream-null '())
(define (stream-null? s) (null? s))
(define-syntax cons-stream
(syntax-rules ()
((cons-stream a b) (cons a (delay b)))))
; A finite stream
(define s (cons-stream1 (cons-stream2 (cons-stream3 stream-null))))
(display (stream-car s)) (newline) ; 1
(display (stream-car (stream-cdr s))) (newline) ; 2
(display (stream-car (stream-cdr (stream-cdr s)))) ; 3
Python
# Python generators are the natural equivalent of streamsdef stream_123():
yield1yield2yield3
s = stream_123()
print(next(s)) # 1print(next(s)) # 2print(next(s)) # 3# Each value computed only when requested
Infinite streams
Since the cdr is delayed, a stream can be infinite. The integers, the Fibonacci sequence, and the primes all have natural stream definitions.
Scheme
; Stream primitives (needed in each REPL block)
(define-syntax cons-stream
(syntax-rules ()
((cons-stream a b) (cons a (delay b)))))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
; Infinite stream of integers starting from n
(define (integers-from n)
(cons-stream n (integers-from (+ n 1))))
(define integers (integers-from 1))
; Take the first n elements of a stream
(define (stream-take s n)
(if (= n 0) '()
(cons (stream-car s)
(stream-take (stream-cdr s) (- n 1)))))
(display (stream-take integers 10)) (newline)
; Fibonacci stream
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 01))
(display (stream-take fibs 12))
Python
fromitertoolsimport islice
def integers_from(n):
whileTrue:
yield n
n += 1def fibs():
a, b = 0, 1whileTrue:
yield a
a, b = b, a + b
print(list(islice(integers_from(1), 10)))
print(list(islice(fibs(), 12)))
Exploiting the stream paradigm
Stream-map, stream-filter, and stream-accumulate give you the same composable pipeline as list operations, but lazily. Define a sieve of Eratosthenes in two lines.
Scheme
; Stream primitives
(define-syntax cons-stream
(syntax-rules ()
((cons-stream a b) (cons a (delay b)))))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define stream-null '())
(define (stream-null? s) (null? s))
(define (integers-from n)
(cons-stream n (integers-from (+ n 1))))
(define (stream-take s n)
(if (= n 0) '()
(cons (stream-car s)
(stream-take (stream-cdr s) (- n 1)))))
; Stream utilities
(define (stream-filter pred s)
(cond ((stream-null? s) stream-null)
((pred (stream-car s))
(cons-stream (stream-car s)
(stream-filter pred (stream-cdr s))))
(else (stream-filter pred (stream-cdr s)))))
(define (stream-map f s)
(if (stream-null? s) stream-null
(cons-stream (f (stream-car s))
(stream-map f (stream-cdr s)))))
; Sieve of Eratosthenes
(define (sieve s)
(cons-stream
(stream-car s)
(sieve (stream-filter
(lambda (x) (not (= 0 (modulo x (stream-car s)))))
(stream-cdr s)))))
(define primes (sieve (integers-from 2)))
(display (stream-take primes 15))
Python
fromitertoolsimport islice, count
def sieve(s):
"""Sieve of Eratosthenes as a generator pipeline."""
p = next(s)
yield p
yieldfrom sieve(n for n in s if n % p != 0)
# Note: Python recursion limit will cap this# For production, use an iterative sieveimport sys
sys.setrecursionlimit(2000)
primes = sieve(count(2))
print(list(islice(primes, 15)))
Implicit stream definitions
Streams can be defined implicitly, referring to themselves. The ones stream is 1 followed by itself. Adding two streams element-wise lets you define Fibonacci numbers as: fibs = 0, 1, fibs + (cdr fibs).
Scheme
; Stream primitives
(define-syntax cons-stream
(syntax-rules ()
((cons-stream a b) (cons a (delay b)))))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define (stream-take s n)
(if (= n 0) '()
(cons (stream-car s)
(stream-take (stream-cdr s) (- n 1)))))
; Implicit definitions: streams that reference themselves; add-streams: element-wise addition
(define (add-streams s1 s2)
(cons-stream (+ (stream-car s1) (stream-car s2))
(add-streams (stream-cdr s1) (stream-cdr s2))))
; ones = 1, 1, 1, ...
(define ones (cons-stream1 ones))
; integers = 1, 2, 3, ... (implicit)
(define integers (cons-stream1 (add-streams ones integers)))
(display "integers: ")
(display (stream-take integers 10)) (newline)
; fibs (implicit): each element is sum of two predecessors
(define fibs
(cons-stream0
(cons-stream1
(add-streams fibs (stream-cdr fibs)))))
(display "fibs: ")
(display (stream-take fibs 12))
Python
fromitertoolsimport islice
# Python generators can't self-reference as elegantly# but we can achieve similar patternsdef ones():
whileTrue:
yield1def add_streams(s1, s2):
for a, b inzip(s1, s2):
yield a + b
def integers():
n = 1whileTrue:
yield n
n += 1def fibs():
a, b = 0, 1whileTrue:
yield a
a, b = b, a + b
print("integers:", list(islice(integers(), 10)))
print("fibs:", list(islice(fibs(), 12)))
Streams and delayed evaluation
Streams decouple the order of events from the apparent structure of the computation. You write code that looks like it processes an entire sequence, but only the needed elements are ever computed. This is normal-order evaluation achieved within an applicative-order language.
Scheme
; Stream primitives
(define-syntax cons-stream
(syntax-rules ()
((cons-stream a b) (cons a (delay b)))))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define (integers-from n)
(cons-stream n (integers-from (+ n 1))))
(define (stream-take s n)
(if (= n 0) '()
(cons (stream-car s)
(stream-take (stream-cdr s) (- n 1)))))
; Partial sums: running total of a stream
(define (add-streams s1 s2)
(cons-stream (+ (stream-car s1) (stream-car s2))
(add-streams (stream-cdr s1) (stream-cdr s2))))
(define (partial-sums s)
(cons-stream (stream-car s)
(add-streams (partial-sums s)
(stream-cdr s))))
; 1, 1+2, 1+2+3, ...
(define sums (partial-sums (integers-from 1)))
(display "partial sums: ")
(display (stream-take sums 8))
Scheme streams are cons pairs with a delayed cdr. Python generators are the idiomatic equivalent, using yield for lazy production.
Scheme streams can be rewound (the pair persists). Python generators are one-shot; once consumed, they are exhausted. Use itertools.tee for multiple passes.
Implicit self-referential streams (like (define ones (cons-stream 1 ones))) have no direct Python analog. Python generators cannot reference their own output mid-iteration without explicit feedback loops.
itertools provides count, islice, accumulate, and chain as stream combinators.
Wikipedia: Lazy evaluation