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 Enrichments.
  30 Require Import NaturalDeduction.
  31 Require Import NaturalDeductionCategory.
  32
  33 Section Programming_Language.
  34
  35   Context {T    : Type}.               (* types of the language *)
  36
  37   Context (Judg : Type).
  38   Context (sequent : Tree ??T -> Tree ??T -> Judg).
  39      Notation "cs |= ss" := (sequent cs ss) : pl_scope.
  40
  41   Context {Rule : Tree ??Judg -> Tree ??Judg -> Type}.
  42
  43   Notation "H /⋯⋯/ C" := (ND Rule H C) : pl_scope.
  44
  45   Open Scope pf_scope.
  46   Open Scope nd_scope.
  47   Open Scope pl_scope.
  48
  49   Class ProgrammingLanguage :=
  50   { pl_eqv0               :  @ND_Relation Judg Rule
  51   ; pl_snd                :> @SequentND Judg Rule _ sequent
  52   ; pl_cnd                :> @ContextND Judg Rule T sequent pl_snd
  53   ; pl_eqv1               :> @SequentND_Relation Judg Rule _ sequent pl_snd pl_eqv0
  54   ; pl_eqv                :> @ContextND_Relation Judg Rule _ sequent pl_snd pl_cnd pl_eqv0 pl_eqv1
  55   }.
  56   Notation "pf1 === pf2" := (@ndr_eqv _ _ pl_eqv _ _ pf1 pf2) : temporary_scope3.
  57
  58   Section LanguageCategory.
  59
  60     Context (PL:ProgrammingLanguage).
  61
  62     (* category of judgments in a fixed type/coercion context *)
  63     Definition Judgments_cartesian := @Judgments_Category_CartesianCat _ Rule pl_eqv.
  64
  65     Definition JudgmentsL          := Judgments_cartesian.
  66
  67     Definition identityProof t : [] ~~{JudgmentsL}~~> [t |= t].
  68       unfold hom; simpl.
  69       apply snd_initial.
  70       Defined.
  71
  72     Definition cutProof a b c : [a |= b],,[b |= c] ~~{JudgmentsL}~~> [a |= c].
  73       unfold hom; simpl.
  74       apply snd_cut.
  75       Defined.
  76
  77     Existing Instance pl_eqv.
  78
  79     Definition TypesL : ECategory JudgmentsL (Tree ??T) (fun x y => [x|=y]).
  80       refine
  81       {| eid   := identityProof
  82        ; ecomp := cutProof
  83       |}; intros.
  84       apply (mon_commutative(MonoidalCat:=JudgmentsL)).
  85       apply (mon_commutative(MonoidalCat:=JudgmentsL)).
  86       unfold identityProof; unfold cutProof; simpl; eapply cndr_inert. apply pl_eqv. auto. auto.
  87       unfold identityProof; unfold cutProof; simpl; eapply cndr_inert. apply pl_eqv. auto. auto.
  88       unfold identityProof; unfold cutProof; simpl; eapply cndr_inert. apply pl_eqv. auto. auto.
  89       apply ndpc_comp; auto.
  90       apply ndpc_comp; auto.
  91       Defined.
  92
  93     Instance Types_first c : EFunctor TypesL TypesL (fun x => x,,c ) :=
  94       { efunc := fun x y => cnd_expand_right(ContextND:=pl_cnd) x y c }.
  95       intros; apply (mon_commutative(MonoidalCat:=JudgmentsL)).
  96       intros. unfold ehom. unfold hom. unfold identityProof. unfold eid. simpl. unfold identityProof.
  97       apply (cndr_inert pl_cnd); auto.
  98       intros. unfold ehom. unfold comp. simpl. unfold cutProof.
  99       rewrite <- (@ndr_prod_preserves_comp _ _ pl_eqv _ _ (cnd_expand_right _ _ c) _ _ (nd_id1 (b|=c0))
 100                   _ (nd_id1 (a,,c |= b,,c))  _ (cnd_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       simpl; eapply cndr_inert. apply pl_eqv. auto. auto.
 104       Defined.
 105
 106     Instance Types_second c : EFunctor TypesL TypesL (fun x => c,,x) :=
 107       { efunc := fun x y => ((@cnd_expand_left _ _ _ _ _ _ x y c)) }.
 108       intros; apply (mon_commutative(MonoidalCat:=JudgmentsL)).
 109       intros. unfold ehom. unfold hom. unfold identityProof. unfold eid. simpl. unfold identityProof.
 110       eapply cndr_inert; auto. apply pl_eqv.
 111       intros. unfold ehom. unfold comp. simpl. unfold cutProof.
 112       rewrite <- (@ndr_prod_preserves_comp _ _ pl_eqv _ _ (cnd_expand_left _ _ c) _ _ (nd_id1 (b|=c0))
 113                   _ (nd_id1 (c,,a |= c,,b))  _ (cnd_expand_left _ _ c)).
 114       setoid_rewrite (@ndr_comp_right_identity _ _ pl_eqv _ [c,,a |= c,,b]).
 115       setoid_rewrite (@ndr_comp_left_identity  _ _ pl_eqv [b |= c0]).
 116       simpl; eapply cndr_inert. apply pl_eqv. auto. auto.
 117       Defined.
 118
 119     Definition Types_binoidal : EBinoidalCat TypesL.
 120       refine
 121         {| ebc_first  := Types_first
 122          ; ebc_second := Types_second
 123          |}.
 124       Defined.
 125
 126     Instance Types_assoc_iso a b c : Isomorphic(C:=TypesL) ((a,,b),,c) (a,,(b,,c)) :=
 127       { iso_forward  := snd_initial _ ;; cnd_ant_cossa _ a b c
 128       ; iso_backward := snd_initial _ ;; cnd_ant_assoc _ a b c
 129       }.
 130       simpl; eapply cndr_inert. unfold identityProof; apply pl_eqv. auto.
 131         apply ndpc_comp; auto.
 132         apply ndpc_comp; auto.
 133         auto.
 134       simpl; eapply cndr_inert. unfold identityProof; apply pl_eqv. auto.
 135         apply ndpc_comp; auto.
 136         apply ndpc_comp; auto.
 137         auto.
 138         Defined.
 139
 140     Instance Types_cancelr_iso a : Isomorphic(C:=TypesL) (a,,[]) a :=
 141       { iso_forward  := snd_initial _ ;; cnd_ant_rlecnac _ a
 142       ; iso_backward := snd_initial _ ;; cnd_ant_cancelr _ a
 143       }.
 144       unfold eqv; unfold comp; simpl.
 145       eapply cndr_inert. apply pl_eqv. auto.
 146         apply ndpc_comp; auto.
 147         apply ndpc_comp; auto.
 148         auto.
 149       unfold eqv; unfold comp; simpl.
 150       eapply cndr_inert. apply pl_eqv. auto.
 151         apply ndpc_comp; auto.
 152         apply ndpc_comp; auto.
 153         auto.
 154       Defined.
 155
 156     Instance Types_cancell_iso a : Isomorphic(C:=TypesL) ([],,a) a :=
 157       { iso_forward  := snd_initial _ ;; cnd_ant_llecnac _ a
 158       ; iso_backward := snd_initial _ ;; cnd_ant_cancell _ a
 159       }.
 160       unfold eqv; unfold comp; simpl.
 161       eapply cndr_inert. apply pl_eqv. auto.
 162         apply ndpc_comp; auto.
 163         apply ndpc_comp; auto.
 164         auto.
 165       unfold eqv; unfold comp; simpl.
 166       eapply cndr_inert. apply pl_eqv. auto.
 167         apply ndpc_comp; auto.
 168         apply ndpc_comp; auto.
 169         auto.
 170       Defined.
 171
 172     Instance Types_assoc a b : Types_second a >>>> Types_first b <~~~> Types_first b >>>> Types_second a :=
 173       { ni_iso := fun c => Types_assoc_iso a c b }.
 174       intros; unfold eqv; simpl.
 175       admit.
 176       Defined.
 177
 178     Instance Types_cancelr   : Types_first [] <~~~> functor_id _ :=
 179       { ni_iso := Types_cancelr_iso }.
 180       intros; simpl.
 181       admit.
 182       Defined.
 183
 184     Instance Types_cancell   : Types_second [] <~~~> functor_id _ :=
 185       { ni_iso := Types_cancell_iso }.
 186       admit.
 187       Defined.
 188
 189     Instance Types_assoc_ll a b : Types_second (a,,b) <~~~> Types_second b >>>> Types_second a :=
 190       { ni_iso := fun c => Types_assoc_iso a b c }.
 191       admit.
 192       Defined.
 193
 194     Instance Types_assoc_rr a b : Types_first (a,,b) <~~~> Types_first a >>>> Types_first b :=
 195       { ni_iso := fun c => iso_inv _ _ (Types_assoc_iso c a b) }.
 196       admit.
 197       Defined.
 198
 199     Instance Types_PreMonoidal : PreMonoidalCat Types_binoidal [] :=
 200       { pmon_assoc    := Types_assoc
 201       ; pmon_cancell  := Types_cancell
 202       ; pmon_cancelr  := Types_cancelr
 203       ; pmon_assoc_rr := Types_assoc_rr
 204       ; pmon_assoc_ll := Types_assoc_ll
 205       }.
 206 (*
 207       apply Build_Pentagon.
 208         intros; simpl.
 209         eapply cndr_inert. apply pl_eqv.
 210         apply ndpc_comp.
 211         apply ndpc_comp.
 212         auto.
 213         apply ndpc_comp.
 214         apply ndpc_prod.
 215         apply ndpc_comp.
 216         apply ndpc_comp.
 217         auto.
 218         apply ndpc_comp.
 219         auto.
 220         auto.
 221         auto.
 222         auto.
 223         auto.
 224         auto.
 225         apply ndpc_comp.
 226         apply ndpc_comp.
 227         auto.
 228         apply ndpc_comp.
 229         auto.
 230         auto.
 231         auto.
 232       apply Build_Triangle; intros; simpl.
 233         eapply cndr_inert. apply pl_eqv.
 234         auto.
 235         apply ndpc_comp.
 236         apply ndpc_comp.
 237         auto.
 238         apply ndpc_comp.
 239         auto.
 240         auto.
 241         auto.
 242         eapply cndr_inert. apply pl_eqv. auto.
 243           auto.
 244 *)
 245 admit.
 246 admit.
 247       intros; simpl; reflexivity.
 248       intros; simpl; reflexivity.
 249       admit.  (* assoc   central *)
 250       admit.  (* cancelr central *)
 251       admit.  (* cancell central *)
 252       Defined.
 253
 254     Definition TypesEnrichedInJudgments : Enrichment.
 255       refine
 256         {| enr_v_mon := Judgments_Category_monoidal _
 257          ; enr_c_pm  := Types_PreMonoidal
 258          ; enr_c_bin := Types_binoidal
 259         |}.
 260       Defined.
 261
 262     Structure HasProductTypes :=
 263     {
 264     }.
 265
 266     (*
 267     Lemma CartesianEnrMonoidal (e:PreMonoidalEnrichment)
 268       `(C:CartesianCat(Ob:= _)(Hom:= _)(C:=Underlying (enr_c e))) : MonoidalEnrichment e.
 269       admit.
 270       Defined.
 271       *)
 272
 273     (* need to prove that if we have cartesian tuples we have cartesian contexts *)
 274     (*
 275     Definition LanguagesWithProductsAreSMME : HasProductTypes -> SurjectiveMonicMonoidalEnrichment TypesEnrichedInJudgments.
 276       admit.
 277       Defined.
 278       *)
 279   End LanguageCategory.
 280
 281 End Programming_Language.
 282 (*
 283 Structure ProgrammingLanguageSMME :=
 284 { plsmme_t       : Type
 285 ; plsmme_judg    : Type
 286 ; plsmme_sequent : Tree ??plsmme_t -> Tree ??plsmme_t -> plsmme_judg
 287 ; plsmme_rule    : Tree ??plsmme_judg -> Tree ??plsmme_judg -> Type
 288 ; plsmme_pl      : @ProgrammingLanguage plsmme_t plsmme_judg plsmme_sequent plsmme_rule
 289 ; plsmme_smme    : SurjectiveMonicMonoidalEnrichment (TypesEnrichedInJudgments _ _ plsmme_pl)
 290 }.
 291 Coercion plsmme_pl   : ProgrammingLanguageSMME >-> ProgrammingLanguage.
 292 Coercion plsmme_smme : ProgrammingLanguageSMME >-> SurjectiveMonicMonoidalEnrichment.
 293 *)
 294 Implicit Arguments ND [ Judgment ].