Ripple

Ripple is something I thought up in order to simplify the chore of having to update user interfaces whenever the data they're displaying changes. It has a lot in common with JavaBeans, but I invented it before JavaBeans was around, so I had to invent all my own terminology. For the sake of people who already know JavaBeans, here's a quick glossary.

Ripple Term JavaBeans Term
stone property that fires events when it changes
greedy list a property's list of registered listeners
relation event handler / listener implementation

Where did my words come from? Think of changes to a variable as "rippling" out from the variable to the things that depend on it. And if you think of the ripples as being ripples in water, then the ripples probably came from throwing a "stone" into a pond. "Relations" specify the relationships between variables (e.g. "x = y + z"). "Greedy lists" are so named because they're a list of all the relations that want to know when a stone changes -- that is, they are a list of relations which are "greedy" for change notifications.

Ripple has a couple concepts for which JavaBeans has no equivalent.

Deep Function Basically, deep functions are functions that act like stones when you call them from inside a relation -- they notify the relation whenever anything changes that might make them return a different value. They're called "deep" because they're transitive -- if one deep function calls another deep function, you end up depending on both of them.
Terminator A relation can delete itself if a condition comes true. This condition is specified by tacking an "until (...)" clause onto the end of the relate-block. Also, if a "while (...)" is embedded inside the relation, the relation is temporarily suspended whenever the while-condition is false.

Ripple Implementation

Relations and Greedy Lists

The Ripple implementation centers around relations and greedy lists. A relation is a function object responsible for either keeping a single relationship up to date, or deciding when to execute a when-block. A greedy list is a list of all the relations that depend on a particular stone. Relations are implemented as anonymous inner classes:

Ripple Java Translation
class Foo {
    int x;
    stone int y, z;

    relate {
        x = y + z;
    } forever;

    public void setY(int new_y) {
        y = new_y;
    }
}
class Foo {
    int x;
    int y, z;
    GreedyList y_greedy = new GreedyList(),
        z_greedy = new GreedyList();

    Relation x_bound = new Relation() {
        protected void init() {
            y_greedy.add(this);
            z_greedy.add(this);
        }
        public void update() {
            x = y + z;
        }
    }

    public void setY(int new_y) {
        y = new_y;
        y_greedy.update();
    }
}

Depending on Functions: Generous Lists

Callers of a deep function don't know which stones, other than the parameters, the function depends on -- which means that the caller doesn't know which greedy lists to add to. So deep functions have to return the greedy list of every stone they depend on. This list of greedy lists is called a generous list. The generous list is recreated for each caller -- this is necessary when the function references array elements where the array index is passed as a parameter. It also has the nice effect of preventing relations from depending on stones that don't actually affect them.

Generous lists are returned to the caller via the java equivalent of an out parameter: a single-element array tacked onto the end of the original argument list.

deep public int getNetProfit() {
    if (irsIsWatching)
        return profit;
    else
        return profit + fudgeFactor;
}
public int getProfit(Vector[] generous) {
    generous[0].addElement(irsIsWatching_greedy);
    if (irsIsWatching) {
        generous[0].addElement(profit_greedy);
        return profit;
    } else {
        generous[0].addElement(profit_greedy);
        generous[0].addElement(fudgeFactor_greedy);
        return profit + fudgeFactor;
    }
}

Note: deep functions aren't allowed to contain relate-blocks, because I don't want to think about how to implement that.

Terminators and Conditionals

Terminators (".. until (..)") and conditionals ("while (..) ..") are implemented in the update method of the relations they control. The alternative is to implement them as separate relations, but that raises several issues in regard to ensuring correct order of execution (terminators and conditionals must be evaluated before the relations they control, but greedy lists have no concept of priority).

relate {
    while (q > 100)
        x = y;
} until (done);
Relation x_bound = new Relation() {
    protected void init() {
        q_greedy.add(this);
        y_greedy.add(this);
        done_greedy.add(this);
    }
    public void update() {
        if (done)
            unbind();
        else {
            if (q > 100)
                x = y;
        }
    }
    protected void unbind() {
        y_greedy.remove(this);
        q_greedy.remove(this);
        done_greedy.remove(this);
        Foo.this.x_bound = null;
    }
}

