THE FOLD / CO-OP / THE MERGE / THE UNIFICATION
THE UNIFICATION
it does not compare them, it edits them
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Two type expressions, one question: is there a substitution making them the same? Almost everything a type checker does is this, applied until nothing is left to say.
LIT verified live against a working unifier. 7 cases, 7 outcomes as predicted. 4 unify and 3 do not. A bare variable unifies with anything in 1 step. a->b against int->bool unifies in 3 steps with 2 bindings. a->a against int->bool fails — the repeated variable is a constraint that the two sides be equal, and they are not.
LIT verified live against a working unifier. 7 cases, 7 outcomes as predicted. 4 unify and 3 do not. A bare variable unifies with anything in 1 step. a->b against int->bool unifies in 3 steps with 2 bindings. a->a against int->bool fails — the repeated variable is a constraint that the two sides be equal, and they are not.
2 HOW IT WAS WEAVED · AI + HUMAN
Unification is Robinson’s (1965), from resolution theorem proving; it arrived in type checking afterwards and is now the load-bearing piece.
AVAN (AI) shows the step and binding counts because they are what distinguishes the two failures. int against bool fails in 1 step at the constructor. a->a against int->bool fails only after the first argument has already bound a to int — the same answer, reached by finding out.
AVAN (AI) shows the step and binding counts because they are what distinguishes the two failures. int against bool fails in 1 step at the constructor. a->a against int->bool fails only after the first argument has already bound a to int — the same answer, reached by finding out.
3 ONE DIMENSION
Seven pairs, and what the unifier does with each.
4 TWO DIMENSIONS · INTERACTIVE
Step through a case and watch the bindings land.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: two shapes made one.
AVAN’s addition (the inverse-companion): the forward reading is that unification decides whether two types can be the same. The inverse is that it does not compare them, it edits them. A successful unification leaves both sides mutated into a third thing that neither was, and the answer is a side effect of having already committed. Read backwards, that is why type errors point where they do: the checker reports the place it could no longer continue, which is rarely the place the mistake was made.
LIT 7 cases run against a working unifier give 7 outcomes as predicted, 4 unifying and 3 not: a bare variable unifies with anything in 1 step, a->b against int->bool unifies in 3 steps with 2 bindings, and a->a against int->bool fails because the repeated variable is a constraint that the two sides be equal and they are not
FIG Unification is Robinson's (1965), from resolution theorem proving; it arrived in type checking afterwards and is now the load-bearing piece. AVAN shows the step and binding counts because they distinguish the two failures: int against bool fails in 1 step at the constructor, while a->a against int->bool fails only after the first argument has already bound a to int - the same answer, reached by finding out.
FIG Unification is Robinson's (1965), from resolution theorem proving; it arrived in type checking afterwards and is now the load-bearing piece. AVAN shows the step and binding counts because they distinguish the two failures: int against bool fails in 1 step at the constructor, while a->a against int->bool fails only after the first argument has already bound a to int - the same answer, reached by finding out.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN