It's Actors All The Way Down

The fringe of a binary tree is simply the sequence of leaves reading from left to right [1]. Comparing the fringe of two binary trees to see if they are the same has been described as the simplest problem that requires multiprocessing or coroutines to easily solve [2]. The challenge is to stop the comparison once the first difference is found and avoid generating the entire fringe unless absolutely necessary [3]. We have previously explored how to solve this problem using actors written in Humus. Now we revisit the problem considering both functional and actor-based solutions in JavaScript.

Functional Fringe

We start with the definition of a simple binary-tree object:

function Y(a, b) {  // binary tree with left branch `a` and right branch `b`
    this.a = a;
    this.b = b;
}

Using this definition, we can create a few sample binary trees.

var aTree = new Y(1, new Y(new Y(2, 3), 4));  // <1, <<2, 3>, 4>>
var bTree = new Y(new Y(1, 2), new Y(3, 4));  // <<1, 2>, <3, 4>>
var cTree = new Y(new Y(new Y(1, 2), 3), new Y(5, 8));  // <<<1, 2>, 3>, <5, 8>>

Figure 1 – Sample Binary Trees

The fringe of a binary tree can be computed with a simple recursive function.

var fringe = function fringe(tree) {
    if (tree instanceof Y) {
        let left = fringe(tree.a);
        let right = fringe(tree.b);
        return left.concat(right);
    }
    return [ tree ];
};

For a binary tree, we first calculate the fringe of the left branch, followed by the right, and concatenate them together. For a leaf, we create a list containing the leaf. The result is a flat list containing the leaves of the tree in left-to-right order.

fringe(aTree);  // [ 1, 2, 3, 4 ]
fringe(bTree);  // [ 1, 2, 3, 4 ]
fringe(cTree);  // [ 1, 2, 3, 5, 8 ]

Of course, the problem with this approach comes when we want to compare the fringe of two trees. We have to generate the entire fringe of both trees before we can begin comparing elements. We would prefer to generate one leaf of the fringe from each tree, compare them, and only generate the next leaf if they match. This way we can stop generating the fringe as soon as we find a mismatch. So, how can we defer generating the rest of the fringe?

Suspending Computations in Closures

One way to defer a computation is to suspend it in a closure. That is, define a function that implements the deferred computation, and call it when we want the computation to be performed. We can use this technique to generate an infinite series of values given a starting value and an update function for determining the next value in the series.

var genSeries = function genSeries(value, update) {
    return () => {
        let next = genSeries(update(value), update);
        return { value: value, next: next };
    };
};

The genSeries function returns a function which takes no parameters. When the returned function is called, we use genSeries to generate a function representing the next value. Then we return the current value along with the next function. Notice how this captures the deferred computation of the next value in the series. Nothing happens until the returned function is called. Consider how genSeries could be used to generate a series of numbers starting with 1 and increasing by 1 at a time.

var r = (genSeries(1, n => n + 1))();  // [ 1, 2, 3, ... ]
while (r.value !== undefined) {
    // ... do something with r.value ...
    r = r.next();
}

We call genSeries to create stream generator with an initial value of 1 and an update function that adds 1 each time. The stream generator is called immediately to produce the result r. As long as r.value is defined, we have a value to work with. Then, we call r.next to obtain the next result.

We can apply the same technique to generating the fringe of a binary tree.

var genFringe = function genFringe(tree, next) {
    next = next || (() => ({}));  // default next == end
    if (tree instanceof Y) {
        return () => {
            var right = genFringe(tree.b, next);
            var left = genFringe(tree.a, right);
            return left();
        }
    } else {
        return () => ({ value: tree, next: next });
    }
};

The genFringe function returns a suspended computation that generates the next leaf of the fringe. For a binary tree, we generate suspended computations for the right and left branches, and return the result of evaluating the left branch. For a leaf, we return the value of the leaf along with a function for generating the next leaf. Suspended calculations are chained together using next to indicate where to resume the search for the next leaf. When there are no more leaves, we return an empty object (where value is undefined).

