THE FOLD / LOOT / THE VAULT / THE PARAMETRICITY
THE PARAMETRICITY
bought by making the function blind
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A function that must work for every type cannot look at its argument. That single restriction is so strong that for some types it leaves exactly one function that could possibly exist.
LIT verified live by exhaustive search. Every function on a carrier of 2 values — all 4 of them — and of 3 values — all 27 — tested for naturality against every function on that carrier. forall a. a -> a has exactly 1 inhabitant at both sizes: the identity. forall a. a -> a -> a has exactly 2: the two projections. The type named them.
LIT verified live by exhaustive search. Every function on a carrier of 2 values — all 4 of them — and of 3 values — all 27 — tested for naturality against every function on that carrier. forall a. a -> a has exactly 1 inhabitant at both sizes: the identity. forall a. a -> a -> a has exactly 2: the two projections. The type named them.
2 HOW IT WAS WEAVED · AI + HUMAN
Parametricity is Reynolds’ (1983); Wadler’s “Theorems for free” is the reading where the type alone yields a proof about every function of that type.
AVAN (AI) first tested naturality against the cyclic permutation only and got 2 inhabitants for a -> a, because swap commutes with itself. A parametric function commutes with every function on the carrier, not only the bijections — and it is the constant functions that rule swap out. The corrected sweep gives 1.
AVAN (AI) first tested naturality against the cyclic permutation only and got 2 inhabitants for a -> a, because swap commutes with itself. A parametric function commutes with every function on the carrier, not only the bijections — and it is the constant functions that rule swap out. The corrected sweep gives 1.
3 ONE DIMENSION
Every function on the carrier, and the few that survive.
4 TWO DIMENSIONS · INTERACTIVE
Watch each candidate tested and eliminated.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a shape with one way to be filled.
AVAN’s addition (the inverse-companion): the forward reading is that a polymorphic type constrains what a function can do. The inverse is that the constraint is ignorance, and it is the ignorance doing the work. The identity is the only inhabitant precisely because a function that cannot inspect its argument has nothing to decide with. Read backwards, a free theorem is not knowledge the type system gained — it is what remains provable once you guarantee the code was never told anything, and every one of these results is bought by making the function blind.
LIT every function on a carrier of 2 values - all 4 - and of 3 values - all 27 - tested for naturality against every function on that carrier leaves forall a. a -> a with exactly 1 inhabitant at both sizes, the identity, and forall a. a -> a -> a with exactly 2, the two projections
FIG Parametricity is Reynolds' (1983); Wadler's Theorems for free is the reading where the type alone yields a proof about every function of that type. AVAN first tested naturality against the cyclic permutation only and got 2 inhabitants for a -> a, because swap commutes with itself. A parametric function commutes with EVERY function on the carrier, not only the bijections - the constant functions rule swap out - and the corrected sweep gives 1.
FIG Parametricity is Reynolds' (1983); Wadler's Theorems for free is the reading where the type alone yields a proof about every function of that type. AVAN first tested naturality against the cyclic permutation only and got 2 inhabitants for a -> a, because swap commutes with itself. A parametric function commutes with EVERY function on the carrier, not only the bijections - the constant functions rule swap out - and the corrected sweep gives 1.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN