File ‹grammar_rel.ML›

(* Author: Basil Fürer *)

(* the definitions behind a grammar, continued: the inductive relation family
   (one definition per strongly connected component) with its language theorem;
   Grammar_Defs is the whole package, the grammar constant and the decoders
   coming from Grammar_Decoders (grammar_defs.ML) *)

signature GRAMMAR_DEFS =
sig
  val define_grammar:
    Grammar_Common.grammar -> local_theory ->
      (term * thm) * local_theory
  val define_const: bool -> binding * binding * term -> local_theory ->
    (term * thm) * local_theory

  type semantics =
   {gram:       term * thm,
    preds:      (string * term) list,
    decs:       (string * term) list,
    intros:     thm list,
    inducts:    thm list,
    sound_thms: thm list}

  val decoder_of: Proof.context -> Grammar_Common.grammar -> string -> term
  val define_decoders:
    Grammar_Common.grammar -> local_theory ->
      (string * term) list * local_theory

  val is_indent_insensitive: Grammar_Common.grammar -> bool
  val components: Grammar_Common.grammar -> string list list
  val prove_family: Proof.context ->
    {comps: ((string * term) list * thm) list, prod_lhss: string list, insensitive: bool,
     wordT: typ, carrier_of: string -> typ, norm: term -> term} ->
    (string -> term -> term -> term -> term) -> (Proof.context -> int -> tactic) ->
    (string * thm) list

  val lookup_rel: Proof.context -> Grammar_Common.grammar ->
    Grammar_Common.rel_info option

  val define_relation:
    Grammar_Common.grammar -> term * thm -> (string * term) list ->
      local_theory -> semantics * local_theory

  val define_relation_of:
    xstring * Position.T -> local_theory ->
      semantics * local_theory
end;

structure Grammar_Defs: GRAMMAR_DEFS =
struct

open Grammar_Common Grammar_Decoders;

(** relation: mutual inductive family, one predicate per nonterminal and one
    intro per production; indentation-insensitive grammars (every annotation
    const‹Any›) drop the indentation argument,
    ‹G_A :: tword ⇒ τA ⇒ bool› **)

