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

# 3.3.1 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))

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

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

# 3.3.2 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 $Θ(n)$ operations.
• A simply modification lets us implement all the operations with $Θ(1)$ time complexity: keep a pointer to the end as well.
• A queue is a pair formed by cons ing the front-pointer and the rear-pointer of a normal list.

# 3.3.3 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\htmlClass{math-punctuation}{\text{,}}$ 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))))

# 3.3.4 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.

# 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

# 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 that 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.

# 3.3.5 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\htmlClass{math-punctuation}{\text{.}}$
  • (multiplier x y z) specifies $xy = z\htmlClass{math-punctuation}{\text{.}}$
  • (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.