src/ProgrammingLanguage.v

   1 (*********************************************************************************************************************************)
   2 (* ProgrammingLanguage                                                                                                           *)
   3 (*                                                                                                                               *)
   4 (*   Basic assumptions about programming languages.                                                                              *)
   5 (*                                                                                                                               *)
   6 (*********************************************************************************************************************************)
   7
   8 Generalizable All Variables.
   9 Require Import Preamble.
  10 Require Import General.
  11 Require Import Categories_ch1_3.
  12 Require Import InitialTerminal_ch2_2.
  13 Require Import Functors_ch1_4.
  14 Require Import Isomorphisms_ch1_5.
  15 Require Import ProductCategories_ch1_6_1.
  16 Require Import OppositeCategories_ch1_6_2.
  17 Require Import Enrichment_ch2_8.
  18 Require Import Subcategories_ch7_1.
  19 Require Import NaturalTransformations_ch7_4.
  20 Require Import NaturalIsomorphisms_ch7_5.
  21 Require Import BinoidalCategories.
  22 Require Import PreMonoidalCategories.
  23 Require Import MonoidalCategories_ch7_8.
  24 Require Import Coherence_ch7_8.
  25 Require Import Enrichment_ch2_8.
  26 Require Import RepresentableStructure_ch7_2.
  27 Require Import FunctorCategories_ch7_7.
  28
  29 Require Import NaturalDeduction.
  30 Require Import NaturalDeductionCategory.
  31
  32 Section Programming_Language.
  33
  34   Context {T    : Type}.               (* types of the language *)
  35
  36   Context (Judg : Type).
  37   Context (sequent : Tree ??T -> Tree ??T -> Judg).
  38      Notation "cs |= ss" := (sequent cs ss) : pl_scope.
  39
  40   Context {Rule : Tree ??Judg -> Tree ??Judg -> Type}.
  41
  42   Notation "H /⋯⋯/ C" := (ND Rule H C) : pl_scope.
  43
  44   Open Scope pf_scope.
  45   Open Scope nd_scope.
  46   Open Scope pl_scope.
  47
  48   Class ProgrammingLanguage :=
  49   { pl_eqv                :  @ND_Relation Judg Rule where "pf1 === pf2" := (@ndr_eqv _ _ pl_eqv _ _ pf1 pf2)
  50   ; pl_tsr                :> @TreeStructuralRules Judg Rule T sequent
  51   ; pl_sc                 :> @SequentCalculus Judg Rule _ sequent
  52   ; pl_subst              :> @CutRule Judg Rule _ sequent pl_eqv pl_sc
  53   ; pl_sequent_join       :> @SequentExpansion Judg Rule T sequent pl_eqv pl_sc pl_subst
  54   }.
  55   Notation "pf1 === pf2" := (@ndr_eqv _ _ pl_eqv _ _ pf1 pf2) : temporary_scope3.
  56
  57   Section LanguageCategory.
  58
  59     Context (PL:ProgrammingLanguage).
  60
  61     (* category of judgments in a fixed type/coercion context *)
  62     Definition Judgments_cartesian := @Judgments_Category_CartesianCat _ Rule pl_eqv.
  63
  64     Definition JudgmentsL          := Judgments_cartesian.
  65
  66     Definition identityProof t : [] ~~{JudgmentsL}~~> [t |= t].
  67       unfold hom; simpl.
  68       apply nd_seq_reflexive.
  69       Defined.
  70
  71     Definition cutProof a b c : [a |= b],,[b |= c] ~~{JudgmentsL}~~> [a |= c].
  72       unfold hom; simpl.
  73       apply pl_subst.
  74       Defined.
  75
  76     Existing Instance pl_eqv.
  77     Definition TypesL : ECategory JudgmentsL (Tree ??T) (fun x y => [x|=y]).
  78       refine
  79       {| eid   := identityProof
  80        ; ecomp := cutProof
  81       |}; intros.
  82       apply (mon_commutative(MonoidalCat:=JudgmentsL)).
  83       apply (mon_commutative(MonoidalCat:=JudgmentsL)).
  84       unfold identityProof; unfold cutProof; simpl.
  85       apply nd_cut_left_identity.
  86       unfold identityProof; unfold cutProof; simpl.
  87       apply nd_cut_right_identity.
  88       unfold identityProof; unfold cutProof; simpl.
  89       symmetry.
  90       apply nd_cut_associativity.
  91       Defined.
  92
  93     Definition Types_first c : EFunctor TypesL TypesL (fun x => x,,c ).
  94       refine {| efunc := fun x y => (@se_expand_right _ _ _ _ _ _ _ (@pl_sequent_join PL) c x y) |}.
  95       intros; apply (mon_commutative(MonoidalCat:=JudgmentsL)).
  96       intros. unfold ehom. unfold hom. unfold identityProof. unfold eid. simpl. unfold identityProof.
  97       apply se_reflexive_right.
  98       intros. unfold ehom. unfold comp. simpl. unfold cutProof.
  99       rewrite <- (@ndr_prod_preserves_comp _ _ pl_eqv _ _ (se_expand_right _ c) _ _ (nd_id1 (b|=c0))
 100                   _ (nd_id1 (a,,c |= b,,c))  _ (se_expand_right _ c)).
 101       setoid_rewrite (@ndr_comp_right_identity _ _ pl_eqv _ [a,, c |= b,, c]).
 102       setoid_rewrite (@ndr_comp_left_identity  _ _ pl_eqv [b |= c0]).
 103       apply se_cut_right.
 104       Defined.
 105
 106     Definition Types_second c : EFunctor TypesL TypesL (fun x => c,,x).
 107       eapply Build_EFunctor.
 108       instantiate (1:=(fun x y => ((@se_expand_left _ _ _ _ _ _ _ (@pl_sequent_join PL) c x y)))).
 109       intros; apply (mon_commutative(MonoidalCat:=JudgmentsL)).
 110       intros. unfold ehom. unfold hom. unfold identityProof. unfold eid. simpl. unfold identityProof.
 111       apply se_reflexive_left.
 112       intros. unfold ehom. unfold comp. simpl. unfold cutProof.
 113       rewrite <- (@ndr_prod_preserves_comp _ _ pl_eqv _ _ (se_expand_left _ c) _ _ (nd_id1 (b|=c0))
 114                   _ (nd_id1 (c,,a |= c,,b))  _ (se_expand_left _ c)).
 115       setoid_rewrite (@ndr_comp_right_identity _ _ pl_eqv _ [c,,a |= c,,b]).
 116       setoid_rewrite (@ndr_comp_left_identity  _ _ pl_eqv [b |= c0]).
 117       apply se_cut_left.
 118       Defined.
 119
 120     Definition Types_binoidal : BinoidalCat TypesL (@T_Branch _).
 121       refine
 122         {| bin_first  := Types_first
 123          ; bin_second := Types_second
 124          |}.
 125       Defined.
 126
 127     Instance Types_assoc_iso a b c : Isomorphic(C:=TypesL) ((a,,b),,c) (a,,(b,,c)) :=
 128       { iso_forward  := nd_seq_reflexive _ ;; tsr_ant_cossa _ a b c
 129       ; iso_backward := nd_seq_reflexive _ ;; tsr_ant_assoc _ a b c
 130       }.
 131       admit.
 132       admit.
 133       Defined.
 134
 135     Instance Types_assoc a b : Types_second a >>>> Types_first b <~~~> Types_first b >>>> Types_second a :=
 136       { ni_iso := fun c => Types_assoc_iso a c b }.
 137       admit.
 138       Defined.
 139
 140     Instance Types_cancelr_iso a : Isomorphic(C:=TypesL) (a,,[]) a :=
 141       { iso_forward  := nd_seq_reflexive _ ;; tsr_ant_rlecnac _ a
 142       ; iso_backward := nd_seq_reflexive _ ;; tsr_ant_cancelr _ a
 143       }.
 144       admit.
 145       admit.
 146       Defined.
 147
 148     Instance Types_cancelr   : Types_first [] <~~~> functor_id _ :=
 149       { ni_iso := Types_cancelr_iso }.
 150       admit.
 151       Defined.
 152
 153     Instance Types_cancell_iso a : Isomorphic(C:=TypesL) ([],,a) a :=
 154       { iso_forward  := nd_seq_reflexive _ ;; tsr_ant_llecnac _ a
 155       ; iso_backward := nd_seq_reflexive _ ;; tsr_ant_cancell _ a
 156       }.
 157       admit.
 158       admit.
 159       Defined.
 160
 161     Instance Types_cancell   : Types_second [] <~~~> functor_id _ :=
 162       { ni_iso := Types_cancell_iso }.
 163       admit.
 164       Defined.
 165
 166     Instance Types_assoc_ll a b : Types_second (a,,b) <~~~> Types_second b >>>> Types_second a :=
 167       { ni_iso := fun c => Types_assoc_iso a b c }.
 168       admit.
 169       Defined.
 170
 171     Instance Types_assoc_rr a b : Types_first (a,,b) <~~~> Types_first a >>>> Types_first b :=
 172       { ni_iso := fun c => iso_inv _ _ (Types_assoc_iso c a b) }.
 173       admit.
 174       Defined.
 175
 176     Instance Types_PreMonoidal : PreMonoidalCat Types_binoidal [] :=
 177         { pmon_assoc    := Types_assoc
 178         ; pmon_cancell  := Types_cancell
 179         ; pmon_cancelr  := Types_cancelr
 180         ; pmon_assoc_rr := Types_assoc_rr
 181         ; pmon_assoc_ll := Types_assoc_ll
 182         }.
 183         admit. (* pentagon law *)
 184         admit. (* triangle law *)
 185         intros; simpl; reflexivity.
 186         intros; simpl; reflexivity.
 187         admit.  (* assoc   central *)
 188         admit.  (* cancelr central *)
 189         admit.  (* cancell central *)
 190         Defined.
 191
 192     (*
 193     Definition TypesEnrichedInJudgments : Enrichment.
 194       refine {| enr_c := TypesL |}.
 195       Defined.
 196
 197     Structure HasProductTypes :=
 198     {
 199     }.
 200
 201     Lemma CartesianEnrMonoidal (e:Enrichment) `(C:CartesianCat(Ob:= _)(Hom:= _)(C:=Underlying (enr_c e))) : MonoidalEnrichment e.
 202       admit.
 203       Defined.
 204
 205     (* need to prove that if we have cartesian tuples we have cartesian contexts *)
 206     Definition LanguagesWithProductsAreSMME : HasProductTypes -> SurjectiveMonicMonoidalEnrichment TypesEnrichedInJudgments.
 207       admit.
 208       Defined.
 209       *)
 210   End LanguageCategory.
 211
 212 End Programming_Language.
 213 (*
 214 Structure ProgrammingLanguageSMME :=
 215 { plsmme_t       : Type
 216 ; plsmme_judg    : Type
 217 ; plsmme_sequent : Tree ??plsmme_t -> Tree ??plsmme_t -> plsmme_judg
 218 ; plsmme_rule    : Tree ??plsmme_judg -> Tree ??plsmme_judg -> Type
 219 ; plsmme_pl      : @ProgrammingLanguage plsmme_t plsmme_judg plsmme_sequent plsmme_rule
 220 ; plsmme_smme    : SurjectiveMonicMonoidalEnrichment (TypesEnrichedInJudgments _ _ plsmme_pl)
 221 }.
 222 Coercion plsmme_pl   : ProgrammingLanguageSMME >-> ProgrammingLanguage.
 223 Coercion plsmme_smme : ProgrammingLanguageSMME >-> SurjectiveMonicMonoidalEnrichment.
 224 *)
 225 Implicit Arguments ND [ Judgment ].