Introducing Assignment

None of the Scheme constructs discussed so far modifies an existing value. For example, using define twice for the same identifier produces an error:

(define x 1)
(define x 2)

; module: identifier already defined

In some situations, however, we really do need to change an existing value. Scheme provides set! for this, allowing us to implement a bank account:

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

A more reasonable design would make balance local to withdraw. We can use let to construct a local variable:

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

Similarly, a function’s formal parameter can serve as a local variable:

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

We can then obtain two withdrawal accounts with independent local variables:

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

The benefit of assignment is obvious: we can implement scenarios that were previously out of reach.

Another typical example is implementing rand. In Scheme, rand-update transforms a random seed to generate a random number. With assignment, we can keep the seed as a local state variable, so callers do not have to supply it every time:

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

Note that rand-update is actually an ordinary, deterministic function that converts one number into another. A common approach, mentioned in a note in the book, is to update \(x\) to $(ax+b)\mod m$:

(define (rand-update x)
  (remainder (+ (* a x) c) m))

We can now call rand directly to obtain a random number. Otherwise, explicitly managing the seed outside the generator would obscure the structure of the calling code. Besides implementing its own algorithm, that code would also have to update the seed, inviting mistakes such as reusing the same one. The book illustrates this with a Monte Carlo simulation that is forced to add a parameter for the seed used at each iteration.

In general, set! is needed to let a procedure update its own local state variables while hiding its changing internal state from the outside. This makes the system more modular.

Without assignment, our procedures resemble mathematical functions: a fixed input always produces a fixed output. Programming without assignment is called functional programming; programming with it is called imperative programming.

Perhaps the most conspicuous difference in everyday style is how the two implement iteration. The latter resembles the while loops we commonly write in C:

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

; imperative programming
(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)))

The Cost of Assignment

Imperative programming brings greater flexibility, but at a substantial cost.

We can no longer explain computation using the substitution model. That model requires symbols to be names for values. With assignment, values can change, so a variable is no longer merely a name: it refers to a location holding a value. Using a symbol therefore requires a time dimension to distinguish whether evaluation occurs before or after a set!. The substitution model cannot do this. We can describe this as breaking referential transparency: the property that an expression can be replaced without changing its value.

Without referential transparency, it becomes difficult to decide whether two objects are the “same.” Even symbols created using exactly the same expression may refer to entirely different objects. Here, for example, the mutable local variable balance means that W1 and W2 may well not be the same:

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

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

By contrast, D1 and D2 here must be the same:

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

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

Mutable Data Objects

Assignment also lets us construct more flexible data objects.

For a simple example, consider the structure of a typical list:

(define x (cons 1 (cons 2 (cons 3 (cons 4 nil)))))

It consists of pairs whose car points to a value and whose cdr points to the next pair. Applying set-car! or set-cdr! to a pair changes those references: the car can become another value, the cdr can point to another pair, or the car can itself point to a pair, turning x into a two-dimensional list.

Assignment also permits more complex sharing. For example, set-cdr! can make the cdr of x point into the middle of another list:

(define y (list a b c d))
(set-cdr! x b)

Now x and y share the (b c d) portion of the list, a situation that did not arise in the functional-programming approach discussed here.

The book also demonstrates queues, tables, and other data structures implemented through assignment, all using similar techniques. The same methods can simulate circuits, where input signals need to change, and construct a constraint system.

Concurrency and Implementing a Mutex

Once assignment exists, the whole system acquires a time dimension. Evaluating a symbol requires knowing when that evaluation occurs, because time can change the result.

In a single-threaded program this is not too serious: the order of operations is clear. Concurrency is quite different. Operations can occur in unpredictable orders, and different threads may share the same local values, creating considerable trouble.

A simple example is the withdrawal procedure we implemented earlier:

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

The key step, (set! balance (- balance amount)), can be broken down into three smaller steps:

  1. Read balance.
  2. Calculate the difference between balance and amount.
  3. Assign the calculated difference to balance.

The first step reads balance; the third writes it. If two concurrent threads, A and B, execute in the order A1–B1–A3–B3, B overwrites A’s write. B read the balance before A wrote it, so its result takes no account of A’s operation.

A natural solution is to use a serializer to constrain procedures, allowing only one of the procedures protected by it to run at a time.

We can define a revised account system intended to restrict withdrawals, deposits, and direct balance queries:

(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)
  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw)
	     (protected withdraw))
	    ((eq? m 'deposit)
	     (protected deposit))
	    ((eq? m 'balance)
	     balance)
	    (else (error "Unknown request:
			  MAKE-ACCOUNT"
			 m))))
    dispatch))

A serializer can be implemented using an object called a mutex:

(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
	(mutex 'acquire)
	(let ((val (apply p args)))
	  (mutex 'release)
	  val))
      serialized-p)))

The mutex itself uses a list with a single element, which we call a cell. That element holds a Boolean value. We can construct the mutex as follows:

