Mutable Data

⇡

3.1Assignment and Local State

We ordinarily view the world as populated by independent objects, each of which has a state that changes over time. An object is said to “have state” if its behavior is influenced by its history. A bank account, for example, has state in that the answer to the question “Can I withdraw $100?” depends upon the history of deposit and withdrawal transactions. We can characterize an object’s state by one or more state variables, which among them maintain enough information about history to determine the object’s current behavior. In a simple banking system, we could characterize the state of an account by a current balance rather than by remembering the entire history of account transactions.

In a system composed of many objects, the objects are rarely completely independent. Each may influence the states of others through interactions, which serve to couple the state variables of one object to those of other objects. Indeed, the view that a system is composed of separate objects is most useful when the state variables of the system can be grouped into closely coupled subsystems that are only loosely coupled to other subsystems.

This view of a system can be a powerful framework for organizing computational models of the system. For such a model to be modular, it should be decomposed into computational objects that model the actual objects in the system. Each computational object must have its own local state variables describing the actual object’s state. Since the states of objects in the system being modeled change over time, the state variables of the corresponding computational objects must also change. If we choose to model the flow of time in the system by the elapsed time in the computer, then we must have a way to construct computational objects whose behaviors change as our programs run. In particular, if we wish to model state variables by ordinary symbolic names in the programming language, then the language must provide an assignment operator to enable us to change the value associated with a name.

3.1.1Local State Variables

To illustrate what we mean by having a computational object with time-varying state, let us model the situation of withdrawing money from a bank account. We will do this using a procedure withdraw, which takes as argument an amount to be withdrawn. If there is enough money in the account to accommodate the withdrawal, then withdraw should return the balance remaining after the withdrawal. Otherwise, withdraw should return the message Insufficient funds. For example, if we begin with $100 in the account, we should obtain the following sequence of responses using withdraw:

def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance -= amount
        return balance
    return withdraw

>>> withdraw = make_withdraw(100)
>>> withdraw(25)
75
>>> withdraw(25)
50
>>> withdraw(60)
'Insufficient funds'
>>> withdraw(15)
35

(withdraw 25)
75

(withdraw 25)
50

(withdraw 60)
"Insufficient funds"

(withdraw 15)
35

Observe that the expression (withdraw 25), evaluated twice, yields different values. This is a new kind of behavior for a procedure. Until now, all our procedures could be viewed as specifications for computing mathematical functions. A call to a procedure computed the value of the function applied to the given arguments, and two calls to the same procedure with the same arguments always produced the same result.

To implement withdraw, we can use a variable balance to indicate the balance of money in the account and define withdraw as a procedure that accesses balance. The withdraw procedure checks to see if balance is at least as large as the requested amount. If so, withdraw decrements balance by amount and returns the new value of balance. Otherwise, withdraw returns the Insufficient funds message. Here are the definitions of balance and withdraw:

balance = 100

def withdraw(amount):
    global balance
    if balance >= amount:
        balance = balance - amount
        return balance
    else:
        return "Insufficient funds"

(define balance 100)

(define (withdraw amount)
  (if (>= balance amount)
  (begin (set! balance (- balance amount))
  balance)
  "Insufficient funds"))

Decrementing balance is accomplished by the expression

balance = balance - amount

(set! balance (- balance amount))

This uses the set! special form, whose syntax is

name = new_value

(set! ⟨name⟩ ⟨new-value⟩)

Here ⟨name⟩ is a symbol and ⟨new-value⟩ is any expression. Set! changes ⟨name⟩ so that its value is the result obtained by evaluating ⟨new-value⟩. In the case at hand, we are changing balance so that its new value will be the result of subtracting amount from the previous value of balance.

Withdraw also uses the begin special form to cause two expressions to be evaluated in the case where the if test is true: first decrementing balance and then returning the value of balance. In general, evaluating the expression

# (begin ⟨exp₁⟩ ⟨exp₂⟩ … ⟨expₖ⟩)
# Sequential execution of expressions; the value of the begin is the value of the last expression.

...  # ⟨exp₁⟩
...  # ⟨exp₂⟩
# ...
result = ...  # ⟨expₖ⟩
result

(begin ⟨exp₁⟩ ⟨exp₂⟩ … ⟨expₖ⟩)

causes the expressions $\langle exp_{1} \rangle$ through $\langle exp_{k} \rangle$ to be evaluated in sequence and the value of the final expression $\langle exp_{k} \rangle$ to be returned as the value of the entire begin form.

Although withdraw works as desired, the variable balance presents a problem. As specified above, balance is a name defined in the global environment and is freely accessible to be examined or modified by any procedure. It would be much better if we could somehow make balance internal to withdraw, so that withdraw would be the only procedure that could access balance directly and any other procedure could access balance only indirectly (through calls to withdraw). This would more accurately model the notion that balance is a local state variable used by withdraw to keep track of the state of the account.

We can make balance internal to withdraw by rewriting the definition as follows:

def _make_new_withdraw():
    balance = 100
    def withdraw(amount):
        nonlocal balance
        if balance >= amount:
            balance = balance - amount
            return balance
        else:
            return "Insufficient funds"
    return withdraw

new_withdraw = _make_new_withdraw()

(define new-withdraw
  (let ((balance 100))
  (lambda (amount)
  (if (>= balance amount)
  (begin (set! balance 
  (- balance amount))
  balance)
  "Insufficient funds"))))

What we have done here is use let to establish an environment with a local variable balance, bound to the initial value 100. Within this local environment, we use lambda to create a procedure that takes amount as an argument and behaves like our previous withdraw procedure. This procedure—returned as the result of evaluating the let expression—is new-withdraw, which behaves in precisely the same way as withdraw but whose variable balance is not accessible by any other procedure.

Combining set! with local variables is the general programming technique we will use for constructing computational objects with local state. Unfortunately, using this technique raises a serious problem: When we first introduced procedures, we also introduced the substitution model of evaluation (1.1.5) to provide an interpretation of what procedure application means. We said that applying a procedure should be interpreted as evaluating the body of the procedure with the formal parameters replaced by their values. The trouble is that, as soon as we introduce assignment into our language, substitution is no longer an adequate model of procedure application. (We will see why this is so in 3.1.3.) As a consequence, we technically have at this point no way to understand why the new-withdraw procedure behaves as claimed above. In order to really understand a procedure such as new-withdraw, we will need to develop a new model of procedure application. In 3.2 we will introduce such a model, together with an explanation of set! and local variables. First, however, we examine some variations on the theme established by new-withdraw.

The following procedure, make-withdraw, creates “withdrawal processors.” The formal parameter balance in make-withdraw specifies the initial amount of money in the account.

def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if balance >= amount:
            balance = balance - amount
            return balance
        else:
            return "Insufficient funds"
    return withdraw

(define (make-withdraw balance)
  (lambda (amount)
  (if (>= balance amount)
  (begin (set! balance 
  (- balance amount))
  balance)
  "Insufficient funds")))

Make-withdraw can be used as follows to create two objects W1 and W2:

# make-withdraw from SICP translated to Python

def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if amount <= balance:
            balance -= amount
            return balance
        else:
            return 'Insufficient funds'
    return withdraw

# REPL interaction
>>> W1 = make_withdraw(100)
>>> W2 = make_withdraw(100)
>>> W1(50)
50
>>> W2(70)
30
>>> W2(40)
'Insufficient funds'
>>> W1(40)
10

(define W1 (make-withdraw 100))
(define W2 (make-withdraw 100))

(W1 50)
50

(W2 70)
30

(W2 40)
"Insufficient funds"

(W1 40)
10

Observe that W1 and W2 are completely independent objects, each with its own local state variable balance. Withdrawals from one do not affect the other.

We can also create objects that handle deposits as well as withdrawals, and thus we can represent simple bank accounts. Here is a procedure that returns a “bank-account object” with a specified initial balance:

def make_account(balance):
    # Create an account with an initial balance.
    def withdraw(amount):
        nonlocal balance
        if balance >= amount:
            balance = balance - amount
            return balance
        return "Insufficient funds"

    def deposit(amount):
        nonlocal balance
        balance = balance + amount
        return balance

    def dispatch(m):
        if m == 'withdraw':
            return withdraw
        elif m == 'deposit':
            return deposit
        else:
            raise Exception("Unknown request: MAKE-ACCOUNT {}".format(m))

    return dispatch

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

Each call to make-account sets up an environment with a local state variable balance. Within this environment, make-account defines procedures deposit and withdraw that access balance and an additional procedure dispatch that takes a “message” as input and returns one of the two local procedures. The dispatch procedure itself is returned as the value that represents the bank-account object. This is precisely the message-passing style of programming that we saw in 2.4.3, although here we are using it in conjunction with the ability to modify local variables.

Make-account can be used as follows:

def make_account(balance):
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return "Insufficient funds"
        balance -= amount
        return balance

    def deposit(amount):
        nonlocal balance
        balance += amount
        return balance

    def dispatch(msg):
        if msg == 'withdraw':
            return withdraw
        elif msg == 'deposit':
            return deposit
        else:
            return None

    return dispatch

>>> acc = make_account(100)
>>> acc('withdraw')(50)
50
>>> acc('withdraw')(60)
'Insufficient funds'
>>> acc('deposit')(40)
90
>>> acc('withdraw')(60)
30

(define acc (make-account 100))