Comparing Suspended Sequences

Now that we have defined stream generators for the fringe, we can implement a stream comparison function that stops when it finds the first difference. The only time it will need to generate the entire fringe is if all of the leaves match.

var sameFringe = function sameFringe(s0, s1) {
    let r0 = s0();  // get result from first stream
    let r1 = s1();  // get result from second stream
    while (r0.value === r1.value) {
        if (r0.value === undefined) {
            return true;   // stream end
        }
        r0 = r0.next();  // next result from first stream
        r1 = r1.next();  // next result from second stream
    }
    return false;  // mismatch
};

The two streams s0 and s1 are represented by generators functions, such as those returned by genSeries or genFringe. These functions are called to generate results r0 and r1 for each stream. The comparison loops as long as the result values are the same. If the results are undefined then we’ve reached the end of both streams, and they match, so we return true. Otherwise, we use the next functions to generate the next pair of results. If any pair of results has mismatched values, the stream do not match, so we return false. Note that this also handles the case where one stream ends (value is undefined) before the other.

sameFringe(genFringe(aTree), genFringe(bTree));  // true
sameFringe(genFringe(bTree), genFringe(cTree));  // false

Using sameFringe on our sample trees demonstrates that aTree and bTree have the same fringe, while the fringe of cTree is different.

Using JavaScript Generators

ECMAScript 2015 (ES6) introduces support for Generator functions which conform to the Iterable and Iterator protocols. This gives us another mechanism to suspend generation of the entire fringe. Using a function* definition, we can create an iterator which produces a leaf of the fringe each time it is called.

var iterFringe = function* iterFringe(tree) {
    if (tree instanceof Y) {
        yield* iterFringe(tree.a);
        yield* iterFringe(tree.b);
    } else {
        yield tree;
    }
};

For a binary tree, we use yield* to delegate first to an iterator for the left branch, then to an iterator for the right branch. For a leaf, we simply yield the value.

The state of the search for the next leaf of the fringe is held in the iterator(s). When the iterator’s next function is called, it returns a result object. The value property of the result object is the next value from the generator, or undefined when the iteration is completed. The done property of the result object is true when the iteration is completed, and false otherwise.

var sameIterable = function sameIterable(g0, g1) {
    let r0 = g0.next();  // get result from first sequence
    let r1 = g1.next();  // get result from second sequence
    while (r0.value === r1.value) {
        if (r0.value === undefined) {
            return true;   // stream end
        }
        r0 = g0.next();
        r1 = g1.next();
    }
    return false;  // mismatch
};

We can compare two iterables using the same strategy we used in sameFringe to compare functional fringe streams. The differences are highlighted above. Iterators are stateful, so we must call next on the iterator. Iterators can not be reused. By contrast, our lazy functional streams had a stateless next in each result object, allowing us to replay a stream from any position.

Actor-Based Fringe

As previously described, an actor-based solution can be defined using a pair of asynchronous pull-based streams. We can incrementally pull leaves from each tree and compare them, stopping when a mismatch is found.

Since Actors are not directly supported by JavaScript, we will use a lightweight framework to implement them. A previous article described this framework. Here we will use a more compact version, so small it fits in a tweet (if you squeeze out the extra space).

var tart = (f) => {
    let c = (b) => {
        let a = (m) => {
            setImmediate(() => {
                try { x.behavior(m) } catch (e) { f && f(e) }
            })
        }, x = { self: a, behavior: b, sponsor: c };
        return a
    };
    return c
};

The tart function (tiny actor run-time) takes an optional failure handler and returns a sponsor function representing the capability to create new actors. The sponsor function takes a behavior function and returns a function representing the capability to send an asynchronous message to the newly-created actor. The behavior function is kind of like a listener (specifying how to respond to message-events) where the actor reference emits a message-event [4].

