dynamically updating dependency networks in Smalltalk

[Kragen Sitaker]

This lets you construct DAGs of arbitrary values computed by arbitrary
blocks, and efficiently updates all outdated values whenever any of
them change.  There's a handy #value: method to set the value to a
particular constant.

Squeak (well, Smalltalk) is a pretty pleasant environment for this
kind of thing.  In particular the support for circular pointers (at
first, before I used WeakSet) and WeakSet were nice here, nicer than
Python; being able to refer to '+' as an ordinary method was nice
(much nicer than the equivalent in Python); and #detect:ifNone: seems
nicer to me than the equivalent locutions in other languages.
Consider:

	parents detect: [ :p | p valid not ] ifNone: [ foo ].

versus
	if not filter(lambda p: not p.valid(), parents): foo
	if not [p for p in parents if not p.valid()]: foo
	foo unless grep { not $_->valid } @parents;

Testing to ensure that the WeakSet really was weak was a little harder
than in Python, in the sense that I had to explicitly issue a
"Smalltalk garbageCollectMost", but I could see the results
immediately in an inspector window, which made up for it.

I seem to recall that there's some sort of observer-observed pattern
already built into Smalltalk but I couldn't find it.

'From Squeak3.6 of ''6 October 2003'' [latest update: #5429] on 22 June 2004 at 6:13:57 am'!
Object subclass: #DynUpdater
	instanceVariableNames: 'value valid children formula parents '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'My stuff'!
!DynUpdater commentStamp: 'kjs 6/22/2004 06:01' prior: 0!
Dynamically updating numbers (or whatever) in formula networks.

"((DynUpdater withValue: 1) + (DynUpdater withValue: 2)) value"

Structure:
 valid			Boolean -- whether I currently have a value
 value			Object -- current value (if valid)
 children		WeakSet -- the other variables whose values depend on me
 formula		Block -- how my value is computed from my parents
 parents		OrderedCollection -- the variables from whom I compute my value.

The 'valid' bit is used to keep a single input value change from causing an exponential number of recalculations.!


!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 05:23'!
+ anOther
	"Answer a dynamically updating variable for my sum with another."
	^ self withBinop: #+ andOther: anOther.! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:01'!
addChild: aDynUpdater
	"Add a variable that depends on me."
	children add: aDynUpdater! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:02'!
formula: newFormula parents: newParents
	"Set my formula and parents, initializing me if necessary."
	valid ifNil: [
		valid _ false.
		children _ WeakSet new.
		parents _ #().
	].
	self invalidate.
	parents do: [ :p | p removeChild: self ].
	parents _ newParents.
	parents do: [ :p | p addChild: self ].
	formula _ newFormula.
	self recalculate.! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:02'!
invalidate
	"Calling this tells me that my current value is invalid."
	valid ifTrue: [
		valid _ false.
		value _ nil.
		children do: [ :d | d invalidate].
	].! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:12'!
newValue: newValue
	"Called internally to set the new value."
	value _ newValue.
	valid _ true.
	children do: [ :d | d recalculate ].
! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:11'!
recalculate
	"Calling this tells me one of my parents has become valid."
	formula ifNil: [ self error: 'Can''t recalculate without a formula.' ].
	valid ifTrue: [^self].  "I already know my value."
	parents detect: [ :p | p valid not ] ifNone: [
		self newValue: (formula valueWithArguments: (parents collect: [ :p | p value ])).
	].! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 00:24'!
removeChild: aDynUpdater
	children remove: aDynUpdater! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 03:57'!
valid
	^valid.! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 03:57'!
value
	valid ifFalse: [self error: 'Can''t read value; presently invalid'].
	^value.! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:03'!
value: newValue
	"Make me merely return a constant value."
	self formula: [newValue] parents: #().
! !

!DynUpdater methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:09'!
withBinop: aBinop andOther: anOther
	^ self class withFormula: [ :a :b | a value perform: aBinop with: b value ]
		andParents: { self. anOther }.
! !

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

DynUpdater class
	instanceVariableNames: ''!

!DynUpdater class methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:05'!
withFormula: aFormula andParents: newParents
	"Answer a DynUpdater depending on newParents computing its value with aFormula."
	^ (DynUpdater new formula: aFormula parents: newParents)! !

!DynUpdater class methodsFor: 'as yet unclassified' stamp: 'kjs 6/22/2004 06:04'!
withValue: aValue
	"Answer a DynUpdater that will return value aValue."
	^ (DynUpdater new value: aValue).! !