TICS

Environments the easy way

Rubén Barroso — Mon, 13 Jun 2011 09:24:06 +0000

What is the result of evaluating the following expression in Scheme?

1 2	(let ((a 9)) (* a 3))

If you answered 27, then think again. In actuality, this question does not make any sense, or partially at least. In Scheme, as well as in other programming languages, an expression is evaluated with respect to an environment that assigns values to its variables. In our example, this includes a and *.

But, what is an environment? There are several ways to explain and represent those, but let’s focus on the functional approach. Say is the finite set of all Scheme symbols, and is the set of all Scheme values, then an environment is a function:

That is, given a symbol that represents a variable, env returns a value for that variable. In an environment env₁ where the symbol x is associated or bound to the value 10, the straightforward expression:

(+ x 4)

is further evaluated to (+ env₁(x) 4), that is 14. Such an environment can be easily represented with a diagram:

Here, env_empty represents a function that returns an unspecified value, or rather, more commonly, raises an error for any symbol in the input. On top of that, env₁ simply augments env_empty with a new association or binding for x. Such extension implies the existence of another function:

extend_env takes an environment, symbols and values for some , and returns an environment that augments the initial with the new bindings. Environments are constructed by starting with env_empty, and repeatedly extending it with extend_env. In diagrams like the one above, the vertical arrows, created by the application of extend_env, relate an environment with its enclosing environment.

Note that, by definition of a function, a symbol cannot be bound to more than one value. This is quite interesting, for it is usual to extend an environment by including bindings for new and existing symbols. To illustrate this, if we want to extend env₁ with new bindings for y and z, we would have:

With this new environment env₂, the previous example expression is evaluated to (+ env₂(x) 4), which is still 14. The procedure works as follows:

Starting from env₂(x), we look up the first binding for the symbol x in the sequence of frames (the colored boxes containing the associations).
We eventually find a value for x or reach env_empty and get a nasty error. In the latter, we would say that x is unbound in env₂.

Now, we extend env₂ with a new binding for x:

In this last environment configuration, our expression is evaluated to (+ env₃(x) 4), but now the result is 23, not 14. We consciously shadowed the previous binding for x in env₁, retrieving 19 instead of 10.

Therefore, in our initial example:

1 2	(let ((a 9)) (* a 3))

If we evaluate it in an environment that shadows the symbol * to return (λ (x y) (+ ( * x y) 4)), then the result would be 31, not 27. Such is the importance of environments.

In a forthcoming article, we shall explain how this concept of environment can be used to implement lexical scoping through the creation of closures.

Exercise 4.1

Rubén Barroso — Mon, 09 May 2011 07:59:00 +0000

From left to right:

1
2
3
4
5
6

(define (list-of-values exps env)
(if (no-operands? exps)
nil
(let ((first (eval (first-operand exps) env)))
(cons first
(list-of-values (rest-operands exps) env)))))

From right to left:

1
2
3
4
5
6

(define (list-of-values exps env)
(if (no-operands? exps)
nil
(let ((rest (list-of-values (rest-operands exps) env)))
(cons (eval (first-operand exps) env)
rest))))

Exercise 3.82

Rubén Barroso — Mon, 09 May 2011 07:57:10 +0000

1
2
3
4
5
6
7
8
9

(define (estimate-integral P x1 x2 y1 y2)
(define experiment-stream
(define test
(lambda () (P (random-in-range (min x1 x2) (max x1 x2))
(random-in-range (min y1 y2) (max y1 y2)))))
(cons-stream test experiment-stream))
(let ((area (* (abs (- x2 x1)) (abs (- y2 y1)))))
(stream-map (lambda (p) (* area p))
(monte-carlo experiment-stream 0 0))))

Exercise 3.81

Rubén Barroso — Mon, 09 May 2011 07:56:28 +0000

Not sure if this works. Cannot test without rand-update:

1
2
3
4
5
6
7
8
9
10
11

