Modeling with Mutable Data

• We previously looked at compound data and data abstraction.
• To model stateful objects, we need mutators in addition to constructors and selectors.
• A mutator is a procedure that modifies the data object.

Mutable List Structure

• The primitive mutators for pairs are set-car! and set-cdr!.
• (set-car! p x) changes the car of the pair p, making it point to x instead.
• The old car is unreachable garbage. We will see later how Lisp recycles this memory.
• We could implement cons in terms of these two procedures in addition to a get-new-part procedure.

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

Exercises: 3.12 3.13 3.14

Sharing and identity

• Consider (define x (list 'a 'b)) and (define z1 (cons x x)).
• z1 is a pair whose car and cdr both point to the same x.
• In contrast: (define z2 (cons (list 'a 'b)) (list 'a 'b)).
• In z2, the two (a b) lists are distinct, although the actual symbols are shared.
• Before assignment, we would think z1 and z2 were “the same.”
• The sharing is undetectable without mutators on list structure.
• It is detectable in our environmental model.
• If we set-car! on the car, this will change both a symbols in z1 but only the first in z2.
• We can use the predicate eq? to test for sameness in the sense of identity.
• (eq? x y) tests whether x and y point to the same object.
• We can exploit sharing for good, but it can be dangerous.

Exercises: 3.15 3.16 3.17 3.18 3.19

Mutation is just assignment

• Earlier we said we can represent pairs purely in terms of procedures:

(define (cons x y)
  (lambda (sel)
    (sel x y)))
(define (car p)
  (p (lambda (x y) x)))
(define (cdr p)
  (p (lambda (x y) y)))

• The same is true of mutable data. We can implement mutators with procedures and assignment alone:

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

• Assignment and mutation are equipotent: each can be implemented in terms of the other.

Exercises: 3.20

Representing Queues

• The mutators allow us to construct new data structures.
• A queue is a sequence in which items are inserted at one end (the rear) and deleted from the other end (the front).
• It is also called a FIFO buffer (first in, first out).
• We define the following operations for data abstraction:
  • a constructor (make-queue),
  • a predicate (empty-queue? q),
  • a selector (front-queue q),
  • two mutators: (insert-queue! q x) and (delete-queue! q).
• A simple list representation is inefficient because we have to scan to get to one end.
• Scanning a list takes $\Theta(n)$ operations.
• A simply modification lets us implement all the operations with $\Theta(1)$ time complexity: keep a pointer to the end as well.
• A queue is a pair formed by consing the front-pointer and the rear-pointer of a normal list.

Exercises: 3.21 3.22 3.23

Representing Tables

• In a one-dimensional table, each value is indexed by one key.
• We can implement it as a simple list of records.
• A record is a pair consisting of a key and an associated value.
• The first record in the table is a dummy, and it hold the arbitrarily chosen symbol '*table*.
  • If a table was just a pointer to the first actual record, then when we wouldn’t be able to write a mutator to add a record to the front.
  • We would need to change the table to point to the new front, but set! on a formal parameter doesn’t work as desired.
  • It would only change the parameter in $E_1$, not the value in the calling environment.
  • We didn’t need to worry about this with sets because a set was a pair of two pointers a therefore we could mutate the car and cdr—but we couldn’t change the set itself, since it was effectively a pointer to the pair, copied on application.
  • We are essentially using a pointer; we are using one cell of the pair. Some schemes provide box, unbox, and set-box! for this purpose.
• The lookup procedure returns the value associated with a key in a table, or false if it cannot be found.
• It uses assoc, which returns the whole record rather than just the associated value.

Two-dimensional tables

• Two-dimensional tables are indexed by two keys.
• In some cases, we could just use a one dimensional table whose keys are pairs of keys.
• We can implement a two-dimensional table as a one-dimensional table whose values are themselves one-dimensional tables.
• We could just use them like that without any specific procedures. However, insertion with two keys is complex enough to merit a convenient two-dimensional procedure.
• We don’t need to box the subtables. They key of the record serves the purpose of '*table*.

Creating local tables

• With our lookup and insert! procedures taking the table as an argument, we can manage multiple tables.
• Another approach is to have separate procedures for each table.
• We could use the message-passing style with the dispatch procedure that we’ve seen a few times already.
• We could also take the λ-calculus approach:

(define (make-table) (lambda (k) false))
(define (lookup key table) (table key))
(define (insert! key value table)
  (lambda (k)
    (if (eq? k key)
        value
        (table k))))