((acc 'withdraw) 50)
50

((acc 'withdraw) 60)
"Insufficient funds"

((acc 'deposit) 40)
90

((acc 'withdraw) 60)
30

Each call to acc returns the locally defined deposit or withdraw procedure, which is then applied to the specified amount. As was the case with make-withdraw, another call to make-account

>>> acc2 = make_account(100)

(define acc2 (make-account 100))

will produce a completely separate account object, which maintains its own local balance.

Exercise 3.1: An accumulator is a procedure that is called repeatedly with a single numeric argument and accumulates its arguments into a sum. Each time it is called, it returns the currently accumulated sum. Write a procedure make-accumulator that generates accumulators, each maintaining an independent sum. The input to make-accumulator should specify the initial value of the sum; for example

Python Scheme

def make_accumulator(n):
    def acc(x):
        nonlocal n
        n += x
        return n
    return acc

>>> A = make_accumulator(5)
>>> A(10)
15
>>> A(10)
25

> (define A (make-accumulator 5))
>
> (A 10)
> 15
>
> (A 10)
> 25
> 

Exercise 3.2: In software-testing applications, it is useful to be able to count the number of times a given procedure is called during the course of a computation. Write a procedure make-monitored that takes as input a procedure, f, that itself takes one input. The result returned by make-monitored is a third procedure, say mf, that keeps track of the number of times it has been called by maintaining an internal counter. If the input to mf is the special symbol how-many-calls?, then mf returns the value of the counter. If the input is the special symbol reset-count, then mf resets the counter to zero. For any other input, mf returns the result of calling f on that input and increments the counter. For instance, we could make a monitored version of the sqrt procedure:

Python Scheme

import math

def make_monitored(f):
    # Create a monitored version of f that counts how many times it's been called.
    count = 0
    def monitored(*args):
        nonlocal count
        # If asked how many calls, return the count
        if len(args) == 1 and args[0] == 'how-many-calls?':
            return count
        else:
            count += 1
            return f(*args)
    return monitored

# (define s (make-monitored sqrt))
s = make_monitored(math.sqrt)

# REPL-style demonstration:
# >>> s(100)
# 10.0
# >>> s('how-many-calls?')
# 1

> (define s (make-monitored sqrt))
>
> (s 100)
> 10
>
> (s 'how-many-calls?)
> 1
> 

Exercise 3.3: Modify the make-account procedure so that it creates password-protected accounts. That is, make-account should take a symbol as an additional argument, as in

Python Scheme

>>> acc = make_account(100, 'secret-password')

> (define acc 
> (make-account 100 'secret-password))
> 

The resulting account object should process a request only if it is accompanied by the password with which the account was created, and should otherwise return a complaint:

Python Scheme

def make_account(initial_balance, password):
    balance = initial_balance
    def acc(pwd, action):
        def withdraw(amount):
            nonlocal balance
            if pwd != password:
                return "Incorrect password"
            if amount > balance:
                return "Insufficient funds"
            balance -= amount
            return balance
        def deposit(amount):
            nonlocal balance
            if pwd != password:
                return "Incorrect password"
            balance += amount
            return balance
        if action == 'withdraw':
            return withdraw
        elif action == 'deposit':
            return deposit
        else:
            return lambda amount: "Unknown operation"
    return acc

acc = make_account(100, 'secret-password')

>>> acc('secret-password', 'withdraw')(40)
60
>>> acc('some-other-password', 'deposit')(50)
'Incorrect password'

> ((acc 'secret-password 'withdraw) 40)
> 60
>
> ((acc 'some-other-password 'deposit) 50)
> "Incorrect password"
> 

Exercise 3.4: Modify the make-account procedure of Exercise 3.3 by adding another local state variable so that, if an account is accessed more than seven consecutive times with an incorrect password, it invokes the procedure call-the-cops.

3.1.2The Benefits of Introducing Assignment

As we shall see, introducing assignment into our programming language leads us into a thicket of difficult conceptual issues. Nevertheless, viewing systems as collections of objects with local state is a powerful technique for maintaining a modular design. As a simple example, consider the design of a procedure rand that, whenever it is called, returns an integer chosen at random.

It is not at all clear what is meant by “chosen at random.” What we presumably want is for successive calls to rand to produce a sequence of numbers that has statistical properties of uniform distribution. We will not discuss methods for generating suitable sequences here. Rather, let us assume that we have a procedure rand-update that has the property that if we start with a given number $x_{1}$ and form

x_2 = rand_update(x_1)
x_3 = rand_update(x_2)

x₂ = (rand-update x₁)
x₃ = (rand-update x₂)

then the sequence of values $x_{1}$, $x_{2}$, $x_{3}$, … will have the desired statistical properties.

We can implement rand as a procedure with a local state variable x that is initialized to some fixed value random-init. Each call to rand computes rand-update of the current value of x, returns this as the random number, and also stores this as the new value of x.

# rand is a stateful generator using a closure to hold x
def _make_rand():
    x = random_init
    def rand():
        nonlocal x
        x = rand_update(x)
        return x
    return rand

rand = _make_rand()

(define rand
  (let ((x random-init))
  (lambda () (set! x (rand-update x)) x)))

Of course, we could generate the same sequence of random numbers without using assignment by simply calling rand-update directly. However, this would mean that any part of our program that used random numbers would have to explicitly remember the current value of x to be passed as an argument to rand-update. To realize what an annoyance this would be, consider using random numbers to implement a technique called Monte Carlo simulation.

The Monte Carlo method consists of choosing sample experiments at random from a large set and then making deductions on the basis of the probabilities estimated from tabulating the results of those experiments. For example, we can approximate $\pi$ using the fact that $6/\pi^{2}$ is the probability that two integers chosen at random will have no factors in common; that is, that their greatest common divisor will be 1. To obtain the approximation to $\pi$, we perform a large number of experiments. In each experiment we choose two integers at random and perform a test to see if their GCD is 1. The fraction of times that the test is passed gives us our estimate of $6/\pi^{2}$, and from this we obtain our approximation to $\pi$.

The heart of our program is a procedure monte-carlo, which takes as arguments the number of times to try an experiment, together with the experiment, represented as a no-argument procedure that will return either true or false each time it is run. Monte-carlo runs the experiment for the designated number of trials and returns a number telling the fraction of the trials in which the experiment was found to be true.

import random
import math

def rand():
    # random integer for gcd test
    return random.randint(1, 10**6)

def cesaro_test():
    return math.gcd(rand(), rand()) == 1

def monte_carlo(trials, experiment):
    def iter_(trials_remaining, trials_passed):
        while True:
            if trials_remaining == 0:
                return trials_passed / trials
            elif experiment():
                trials_remaining -= 1
                trials_passed += 1
            else:
                trials_remaining -= 1
    return iter_(trials, 0)

def estimate_pi(trials):
    return math.sqrt(6 / monte_carlo(trials, cesaro_test))

(define (estimate-pi trials)
  (sqrt (/ 6 (monte-carlo trials 
  cesaro-test))))
(define (cesaro-test)
  (= (gcd (rand) (rand)) 1))

(define (monte-carlo trials experiment)
  (define (iter trials-remaining trials-passed)
  (cond ((= trials-remaining 0)
  (/ trials-passed trials))
  ((experiment)
  (iter (- trials-remaining 1) 
  (+ trials-passed 1)))
  (else
  (iter (- trials-remaining 1) 
  trials-passed))))
  (iter trials 0))

Now let us try the same computation using rand-update directly rather than rand, the way we would be forced to proceed if we did not use assignment to model local state:

import math

def estimate_pi(trials):
    return math.sqrt(6 / random_gcd_test(trials, random_init))

def random_gcd_test(trials, initial_x):
    def iter(trials_remaining, trials_passed, x):
        x1 = rand_update(x)
        x2 = rand_update(x1)
        if trials_remaining == 0:
            return trials_passed / trials
        elif math.gcd(x1, x2) == 1:
            return iter(trials_remaining - 1, trials_passed + 1, x2)
        else:
            return iter(trials_remaining - 1, trials_passed, x2)
    return iter(trials, 0, initial_x)

(define (estimate-pi trials)
  (sqrt (/ 6 (random-gcd-test trials 
  random-init))))

(define (random-gcd-test trials initial-x)
  (define (iter trials-remaining 
  trials-passed 
  x)
  (let ((x1 (rand-update x)))
  (let ((x2 (rand-update x1)))
  (cond ((= trials-remaining 0)
  (/ trials-passed trials))
  ((= (gcd x1 x2) 1)
  (iter (- trials-remaining 1)
  (+ trials-passed 1)
  x2))
  (else
  (iter (- trials-remaining 1)
  trials-passed
  x2))))))
  (iter trials 0 initial-x))

While the program is still simple, it betrays some painful breaches of modularity. In our first version of the program, using rand, we can express the Monte Carlo method directly as a general monte-carlo procedure that takes as an argument an arbitrary experiment procedure. In our second version of the program, with no local state for the random-number generator, random-gcd-test must explicitly manipulate the random numbers x1 and x2 and recycle x2 through the iterative loop as the new input to rand-update. This explicit handling of the random numbers intertwines the structure of accumulating test results with the fact that our particular experiment uses two random numbers, whereas other Monte Carlo experiments might use one random number or three. Even the top-level procedure estimate-pi has to be concerned with supplying an initial random number. The fact that the random-number generator’s insides are leaking out into other parts of the program makes it difficult for us to isolate the Monte Carlo idea so that it can be applied to other tasks. In the first version of the program, assignment encapsulates the state of the random-number generator within the rand procedure, so that the details of random-number generation remain independent of the rest of the program.

The general phenomenon illustrated by the Monte Carlo example is this: From the point of view of one part of a complex process, the other parts appear to change with time. They have hidden time-varying local state. If we wish to write computer programs whose structure reflects this decomposition, we make computational objects (such as bank accounts and random-number generators) whose behavior changes with time. We model state with local state variables, and we model the changes of state with assignments to those variables.

It is tempting to conclude this discussion by saying that, by introducing assignment and the technique of hiding state in local variables, we are able to structure systems in a more modular fashion than if all state had to be manipulated explicitly, by passing additional parameters. Unfortunately, as we shall see, the story is not so simple.

Exercise 3.5: Monte Carlo integration is a method of estimating definite integrals by means of Monte Carlo simulation. Consider computing the area of a region of space described by a predicate $P(x,y)$ that is true for points $(x,y)$ in the region and false for points not in the region. For example, the region contained within a circle of radius 3 centered at (5, 7) is described by the predicate that tests whether $(x - 5)^{2} + (y - 7)^{2} \le 3^{2}$. To estimate the area of the region described by such a predicate, begin by choosing a rectangle that contains the region. For example, a rectangle with diagonally opposite corners at (2, 4) and (8, 10) contains the circle above. The desired integral is the area of that portion of the rectangle that lies in the region. We can estimate the integral by picking, at random, points $(x,y)$ that lie in the rectangle, and testing $P(x,y)$ for each point to determine whether the point lies in the region. If we try this with many points, then the fraction of points that fall in the region should give an estimate of the proportion of the rectangle that lies in the region. Hence, multiplying this fraction by the area of the entire rectangle should produce an estimate of the integral.

Implement Monte Carlo integration as a procedure estimate-integral that takes as arguments a predicate P, upper and lower bounds x1, x2, y1, and y2 for the rectangle, and the number of trials to perform in order to produce the estimate. Your procedure should use the same monte-carlo procedure that was used above to estimate $\pi$. Use your estimate-integral to produce an estimate of $\pi$ by measuring the area of a unit circle.

You will find it useful to have a procedure that returns a number chosen at random from a given range. The following random-in-range procedure implements this in terms of the random procedure used in 1.2.6, which returns a nonnegative number less than its input.

Python Scheme

import random

def random_in_range(low, high):
    range_ = high - low
    return low + random.randrange(range_)

> (define (random-in-range low high)
> (let ((range (- high low)))
> (+ low (random range))))
> 

Exercise 3.6: It is useful to be able to reset a random-number generator to produce a sequence starting from a given value. Design a new rand procedure that is called with an argument that is either the symbol generate or the symbol reset and behaves as follows: (rand 'generate) produces a new random number; ((rand 'reset) ⟨new-value⟩) resets the internal state variable to the designated ⟨new-value⟩. Thus, by resetting the state, one can generate repeatable sequences. These are very handy to have when testing and debugging programs that use random numbers.

3.1.3The Costs of Introducing Assignment

As we have seen, the set! operation enables us to model objects that have local state. However, this advantage comes at a price. Our programming language can no longer be interpreted in terms of the substitution model of procedure application that we introduced in 1.1.5. Moreover, no simple model with “nice” mathematical properties can be an adequate framework for dealing with objects and assignment in programming languages.

So long as we do not use assignments, two evaluations of the same procedure with the same arguments will produce the same result, so that procedures can be viewed as computing mathematical functions. Programming without any use of assignments, as we did throughout the first two chapters of this book, is accordingly known as functional programming.

To understand how assignment complicates matters, consider a simplified version of the make-withdraw procedure of 3.1.1 that does not bother to check for an insufficient amount:

def make_simplified_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        balance = balance - amount
        return balance
    return withdraw

W = make_simplified_withdraw(25)

>>> W(20)
5

>>> W(10)
-5

(define (make-simplified-withdraw balance)
  (lambda (amount)
  (set! balance (- balance amount))
  balance))

(define W (make-simplified-withdraw 25))

(W 20)
5

(W 10)
-5

Compare this procedure with the following make-decrementer procedure, which does not use set!:

def make_decrementer(balance):
    return lambda amount: balance - amount

# Example usage:
# >>> dec = make_decrementer(10)
# >>> dec(3)
# 7

(define (make-decrementer balance)
  (lambda (amount)
  (- balance amount)))

Make-decrementer returns a procedure that subtracts its input from a designated amount balance, but there is no accumulated effect over successive calls, as with make-simplified-withdraw:

# make-decrementer: returns a function that subtracts its argument from n
def make_decrementer(n):
    def decrementer(k):
        return n - k
    return decrementer

D = make_decrementer(25)

>>> D(20)
5

>>> D(10)
15

(define D (make-decrementer 25))

(D 20)
5

(D 10)
15

We can use the substitution model to explain how make-decrementer works. For instance, let us analyze the evaluation of the expression

def make_decrementer(n):
    def decrementer(x):
        return x - n
    return decrementer

>>> (make_decrementer(25))(20)
-5

((make-decrementer 25) 20)

We first simplify the operator of the combination by substituting 25 for balance in the body of make-decrementer. This reduces the expression to

>>> (lambda amount: 25 - amount)(20)
5

((lambda (amount) (- 25 amount)) 20)

Now we apply the operator by substituting 20 for amount in the body of the lambda expression:

>>> 25 - 20
5

(- 25 20)

The final answer is 5.

Observe, however, what happens if we attempt a similar substitution analysis with make-simplified-withdraw:

>>> def make_simplified_withdraw(balance):
...     def withdraw(amount):
...         nonlocal balance
...         if amount > balance:
...             return "insufficient funds"
...         else:
...             balance -= amount
...             return balance
...     return withdraw
>>> (make_simplified_withdraw(25))(20)
5

((make-simplified-withdraw 25) 20)

We first simplify the operator by substituting 25 for balance in the body of make-simplified-withdraw. This reduces the expression to

>>> def _anon(amount):
...     global balance
...     balance = 25 - amount
...     return 25
...
>>> _anon(20)
25
>>> balance
5

((lambda (amount) 
  (set! balance (- 25 amount)) 25)
 20)

Now we apply the operator by substituting 20 for amount in the body of the lambda expression:

>>> balance = 25 - 20
25

(set! balance (- 25 20)) 25

If we adhered to the substitution model, we would have to say that the meaning of the procedure application is to first set balance to 5 and then return 25 as the value of the expression. This gets the wrong answer. In order to get the correct answer, we would have to somehow distinguish the first occurrence of balance (before the effect of the set!) from the second occurrence of balance (after the effect of the set!), and the substitution model cannot do this.

The trouble here is that substitution is based ultimately on the notion that the symbols in our language are essentially names for values. But as soon as we introduce set! and the idea that the value of a variable can change, a variable can no longer be simply a name. Now a variable somehow refers to a place where a value can be stored, and the value stored at this place can change. In 3.2 we will see how environments play this role of “place” in our computational model.

Sameness and change

The issue surfacing here is more profound than the mere breakdown of a particular model of computation. As soon as we introduce change into our computational models, many notions that were previously straightforward become problematical. Consider the concept of two things being “the same.”

Suppose we call make-decrementer twice with the same argument to create two procedures:

>>> D1 = make_decrementer(25)
>>> D2 = make_decrementer(25)

(define D1 (make-decrementer 25))
(define D2 (make-decrementer 25))

Are D1 and D2 the same? An acceptable answer is yes, because D1 and D2 have the same computational behavior—each is a procedure that subtracts its input from 25. In fact, D1 could be substituted for D2 in any computation without changing the result.

Contrast this with making two calls to make-simplified-withdraw:

W1 = make_simplified_withdraw(25)
W2 = make_simplified_withdraw(25)

(define W1 (make-simplified-withdraw 25))
(define W2 (make-simplified-withdraw 25))

Are W1 and W2 the same? Surely not, because calls to W1 and W2 have distinct effects, as shown by the following sequence of interactions:

>>> W1(20)
5

>>> W1(20)
-15

>>> W2(20)
5

(W1 20)
5

(W1 20)
-15

(W2 20)
5

Even though W1 and W2 are “equal” in the sense that they are both created by evaluating the same expression, (make-simplified-withdraw 25), it is not true that W1 could be substituted for W2 in any expression without changing the result of evaluating the expression.

A language that supports the concept that “equals can be substituted for equals” in an expression without changing the value of the expression is said to be referentially transparent. Referential transparency is violated when we include set! in our computer language. This makes it tricky to determine when we can simplify expressions by substituting equivalent expressions. Consequently, reasoning about programs that use assignment becomes drastically more difficult.

Once we forgo referential transparency, the notion of what it means for computational objects to be “the same” becomes difficult to capture in a formal way. Indeed, the meaning of “same” in the real world that our programs model is hardly clear in itself. In general, we can determine that two apparently identical objects are indeed “the same one” only by modifying one object and then observing whether the other object has changed in the same way. But how can we tell if an object has “changed” other than by observing the “same” object twice and seeing whether some property of the object differs from one observation to the next? Thus, we cannot determine “change” without some a priori notion of “sameness,” and we cannot determine sameness without observing the effects of change.

As an example of how this issue arises in programming, consider the situation where Peter and Paul have a bank account with $100 in it. There is a substantial difference between modeling this as

>>> peter_acc = make_account(100)
>>> paul_acc = make_account(100)

(define peter-acc (make-account 100))
(define paul-acc (make-account 100))

and modeling it as

>>> peter_acc = make_account(100)
>>> paul_acc = peter_acc

(define peter-acc (make-account 100))
(define paul-acc peter-acc)

In the first situation, the two bank accounts are distinct. Transactions made by Peter will not affect Paul’s account, and vice versa. In the second situation, however, we have defined paul-acc to be the same thing as peter-acc. In effect, Peter and Paul now have a joint bank account, and if Peter makes a withdrawal from peter-acc Paul will observe less money in paul-acc. These two similar but distinct situations can cause confusion in building computational models. With the shared account, in particular, it can be especially confusing that there is one object (the bank account) that has two different names (peter-acc and paul-acc); if we are searching for all the places in our program where paul-acc can be changed, we must remember to look also at things that change peter-acc.

With reference to the above remarks on “sameness” and “change,” observe that if Peter and Paul could only examine their bank balances, and could not perform operations that changed the balance, then the issue of whether the two accounts are distinct would be moot. In general, so long as we never modify data objects, we can regard a compound data object to be precisely the totality of its pieces. For example, a rational number is determined by giving its numerator and its denominator. But this view is no longer valid in the presence of change, where a compound data object has an “identity” that is something different from the pieces of which it is composed. A bank account is still “the same” bank account even if we change the balance by making a withdrawal; conversely, we could have two different bank accounts with the same state information. This complication is a consequence, not of our programming language, but of our perception of a bank account as an object. We do not, for example, ordinarily regard a rational number as a changeable object with identity, such that we could change the numerator and still have “the same” rational number.

Pitfalls of imperative programming

In contrast to functional programming, programming that makes extensive use of assignment is known as imperative programming. In addition to raising complications about computational models, programs written in imperative style are susceptible to bugs that cannot occur in functional programs. For example, recall the iterative factorial program from 1.2.1:

def factorial(n):
    def iter(product, counter):
        if counter > n:
            return product
        else:
            return iter(counter * product, counter + 1)
    return iter(1, 1)

(define (factorial n)
  (define (iter product counter)
  (if (> counter n)
  product
  (iter (* counter product)
  (+ counter 1))))
  (iter 1 1))

Instead of passing arguments in the internal iterative loop, we could adopt a more imperative style by using explicit assignment to update the values of the variables product and counter:

def factorial(n):
    product = 1
    counter = 1
    def iter():
        nonlocal product, counter
        if counter > n:
            return product
        else:
            product = counter * product
            counter = counter + 1
            return iter()
    return iter()

(define (factorial n)
  (let ((product 1)
  (counter 1))
  (define (iter)
  (if (> counter n)
  product
  (begin (set! product (* counter 
  product))
  (set! counter (+ counter 1))
  (iter))))
  (iter)))

This does not change the results produced by the program, but it does introduce a subtle trap. How do we decide the order of the assignments? As it happens, the program is correct as written. But writing the assignments in the opposite order

counter = counter + 1
product = counter * product

(set! counter (+ counter 1))
(set! product (* counter product))

would have produced a different, incorrect result. In general, programming with assignment forces us to carefully consider the relative orders of the assignments to make sure that each statement is using the correct version of the variables that have been changed. This issue simply does not arise in functional programs.

The complexity of imperative programs becomes even worse if we consider applications in which several processes execute concurrently. We will return to this in 3.4. First, however, we will address the issue of providing a computational model for expressions that involve assignment, and explore the uses of objects with local state in designing simulations.

Exercise 3.7: Consider the bank account objects created by make-account, with the password modification described in Exercise 3.3. Suppose that our banking system requires the ability to make joint accounts. Define a procedure make-joint that accomplishes this. Make-joint should take three arguments. The first is a password-protected account. The second argument must match the password with which the account was defined in order for the make-joint operation to proceed. The third argument is a new password. Make-joint is to create an additional access to the original account using the new password. For example, if peter-acc is a bank account with password open-sesame, then

Python Scheme

>>> paul_acc = make_joint(peter_acc, 'open-sesame', 'rosebud')

> (define paul-acc
> (make-joint peter-acc 
> 'open-sesame 
> 'rosebud))
> 

will allow one to make transactions on peter-acc using the name paul-acc and the password rosebud. You may wish to modify your solution to Exercise 3.3 to accommodate this new feature.

Exercise 3.8: When we defined the evaluation model in 1.1.3, we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never specified the order in which the subexpressions should be evaluated (e.g., left to right or right to left). When we introduce assignment, the order in which the arguments to a procedure are evaluated can make a difference to the result. Define a simple procedure f such that evaluating

Python Scheme

>>> f(0) + f(1)

> (+ (f 0) (f 1))
> 

will return 0 if the arguments to + are evaluated from left to right but will return 1 if the arguments are evaluated from right to left.

⇡

3.3Modeling with Mutable Data

Chapter 2 dealt with compound data as a means for constructing computational objects that have several parts, in order to model real-world objects that have several aspects. In that chapter we introduced the discipline of data abstraction, according to which data structures are specified in terms of constructors, which create data objects, and selectors, which access the parts of compound data objects. But we now know that there is another aspect of data that chapter 2 did not address. The desire to model systems composed of objects that have changing state leads us to the need to modify compound data objects, as well as to construct and select from them. In order to model compound objects with changing state, we will design data abstractions to include, in addition to selectors and constructors, operations called

mutators, which modify data objects. For instance, modeling a banking system requires us to change account balances. Thus, a data structure for representing bank accounts might admit an operation

>>> set_balance(..., ...)

(set-balance! ⟨account⟩ ⟨new-value⟩)

that changes the balance of the designated account to the designated new value. Data objects for which mutators are defined are known as mutable data objects.

Chapter 2 introduced pairs as a general-purpose “glue” for synthesizing compound data. We begin this section by defining basic mutators for pairs, so that pairs can serve as building blocks for constructing mutable data objects. These mutators greatly enhance the representational power of pairs, enabling us to build data structures other than the sequences and trees that we worked with in 2.2. We also present some examples of simulations in which complex systems are modeled as collections of objects with local state.

3.3.1Mutable List Structure

The basic operations on pairs—cons, car, and cdr—can be used to construct list structure and to select parts from list structure, but they are incapable of modifying list structure. The same is true of the list operations we have used so far, such as append and list, since these can be defined in terms of cons, car, and cdr. To modify list structures we need new operations.

The primitive mutators for pairs are set-car! and set-cdr!. Set-car! takes two arguments, the first of which must be a pair. It modifies this pair, replacing the car pointer by a pointer to the second argument of set-car!.

As an example, suppose that x is bound to the list ((a b) c d) and y to the list (e f) as illustrated in Figure 3.12. Evaluating the expression (set-car! x y) modifies the pair to which x is bound, replacing its car by the value of y. The result of the operation is shown in Figure 3.13. The structure x has been modified and would now be printed as ((e f) c d). The pairs representing the list (a b), identified by the pointer that was replaced, are now detached from the original structure.

Compare Figure 3.13 with Figure 3.14, which illustrates the result of executing (define z (cons y (cdr x))) with x and y bound to the original lists of Figure 3.12. The variable z is now bound to a new pair created by the cons operation; the list to which x is bound is unchanged.

The set-cdr! operation is similar to set-car!. The only difference is that the cdr pointer of the pair, rather than the car pointer, is replaced. The effect of executing (set-cdr! x y) on the lists of Figure 3.12 is shown in Figure 3.15. Here the cdr pointer of x has been replaced by the pointer to (e f). Also, the list (c d), which used to be the cdr of x, is now detached from the structure.

Cons builds new list structure by creating new pairs, while set-car! and set-cdr! modify existing pairs. Indeed, we could implement cons in terms of the two mutators, together with a procedure get-new-pair, which returns a new pair that is not part of any existing list structure. We obtain the new pair, set its car and cdr pointers to the designated objects, and return the new pair as the result of the cons.

def cons(x, y):
    new = get_new_pair()
    set_car(new, x)
    set_cdr(new, y)
    return new

(define (cons x y)
  (let ((new (get-new-pair)))
  (set-car! new x)
  (set-cdr! new y)
  new))

Exercise 3.12: The following procedure for appending lists was introduced in 2.2.1:

Python Scheme

def append(x, y):
    # Append list x and list y, returning a new list
    if len(x) == 0:
        return y
    else:
        return [x[0]] + append(x[1:], y)

> (define (append x y)
> (if (null? x)
> y
> (cons (car x) (append (cdr x) y))))
> 

Append forms a new list by successively consing the elements of x onto y. The procedure append! is similar to append, but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of x so that its cdr is now y. (It is an error to call append! with an empty x.)

Python Scheme

def last_pair(p):
    # p is a pair represented as [first, rest], where rest is None or another pair
    while p[1] is not None:
        p = p[1]
    return p

def append_bang(x, y):
    last = last_pair(x)
    last[1] = y  # set-cdr! (last-pair x) y
    return x

> (define (append! x y)
> (set-cdr! (last-pair x) y)
> x)
> 

Here last-pair is a procedure that returns the last pair in its argument:

Python Scheme

def last_pair(x):
    # Return the last "pair" (sublist) of list x
    if len(x) == 1:
        return x
    else:
        return last_pair(x[1:])

> (define (last-pair x)
> (if (null? (cdr x))
> x
> (last-pair (cdr x))))
> 

Consider the interaction

Python Scheme

>>> x = ['a', 'b']
>>> y = ['c', 'd']
>>> z = x + y
>>> z
['a', 'b', 'c', 'd']
>>> x[1:]
['b']
>>> w = x
>>> w.extend(y)
>>> w
['a', 'b', 'c', 'd']
>>> x[1:]
['b', 'c', 'd']

> (define x (list 'a 'b))
> (define y (list 'c 'd))
> (define z (append x y))
>
> z
> (a b c d)
>
> (cdr x)
> ⟨response⟩
>
> (define w (append! x y))
>
> w
> (a b c d)
>
> (cdr x)
> ⟨response⟩
> 

What are the missing ⟨response⟩s? Draw box-and-pointer diagrams to explain your answer.

Exercise 3.13: Consider the following make-cycle procedure, which uses the last-pair procedure defined in Exercise 3.12:

Python Scheme

# Assuming pairs are represented as [car, cdr] where cdr is another pair or None
def last_pair(x):
    """Return the last pair in a linked list represented by nested [car, cdr] pairs."""
    p = x
    while p[1] is not None:
        p = p[1]
    return p

def make_cycle(x):
    # set-cdr! (last-pair x) x
    last_pair(x)[1] = x
    return x

> (define (make-cycle x)
> (set-cdr! (last-pair x) x)
> x)
> 

Draw a box-and-pointer diagram that shows the structure z created by

Python Scheme

>>> z = make_cycle(['a', 'b', 'c'])

> (define z (make-cycle (list 'a 'b 'c)))
> 

What happens if we try to compute (last-pair z)?

Exercise 3.14: The following procedure is quite useful, although obscure:

Python Scheme

def mystery(x):
    def loop(x, y):
        if x is None:
            return y
        else:
            temp = x[1]  # cdr
            x[1] = y     # set-cdr!
            return loop(temp, x)
    return loop(x, None)

> (define (mystery x)
> (define (loop x y)
> (if (null? x)
> y
> (let ((temp (cdr x)))
> (set-cdr! x y)
> (loop temp x))))
> (loop x '()))
> 

Loop uses the “temporary” variable temp to hold the old value of the cdr of x, since the set-cdr! on the next line destroys the cdr. Explain what mystery does in general. Suppose v is defined by (define v (list 'a 'b 'c 'd)). Draw the box-and-pointer diagram that represents the list to which v is bound. Suppose that we now evaluate (define w (mystery v)). Draw box-and-pointer diagrams that show the structures v and w after evaluating this expression. What would be printed as the values of v and w?

Sharing and identity

We mentioned in 3.1.3 the theoretical issues of “sameness” and “change” raised by the introduction of assignment. These issues arise in practice when individual pairs are shared among different data objects. For example, consider the structure formed by

x = ['a', 'b']
z1 = [x, x]

(define x (list 'a 'b))
(define z1 (cons x x))

As shown in Figure 3.16, z1 is a pair whose car and cdr both point to the same pair x. This sharing of x by the car and cdr of z1 is a consequence of the straightforward way in which cons is implemented. In general, using cons to construct lists will result in an interlinked structure of pairs in which many individual pairs are shared by many different structures.

In contrast to Figure 3.16, Figure 3.17 shows the structure created by

>>> z2 = [['a', 'b'], 'a', 'b']

(define z2 
  (cons (list 'a 'b) (list 'a 'b)))

In this structure, the pairs in the two (a b) lists are distinct, although the actual symbols are shared.

When thought of as a list, z1 and z2 both represent “the same” list, ((a b) a b). In general, sharing is completely undetectable if we operate on lists using only cons, car, and cdr. However, if we allow mutators on list structure, sharing becomes significant. As an example of the difference that sharing can make, consider the following procedure, which modifies the car of the structure to which it is applied:

def set_to_wow(x):
    # (set-to-wow! x) — set the car of the car of x to 'wow' and return x
    x[0][0] = 'wow'
    return x

(define (set-to-wow! x)
  (set-car! (car x) 'wow)
  x)

Even though z1 and z2 are “the same” structure, applying set-to-wow! to them yields different results. With z1, altering the car also changes the cdr, because in z1 the car and the cdr are the same pair. With z2, the car and cdr are distinct, so set-to-wow! modifies only the car:

z1
((a b) a b)

(set-to-wow! z1)
((wow b) wow b)

z2
((a b) a b)

(set-to-wow! z2)
((wow b) a b)

One way to detect sharing in list structures is to use the predicate eq?, which we introduced in 2.3.1 as a way to test whether two symbols are equal. More generally, (eq? x y) tests whether x and y are the same object (that is, whether x and y are equal as pointers). Thus, with z1 and z2 as defined in Figure 3.16 and Figure 3.17, (eq? (car z1) (cdr z1)) is true and (eq? (car z2) (cdr z2)) is false.

As will be seen in the following sections, we can exploit sharing to greatly extend the repertoire of data structures that can be represented by pairs. On the other hand, sharing can also be dangerous, since modifications made to structures will also affect other structures that happen to share the modified parts. The mutation operations set-car! and set-cdr! should be used with care; unless we have a good understanding of how our data objects are shared, mutation can have unanticipated results.

Exercise 3.15: Draw box-and-pointer diagrams to explain the effect of set-to-wow! on the structures z1 and z2 above.

Exercise 3.16: Ben Bitdiddle decides to write a procedure to count the number of pairs in any list structure. “It’s easy,” he reasons. “The number of pairs in any structure is the number in the car plus the number in the cdr plus one more to count the current pair.” So Ben writes the following procedure:

Python Scheme

def count_pairs(x):
    # Count the number of pair nodes in a nested pair structure.
    # A Scheme pair is represented here as a Python list/tuple of length 2.
    if not (isinstance(x, (list, tuple)) and len(x) == 2):
        return 0
    return count_pairs(x[0]) + count_pairs(x[1]) + 1

# Examples:
# >>> count_pairs(1)
# 0
# >>> count_pairs([1, 2])
# 1
# >>> count_pairs([[1, 2], 3])
# 2
# >>> count_pairs([[1, 2], [3, 4]])
# 3

> (define (count-pairs x)
> (if (not (pair? x))
> 0
> (+ (count-pairs (car x))
> (count-pairs (cdr x))
> 1)))
> 

Show that this procedure is not correct. In particular, draw box-and-pointer diagrams representing list structures made up of exactly three pairs for which Ben’s procedure would return 3; return 4; return 7; never return at all.

Exercise 3.17: Devise a correct version of the count-pairs procedure of Exercise 3.16 that returns the number of distinct pairs in any structure. (Hint: Traverse the structure, maintaining an auxiliary data structure that is used to keep track of which pairs have already been counted.)

Exercise 3.18: Write a procedure that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking successive cdrs would go into an infinite loop. Exercise 3.13 constructed such lists.

Exercise 3.19: Redo Exercise 3.18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.)

Mutation is just assignment

When we introduced compound data, we observed in 2.1.3 that pairs can be represented purely in terms of procedures:

def cons(x, y):
    def dispatch(m):
        if m == 'car':
            return x
        elif m == 'cdr':
            return y
        else:
            raise Exception(f"Undefined operation: CONS {m}")
    return dispatch

def car(z):
    return z('car')

def cdr(z):
    return z('cdr')

(define (cons x y)
  (define (dispatch m)
  (cond ((eq? m 'car) x)
  ((eq? m 'cdr) y)
  (else (error "Undefined 
  operation: CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

The same observation is true for mutable data. We can implement mutable data objects as procedures using assignment and local state. For instance, we can extend the above pair implementation to handle set-car! and set-cdr! in a manner analogous to the way we implemented bank accounts using make-account in 3.1.1:

def cons(x, y):
    def set_x(v):
        nonlocal x
        x = v
    def set_y(v):
        nonlocal y
        y = v
    def dispatch(m):
        if m == 'car':
            return x
        elif m == 'cdr':
            return y
        elif m == 'set-car!':
            return set_x
        elif m == 'set-cdr!':
            return set_y
        else:
            raise Exception("Undefined operation: CONS {}".format(m))
    return dispatch

def car(z):
    return z('car')

def cdr(z):
    return z('cdr')

def set_car(z, new_value):
    (z('set-car!'))(new_value)
    return z

def set_cdr(z, new_value):
    (z('set-cdr!'))(new_value)
    return z

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
  (cond ((eq? m 'car) x)
  ((eq? m 'cdr) y)
  ((eq? m 'set-car!) set-x!)
  ((eq? m 'set-cdr!) set-y!)
  (else (error "Undefined 
  operation: CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

(define (set-car! z new-value)
  ((z 'set-car!) new-value)
  z)

(define (set-cdr! z new-value)
  ((z 'set-cdr!) new-value)
  z)

Assignment is all that is needed, theoretically, to account for the behavior of mutable data. As soon as we admit set! to our language, we raise all the issues, not only of assignment, but of mutable data in general.

Exercise 3.20: Draw environment diagrams to illustrate the evaluation of the sequence of expressions

Python Scheme

>>> x = [1, 2]
>>> z = [x, x]
>>> z[1][0] = 17  # set-car! (cdr z) 17
>>> x[0]
17

> (define x (cons 1 2))
> (define z (cons x x))
>
> (set-car! (cdr z) 17)
>
> (car x)
> 17
> 

using the procedural implementation of pairs given above. (Compare Exercise 3.11.)

3.3.2Representing Queues

The mutators set-car! and set-cdr! enable us to use pairs to construct data structures that cannot be built with cons, car, and cdr alone. This section shows how to use pairs to represent a data structure called a queue. Section 3.3.3 will show how to represent data structures called tables.

A queue is a sequence in which items are inserted at one end (called the rear of the queue) and deleted from the other end (the

front). Figure 3.18 shows an initially empty queue in which the items a and b are inserted. Then a is removed, c and d are inserted, and b is removed. Because items are always removed in the order in which they are inserted, a queue is sometimes called a FIFO (first in, first out) buffer.

In terms of data abstraction, we can regard a queue as defined by the following set of operations: - a constructor: (make-queue) returns an empty queue (a queue containing no items).- two selectors:

(empty-queue? ⟨queue⟩) tests if the queue is empty.

(front-queue ⟨queue⟩) returns the object at the front of the queue, signaling an error if the queue is empty; it does not modify the queue.- two mutators:

(insert-queue! ⟨queue⟩ ⟨item⟩) inserts the item at the rear of the queue and returns the modified queue as its value.

(delete-queue! ⟨queue⟩) removes the item at the front of the queue and returns the modified queue as its value, signaling an error if the queue is empty before the deletion. Because a queue is a sequence of items, we could certainly represent it as an ordinary list; the front of the queue would be the car of the list, inserting an item in the queue would amount to appending a new element at the end of the list, and deleting an item from the queue would just be taking the cdr of the list. However, this representation is inefficient, because in order to insert an item we must scan the list until we reach the end. Since the only method we have for scanning a list is by successive cdr operations, this scanning requires $Θ(n)$ steps for a list of $n$ items. A simple modification to the list representation overcomes this disadvantage by allowing the queue operations to be implemented so that they require $Θ(1)$ steps; that is, so that the number of steps needed is independent of the length of the queue.

The difficulty with the list representation arises from the need to scan to find the end of the list. The reason we need to scan is that, although the standard way of representing a list as a chain of pairs readily provides us with a pointer to the beginning of the list, it gives us no easily accessible pointer to the end. The modification that avoids the drawback is to represent the queue as a list, together with an additional pointer that indicates the final pair in the list. That way, when we go to insert an item, we can consult the rear pointer and so avoid scanning the list.

A queue is represented, then, as a pair of pointers, front-ptr and rear-ptr, which indicate, respectively, the first and last pairs in an ordinary list. Since we would like the queue to be an identifiable object, we can use cons to combine the two pointers. Thus, the queue itself will be the cons of the two pointers. Figure 3.19 illustrates this representation.

To define the queue operations we use the following procedures, which enable us to select and to modify the front and rear pointers of a queue:

def front_ptr(queue):
    return queue[0]

def rear_ptr(queue):
    return queue[1]

def set_front_ptr(queue, item):
    queue[0] = item

def set_rear_ptr(queue, item):
    queue[1] = item

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) 
  (set-car! queue item))
(define (set-rear-ptr! queue item) 
  (set-cdr! queue item))

Now we can implement the actual queue operations. We will consider a queue to be empty if its front pointer is the empty list:

def empty_queue_p(queue):
    return front_ptr(queue) is None

(define (empty-queue? queue) 
  (null? (front-ptr queue)))

The make-queue constructor returns, as an initially empty queue, a pair whose car and cdr are both the empty list:

def make_queue():
    return [[], []]

(define (make-queue) (cons '() '()))

To select the item at the front of the queue, we return the car of the pair indicated by the front pointer:

def front_queue(queue):
    if empty_queue(queue):
        raise ValueError("FRONT called with an empty queue: {}".format(queue))
    else:
        return front_ptr(queue)[0]

(define (front-queue queue)
  (if (empty-queue? queue)
  (error "FRONT called with an 
  empty queue" queue)
  (car (front-ptr queue))))

To insert an item in a queue, we follow the method whose result is indicated in Figure 3.20. We first create a new pair whose car is the item to be inserted and whose cdr is the empty list. If the queue was initially empty, we set the front and rear pointers of the queue to this new pair. Otherwise, we modify the final pair in the queue to point to the new pair, and also set the rear pointer to the new pair.

def insert_queue(queue, item):
    # create a new pair as a two-element list: [item, cdr]
    new_pair = [item, []]
    if empty_queue(queue):
        set_front_ptr(queue, new_pair)
        set_rear_ptr(queue, new_pair)
        return queue
    else:
        set_cdr(rear_ptr(queue), new_pair)
        set_rear_ptr(queue, new_pair)
        return queue

(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
  (cond ((empty-queue? queue)
  (set-front-ptr! queue new-pair)
  (set-rear-ptr! queue new-pair)
  queue)
  (else (set-cdr! (rear-ptr queue) 
  new-pair)
  (set-rear-ptr! queue new-pair)
  queue))))

To delete the item at the front of the queue, we merely modify the front pointer so that it now points at the second item in the queue, which can be found by following the cdr pointer of the first item (see Figure 3.21):

def delete_queue_bang(queue):
    # Mutatively delete the front element of the queue.
    if empty_queue(queue):
        raise Exception("DELETE! called with an empty queue", queue)
    else:
        set_front_ptr_bang(queue, front_ptr(queue)[1])
        return queue

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
  (error "DELETE! called with 
  an empty queue" queue))
  (else (set-front-ptr! 
  queue 
  (cdr (front-ptr queue)))
  queue)))

Exercise 3.21: Ben Bitdiddle decides to test the queue implementation described above. He types in the procedures to the Lisp interpreter and proceeds to try them out:

Python Scheme

> (define q1 (make-queue))
>
> (insert-queue! q1 'a)
> ((a) a)
>
> (insert-queue! q1 'b)
> ((a b) b)
>
> (delete-queue! q1)
> ((b) b)
>
> (delete-queue! q1)
> (() b)
> 

“It’s all wrong!” he complains. “The interpreter’s response shows that the last item is inserted into the queue twice. And when I delete both items, the second b is still there, so the queue isn’t empty, even though it’s supposed to be.” Eva Lu Ator suggests that Ben has misunderstood what is happening. “It’s not that the items are going into the queue twice,” she explains. “It’s just that the standard Lisp printer doesn’t know how to make sense of the queue representation. If you want to see the queue printed correctly, you’ll have to define your own print procedure for queues.” Explain what Eva Lu is talking about. In particular, show why Ben’s examples produce the printed results that they do. Define a procedure print-queue that takes a queue as input and prints the sequence of items in the queue.

Exercise 3.22: Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the make-queue procedure will have the form

Python Scheme

def make_queue():
    front_ptr = ...
    rear_ptr = ...
    # definitions of internal procedures
    # ...
    def dispatch(m):
        ...
    return dispatch

> (define (make-queue)
> (let ((front-ptr … )
> (rear-ptr … ))
> ⟨definitions of internal procedures⟩
> (define (dispatch m) …)
> dispatch))
> 

Complete the definition of make-queue and provide implementations of the queue operations using this representation.

Exercise 3.23: A deque (“double-ended queue”) is a sequence in which items can be inserted and deleted at either the front or the rear. Operations on deques are the constructor make-deque, the predicate empty-deque?, selectors front-deque and rear-deque, and mutators front-insert-deque!, rear-insert-deque!, front-delete-deque!, rear-delete-deque!. Show how to represent deques using pairs, and give implementations of the operations.
All operations should be accomplished in $Θ(1)$ steps.

3.3.3Representing Tables

When we studied various ways of representing sets in Chapter 2, we mentioned in 2.3.3 the task of maintaining a table of records indexed by identifying keys. In the implementation of data-directed programming in 2.4.3, we made extensive use of two-dimensional tables, in which information is stored and retrieved using two keys. Here we see how to build tables as mutable list structures.

We first consider a one-dimensional table, in which each value is stored under a single key. We implement the table as a list of records, each of which is implemented as a pair consisting of a key and the associated value. The records are glued together to form a list by pairs whose cars point to successive records. These gluing pairs are called the backbone of the table. In order to have a place that we can change when we add a new record to the table, we build the table as a headed list. A headed list has a special backbone pair at the beginning, which holds a dummy “record”—in this case the arbitrarily chosen symbol *table*. Figure 3.22 shows the box-and-pointer diagram for the table

a = 1
b = 2
c = 3

a: 1
b: 2
c: 3

To extract information from a table we use the lookup procedure, which takes a key as argument and returns the associated value (or false if there is no value stored under that key). Lookup is defined in terms of the assoc operation, which expects a key and a list of records as arguments. Note that assoc never sees the dummy record. Assoc returns the record that has the given key as its car. Lookup then checks to see that the resulting record returned by assoc is not false, and returns the value (the cdr) of the record.

def lookup(key, table):
    # (define (lookup key table)
    #   (let ((record (assoc key (cdr table))))
    #     (if record
    #         (cdr record)
    #         false)))
    record = assoc(key, table[1:])  # cdr table
    if record:
        return record[1]  # cdr record -> value part
    return False

def assoc(key, records):
    # (define (assoc key records)
    #   (cond ((null? records) false)
    #         ((equal? key (caar records)) (car records))
    #         (else (assoc key (cdr records)))))
    if len(records) == 0:
        return False
    elif key == records[0][0]:  # (caar records)
        return records[0]      # (car records)
    else:
        return assoc(key, records[1:])

(define (lookup key table)
  (let ((record (assoc key (cdr table))))
  (if record
  (cdr record)
  false)))

(define (assoc key records)
  (cond ((null? records) false)
  ((equal? key (caar records)) 
  (car records))
  (else (assoc key (cdr records)))))

To insert a value in a table under a specified key, we first use assoc to see if there is already a record in the table with this key. If not, we form a new record by consing the key with the value, and insert this at the head of the table’s list of records, after the dummy record. If there already is a record with this key, we set the cdr of this record to the designated new value. The header of the table provides us with a fixed location to modify in order to insert the new record.

def assoc(key, records):
    # Return the first record (a [key, value] pair) in records whose key matches,
    # or None if not found.
    for record in records:
        if record[0] == key:
            return record
    return None

def insert_bang(key, value, table):
    # table is represented as a two-element list whose second element is the
    # list of records (each record is a [key, value] list).
    record = assoc(key, table[1])
    if record:
        # set-cdr! record value  -> update record's value
        record[1] = value
    else:
        # set-cdr! table (cons (cons key value) (cdr table))
        new_pair = [key, value]
        table[1] = [new_pair] + table[1]
    return 'ok'

(define (insert! key value table)
  (let ((record (assoc key (cdr table))))
  (if record
  (set-cdr! record value)
  (set-cdr! table
  (cons (cons key value) 
  (cdr table)))))
  'ok)

To construct a new table, we simply create a list containing the symbol *table*:

def make_table():
    return ['*table*']

(define (make-table)
  (list '*table*))

Two-dimensional tables

In a two-dimensional table, each value is indexed by two keys. We can construct such a table as a one-dimensional table in which each key identifies a subtable. Figure 3.23 shows the box-and-pointer diagram for the table

# math:
math = {'+': 43, '-': 45, '*': 42}

# letters:
letters = {'a': 97, 'b': 98}

print(math)
print(letters)

math: +: 43 letters: a: 97
  -: 45 b: 98
  *: 42

which has two subtables. (The subtables don’t need a special header symbol, since the key that identifies the subtable serves this purpose.)

When we look up an item, we use the first key to identify the correct subtable. Then we use the second key to identify the record within the subtable.

def assoc(key, items):
    # assoc: find the first pair in items whose first element equals key
    for item in items:
        if item[0] == key:
            return item
    return False

def lookup(key_1, key_2, table):
    # subtable corresponds to (assoc key-1 (cdr table))
    subtable = assoc(key_1, table[1:])
    if subtable:
        # record corresponds to (assoc key-2 (cdr subtable))
        record = assoc(key_2, subtable[1])
        if record:
            return record[1]
    return False

(define (lookup key-1 key-2 table)
  (let ((subtable (assoc key-1 (cdr table))))
  (if subtable
  (let ((record 
  (assoc key-2 (cdr subtable))))
  (if record (cdr record) false))
  false)))

To insert a new item under a pair of keys, we use assoc to see if there is a subtable stored under the first key. If not, we build a new subtable containing the single record (key-2, value) and insert it into the table under the first key. If a subtable already exists for the first key, we insert the new record into this subtable, using the insertion method for one-dimensional tables described above:

# assoc: find the first pair [key, value] in an association list (alist)
def assoc(key, alist):
    for pair in alist:
        if pair[0] == key:
            return pair
    return None

def insert_bang(key_1, key_2, value, table):
    # table is represented as [header, entries_list]
    # where entries_list is a list of [key, subtable] pairs,
    # and each subtable is a list of [key_2, value] pairs.
    subtable = assoc(key_1, table[1])
    if subtable:
        record = assoc(key_2, subtable[1])
        if record:
            # set-cdr! record value
            record[1] = value
        else:
            # set-cdr! subtable (cons (cons key-2 value) (cdr subtable))
            subtable[1].insert(0, [key_2, value])
    else:
        # set-cdr! table (cons (list key-1 (cons key-2 value)) (cdr table))
        table[1].insert(0, [key_1, [[key_2, value]]])
    return 'ok'

(define (insert! key-1 key-2 value table)
  (let ((subtable (assoc key-1 (cdr table))))
  (if subtable
  (let ((record 
  (assoc key-2 (cdr subtable))))
  (if record
  (set-cdr! record value)
  (set-cdr! 
  subtable
  (cons (cons key-2 value)
  (cdr subtable)))))
  (set-cdr! 
  table
  (cons (list key-1 (cons key-2 value))
  (cdr table)))))
  'ok)

Creating local tables

The lookup and insert! operations defined above take the table as an argument. This enables us to use programs that access more than one table. Another way to deal with multiple tables is to have separate lookup and insert! procedures for each table. We can do this by representing a table procedurally, as an object that maintains an internal table as part of its local state. When sent an appropriate message, this “table object” supplies the procedure with which to operate on the internal table. Here is a generator for two-dimensional tables represented in this fashion:

def make_table():
    # local_table starts with a placeholder as in the Scheme version
    local_table = ['*table*']

    def lookup(key_1, key_2):
        # find subtable whose first element is key_1
        subtable = next((st for st in local_table[1:] if st[0] == key_1), None)
        if subtable:
            # find record whose first element is key_2
            record = next((r for r in subtable[1] if r[0] == key_2), None)
            if record:
                return record[1]
            return False
        return False

    def insert_(key_1, key_2, value):
        # find subtable whose first element is key_1
        subtable = next((st for st in local_table[1:] if st[0] == key_1), None)
        if subtable:
            # find record whose first element is key_2
            record = next((r for r in subtable[1] if r[0] == key_2), None)
            if record:
                # set-cdr! record value  => update record's value
                record[1] = value
            else:
                # prepend new record to the subtable's record list
                subtable[1] = [[key_2, value]] + subtable[1]
        else:
            # prepend a new subtable to local_table's cdr
            new_subtable = [key_1, [[key_2, value]]]
            local_table[1:] = [new_subtable] + local_table[1:]
        return 'ok'

    def dispatch(m):
        if m == 'lookup-proc':
            return lookup
        elif m == 'insert-proc!':
            return insert_
        else:
            raise ValueError("Unknown operation: TABLE " + str(m))

    return dispatch

(define (make-table)
  (let ((local-table (list '*table*)))
  (define (lookup key-1 key-2)
  (let ((subtable 
  (assoc key-1 (cdr local-table))))
  (if subtable
  (let ((record 
  (assoc key-2 
  (cdr subtable))))
  (if record (cdr record) false))
  false)))
  (define (insert! key-1 key-2 value)
  (let ((subtable 
  (assoc key-1 (cdr local-table))))
  (if subtable
  (let ((record 
  (assoc key-2 
  (cdr subtable))))
  (if record
  (set-cdr! record value)
  (set-cdr! 
  subtable
  (cons (cons key-2 value)
  (cdr subtable)))))
  (set-cdr! 
  local-table
  (cons (list key-1
  (cons key-2 value))
  (cdr local-table)))))
  'ok)
  (define (dispatch m)
  (cond ((eq? m 'lookup-proc) lookup)
  ((eq? m 'insert-proc!) insert!)
  (else (error "Unknown operation: 
  TABLE" m))))
  dispatch))

Using make-table, we could implement the get and put operations used in 2.4.3 for data-directed programming, as follows:

operation_table = make_table()
get = operation_table('lookup-proc')
put = operation_table('insert-proc!')

(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))

Get takes as arguments two keys, and put takes as arguments two keys and a value. Both operations access the same local table, which is encapsulated within the object created by the call to make-table.

Exercise 3.24: In the table implementations above, the keys are tested for equality using equal? (called by assoc). This is not always the appropriate test. For instance, we might have a table with numeric keys in which we don’t need an exact match to the number we’re looking up, but only a number within some tolerance of it. Design a table constructor make-table that takes as an argument a same-key? procedure that will be used to test “equality” of keys. Make-table should return a dispatch procedure that can be used to access appropriate lookup and insert! procedures for a local table.

Exercise 3.25: Generalizing one- and two-dimensional tables, show how to implement a table in which values are stored under an arbitrary number of keys and different values may be stored under different numbers of keys. The lookup and insert! procedures should take as input a list of keys used to access the table.

Exercise 3.26: To search a table as implemented above, one needs to scan through the list of records. This is basically the unordered list representation of 2.3.3. For large tables, it may be more efficient to structure the table in a different manner. Describe a table implementation where the (key, value) records are organized using a binary tree, assuming that keys can be ordered in some way (e.g., numerically or alphabetically). (Compare Exercise 2.66 of Chapter 2.)

Exercise 3.27: Memoization (also called tabulation) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from 1.2.2 the exponential process for computing Fibonacci numbers:

Python Scheme

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

> (define (fib n)
> (cond ((= n 0) 0)
> ((= n 1) 1)
> (else (+ (fib (- n 1))
> (fib (- n 2))))))
> 

The memoized version of the same procedure is

Python Scheme

# memoized Fibonacci using a memoize decorator/function
def _memo_fib_impl(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return memo_fib(n - 1) + memo_fib(n - 2)

memo_fib = memoize(_memo_fib_impl)

> (define memo-fib
> (memoize 
> (lambda (n)
> (cond ((= n 0) 0)
> ((= n 1) 1)
> (else 
> (+ (memo-fib (- n 1))
> (memo-fib (- n 2))))))))
> 

where the memoizer is defined as

Python Scheme

def memoize(f):
    table = {}
    def memoized(x):
        # Check if x has been computed before
        if x in table:
            return table[x]
        # Otherwise compute, store, and return
        result = f(x)
        table[x] = result
        return result
    return memoized

> (define (memoize f)
> (let ((table (make-table)))
> (lambda (x)
> (let ((previously-computed-result 
> (lookup x table)))
> (or previously-computed-result
> (let ((result (f x)))
> (insert! x result table)
> result))))))
> 

Draw an environment diagram to analyze the computation of (memo-fib 3). Explain why memo-fib computes the $n^{\text{th}}$ Fibonacci number in a number of steps proportional to $n$. Would the scheme still work if we had simply defined memo-fib to be (memoize fib)?

3.3.4A Simulator for Digital Circuits

Designing complex digital systems, such as computers, is an important engineering activity. Digital systems are constructed by interconnecting simple elements. Although the behavior of these individual elements is simple, networks of them can have very complex behavior. Computer simulation of proposed circuit designs is an important tool used by digital systems engineers. In this section we design a system for performing digital logic simulations. This system typifies a kind of program called an

event-driven simulation, in which actions (“events”) trigger further events that happen at a later time, which in turn trigger more events, and so on.

Our computational model of a circuit will be composed of objects that correspond to the elementary components from which the circuit is constructed. There are wires, which carry digital signals. A digital signal may at any moment have only one of two possible values, 0 and 1. There are also various types of digital function boxes, which connect wires carrying input signals to other output wires. Such boxes produce output signals computed from their input signals. The output signal is delayed by a time that depends on the type of the function box. For example, an

inverter is a primitive function box that inverts its input. If the input signal to an inverter changes to 0, then one inverter-delay later the inverter will change its output signal to 1. If the input signal to an inverter changes to 1, then one inverter-delay later the inverter will change its output signal to 0. We draw an inverter symbolically as in Figure 3.24.
An and-gate, also shown in figure 3.24, is a primitive function box with two inputs and one output. It drives its output signal to a value that is the logical and of the inputs. That is, if both of its input signals become 1, then one and-gate-delay time later the and-gate will force its output signal to be 1; otherwise the output will be 0. An

or-gate is a similar two-input primitive function box that drives its output signal to a value that is the logical or of the inputs. That is, the output will become 1 if at least one of the input signals is 1; otherwise the output will become 0.

We can connect primitive functions together to construct more complex functions. To accomplish this we wire the outputs of some function boxes to the inputs of other function boxes. For example, the half-adder circuit shown in Figure 3.25 consists of an or-gate, two and-gates, and an inverter. It takes two input signals, A and B, and has two output signals, S and C. S will become 1 whenever precisely one of A and B is 1, and C will become 1 whenever A and B are both 1. We can see from the figure that, because of the delays involved, the outputs may be generated at different times. Many of the difficulties in the design of digital circuits arise from this fact.

We will now build a program for modeling the digital logic circuits we wish to study. The program will construct computational objects modeling the wires, which will “hold” the signals. Function boxes will be modeled by procedures that enforce the correct relationships among the signals.

One basic element of our simulation will be a procedure make-wire, which constructs wires. For example, we can construct six wires as follows:

a = make_wire()
b = make_wire()
c = make_wire()
d = make_wire()
e = make_wire()
s = make_wire()

(define a (make-wire))
(define b (make-wire))
(define c (make-wire))
(define d (make-wire))
(define e (make-wire))
(define s (make-wire))

We attach a function box to a set of wires by calling a procedure that constructs that kind of box. The arguments to the constructor procedure are the wires to be attached to the box. For example, given that we can construct and-gates, or-gates, and inverters, we can wire together the half-adder shown in Figure 3.25:

>>> or_gate(a, b, d)
ok

>>> and_gate(a, b, c)
ok

>>> inverter(c, e)
ok

>>> and_gate(d, e, s)
ok

(or-gate a b d)
ok

(and-gate a b c)
ok

(inverter c e)
ok

(and-gate d e s)
ok

Better yet, we can explicitly name this operation by defining a procedure half-adder that constructs this circuit, given the four external wires to be attached to the half-adder:

def half_adder(a, b, s, c):
    d = make_wire()
    e = make_wire()
    or_gate(a, b, d)
    and_gate(a, b, c)
    inverter(c, e)
    and_gate(d, e, s)
    return 'ok'

(define (half-adder a b s c)
  (let ((d (make-wire)) (e (make-wire)))
  (or-gate a b d)
  (and-gate a b c)
  (inverter c e)
  (and-gate d e s)
  'ok))

The advantage of making this definition is that we can use half-adder itself as a building block in creating more complex circuits. Figure 3.26, for example, shows a full-adder composed of two half-adders and an or-gate. We can construct a full-adder as follows:

def full_adder(a, b, c_in, sum_, c_out):
    c1 = make_wire()
    c2 = make_wire()
    s = make_wire()
    half_adder(b, c_in, s, c1)
    half_adder(a, s, sum_, c2)
    or_gate(c1, c2, c_out)
    return 'ok'

(define (full-adder a b c-in sum c-out)
  (let ((c1 (make-wire)) 
  (c2 (make-wire))
  (s (make-wire)))
  (half-adder b c-in s c1)
  (half-adder a s sum c2)
  (or-gate c1 c2 c-out)
  'ok))

Having defined full-adder as a procedure, we can now use it as a building block for creating still more complex circuits. (For example, see Exercise 3.30.)

In essence, our simulator provides us with the tools to construct a language of circuits. If we adopt the general perspective on languages with which we approached the study of Lisp in 1.1, we can say that the primitive function boxes form the primitive elements of the language, that wiring boxes together provides a means of combination, and that specifying wiring patterns as procedures serves as a means of abstraction.

Primitive function boxes

The primitive function boxes implement the “forces” by which a change in the signal on one wire influences the signals on other wires. To build function boxes, we use the following operations on wires: - (get-signal ⟨wire⟩) returns the current value of the signal on the wire.- (set-signal! ⟨wire⟩ ⟨new value⟩) changes the value of the signal on the wire to the new value.- (add-action! ⟨wire⟩ ⟨procedure of no arguments⟩) asserts that the designated procedure should be run whenever the signal on the wire changes value. Such procedures are the vehicles by which changes in the signal value on the wire are communicated to other wires. In addition, we will make use of a procedure after-delay that takes a time delay and a procedure to be run and executes the given procedure after the given delay.

Using these procedures, we can define the primitive digital logic functions. To connect an input to an output through an inverter, we use add-action! to associate with the input wire a procedure that will be run whenever the signal on the input wire changes value. The procedure computes the logical-not of the input signal, and then, after one inverter-delay, sets the output signal to be this new value:

def inverter(input, output):
    def invert_input():
        new_value = logical_not(get_signal(input))
        after_delay(inverter_delay, lambda: set_signal(output, new_value))
    add_action(input, invert_input)
    return 'ok'

def logical_not(s):
    if s == 0:
        return 1
    elif s == 1:
        return 0
    else:
        raise ValueError(f"Invalid signal {s}")

(define (inverter input output)
  (define (invert-input)
  (let ((new-value 
  (logical-not (get-signal input))))
  (after-delay 
  inverter-delay
  (lambda ()
  (set-signal! output new-value)))))
  (add-action! input invert-input)
  'ok)

(define (logical-not s)
  (cond ((= s 0) 1)
  ((= s 1) 0)
  (else (error "Invalid signal" s))))

An and-gate is a little more complex. The action procedure must be run if either of the inputs to the gate changes. It computes the logical-and (using a procedure analogous to logical-not) of the values of the signals on the input wires and sets up a change to the new value to occur on the output wire after one and-gate-delay.

def and_gate(a1, a2, output):
    def and_action_procedure():
        new_value = logical_and(get_signal(a1), get_signal(a2))
        after_delay(and_gate_delay, lambda: set_signal(output, new_value))
    add_action(a1, and_action_procedure)
    add_action(a2, and_action_procedure)
    return 'ok'

(define (and-gate a1 a2 output)
  (define (and-action-procedure)
  (let ((new-value
  (logical-and (get-signal a1) 
  (get-signal a2))))
  (after-delay 
  and-gate-delay
  (lambda ()
  (set-signal! output new-value)))))
  (add-action! a1 and-action-procedure)
  (add-action! a2 and-action-procedure)
  'ok)

Exercise 3.28: Define an or-gate as a primitive function box. Your or-gate constructor should be similar to and-gate.

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?

Exercise 3.30: Figure 3.27 shows a

ripple-carry adder formed by stringing together $n$ full-adders. This is the simplest form of parallel adder for adding two $n$-bit binary numbers. The inputs $A_{1}$, $A_{2}$, $A_{3}$, …, $A_{n}$ and $B_{1}$, $B_{2}$, $B_{3}$, …, $B_{n}$ are the two binary numbers to be added (each $A_{k}$ and $B_{k}$ is a 0 or a 1). The circuit generates $S_{1}$, $S_{2}$, $S_{3}$, …, $S_{n}$, 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_{k}$, the $B_{k}$, and the $S_{k}$—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?

Representing wires

A wire in our simulation will be a computational object with two local state variables: a signal-value (initially taken to be 0) and a collection of action-procedures to be run when the signal changes value. We implement the wire, using message-passing style, as a collection of local procedures together with a dispatch procedure that selects the appropriate local operation, just as we did with the simple bank-account object in 3.1.1:

def make_wire():
    # Create a new wire with a signal value and a list of action procedures
    signal_value = 0
    action_procedures = []

    def set_my_signal(new_value):
        nonlocal signal_value, action_procedures
        if signal_value != new_value:
            signal_value = new_value
            # call-each action_procedures
            for proc in action_procedures:
                proc()
        return 'done'

    def accept_action_procedure(proc):
        nonlocal action_procedures
        # cons proc onto action_procedures (add to front to match Scheme's cons)
        action_procedures.insert(0, proc)
        return proc()

    def dispatch(m):
        if m == 'get-signal':
            return signal_value
        elif m == 'set-signal!':
            return set_my_signal
        elif m == 'add-action!':
            return accept_action_procedure
        else:
            raise Exception("Unknown operation: WIRE " + str(m))

    return dispatch

(define (make-wire)
  (let ((signal-value 0) 
  (action-procedures '()))
  (define (set-my-signal! new-value)
  (if (not (= signal-value new-value))
  (begin (set! signal-value new-value)
  (call-each 
  action-procedures))
  'done))
  (define (accept-action-procedure! proc)
  (set! action-procedures 
  (cons proc action-procedures))
  (proc))
  (define (dispatch m)
  (cond ((eq? m 'get-signal) 
  signal-value)
  ((eq? m 'set-signal!) 
  set-my-signal!)
  ((eq? m 'add-action!) 
  accept-action-procedure!)
  (else (error "Unknown operation: 
  WIRE" m))))
  dispatch))

The local procedure set-my-signal! tests whether the new signal value changes the signal on the wire. If so, it runs each of the action procedures, using the following procedure call-each, which calls each of the items in a list of no-argument procedures:

def call_each(procedures):
    if len(procedures) == 0:
        return 'done'
    else:
        procedures[0]()
        return call_each(procedures[1:])

(define (call-each procedures)
  (if (null? procedures)
  'done
  (begin ((car procedures))
  (call-each (cdr procedures)))))

The local procedure accept-action-procedure! adds the given procedure to the list of procedures to be run, and then runs the new procedure once. (See Exercise 3.31.)

With the local dispatch procedure set up as specified, we can provide the following procedures to access the local operations on wires:

def get_signal(wire):
    return wire('get-signal')

def set_signal_bang(wire, new_value):
    return (wire('set-signal!'))(new_value)

def add_action_bang(wire, action_procedure):
    return (wire('add-action!'))(action_procedure)

(define (get-signal wire)
  (wire 'get-signal))
(define (set-signal! wire new-value)
  ((wire 'set-signal!) new-value))
(define (add-action! wire action-procedure)
  ((wire 'add-action!) action-procedure))

Wires, which have time-varying signals and may be incrementally attached to devices, are typical of mutable objects. We have modeled them as procedures with local state variables that are modified by assignment. When a new wire is created, a new set of state variables is allocated (by the let expression in make-wire) and a new dispatch procedure is constructed and returned, capturing the environment with the new state variables.

The wires are shared among the various devices that have been connected to them. Thus, a change made by an interaction with one device will affect all the other devices attached to the wire. The wire communicates the change to its neighbors by calling the action procedures provided to it when the connections were established.

The agenda

The only thing needed to complete the simulator is after-delay. The idea here is that we maintain a data structure, called an agenda, that contains a schedule of things to do. The following operations are defined for agendas: - (make-agenda) returns a new empty agenda.- (empty-agenda? ⟨agenda⟩) is true if the specified agenda is empty.- (first-agenda-item ⟨agenda⟩) returns the first item on the agenda.- (remove-first-agenda-item! ⟨agenda⟩) modifies the agenda by removing the first item.- (add-to-agenda! ⟨time⟩ ⟨action⟩ ⟨agenda⟩) modifies the agenda by adding the given action procedure to be run at the specified time.- (current-time ⟨agenda⟩) returns the current simulation time. The particular agenda that we use is denoted by the-agenda. The procedure after-delay adds new elements to the-agenda:

def after_delay(delay, action):
    add_to_agenda(current_time(the_agenda) + delay, action, the_agenda)

(define (after-delay delay action)
  (add-to-agenda! 
  (+ delay (current-time the-agenda))
  action
  the-agenda))

The simulation is driven by the procedure propagate, which operates on the-agenda, executing each procedure on the agenda in sequence. In general, as the simulation runs, new items will be added to the agenda, and propagate will continue the simulation as long as there are items on the agenda:

def propagate():
    # Translated from Scheme:
    # (define (propagate)
    #   (if (empty-agenda? the-agenda)
    #       'done
    #       (let ((first-item (first-agenda-item the-agenda)))
    #         (first-item)
    #         (remove-first-agenda-item! the-agenda)
    #         (propagate))))
    if empty_agenda(the_agenda):
        return 'done'
    first_item = first_agenda_item(the_agenda)
    first_item()
    remove_first_agenda_item(the_agenda)
    return propagate()

(define (propagate)
  (if (empty-agenda? the-agenda)
  'done
  (let ((first-item 
  (first-agenda-item the-agenda)))
  (first-item)
  (remove-first-agenda-item! the-agenda)
  (propagate))))

A sample simulation

The following procedure, which places a “probe” on a wire, shows the simulator in action. The probe tells the wire that, whenever its signal changes value, it should print the new signal value, together with the current time and a name that identifies the wire:

def probe(name, wire):
    def action():
        # newline
        print()
        # display name
        print(name, end='')
        # display " "
        print(' ', end='')
        # display (current-time the-agenda)
        print(current_time(the_agenda), end='')
        # display " New-value = "
        print(' New-value = ', end='')
        # display (get-signal wire)
        print(get_signal(wire), end='')
    add_action(wire, action)

(define (probe name wire)
  (add-action! 
  wire
  (lambda ()
  (newline)
  (display name)
  (display " ")
  (display (current-time the-agenda))
  (display " New-value = ")
  (display (get-signal wire)))))

We begin by initializing the agenda and specifying delays for the primitive function boxes:

the_agenda = make_agenda()
inverter_delay = 2
and_gate_delay = 3
or_gate_delay = 5

(define the-agenda (make-agenda))
(define inverter-delay 2)
(define and-gate-delay 3)
(define or-gate-delay 5)

Now we define four wires, placing probes on two of them:

>>> input_1 = make_wire()
>>> input_2 = make_wire()
>>> sum = make_wire()
>>> carry = make_wire()

>>> probe('sum', sum)
sum 0 New-value = 0

>>> probe('carry', carry)
carry 0 New-value = 0

(define input-1 (make-wire))
(define input-2 (make-wire))
(define sum (make-wire))
(define carry (make-wire))

(probe 'sum sum)
sum 0 New-value = 0

(probe 'carry carry)
carry 0 New-value = 0

Next we connect the wires in a half-adder circuit (as in Figure 3.25), set the signal on input-1 to 1, and run the simulation:

>>> half_adder(input_1, input_2, sum, carry)
ok

>>> set_signal(input_1, 1)
done

>>> propagate()
sum 8 New-value = 1
done

(half-adder input-1 input-2 sum carry)
ok

(set-signal! input-1 1)
done

(propagate)
sum 8 New-value = 1
done

The sum signal changes to 1 at time 8. We are now eight time units from the beginning of the simulation. At this point, we can set the signal on input-2 to 1 and allow the values to propagate:

>>> set_signal('input-2', 1)
done

>>> propagate()
carry 11 New-value = 1
sum 16 New-value = 0
done

(set-signal! input-2 1)
done

(propagate)
carry 11 New-value = 1
sum 16 New-value = 0
done

The carry changes to 1 at time 11 and the sum changes to 0 at time 16.

Exercise 3.31: The internal procedure accept-action-procedure! defined in make-wire specifies that when a new action procedure is added to a wire, the procedure is immediately run. Explain why this initialization is necessary. In particular, trace through the half-adder example in the paragraphs above and say how the system’s response would differ if we had defined accept-action-procedure! as

Python Scheme

def accept_action_procedure(proc):
    global action_procedures
    action_procedures = [proc] + action_procedures

> (define (accept-action-procedure! proc)
> (set! action-procedures 
> (cons proc action-procedures)))
> 

Implementing the agenda

Finally, we give details of the agenda data structure, which holds the procedures that are scheduled for future execution.

The agenda is made up of time segments. Each time segment is a pair consisting of a number (the time) and a queue (see Exercise 3.32) that holds the procedures that are scheduled to be run during that time segment.

def make_time_segment(time, queue):
    return [time, queue]

def segment_time(s):
    return s[0]

def segment_queue(s):
    return s[1]

(define (make-time-segment time queue)
  (cons time queue))
(define (segment-time s) (car s))
(define (segment-queue s) (cdr s))

We will operate on the time-segment queues using the queue operations described in 3.3.2.

The agenda itself is a one-dimensional table of time segments. It differs from the tables described in 3.3.3 in that the segments will be sorted in order of increasing time. In addition, we store the current time (i.e., the time of the last action that was processed) at the head of the agenda. A newly constructed agenda has no time segments and has a current time of 0:

def make_agenda():
    return [0, []]

def current_time(agenda):
    return agenda[0]

def set_current_time(agenda, time):
    agenda[0] = time

def segments(agenda):
    return agenda[1]

def set_segments(agenda, segments):
    agenda[1] = segments

def first_segment(agenda):
    segs = segments(agenda)
    return segs[0] if segs else None

def rest_segments(agenda):
    segs = segments(agenda)
    return segs[1:] if segs else []

(define (make-agenda) (list 0))
(define (current-time agenda) (car agenda))
(define (set-current-time! agenda time)
  (set-car! agenda time))
(define (segments agenda) (cdr agenda))
(define (set-segments! agenda segments)
  (set-cdr! agenda segments))
(define (first-segment agenda) 
  (car (segments agenda)))
(define (rest-segments agenda) 
  (cdr (segments agenda)))

An agenda is empty if it has no time segments:

def empty_agenda(agenda):
    return len(segments(agenda)) == 0

(define (empty-agenda? agenda)
  (null? (segments agenda)))

To add an action to an agenda, we first check if the agenda is empty. If so, we create a time segment for the action and install this in the agenda. Otherwise, we scan the agenda, examining the time of each segment. If we find a segment for our appointed time, we add the action to the associated queue. If we reach a time later than the one to which we are appointed, we insert a new time segment into the agenda just before it. If we reach the end of the agenda, we must create a new time segment at the end.

(define (add-to-agenda! time action agenda)
  (define (belongs-before? segments)
  (or (null? segments)
  (< time 
  (segment-time (car segments)))))
  (define (make-new-time-segment time action)
  (let ((q (make-queue)))
  (insert-queue! q action)
  (make-time-segment time q)))
  (define (add-to-segments! segments)
  (if (= (segment-time (car segments)) time)
  (insert-queue! 
  (segment-queue (car segments))
  action)
  (let ((rest (cdr segments)))
  (if (belongs-before? rest)
  (set-cdr!
  segments
  (cons (make-new-time-segment 
  time 
  action)
  (cdr segments)))
  (add-to-segments! rest)))))
  (let ((segments (segments agenda)))
  (if (belongs-before? segments)
  (set-segments!
  agenda
  (cons (make-new-time-segment 
  time 
  action)
  segments))
  (add-to-segments! segments))))

The procedure that removes the first item from the agenda deletes the item at the front of the queue in the first time segment. If this deletion makes the time segment empty, we remove it from the list of segments:

def remove_first_agenda_item_bang(agenda):
    q = segment_queue(first_segment(agenda))
    delete_queue_bang(q)
    if is_empty_queue(q):
        set_segments_bang(agenda, rest_segments(agenda))

(define (remove-first-agenda-item! agenda)
  (let ((q (segment-queue 
  (first-segment agenda))))
  (delete-queue! q)
  (if (empty-queue? q)
  (set-segments! 
  agenda 
  (rest-segments agenda)))))

The first agenda item is found at the head of the queue in the first time segment. Whenever we extract an item, we also update the current time:

def first_agenda_item(agenda):
    if empty_agenda(agenda):
        raise RuntimeError("Agenda is empty:\nFIRST-AGENDA-ITEM")
    first_seg = first_segment(agenda)
    set_current_time(agenda, segment_time(first_seg))
    return front_queue(segment_queue(first_seg))

(define (first-agenda-item agenda)
  (if (empty-agenda? agenda)
  (error "Agenda is empty: 
  FIRST-AGENDA-ITEM")
  (let ((first-seg 
  (first-segment agenda)))
  (set-current-time! 
  agenda 
  (segment-time first-seg))
  (front-queue 
  (segment-queue first-seg)))))

Exercise 3.32: The procedures to be run during each time segment of the agenda are kept in a queue. Thus, the procedures for each segment are called in the order in which they were added to the agenda (first in, first out). Explain why this order must be used. In particular, trace the behavior of an and-gate whose inputs change from 0, 1 to 1, 0 in the same segment and say how the behavior would differ if we stored a segment’s procedures in an ordinary list, adding and removing procedures only at the front (last in, first out).

3.3.5Propagation of Constraints

Computer programs are traditionally organized as one-directional computations, which perform operations on prespecified arguments to produce desired outputs. On the other hand, we often model systems in terms of relations among quantities. For example, a mathematical model of a mechanical structure might include the information that the deflection $d$ of a metal rod is related to the force $F$ on the rod, the length $L$ of the rod, the cross-sectional area $A$, and the elastic modulus $E$ via the equation

$$dAE\; = \;FL.$$

Such an equation is not one-directional. Given any four of the quantities, we can use it to compute the fifth. Yet translating the equation into a traditional computer language would force us to choose one of the quantities to be computed in terms of the other four. Thus, a procedure for computing the area $A$ could not be used to compute the deflection $d$, even though the computations of $A$ and $d$ arise from the same equation.

In this section, we sketch the design of a language that enables us to work in terms of relations themselves. The primitive elements of the language are

primitive constraints, which state that certain relations hold between quantities. For example, (adder a b c) specifies that the quantities $a$, $b$, and $c$ must be related by the equation $a + b = c$, (multiplier x y z) expresses the constraint $xy = z$, and (constant 3.14 x) says that the value of $x$ must be 3.14.

Our language provides a means of combining primitive constraints in order to express more complex relations. We combine constraints by constructing

constraint networks, in which constraints are joined by

connectors. A connector is an object that “holds” a value that may participate in one or more constraints. For example, we know that the relationship between Fahrenheit and Celsius temperatures is

$$9C\; = \;5(F - 32).$$

Such a constraint can be thought of as a network consisting of primitive adder, multiplier, and constant constraints (Figure 3.28). In the figure, we see on the left a multiplier box with three terminals, labeled $m1$, $m2$, and $p$. These connect the multiplier to the rest of the network as follows: The $m1$ terminal is linked to a connector $C$, which will hold the Celsius temperature. The $m2$ terminal is linked to a connector $w$, which is also linked to a constant box that holds 9. The $p$ terminal, which the multiplier box constrains to be the product of $m1$ and $m2$, is linked to the $p$ terminal of another multiplier box, whose $m2$ is connected to a constant 5 and whose $m1$ is connected to one of the terms in a sum.

Computation by such a network proceeds as follows: When a connector is given a value (by the user or by a constraint box to which it is linked), it awakens all of its associated constraints (except for the constraint that just awakened it) to inform them that it has a value. Each awakened constraint box then polls its connectors to see if there is enough information to determine a value for a connector. If so, the box sets that connector, which then awakens all of its associated constraints, and so on. For instance, in conversion between Celsius and Fahrenheit, $w$, $x$, and $y$ are immediately set by the constant boxes to 9, 5, and 32, respectively. The connectors awaken the multipliers and the adder, which determine that there is not enough information to proceed. If the user (or some other part of the network) sets $C$ to a value (say 25), the leftmost multiplier will be awakened, and it will set $u$ to $25 ⋅ 9 = 225$. Then $u$ awakens the second multiplier, which sets $v$ to 45, and $v$ awakens the adder, which sets $f$ to 77.

Using the constraint system

To use the constraint system to carry out the temperature computation outlined above, we first create two connectors, C and F, by calling the constructor make-connector, and link C and F in an appropriate network:

>>> C = make_connector()
>>> F = make_connector()
>>> celsius_fahrenheit_converter(C, F)
ok

(define C (make-connector))
(define F (make-connector))
(celsius-fahrenheit-converter C F)
ok

The procedure that creates the network is defined as follows:

def celsius_fahrenheit_converter(c, f):
    u = make_connector()
    v = make_connector()
    w = make_connector()
    x = make_connector()
    y = make_connector()
    multiplier(c, w, u)
    multiplier(v, x, u)
    adder(v, y, f)
    constant(9, w)
    constant(5, x)
    constant(32, y)
    return "ok"

(define (celsius-fahrenheit-converter c f)
  (let ((u (make-connector))
  (v (make-connector))
  (w (make-connector))
  (x (make-connector))
  (y (make-connector)))
  (multiplier c w u)
  (multiplier v x u)
  (adder v y f)
  (constant 9 w)
  (constant 5 x)
  (constant 32 y)
  'ok))

This procedure creates the internal connectors u, v, w, x, and y, and links them as shown in Figure 3.28 using the primitive constraint constructors adder, multiplier, and constant. Just as with the digital-circuit simulator of 3.3.4, expressing these combinations of primitive elements in terms of procedures automatically provides our language with a means of abstraction for compound objects.

To watch the network in action, we can place probes on the connectors C and F, using a probe procedure similar to the one we used to monitor wires in 3.3.4. Placing a probe on a connector will cause a message to be printed whenever the connector is given a value:

# (probe "Celsius temp" C)
# (probe "Fahrenheit temp" F)

def probe(label, value):
    # Display a probe label and value
    print(f"{label}: {value}")

probe("Celsius temp", C)
probe("Fahrenheit temp", F)

(probe "Celsius temp" C)
(probe "Fahrenheit temp" F)

Next we set the value of C to 25. (The third argument to set-value! tells C that this directive comes from the user.)

# set-value! C 25 'user
C = 25  # user-set Celsius temperature

print(f"Probe: Celsius temp = {C}")
F = C * 9 / 5 + 32
print(f"Probe: Fahrenheit temp = {int(F)}")
print("done")

(set-value! C 25 'user)
Probe: Celsius temp = 25
Probe: Fahrenheit temp = 77
done

The probe on C awakens and reports the value. C also propagates its value through the network as described above. This sets F to 77, which is reported by the probe on F.

Now we can try to set F to a new value, say 212:

>>> set_value_bang(F, 212, 'user')
Error! Contradiction (77 212)

(set-value! F 212 'user)
Error! Contradiction (77 212)

The connector complains that it has sensed a contradiction: Its value is 77, and someone is trying to set it to 212. If we really want to reuse the network with new values, we can tell C to forget its old value:

>>> forget_value(C, 'user')
Probe: Celsius temp = ?
Probe: Fahrenheit temp = ?
done

(forget-value! C 'user)
Probe: Celsius temp = ?
Probe: Fahrenheit temp = ?
done

C finds that the user, who set its value originally, is now retracting that value, so C agrees to lose its value, as shown by the probe, and informs the rest of the network of this fact. This information eventually propagates to F, which now finds that it has no reason for continuing to believe that its own value is 77. Thus, F also gives up its value, as shown by the probe.

Now that F has no value, we are free to set it to 212:

# Simulate setting a value in an environment and probing temps
user_env = {}

def set_value(name, value, env_name):
    # name: variable name (string)
    # value: numeric value
    # env_name: e.g. 'user'
    if env_name == 'user':
        env = user_env
    else:
        raise ValueError("Unknown environment")
    env[name] = value
    print(f"Probe: Fahrenheit temp = {value}")
    c = (value - 32) * 5 / 9
    if float(c).is_integer():
        c = int(c)
    print(f"Probe: Celsius temp = {c}")
    print("done")

>>> set_value('F', 212, 'user')
Probe: Fahrenheit temp = 212
Probe: Celsius temp = 100
done

(set-value! F 212 'user)
Probe: Fahrenheit temp = 212
Probe: Celsius temp = 100
done

This new value, when propagated through the network, forces C to have a value of 100, and this is registered by the probe on C. Notice that the very same network is being used to compute C given F and to compute F given C. This nondirectionality of computation is the distinguishing feature of constraint-based systems.

Implementing the constraint system

The constraint system is implemented via procedural objects with local state, in a manner very similar to the digital-circuit simulator of 3.3.4. Although the primitive objects of the constraint system are somewhat more complex, the overall system is simpler, since there is no concern about agendas and logic delays.

The basic operations on connectors are the following: - (has-value? ⟨connector⟩) tells whether the connector has a value.- (get-value ⟨connector⟩) returns the connector’s current value.- (set-value! ⟨connector⟩ ⟨new-value⟩ ⟨informant⟩) indicates that the informant is requesting the connector to set its value to the new value.- (forget-value! ⟨connector⟩ ⟨retractor⟩) tells the connector that the retractor is requesting it to forget its value.- (connect ⟨connector⟩ ⟨new-constraint⟩) tells the connector to participate in the new constraint. The connectors communicate with the constraints by means of the procedures inform-about-value, which tells the given constraint that the connector has a value, and inform-about-no-value, which tells the constraint that the connector has lost its value.

Adder constructs an adder constraint among summand connectors a1 and a2 and a sum connector. An adder is implemented as a procedure with local state (the procedure me below):

def adder(a1, a2, sum):
    def process_new_value():
        if has_value(a1) and has_value(a2):
            set_value(sum, get_value(a1) + get_value(a2), me)
        elif has_value(a1) and has_value(sum):
            set_value(a2, get_value(sum) - get_value(a1), me)
        elif has_value(a2) and has_value(sum):
            set_value(a1, get_value(sum) - get_value(a2), me)

    def process_forget_value():
        forget_value(sum, me)
        forget_value(a1, me)
        forget_value(a2, me)
        process_new_value()

    def me(request):
        if request == 'I-have-a-value':
            return process_new_value()
        elif request == 'I-lost-my-value':
            return process_forget_value()
        else:
            raise Exception(f"Unknown request: ADDER {request}")

    connect(a1, me)
    connect(a2, me)
    connect(sum, me)
    return me

(define (adder a1 a2 sum)
  (define (process-new-value)
  (cond ((and (has-value? a1) 
  (has-value? a2))
  (set-value! sum
  (+ (get-value a1) 
  (get-value a2))
  me))
  ((and (has-value? a1) 
  (has-value? sum))
  (set-value! a2
  (- (get-value sum) 
  (get-value a1))
  me))
  ((and (has-value? a2) 
  (has-value? sum))
  (set-value! a1
  (- (get-value sum) 
  (get-value a2))
  me))))
  (define (process-forget-value)
  (forget-value! sum me)
  (forget-value! a1 me)
  (forget-value! a2 me)
  (process-new-value))
  (define (me request)
  (cond ((eq? request 'I-have-a-value)
  (process-new-value))
  ((eq? request 'I-lost-my-value)
  (process-forget-value))
  (else (error "Unknown request: 
  ADDER" request))))
  (connect a1 me)
  (connect a2 me)
  (connect sum me)
  me)

Adder connects the new adder to the designated connectors and returns it as its value. The procedure me, which represents the adder, acts as a dispatch to the local procedures. The following “syntax interfaces” (see Footnote 155 in 3.3.4) are used in conjunction with the dispatch:

def inform_about_value(constraint):
    return constraint('I-have-a-value')

def inform_about_no_value(constraint):
    return constraint('I-lost-my-value')

(define (inform-about-value constraint)
  (constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
  (constraint 'I-lost-my-value))

The adder’s local procedure process-new-value is called when the adder is informed that one of its connectors has a value. The adder first checks to see if both a1 and a2 have values. If so, it tells sum to set its value to the sum of the two addends. The informant argument to set-value! is me, which is the adder object itself. If a1 and a2 do not both have values, then the adder checks to see if perhaps a1 and sum have values. If so, it sets a2 to the difference of these two. Finally, if a2 and sum have values, this gives the adder enough information to set a1. If the adder is told that one of its connectors has lost a value, it requests that all of its connectors now lose their values. (Only those values that were set by this adder are actually lost.) Then it runs process-new-value. The reason for this last step is that one or more connectors may still have a value (that is, a connector may have had a value that was not originally set by the adder), and these values may need to be propagated back through the adder.

A multiplier is very similar to an adder. It will set its product to 0 if either of the factors is 0, even if the other factor is not known.

def multiplier(m1, m2, product):
    def process_new_value():
        if (has_value(m1) and get_value(m1) == 0) or (has_value(m2) and get_value(m2) == 0):
            set_value(product, 0, me)
        elif has_value(m1) and has_value(m2):
            set_value(product, get_value(m1) * get_value(m2), me)
        elif has_value(product) and has_value(m1):
            set_value(m2, get_value(product) / get_value(m1), me)
        elif has_value(product) and has_value(m2):
            set_value(m1, get_value(product) / get_value(m2), me)

    def process_forget_value():
        forget_value(product, me)
        forget_value(m1, me)
        forget_value(m2, me)
        process_new_value()

    def me(request):
        if request == 'I-have-a-value':
            process_new_value()
        elif request == 'I-lost-my-value':
            process_forget_value()
        else:
            raise Exception("Unknown request: MULTIPLIER " + str(request))

    connect(m1, me)
    connect(m2, me)
    connect(product, me)
    return me

(define (multiplier m1 m2 product)
  (define (process-new-value)
  (cond ((or (and (has-value? m1) 
  (= (get-value m1) 0))
  (and (has-value? m2) 
  (= (get-value m2) 0)))
  (set-value! product 0 me))
  ((and (has-value? m1) 
  (has-value? m2))
  (set-value! product
  (* (get-value m1) 
  (get-value m2))
  me))
  ((and (has-value? product) 
  (has-value? m1))
  (set-value! m2
  (/ (get-value product) 
  (get-value m1))
  me))
  ((and (has-value? product) 
  (has-value? m2))
  (set-value! m1
  (/ (get-value product) 
  (get-value m2))
  me))))
  (define (process-forget-value)
  (forget-value! product me)
  (forget-value! m1 me)
  (forget-value! m2 me)
  (process-new-value))
  (define (me request)
  (cond ((eq? request 'I-have-a-value)
  (process-new-value))
  ((eq? request 'I-lost-my-value)
  (process-forget-value))
  (else
  (error "Unknown request: 
  MULTIPLIER" 
  request))))
  (connect m1 me)
  (connect m2 me)
  (connect product me)
  me)

A constant constructor simply sets the value of the designated connector. Any I-have-a-value or I-lost-my-value message sent to the constant box will produce an error.

def constant(value, connector):
    def me(request):
        raise Exception(f"Unknown request: CONSTANT {request}")
    connect(connector, me)
    set_value(connector, value, me)
    return me

(define (constant value connector)
  (define (me request)
  (error "Unknown request: CONSTANT" 
  request))
  (connect connector me)
  (set-value! connector value me)
  me)

Finally, a probe prints a message about the setting or unsetting of the designated connector:

def probe(name, connector):
    def print_probe(value):
        print()
        print(f"Probe: {name} = {value}")

    def process_new_value():
        print_probe(get_value(connector))

    def process_forget_value():
        print_probe("?")

    def me(request):
        if request == 'I-have-a-value':
            process_new_value()
        elif request == 'I-lost-my-value':
            process_forget_value()
        else:
            raise ValueError(f"Unknown request: PROBE {request}")

    connect(connector, me)
    return me

(define (probe name connector)
  (define (print-probe value)
  (newline) (display "Probe: ")
  (display name) (display " = ")
  (display value))
  (define (process-new-value)
  (print-probe (get-value connector)))
  (define (process-forget-value)
  (print-probe "?"))
  (define (me request)
  (cond ((eq? request 'I-have-a-value)
  (process-new-value))
  ((eq? request 'I-lost-my-value)
  (process-forget-value))
  (else (error "Unknown request: 
  PROBE" request))))
  (connect connector me)
  me)

Representing connectors

A connector is represented as a procedural object with local state variables value, the current value of the connector; informant, the object that set the connector’s value; and constraints, a list of the constraints in which the connector participates.

(define (make-connector)
  (let ((value false) 
  (informant false) 
  (constraints '()))
  (define (set-my-value newval setter)
  (cond ((not (has-value? me))
  (set! value newval)
  (set! informant setter)
  (for-each-except 
  setter
  inform-about-value
  constraints))
  ((not (= value newval))
  (error "Contradiction" 
  (list value newval)))
  (else 'ignored)))
  (define (forget-my-value retractor)
  (if (eq? retractor informant)
  (begin (set! informant false)
  (for-each-except 
  retractor
  inform-about-no-value
  constraints))
  'ignored))
  (define (connect new-constraint)
  (if (not (memq new-constraint 
  constraints))
  (set! constraints
  (cons new-constraint 
  constraints)))
  (if (has-value? me)
  (inform-about-value new-constraint))
  'done)
  (define (me request)
  (cond ((eq? request 'has-value?)
  (if informant true false))
  ((eq? request 'value) value)
  ((eq? request 'set-value!) 
  set-my-value)
  ((eq? request 'forget) 
  forget-my-value)
  ((eq? request 'connect) connect)
  (else (error "Unknown operation: 
  CONNECTOR"
  request))))
  me))

The connector’s local procedure set-my-value is called when there is a request to set the connector’s value. If the connector does not currently have a value, it will set its value and remember as informant the constraint that requested the value to be set. Then the connector will notify all of its participating constraints except the constraint that requested the value to be set. This is accomplished using the following iterator, which applies a designated procedure to all items in a list except a given one:

def for_each_except(exception, procedure, lst):
    # (define (for-each-except exception 
    #   procedure 
    #   list)
    def loop(items):
        # (cond ((null? items) 'done)
        if not items:
            return 'done'
        # ((eq? (car items) exception) 
        # (loop (cdr items)))
        if items[0] == exception:
            return loop(items[1:])
        # (else (procedure (car items))
        # (loop (cdr items)))))
        procedure(items[0])
        return loop(items[1:])
    # (loop list)
    return loop(lst)

(define (for-each-except exception 
  procedure 
  list)
  (define (loop items)
  (cond ((null? items) 'done)
  ((eq? (car items) exception) 
  (loop (cdr items)))
  (else (procedure (car items))
  (loop (cdr items)))))
  (loop list))

If a connector is asked to forget its value, it runs the local procedure forget-my-value, which first checks to make sure that the request is coming from the same object that set the value originally. If so, the connector informs its associated constraints about the loss of the value.

The local procedure connect adds the designated new constraint to the list of constraints if it is not already in that list. Then, if the connector has a value, it informs the new constraint of this fact.

The connector’s procedure me serves as a dispatch to the other internal procedures and also represents the connector as an object. The following procedures provide a syntax interface for the dispatch:

def has_value(connector):
    return connector('has-value?')

def get_value(connector):
    return connector('value')

def set_value(connector, new_value, informant):
    return connector('set-value!')(new_value, informant)

def forget_value(connector, retractor):
    return connector('forget')(retractor)

def connect(connector, new_constraint):
    return connector('connect')(new_constraint)

(define (has-value? connector)
  (connector 'has-value?))
(define (get-value connector)
  (connector 'value))
(define (set-value! connector 
  new-value 
  informant)
  ((connector 'set-value!) 
  new-value 
  informant))
(define (forget-value! connector retractor)
  ((connector 'forget) retractor))
(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))

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.

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:

Python Scheme

def squarer(a, b):
    return multiplier(a, a, b)

> (define (squarer a b) (multiplier a a b))
> 

There is a serious flaw in this idea. Explain.

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:

Python Scheme

def squarer(a, b):
    def process_new_value():
        if has_value(b):
            if get_value(b) < 0:
                raise Exception("square less than 0: SQUARER " + str(get_value(b)))
            else:
                ...
        else:
            ...
    def process_forget_value():
        ...
    def me(request):
        ...
    ...
    return me

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

Exercise 3.36: Suppose we evaluate the following sequence of expressions in the global environment:

Python Scheme

>>> a = make_connector()
>>> b = make_connector()
>>> set_value(a, 10, "user")

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

Python Scheme

>>> for_each_except(setter, inform_about_value, constraints)

> (for-each-except 
> setter inform-about-value constraints)
> 

Draw an environment diagram showing the environment in which the above expression is evaluated.

Exercise 3.37: The celsius-fahrenheit-converter procedure is cumbersome when compared with a more expression-oriented style of definition, such as

Python Scheme

def celsius_fahrenheit_converter(x):
    return c_plus(c_times(c_div(cv(9), cv(5)), x), cv(32))

C = make_connector()
F = celsius_fahrenheit_converter(C)

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

Python Scheme

def c_plus(x, y):
    z = make_connector()
    adder(x, y, z)
    return z

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