mirror of
https://github.com/correl/sicp.git
synced 2024-11-23 19:19:56 +00:00
394 lines
11 KiB
Org Mode
394 lines
11 KiB
Org Mode
#+TITLE: 3.5 - Streams
|
|
#+STARTUP: indent
|
|
|
|
#+BEGIN_HTML
|
|
<script type="text/javascript"
|
|
src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
|
|
</script>
|
|
#+END_HTML
|
|
|
|
* Streams are Delayed Lists
|
|
** Notes
|
|
#+BEGIN_SRC scheme
|
|
(define x (delay 5))
|
|
|
|
;; is equivalent to
|
|
|
|
(define x (lambda () 5))
|
|
|
|
;; A "thunk" (a function of no arguments, used to delay evaluation of its return value)
|
|
|
|
(force x)
|
|
;; => 5
|
|
#+END_SRC
|
|
|
|
The MIT implementation of =delay= returns a =promise= value. Force
|
|
will evaluate a =promise= if it hasn't yet been computed. The result
|
|
of the evaluation will be memoized for future calls to force.
|
|
|
|
Stream processing explanation: [[https://www.youtube.com/watch?v%3Da2Qt9uxhNSM#t%3D48m00s][MIT OpenCourseWare Lecture 6A]]
|
|
|
|
A stream a sequence built as a pair of an initial value, and a
|
|
procedure to generate the next value and the next procedure to
|
|
continue the sequence.
|
|
** Code
|
|
#+begin_src scheme
|
|
(define (cons-stream a b)
|
|
(cons a (delay b)))
|
|
|
|
(define (stream-car s)
|
|
(car s))
|
|
|
|
(define (stream-cdr s)
|
|
(force (cdr s)))
|
|
|
|
(define the-empty-stream '())
|
|
|
|
(define (stream-ref s n)
|
|
(if (= n 0)
|
|
(stream-car s)
|
|
(stream-ref (stream-cdr s) (- n 1))))
|
|
|
|
(define (stream-map proc s)
|
|
(if (stream-null? s)
|
|
the-empty-stream
|
|
(cons-stream (proc (stream-car s))
|
|
(stream-map proc (stream-cdr s)))))
|
|
|
|
(define (stream-for-each proc s)
|
|
(if (stream-null? s)
|
|
'done
|
|
(begin (proc (stream-car s))
|
|
(stream-for-each proc (stream-cdr s)))))
|
|
#+end_src
|
|
|
|
#+begin_src scheme :tangle yes
|
|
;; ===================================================================
|
|
;; 3.5.1: Streams are Delayed Lists
|
|
;; ===================================================================
|
|
|
|
(define (display-stream s)
|
|
(stream-for-each display-line s))
|
|
|
|
(define (display-line x)
|
|
(newline)
|
|
(display x))
|
|
|
|
(define (stream-enumerate-interval low high)
|
|
(if (> low high)
|
|
the-empty-stream
|
|
(cons-stream
|
|
low
|
|
(stream-enumerate-interval (+ low 1) high))))
|
|
|
|
(define (stream-filter pred stream)
|
|
(cond ((stream-null? stream) the-empty-stream)
|
|
((pred (stream-car stream))
|
|
(cons-stream (stream-car stream)
|
|
(stream-filter pred
|
|
(stream-cdr stream))))
|
|
(else (stream-filter pred (stream-cdr stream)))))
|
|
|
|
#+end_src
|
|
|
|
** Exercises
|
|
*** Exercise 3.50
|
|
Complete the following definition, which generalizes `stream-map' to
|
|
allow procedures that take multiple arguments, analogous to `map' in
|
|
section *Note 2-2-3::, footnote *Note Footnote 12::.
|
|
|
|
#+begin_src scheme
|
|
(define (stream-map proc . argstreams)
|
|
(if (<??> (car argstreams))
|
|
the-empty-stream
|
|
(<??>
|
|
(apply proc (map <??> argstreams))
|
|
(apply stream-map
|
|
(cons proc (map <??> argstreams))))))
|
|
#+end_src
|
|
|
|
----------------------------------------------------------------------
|
|
|
|
#+begin_src scheme
|
|
;; -------------------------------------------------------------------
|
|
;; Exercise 3.50
|
|
;; -------------------------------------------------------------------
|
|
|
|
(define (stream-map proc . argstreams)
|
|
(if (stream-null? (car argstreams))
|
|
the-empty-stream
|
|
(cons-stream
|
|
(apply proc (map stream-car argstreams))
|
|
(apply stream-map
|
|
(cons proc (map stream-cdr argstreams))))))
|
|
#+end_src
|
|
|
|
*** Exercise 3.51
|
|
In order to take a closer look at delayed
|
|
evaluation, we will use the following procedure, which simply
|
|
returns its argument after printing it:
|
|
|
|
#+begin_src scheme
|
|
(define (show x)
|
|
(display-line x)
|
|
x)
|
|
#+end_src
|
|
|
|
What does the interpreter print in response to evaluating each
|
|
expression in the following sequence?(7)
|
|
|
|
#+begin_src scheme
|
|
(define x (stream-map show (stream-enumerate-interval 0 10)))
|
|
|
|
(stream-ref x 5)
|
|
|
|
(stream-ref x 7)
|
|
#+end_src scheme
|
|
|
|
----------------------------------------------------------------------
|
|
|
|
#+begin_src scheme
|
|
(define x (stream-map show (stream-enumerate-interval 0 10)))
|
|
; 0
|
|
;Value: x
|
|
|
|
(stream-ref x 5)
|
|
1
|
|
2
|
|
3
|
|
4
|
|
5
|
|
;Value: 5
|
|
|
|
(stream-ref x 7)
|
|
6
|
|
7
|
|
;Value: 7
|
|
|
|
#+end_src
|
|
*** Exercise 3.52
|
|
Consider the sequence of expressions
|
|
|
|
#+begin_src scheme
|
|
(define sum 0)
|
|
|
|
(define (accum x)
|
|
(set! sum (+ x sum))
|
|
sum)
|
|
|
|
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
|
|
(define y (stream-filter even? seq))
|
|
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
|
|
seq))
|
|
|
|
(stream-ref y 7)
|
|
|
|
(display-stream z)
|
|
#+end_src
|
|
|
|
What is the value of `sum' after each of the above expressions is
|
|
evaluated? What is the printed response to evaluating the
|
|
`stream-ref' and `display-stream' expressions? Would these responses
|
|
differ if we had implemented `(delay <EXP>)' simply as `(lambda ()
|
|
<EXP>)' without using the optimization provided by `memo-proc'?
|
|
Explain
|
|
|
|
----------------------------------------------------------------------
|
|
|
|
#+begin_example
|
|
1 ]=> sum
|
|
;Value: 210
|
|
|
|
1 ]=> (stream-head y 10)
|
|
|
|
;Value 18: (210 204 200 182 174 144 132 90 74 20)
|
|
|
|
1 ]=> (display-stream z)
|
|
|
|
210
|
|
200
|
|
195
|
|
165
|
|
155
|
|
105
|
|
90
|
|
20
|
|
;Value: done
|
|
#+end_example
|
|
|
|
After the definition of =seq=, =sum= is equal to 210. It remains at
|
|
210 through the remainder of the operations.This would not be the
|
|
case if delay were not memoized, as without being so it would be
|
|
recalculated each time the items in the node were resolved, adding to
|
|
the value of =sum= each time, and changing the results captured by =y=
|
|
and =z=.
|
|
* Infinite Streams
|
|
** Notes
|
|
Streams can continue forever if the promise never returns an empty
|
|
stream.
|
|
|
|
Streams can be combined to model complex sequences.
|
|
** Code
|
|
#+begin_src scheme :tangle yes
|
|
;; ===================================================================
|
|
;; 3.5.2: Infinite Streams
|
|
;; ===================================================================
|
|
|
|
(define (integers-starting-from n)
|
|
(cons-stream n (integers-starting-from (+ n 1))))
|
|
|
|
(define integers (integers-starting-from 1))
|
|
|
|
(define (divisible? x y) (= (remainder x y) 0))
|
|
|
|
(define no-sevens
|
|
(stream-filter (lambda (x) (not (divisible? x 7)))
|
|
integers))
|
|
|
|
(define (fibgen a b)
|
|
(cons-stream a (fibgen b (+ a b))))
|
|
|
|
(define fibs (fibgen 0 1))
|
|
|
|
(define (sieve stream)
|
|
(cons-stream
|
|
(stream-car stream)
|
|
(sieve (stream-filter
|
|
(lambda (x)
|
|
(not (divisible? x (stream-car stream))))
|
|
(stream-cdr stream)))))
|
|
|
|
(define primes (sieve (integers-starting-from 2)))
|
|
#+end_src
|
|
*** Defining streams implicitly
|
|
#+begin_src scheme :tangle yes
|
|
(define ones (cons-stream 1 ones))
|
|
|
|
(define (add-streams s1 s2)
|
|
(stream-map + s1 s2))
|
|
|
|
(define integers (cons-stream 1 (add-streams ones integers)))
|
|
|
|
(define fibs
|
|
(cons-stream 0
|
|
(cons-stream 1
|
|
(add-streams (stream-cdr fibs)
|
|
fibs))))
|
|
(define (scale-stream stream factor)
|
|
(stream-map (lambda (x) (* x factor)) stream))
|
|
|
|
(define double (cons-stream 1 (scale-stream double 2)))
|
|
|
|
(define primes
|
|
(cons-stream
|
|
2
|
|
(stream-filter prime? (integers-starting-from 3))))
|
|
|
|
(define (prime? n)
|
|
(define (iter ps)
|
|
(cond ((> (square (stream-car ps)) n) true)
|
|
((divisible? n (stream-car ps)) false)
|
|
(else (iter (stream-cdr ps)))))
|
|
(iter primes))
|
|
#+end_src
|
|
** Exercises
|
|
*** Exercise 3.53
|
|
Without running the program, describe the elements of the stream
|
|
defined by
|
|
|
|
#+begin_src scheme
|
|
(define s (cons-stream 1 (add-streams s s)))
|
|
#+end_src
|
|
|
|
----------------------------------------------------------------------
|
|
|
|
\[
|
|
\sum_{i=1}^\infty 2^i
|
|
\]
|
|
*** Exercise 3.54
|
|
Define a procedure `mul-streams', analogous to `add-streams', that
|
|
produces the elementwise product of its two input streams. Use this
|
|
together with the stream of `integers' to complete the following
|
|
definition of the stream whose nth element (counting from 0) is n + 1
|
|
factorial:
|
|
|
|
#+begin_src scheme
|
|
(define factorials (cons-stream 1 (mul-streams <??> <??>)))
|
|
#+end_src
|
|
|
|
----------------------------------------------------------------------
|
|
|
|
#+begin_src scheme :tangle yes
|
|
(define (mul-streams s1 s2)
|
|
(stream-map * s1 s2))
|
|
|
|
(define factorials (cons-stream 1 (mul-streams (add-streams ones integers) factorials)))
|
|
#+end_src
|
|
*** Exercise 3.55
|
|
Define a procedure `partial-sums' that takes as argument a stream S
|
|
and returns the stream whose elements are S_0, S_0 + S_1, S_0 + S_1 +
|
|
S_2, .... For example, `(partial-sums integers)' should be the stream
|
|
1, 3, 6, 10, 15, ....
|
|
* Exploiting the Stream Paradigm
|
|
** Notes
|
|
Streams and their property of delayed evaluation can be used to build
|
|
abstractions over the sequences and computations used to generate
|
|
them. The examples are the square-root stream and the pi streams being
|
|
accelerated via a generic stream transformation method.
|
|
|
|
* Streams and Delayed Evaluation
|
|
** Notes
|
|
#+BEGIN_QUOTE
|
|
...stream models of systems with loops may require uses of delay
|
|
beyond the “hidden” delay supplied by cons-stream.
|
|
#+END_QUOTE
|
|
|
|
#+BEGIN_QUOTE
|
|
Unfortunately, including delays in procedure calls wreaks havoc with
|
|
our ability to design programs that depend on the order of events,
|
|
such as programs that use assignment, mutate data, or perform input or
|
|
output.
|
|
|
|
...
|
|
|
|
As far as anyone knows, mutability and delayed evaluation do not mix
|
|
well in programming languages, and devising ways to deal with both of
|
|
these at once is an active area of research.
|
|
#+END_QUOTE
|
|
|
|
* Modularity of Functional Programs and Modularity of Objects
|
|
|
|
** Notes
|
|
Random number generation can be implemented as an infinite stream
|
|
instantiated with some seed.
|
|
|
|
*** A functional-programming view of time
|
|
#+BEGIN_QUOTE
|
|
We can model a changing quantity, such as the local state of some
|
|
object, using a stream that represents the time history of successive
|
|
states. In essence, we represent time explicitly, using streams, so
|
|
that we decouple time in our simulated world from the sequence of
|
|
events that take place during evaluation.
|
|
#+END_QUOTE
|
|
|
|
Events over time can be merged / serialized (deterministically?) into
|
|
a stream of events.
|
|
|
|
#+BEGIN_QUOTE
|
|
This is precisely the same constraint that we had to deal with in
|
|
3.4.1, where we found the need to introduce explicit synchronization
|
|
to ensure a “correct” order of events in concurrent processing of
|
|
objects with state. Thus, in an attempt to support the functional
|
|
style, the need to merge inputs from different agents reintroduces the
|
|
same problems that the functional style was meant to eliminate.
|
|
#+END_QUOTE
|
|
|
|
With a working merge solution, a system can be designed in a
|
|
functional way, operating on a stream of state and inputs.
|
|
|
|
The Erlang/OTP generic server, generic fsm and other behaviours are
|
|
implemented in such a way that input streams received concurrently are
|
|
merged by the vm and combined with the state of the process as a
|
|
single stream pairing the current state with the next input to
|
|
process, allowing an Erlang developer to build a functional interface
|
|
with the complexities of concurrency abstracted away.
|