Add a couple more identifiers to support eager rec

This will allow us to write rewrite rules that eagerly evaluate
recursion principles on the RHS.

After     | File Name                                                   | Before    || Change    | % Change
-----------------------------------------------------------------------------------------------------------
35m52.89s | Total                                                       | 35m21.19s || +0m31.69s | +1.49%
-----------------------------------------------------------------------------------------------------------
1m03.44s  | GENERATEDIdentifiersWithoutTypesProofs.vo                   | 0m52.51s  || +0m10.92s | +20.81%
0m42.76s  | UnderLetsProofs.vo                                          | 0m37.59s  || +0m05.16s | +13.75%
1m50.02s  | RewriterRulesInterpGood.vo                                  | 1m46.65s  || +0m03.37s | +3.15%
3m14.40s  | p384_32.c                                                   | 3m16.54s  || -0m02.13s | -1.08%
1m53.47s  | RewriterRulesGood.vo                                        | 1m56.16s  || -0m02.68s | -2.31%
0m34.80s  | AbstractInterpretationZRangeProofs.vo                       | 0m32.33s  || +0m02.46s | +7.63%
0m22.80s  | ExtractionOCaml/word_by_word_montgomery                     | 0m20.53s  || +0m02.26s | +11.05%
2m55.61s  | PushButtonSynthesis/WordByWordMontgomeryReificationCache.vo | 2m53.77s  || +0m01.84s | +1.05%
2m37.56s  | Fancy/Compiler.vo                                           | 2m39.51s  || -0m01.94s | -1.22%
1m47.71s  | Fancy/Barrett256.vo                                         | 1m46.42s  || +0m01.29s | +1.21%
0m59.28s  | ExtractionHaskell/word_by_word_montgomery                   | 0m57.33s  || +0m01.95s | +3.40%
0m42.71s  | LanguageInversion.vo                                        | 0m40.75s  || +0m01.96s | +4.80%
0m40.95s  | ExtractionHaskell/unsaturated_solinas                       | 0m39.76s  || +0m01.19s | +2.99%
0m32.88s  | AbstractInterpretationProofs.vo                             | 0m31.38s  || +0m01.50s | +4.78%
0m28.98s  | PushButtonSynthesis/MontgomeryReductionReificationCache.vo  | 0m27.08s  || +0m01.90s | +7.01%
0m17.39s  | PushButtonSynthesis/BarrettReductionReificationCache.vo     | 0m18.95s  || -0m01.55s | -8.23%
0m12.51s  | GENERATEDIdentifiersWithoutTypes.vo                         | 0m11.11s  || +0m01.40s | +12.60%
0m12.30s  | ExtractionOCaml/word_by_word_montgomery.ml                  | 0m13.84s  || -0m01.53s | -11.12%
0m07.16s  | ExtractionHaskell/unsaturated_solinas.hs                    | 0m05.67s  || +0m01.49s | +26.27%
0m05.84s  | ExtractionHaskell/saturated_solinas.hs                      | 0m04.84s  || +0m01.00s | +20.66%
2m01.25s  | RewriterWf2.vo                                              | 2m01.06s  || +0m00.18s | +0.15%
1m22.67s  | Rewriter.vo                                                 | 1m22.48s  || +0m00.18s | +0.23%
0m54.42s  | AbstractInterpretationWf.vo                                 | 0m55.26s  || -0m00.83s | -1.52%
0m53.40s  | RewriterInterpProofs1.vo                                    | 0m52.85s  || +0m00.54s | +1.04%
0m46.26s  | p521_32.c                                                   | 0m46.58s  || -0m00.32s | -0.68%
0m44.94s  | PushButtonSynthesis/UnsaturatedSolinasReificationCache.vo   | 0m45.20s  || -0m00.26s | -0.57%
0m40.17s  | p521_64.c                                                   | 0m39.49s  || +0m00.67s | +1.72%
0m37.93s  | Fancy/Montgomery256.vo                                      | 0m37.31s  || +0m00.61s | +1.66%
0m36.59s  | PushButtonSynthesis/UnsaturatedSolinas.vo                   | 0m36.22s  || +0m00.37s | +1.02%
0m30.06s  | ExtractionHaskell/saturated_solinas                         | 0m29.33s  || +0m00.73s | +2.48%
0m29.61s  | LanguageWf.vo                                               | 0m29.48s  || +0m00.12s | +0.44%
0m26.76s  | PushButtonSynthesis/WordByWordMontgomery.vo                 | 0m26.77s  || -0m00.00s | -0.03%
0m26.23s  | SlowPrimeSynthesisExamples.vo                               | 0m26.36s  || -0m00.12s | -0.49%
0m25.30s  | RewriterWf1.vo                                              | 0m25.47s  || -0m00.16s | -0.66%
0m20.01s  | p448_solinas_64.c                                           | 0m19.97s  || +0m00.04s | +0.20%
0m19.56s  | p256_32.c                                                   | 0m20.04s  || -0m00.48s | -2.39%
0m19.28s  | secp256k1_32.c                                              | 0m18.86s  || +0m00.42s | +2.22%
0m16.08s  | CStringification.vo                                         | 0m15.70s  || +0m00.37s | +2.42%
0m16.04s  | p434_64.c                                                   | 0m15.20s  || +0m00.83s | +5.52%
0m13.39s  | ExtractionOCaml/unsaturated_solinas                         | 0m13.13s  || +0m00.25s | +1.98%
0m09.57s  | p224_32.c                                                   | 0m08.95s  || +0m00.62s | +6.92%
0m09.27s  | ExtractionOCaml/saturated_solinas                           | 0m10.22s  || -0m00.95s | -9.29%
0m08.70s  | p384_64.c                                                   | 0m07.93s  || +0m00.76s | +9.70%
0m08.43s  | ExtractionOCaml/unsaturated_solinas.ml                      | 0m09.07s  || -0m00.64s | -7.05%
0m07.44s  | ExtractionHaskell/word_by_word_montgomery.hs                | 0m08.35s  || -0m00.90s | -10.89%
0m06.97s  | ExtractionOCaml/saturated_solinas.ml                        | 0m07.28s  || -0m00.31s | -4.25%
0m06.81s  | BoundsPipeline.vo                                           | 0m06.78s  || +0m00.02s | +0.44%
0m06.72s  | PushButtonSynthesis/SaturatedSolinasReificationCache.vo     | 0m06.85s  || -0m00.12s | -1.89%
0m05.77s  | Fancy/Prod.vo                                               | 0m06.07s  || -0m00.30s | -4.94%
0m04.06s  | MiscCompilerPassesProofs.vo                                 | 0m03.84s  || +0m00.21s | +5.72%
0m03.71s  | PushButtonSynthesis/Primitives.vo                           | 0m03.34s  || +0m00.37s | +11.07%
0m03.34s  | PushButtonSynthesis/SmallExamples.vo                        | 0m03.26s  || +0m00.08s | +2.45%
0m03.16s  | PushButtonSynthesis/SaturatedSolinas.vo                     | 0m03.22s  || -0m00.06s | -1.86%
0m03.15s  | PushButtonSynthesis/BarrettReduction.vo                     | 0m03.29s  || -0m00.14s | -4.25%
0m02.84s  | PushButtonSynthesis/MontgomeryReduction.vo                  | 0m02.90s  || -0m00.06s | -2.06%
0m02.79s  | curve25519_32.c                                             | 0m02.92s  || -0m00.12s | -4.45%
0m02.12s  | curve25519_64.c                                             | 0m02.13s  || -0m00.00s | -0.46%
0m01.70s  | secp256k1_64.c                                              | 0m01.55s  || +0m00.14s | +9.67%
0m01.64s  | p256_64.c                                                   | 0m01.23s  || +0m00.40s | +33.33%
0m01.57s  | p224_64.c                                                   | 0m01.68s  || -0m00.10s | -6.54%
0m01.36s  | Language.vo                                                 | 0m01.33s  || +0m00.03s | +2.25%
0m01.33s  | CLI.vo                                                      | 0m01.32s  || +0m00.01s | +0.75%
0m01.26s  | AbstractInterpretation.vo                                   | 0m01.25s  || +0m00.01s | +0.80%
0m01.13s  | RewriterProofs.vo                                           | 0m01.18s  || -0m00.05s | -4.23%
0m01.13s  | StandaloneOCamlMain.vo                                      | 0m01.04s  || +0m00.08s | +8.65%
0m01.10s  | CompilersTestCases.vo                                       | 0m01.16s  || -0m00.05s | -5.17%
0m01.04s  | StandaloneHaskellMain.vo                                    | 0m01.18s  || -0m00.13s | -11.86%
0m00.76s  | MiscCompilerPasses.vo                                       | 0m00.74s  || +0m00.02s | +2.70%
0m00.60s  | PushButtonSynthesis/LegacySynthesisTactics.vo               | 0m00.66s  || -0m00.06s | -9.09%
0m00.46s  | UnderLets.vo                                                | 0m00.48s  || -0m00.01s | -4.16%
0m00.44s  | PushButtonSynthesis/ReificationCache.vo                     | 0m00.52s  || -0m00.08s | -15.38%