An important difference is that sending a message via an actor reference does not immediately invoke the behavior, it simply schedules (via setImmediate) the event for asynchronous execution. When the behavior function is invoked (with the message as a parameter), this refers to the actor’s private context where this.self is the send capability, this.behavior is the behavior function (assigning to this property implements the actor become primitive), and this.sponsor is the create capability.

Actor-per-Node

The strategy for our actor-based solution is the same as the one we used with closure-suspended computations. Actor behaviors always suspended computations since they are not evaluated until an asynchronous message is received by the actor. Each actor represents a position in the tree, just like the closure did.

var mkFringe = function mkFringe(tree, next) {
    return function fringeBeh(cust) {
        next = next || this.sponsor(function (cust) { cust({}); });
        if (tree instanceof Y) {
            var right = this.sponsor(mkFringe(tree.b, next));
            var left = this.sponsor(mkFringe(tree.a, right));
            left(cust);
        } else {
            cust({ value: tree, next: next });
        }
    };
};

The mkFringe function returns an actor behavior function, which is given to a sponsor to create an actor representing a search location in a tree. No work is done until the actor actually receives a message representing the customer waiting for the result. Since all actor communication is through asynchronous messages (there are no “return” values), the customer is like a call-back which receives asynchronous notification of the result.

When an actor with fringeBeh receives a customer cust, it checks if a next actor was provided and if not, creates a default representing the stream end. If the actor references a branch in the tree, new actors are created for the right and left sub-trees, and the customer is passed to the left (for language geeks, this corresponds to recursive tail-call optimization). The next links in each actor indicate where to resume the search for the next leaf. If the actor references a leaf, a result value is sent to the customer with the leaf value and a reference to the actor to ask for the next leaf.

var collector = function collector(fringe) {
    return function collectBeh(leaf) {  // leaf = { value:, next: } | {}
        if (leaf.value) {
            this.behavior = collector(fringe.concat([ leaf.value ]));
            leaf.next(this.self);
        } else {
            console.log(fringe);  // display final collection
        }
    };
};

We can demonstrate the actor-based fringe stream-generator by providing an actor to collect the results into a array. Although it would be possible to mutate the collection directly, we prefer to use a style which assumes immutable data structures. The actor’s behavior encapsulates the state of the collection, so we update the behavior with a new fringe collection value each time a new value is sent by the stream. Then we send our collector customer to the next actor, requesting the next leaf of the fringe from the generator.

var stream = sponsor(mkFringe(aTree));
var reader = sponsor(collector([]));
stream(reader);  // [ 1, 2, 3, 4 ]

With our sample definitions in place, we can construct an initial fringe generator for aTree and a collector with an initially empty array. When the fringe stream ends, the final collection of leaves is printed to the console.

Actor-per-Leaf

Our initial actor-based solution creates an actor for every node in the tree, branches and leaves. We can do better than that. We can have each actor represent the search for the next leaf and the eventual result when we find it. The changes required (highlighted below) are relatively small. Instead of creating separate actors for both right and left sub-trees, we simply update the current actor’s behavior to follow the left branch until a leaf is found. The new actors for the right branches are still chained together to remember where to continue our search.

var mkFringe = function mkFringe(tree, next) {
    return function fringeBeh(cust) {
        next = next || this.sponsor(function (cust) { cust({}); });
        if (tree instanceof Y) {
            var right = this.sponsor(mkFringe(tree.b, next));
            this.behavior = mkFringe(tree.a, right);
            this.self(cust);
        } else {
            cust({ value: tree, next: next });
        }
    };
};

Let’s consider how this version of mkFringe would traverse our sample aTree. Figure 2 shows the initial conditions. We have created a stream actor that references the top of the tree, and sent the stream a message with a customer to retrieve the first leaf.

Figure 2 – Initial Stream