(define (rand random-stream)
(define (random-numbers initial-value)
(cons-stream initial-value
(stream-map rand-update random-numbers)))
(define (dispatch op)
(cond ((eq? op 'generate) (random-numbers random-init))
((eq? op 'reset)
(lambda (new-value)
(random-numbers (stream-car (stream-filter (lambda (n) (= n new-value)) (random-numbers random-init))))))
(else (error "Operation not found -- RAND" op))))
dispatch)

Exercise 3.80

Rubén Barroso — Mon, 09 May 2011 07:55:12 +0000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(define (RLC R L C dt)
(lambda (vc0 il0)
(cons (vc-stream vc0 C dt)
(il-stream il0 R L dt))))

(define (vc-stream vc0 C dt)
(define vc (integral (delay dvc) vc0 dt))
(define dvc (scale-stream (delay il-stream) (/ -1.0 C)))
vc)

(define (il-stream il0 R L dt)
(define il (integral (delay dil) il0 dt))
(define dil (add-streams (scale-stream vc-stream (/ 1.0 L))
(scale-stream il (* (- R) (/ 1.0 L)))))
il)

Exercise 3.79

Rubén Barroso — Mon, 09 May 2011 07:54:13 +0000

1
2
3
4
5

(define (solve-2nd f dt y0 dy0)
(define y (integral (delay dy) y0 dt))
(define dy (integral (delay ddy) dy0 dt))
(define ddy (stream-map f y))
y)

Exercise 3.78

Rubén Barroso — Mon, 09 May 2011 07:53:14 +0000

1
2
3
4
5
6

(define (solve-2nd a b dt y0 dy0)
(define y (integral (delay dy) y0 dt))
(define dy (integral (delay ddy) dy0 dt))
(define ddy (add-stream (scale-stream dy a)
(scale-stream y b)))
y)

Exercise 3.77

Rubén Barroso — Mon, 09 May 2011 07:52:31 +0000

1
2
3
4
5
6
7
8
9

(define (integral delayed-integrand initial-value dt)
(cons-stream initial-value
(let ((integral (force delayed-integral)))
(if (stream-null? integrand)
the-empty-stream
(integral (delay (stream-cdr integrand))
(+ (* dt (stream-car integrand))
initial-value)
dt)))))

Exercise 3.76

Rubén Barroso — Mon, 09 May 2011 07:51:46 +0000

1
2
3
4
5
6
7
8
9
10
11

(define (smooth input-stream)
(let ((avpt (/ (+ (stream-car input-stream)
(stream-car (stream-cdr input-stream)))
2)))
(cons-stream avpt
(smooth (stream-cdr input-stream)))))

(define input-example (cons-stream 1 (cons-stream 2 (cons-stream 3 (cons-stream 4 nil)))))

(define (make-zero-crossings input-stream last-value smooth)
(smooth (cons-stream last-value input-stream)))

Exercise 3.75

Rubén Barroso — Mon, 09 May 2011 07:51:02 +0000

Louis’s code is averaging the values from the output, which is not correct. Fixed:

1
2
3
4
5
6

(define (make-zero-crossings input-stream last-value last-avpt)
(let ((avpt (/ (+ last-value (stream-car input-stream)) 2)))
(cons-stream (sign-change-detector avpt last-avpt)
(make-zero-crossings (stream-cdr input-stream)
(stream-car input-stream)
avpt))))

Exercise 3.74

Rubén Barroso — Mon, 09 May 2011 07:49:51 +0000

1
2
3
4
5
6
7

(define (make-zero-crossings input-stream last-value)
(cons-stream
(sign-change-detector (stream-car input-stream) last-value)
(make-zero-crossings (stream-cdr input-stream)
(stream-car input-stream))))

(define zero-crossings (make-zero-crossings sense-data 0))

Alternative:

1
2
3
4

(define zero-crossings
(stream-map sign-change-detector
sense-data
(cons-stream 0 sense-data)))

Exercise 3.73

Rubén Barroso — Mon, 09 May 2011 07:48:01 +0000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(define (integral integrand initial-value dt)
(define int
(cons-stream initial-value
(add-streams (scale-stream integrand dt)
int)))
int)

(define (RC R C dt)
(lambda (i v0)
(define v
(add-streams (integral (scale-stream i (/ 1.0 C)) v0 dt)
(scale-stream i R)))
v))

(define RC1 (RC 5 1 0.5))

Exercise 3.72

Rubén Barroso — Tue, 03 May 2011 08:10:13 +0000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

(define (weight-sum-squares pair)
(let ((i (car pair))
(j (cadr pair)))
(+ (* i i) (* j j))))

(define sum-squares
(weighted-pairs integers integers weight-sum-squares))

(define (iter-sq pairs weight)
(let ((car-pairs (stream-car pairs))
(cadr-pairs (stream-car (stream-cdr pairs)))
(caddr-pairs (stream-car (stream-cdr (stream-cdr pairs))))
(cdddr-pairs (stream-cdr (stream-cdr (stream-cdr pairs)))))
(cond ((stream-null? pairs) nil)
((= (weight car-pairs)
(weight cadr-pairs)
(weight caddr-pairs))
(cons-stream (list (weight car-pairs)
car-pairs
cadr-pairs
caddr-pairs)
(iter-sq cdddr-pairs weight)))
(else (iter-sq (stream-cdr pairs) weight)))))

(define 3way-square-numbers
(iter-sq sum-squares weight-sum-squares))

Test:

1
2
3
4
5
6
7

(display-stream 3way-square-numbers 6)
(325 (1 18) (6 17) (10 15))
(425 (5 20) (8 19) (13 16))
(650 (5 25) (11 23) (17 19))
(725 (7 26) (10 25) (14 23))
(845 (2 29) (13 26) (19 22))
(850 (3 29) (11 27) (15 25))

Exercise 3.71

Rubén Barroso — Tue, 03 May 2011 08:09:10 +0000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(define (weight-sum-cubes pair)
(let ((i (car pair))
(j (cadr pair)))
(+ (* i i i) (* j j j))))

(define sum-cubes
(weighted-pairs integers integers weight-sum-cubes))

(define (iter pairs weight)
(let ((car-pairs (stream-car pairs))
(cadr-pairs (stream-car (stream-cdr pairs)))
(cddr-pairs (stream-cdr (stream-cdr pairs))))
(cond ((stream-null? pairs) nil)
((= (weight car-pairs)
(weight cadr-pairs))
(cons-stream (list (weight car-pairs) car-pairs cadr-pairs)
(iter cddr-pairs weight)))
(else (iter (stream-cdr pairs) weight)))))

(define ramanujan-numbers
(iter sum-cubes weight-sum-cubes))

Test:

1
2
3
4
5
6
7

(display-stream ramanujan-numbers 6)
(1729 (1 12) (9 10))
(4104 (2 16) (9 15))
(13832 (2 24) (18 20))
(20683 (10 27) (19 24))
(32832 (4 32) (18 30))
(39312 (2 34) (15 33))

Exercise 3.70

Rubén Barroso — Tue, 03 May 2011 08:08:01 +0000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

(define (merge-weighted s1 s2 weight)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2))
(weight-s1car (weight (stream-car s1)))
(weight-s2car (weight (stream-car s2))))
(cond ((< = weight-s1car weight-s2car)
(cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))
(else
(cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))

(define (weighted-pairs s t weight)
(cons-stream
(list (stream-car s) (stream-car t))
(merge-weighted
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(weighted-pairs (stream-cdr s) (stream-cdr t) weight)
weight)))

(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))

(define (stream-for-each proc s n)
(cond ((stream-null? s) (newline))
((= n 0) (newline))
(else (begin (proc (stream-car s))
(stream-for-each proc (stream-cdr s) (- n 1))))))

(define (display-stream s n)
(stream-for-each display-line s n))

(define (display-line x)
(newline)
(display x))

1
2
3
4
5
6
7

(define (accumulated pair)
(let ((i (car pair))
(j (cadr pair)))
(+ i j)))

(define accumulated-pairs
(weighted-pairs integers integers accumulated))

Test:

1
2
3
4
5
6
7
8
9
10
11

(display-stream accumulated-pairs 10)
(1 1)
(1 2)
(1 3)
(2 2)
(1 4)
(2 3)
(1 5)
(2 4)
(3 3)
(1 6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

(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)))))

