Samefringe

[masak]

Let's define a (binary) Tree as being either a Node or a Leaf. In current 007, we can create and inspect trees like this:

func makeNode(left, right) {
    return { left, right };
}

func isNode(o) {
    return o ~~ Dict && o.has("left") && o.has("right");
}

In Awesome Future 007, I'd like to be able to write it like this:

type Tree<T> = T | Node<T>;

class Node<T> {
    constructor(@public left: Tree<T>, @public right: Tree<T>) {
    }
}

func isNode<T>(o) {
    return o ~~ Node<T>;
}

But never mind, the former version works today, so let's go with that.

Now we can form trees that are distinct but have the same fringe, that is, the same preorder traversal of leaf nodes:

#   .
#  / \
# 1   .
#    / \
#   2   3
my tree1 = makeNode(1, makeNode(2, 3));

#     .
#    / \
#   .   3
#  / \
# 1   2
my tree2 = makeNode(makeNode(1, 2), 3);

Computing the actual fringe of a tree, in order to compare it against another fringe, is straightforward.

func fringe(tree) {
    if isNode(tree) {
        return fringe(tree.left).concat(fringe(tree.right));
    }
    else {
        return [tree];
    }
}

The two trees are shown to have the same fringe.

say(fringe(tree1));        # [1, 2, 3]
say(fringe(tree2));        # [1, 2, 3]
say(fringe(tree1) == fringe(tree2));    # True

Whereas a tree having exactly the same shape as tree2 but a different value in one of the leaves does not have the same fringe.

#     .
#    / \
#   .   3
#  / \
# 1   7
my tree3 = makeNode(makeNode(1, 7), 3);

say(fringe(tree2) == fringe(tree3));

And we're done.

---

Except we're not really done, because (quoting Rosetta Code)

[...] an elegant solution is one that can perform the minimum amount of work to falsify the equivalence of the fringes when they differ somewhere in the middle, short-circuiting the unnecessary additional traversals and comparisons.

The challenge, if you ask me, is to both get the above minimum-work elegance, while also retaining a simple, understandable structure in the program.

Here's how I would like to write the solution, again in Wishful Thinking 007:

func sameFringe(tree1, tree2) {
    return all(fringe(tree1) Z== fringe(tree2));
}

I cannot imagine a shorter, more elegant solution to the problem than the above, not without starting to drop detail. But there are a number of assumptions here:

• all() would take something iterable and returns the first falsy value if any, or True.
• fringe(node) cannot be the eager variant implemented above. Instead it needs to be a coroutine:

func* fringe(tree) {
    if isNode(tree) {
        yield* concat(fringe(tree.left), fringe(tree.right));
    }
    else {
        yield tree;
    }
}

(I've borrowed JavaScript's syntax with the star. Python manages to do this without the star. Similarly, the yield* keyword, also from JavaScript, is short for for <expr> -> v { yield v; }.)

• Finally, the existence of the zip metaoperator is assumed here. This operator is also lazy, making the whole sameFringe function evaluate only the minimum necessary. (I originally wrote it as »==«, but the hyperoperator is not lazy.)

• One difference to Perl 6's Z== is that we don't want to truncate on the length of the shortest operand; instead if one is shorter than the other, we want to return False. A hybrid between Z== and Python's zip_longest would be ideal here. (Much later edit: although, thinking about it, the "stop at shortest" strategy is the natural one. Perhaps better to extend the two sequences with a freshly-unique stopper?)

---

I'm not super-sure what's the conclusion here. I think we should add all that laziness and iterables into 007, since we're heading there anyway. Long-term, I think we should have coroutines/yield, also, mostly because since we already have upwards funargs first-class closures, the mechanism for having coroutines is mostly there already.

I'm curious what the limits are to statically optimizing a line of code such as all(fringe(tree1) Z== fringe(tree2)). Ideally I would have it set up two generators, pull them in a while loop, and return False as soon as it found a discrepancy. What, pray tell, would prevent the inlining of Z== and all() to make that happen?

Going to close this issue immediately though, because it was more of an exploration of ideas anyway. Might be good to have it linkable in the future.

---

Here, as a parting gift, I was able to put together a lazy solution using Today Working 007, by porting a Scheme implementation using continuation-passing style that I found on Ward's Wiki:

func lazyFlatten(tree) {
    func helper(tree, tailCont) {
        if isNode(tree) {
            return helper(tree.left, func() { helper(tree.right, tailCont) });
        }
        else {
            return [tree, tailCont];
        }
    }
    return helper(tree, func() { return None; });
}