When the actor representing the head of the stream receives the request for the first leaf (represented by the customer who should be sent the result), the actor recognizes that no next has been specified, so an actor is created (as next) to represent the end of the stream. Since top node of the tree is a branch, a new fringe stream actor is created for the right sub-tree, and the behavior of the current actor is updated to point to the left sub-tree (the leaf “1“). The customer is re-sent to the current actor, so it can continue searching the left sub-tree, as shown in Figure 3.

Figure 3 – Expand First Branch

When the customer message is re-received (by the first stream actor), the head of the stream now points to the leaf “1“, so this result is sent to the customer. The customer does something with the result value, then sends itself as the customer requesting the next leaf, as shown in Figure 4.

Figure 4 – After First Result

When the request for the next leaf is received (by the second stream actor), the second branch of the tree is searched. This results in the creation of an actor to represent the right sub-tree (the leaf “4“), and updates the current actor to point to the left sub-tree. Once again, the customer is re-sent to the current actor, so it can continue searching the left sub-tree, as shown in Figure 5.

Figure 5 – Expand Second Branch

Now the third branch is searched and expanded, such that the current actor points to the leaf “2” and a new actor is added pointing to the leaf “3“. One more self-delegation to the current actor sends the result (the leaf “2“) to the customer. At this point all of the fringe stream actors point to leaves of the fringe, as shown in Figure 6.

Figure 6 – Expand Third Branch

The final chain of actors represents a re-readable stream of fringe leaves. Each actor represents a unique position in the stream. Incremental creation of fringe stream actors is driven by demand for each next position. All of the work done to find the next leaf is cached for efficiency, and the work is suspended as soon as the next leaf is found.

Comparing Streams

Comparing two actor-based streams involves incrementally requesting and comparing values from each stream. A comparator actor is created and sent as the customer requesting results from both streams to be compared. It doesn’t matter which stream produces a result first, since we are only interested in determining if both results have the same value (or both end).

var comparator = function comparator(cust) {
    var initBeh = function compareBeh(r0) {  // { value:, next: } | {}
        this.behavior = function compareBeh(r1) {  // { value:, next: } | {}
            this.behavior = initBeh;
            if (r0.value === r1.value) {
                if (r0.value === undefined) {
                    cust(true);  // stream end
                } else {
                    r0.next(this.self);
                    r1.next(this.self);
                }
            } else {
                cust(false);  // mismatch
            }
        };
    };
    return initBeh;
};

The comparator function takes a final customer cust and creates a pair of actor behaviors representing a simple state-machine for comparing streams. In the initial state, the actor receives the first result r0, and updates its behavior to the inner state. In the inner state, the actor receives the second result r1. It then switches back to the initial behavior (in anticipation of the next pair of results), and compares the results received. If the result values do not match, false is sent to the final customer. If both streams ended, then they matched, so true is sent to the final customer. If the result values match, then the next pair of results are requested by sending the comparator (self) as the customer to the next of both streams.

Summary

Both functional closures and actor behaviors capture algorithm fragments that can be passed around as values and invoked (or not) whenever we choose. These mechanisms are related to continuations [5], which have been discovered in various contexts by different people. If you squint, you could view all of these as kinds of coroutine implementations. The “same fringe” problem provides a simple but challenging context in which to exercise various approaches. Comparing the solutions helps us understand the useful application of these techniques.

References

[1]

R. Gabriel. The Design of Parallel Programming Languages. http://www.dreamsongs.com/10ideas.html, 1991.

[2]

J. McCarthy. Another Samefringe. In SIGART Newsletter, No. 61, February 1977.

[3]

Various. Same Fringe Problem. http://wiki.c2.com/?SameFringeProblem, 2016-12.

[4]

Events. Node.js v7.3.0 Documentation, Retrieved 2016-12-22.

[5]

J. Reynolds. The Discoveries of Continuations. Lisp and Symbolic Computation. 6 (3/4): 233-248, 1993.

Special thanks to Tristan Slominski for JavaScript Generator examples.