fun is_indent_insensitive (gram: Grammar_Common.grammar) =
  forall (fn {rhs, ...}: Grammar_Common.prod => forall (fn (_, a) => a = Any) rhs)
    (#prods gram);

fun ch_span_typ chT = Type (type_name‹TIGER_Token.span_ext›, [chT, typ‹unit›]);

(* ‹⦇tok = t, span = sp, … = m⦈›: the relation quantifies over the record
   extension ‹m› of every token, so it is stated for any client extension *)
fun mk_token_ext tokT chT moreT =
  let val tokenT = Type (type_name‹TIGER_Token.token_ext›, [tokT, chT, moreT]) in
    Const (const_name‹TIGER_Token.token.token_ext›,
      tokT --> ch_span_typ chT --> moreT --> tokenT)
  end;

fun col_rel_term _ Grammar_Common.Any = NONE
  | col_rel_term (segK, seg1) rel =
  let
    val nat_less = Const (const_name‹Orderings.less›, typ‹nat› --> typ‹nat› --> HOLogic.boolT);
    val nat_leq = Const (const_name‹Orderings.less_eq›, typ‹nat› --> typ‹nat› --> HOLogic.boolT);
  in SOME
    (case rel of
      Grammar_Common.Eq => HOLogic.mk_eq (segK, seg1)
    | Grammar_Common.Ge => nat_leq $ seg1 $ segK
    | Grammar_Common.Gt => nat_less $ seg1 $ segK
    | Grammar_Common.Any => raise Match)
  end;

(* the strongly connected components of the nonterminals, a component after
   the components it refers to; the nonterminals of a component in the order
   of the grammar *)
fun components (gram: Grammar_Common.grammar) =
  let
    val nnames = map fst (Grammar_Common.nonterms_list gram);
    val succs =
      fold (fn {lhs, rhs, ...} =>
          Symtab.map_default (lhs, [])
            (fold (fn (Grammar_Common.RN B, _) => insert (op =) B | _ => I) rhs))
        (#prods gram) Symtab.empty;
    fun succ A = these (Symtab.lookup succs A);
    (* Tarjan: a component is complete after all components reachable from it *)
    val counter = Unsynchronized.ref 0;
    val index = Unsynchronized.ref Symtab.empty;
    val low = Unsynchronized.ref Symtab.empty;
    val stack = Unsynchronized.ref ([]: string list);
    val on_stack = Unsynchronized.ref Symtab.empty;
    val comps = Unsynchronized.ref ([]: string list list);
    fun get tab A = the (Symtab.lookup (! tab) A);
    fun lower v k = low := Symtab.update (v, Int.min (get low v, k)) (! low);
    fun visit v =
      let
        val _ = index := Symtab.update (v, ! counter) (! index);
        val _ = low := Symtab.update (v, ! counter) (! low);
        val _ = counter := ! counter + 1;
        val _ = stack := v :: ! stack;
        val _ = on_stack := Symtab.update (v, ()) (! on_stack);
        val _ =
          succ v |> List.app (fn w =>
            if not (Symtab.defined (! index) w) then (visit w; lower v (get low w))
            else if Symtab.defined (! on_stack) w then lower v (get index w)
            else ());
        fun pop acc =
          (case ! stack of
            w :: rest =>
              (stack := rest; on_stack := Symtab.delete_safe w (! on_stack);
               if w = v then w :: acc else pop (w :: acc))
          | [] => raise Fail "components: stack");
      in if get low v = get index v then comps := pop [] :: ! comps else () end;
    val _ = List.app (fn v => if Symtab.defined (! index) v then () else visit v) nnames;
  in map (fn c => filter (member (op =) c) nnames) (rev (! comps)) end;

(* An induction rule whose cases also assume the bodies of predicates of lower
   components: a case premise pred_B args, B defined earlier, is followed by
   body_B args, as if B were in the component and the premise its induction
   hypothesis.  lowers: the predicates of the lower components, the body
   proposition of their arguments, and their lemmas pred_B args ⟹ body_B args *)
fun strengthen_induct ctxt arity lowers th =
  let
    val (prop, ctxt1) =
      Variable.import_terms true [Envir.beta_norm (Thm.prop_of th)] ctxt |>> the_single;
    fun lower_body H =
      (case try HOLogic.dest_Trueprop H of
        NONE => NONE
      | SOME t =>
          let
            val (h, args) = strip_comb t;
            val m = length args;
          in
            if m < arity then NONE
            else
              let val (pargs, xargs) = chop (m - arity) args in
                get_first (fn (pt, mk, _) =>
                    if list_comb (h, pargs) aconv pt then SOME (mk xargs) else NONE)
                  lowers
              end
          end);
    fun strengthen_case c =
      let
        val vs = Term.strip_all_vars c;
        val (names, _) = Variable.variant_fixes (map #1 vs) ctxt1;
        val frees = map2 (fn nm => fn (_, T) => Free (nm, T)) names vs;
        val b = Term.subst_bounds (rev frees, Term.strip_all_body c);
        val hs = Logic.strip_imp_prems b;
        val hs' = maps (fn h => h :: the_list (lower_body h)) hs;
      in
        if length hs' = length hs then c
        else fold_rev Logic.all frees (Logic.list_implies (hs', Logic.strip_imp_concl b))
      end;
    val cases = map strengthen_case (Logic.strip_imp_prems prop);
    val lower_ths = map #3 lowers;
    fun tac {context, prems} =
      HEADGOAL (resolve_tac context [th])
      THEN EVERY (prems |> map (fn c =>
        HEADGOAL (resolve_tac context [c] THEN_ALL_NEW
          (assume_tac context ORELSE'
            (resolve_tac context lower_ths THEN' assume_tac context)))));
  in
    Goal.prove_sorry ctxt1 [] cases (Logic.strip_imp_concl prop) tac
    |> singleton (Variable.export ctxt1 ctxt)
  end;

(* the family's induction rules on the mutual statements, one per component

     (pred1 i w x ⟶ body1 i w x) ∧ … ∧ (predn i w x ⟶ bodyn i w x)

   split into one implication per nonterminal; insensitive grammars fix i at 0.
   The components come with their induction rules, lower components first;
   case_tac k proves the case of production k (in the order of prod_lhss) *)
fun prove_family ctxt {comps, prod_lhss, insensitive, wordT, carrier_of, norm} body case_tac =
  let
    val zero = term‹0 :: nat›;
    val arity = if insensitive then 2 else 3;
    fun body_prop A args =
      HOLogic.mk_Trueprop (norm
        (case args of
          [w, x] => body A zero w x
        | [i, w, x] => body A i w x
        | _ => raise Fail "prove_family: predicate arguments"));
    fun prove_comp (preds, induct) lowers =
      let
        val n = length preds;
        val fresh =
          Variable.variant_fixes
            (maps (fn k =>
                (if insensitive then [] else ["ii" ^ string_of_int k]) @
                ["ww" ^ string_of_int k, "xx" ^ string_of_int k]) (0 upto n - 1)) ctxt
          |> fst;
        fun chunks [] = []
          | chunks xs = let val (a, b) = chop arity xs in a :: chunks b end;
        fun conj_of ((A, pred), names) =
          let
            val (i_t, w_n, x_n) =
              if insensitive then (zero, nth names 0, nth names 1)
              else (Free (nth names 0, HOLogic.natT), nth names 1, nth names 2);
            val w = Free (w_n, wordT);
            val x = Free (x_n, carrier_of A);
            val pred_app = if insensitive then pred $ w $ x else pred $ i_t $ w $ x;
          in HOLogic.mk_imp (pred_app, body A i_t w x) end;
        val prop =
          norm (HOLogic.mk_Trueprop
            (foldr1 HOLogic.mk_conj (map conj_of (preds ~~ chunks fresh))));
        fun P_of (A, _) =
          let
            val i = Free ("__i", HOLogic.natT);
            val w = Free ("__w", wordT);
            val x = Free ("__x", carrier_of A);
            val lam = Term.lambda w (Term.lambda x (body A (if insensitive then zero else i) w x));
          in norm (if insensitive then lam else Term.lambda i lam) end;
        (* the predicate variables: P for a single predicate, P1, …, Pn otherwise *)
        fun p_index nm =
          if nm = "P" then SOME 0
          else if String.isPrefix "P" nm then Int.fromString (unprefix "P" nm)
          else NONE;
        val p_vars =
          Term.add_vars (Thm.prop_of induct) []
          |> filter (is_some o p_index o #1 o #1)
          |> sort (int_ord o apply2 (the o p_index o #1 o #1));
        val _ =
          if length p_vars = n then ()
          else raise Fail "prove_family: predicate variables of the induction rule";
        val insts = map2 (fn (v, _) => fn pr => (v, Thm.cterm_of ctxt (P_of pr))) p_vars preds;
        val induct' =
          Drule.infer_instantiate ctxt insts induct
          |> not (null lowers) ? strengthen_induct ctxt arity lowers;
        val names = map fst preds;
        val idxs =
          map_filter (fn (k, A) => if member (op =) names A then SOME k else NONE)
            (map_index I prod_lhss);
        (* the production cases in parallel (on a large grammar, in the one state of the
           induction: 879 s of the relation's 1136 s; now 13 s) *)
        fun cases_tac context =
          Grammar_Common.timed ctxt "prove_family"
            (string_of_int (length idxs) ^ " production cases of " ^ space_implode " " names)
            (Grammar_Common.PARALLEL_CASES (map (fn k => K (case_tac context k)) idxs) 1);
        fun tac {context, ...} =
          (if n = 1 then
             HEADGOAL (resolve_tac context @{thms impI})
             THEN HEADGOAL (eresolve_tac context [induct'])
           else HEADGOAL (resolve_tac context [induct']))
          THEN cases_tac context;
        val th = Goal.prove_sorry ctxt fresh [] prop tac;
        fun conjunct k =
          let val rest = funpow k (fn t => @{thm conjunct2} OF [t]) th
          in if k = n - 1 then rest else @{thm conjunct1} OF [rest] end;
      in names ~~ map (fn k => conjunct k RS @{thm mp}) (0 upto n - 1) end;
    fun step (comp as (preds, _)) (lowers, results) =
      let
        val ths = prove_comp comp lowers;
        val lowers' = map2 (fn (A, pt) => fn (_, th) => (pt, body_prop A, th)) preds ths;
      in (lowers @ lowers', results @ ths) end;
  in #2 (fold step comps ([], [])) end;

(** relation families of registered grammars: created with the grammar in its
    artifacts, added later (define_relation_of) in this table, keyed by the
    grammar constant **)

fun gram_key (arts: Grammar_Common.artifacts) =
  (case Term.head_of (#gram_t arts) of
    Const (c, _) => c
  | _ => raise Fail "gram_key: grammar term without head constant");

structure Rel_Data = Generic_Data
(
  type T = Grammar_Common.rel_info Symtab.table;
  val empty = Symtab.empty;
  fun merge data = Symtab.merge (K true) data;
);

fun lookup_rel ctxt (gram: Grammar_Common.grammar) =
  (case #artifacts gram of
    NONE => NONE
  | SOME arts =>
      (case #rel arts of
        SOME ri => SOME ri
      | NONE => Symtab.lookup (Rel_Data.get (Context.Proof ctxt)) (gram_key arts)));

fun store_rel (gram: Grammar_Common.grammar) (ri: Grammar_Common.rel_info) =
  let val key = gram_key (Grammar_Common.artifacts_of gram) in
    Local_Theory.declaration {syntax = false, pervasive = false, pos = Position.none}
      (fn phi =>
        Rel_Data.map (Symtab.update (key, Grammar_Common.morph_rel_info phi ri)))
  end;

fun gen_define_relation gram_t gram_th (gram: Grammar_Common.grammar) lthy =
  let
    val {chT, moreT, wordT, tokenT, isgT, symT, ptreeT, ...} = Grammar_Common.get_desc gram;
    val {name = gram_b, prods, tokT, ...} = gram;
    val nts = Grammar_Common.nonterms_list gram;
    val nnames = map fst nts;
    val carriers = map (#carrier o snd) nts;
    val carrier_of = Grammar_Common.carrier_of gram;

    val ch_spanT = ch_span_typ chT;
    val token_ext_c = mk_token_ext tokT chT moreT;
    val app_c = Const (const_name‹List.append›, wordT --> wordT --> wordT);
    val col_of_c = Const (const_name‹col_of›, wordT --> HOLogic.natT);
    val classify = classify_of gram;
    val insensitive = is_indent_insensitive gram;

    val pred_bindings = map (fn nm => suffix_bind ("_" ^ Grammar_Common.ident_in gram nm) gram_b) nnames;
    (* the flat relation names can collide across grammars (G with A_B and
       G_A with B both give G_A_B) *)
    val _ =
      pred_bindings |> List.app (fn b =>
        if Sign.declared_const (Proof_Context.theory_of lthy) (Local_Theory.full_name lthy b)
        then error ("grammar " ^ quote (Binding.name_of gram_b) ^ ": the relation constant " ^
          quote (Binding.name_of b) ^ " already exists (another grammar / nonterminal \
          \pair produces the same name); rename the grammar or the nonterminal" ^
          Position.here (Binding.pos_of gram_b))
        else ());
    val pred_types =
      map (fn cT =>
             (if insensitive then wordT --> cT --> HOLogic.boolT
              else HOLogic.natT --> wordT --> cT --> HOLogic.boolT))
        carriers;
    val pred_specs = map2 (fn b => fn T => ((b, T), NoSyn)) pred_bindings pred_types;
    val pred_frees =
      map2 (fn b => fn T => Free (Binding.name_of b, T)) pred_bindings pred_types;
    fun pred_of A = nth pred_frees (find_index (curry (op =) A) nnames);

    fun mk_token tok sp m = token_ext_c $ tok $ sp $ m;
    fun singleton_word tok sp m = HOLogic.mk_list tokenT [mk_token tok sp m];

    fun concat_words [] = HOLogic.mk_list tokenT []
      | concat_words [w] = w
      | concat_words (w :: ws) = app_c $ w $ concat_words ws;

    fun intro_meta ({rhs, ...}: Grammar_Common.prod) =
      let
        val classified = map (fn (s, a) => (classify s, a)) rhs;
        val fresh_names =
          (if insensitive then [] else ["i"]) @
            maps (fn (NTc _, _) =>
                    (if insensitive then ["v", "w"] else ["v", "w", "j"])
                   | (ClassTm _, _) => ["sp", "m"]
                   | (LitTm _, _) => ["sp", "m"]) classified;
        val (names, _) = Variable.variant_fixes fresh_names lthy;
        val (i_name, child_names) =
          if insensitive then ("", names) else (hd names, tl names);
        fun distribute [] [] = []
          | distribute ((NTc A, r) :: cs) (v :: w :: rest) =
              if insensitive then
                (NTc A, r, [v, w]) :: distribute cs rest
              else
                (case rest of
                  j :: ns => (NTc A, r, [v, w, j]) :: distribute cs ns
                | _ => raise Fail "intro_meta: distribute NT")
          | distribute ((ClassTm t, r) :: cs) (sp :: m :: ns) =
              (ClassTm t, r, [sp, m]) :: distribute cs ns
          | distribute ((LitTm t, r) :: cs) (sp :: m :: ns) =
              (LitTm t, r, [sp, m]) :: distribute cs ns
          | distribute _ _ = raise Fail "intro_meta: distribute";
      in (i_name, distribute classified child_names) end;

    fun intro_prop (prod as {lhs, action, ...}: Grammar_Common.prod) =
      let
        val (i_name, assigned) = intro_meta prod;
        val i_term_opt =
          if insensitive then NONE
          else SOME (Free (i_name, typ‹nat›));

        fun seg (NTc _, _, v_w_j) = Free (nth v_w_j 1, wordT)
          | seg (ClassTm tok, _, [sp, m]) =
              singleton_word tok (Free (sp, ch_spanT)) (Free (m, moreT))
          | seg (LitTm tok, _, [sp, m]) =
              singleton_word tok (Free (sp, ch_spanT)) (Free (m, moreT))
          | seg _ = raise Fail "intro_prop: seg";
        val segments = map seg assigned;
        val full_word = concat_words segments;

        fun arg_of (NTc A, _, v_w_j) =
              SOME (Free (nth v_w_j 0, carrier_of A))
          | arg_of (ClassTm tok, _, [sp, m]) =
              SOME (mk_token tok (Free (sp, ch_spanT)) (Free (m, moreT)))
          | arg_of (LitTm _, _, _) = NONE
          | arg_of _ = raise Fail "intro_prop: arg_of";
        val args = map_filter arg_of assigned;
        (* ‹@span›: the span of the production's word, the action's first argument *)
        val span_args =
          if #span prod then
            [Const (const_name‹word_span›, wordT --> ch_spanT) $ full_word]
          else [];
        val value_term = Term.betapplys (action, span_args @ args);

        val nt_prems =
          if insensitive then
            map_filter (fn (NTc A, _, [v, w]) =>
                          SOME (pred_of A $ Free (w, wordT) $ Free (v, carrier_of A))
                         | _ => NONE) assigned
          else
            map_filter (fn (NTc A, _, [v, w, j]) =>
                          SOME (pred_of A $ Free (j, typ‹nat›)
                                          $ Free (w, wordT)
                                          $ Free (v, carrier_of A))
                        | _ => NONE) assigned;
        val col_prems =
          if insensitive then []
          else
            (case i_term_opt of NONE => [] | SOME i_term =>
              map_filter (fn (elem, segK) =>
                  (case elem of
                    (NTc _, ann, [_, _, j]) =>
                      col_rel_term (Free (j, typ‹nat›), i_term) ann
                  | (ClassTm _, ann, _) =>
                      col_rel_term (col_of_c $ segK, i_term) ann
                  | (LitTm _, ann, _) =>
                      col_rel_term (col_of_c $ segK, i_term) ann
                  | _ => NONE))
                (assigned ~~ segments));
        val concl =
          case i_term_opt of
            NONE => pred_of lhs $ full_word $ value_term
          | SOME i_term => pred_of lhs $ i_term $ full_word $ value_term;
      in
        ground_tvars
          (Logic.list_implies
            (map HOLogic.mk_Trueprop (nt_prems @ col_prems),
             HOLogic.mk_Trueprop concl))
      end;

    fun timed label f x = Grammar_Common.timed lthy (Binding.name_of gram_b) label f x;

    val intro_props =
      timed "build intro_props" (fn () =>
        map_index (fn (p, prod) =>
          let val nm = "intro_" ^ Grammar_Common.ident_in gram (#lhs prod) ^ "_" ^ string_of_int p in
            ((Binding.name nm, []), intro_prop prod)
          end) prods) ();

    val add_flags: Inductive.flags =
      {quiet_mode = true, verbose = false, alt_name = Binding.empty,
       coind = false, no_elim = false, no_ind = false, skip_mono = false};

    (* one inductive definition per strongly connected component, lower
       components first: the inductive package is quadratic in the number of
       introduction rules of one definition.  Later intros refer to the
       predicates defined before. *)
    val comps = components gram;
    fun nt_index A = find_index (curry (op =) A) nnames;
    fun define_comp comp (defined, lthy) =
      let
        val idxs =
          map_filter (fn (k, p: Grammar_Common.prod) =>
              if member (op =) comp (#lhs p) then SOME k else NONE)
            (map_index I prods);
        val intros =
          map (fn k => nth intro_props k |> apsnd (Term.subst_free defined)) idxs;
        val specs = map (nth pred_specs o nt_index) comp;
        val label =
          "add_inductive " ^ space_implode " " comp ^ " (" ^ string_of_int (length comp) ^
            " nonterminals, " ^ string_of_int (length idxs) ^ " intros)";
        val (res, lthy') =
          timed label
            (with_concealed (Inductive.add_inductive add_flags specs [] intros [])) lthy;
        val defined' = defined @ (map pred_of comp ~~ #preds res);
      in ((comp, idxs, res), (defined', lthy')) end;
    val (comp_results, (_, lthy)) =
      timed unchecked_name‹Inductive.add_inductive› (fold_map define_comp comps) ([], lthy);

    (* the predicates, and the intros and inducts in the order of the grammar *)
    val pred_tab =
      fold (fn (comp, _, res) => fold2 (curry Symtab.update) comp (#preds res))
        comp_results Symtab.empty;
    fun pred_of A = the (Symtab.lookup pred_tab A);
    val all_intrs =
      fold (fn (_, idxs, res) => fold2 (curry Inttab.update) idxs (#intrs res))
        comp_results Inttab.empty
      |> Inttab.dest |> map #2;
    val all_inducts =
      let
        val tab =
          fold (fn (comp, _, res) => fold2 (curry Symtab.update) comp (#inducts res))
            comp_results Symtab.empty;
      in map (the o Symtab.lookup tab) nnames end;

    val cleanup =
      Simplifier.full_simplify
        (put_simpset HOL_basic_ss lthy
         |> fold Simplifier.add_simp
            (@{thms append.simps col_of_Nil col_of_Cons} @ @{thms token.simps}));

    val cleaned_intros =
      timed "cleanup intros" (map cleanup) all_intrs;

    val cleaned_inducts =
      timed "cleanup inducts" (map cleanup) all_inducts;

    (** cornerstone lemmas: relate the mutual predicate family to wf_ptree **)
    val prootT = HOLogic.mk_prodT (symT, HOLogic.natT);
    val wf_ptree_c = Const (const_name‹wf_ptree›, isgT --> ptreeT --> HOLogic.boolT);
    val proot_c = Const (const_name‹proot›, ptreeT --> prootT);
    val pyield_c = Const (const_name‹pyield›, ptreeT --> wordT);
    val Nt_c = Const (const_name‹Nt›, Grammar_Common.name_typ gram --> symT);

    (* ∃pt. wf_ptree G pt ∧ proot pt = (Nt A, i) ∧ pyield pt = w *)
    fun sound_body_of A i_t w_t =
      HOLogic.mk_exists ("pt", ptreeT,
        HOLogic.mk_conj (wf_ptree_c $ gram_t $ Bound 0,
          HOLogic.mk_conj
            (HOLogic.mk_eq (proot_c $ Bound 0,
                            HOLogic.mk_prod (Nt_c $ Grammar_Common.name_term gram A, i_t)),
             HOLogic.mk_eq (pyield_c $ Bound 0, w_t))));

    (* sound direction. prove the mutual conjunction
      ‹(pred1 i w x ⟶ body1 i w) ∧ … ∧ (predn i w x ⟶ bodyn i w)› *)
    val ptreeListT = HOLogic.listT ptreeT;
    val PNode_c = Const (const_name‹PNode›,
      Grammar_Common.name_typ gram --> HOLogic.natT --> ptreeListT --> ptreeT);
    val PLeaf_c = Const (const_name‹PLeaf›, tokenT --> ptreeT);


    val sound_simps =
      @{thms proot.simps pyield.simps list.map(1) list.map(2)
             list.set(1) list.set(2) list.inject list.distinct
             concat.simps append.simps append_Nil2 append_assoc
             col_of_Nil col_of_Cons
             list_all2_Nil list_all2_Cons irel_sat.simps
             wf_leaf is_cfg.make_def is_cfg.select_convs token.select_convs
             HOL.simp_thms fst_conv snd_conv insert_iff empty_iff
             prod.inject sym.inject sym.distinct char.inject};

    (* iprods G = [p0, …]: membership in the productions is decided on
       this list, without unfolding the grammar constant elsewhere *)
    fun iprods_info_of () =
      let
        val gram_rhs =
          (case Thm.prop_of gram_th of
            Const (const_name‹Pure.eq›, _) $ _ $ r => r
          | t => snd (HOLogic.dest_eq (HOLogic.dest_Trueprop t)));
        val ps =
          (case gram_rhs of
            _ $ ps $ _ $ _ => ps
          | _ => raise Fail "iprods_info: grammar constant");
        val iprods_c =
          Const (const_name‹iprods›, fastype_of gram_t --> fastype_of ps);
        val iprods_eq =
          Goal.prove_sorry lthy [] [] (HOLogic.mk_Trueprop (HOLogic.mk_eq (iprods_c $ gram_t, ps)))
            (fn {context, ...} =>
              HEADGOAL (simp_only context
                (@{thms is_cfg.make_def is_cfg.select_convs} @ [gram_th])));
      in (ps, iprods_c, iprods_eq) end;
    val iprods_info = timed "iprods equation" (try iprods_info_of) ();

    (* (A, rhs) ∈ set (iprods G) for each production, by walking the list of
       productions: simp on the unfolded grammar compares the production with
       all others, quadratic in the number of productions *)
    fun prod_mems_of (ps, _, iprods_eq) =
      let
        val fold_iprods =
          HOLogic.Trueprop_conv (Conv.arg_conv (Conv.arg_conv
            (Conv.rewr_conv (Thm.symmetric (mk_meta_eq iprods_eq)))));
        fun tails ct =
          (case Thm.term_of ct of
            Const (const_name‹Nil›, _) => []
          | _ => ct :: tails (Thm.dest_arg ct));
        val tls = tails (Thm.cterm_of lthy ps);
        (* instantiated without unification: each step only compares the
           premise with the previous step's conclusion *)
        val prodT =
          (case fastype_of ps of
            Type (type_name‹list›, [T]) => T
          | _ => raise Fail "prod_mems: productions");
        val cT = Thm.ctyp_of lthy prodT;
        val listT = HOLogic.listT prodT;
        val mem_hd = Thm.instantiate' [SOME cT] [] @{lemma ‹x ∈ set (x # xs)› by simp};
        val mem_tl =
          Thm.instantiate' [SOME cT] [] @{lemma ‹x ∈ set xs ⟹ x ∈ set (y # xs)› by simp};
        fun inst th insts =
          Thm.instantiate (TVars.empty,
            Vars.make (map (fn ((n, T), ct) => (((n, 0), T), ct)) insts)) th;
        (* x ∈ set (tls ! j) for the head x of tls ! k, j ≤ k *)
        fun mem k =
          let
            val tl_k = nth tls k;
            val x = Thm.dest_arg1 tl_k;
            val th0 = inst mem_hd [(("x", prodT), x), (("xs", listT), Thm.dest_arg tl_k)];
            fun up j th =
              if j < 0 then th
              else
                let val tl_j = nth tls j in
                  up (j - 1)
                    (Thm.implies_elim
                      (inst mem_tl
                        [(("x", prodT), x), (("y", prodT), Thm.dest_arg1 tl_j),
                         (("xs", listT), Thm.dest_arg tl_j)])
                      th)
                end;
          in Conv.fconv_rule fold_iprods (up (k - 1) th0) end;
      in map_index (fn (k, _) => try mem k) prods end;
    val prod_mems =
      timed "production memberships"
        (the_default (map (K NONE) prods) o Option.mapPartial (try prod_mems_of)) iprods_info;

    fun sound_case_tac ctxt ((prod: Grammar_Common.prod, (i_name, assigned)), prod_mem) =
      let
        val nt_count =
          length (filter (fn (NTc _, _, _) => true | _ => false) assigned);
        val rhs_hol = Grammar_Ptree_Induct.rhs_term gram prod;

        val elim_step =
          REPEAT_DETERM_N nt_count (HEADGOAL (eresolve_tac ctxt [@{thm exE}])) THEN
          HEADGOAL (REPEAT_DETERM o eresolve_tac ctxt [@{thm conjE}]);

        val focus = Subgoal.FOCUS_PARAMS (fn {params, context, ...} =>
          let
            val name_map = map (apsnd Thm.term_of) params;
            fun get n =
              (case AList.lookup (op =) name_map n of
                SOME t => t
              | NONE => raise Fail ("sound_case: missing param " ^ n));
            val n_params = length name_map;
            val pt_terms =
              List.drop (name_map, n_params - nt_count) |> map snd;
            val i_t = if insensitive then term‹0 :: nat› else get i_name;
            fun mk_children [] _ = []
              | mk_children ((NTc _, _, _) :: rest) (pt :: pts_rest) =
                  pt :: mk_children rest pts_rest
              | mk_children ((ClassTm t, _, [sp, m]) :: rest) pts_rest =
                  (PLeaf_c $ mk_token t (get sp) (get m)) :: mk_children rest pts_rest
              | mk_children ((LitTm t, _, [sp, m]) :: rest) pts_rest =
                  (PLeaf_c $ mk_token t (get sp) (get m)) :: mk_children rest pts_rest
              | mk_children _ _ = raise Fail "sound_case: mk_children";
            val children = mk_children assigned pt_terms;
            val pts_hol = HOLogic.mk_list ptreeT children;
            val witness =
              PNode_c $ Grammar_Common.name_term gram (#lhs prod) $ i_t $ pts_hol;
            val (exI_inst, wf_node_inst) =
              Grammar_Ptree_Induct.node_intros context
                {witness = witness, rhs = rhs_hol, pts = pts_hol};
            fun solved st = if Thm.nprems_of st = 0 then all_tac st else no_tac st;
            val by_mem =
              (case prod_mem of
                SOME th =>
                  HEADGOAL (resolve_tac context [th])
                  THEN ALLGOALS (simp_only context sound_simps) THEN solved
              | NONE => no_tac);
          in
            HEADGOAL (resolve_tac context [exI_inst])
            THEN HEADGOAL (resolve_tac context [@{thm conjI}])
            THEN HEADGOAL (resolve_tac context [wf_node_inst])
            THEN (by_mem ORELSE ALLGOALS (simp_only context (sound_simps @ [gram_th])))
          end) ctxt;

      in elim_step THEN HEADGOAL focus end;

    val prods_meta = map (fn p => (p, intro_meta p)) prods;

    val sound_thms =
      timed "prove sound_conj" (fn () =>
        prove_family lthy
          {comps = map (fn (comp, _, res) => (map (fn A => (A, pred_of A)) comp, #induct res))
             comp_results,
           prod_lhss = map #lhs prods, insensitive = insensitive,
           wordT = wordT, carrier_of = carrier_of, norm = ground_tvars}
          (fn A => fn i_t => fn w => fn _ => sound_body_of A i_t w)
          (fn ctxt => fn k => sound_case_tac ctxt (nth prods_meta k, nth prod_mems k))
        |> (fn ths => map (the o AList.lookup (op =) ths) nnames)) ();

    val (_, lthy) =
      timed "Local_Theory.notes (intros + inducts)"
        (Local_Theory.notes
          [((qualify_bind gram_b "intros", []),  [(cleaned_intros, [])]),
           ((qualify_bind gram_b "inducts", []),  [(cleaned_inducts, [])])]) lthy;

    (* completeness for each NT ‹Ak›:
      ‹wf_ptree G pt ⟹ fst (proot pt) = Nt Ak ⟶ (∃x. predk [snd (proot pt)] (pyield pt) x)›. *)

    val gram_folded_th = Local_Defs.unfold lthy @{thms is_cfg.make_def} gram_th;

    val snd_root_c = Const (const_name‹snd›, prootT --> HOLogic.natT);

    (* body_A pt: ‹∃x. predA [snd (proot pt)] (pyield pt) x› *)
    fun complete_body_of A pt_t =
      let val cT = carrier_of A in
        HOLogic.mk_exists ("x", cT,
          if insensitive
          then pred_of A $ (pyield_c $ pt_t) $ Bound 0
          else pred_of A $ (snd_root_c $ (proot_c $ pt_t))
                        $ (pyield_c $ pt_t) $ Bound 0)
        |> ground_tvars
      end;

    val intros_rev = rev cleaned_intros;

    (* production cases of the root-indexed induction (Grammar_Ptree_Induct): the
       selector equations rewrite the conclusion and the induction hypotheses
       to the bodies *)
    fun complete_prod0_tac ctxt sel_eqs k =
      SELECT_GOAL (unfold_tac ctxt @{thms prod.inject}) THEN'
      eresolve_tac ctxt @{thms conjE} THEN'
      Hypsubst.hyp_subst_tac_thin false ctxt THEN'
      simp_only ctxt (sel_eqs @ @{thms list_all2_Nil pyield.simps list.map concat.simps}) THEN'
      resolve_tac ctxt @{thms exI} THEN'
      resolve_tac ctxt [nth intros_rev k];

    fun complete_prod1_tac ctxt sel_eqs k =
      SELECT_GOAL (unfold_tac ctxt @{thms prod.inject sym.inject fst_conv}) THEN'
      REPEAT_ALL_NEW (ematch_tac ctxt @{thms conjE}) THEN'
      Hypsubst.hyp_subst_tac_thin true ctxt THEN'
      SELECT_GOAL (unfold_tac ctxt @{thms list_all2_Cons1 list_all2_Nil}) THEN'
      (REPEAT_DETERM o ematch_tac ctxt @{thms exE conjE}) THEN'
      SELECT_GOAL (unfold_tac ctxt @{thms fst_conv snd_conv sym.inject sym.distinct}) THEN'
      (REPEAT_DETERM o ematch_tac ctxt @{thms exE}) THEN'
      SELECT_GOAL (Local_Defs.fold_tac ctxt [gram_folded_th]) THEN'
      Hypsubst.hyp_subst_tac_thin true ctxt THEN'
      simp_only ctxt (sel_eqs @ @{thms sym.inject sym.distinct simp_thms}) THEN'
      Subgoal.FOCUS_PARAMS (fn {context = ctxt', ...} =>
        (REPEAT_DETERM o HEADGOAL)
          (dresolve_tac ctxt' @{thms wf_ptree_Tm_leaf}
           THEN' assume_tac ctxt')
        THEN (REPEAT_DETERM o HEADGOAL) (eresolve_tac ctxt' @{thms exE conjE})
        THEN HEADGOAL
          (simp_only ctxt'
             @{thms pyield.simps list.map concat.simps append.simps append_Nil2})
        (* a unit self-loop (A = A) is closed by the simp step already *)
        THEN COND (has_fewer_prems 1) all_tac
         (HEADGOAL
            (Subgoal.FOCUS_PARAMS (fn {params = ps, ...} =>
               (HEADGOAL o EVERY')
                 (map (fn (_, ct) => EqSubst.eqsubst_tac ctxt' [0]
                   [infer_instantiate' ctxt' [SOME ct] @{thm token.surjective}])
                   (* the token parameters only *)
                   (filter (fn (_, ct) =>
                      (case Thm.typ_of_cterm ct of
                        Type (type_name‹TIGER_Token.token_ext›, _) => true
                      | _ => false)) ps)))
               ctxt')
          THEN (REPEAT_DETERM o HEADGOAL)
            (eresolve_tac ctxt' @{thms exE conjE impE[OF _ refl]})
          THEN HEADGOAL
            (simp_only ctxt' @{thms token.simps}
             THEN' (Hypsubst.hyp_subst_tac_thin true ctxt' ORELSE' K all_tac)
             THEN' resolve_tac ctxt' @{thms exI})
          THEN HEADGOAL
            (resolve_tac ctxt' [nth intros_rev k]
             THEN_ALL_NEW (assume_tac ctxt' ORELSE'
               (simp_only ctxt' @{thms irel_sat.simps proot.simps snd_conv}
                THEN_ALL_NEW assume_tac ctxt'))))) ctxt;

    fun complete_prod_tac ctxt sel_eqs (k, prod: Grammar_Common.prod) =
      if null (#rhs prod)
      then complete_prod0_tac ctxt sel_eqs k
      else complete_prod1_tac ctxt sel_eqs k;

    (* (A, rhs) ∈ set (iprods G) ≡ A = A0 ∧ rhs = rhs0 ∨ …, derived on the
       list of productions, so that the node case does not unfold the grammar
       constant: every production case would carry it *)
    fun mem_iprods_iff_of (_, iprods_c, iprods_eq) =
      let
        val prodT =
          (case range_type (fastype_of iprods_c) of
            Type (type_name‹list›, [T]) => T
          | _ => raise Fail "mem_iprods_iff: productions");
        val (a_T, rhs_T) = HOLogic.dest_prodT prodT;
        val (a_n, rhs_n) =
          (case Variable.variant_fixes ["A", "rhs"] lthy |> fst of
            [a, b] => (a, b)
          | _ => raise Fail "mem_iprods_iff");
        val set_c =
          Const (const_name‹set›, HOLogic.listT prodT --> HOLogic.mk_setT prodT);
        val mem_t =
          HOLogic.mk_mem (HOLogic.mk_prod (Free (a_n, a_T), Free (rhs_n, rhs_T)),
            set_c $ (iprods_c $ gram_t));
        val ss =
          put_simpset HOL_basic_ss lthy
            |> Simplifier.add_simps @{thms list.set insert_iff singleton_iff empty_iff prod.inject};
        val eq =
          (Conv.arg_conv (Conv.arg_conv (Conv.rewr_conv (mk_meta_eq iprods_eq)))
            then_conv Simplifier.rewrite ss) (Thm.cterm_of lthy mem_t);
      in
        Goal.prove_sorry lthy [a_n, rhs_n] [] (Thm.prop_of eq)
          (fn {context, ...} => HEADGOAL (resolve_tac context [eq]))
      end;
    val mem_iprods_iff =
      timed "membership disjunction" (Option.mapPartial (try mem_iprods_iff_of)) iprods_info;

    (* the node case: the conclusion to ‹P A (PNode A i pts)›, the membership
       to a disjunction over the productions, one case each *)
    fun complete_node_tac ctxt sel_eqs =
      simp_only ctxt @{thms proot.simps fst_conv sym.inject simp_thms}
      THEN' (case mem_iprods_iff of
              SOME th => simp_only ctxt (th :: @{thms prod.inject sym.inject})
            | NONE =>
                simp_only ctxt
                  (@{thms prod.inject sym.inject
                          is_cfg.make_def is_cfg.select_convs list.set
                          insert_iff singleton_iff empty_iff}
                   @ [gram_th]))
      THEN' REPEAT_ALL_NEW (eresolve_tac ctxt @{thms disjE[OF disj_commute[THEN iffD1]]})
      THEN' eresolve_tac ctxt @{thms FalseE}
      THEN' Grammar_Common.PARALLEL_CASES (map_index (complete_prod_tac ctxt sel_eqs) (rev prods));

    val complete_of =
      timed "prove complete_conj" (fn () =>
        Grammar_Ptree_Induct.prove lthy
          {gram_t = ground_tvars gram_t, ptreeT = ground_typ ptreeT, tokT = ground_typ tokT,
           nameT = Grammar_Common.name_typ gram, name = Grammar_Common.name_term gram,
           bodies = map (fn A => (A, complete_body_of A)) nnames}
          complete_node_tac) ();

    val start = #start gram;
    val start_lit = Grammar_Common.name_term gram start;
    val zero_nat = term‹0 :: nat›;
    val istart_c = Const (const_name‹istart›, isgT --> Grammar_Common.name_typ gram);
    val istart_ind_c = Const (const_name‹istart_ind›, isgT --> HOLogic.natT);

    val gram_simp = Local_Defs.unfold lthy @{thms is_cfg.make_def} gram_th;

    val istart_eq_prop =
      HOLogic.mk_Trueprop (HOLogic.mk_eq (istart_c $ gram_t, start_lit));
    val istart_eq_th =
      Goal.prove_sorry lthy [] [] istart_eq_prop
        (fn {context, ...} =>
           HEADGOAL (asm_full_simp_tac
             (context |> Simplifier.add_simps [gram_simp])));

    val istart_ind_eq_prop =
      HOLogic.mk_Trueprop (HOLogic.mk_eq (istart_ind_c $ gram_t, zero_nat));
    val istart_ind_eq_th =
      Goal.prove_sorry lthy [] [] istart_ind_eq_prop
        (fn {context, ...} =>
           HEADGOAL (asm_full_simp_tac
             (context |> Simplifier.add_simps [gram_simp])));

    val start_idx = find_index (curry (op =) start) nnames;
    val sound_start = nth sound_thms start_idx;
    val complete_start = timed "project start" complete_of start;

    val start_carrier = carrier_of start;
    val lang_th =
      let
        val (lang_fresh, lthy_gen) =
          Variable.variant_fixes ["w_lang"] lthy;
        val w_nm = hd lang_fresh;
        val w_v = Free (w_nm, wordT);
        val pred_start = pred_of start;
        val ex_body =
          HOLogic.mk_exists ("x", start_carrier,
             if insensitive then pred_start $ w_v $ Bound 0
             else pred_start $ zero_nat $ w_v $ Bound 0);

        val ilang_c =
          Const (const_name‹ilang›, isgT --> HOLogic.mk_setT wordT);
        val mem_body = HOLogic.mk_mem (w_v, ilang_c $ gram_t);
        val prop =
          HOLogic.mk_Trueprop (HOLogic.mk_eq (ex_body, mem_body))
          |> ground_tvars;
        val lang_simps =
          (gram_simp :: istart_eq_th :: istart_ind_eq_th ::
            @{thms ilang_iff_ast ast_of_def});
        val complete_folded =
          Local_Defs.fold lthy @{thms atomize_imp} complete_start;

        val bridge_focus = Subgoal.FOCUS (fn {context = ctxt', prems, ...} =>
          let
            fun is_root_eq th =
              (case Thm.concl_of th of
                Const (const_name‹Trueprop›, _) $
                  (Const (const_name‹HOL.eq›, _) $
                     (Const (const_name‹proot›, _) $ _) $ _) => true
              | _ => false);
            fun is_wf th =
              (case Thm.concl_of th of
                Const (const_name‹Trueprop›, _) $
                  (Const (const_name‹wf_ptree›, _) $ _ $ _) => true
              | _ => false);
            val root_eq = the (find_first is_root_eq prems);
            val wf_prem = the (find_first is_wf prems);
            val fst_eq =
              (root_eq RS @{thm fstI})
              |> Local_Defs.unfold ctxt' [istart_eq_th];
            val snd_eq =
              (root_eq RS @{thm sndI})
              |> Local_Defs.unfold ctxt' [istart_ind_eq_th];
            val bridged =
              (complete_folded OF [wf_prem, fst_eq])
              |> Local_Defs.unfold ctxt' [snd_eq];
          in HEADGOAL (resolve_tac ctxt' [bridged]) end);
        val backward_step =
          eresolve_tac lthy_gen [@{thm lang_of_complete}]
          THEN' bridge_focus lthy_gen;
        val raw_th =
          timed "prove lang" (fn () =>
            Goal.prove_sorry lthy_gen [] [] prop
              (fn {context, ...} =>
                 HEADGOAL (resolve_tac context [@{thm iffI}])
                 (*Forward: ‹∃x. pred w x ⟹ w ∈ ilang G›.*)
                 THEN HEADGOAL (eresolve_tac context [@{thm exE}])
                 THEN HEADGOAL (dresolve_tac context [sound_start])
                 THEN HEADGOAL (asm_full_simp_tac
                   (context |> Simplifier.add_simps lang_simps))
                 (*Backward: ‹w ∈ ilang G ⟹ ∃x. pred w x›.*)
                 THEN HEADGOAL backward_step)) ();
      in singleton (Proof_Context.export lthy_gen lthy) raw_th end;

    val (_, lthy) =
      timed "Local_Theory.notes (lang)"
        (Local_Theory.notes
          [((qualify_bind gram_b "lang", []), [([lang_th], [])])]) lthy;

  in (map (fn A => (A, pred_of A)) nnames, cleaned_intros, cleaned_inducts, sound_thms, lthy)
  end;


(** public entry: grammar + relation + theorem
    (grammar constant and decoders are reused when already defined) **)

type semantics =
 {gram:       term * thm,
  preds:      (string * term) list,
  decs:       (string * term) list,
  intros:     thm list,
  inducts:    thm list,
  sound_thms: thm list};

fun semantics_of (arts: Grammar_Common.artifacts) (ri: Grammar_Common.rel_info)
    : semantics =
  {gram = (#gram_t arts, #gram_def arts), decs = #decs arts,
   preds = #preds ri, intros = #intros ri,
   inducts = #inducts ri, sound_thms = #sound_thms ri};

fun rel_info_of ({preds, intros, inducts, sound_thms, ...}: semantics)
    : Grammar_Common.rel_info =
  {preds = preds, intros = intros,
   inducts = inducts, sound_thms = sound_thms};

(* the relation family of an elaborated grammar; the grammar constant, its
   definition and the decoders are passed in *)
fun define_relation (gram: Grammar_Common.grammar) (gram_t, gram_th) decs lthy =
  let
    fun timed label f x = Grammar_Common.timed lthy (Binding.name_of (#name gram)) label f x;
    val (preds, intros, inducts_ths, sound_ths, lthy) =
      timed "gen_define_relation" (gen_define_relation gram_t gram_th gram) lthy;
  in
    ({gram = (gram_t, gram_th), preds = preds,
      decs = decs, intros = intros, inducts = inducts_ths,
      sound_thms = sound_ths}, lthy)
  end;

(* add a relation family to a registered grammar; idempotent *)
fun define_relation_of name_ref lthy =
  let
    val (_, gram) = Grammar_Common.check_grammar lthy name_ref;
    val arts = Grammar_Common.artifacts_of gram;
  in
    (case lookup_rel lthy gram of
      SOME ri => (semantics_of arts ri, lthy)
    | NONE =>
        let
          val (sem, lthy) =
            define_relation gram (#gram_t arts, #gram_def arts) (#decs arts) lthy;
          val lthy = store_rel gram (rel_info_of sem) lthy;
        in (sem, lthy) end)
  end;

end;