1 files changed, 54 insertions, 0 deletions

diff --git a/src/Language.v b/src/Language.v
index 52c340d18..695073248 100644
--- a/src/Language.v
+++ b/src/Language.v
@@ -877,7 +877,11 @@ Module Compilers.
         | bool_rect {T:base.type} : ident ((unit -> T) -> (unit -> T) -> bool -> T)
         | nat_rect {P:base.type} : ident ((unit -> P) -> (nat -> P -> P) -> nat -> P)
         | nat_rect_arrow {P Q:base.type} : ident ((P -> Q) -> (nat -> (P -> Q) -> (P -> Q)) -> nat -> P -> Q)
+        | eager_nat_rect {P:base.type} : ident ((unit -> P) -> (nat -> P -> P) -> nat -> P)
+        | eager_nat_rect_arrow {P Q:base.type} : ident ((P -> Q) -> (nat -> (P -> Q) -> (P -> Q)) -> nat -> P -> Q)
         | list_rect {A P:base.type} : ident ((unit -> P) -> (A -> list A -> P -> P) -> list A -> P)
+        | eager_list_rect {A P:base.type} : ident ((unit -> P) -> (A -> list A -> P -> P) -> list A -> P)
+        | eager_list_rect_arrow {A P Q:base.type} : ident ((P -> Q) -> (A -> list A -> (P -> Q) -> (P -> Q)) -> list A -> P -> Q)
         | list_case {A P:base.type} : ident ((unit -> P) -> (A -> list A -> P) -> list A -> P)
         | List_length {T} : ident (list T -> nat)
         | List_seq : ident (nat -> nat -> list nat)