(define (divisible? n)
(or (= 0 (remainder n 2))
(= 0 (remainder n 3))
(= 0 (remainder n 5))))

(define (weight-non-divisible pair)
(let ((i (car pair))
(j (cadr pair)))
(+ (* 2 i) (* 3 j) (* 5 i j))))

(define non-divisible
(stream-filter (lambda (x) (not (divisible? x))) integers))

(define non-divisible-pairs
(weighted-pairs non-divisible non-divisible weight-non-divisible))

Test:

1
2
3
4
5
6
7
8
9
10
11

(display-stream non-divisible-pairs 10)
(1 1)
(1 7)
(1 11)
(1 13)
(1 17)
(1 19)
(1 23)
(1 29)
(1 31)
(7 7)

Exercise 3.69

Rubén Barroso — Tue, 03 May 2011 08:05:25 +0000

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(define (triples s t u)
(cons-stream
(list (stream-car s) (stream-car t) (stream-car u))
(interleave
(stream-map (lambda (x) (append (list (stream-car s)) x))
(stream-cdr (pairs t u)))
(triples (stream-cdr s) (stream-cdr t) (stream-cdr u)))))

(define pythagorean
(stream-filter
(lambda (x)
(= (+ (square (car x)) (square (cadr x)))
(square (caddr x))))
(triples integer integer integer)))

