[e-lang] Dynamic whenever, composability of Ever* mechanisms

Kevin Reid kpreid at attglobal.net
Fri Apr 2 17:44:03 EST 2004


Mark S. Miller <markm at caplet.com> wrote:

> At 08:03 AM 3/31/2004  Wednesday, Kevin Reid wrote:
> >(Possible external interface: whenever constructor which accepts a thunk
> >which returns Tuple[any (result value), Set[EverReporter] (those which
> >the result depends on *this* time)].)
> 
> That sounds like a promising approach -- I think I like it. You should try 
> making such a whenever function. If you need to modify any of the code in 
> the source tree, please post these as suggested changes. Thanks.

I don't know whether this version is optimal, but it seems to work. Derived from
E 0.8.26g.



# Copyright 2002 Combex, Inc. under the terms of the MIT X license
# found at http://www.opensource.org/licenses/mit-license.html ................

def Slot := <type:org.erights.e.elib.slot.Slot>
def EverReporter := <type:org.erights.e.elib.slot.EverReporter>
def EverReactor := <type:org.erights.e.elib.slot.EverReactor>

/**
 * Makes an everFormula, which is a "perpetually evaluating expression"
 * involving a formula defined in terms of a list of input values, and a
 * corresponding list of input {@link EverReporters} from which to obtain
 * these values, and to find out when these values change.
 * <p>
 * The everFormula subscribes to each of its input Reporters. Whenever the
 * everFormula receives a report that any of its inputs have changed, it is
 * asked to recalculate the value of the formula.
 * <p>
 * An everFormula will typically be defined in a scope in which these inputs
 * appear as variables (with an EverReporter as each variable's Slot).
 * Therefore, these the input Reporters must be near. This is less of a
 * constraint then it seems: If a desired input Reporter is remote, use
 * {@link makeLamportSlot} to make a local object that acts as an Reporter
 * for a local but stale and eventually consistent copy of the value.
 * <p>
 * The everFormula itself is an EverReporter whose value is the formula's most
 * recently calculated value.  Therefore, everFormulas can also be used as
 * inputs for other everFormulas. This enables a weak form of one-way
 * constraint programming, as found in spreadsheets.
 * <p>
 * An everFormula may range from a whenever-formula to a forever-formula. See
 * {@link EverReporter}.
 * <p>
 * RACE CONDITION DANGER!  Although a lamportSlot used by itself has
 * the kind of strong synchronous guarantees normally associated with
 * Slots (a getValue() get the most recently setValue()), when they are
 * hooked together in Lamport Cells, they, and the Lamport Cell as a
 * whole, has much weaker concurrency guarantees.  Multiple Lamport
 * Cells have no joint simultenaity guarantees, so a formula that
 * depends on several such cells may calculate terribly inconsistent
 * values as it takes snapshots despite the lack of simultenaety.
 * Lamport Cells do guarantee eventual convergence to the current
 * answer given continued interest, quiescence and lack of partition.
 * Likewise, if the formula is side effect free or idempotent (strongly
 * recommended), this creates a corresponding guarantee of converging on the
 * correct calculated value.
 *
 * @author Mark S. Miller (with help from K. Eric Drexler)
 */