@@ -1057,8 +1061,16 @@ Module Compilers.
                => fun O_case S_case => Datatypes.nat_rect _ (O_case tt) S_case
              | nat_rect_arrow P Q
                => fun O_case S_case => Datatypes.nat_rect _ O_case S_case
+             | eager_nat_rect P
+               => fun O_case S_case => Datatypes.nat_rect _ (O_case tt) S_case
+             | eager_nat_rect_arrow P Q
+               => fun O_case S_case => Datatypes.nat_rect _ O_case S_case
              | list_rect A P
                => fun N_case C_case => Datatypes.list_rect _ (N_case tt) C_case
+             | eager_list_rect A P
+               => fun N_case C_case => Datatypes.list_rect _ (N_case tt) C_case
+             | eager_list_rect_arrow A P Q
+               => fun N_case C_case => Datatypes.list_rect _ N_case C_case
              | list_case A P
                => fun N_case C_case => ListUtil.list_case _ (N_case tt) C_case
              | List_length T => @List.length _
@@ -1149,6 +1161,7 @@ Module Compilers.
     Notation LiteralNat := (@Literal base.type.nat).
     Notation LiteralZRange := (@Literal base.type.zrange).
     Definition literal {T} (v : T) := v.
+    Definition eagerly {T} (v : T) := v.
 
     (** TODO: MOVE ME? *)
     Module Thunked.