(define (make-mutex)
  (let ((cell (list false)))
    (define (the-mutex m)
      (cond ((eq? m 'acquire)
	     (if (test-and-set! cell)
		 (the-mutex 'acquire))) ; retry
	    ((eq? m 'release) (clear! cell))))
    the-mutex))
(define (clear! cell) (set-car! cell false))

Here, test-and-set! checks the cell. If it is false, the procedure immediately changes it to true and returns false, allowing the-mutex to finish acquiring the mutex:

(define (test-and-set! cell)
  (if (car cell)
      true
      (begin (set-car! cell true)
	     false)))

This alone does not guarantee a working mutex. We must be certain that test-and-set! executes atomically: once it finds the cell false, it must be able to set it to true without interference. Otherwise, the implementation has the same problem as the withdrawal example.

That guarantee depends on the operating system, not something that can be solved at the programming-language level alone. For a simple example, many operating systems schedule processes using time slices. Interrupts could be blocked while an atomic operation runs, ensuring that it executes from beginning to end. Multicore CPUs should support atomic instructions at the hardware level.

Another interesting issue is the arbiter. If two processes use a hardware-level atomic instruction simultaneously, an arbiter must decide which obtains control of the resource. Unfortunately, we can prove that an arbiter effective 100% of the time cannot be constructed. The problem was first posed by the fourteenth-century French philosopher Jean Buridan as Buridan’s ass: a donkey starves because it cannot decide which of two haystacks to eat. In other words, when neither choice has a clear reason to be preferred, a perfectly rational decision-maker has great difficulty choosing.

Streams

Assignment produces many side effects. We need it because objects in the real world really do change state. But variables are not the only way to describe those changes.

We could instead view a state as a time-dependent function, \(f(t)\). Once time is supplied as an argument, the value is fixed. The history of that function can be imagined as a very long list, with each element giving the value at one moment.

Treating it as a list, however, presents two main problems:

  1. The values across time should be unbounded, but an infinitely long list cannot actually be constructed.
  2. Even a finite list can require considerable computation and storage to construct and retain.

An extreme example illustrates the problem. Suppose we find the second prime between 10000 and 1000000 this way:

(car (cdr
      (filter
       prime?
       (enumerate-interval 10000 1000000))))

We enumerate every integer from 10000 to 1000000, test each for primality, then discard almost all the results and keep just one. This is clearly an unreasonable way to write the program, but it exposes a problem with representing the sequence as a list.

Here we introduce a new data structure: the stream. A stream is used much like a list, but its elements are not all generated at construction time. They are computed only when needed. We can think of a stream as a delayed list.

Like a list, a stream begins with a pair, but its structure is:

(cons ⟨a⟩ (delay ⟨b⟩))

The car is an ordinary expression, while the cdr is a delayed expression, called a promise.

Naturally, obtaining the stream’s cdr requires forcing that promise into an actual value:

(define (stream-cdr stream)
  (force (cdr stream)))

Here is the earlier extreme example implemented with streams:

(stream-car
 (stream-cdr
  (stream-filter
   prime? (stream-enumerate-interval
	   10000 1000000))))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1)
				  high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream)
	 the-empty-stream)
	((pred (stream-car stream))
	 (cons-stream
	  (stream-car stream)
	  (stream-filter
	   pred
	   (stream-cdr stream))))
	(else (stream-filter
	       pred
	       (stream-cdr stream)))))

Initially, stream-filter finds that 10000 is not prime and executes (stream-filter pred (stream-cdr stream)). stream-cdr forces a promise, making stream-enumerate-interval return:

(cons 10001
      (delay
	(stream-enumerate-interval
	 10002
	 1000000)))

stream-filter then uses stream-car to obtain 10001 and repeats the process. Eventually it reaches 10007, discovers that it is prime, and constructs a pair with it. The overall result at that point is:

(cons 10007
      (delay
	(stream-filter
	 prime?
	 (cons 10008
	       (delay
		 (stream-enumerate-interval
		  10009 1000000))))))

Finding 10009 works in the same way, and the whole expression then returns 10009. The number of operations performed differs from the list-based version by orders of magnitude.

The implementations of delay and force are conceptually straightforward. To delay an expression, wrap it in a procedure and return that procedure. To force it, simply call the procedure:

(define (delay exp)
  (lambda () exp))

(define (force delayed-object)
  (delayed-object))

We can see, however, that delay must be a special form, not an ordinary procedure. The definition above is therefore only illustrative, not an actual implementation: under applicative-order evaluation, an ordinary procedure’s arguments would already have been evaluated.

To make streams more efficient, a memo-proc can save values already computed. When an element depends on earlier ones, this can greatly reduce the number of required steps:

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
	  (begin (set! result (proc))
		 (set! already-run? true)
		 result)
	  result))))

(define (delay exp)
  (memo-proc (lambda () exp)))

One important feature of streams is that they can be infinite. We can define a stream of integers like this:

(define (integers-starting-from n)
  (cons-stream
   n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))

This is a fairly direct definition, using integers-starting-from to generate successive values recursively. We can also use a less explicit definition:

(define ones (cons-stream 1 ones))
(define (add-streams s1 s2)
  (stream-map + s1 s2))
(define integers
  (cons-stream 1 (add-streams ones integers)))

We can now revisit rand. From a stream perspective, there is no random-number generator, but there can be an infinite stream of random numbers:

(define random-numbers
  (cons-stream random-init
	       (stream-map rand-update
			   random-numbers)))

This stream can still be neatly abstracted, leaving the logical structure of higher-level algorithms unaffected.

Time from a Functional-Programming Perspective

Real-world objects have states, and those states change over time. We introduced assignment into the language precisely to model that situation. But assignment carries so many costs that we have tried to find another route.

Streams let us represent the history of a variable’s changes explicitly, loosening the tight connection between time in the modeled world and the process of computation.

We can compare the approaches again using withdrawals. This is the assignment-based version:

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

And this is the stream-based version, which produces a stream representing the history of the balance:

(define (stream-withdraw balance amount-stream)
  (cons-stream
   balance
   (stream-withdraw
    (- balance (stream-car amount-stream))
    (stream-cdr amount-stream))))

stream-withdraw performs the required task while remaining a well-defined function in the mathematical sense: its return value depends only on its arguments.

For the stream itself, there is no notion of time and no state. Yet to its user, it appears to be a system with which they interact, acquiring a state through that interaction. This difference in perception arises because the user exists in time. Just as arguments are supplied to a function, the user supplies temporal information to the system, thereby perceiving a stateless stream as stateful.