3 Chapter 3. Modularity, Objects, and State
3.1 The Environment Model of Evaluation
3.1.1 The Rules for Evaluation
Concepts:
Environment : A sequence of Frames, in which values can be stored.
Frame: A table (possibly empty) of bindings, which associate variable names with their corresponding values.
- Procedure: A pair consisting of some code and a pointer to an Environment. Procedures are created in one way only: by evaluation of a lambda expression.
Code is obtained from the text of the lambda expression.
Environment is the environment in which the lambda expression was evaluated to produce the procedure.
The Rules for Evaluation:
Rule 1: A procedure object is applied to a set of arguments by constructing a frame binding the formal parameters of the call, and then evaluating the body of the procedure in the context of the new environment constructed. The new frame has as its enclosing environment the environment part of the procedure object being applied.
Rule 2: A lambda-expression is evaluated relative to a given environment as follows: a new procedure object is formed, combining the text (code) of the lambda-expression with a pointer to the environment of evaluation.
Actions and Identity:
We say that an action, A, had an effect on an object, X, (or equivalently, that X was changed by A) if some property, P, which was true of X before A became false of X after A.
We say that two objects, X and Y, are the same if any action which has an effect on X has the same effect on Y.
3.1.2 Apply Simple Procedures
3.1.2.1 Exercise 3.9
In Section 1.2.1 we used the substitution model to analyze two procedures for computing factorials, a recursive version:
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
and an iterative version:
(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))
Show the environment structures created by evaluating (factorial 6) using each version of factorial procedure.
Solution:
Recursive Version:
Iterative Version:
3.1.3 Frames as the Repository of Local State
3.1.3.1 Exercise 3.10
In the make-withdraw procedure, the local variable balance is created as a parameter of make-withdraw. We could also create the local state variable explicitly, using let, as follows:
(define (make-withdraw initial-amount) (let ((balance initial-amount)) (lambda (amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds"))))
(let ((var> <exp>)) <body>)
((lambda (var) <body>) <exp>)
Use the environment model to analyze this alternate version of make-withdraw, drawing figures like the ones above to illustrate the interactions
(define W1 (make-withdraw 100)) (W1 50) (define W2 (make-withdraw 100))
Show that the two versions of make-withdraw create objects with the same behavior. How do the environment structures differ for the two versions?
Solution:
Figure 3: Environment Model of the let Version make-withdraw
The let version of make-withdraw cloned a frame in the environment chain. When accessing the balance variable, the program found it in the frame created by let instead of the frame created by make-withdraw. And there is no behavioral difference between the two versions of make-withdraw.
3.1.4 Internal Definitions
3.1.4.1 Exercise 3.11
In Section 3.2.3 we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of Section 3.1.1:
(define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch)
Show the environment structure generated by the sequence of interactions
(define acc (make-account 50)) ((acc 'deposit) 40) ((acc 'withdraw) 60)
Where is the local state for acc kept? Suppose we define another account
(define acc2 (make-account 100))
How are the local states for the two accounts kept distinct? Which parts of the environment structure are shared between acc and acc2?
Solution:
3.2 Modeling with Mutable Data
3.2.1 A Simulator for Digital Circuits
3.2.1.1 Exercise 3.28
Define an or-gate as a primitive function box. Your or-gate constructor should be similar to and-gate
#lang racket/base (provide or-gate) (require racket/match racket/contract akari-sicp/lib/digital-circuits) (define or-gate-delay 5) (define/match (logical-or _a _b) [(0 0) 0] [(0 1) 1] [(1 0) 1] [(1 1) 1] [(_ _) (error 'logical-or "Invalid signal value")]) (define/contract (or-gate a1 a2 output) (-> wire? wire? wire? void?) (define (or-action-procedure) (define new-value (logical-or (get-signal a1) (get-signal a2))) (after-delay or-gate-delay (lambda () (set-signal! output new-value)))) (add-action! a1 or-action-procedure) (add-action! a2 or-action-procedure)) (module+ test (require akari-sicp/lib/testing) (define a1 (make-wire)) (define a2 (make-wire)) (define output (make-wire)) (run-tests (describe "test or gate" #:before (lambda () (or-gate a1 a2 output)) (it "0 or 0 should be 0" (set-signal! a1 0) (set-signal! a2 0) (propagate) (expect [(get-signal output) => 0])) (it "0 or 1 should be 1" (set-signal! a1 0) (set-signal! a2 1) (propagate) (expect [(get-signal output) => 1])) (it "1 or 0 should be 1" (set-signal! a1 1) (set-signal! a2 0) (propagate) (expect [(get-signal output) => 1])) (it "1 or 1 should be 1" (set-signal! a1 1) (set-signal! a2 1) (propagate) (expect [(get-signal output) => 1])))))
3.2.1.2 Exercise 3.29
Another way to construct an or-gate is as a compound digital logic device, built from and-gates and inverters. Define a procedure or-gate that accomplishes this. What is the delay time of the or-gate in terms of and-gate-delay and inverter-delay?
Solution:
#lang racket/base (require racket/contract akari-sicp/lib/digital-circuits) ;; ┌──────────┐ b1 ;; a1───►│ inverter ┼─────┐ ;; └──────────┘ ┌──▼───────┐ c ┌────────┐ ;; │ and-gate ├──►│inverter┼─►output ;; ┌──────────┐ └──▲───────┘ └────────┘ ;; a2───►│ inverter ┼─────┘ ;; └──────────┘ b2 ;; or-gate-delay = (+ and-gate-delay (* 2 inverter-delay)) (define/contract (or-gate a1 a2 output) (-> wire? wire? wire? void?) (define b1 (make-wire)) (define b2 (make-wire)) (define c (make-wire)) (inverter a1 b1) (inverter a2 b2) (and-gate b1 b2 c) (inverter c output)) (module+ test (require akari-sicp/lib/testing) (run-tests (let ([a1 (make-wire)] [a2 (make-wire)] [output (make-wire)]) (describe "test or gate" #:before (lambda () (or-gate a1 a2 output)) (it "0 or 0 should be 0" (set-signal! a1 0) (set-signal! a2 0) (propagate) (expect [(get-signal output) => 0])) (it "0 or 1 should be 1" (set-signal! a1 0) (set-signal! a2 1) (propagate) (expect [(get-signal output) => 1])) (it "1 or 0 should be 1" (set-signal! a1 1) (set-signal! a2 0) (propagate) (expect [(get-signal output) => 1])) (it "1 or 1 should be 1" (set-signal! a1 1) (set-signal! a2 1) (propagate) (expect [(get-signal output) => 1]))))))
3.2.1.3 Exercise 3.30
ripple-carry adder is the simplest form of parallel adder for adding two n-bit binary numbers. The inputs A₁, A₂, A₃, …, Aₙ and B₁, B₂, B₃, …, Bₙ are the two binary numbers to be added (each Aₖ and Bₖ is a 0 or a 1). The circuit generates S₁, S₂, S₃, …, Sₙ, the n bits of the sum, and C, the carry from the addition.
Write a procedure ripple-carry-adder that generates this circuit. The procedure should take as arguments three lists of n wires each — the Aₖ, the Bₖ, and the Sₖ — and also another wire C.
The major drawback of the ripple-carry adder is the need to wait for the carry signals to propagate. What is the delay needed to obtain the complete output from an n-bit ripple-carry adder, expressed in terms of the delays for and-gates, or-gates, and inverters?
Solution:
#lang racket/base (require racket/contract akari-sicp/lib/digital-circuits (only-in "ch3-ex28.rkt" or-gate)) (define/contract (half-adder a b s c) (-> wire? wire? wire? wire? void?) (define d (make-wire)) (define e (make-wire)) (or-gate a b d) (and-gate a b c) (inverter c e) (and-gate d e s)) (define/contract (full-adder a b c-in sum c-out) (-> wire? wire? wire? wire? wire? void?) (define s (make-wire)) (define c1 (make-wire)) (define c2 (make-wire)) (half-adder b c-in s c1) (half-adder a s sum c2) (or-gate c1 c2 c-out)) (define/contract (ripple-carry-adder as bs c-in ss c-out) (-> (listof wire?) (listof wire?) wire? (listof wire?) wire? void?) (define/contract (connect as bs c-in ss) (-> (listof wire?) (listof wire?) wire? (listof wire?) void?) (if (null? as) (add-action! c-in (lambda () (set-signal! c-out (get-signal c-in)))) (let ([c-out-n (make-wire)]) (full-adder (car as) (car bs) c-in (car ss) c-out-n) (connect (cdr as) (cdr bs) c-out-n (cdr ss))))) (connect as bs c-in ss)) (module+ test (require akari-sicp/lib/testing) ;; Half-adder tests (run-tests (let ([a (make-wire)] [b (make-wire)] [s (make-wire)] [c (make-wire)]) (describe "test half-adder" #:before (lambda () (half-adder a b s c)) (it "0 + 0 should output sum=0, carry=0" (set-signal! a 0) (set-signal! b 0) (propagate) (expect [(get-signal s) => 0] [(get-signal c) => 0])) (it "1 + 0 should output sum=1, carry=0" (set-signal! a 1) (set-signal! b 0) (propagate) (expect [(get-signal s) => 1] [(get-signal c) => 0])) (it "0 + 1 should output sum=1, carry=0" (set-signal! a 0) (set-signal! b 1) (propagate) (expect [(get-signal s) => 1] [(get-signal c) => 0])) (it "1 + 1 should output sum=0, carry=1" (set-signal! a 1) (set-signal! b 1) (propagate) (expect [(get-signal s) => 0] [(get-signal c) => 1]))))) ;; Full-adder tests (run-tests (let ([a (make-wire)] [b (make-wire)] [c-in (make-wire)] [sum (make-wire)] [c-out (make-wire)]) (describe "test full-adder" #:before (lambda () (full-adder a b c-in sum c-out)) (it "0 + 0 + 0 should output sum=0, carry=0" (set-signal! a 0) (set-signal! b 0) (set-signal! c-in 0) (propagate) (expect [(get-signal sum) => 0] [(get-signal c-out) => 0])) (it "1 + 0 + 0 should output sum=1, carry=0" (set-signal! a 1) (set-signal! b 0) (set-signal! c-in 0) (propagate) (expect [(get-signal sum) => 1] [(get-signal c-out) => 0])) (it "0 + 1 + 0 should output sum=1, carry=0" (set-signal! a 0) (set-signal! b 1) (set-signal! c-in 0) (propagate) (expect [(get-signal sum) => 1] [(get-signal c-out) => 0])) (it "0 + 0 + 1 should output sum=1, carry=0" (set-signal! a 0) (set-signal! b 0) (set-signal! c-in 1) (propagate) (expect [(get-signal sum) => 1] [(get-signal c-out) => 0])) (it "1 + 1 + 0 should output sum=0, carry=1" (set-signal! a 1) (set-signal! b 1) (set-signal! c-in 0) (propagate) (expect [(get-signal sum) => 0] [(get-signal c-out) => 1])) (it "1 + 0 + 1 should output sum=0, carry=1" (set-signal! a 1) (set-signal! b 0) (set-signal! c-in 1) (propagate) (expect [(get-signal sum) => 0] [(get-signal c-out) => 1])) (it "0 + 1 + 1 should output sum=0, carry=1" (set-signal! a 0) (set-signal! b 1) (set-signal! c-in 1) (propagate) (expect [(get-signal sum) => 0] [(get-signal c-out) => 1])) (it "1 + 1 + 1 should output sum=1, carry=1" (set-signal! a 1) (set-signal! b 1) (set-signal! c-in 1) (propagate) (expect [(get-signal sum) => 1] [(get-signal c-out) => 1]))))) ;; Ripple-carry-adder tests (run-tests (let ([a-wires (list (make-wire) (make-wire) (make-wire) (make-wire))] [b-wires (list (make-wire) (make-wire) (make-wire) (make-wire))] [sum-wires (list (make-wire) (make-wire) (make-wire) (make-wire))] [c-in (make-wire)] [c-out (make-wire)]) (describe "test ripple-carry-adder (4-bit)" #:before (lambda () (ripple-carry-adder a-wires b-wires c-in sum-wires c-out)) (it "0000 + 0000 + 0 should output sum=0000, carry=0" (for-each (lambda (wire) (set-signal! wire 0)) a-wires) (for-each (lambda (wire) (set-signal! wire 0)) b-wires) (set-signal! c-in 0) (propagate) (expect [(map get-signal sum-wires) => '(0 0 0 0)] [(get-signal c-out) => 0])) (it "0101 + 0011 + 0 should output sum=1000, carry=0" (set-signal! (list-ref a-wires 0) 1) (set-signal! (list-ref a-wires 1) 0) (set-signal! (list-ref a-wires 2) 1) (set-signal! (list-ref a-wires 3) 0) (set-signal! (list-ref b-wires 0) 1) (set-signal! (list-ref b-wires 1) 1) (set-signal! (list-ref b-wires 2) 0) (set-signal! (list-ref b-wires 3) 0) (set-signal! c-in 0) (propagate) (expect [(map get-signal sum-wires) => '(0 0 0 1)] [(get-signal c-out) => 0])) (it "1111 + 0001 + 0 should output sum=0000, carry=1" (for-each (lambda (wire) (set-signal! wire 1)) a-wires) (set-signal! (list-ref b-wires 0) 1) (set-signal! (list-ref b-wires 1) 0) (set-signal! (list-ref b-wires 2) 0) (set-signal! (list-ref b-wires 3) 0) (set-signal! c-in 0) (propagate) (expect [(map get-signal sum-wires) => '(0 0 0 0)] [(get-signal c-out) => 1]))))))
3.2.2 Propagation of Constraints
3.2.2.1 Exercise 3.33
Using primitive multiplier, adder, and constant constraints, define a procedure averager that takes three connectors a, b, and c as inputs and establishes the constraint that the value of c is the average of the values of a and b.
Solution:
#lang racket/base (require (only-in akari-sicp/lib/constraint-system make-connector multiplier constant adder)) (define (averager a b c) (define s (make-connector)) (adder a b s) (define _2 (make-connector)) (constant 2 _2) (define p (make-connector)) (multiplier _2 c s)) (module+ test (require akari-sicp/lib/testing (only-in akari-sicp/lib/constraint-system probe set-value! get-value has-value?)) (run-tests (describe "Averager Tests" (it "propagates from a and b to c" (define a (make-connector)) (define b (make-connector)) (define c (make-connector)) (averager a b c) (probe "c" c) (set-value! a 10 'user) (expect [(set-value! b 20 'user) =$> '("Probe: c = 15")] [(get-value c) => 15] [(has-value? c) => #t])) (it "propagates from a and c to b" (define a (make-connector)) (define b (make-connector)) (define c (make-connector)) (averager a b c) (probe "b" b) (set-value! a 8 'user) (expect [(set-value! c 13 'user) =$> '("Probe: b = 18")] [(get-value b) => 18] [(has-value? b) => #t])) (it "propagates from b and c to a" (define a (make-connector)) (define b (make-connector)) (define c (make-connector)) (averager a b c) (probe "a" a) (set-value! b 50 'user) (expect [(set-value! c 35 'user) =$> '("Probe: a = 20")] [(get-value a) => 20] [(has-value? a) => #t])) (it "raises error on contradiction" (define a (make-connector)) (define b (make-connector)) (define c (make-connector)) (averager a b c) (set-value! a 10 'user) (set-value! b 20 'user) (expect [(set-value! c 20 'user) =!> #rx"contradiction"])))))
3.2.2.2 Exercise 3.34
Louis Reasoner wants to build a squarer, a constraint device with two terminals such that the value of connector b on the second terminal will always be the square of the value a on the first terminal. He proposes the following simple device made from a multiplier:
(define (squarer a b) (multiplier a a b))
There is a serious flaw in this idea. Explain.
Solution:
#lang racket/base (require (only-in akari-sicp/lib/constraint-system make-connector multiplier constant adder)) (define (squarer a b) (multiplier a a b)) (module+ test (require akari-sicp/lib/testing (only-in akari-sicp/lib/constraint-system probe set-value! get-value has-value?)) (run-tests (describe "Squarer Tests" (it "propagates from a to b" (define a (make-connector)) (define b (make-connector)) (squarer a b) (probe "b" b) (expect [(set-value! a 10 'user) =$> '("Probe: b = 100")] [(get-value b) => 100] [(has-value? b) => #t])) (it "propagates from b to a" (define a (make-connector)) (define b (make-connector)) (squarer a b) (probe "a" a) (set-value! b 25 'user) ;; read the logic of multiplier ;; when b is set, the a wait itself to be set ;; so it will not propagate (expect [(get-value a) => #f] [(has-value? a) => #f])))))
3.2.2.3 Exercise 3.35
Ben Bitdiddle tells Louis that one way to avoid the trouble in Exercise 3.34 is to define a squarer as a new primitive constraint. Fill in the missing portions in Ben’s outline for a procedure to implement such a constraint:
(define (squarer a b) (define (process-new-value) (if (has-value? b) (if (< (get-value b) 0) (error "square less than 0: SQUARER" (get-value b)) ⟨alternative1⟩) ⟨alternative2⟩)) (define (process-forget-value) ⟨body1⟩) (define (me request) ⟨body2⟩) ⟨rest of definition⟩ me)
Solution:
#lang racket/base (require racket/match akari-sicp/lib/constraint-system) (define (squarer a b) (define (process-new-value) (if (has-value? b) (if (< (get-value b) 0) (error "square less than 0 ~a" (get-value b)) (set-value! a (sqrt (get-value b)) me)) (when (has-value? a) (set-value! b (* (get-value a) (get-value a)) me)))) (define (process-forget-value) (forget-value! a me) (forget-value! b me) (process-new-value)) (define me (match-lambda ['I-have-a-value (process-new-value)] ['I-lost-my-value (process-forget-value)] [otherwise (error 'squarer "unknown request ~a" otherwise)])) (connect a me) (connect b me) me) (module+ test (require akari-sicp/lib/testing) (run-tests (describe "Squarer Tests" (it "propagates from a to b" (define a (make-connector)) (define b (make-connector)) (squarer a b) (probe "b" b) (expect [(set-value! a 10 'user) =$> '("Probe: b = 100")] [(get-value b) => 100] [(has-value? b) => #t])) (it "propagates from b to a" (define a (make-connector)) (define b (make-connector)) (squarer a b) (probe "a" a) (expect [(set-value! b 25 'user) =$> '("Probe: a = 5")] [(has-value? a) => #t] [(get-value a) => 5])))))
3.2.2.4 Exercise 3.36
Suppose we evaluate the following sequence of expressions in the global environment:
(define a (make-connector)) (define b (make-connector)) (set-value! a 10 'user)
At some time during evaluation of the set-value!, the following expression from the connector’s local procedure is evaluated:
(for-each-except setter inform-about-value constraints)
Draw an environment diagram showing the environment in which the above expression is evaluated.
Solution:
3.2.2.5 Exercise 3.37
The celsius-fahrenheit-converter procedure is cumbersome when compared with a more expression-oriented style of definition, such as
(define (celsius-fahrenheit-converter x) (c+ (c* (c/ (cv 9) (cv 5)) x) (cv 32))) (define C (make-connector)) (define F (celsius-fahrenheit-converter C))
Here c+, c*, etc. are the "constraint" versions of the arithmetic operations. For example, c+ takes two connectors as arguments and returns a connector that is related to these by an adder constraint:
(define (c+ x y) (let ((z (make-connector))) (adder x y z) z))
Define analogous procedures c-, c*, c/, and cv (constant value) that enable us to define compound constraints as in the converter example above.
Solution:
#lang racket/base (provide c+ c- c* c/ cv) (require (only-in akari-sicp/lib/constraint-system make-connector multiplier constant adder)) (define (c+ x y) (define z (make-connector)) (adder x y z) z) (define (c- x y) (define z (make-connector)) (adder z y x) z) (define (c* x y) (define z (make-connector)) (multiplier x y z) z) (define (c/ x y) (define z (make-connector)) (multiplier z y x) z) (define (cv x) (define c (make-connector)) (constant x c) c) (define (celsius-fahrenheit-converter x) (c+ (c* (c/ (cv 9) (cv 5)) x) (cv 32))) (module+ test (require akari-sicp/lib/testing (only-in akari-sicp/lib/constraint-system probe set-value! get-value has-value?)) (run-tests (describe "Celsius to Fahrenheit Converter Tests" (it "converts 0 Celsius to 32 Fahrenheit" (define c (cv 0)) (define f (celsius-fahrenheit-converter c)) (expect [(probe 'f f) =$> '("Probe: f = 32")] [(get-value f) => 32] [(has-value? f) => #t])) (it "converts 100 Celsius to 212 Fahrenheit" (define c (cv 100)) (define f (celsius-fahrenheit-converter c)) (expect [(probe 'f f) =$> '("Probe: f = 212")] [(get-value f) => 212] [(has-value? f) => #t])))))
3.3 Streams
3.3.1 Streams Are Delayed Lists
3.3.1.1 Exercise 3.50
Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in Section 2.2.1, Footnote 12.
(define (stream-map proc . argstreams) (if (⟨??⟩ (car argstreams)) the-empty-stream (⟨??⟩ (apply proc (map ⟨??⟩ argstreams)) (apply stream-map (cons proc (map ⟨??⟩ argstreams))))))
Solution:
#lang racket/base (provide stream-map) (require akari-sicp/lib/stream) (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)))))) (module+ test (require akari-sicp/lib/testing) (run-tests (describe "test stream-map" (it "should work properly" (define sum-stream (stream-map + (stream-enumerate-interval 1 5) (stream-enumerate-interval 11 15))) (expect [sum-stream =>> (list 12 14 16 18 20)])))))
3.3.1.2 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:
(define (show x) (display-line x) x)
What does the interpreter print in response to evaluating each expression in the following sequence?
(define x (stream-map show (stream-enumerate-interval 0 10))) (stream-ref x 5) (stream-ref x 7)
Solution:
#lang racket/base (require akari-sicp/lib/stream "ch3-ex50.rkt") (define (show x) (displayln x) x) (module+ test (require akari-sicp/lib/testing) (define x '()) (run-tests (describe "exercise 3.51" (it "should only evaluation the first element when initialized" (expect [(set! x (stream-map show (stream-enumerate-interval 0 10))) =$> '("0")])) (it "should evaluate up to the 5th element when calling (stream-ref x 5)" (expect [(expect [(stream-ref x 5) => 5]) =$> '("1" "2" "3" "4" "5")])) (it "should evaluate up to the 7th element when calling (stream-ref x 7)" (expect [(expect [(stream-ref x 7) => 7]) =$> '("6" "7")])))))
3.3.1.3 Exercise 3.52
Consider the sequence of expressions
(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)
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.
Solutions:
#lang racket/base (module+ test (require rackunit/text-ui akari-sicp/lib/testing akari-sicp/lib/stream "ch3-ex50.rkt") (run-tests (describe "Exercise 3.52" (it "with memo optimization" (define sum 0) (define (accum x) (set! sum (+ x sum)) sum) (define seq (stream-map accum (stream-enumerate-interval 1 20))) ;; 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ;; 66, 78, 91, 105, 120, 136, 153, 171, 190, 210 (expect [sum => 1 "the first element should be evaluted after initialization"]) (define y (stream-filter even? seq)) (expect [sum => 6 "the first even number is 6"]) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) (expect [sum => 10 "the first number divisible by 5 is 10"]) (expect [(stream-ref y 7) => 136 "the 7th even number is 136"] [sum => 136]) (expect [(display-stream z) =$> '("10" "15" "45" "55" "105" "120" "190" "210")])) (it "without memo optimization" (parameterize ([stream-memo? #f]) (define sum 0) (define (accum x) (set! sum (+ x sum)) sum) ; 1 ; sum: 0 ; seq: 1 (define seq (stream-map accum (stream-enumerate-interval 1 20))) (expect [sum => 1]) ; 2 3 ; sum: 1 3 ; seq: 1 3 6 ; y: _ _ 6 (define y (stream-filter even? seq)) (expect [sum => 6]) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ; 2 3 4 ... ; sum: 6 8 11 ... ; seq: 1 8 11 15 ... ; z: _ _ _ 15 ... (expect [sum => 15]) ; 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ; sum: 15 19 24 30 37 45 54 64 75 87 100 114 129 145 ; seq: 19 24 30 37 45 54 64 75 87 100 114 129 145 162 ; y: 6 _ 24 30 _ _ 54 64 _ _ 100 114 _ _ 162 (expect [(stream-ref y 7) => 162] [sum => 162]) ; 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ; sum: 162 167 173 180 188 197 207 218 230 243 257 272 288 305 323 342 ; seq: 167 173 180 188 197 207 218 230 243 257 272 288 305 323 342 362 ; z: 15 _ _ 180 _ _ _ _ 230 _ _ _ _ 305 _ _ _ (expect [(display-stream z) =$> '("15" "180" "230" "305")]))))))