Exercise 3.68

Rubén Barroso — Tue, 03 May 2011 08:04:32 +0000

Louis’s version causes an infinite loop because there is no delayed evaluation of the recursive call (using the cons-stream left out).

Exercise 3.67

Rubén Barroso — Tue, 03 May 2011 08:03:16 +0000

1
2
3
4
5
6
7
8
9
10

(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(interleave
(stream-map (lambda (x) (list x (stream-car t)))
(stream-cdr s))
(pairs (stream-cdr s) (stream-cdr t))))))

Exercise 3.66

Rubén Barroso — Mon, 02 May 2011 08:12:44 +0000

1 2	(pairs integers integers) => (0,0), (0,1), (1,1), (0,2), (1,2), (2,2) ...

Pair	Pos	n
(1,1)	1	1
(1,2)	2	2
(2,2)	3
(1,3)	4	3
(2,3)	5
(1,4)	6	4
(3,3)	7
(1,5)	8	5
(2,4)	9
…	…	…

(1,n) appears in position 2n-2. For n=100, 2·100-2=198 positions for (1,100).

Exercise 3.65

Rubén Barroso — Mon, 02 May 2011 08:04:00 +0000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

(define (ln2-summands n)
(cons-stream (/ 1.0 n)
(stream-map - (ln2-summands (+ n 1)))))

(define ln2-stream
(partial-sums (ln2-summands 1)))

(define (euler-transform s)
(let ((s0 (stream-ref s 0)) ; S[n-1]
(s1 (stream-ref s 1)) ; S[n]
(s2 (stream-ref s 2))) ; S[n+1]
(cons-stream (- s2 (/ (square (- s2 s1))
(+ s0 (* -2 s1) s2)))
(euler-transform (stream-cdr s)))))

(define (square n) (* n n))

(define (make-tableau transform s)
(cons-stream s
(make-tableau transform
(transform s))))

(define (accelerated-sequence transform s)
(stream-map stream-car
(make-tableau transform s)))

(define acc-ln2 (accelerated-sequence euler-transform
ln2-stream))

Convergence test:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(stream-ref acc-ln2 0)
=> 1.0

(stream-ref acc-ln2 1)
=> 0.7

(stream-ref acc-ln2 2)
=> 0.6932773109243697

(stream-ref acc-ln2 3)
=> 0.6931488693329254

(stream-ref acc-ln2 4)
=> 0.6931471960735491

(stream-ref acc-ln2 5)
=> 0.6931471806635636