THE FOLD / BOSS / THE GATEKEEPER / THE OCCURS CHECK
THE OCCURS CHECK
rejected by a choice rather than by a contradiction
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Before binding a variable to a type, check that the variable does not appear inside it. Skip that one test and the unifier will happily build a type that contains itself.
LIT verified live. The expression \x. x x generates the constraint a ~ a -> b. With the occurs check the unifier rejects it — 1 rejection, and the program is a type error. Without the occurs check it succeeds, and the resulting term is cyclic: walking it hits the depth cap at 201 and printing it produces (((((((((((((... -> ...) -> t2) -> t2) .... One rule is the entire difference.
LIT verified live. The expression \x. x x generates the constraint a ~ a -> b. With the occurs check the unifier rejects it — 1 rejection, and the program is a type error. Without the occurs check it succeeds, and the resulting term is cyclic: walking it hits the depth cap at 201 and printing it produces (((((((((((((... -> ...) -> t2) -> t2) .... One rule is the entire difference.
2 HOW IT WAS WEAVED · AI + HUMAN
The occurs check is what makes unification produce finite terms; Prolog famously omits it by default for speed, and the cyclic terms are exactly what you get.
AVAN (AI) ran the same constraint through the same unifier twice with the single flag flipped, so the difference is attributable to nothing else. The depth of 201 is a cap, not a measurement — the term has no depth, which is the point.
AVAN (AI) ran the same constraint through the same unifier twice with the single flag flipped, so the difference is attributable to nothing else. The depth of 201 is a cap, not a measurement — the term has no depth, which is the point.
3 ONE DIMENSION
One constraint, one flag, two worlds.
4 TWO DIMENSIONS · INTERACTIVE
Unwind the cyclic term one level at a time.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a type inside itself.
AVAN’s addition (the inverse-companion): the forward reading is that the occurs check prevents an infinite type. The inverse is that the infinite type is perfectly coherent and some languages want it. A cyclic term is exactly what a recursive type is, and systems with equi-recursive types drop the check on purpose. Read backwards, this is not a safety rail against nonsense but a decision about which infinities are allowed to be named, and \x. x x is rejected by a choice rather than by a contradiction.
LIT the expression \x. x x generates the constraint a ~ a -> b, which the unifier rejects with the occurs check on - 1 rejection, a type error - and accepts with it off, leaving a cyclic term whose walk hits the depth cap at 201 and which prints as (((((((((((((... -> ...) -> t2) -> t2) and onward: one rule is the entire difference
FIG The occurs check is what makes unification produce finite terms; Prolog famously omits it by default for speed, and cyclic terms are exactly what you get. AVAN ran the same constraint through the same unifier twice with the single flag flipped, so the difference is attributable to nothing else. The depth of 201 is a cap, not a measurement - the term has no depth, which is the point.
FIG The occurs check is what makes unification produce finite terms; Prolog famously omits it by default for speed, and cyclic terms are exactly what you get. AVAN ran the same constraint through the same unifier twice with the single flag flipped, so the difference is attributable to nothing else. The depth of 201 is a cap, not a measurement - the term has no depth, which is the point.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN