val flatten_correct (#a: Type) (m: cm a) (am: amap a) (e: exp)
    : Lemma (mdenote m am e == xsdenote m am (flatten e))
let rec flatten_correct (#a:Type) (m:cm a) (am:amap a) (e:exp) :
    Lemma (mdenote m am e == xsdenote m am (flatten e)) =
  match e with
  | Unit | Atom _ -> ()
  | Mult e1 e2 -> flatten_correct_aux m am (flatten e1) (flatten e2);
                  flatten_correct m am e1; flatten_correct m am e2
val flatten_correct (#a: Type) (m: cm a) (am: amap a) (e: exp)
    : Lemma (mdenote m am e == xsdenote m am (flatten e))
let rec flatten_correct (#a: Type) (m: cm a) (am: amap a) (e: exp)
    : Lemma (mdenote m am e == xsdenote m am (flatten e)) =
match e with
| Unit | Atom _ -> ()
| Mult e1 e2 ->
  flatten_correct_aux m am (flatten e1) (flatten e2);
  flatten_correct m am e1;
  flatten_correct m am e2
FStar.Tactics.CanonCommMonoidSimple.fst.checked
prims.fst.checked FStar.Tactics.V2.fst.checked FStar.Tactics.CanonCommSwaps.fst.checked FStar.Tactics.fst.checked FStar.Reflection.V2.fst.checked FStar.Pervasives.Native.fst.checked FStar.Pervasives.fsti.checked FStar.Mul.fst.checked FStar.List.Tot.Properties.fst.checked FStar.List.Tot.Base.fst.checked FStar.List.Tot.fst.checked FStar.List.fst.checked FStar.Classical.fsti.checked FStar.Algebra.CommMonoid.fst.checked
FStar.Tactics.CanonCommMonoidSimple.fst
FStar.Algebra.CommMonoid.cm FStar.Tactics.CanonCommMonoidSimple.amap FStar.Tactics.CanonCommMonoidSimple.exp FStar.Tactics.CanonCommMonoidSimple.atom FStar.Tactics.CanonCommMonoidSimple.flatten_correct Prims.unit FStar.Tactics.CanonCommMonoidSimple.flatten_correct_aux FStar.Tactics.CanonCommMonoidSimple.flatten Prims.l_True Prims.squash Prims.eq2 FStar.Tactics.CanonCommMonoidSimple.mdenote FStar.Tactics.CanonCommMonoidSimple.xsdenote Prims.Nil FStar.Pervasives.pattern
(*
   Copyright 2008-2018 Microsoft Research

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*)
module FStar.Tactics.CanonCommMonoidSimple

open FStar.Algebra.CommMonoid
open FStar.List
open FStar.Reflection.V2
open FStar.Tactics.V2
open FStar.Classical
open FStar.Tactics.CanonCommSwaps

let term_eq = FStar.Tactics.term_eq_old

(* A simple expression canonizer for commutative monoids.
   For a canonizer with more features see FStar.Tactics.CanonCommMonoid.fst.

   Inspired by:
   - http://adam.chlipala.net/cpdt/html/Cpdt.Reflection.html
   - http://poleiro.info/posts/2015-04-13-writing-reflective-tactics.html
*)

(* Only dump when debugging is on *)
let dump m = if debugging () then dump m

(***** Expression syntax *)

let atom : eqtype = nat

type exp : Type =
  | Unit : exp
  | Mult : exp -> exp -> exp
  | Atom : atom -> exp

let rec exp_to_string (e:exp) : string =
  match e with
  | Unit -> "Unit"
  | Atom x -> "Atom " ^ string_of_int (x <: atom)
  | Mult e1 e2 -> "Mult (" ^ exp_to_string e1
                   ^ ") (" ^ exp_to_string e2 ^ ")"

(***** Expression denotation *)

// Use a map that stores for each atom
// (1) its denotation that should be treated abstractly (type a) and
// (2) user-specified extra information depending on its term (type b)

let amap (a:Type) = list (atom * a) * a
let const (#a:Type) (xa:a) : amap a = ([], xa)
let select (#a:Type) (x:atom) (am:amap a) : Tot a =
  match assoc #atom #a x (fst am) with
  | Some a -> a
  | _ -> snd am
let update (#a:Type) (x:atom) (xa:a) (am:amap a) : amap a =
  (x, xa)::fst am, snd am

let rec mdenote (#a:Type) (m:cm a) (am:amap a) (e:exp) : a =
  match e with
  | Unit -> CM?.unit m
  | Atom x -> select x am
  | Mult e1 e2 -> CM?.mult m (mdenote m am e1) (mdenote m am e2)

let rec xsdenote (#a:Type) (m:cm a) (am:amap a) (xs:list atom) : a =
  match xs with
  | [] -> CM?.unit m
  | [x] -> select x am
  | x::xs' -> CM?.mult m (select x am) (xsdenote m am xs')

(***** Flattening expressions to lists of atoms *)

let rec flatten (e:exp) : list atom =
  match e with
  | Unit -> []
  | Atom x -> [x]
  | Mult e1 e2 -> flatten e1 @ flatten e2

let rec flatten_correct_aux (#a:Type) (m:cm a) (am:amap a) (xs1 xs2:list atom) :
    Lemma (xsdenote m am (xs1 @ xs2) == CM?.mult m (xsdenote m am xs1)
                                                   (xsdenote m am xs2)) =
  match xs1 with
  | [] -> CM?.identity m (xsdenote m am xs2)
  | [x] -> if (Nil? xs2) then right_identity m (select x am)
  | x::xs1' -> (CM?.associativity m (select x am)
                      (xsdenote m am xs1') (xsdenote m am xs2);
                flatten_correct_aux m am xs1' xs2)

let rec flatten_correct (#a:Type) (m:cm a) (am:amap a) (e:exp) :
val flatten_correct (#a: Type) (m: cm a) (am: amap a) (e: exp)
    : Lemma (mdenote m am e == xsdenote m am (flatten e))

    m: FStar.Algebra.CommMonoid.cm a ->
    am: FStar.Tactics.CanonCommMonoidSimple.amap a ->
    e: FStar.Tactics.CanonCommMonoidSimple.exp
  -> FStar.Pervasives.Lemma
    (ensures
      FStar.Tactics.CanonCommMonoidSimple.mdenote m am e ==
      FStar.Tactics.CanonCommMonoidSimple.xsdenote m
        am
        (FStar.Tactics.CanonCommMonoidSimple.flatten e))