Meta-Relations

Users never create a meta-relation -- they're only generated automatically. A meta-relation is a relation that, in its update method, messes around with other relations. A meta-relation is needed whenever a relation uses a dot expression (a.b) or an array subscript (a[b]).

The example below declares a relationship "a = m.n". If m.n changes, the relation responsible for the relationship needs to update a. But if m changes, the relation needs to remove itself from the greedy list of the old m.n, add itself to the greedy list of the new m.n, and then update a. Because adding and removing from greedy lists takes time, we don't want to do it unless we have to. So we have different relations for m_greedy and m.n_greedy. The former is a meta-relation.

relate {
    a = m.n;
} forever;
Relation a_bound = new Relation() {
    protected void init() {
        m.n_greedy.add(this);
        new MetaRelation(this, m_greedy) {
            protected GreedyList getGreedy() {
                return m.n_greedy;
            }
        }
    }
    public void update() {
        a = m.n;
    }
}

The above translation assumes this definition for the class MetaRelation:

class MetaRelation extends Relation {
    Relation parentRelation;
    GreedyList old_greedy;
    public MetaRelation(Relation parentRelation, GreedyList addTo) {
        this.parentRelation = parentRelation;
        addTo.add(this);
        old_greedy = getGreedy();
    }
    public void update() {
        old_greedy.remove(parentRelation);
        old_greedy = getGreedy();
        old_greedy.add(parentRelation);
        parentRelation.update();
    }
    protected abstract GreedyList getGreedy();
}

I'm still working on figuring out array meta-relations ("a = m.n[o][p].q").

Cascading

Cascading is mostly an efficiency problem. It's similar to common subexpression elimination. Consider this example:

relate {
    z = x + y;      // Relation1
    y = x + 1;      // Relation2
} forever;

Both z and y depend on x, and z depends on y. If you're not smart about it, when x changes, it triggers Relation1 and Relation2; then Relation2 updates y, which triggers Relation1 again. So Relation1 gets triggered twice. This is not a bug, but it is a waste of time.

The redundancy can be elimated by changing the way relationships are updated. Instead of updating relationships recursively, the reference that changed (x in this example) examines the entire tree of dependants, eliminates redundant updates, and then iteratively updates every relationship that needs updating. So when x changes, it would eliminate the redundant updates of Relation1.

The algorithm is basically a pre-order traversal of the dependency graph. When you encounter the same relationship twice, you only use the later encounter. One thing complicates this otherwise straighforward algorithm: making sure relationships are only updated if absolutely necessary. For example,

relate {
    W = A + B;
    X = (A > B);
    Y = X + 1;
    Z = X + W;
} forever;

Suppose A starts at 0 and B starts at 100, and then A becomes 10. W is re-evaluated and it changes from 100 to 110. X is also re-evaluated, but it doesn't change (it stays true). So Y should not be re-evaluated because it only depends on X, which didn't change. Okay, so we just don't re-evaluate anybody who depends on X. But that means that we don't re-evaluate Z -- even though Z also depends on W, which did change. So we need to be a bit smarter about it.

One way to be smarter about it is to use reference counts. While traversing the dependency tree, you ignore duplicate updates of the same Relation, but for every update you ignore, you increment that Relation's reference count. Then you start updating Relations starting at the beginning of the list, only if their reference count is greater than 0. Whenever a variable doesn't change, you decrement the reference count on all the Relations that depended on that variable.

This algorithm needs to know which other Relations a given Relation will cause to update(). Relations don't actually update() each other directly -- they do it via greedy lists. So Relations have a method named getBoundGreedy() that returns the greedy list(s) that they update() when their update() method is called (it could return null if the Relation doesn't perform any assignments). If a Relation calls a function, it also has to return all the greedy lists that the function might update.

Remaining Issues

Ripple could probably do updates concurrently with a little more work in the anti-cascading algorithm.

I'm not sure whether it should be legal to have circular relationships. For example,

relate {
    x = y + 1;
    y = x - 1;
} forever;

Related Work


Last updated March 8, 1997
Back to Kimberley's Code.
Back to Kimberley's Home Page.