Rocq formalisation of section 3 (The Logic of Recipes) and of the first lemmas of section 4 (Verification Condition Generation) of the Coma paper, TOPLAS 48(3), 2026, by Andrei Paskevich, Paul Patault and Jean-Christophe Filliâtre. There is an extended version on HAL.
Code on codeberg, coqdoc here.
Everything from 3.1 to 3.11 is proved. Same for appendix F up to F.4.
Axioms: functional extensionality, and the rules on
valid. These rules are a module type (Recipes_valid_sig)
and have a model in Prop (Recipes_valid_model).
Main prints the
definitions, the statements and the axioms they use.
| paper | Rocq |
|---|---|
| 3.1 | logical_relation_lemma |
| 3.2, ⟦ ⟧ is defined on complete recipes | eval_def |
| 3.3 | neuneug |
| 3.4, 3.5 | entails_refl,
entails_trans |
| 3.6 | entails_36 |
| 3.7, fusion is a meet | fusion_meet |
| 3.8, 3.9 | cross_lemma,
entails_neu |
| 3.10 | l_3_10 |
| D.1 | d1 |
| 3.11, jokers | joker_entails |
typing of VC, implicit in the paper |
has_type_VC |
| F.1 | VC_hsubst, VC_ren |
| F.2 (4.1), the null VC is neutral | VC_neutral |
| F.3 | VC_notnot |
| F.4 (4.4), the full VC is a meet | VC_meet,
VC_split |
In dependency order, roughly:
Recipes: syntax
(with Autosubst), neu, weight, depth, orderRecipes_typingRecipes_stacks:
s ∘ lRecipes_logrel,
Recipes_directly_box,
Recipes_box_rel:
logical relations, and the induction on boxed subrecipesRecipes_eval: ⟦ ·
⟧, existence and uniquenessRecipes_evalf:
evaluation with fuel, extracted to OCaml (in file Extraction)Recipes_neuneu:
3.3 to 3.6Recipes_fusion:
3.7 to 3.10Recipes_joker:
jokers, appendix D, lemma 3.11Coma: syntax,
typing and reduction of ComaVCgen:
VC, uniform properties, F.1 to F.4We use de Bruijn indices for both recipes and terms.
For a functional signature, the logical relation asks the argument to be related under every renaming of its term variables.
The cover relation of appendix D counts the term binders crossed:
under k binders, a box contains the recipe of the stack
shifted by k. The paper does not have to say it
explicitely.
We also need the two quantifier rules on valid in de
Bruijn form.
In Sec. 4, a property holds uniformly when it holds under every recipe substitution and every term substitution (the paper only asks for the former).
The recipe of a handler definition is ∀h. λπ. where the
paper has λπ. ∀h..
autosubst_lib is copied from the Autosubst
gallery.
I used Claude (Anthropic) to help write this website and the README.