Formalizing OCaml GADT typing in Coq
summary
Mechanization of OCaml GADT typing in Coq formalizes ambivalent-type principality and proves subject reduction for a graph-based encoding; implementation exposes and fixes a concrete ambiguity bug where applying a function under competing equalities yields different result types. Uses Coq proofs, a graph representation of types, explicit witness-elimination rules and GC of unreachable nodes to detect ambivalence. Claims: soundness of ambivalence relative to local unification, mechanized subject reduction, and groundwork toward a Coq proof of principality and soundness for OCaml GADT inference using graph types.
AI-written summary · about