def whenever {

    /**
     * <tt>interest</tt> defaults to <tt>thunk{false}</tt>.
     * <p>
     * This creates a whenever-formula rather than a forever-formula.
     *
     * @see EverReporter
     */
    to (inputReporters :EverReporter[], formula :near) :EverReporter {
        whenever(inputReporters, formula, thunk{false})
    }

    /**
     * @param inputReporters A list of inputReporters to be subscribed to.
     * @param formula A no-argument function (whose instance variables will
     *                typically the input variables whose slots are the
     *                inputReporters), that computes and returns the current
     *                value of the everFormula.
     * @param interest If interest() returns true, then we are interested in
     *                 being less stale even in the absence of other
     *                 expressions of local interest.
     */
    to (inputReporters :EverReporter[],
        formula :near,
        interest :near) :EverReporter {

        whenever.makePair(inputReporters, formula, interest)[0]
    }

    /**
     * Like whenever/3, but returns a pair of an EverReporter and its
     * EverReactor.
     * <p>
     * Useful if you want to manually subscribe the reactor to a dynamic set of
     * inputs, but never unsubscribe from them, in which case this is more
     * efficient than whenever.dynamic.
     */
    to makePair(inputReporters :EverReporter[],
                formula :near,
                interest :near) :Tuple[EverReporter, EverReactor] {
        whenever.makePairDynamic(inputReporters, thunk{formula()[0]}, interest)
    }

    /**
     * Like whenever/2, but the formula should return a tuple of the result
     * and additional near EverReporters which the result depends upon.
     */
    to dynamic(inputReporters :EverReporter[],
               pairFormula :near) :EverReporter {
        whenever.makePairDynamic(inputReporters, pairFormula, thunk{false})[0]
    }

    /**
     * Like whenever/3, but the formula should return a tuple of the result
     * and additional near EverReporters which the result depends upon.
     */
    to dynamic(inputReporters :EverReporter[],
               pairFormula :near,
               interest :near) :EverReporter {
        whenever.makePairDynamic(inputReporters, pairFormula, interest)[0]
    }

    /**
     * Takes arguments as whenever.dynamic/3 and returns as 
     * whenever.makePair/3.
     */
    to makePairDynamic(inputReporters :EverReporter[],
                       pairFormula :near,
                       interest :near) :Tuple[EverReporter, EverReactor] {

        # the value of the formula as a whole
        var value := null
        
        # Our own generation number for our value, for coordinating with
        # EverReactors downstream from us.
        var myGeneration := 0

        # Those downstream waiting to hear this EverFormula report a change
        # to its value.
        var optReactors := null

        # The subset of upstream inputReporters that have reported to us, but
        # which we haven't yet re-subscribed with.  This allows us to delay
        # re-subscription until there's a demonstration of local interest.
        # Each element is a pair of the Reporter and the Reporter's generation
        # number as of their last report to us.
        var optSources := null

        # Reporters we will want to subscribe to if there is interest, but not
        # more than once, unless the pairFormula thunk returns it again.
        var dynamicSources := [].asSet()
        
        # Reporters we've subscribed to, which we need to remember so we don't
        # subscribe twice.
        var dynamicSubscriptions := [].asSet()
        
        # Generations from subscriptions we might want to resume
        var oldDynamicGenerations := [].asMap()

        def everFormula
        def everFormulaReactor

        /**
         * Called internally when there's evidence of local interest in
         * a current value.
         * <p>
         * Triggers any delayed reregistrations.
         */
        def localInterest() :void {
            if (optSources != null) {
                for [reporter, srcGen] in optSources {
                    reporter.whenUpdated(everFormulaReactor, srcGen)
                }
                optSources := null
            }
            for reporter in dynamicSources {
                reporter.whenUpdated(def dynamicSourceReactor {
                    to reactToUpdate(_, newReporterGen :int, _) :void {
                        oldDynamicGenerations with= (reporter, newReporterGen)
                        everFormulaReactor <- update()
                        dynamicSubscriptions without= reporter
                    }
                }, oldDynamicGenerations.fetch(reporter, thunk{-1}))
                dynamicSubscriptions with= reporter
            }
            dynamicSources := [].asSet()
        }

        /**
         * The everFormulaReactor is subscribed to each of the inputReporters
         * so it can receive reports of state changes.
         */
        bind everFormulaReactor implements EverReactor {

            /**
             * Recalculate & report to downstream EverReactors
             */
            to update() :void {
                def [newValue, newDynamicSources] := pairFormula()

                dynamicSources := 
                  newDynamicSources.asSet() &! dynamicSubscriptions
                
                # Clean up oldDynamicGenerations: we only need entries for
                # reporters which we plan to subscribe to, i.e. those in
                # dynamicSources.
                for reporter ? !dynamicSources.contains(reporter) \
                  in oldDynamicGenerations {
                    oldDynamicGenerations without= reporter
                }

                if (! Ref.isSettled(value) ||
                      ! Ref.isSettled(newValue) ||
                      value != newValue) {
                    # If it's not known to be the same.

                    value := newValue
                    myGeneration += 1
                    if (optReactors == null) {
                        if (interest()) {
                            # Although no one is interested in us at the
                            # moment, we're interested anyway.
                            localInterest()
                        }
                    } else {
                        for reactor in optReactors {
                            reactor <- reactToUpdate(value,
                                                     myGeneration,
                                                     everFormula)
                        }
                        optReactors := null
                        # The fact that we had downstream reactors to report to
                        # is sufficient demonstration of interest for us to
                        # resubscribe to out inputs.
                        localInterest()
                    }
                }
            }
            /**
             *
             */
            to reactToUpdate(_,
                             newReporterGen :int,
                             optNewReporter :nullOk[EverReporter]) :void {
                if (optNewReporter != null) {
                    if (interest() || optReactors != null) {
                        optNewReporter.whenUpdated(everFormulaReactor,
                                                   newReporterGen)
                    } else {
                        if (optSources == null) {
                            optSources := [].diverge()
                        }
                        optSources.push([optNewReporter, newReporterGen])
                    }
                }
                # Since update is going to reread its input
                # values, we needn't be concerned about
                # whether newReporterGen is most recent we've heard,
                # but we do need to use it when re-subscribing.
                everFormulaReactor.update()
            }
        }

        # initial connectivity
        everFormulaReactor.update()
        for reporter in inputReporters {
            reporter.whenUpdated(everFormulaReactor)
        }

        /**
         * The everFormula reports successively more recent values calculated
         * by the formula.
         */
        bind everFormula implements EverReporter {

            /**
             * Synchronously returns the locally cached value, but also
             * arranges for this value to become more current.
             * <p>
             * Only a watched Slot never spoils.
             */
            to getValue() :any {
                localInterest()
                value
            }

            /**
             * reactor wants to be informed of any changes more recent
             * than my lastGeneration.
             * <p>
             * If we've got more recent news, let it know immediately.
             * Otherwise, remember to inform it.  In either case, this request
             * demonstrates local interest.
             */
            to whenUpdated(reactor :EverReactor, lastGeneration :int) :void {
                localInterest()
                if (lastGeneration < myGeneration) {
                    reactor <- reactToUpdate(value,
                                             myGeneration,
                                             everFormula)
                } else {
                    if (optReactors == null) {
                        optReactors := [].diverge()
                    }
                    optReactors.push(reactor)
                }
            }

            /**
             * For initial connectivity.
             */
            to whenUpdated(reactor :EverReactor) :void {
                everFormula.whenUpdated(reactor, -1)
            }
        }
        [everFormula, everFormulaReactor]
    }
}




? def makeLamportSlot := <elib:slot.makeLamportSlot>
# value: <makeLamportSlot>

? def a := makeLamportSlot(1)    
# value: <lamport 1 as of 0>

? def b := makeLamportSlot(2)
# value: <lamport 2 as of 0>

? def c := makeLamportSlot(3)
# value: <lamport 3 as of 0>

? def l := makeLamportSlot([a])
# value: <lamport [<lamport 1 as of 0>] as of 0>

? def whenever := <elib:slot.whenever>
# value: <whenever>

? def m := whenever.dynamic([l], thunk{
>     var out := []
>     for x in l.getValue() {
>         out with= x.getValue()
>     }
>     [out, l.getValue()]
> })
# value: <everFormula_23>

? m.getValue()
# value: [1]

? a.setValue(11)
? m.getValue()
# value: [1]

? m.getValue()
# value: [11]

? l.setValue([a, b, c])
? m.getValue()
# value: [11, 2, 3]

? b.setValue(22)
? m.getValue()
# value: [11, 2, 3]

? m.getValue()
# value: [11, 22, 3]

? a.setValue(111)
? l.setValue([])
? l.setValue([a, c])
? m.getValue()    
# value: []

? m.getValue()
# value: [111, 3]

? a.setValue(4)
? b.setValue(5)
? c.setValue(6)
? m.getValue()
# value: [4, 6]



More information about the e-lang mailing list