func streamEqual(stream1, stream2) {
    if stream1 == none && stream2 == none {
        return True;
    }
    else if stream1 ~~ Array && stream2 ~~ Array && stream1[0] == stream2[0] {
        return streamEqual(stream1[1](), stream2[1]());
    }
    else {
        return False;
    }
}

func sameFringe(tree1, tree2) {
    return streamEqual(lazyFlatten(tree1), lazyFlatten(tree2));
}

lazyFlatten is kinda similar to a coroutine fringe, and streamEqual is basically all and Z== in spirit. The callbacks and tuplesarrays constitute the inelegance in the shape of poor man's coroutines.

But it works!

---

Further reading:

• SameFringeProblem at Ward's Wiki
• The Design of Parallel Programming Languages, linked from the above wiki page. The naive solution presented first is equivalent to the naive solution presented first here.
• Same Fringe at Rosetta Code
• Scheme: An Interpreter for Extended Lambda Calculus has two implementations of SAMEFRINGE on page 9

[masak]

Coming back to this musing much later, I now think expressing the solution (slightly longer) as a for loop ought to be not just desirable, but perfectly natural:

That is, instead of this code:

func sameFringe(tree1, tree2) {
    return all(fringe(tree1) Z== fringe(tree2));
}

We'd write this code:

func sameFringe(tree1, tree2) {
    for zip(fringe(tree1), fringe(tree2)) -> [n1, n2] {
        if n1 != n2 {
            return false;
        }
    }
    return true;
}

Where zip (akin to Python) takes a bunch of iterables and returns an iterator, but (unlike Python) there's some accommodation for it not stopping at the shortest input iterable.

I like to use for here to express "we're going to step through a bunch of things"; it's a natural fit, and the fact that any iterable can be plugged into the statement form (and not just, say, arrays) only makes it more fitting. On the other hand, the original solution's all and Z== could arguably be seen as a more "declarative" form of the same solution, soaking up the slight boilerplate of the for solution in the form of "if we find a counterexample, return false immediately; otherwise return true at the end".

All of this was triggered by reading the code at the top of page 268 of this paper. It just occurred to me how nice it would be for a language to be general enough to just be able to plug its for loop into any desired concrete traversal strategy. Oddly enough, this is true of Java (as well as a number of other modern languages), but it seems to be very underappreciated.

[masak]

Although I do seem to be stuck in an annoying oscillation between explicit step-by-step thinking and descriptive/declarative verbs — when I look at that for loop, my brain goes "hey! that's a sequential all idiom waiting to be collapsed!"...

[masak]

Bob Nystrom has a blog post called Iteration Inside and Out where he talks about "interleaving two sequences" (using internal iterators, described in the blog post):

Back so soon? How’d it go? How much time did you waste?

Right. As far as I can tell, you simply can't solve this problem using internal iterators unless you’re willing to reach for some heavy weaponry like threads or continuations. You’re up a creek sans paddle.

This is, I think, a big reason why most mainstream languages do external iterators. Sure, the tree example was verbose, but at least it was possible. (It’s also probably why languages that do internal iterators also have continuations.)

Change the final "continuations" to "coroutines", and I agree; that's what makes the above solutions nice.

The paper On the Dynamic Extent of Delimited Continuations uses samefringe as a motivating example to explore different strategies (some of them using delimited continuations) for traversal.

[masak]

Here's how I would like to write the solution, again in Wishful Thinking 007:

func sameFringe(tree1, tree2) {
    return all(fringe(tree1) Z== fringe(tree2));
}

I cannot imagine a shorter, more elegant solution to the problem than the above, not without starting to drop detail.

Hello past me, this is future me. I can imagine a shorter, more elegant solution:

func sameFringe(tree1, tree2) {
    return fringe(tree1) == fringe(tree2);
}

Where fringe produces a generator which lazily spits out leaf node values, and == is overloaded on two generators to frugally pull out elements and compare them pointwise.

Yes, there is a "playing with fire" element in there, in that == is not well-defined in general on such generators. (If both generators keep generating identical elements without bound, the comparison will diverge instead of ever returning true.) But that's not an issue in this particular sameFringe function, because we're assuming finite trees, and so all fringe generators will be finite, too. We're being lax in stating or including a proof of that in the program. Maybe it's worth a sentence or two in a comment.

The all and Z== in the original solution were concessions to the generator-y nature of the values. But it's perfectly valid to smooth over those differences, and to let either static typing and overloading sort that out, or some kind of dynamic dispatch. Python allows list values to be compared with == using the obvious pointwise semantics; the code above does the same, but with generators, which is just as sensible.