@@ -1291,6 +1304,25 @@ Module Compilers.
         | @Thunked.nat_rect ?T
           => let rT := base.reify T in
              then_tac (@ident.nat_rect rT)
+        | eagerly (@Datatypes.nat_rect) ?T0 ?P0
+          => lazymatch (eval cbv beta in T0) with
+             | fun _ => _ -> _ => else_tac ()
+             | fun _ => ?T => reify_rec (eagerly (@Thunked.nat_rect) T (fun _ : Datatypes.unit => P0))
+             | T0 => else_tac ()
+             | ?T' => reify_rec (eagerly (@Datatypes.nat_rect) T' P0)
+             end
+        | eagerly (@Datatypes.nat_rect) ?T0
+          => lazymatch (eval cbv beta in T0) with
+             | (fun _ => ?P -> ?Q)
+               => let rP := base.reify P in
+                  let rQ := base.reify Q in
+                  then_tac (@ident.eager_nat_rect_arrow rP rQ)
+             | T0 => else_tac ()
+             | ?T' => reify_rec (eagerly (@Datatypes.nat_rect) T')
+            end
+        | eagerly (@Thunked.nat_rect) ?T
+          => let rT := base.reify T in
+             then_tac (@ident.eager_nat_rect rT)
         | @Datatypes.list_rect ?A ?T0 ?Pnil
           => lazymatch (eval cbv beta in T0) with
             | fun _ => ?T => reify_rec (@Thunked.list_rect A T (fun _ : Datatypes.unit => Pnil))
@@ -1301,6 +1333,27 @@ Module Compilers.
           => let rA := base.reify A in
              let rT := base.reify T in
              then_tac (@ident.list_rect rA rT)
+        | eagerly (@Datatypes.list_rect) ?A ?T0 ?Pnil
+          => lazymatch (eval cbv beta in T0) with
+             | fun _ => _ -> _ => else_tac ()
+             | fun _ => ?T => reify_rec (eagerly (@Thunked.list_rect) A T (fun _ : Datatypes.unit => Pnil))
+             | T0 => else_tac ()
+             | ?T' => reify_rec (eagerly (@Datatypes.list_rect) A T' Pnil)
+             end
+        | eagerly (@Datatypes.list_rect) ?A ?T0
+          => lazymatch (eval cbv beta in T0) with
+             | (fun _ => ?P -> ?Q)
+               => let rA := base.reify A in
+                  let rP := base.reify P in
+                  let rQ := base.reify Q in
+                  then_tac (@ident.eager_list_rect_arrow rA rP rQ)
+             | T0 => else_tac ()
+             | ?T' => reify_rec (eagerly (@Datatypes.list_rect) A T')
+             end
+        | eagerly (@Thunked.list_rect) ?A ?T
+          => let rA := base.reify A in
+             let rT := base.reify T in
+             then_tac (@ident.eager_list_rect rA rT)
         | @ListUtil.list_case ?A ?T0 ?Pnil
           => lazymatch (eval cbv beta in T0) with
             | fun _ => ?T => reify_rec (@Thunked.list_case A T (fun _ : Datatypes.unit => Pnil))
@@ -1398,6 +1451,7 @@ Module Compilers.
           => let rA := base.reify A in
              then_tac (@ident.None rA)
         | ZRange.Build_zrange => then_tac ident.Build_zrange
+        | eagerly (?f ?x) => reify_rec (eagerly f x)
         | fancy.interp ?idc
           => let ridc := (eval cbv [to_fancy] in (to_fancy idc)) in
              then_tac ridc