3.3.6 · Relations through shared state

A constraint propagates knowledge in either direction.

Connectors remember values and their informants, so an adder relation derives any missing term and retracts knowledge that depended on a forgotten value.

Guiding question

How can one relation react correctly no matter which two values arrive first?

Represent a connector value, informant, and constraint list explicitly
Notify connected constraints when knowledge appears or disappears
Use an adder relation to derive any one of its three values
Retract dependent knowledge without erasing independent user values

Each connector stores whether it has a value, the value, who supplied it, and the constraints to notify. set-value! accepts the first value and sends new-value to every constraint except the setter. The adder can therefore compute total from two terms or either term from the total and the other term.

forget-value! succeeds only when the retractor is the stored informant. When the user forgets total, the adder retracts right because it supplied that derived value, but it cannot retract the independently supplied left value. Supplying a new right value then derives a new total through the same relation.

SICP code2,377 of 1,048,576 UTF-8 bytes

(begin
  (define (make-connector) (vector #f 0 #f '()))
  (define (has-value? connector) (vector-ref connector 0))
  (define (get-value connector) (vector-ref connector 1))
  (define (inform-about-except exception message constraints)
    (if (null? constraints)
        'done
        (begin
          (if (eq? exception (car constraints))
              #f
              ((car constraints) message))
          (inform-about-except exception message (cdr constraints)))))
  (define (set-value! connector value setter)
    (if (has-value? connector)
        (if (= (get-value connector) value) 'ignored 'contradiction)
        (begin
          (vector-set! connector 0 #t)
          (vector-set! connector 1 value)
          (vector-set! connector 2 setter)
          (inform-about-except setter 'new-value (vector-ref connector 3))
          'set)))
  (define (forget-value! connector retractor)
    (if (eq? retractor (vector-ref connector 2))
        (begin
          (vector-set! connector 0 #f)
          (vector-set! connector 2 #f)
          (inform-about-except retractor 'lost-value (vector-ref connector 3))
          'forgotten)
        'ignored))
  (define (connect connector constraint)
    (vector-set! connector 3 (cons constraint (vector-ref connector 3)))
    (if (has-value? connector) (constraint 'new-value) #f)
    'connected)
  (define (adder left right total)
    (define (new-value)
      (cond ((and (has-value? left) (has-value? right))
             (set-value! total (+ (get-value left) (get-value right)) me))
            ((and (has-value? left) (has-value? total))
             (set-value! right (- (get-value total) (get-value left)) me))
            ((and (has-value? right) (has-value? total))
             (set-value! left (- (get-value total) (get-value right)) me))
            (else 'waiting)))
    (define (lost-value)
      (forget-value! left me)
      (forget-value! right me)
      (forget-value! total me)
      (new-value))
    (define (me message)
      (if (eq? message 'new-value) (new-value) (lost-value)))
    (connect left me)
    (connect right me)
    (connect total me)
    me)
  (define left (make-connector))
  (define right (make-connector))
  (define total (make-connector))
  (adder left right total)
  (set-value! left 10 'user)
  (set-value! right 32 'user)
  (list (get-value left) (get-value right) (get-value total)))

(begin
  (define (make-connector) (vector #f 0 #f '()))
  (define (has-value? connector) (vector-ref connector 0))
  (define (get-value connector) (vector-ref connector 1))
  (define (inform-about-except exception message constraints)
    (if (null? constraints)
        'done
        (begin
          (if (eq? exception (car constraints))
              #f
              ((car constraints) message))
          (inform-about-except exception message (cdr constraints)))))
  (define (set-value! connector value setter)
    (if (has-value? connector)
        (if (= (get-value connector) value) 'ignored 'contradiction)
        (begin
          (vector-set! connector 0 #t)
          (vector-set! connector 1 value)
          (vector-set! connector 2 setter)
          (inform-about-except setter 'new-value (vector-ref connector 3))
          'set)))
  (define (forget-value! connector retractor)
    (if (eq? retractor (vector-ref connector 2))
        (begin
          (vector-set! connector 0 #f)
          (vector-set! connector 2 #f)
          (inform-about-except retractor 'lost-value (vector-ref connector 3))
          'forgotten)
        'ignored))
  (define (connect connector constraint)
    (vector-set! connector 3 (cons constraint (vector-ref connector 3)))
    (if (has-value? connector) (constraint 'new-value) #f)
    'connected)
  (define (adder left right total)
    (define (new-value)
      (cond ((and (has-value? left) (has-value? right))
             (set-value! total (+ (get-value left) (get-value right)) me))
            ((and (has-value? left) (has-value? total))
             (set-value! right (- (get-value total) (get-value left)) me))
            ((and (has-value? right) (has-value? total))
             (set-value! left (- (get-value total) (get-value right)) me))
            (else 'waiting)))
    (define (lost-value)
      (forget-value! left me)
      (forget-value! right me)
      (forget-value! total me)
      (new-value))
    (define (me message)
      (if (eq? message 'new-value) (new-value) (lost-value)))
    (connect left me)
    (connect right me)
    (connect total me)
    me)
  (define left (make-connector))
  (define right (make-connector))
  (define total (make-connector))
  (adder left right total)
  (set-value! left 10 'user)
  (set-value! right 32 'user)
  (list (get-value left) (get-value right) (get-value total)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (10 32 42). The second returns ((10 32 42) (#t #f #f) 15).

Trace focus

Follow each connector notification to the adder. In the second run, distinguish the user-owned left value from the adder-owned right value, then watch the lost-value message retract only the derived path before a new total propagates.

Try it yourself

Change the program and compare the result.

In the second program, forget left instead of total. Predict which connectors lose values and which user-supplied value remains.

Show hint

A connector accepts a retraction only from its current informant. The adder can retract values that it supplied, not values supplied by user.

Complete this lesson

0 of 21 lessons complete in this chapter0%