Anti-unification, part 4

All right, let's implement this thing. We'll start with a few caveats:

• In the previous post I worked an example on function calls; in this code, we'll do the algorithm on syntax trees. Hopefully it is obvious that they're equivalent.
• As I prefer, I'll work with immutable data structures whenever possible.
• This code is intended to illustrate the concepts; there are numerous places where it could be made faster or more memory-efficient. Those are left as exercises.
• There's a small amount of boilerplate code because I want value equality on immutable trees. It's irritating to write, but we'll do it.
• WordPress turns quotation marks into "smart quotes" automatically and I don't remember how to turn it off. VEXING.

Let's get through the boring code quickly in this episode, and then we can look in more detail at the algorithm proper in the next episode. As often is the case, if we get the boring boilerplate infrastructure right, then the algorithm reads very clearly.

I want to be able to make new, unique "holes"; a class that is purpose-built to count off numbers is useful for that. I'm unlikely to have two billion holes, so the fact that it wraps around is irrelevant; I could always swap it out for longs if I had to.

internal sealed class Counter
{
private int count = 0;
public int Next()
{
int current = count;
count += 1;
return current;
}
}

Yes I know that ++ exists. I do not like that thing.

I originally thought that I'd make a "substitution" type that is logically a Tree, Tree tuple, but then I realized that the only time I use substitutions is when looking them up in a collection of substitutions. I'll therefore just use an immutable dictionary from trees to trees as my collection of substitutions, and the key-value pair as my substitution.

using Substitutions =
System.Collections.Immutable.ImmutableDictionary<Tree, Tree>;
internal static class Extensions
{
public static string LineSeparated(this Substitutions s)
=> string.Join("\n",
s.Select(kv => $"{kv.Value}/{kv.Key}"));
}

All right. Let's get through the boring parts of making an immutable syntax tree that has value equality. We'll say that a tree is characterized by three things: it has a kind, it has a value, and it has any number of ordered children. We'll store the children in an array but ensure that it is never exposed and hence never mutated.

internal sealed class Tree
{
public string Kind { get; }
public string Value { get; }
private readonly Tree[] children;
public IEnumerable<Tree> Children =>
this.children.Select(c => c);
public int ChildCount => this.children.Length;
public Tree(string kind, string value, params Tree[] children)
: this(kind, value, (IEnumerable<Tree>)children)
{ }
public Tree(
string kind, string value, IEnumerable<Tree> children)
{
this.Kind = kind;
this.Value = value;
this.children = children.ToArray();
}
public static bool operator ==(Tree a, Tree b) =>
ReferenceEquals(a, b) || !(a is null) && a.Equals(b);
public static bool operator !=(Tree a, Tree b) => !(a == b);
public override bool Equals(object obj) =>
obj is Tree t &&
t.Kind == this.Kind &&
t.Value == this.Value &&
t.Children.SequenceEqual(this.Children);
public override int GetHashCode() =>
HashCode.Combine(this.Kind, this.Value,
this.children.Aggregate(0, HashCode.Combine));

I am loving the "is" patterns but C# really needs a !is null or a is not null or something like that. This !(a is null) is ugly. Of course I cannot use a != null - do you see why? I'd have to use ReferenceEquals. There is an opportunity here for a more general feature of "match the negation of this pattern".

Printing out trees is straightforward; we'll just print them out in their function call form:

public override string ToString() =>
this.ChildCount == 0 ?
this.Value :
$"{this.Value}({string.Join<Tree>(',', this.children)})";

Given a substitution, what is the tree after the substitution is applied?

public Tree Substitute(Tree original, Tree replacement) =>
this == original ?
replacement :
new Tree(this.Kind, this.Value, this.Children.Select(
e => e.Substitute(original, replacement)));

Easy peasy. Finally, I want a factory for holes:

private static readonly Counter counter = new Counter();
public static Tree MakeHole() =>
new Tree("hole", $"h{counter.Next()}");

And that does it for the boring boilerplate code.

Next time on FAIC: let's implement anti-unification for real.