A constraint propagates knowledge in either direction.
Connectors remember values and their informants, allowing an adder relation to derive any missing term and retract only knowledge that depended on a forgotten value.
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.
(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)))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (10 32 42). The second returns ((10 32 42) (#t #f #f) 15).
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.
Change the program before you read the hint.
In the second program, forget left instead of total. Predict which connectors lose values and which user-supplied value remains.
Show one hint
A connector accepts a retraction only from its current informant. The adder can retract values that it supplied, not values supplied by user.