Rocoma

Rocoma

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.

Status

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

Files

In dependency order, roughly:

Differences with the paper

We 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..

Licence

autosubst_lib is copied from the Autosubst gallery.

Use of AI

I used Claude (Anthropic) to help write this website and the README.