5B Computational Objects⁠

# Part 1

# Recap

• We’re going to do some complicated programming to illustrate what you can do with mutable state.
• We were motivated by the need to model physical systems.
• Programming this way buys us modularity, if done correctly.

# Electrical systems

• We are going to model electrical systems.
• We can consider the things wires are connected to as objects.
• The connections can be made abstract. We use ideal wires.
• We create wires with (make-wire), and we connect them with gates: and-gate, or-gate, and inverter.
• (inverter a b) connects wires a and b with an inverter.
• Our language will be embedded in Lisp, like the Henderson picture language.
• We can wire up half adders and full adders with these gates.
• We have primitives (wires), means of combination (gates), and means of abstraction (lambda). Lambda is the ultimate glue.

# Implementing the primitives

• All we have to do is implement the primitives. The rest is free.
• An inverter works by adding an action to its input wire. When a new signal arrives, this action delays and then sets the signal of its output wire to the logical-not of its input signal.
• And-gates and or-gates are implemented similarly. The action must be added to both input wires.
• Each wires must remember its signals and its list of actions.
• The actions procedures need to keep references to their wires. These are captured by the lambda inside the gate procedures.
• We implement wires with the message-passing style. It responds to get-signal, set-signal!, and add-action!.
• The wire executes all actions after its signal is set.

# Scheduling delayed tasks

• The agenda is a schedule of actions to run. Whenever after-delay is used in an action, a task is added to the agenda.
• These get executed in the proper order, with a time variable maintaining the correct time.
• The propagate procedure executers everything the agenda, emptying it as it goes.

# Part 2

# Implementing the agenda

• We’ve made a simulation where objects and state changed in the computer match the objects and state changes in the world.
• We’re going to use agendas (priority queues) to organize time.
• We have a constructor make-agenda; selector current-time and first-item; predicate empty-agenda?; and mutators add-to-agenda! and remove-first-item!.
• We will represent it as a list a segments. Each segment is a time cons ed to a queue of tasks (procedures of no arguments).
• To add a task, we either add it to the queue of the appropriate segment, or create a new segment with that time.

# Queues

• We construct queues with (make-queue).
• There are two mutators, (insert-queue! q x) and (delete-queue! q); a selector, (front-queue q); and a predicate, (empty-queue? q).
• A queue is represented as a front pointer of a list cons ed to the rear pointer of the same list.
• The mutators use set-car! and set-cdr!.

# Part 3

# Identity of pairs

• Before, all we needed to know about cons was that for all values of x and y, (= x (car (cons x y))) and (= y (cdr (cons x y))). This says nothing about identity.
• These no longer tell the whole story, now that we have mutators.
• This raises a question: if you change the car of a pair, do all pairs that look the same also change?
• Pairs now have an identity.
• When we have multiple names for the same object, they are called aliases. Changing one changes them all. Sometimes sharing is what we want.

# Lambda calculus

• Assignment and mutators are equally powerful. We can implement the cons mutators in terms of set!.
• We’ve already seen Alonzo Church’s way of creating pairs just with lambda expressions:

(define (cons x y)
  (lambda (m)
    (m x y)))
(define (car x) (x (lambda (a d) a)))
(define (cdr x) (x (lambda (a d) d)))

• We can change it to allow mutation:

(define (cons x y)
  (lambda (m)
    (m x
       y
       (lambda (n) (set! x n))
       (lambda (n) (set! y n)))))
(define (car x)
  (x (lambda (a d sa sd) a)))
(define (cdr x)
  (x (lambda (a d sa sd) d)))
(define (set-car! x v)
  (x (lambda (a d sa sd) (sa v))))
(define (set-cdr! x v)
  (x (lambda (a d sa sd) (sd v))))

• (I just realized that creating objects this way, where you apply the object to a procedure that is passed all the state variables, is just like pattern matching.)