Exercises: 3.24 3.25 3.26 3.27

A Simulator for Digital Circuits

• Digital circuits are made up of simple elements.
• Networks of these simple elements can have very complex behavior.
• We will design a system to simulator digital logic. This type of program is called an event-driven simulation.
• Our computational model is based on the physical components.
  • A wire carries a digital signal, which is either 0 or 1.
  • A function box connects to input wires and output wires.
  • The output signal is delayed by a time that depends on the type of function box.
  • Our primitive function boxes are the inverter, and-gate, and or-gate. Each has its own delay.
  • We construct complex functions by connecting primitives.
  • Multiple outputs are not necessarily generated at the same time.
• We construct wires with (make-wire).
• Evaluating (define a (make-wire)) and (define b (make-wire)) followed by (inverter a b) connects a and b with an inverter.
• The primitive functions are our primitive elements; wiring is the means of combination; specifying wiring patterns as procedures is the means of abstraction.

Primitive function boxes

• The primitives boxes implement “forces” by which changes in the signal of one wire influence the signal of another.
• We have the following operations on wires:
  • (get-signal wire) returns the current value of the signal.
  • (set-signal! wire value) changes the value of the signal.
  • (add-action! wire procedure-of-no-arguments) asserts that the given procedure should be run whenever the signal on the wire changes value.
• The procedure after-delay executes a procedure after a given time delay.

Exercises: 3.28 3.29 3.26 3.30

Representing wires

• Our wires will be computational objects each having two local state variables: signal-value and action-procedures.
• We use the message-passing style as before.
• Wires have time-varying signals and can be incrementally attached to devices. They are a good example of when you need to use a mutable object in the computational model.
• A wire is shared between the devices connected to it. If one changes it, the rest see the change.
• This would be impossible if you didn’t model the wire as an identity, separate from its signal value.

The agenda

• The only thing left is after-delay.
• An agenda is a data structure that schedules things to do.
• For an agenda (define a (make-agenda)), the operations (empty-agenda? a), (first-agenda-item a), (remove-first-agenda-item! a), and (current-time a) are self-explanatory.
• We schedule new items with (add-to-agenda time action a).
• We call the global agenda the-agenda.
• The simulation is driven by propagate, which executes each item on the agenda in sequence.

A sample simulation

Exercises: 3.31

Implementing the agenda

• The agenda is a pair: the current time, and a list of time segments sorted in increasing order of time.
• A time segment is a pair: a number (the time) and a queue of procedures that are scheduled to run during that time segment.
• To add an action to the agenda, we scan its segments, examining their times. If we find the right time, we add the action to the segment’s queue. Otherwise, we create a new segment.
• To remove the first agenda item, we delete the first item in the first queue, and if this makes the queue empty, we delete the first time segment as well.
• Whenever we extract the first item with first-agenda-item, we also update the current time.

Exercises: 3.32

Propagation of Constraints

• We often organize computer programs in one direction: from input to output.
• On the other hand, we often model systems in terms of relations among quantities.
• The equation $dAE = FL$ is not one-directional.
• We will create a language to work in terms of the relations themselves, so that we don’t have to write five procedures.
• The primitive elements are primitive constraints.
  • (adder a b c) specifies $a+b=c$
  • (multiplier x y z) specifies $xy = z$
  • (constant 3.14 x) says that the value of x must be 3.14.
• The means of combination are constructing constraint networks in which constraints are joined by connectors.
• The means of abstraction are procedures.

Using the constraint system

• We create connectors with (make-connector), just like wires.
• We use (probe "name" connector), again just like wires.
• (set-value! connector value 'user) assigns a value to the connector, and this information propagates through the network.
• This will give an error if the new value causes a contradiction.
• (forget-value! connector 'user) undoes the assignment.

Implementing the constraint system

• The overall system is simpler than the digital circuit system because there are no propagation delays.
• There are five basic operations on a connector c: (has-value? c), (get-value c), (set-value! c value informant), (forget-value! c retractor), and (connect c constraint).
• The procedures inform-about-value and inform-about-no-value tells the constraint that a connector has (lost) a value.
• Whenever an adder gets a new value, it checks if it has two and can calculate the third.

Representing connectors

• A connector is a procedural object with local state variables—again, just like a wire.
• Each time the connector’s value is set, it remembers the informant. This could be a constraint, or a symbol like 'user.
• for-each-except is used to notify all other constraints.

Exercises: 3.33 3.34 3.35 3.36 3.37