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 Enrichments.
30 Require Import NaturalDeduction.
31 Require Import NaturalDeductionCategory.
33 Section Programming_Language.
35 Context {T : Type}. (* types of the language *)
37 Definition PLJudg := (Tree ??T) * (Tree ??T).
38 Definition sequent := @pair (Tree ??T) (Tree ??T).
39 Notation "cs |= ss" := (sequent cs ss) : pl_scope.
41 Context {Rule : Tree ??PLJudg -> Tree ??PLJudg -> Type}.
43 Notation "H /⋯⋯/ C" := (ND Rule H C) : pl_scope.
49 Class ProgrammingLanguage :=
50 { pl_eqv0 : @ND_Relation PLJudg Rule
51 ; pl_snd :> @SequentND PLJudg Rule _ sequent
52 ; pl_cnd :> @ContextND PLJudg Rule T sequent pl_snd
53 ; pl_eqv1 :> @SequentND_Relation PLJudg Rule _ sequent pl_snd pl_eqv0
54 ; pl_eqv :> @ContextND_Relation PLJudg Rule _ sequent pl_snd pl_cnd pl_eqv0 pl_eqv1
56 Notation "pf1 === pf2" := (@ndr_eqv _ _ pl_eqv _ _ pf1 pf2) : temporary_scope3.
58 Section LanguageCategory.
60 Context (PL:ProgrammingLanguage).
62 (* category of judgments in a fixed type/coercion context *)
63 Definition Judgments_cartesian := @Judgments_Category_CartesianCat _ Rule pl_eqv.
65 Definition JudgmentsL := Judgments_cartesian.
67 Definition identityProof t : [] ~~{JudgmentsL}~~> [t |= t].
72 Definition cutProof a b c : [a |= b],,[b |= c] ~~{JudgmentsL}~~> [a |= c].
77 Existing Instance pl_eqv.
79 Definition TypesL : ECategory JudgmentsL (Tree ??T) (fun x y => [x|=y]).
81 {| eid := identityProof
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.
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.
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.
119 Definition Types_binoidal : EBinoidalCat TypesL (@T_Branch _).
121 {| ebc_first := Types_first
122 ; ebc_second := Types_second
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
130 simpl; eapply cndr_inert. unfold identityProof; apply pl_eqv. auto.
131 apply ndpc_comp; auto.
132 apply ndpc_comp; auto.
134 simpl; eapply cndr_inert. unfold identityProof; apply pl_eqv. auto.
135 apply ndpc_comp; auto.
136 apply ndpc_comp; auto.
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
144 unfold eqv; unfold comp; simpl.
145 eapply cndr_inert. apply pl_eqv. auto.
146 apply ndpc_comp; auto.
147 apply ndpc_comp; 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.
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
160 unfold eqv; unfold comp; simpl.
161 eapply cndr_inert. apply pl_eqv. auto.
162 apply ndpc_comp; auto.
163 apply ndpc_comp; 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.
172 (* this tactical searches the environment; setoid_rewrite doesn't seem to be able to do that properly sometimes *)
173 Ltac nd_swap_ltac P EQV :=
175 [ |- context [ (?F ** nd_id _) ;; (nd_id _ ** ?G) ] ] =>
176 set (@nd_swap _ _ EQV _ _ _ _ F G) as P
179 Instance Types_assoc a b : Types_second a >>>> Types_first b <~~~> Types_first b >>>> Types_second a :=
180 { ni_iso := fun c => Types_assoc_iso a c b }.
189 nd_swap_ltac p pl_eqv.
193 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
194 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
195 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
196 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
198 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
199 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
201 set (ni_commutes' (jud_mon_cancelr pl_eqv) f) as q.
207 set (ni_commutes' (jud_mon_cancell pl_eqv) f) as q.
209 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
210 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
212 setoid_rewrite qq in q.
216 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
217 apply ndr_comp_respects; try reflexivity.
220 apply (cndr_inert pl_cnd); auto.
221 apply ndpc_comp; auto.
222 apply ndpc_comp; auto.
223 apply ndpc_comp; auto.
224 apply ndpc_comp; auto.
225 apply ndpc_comp; auto.
226 apply ndpc_comp; auto.
229 Instance Types_assoc_ll a b : Types_second (a,,b) <~~~> Types_second b >>>> Types_second a :=
230 { ni_iso := fun c => Types_assoc_iso a b c }.
239 nd_swap_ltac p pl_eqv.
243 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
244 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
245 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
247 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
248 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
250 set (ni_commutes' (jud_mon_cancelr pl_eqv) f) as q.
256 set (ni_commutes' (jud_mon_cancell pl_eqv) f) as q.
258 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
259 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
261 setoid_rewrite qq in q.
265 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
266 apply ndr_comp_respects; try reflexivity.
269 apply (cndr_inert pl_cnd); auto.
270 apply ndpc_comp; auto.
271 apply ndpc_comp; auto.
272 apply ndpc_comp; auto.
273 apply ndpc_comp; auto.
274 apply ndpc_comp; auto.
277 Instance Types_assoc_rr a b : Types_first (a,,b) <~~~> Types_first a >>>> Types_first b :=
278 { ni_iso := fun c => iso_inv _ _ (Types_assoc_iso c a b) }.
287 nd_swap_ltac p pl_eqv.
291 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
292 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
293 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
295 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
296 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
298 set (ni_commutes' (jud_mon_cancelr pl_eqv) f) as q.
304 set (ni_commutes' (jud_mon_cancell pl_eqv) f) as q.
306 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
307 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
309 setoid_rewrite qq in q.
313 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
314 apply ndr_comp_respects; try reflexivity.
317 apply (cndr_inert pl_cnd); auto.
318 apply ndpc_comp; auto.
319 apply ndpc_comp; auto.
320 apply ndpc_comp; auto.
321 apply ndpc_comp; auto.
322 apply ndpc_comp; auto.
325 Instance Types_cancelr : Types_first [] <~~~> functor_id _ :=
326 { ni_iso := Types_cancelr_iso }.
331 nd_swap_ltac p pl_eqv.
333 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
334 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
335 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
337 set (ni_commutes' (jud_mon_cancelr pl_eqv) f) as q.
343 set (ni_commutes' (jud_mon_cancell pl_eqv) f) as q.
345 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
346 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
348 setoid_rewrite qq in q.
352 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
353 apply ndr_comp_respects; try reflexivity.
356 apply (cndr_inert pl_cnd); auto.
357 apply ndpc_comp; auto.
358 apply ndpc_comp; auto.
359 apply ndpc_comp; auto.
362 Instance Types_cancell : Types_second [] <~~~> functor_id _ :=
363 { ni_iso := Types_cancell_iso }.
368 nd_swap_ltac p pl_eqv.
370 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
371 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
372 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
374 set (ni_commutes' (jud_mon_cancelr pl_eqv) f) as q.
380 set (ni_commutes' (jud_mon_cancell pl_eqv) f) as q.
382 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
383 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
385 setoid_rewrite qq in q.
388 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
390 apply ndr_comp_respects; try reflexivity.
393 apply (cndr_inert pl_cnd); auto.
394 apply ndpc_comp; auto.
395 apply ndpc_comp; auto.
396 apply ndpc_comp; auto.
399 Lemma TypesL_assoc_central a b c : CentralMorphism(H:=Types_binoidal) #((Types_assoc a b) c).
401 apply Build_CentralMorphism.
408 nd_swap_ltac p pl_eqv.
411 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
412 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
413 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
414 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
416 set (ni_commutes' (jud_mon_cancelr pl_eqv) g) as q.
422 set (ni_commutes' (jud_mon_cancell pl_eqv) g) as q.
424 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
425 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
427 setoid_rewrite qq in q.
431 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
432 apply ndr_comp_respects.
436 apply (cndr_inert pl_cnd); auto.
437 apply ndpc_comp; auto.
438 apply ndpc_comp; auto.
439 apply ndpc_comp; auto.
440 apply ndpc_comp; auto.
441 apply ndpc_comp; auto.
442 apply ndpc_comp; auto.
451 nd_swap_ltac p pl_eqv.
454 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
455 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
456 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
457 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
459 set (ni_commutes' (jud_mon_cancelr pl_eqv) g) as q.
465 set (ni_commutes' (jud_mon_cancell pl_eqv) g) as q.
467 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
468 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
470 setoid_rewrite qq in q.
474 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
475 apply ndr_comp_respects.
479 apply (cndr_inert pl_cnd); auto.
480 apply ndpc_comp; auto.
481 apply ndpc_comp; auto.
482 apply ndpc_comp; auto.
483 apply ndpc_comp; auto.
484 apply ndpc_comp; auto.
485 apply ndpc_comp; auto.
488 Lemma TypesL_cancell_central a : CentralMorphism(H:=Types_binoidal) #(Types_cancell a).
490 apply Build_CentralMorphism.
497 nd_swap_ltac p pl_eqv.
500 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
501 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
502 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
503 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
505 set (ni_commutes' (jud_mon_cancelr pl_eqv) g) as q.
511 set (ni_commutes' (jud_mon_cancell pl_eqv) g) as q.
513 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
514 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
516 setoid_rewrite qq in q.
520 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
521 apply ndr_comp_respects.
525 apply (cndr_inert pl_cnd); auto.
526 apply ndpc_comp; auto.
527 apply ndpc_comp; auto.
528 apply ndpc_comp; auto.
529 apply ndpc_comp; auto.
530 apply ndpc_comp; auto.
531 apply ndpc_comp; auto.
540 nd_swap_ltac p pl_eqv.
543 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
544 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
545 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
546 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
548 set (ni_commutes' (jud_mon_cancelr pl_eqv) g) as q.
554 set (ni_commutes' (jud_mon_cancell pl_eqv) g) as q.
556 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
557 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
559 setoid_rewrite qq in q.
563 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
564 apply ndr_comp_respects.
568 apply (cndr_inert pl_cnd); auto.
569 apply ndpc_comp; auto.
570 apply ndpc_comp; auto.
571 apply ndpc_comp; auto.
572 apply ndpc_comp; auto.
573 apply ndpc_comp; auto.
574 apply ndpc_comp; auto.
577 Lemma TypesL_cancelr_central a : CentralMorphism(H:=Types_binoidal) #(Types_cancelr a).
579 apply Build_CentralMorphism.
586 nd_swap_ltac p pl_eqv.
589 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
590 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
591 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
592 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
594 set (ni_commutes' (jud_mon_cancelr pl_eqv) g) as q.
600 set (ni_commutes' (jud_mon_cancell pl_eqv) g) as q.
602 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
603 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
605 setoid_rewrite qq in q.
609 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
610 apply ndr_comp_respects.
614 apply (cndr_inert pl_cnd); auto.
615 apply ndpc_comp; auto.
616 apply ndpc_comp; auto.
617 apply ndpc_comp; auto.
618 apply ndpc_comp; auto.
619 apply ndpc_comp; auto.
620 apply ndpc_comp; auto.
629 nd_swap_ltac p pl_eqv.
632 setoid_rewrite (@nd_prod_split_left _ Rule pl_eqv _ _ _ []).
633 setoid_rewrite (@nd_prod_split_right _ Rule pl_eqv _ _ _ []).
634 repeat setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
635 setoid_rewrite <- (@ndr_comp_associativity _ Rule pl_eqv).
637 set (ni_commutes' (jud_mon_cancelr pl_eqv) g) as q.
643 set (ni_commutes' (jud_mon_cancell pl_eqv) g) as q.
645 set (coincide (pmon_triangle(PreMonoidalCat:=(Judgments_Category_premonoidal pl_eqv)))) as q'.
646 set (isos_forward_equal_then_backward_equal _ _ q') as qq.
648 setoid_rewrite qq in q.
652 setoid_rewrite (@ndr_comp_associativity _ Rule pl_eqv).
653 apply ndr_comp_respects.
657 apply (cndr_inert pl_cnd); auto.
658 apply ndpc_comp; auto.
659 apply ndpc_comp; auto.
660 apply ndpc_comp; auto.
661 apply ndpc_comp; auto.
662 apply ndpc_comp; auto.
663 apply ndpc_comp; auto.
666 Instance TypesL_PreMonoidal : PreMonoidalCat Types_binoidal [] :=
667 { pmon_assoc := Types_assoc
668 ; pmon_cancell := Types_cancell
669 ; pmon_cancelr := Types_cancelr
670 ; pmon_assoc_rr := Types_assoc_rr
671 ; pmon_assoc_ll := Types_assoc_ll
673 apply Build_Pentagon.
675 eapply cndr_inert. apply pl_eqv.
699 apply Build_Triangle; intros; simpl.
700 eapply cndr_inert. apply pl_eqv.
709 eapply cndr_inert. apply pl_eqv. auto.
711 intros; simpl; reflexivity.
712 intros; simpl; reflexivity.
713 apply TypesL_assoc_central.
714 apply TypesL_cancelr_central.
715 apply TypesL_cancell_central.
718 Definition TypesEnrichedInJudgments : SurjectiveEnrichment.
720 {| senr_c_pm := TypesL_PreMonoidal
721 ; senr_v := JudgmentsL
722 ; senr_v_bin := Judgments_Category_binoidal _
723 ; senr_v_pmon := Judgments_Category_premonoidal _
724 ; senr_v_mon := Judgments_Category_monoidal _
725 ; senr_c_bin := Types_binoidal
730 End LanguageCategory.
732 End Programming_Language.
733 Implicit Arguments ND [ Judgment ].