signature QUOTIENT =

sig

  type maps_info = {mapfun: string, relfun: string}

  val mk_quotient_type: ((binding * mixfix) * (typ * term)) list -> Proof.context -> Proof.state

  val mk_quotient_type_cmd: (((bstring * mixfix) * string) * string) list -> Proof.context -> Proof.state

  val define: binding * mixfix * term -> local_theory -> (term * thm) * local_theory

  val note: binding * thm -> local_theory -> thm * local_theory

  val maps_lookup: theory -> string -> maps_info option

  val maps_update: string -> maps_info -> theory -> theory                                  

end;

structure Quotient: QUOTIENT =

struct

(* data containers *)

(*******************)

(* info about map- and rel-functions *)

type maps_info = {mapfun: string, relfun: string}

structure MapsData = TheoryDataFun

  (type T = maps_info Symtab.table

   val empty = Symtab.empty

   val copy = I

   val extend = I

   fun merge _ = Symtab.merge (K true))

val maps_lookup = Symtab.lookup o MapsData.get

fun maps_update k v = MapsData.map (Symtab.update (k, v))

(* info about the quotient types *)

type quotient_info = {qtyp: typ, rtyp: typ, rel: term}

structure QuotData = TheoryDataFun

  (type T = quotient_info list

   val empty = []

   val copy = I

   val extend = I

   fun merge _ = (op @))

val quotdata_lookup = QuotData.get

fun quotdata_update (qty, rty, rel) = 

      QuotData.map (fn ls => {qtyp = qty, rtyp = rty, rel = rel}::ls)

fun print_quotdata ctxt =

let

  val quots = QuotData.get (Context.theory_of_proof ctxt)

  fun prt_quot {qtyp, rtyp, rel} = Pretty.block

      [Pretty.str ("quotient:"), 

       Pretty.brk 2, 

       Syntax.pretty_typ ctxt qtyp,

       Pretty.brk 2, 

       Syntax.pretty_typ ctxt rtyp,

       Pretty.brk 2, 

       Syntax.pretty_term ctxt rel]

in

  [Pretty.big_list "quotients:" (map prt_quot quots)]

  |> Pretty.chunks |> Pretty.writeln

end

val _ = 

  OuterSyntax.improper_command "print_quotients" "print quotient types of this theory" 

    OuterKeyword.diag (Scan.succeed (Toplevel.keep (print_quotdata o Toplevel.context_of)))

(* wrappers for define and note *)

fun define (name, mx, rhs) lthy =

let

  val ((rhs, (_ , thm)), lthy') =

     LocalTheory.define Thm.internalK ((name, mx), (Attrib.empty_binding, rhs)) lthy

in

  ((rhs, thm), lthy')

end

fun note (name, thm) lthy =

let

  val ((_,[thm']), lthy') = LocalTheory.note Thm.theoremK ((name, []), [thm]) lthy

in

  (thm', lthy')

end

(* definition of the quotient type *)

(***********************************)

(* constructs the term lambda (c::rty => bool). EX (x::rty). c = rel x *)

fun typedef_term rel rty lthy =

let

  val [x, c] = [("x", rty), ("c", HOLogic.mk_setT rty)]

               |> Variable.variant_frees lthy [rel]

               |> map Free

in

  lambda c

    (HOLogic.exists_const rty $

       lambda x (HOLogic.mk_eq (c, (rel $ x))))

end

(* makes the new type definitions and proves non-emptyness*)

fun typedef_make (qty_name, mx, rel, rty) lthy =

let

  val typedef_tac =

     EVERY1 [rewrite_goal_tac @{thms mem_def},

             rtac @{thm exI},

             rtac @{thm exI},

             rtac @{thm refl}]

  val tfrees = map fst (Term.add_tfreesT rty [])

in

  LocalTheory.theory_result

    (Typedef.add_typedef false NONE

       (qty_name, tfrees, mx)

         (typedef_term rel rty lthy)

           NONE typedef_tac) lthy

end

(* tactic to prove the QUOT_TYPE theorem for the new type *)

fun typedef_quot_type_tac equiv_thm (typedef_info: Typedef.info) =

let

  val unfold_mem = MetaSimplifier.rewrite_rule @{thms mem_def}

  val rep_thm = #Rep typedef_info |> unfold_mem

  val rep_inv = #Rep_inverse typedef_info

  val abs_inv = #Abs_inverse typedef_info |> unfold_mem

  val rep_inj = #Rep_inject typedef_info

in

  EVERY1 [rtac @{thm QUOT_TYPE.intro},

          rtac equiv_thm,

          rtac rep_thm,

          rtac rep_inv,

          rtac abs_inv,

          rtac @{thm exI}, 

          rtac @{thm refl},

          rtac rep_inj]

end

(* proves the QUOT_TYPE theorem *)

fun typedef_quot_type_thm (rel, abs, rep, equiv_thm, typedef_info) lthy =

let

  val quot_type_const = Const (@{const_name "QUOT_TYPE"}, dummyT)

  val goal = HOLogic.mk_Trueprop (quot_type_const $ rel $ abs $ rep)

             |> Syntax.check_term lthy

in

  Goal.prove lthy [] [] goal

    (K (typedef_quot_type_tac equiv_thm typedef_info))

end

(* proves the quotient theorem *)

fun typedef_quotient_thm (rel, abs, rep, abs_def, rep_def, quot_type_thm) lthy =

let

  val quotient_const = Const (@{const_name "QUOTIENT"}, dummyT)

  val goal = HOLogic.mk_Trueprop (quotient_const $ rel $ abs $ rep)

             |> Syntax.check_term lthy

  val typedef_quotient_thm_tac =

    EVERY1 [K (rewrite_goals_tac [abs_def, rep_def]),

            rtac @{thm QUOT_TYPE.QUOTIENT},

            rtac quot_type_thm]

in

  Goal.prove lthy [] [] goal

    (K typedef_quotient_thm_tac)

end

(* main function for constructing the quotient type *)

fun mk_typedef_main (((qty_name, mx), (rty, rel)), equiv_thm) lthy =

let

  (* generates typedef *)

  val ((_, typedef_info), lthy1) = typedef_make (qty_name, mx, rel, rty) lthy

  (* abs and rep functions *)

  val abs_ty = #abs_type typedef_info

  val rep_ty = #rep_type typedef_info

  val abs_name = #Abs_name typedef_info

  val rep_name = #Rep_name typedef_info

  val abs = Const (abs_name, rep_ty --> abs_ty)

  val rep = Const (rep_name, abs_ty --> rep_ty)

  (* ABS and REP definitions *)

  val ABS_const = Const (@{const_name "QUOT_TYPE.ABS"}, dummyT )

  val REP_const = Const (@{const_name "QUOT_TYPE.REP"}, dummyT )

  val ABS_trm = Syntax.check_term lthy1 (ABS_const $ rel $ abs)

  val REP_trm = Syntax.check_term lthy1 (REP_const $ rep)

  val ABS_name = Binding.prefix_name "ABS_" qty_name

  val REP_name = Binding.prefix_name "REP_" qty_name

  val (((ABS, ABS_def), (REP, REP_def)), lthy2) =

         lthy1 |> define (ABS_name, NoSyn, ABS_trm)

               ||>> define (REP_name, NoSyn, REP_trm)

  (* quot_type theorem *)

  val quot_thm = typedef_quot_type_thm (rel, abs, rep, equiv_thm, typedef_info) lthy2

  val quot_thm_name = Binding.prefix_name "QUOT_TYPE_" qty_name

  (* quotient theorem *)

  val quotient_thm = typedef_quotient_thm (rel, ABS, REP, ABS_def, REP_def, quot_thm) lthy2

  val quotient_thm_name = Binding.prefix_name "QUOTIENT_" qty_name

  (* interpretation *)

  val bindd = ((Binding.make ("", Position.none)), ([]: Attrib.src list))

  val ((_, [eqn1pre]), lthy3) = Variable.import true [ABS_def] lthy2;

  val eqn1i = Thm.prop_of (symmetric eqn1pre)

  val ((_, [eqn2pre]), lthy4) = Variable.import true [REP_def] lthy3;

  val eqn2i = Thm.prop_of (symmetric eqn2pre)

  val exp_morphism = ProofContext.export_morphism lthy4 (ProofContext.init (ProofContext.theory_of lthy4));

  val exp_term = Morphism.term exp_morphism;

  val exp = Morphism.thm exp_morphism;

  val mthd = Method.SIMPLE_METHOD ((rtac quot_thm 1) THEN

    ALLGOALS (simp_tac (HOL_basic_ss addsimps [(symmetric (exp ABS_def)), (symmetric (exp REP_def))])))

  val mthdt = Method.Basic (fn _ => mthd)

  val bymt = Proof.global_terminal_proof (mthdt, NONE)

  val exp_i = [(@{const_name QUOT_TYPE}, ((("QUOT_TYPE_I_" ^ (Binding.name_of qty_name)), true),

    Expression.Named [

     ("R", rel),

     ("Abs", abs),

     ("Rep", rep)

    ]))]

in

  lthy4

  |> note (quot_thm_name, quot_thm)

  ||>> note (quotient_thm_name, quotient_thm)

  ||> LocalTheory.theory (fn thy =>

      let

        val global_eqns = map exp_term [eqn2i, eqn1i];

        (* Not sure if the following context should not be used *)

        val (global_eqns2, lthy5) = Variable.import_terms true global_eqns lthy4;

        val global_eqns3 = map (fn t => (bindd, t)) global_eqns2;

      in ProofContext.theory_of (bymt (Expression.interpretation (exp_i, []) global_eqns3 thy)) end)

end

(* interface and syntax setup *)

(* the ML-interface takes a list of 4-tuples consisting of  *)

(*                                                          *)

(* - the name of the quotient type                          *)

(* - its mixfix annotation                                  *)

(* - the type to be quotient                                *)

(* - the relation according to which the type is quotient   *)

fun mk_quotient_type quot_list lthy = 

let

  fun get_goal (rty, rel) =

  let

      val EQUIV_ty = ([rty, rty] ---> @{typ bool}) --> @{typ bool}

  in 

    (HOLogic.mk_Trueprop (Const (@{const_name EQUIV}, EQUIV_ty) $ rel), [])

  end

  val goals = map (get_goal o snd) quot_list

  fun after_qed thms lthy =

    fold_map mk_typedef_main (quot_list ~~ (flat thms)) lthy |> snd

in

  Proof.theorem_i NONE after_qed [goals] lthy

end

val quotspec_parser = 

    OuterParse.and_list1

     (OuterParse.short_ident -- OuterParse.opt_infix -- 

       (OuterParse.$$$ "=" |-- OuterParse.typ) -- 

         (OuterParse.$$$ "/" |-- OuterParse.term))

fun mk_quotient_type_cmd spec lthy = 

let

  fun parse_spec (((qty_str, mx), rty_str), rel_str) =

  let

    val qty_name = Binding.name qty_str

    val rty = Syntax.parse_typ lthy rty_str

    val rel = Syntax.parse_term lthy rel_str

              |> Syntax.check_term lthy

  in

     ((qty_name, mx), (rty, rel))

  end

in

  mk_quotient_type (map parse_spec spec) lthy

end

val _ = OuterKeyword.keyword "/"

val _ = 

    OuterSyntax.local_theory_to_proof "quotient" 

      "quotient type definitions (requires equivalence proofs)"

         OuterKeyword.thy_goal (quotspec_parser >> mk_quotient_type_cmd)

end; (* structure *)

open Quotient