1 (*********************************************************************************************************************************)
2 (* ProgrammingLanguage *)
4 (* Basic assumptions about programming languages. *)
6 (*********************************************************************************************************************************)
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.
29 Require Import NaturalDeduction.
30 Require Import NaturalDeductionCategory.
32 Section Programming_Language.
34 Context {T : Type}. (* types of the language *)
36 Context (Judg : Type).
37 Context (sequent : Tree ??T -> Tree ??T -> Judg).
38 Notation "cs |= ss" := (sequent cs ss) : pl_scope.
40 Context {Rule : Tree ??Judg -> Tree ??Judg -> Type}.
42 Notation "H /⋯⋯/ C" := (ND Rule H C) : pl_scope.
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
55 Notation "pf1 === pf2" := (@ndr_eqv _ _ pl_eqv _ _ pf1 pf2) : temporary_scope3.
57 Section LanguageCategory.
59 Context (PL:ProgrammingLanguage).
61 (* category of judgments in a fixed type/coercion context *)
62 Definition Judgments_cartesian := @Judgments_Category_CartesianCat _ Rule pl_eqv.
64 Definition JudgmentsL := Judgments_cartesian.
66 Definition identityProof t : [] ~~{JudgmentsL}~~> [t |= t].
68 apply nd_seq_reflexive.
71 Definition cutProof a b c : [a |= b],,[b |= c] ~~{JudgmentsL}~~> [a |= c].
76 Existing Instance pl_eqv.
77 Definition TypesL : ECategory JudgmentsL (Tree ??T) (fun x y => [x|=y]).
79 {| eid := identityProof
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.
90 apply nd_cut_associativity.
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]).
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]).
120 Definition Types_binoidal : BinoidalCat TypesL (@T_Branch _).
122 {| bin_first := Types_first
123 ; bin_second := Types_second
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
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 }.
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
148 Instance Types_cancelr : Types_first [] <~~~> functor_id _ :=
149 { ni_iso := Types_cancelr_iso }.
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
161 Instance Types_cancell : Types_second [] <~~~> functor_id _ :=
162 { ni_iso := Types_cancell_iso }.
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 }.
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) }.
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
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 *)
193 Definition TypesEnrichedInJudgments : Enrichment.
194 refine {| enr_c := TypesL |}.
197 Structure HasProductTypes :=
201 Lemma CartesianEnrMonoidal (e:Enrichment) `(C:CartesianCat(Ob:= _)(Hom:= _)(C:=Underlying (enr_c e))) : MonoidalEnrichment e.
205 (* need to prove that if we have cartesian tuples we have cartesian contexts *)
206 Definition LanguagesWithProductsAreSMME : HasProductTypes -> SurjectiveMonicMonoidalEnrichment TypesEnrichedInJudgments.
210 End LanguageCategory.
212 End Programming_Language.
214 Structure ProgrammingLanguageSMME :=
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)
222 Coercion plsmme_pl : ProgrammingLanguageSMME >-> ProgrammingLanguage.
223 Coercion plsmme_smme : ProgrammingLanguageSMME >-> SurjectiveMonicMonoidalEnrichment.
225 Implicit Arguments ND [ Judgment ].