Brendan Hart 2019-2020 \begin{code} {-# OPTIONS --safe --without-K #-} open import MLTT.Spartan open import UF.FunExt open import UF.PropTrunc open import UF.Subsingletons module PCF.Lambda.Adequacy (pt : propositional-truncations-exist) (fe : β {π€ π₯} β funext π€ π₯) (pe : propext π€β) where open PropositionalTruncation pt open import UF.UniverseEmbedding open import DomainTheory.Basics.Dcpo pt fe π€β open import DomainTheory.Basics.Exponential pt fe π€β open import DomainTheory.Basics.LeastFixedPoint pt fe π€β open import DomainTheory.Basics.Pointed pt fe π€β open import Lifting.Construction π€β hiding (β₯) open import Lifting.Miscelanea π€β open import Naturals.Properties hiding (pred-succ) open import PCF.Combinatory.PCFCombinators pt fe π€β open import PCF.Lambda.AbstractSyntax pt open import PCF.Lambda.ApplicativeApproximation pt open import PCF.Lambda.BigStep pt open import PCF.Lambda.ScottModelOfContexts pt fe pe open import PCF.Lambda.ScottModelOfTerms pt fe pe open import PCF.Lambda.ScottModelOfTypes pt fe pe open import PCF.Lambda.Substitution pt fe pe open IfZeroDenotationalSemantics pe adequate : (Ο : type) (d : β¨ β¦ Ο β§ β» β©) (M : PCF β¨β© Ο) β π€βΜ adequate ΞΉ l t = π Γ ((p : is-defined l) β t β numeral (value l p)) adequate (Ο β Οβ) l t = (d : β¨ β¦ Ο β§ β» β©) (M : PCF β¨β© Ο) β adequate Ο d M β adequate Οβ (prβ l d) (t Β· M) lemma7-1-1 : {Ο : type} β (d : β¨ β¦ Ο β§ β» β©) β (d' : β¨ β¦ Ο β§ β» β©) β (d' ββ¨ β¦ Ο β§ β» β© d) β (M : PCF β¨β© Ο) β adequate Ο d M β adequate Ο d' M lemma7-1-1 {ΞΉ} d d' x M (_ , o) = β , f where f : (p : is-defined d') β M β numeral (value d' p) f p = transport (Ξ» - β M β numeral -) (eβ β»ΒΉ) (o (οΌ-to-is-defined eβ p)) where eβ : d' οΌ d eβ = x p eβ : value d' p οΌ value d (οΌ-to-is-defined eβ p) eβ = οΌ-of-values-from-οΌ eβ lemma7-1-1 {Ο β Οβ} f g x M p = Ξ³ where Ξ³ : (d : β¨ β¦ Ο β§ β» β©) β β N β adequate Ο d N β adequate Οβ (prβ g d) (M Β· N) Ξ³ d N a = IH where i : adequate Οβ (prβ f d) (M Β· N) i = p d N a ii : prβ g d ββ¨ β¦ Οβ β§ β» β© prβ f d ii = x d IH : adequate Οβ (prβ g d) (M Β· N) IH = lemma7-1-1 (prβ f d) (prβ g d) ii (M Β· N) i adequacy-lubs : {Ο : type} {I : π€βΜ } β (u : I β β¨ β¦ Ο β§ β» β©) β (Ξ΄ : is-Directed ( β¦ Ο β§ β») u) β (t : PCF β¨β© Ο) β ((i : I) β adequate Ο (u i) t) β adequate Ο (β ( β¦ Ο β§ β») Ξ΄) t adequacy-lubs {ΞΉ} {I} u Ξ΄ t a = β , g where g : (p : is-defined (β ( β¦ ΞΉ β§ β») Ξ΄)) β t β numeral (value (β ( β¦ ΞΉ β§ β») Ξ΄) p) g p = β₯β₯-rec β₯β₯-is-prop f p where f : (Ξ£ i κ I , is-defined (u i)) β t β numeral (value (β ( β¦ ΞΉ β§ β») Ξ΄) p) f (i , d) = transport (Ξ» - β t β numeral -) value-lub-is-same (prβ (a i) d) where lub-is-same : u i οΌ β ( β¦ ΞΉ β§ β») Ξ΄ lub-is-same = β-is-upperbound ( β¦ ΞΉ β§ β») Ξ΄ i d value-lub-is-same : value (u i) d οΌ value (β ( β¦ ΞΉ β§ β») Ξ΄) p value-lub-is-same = οΌ-of-values-from-οΌ lub-is-same adequacy-lubs {Ο β Οβ} {I} u Ξ΄ t a p M x = IH where ptfam : I β β¨ β¦ Οβ β§ β» β© ptfam = pointwise-family ( β¦ Ο β§ β») ( β¦ Οβ β§ β») u p ptfam-is-directed : is-Directed ( β¦ Οβ β§ β») ptfam ptfam-is-directed = pointwise-family-is-directed ( β¦ Ο β§ β») ( β¦ Οβ β§ β») u Ξ΄ p new_rel : (i : I) β adequate Οβ (ptfam i) (t Β· M) new_rel i = a i p M x IH : adequate Οβ (β ( β¦ Οβ β§ β») ptfam-is-directed) (t Β· M) IH = adequacy-lubs {Οβ} {I} ptfam ptfam-is-directed (t Β· M) new_rel adequacy-step : {Ο : type} (M M' : PCF β¨β© Ο) β M βΜ° M' β (a : β¨ β¦ Ο β§ β» β©) β adequate Ο a M β adequate Ο a M' adequacy-step {ΞΉ} M M' r a (β , Ο) = β , f where f : (p : is-defined a) β M' β numeral (value a p) f p = r (value a p) (Ο p) adequacy-step {Ο β Οβ} M M' r (Ο , _) rel d Mβ x = IH where new_rel : adequate Οβ (Ο d) (M Β· Mβ) new_rel = rel d Mβ x IH : adequate Οβ (Ο d) (M' Β· Mβ) IH = adequacy-step (M Β· Mβ) (M' Β· Mβ) (r Mβ) (Ο d) new_rel adequacy-bottom : {Ο : type} β (t : PCF β¨β© Ο) β adequate Ο (β₯ β¦ Ο β§) t adequacy-bottom {ΞΉ} t = β , (Ξ» p β π-elim p) adequacy-bottom {Ο β Οβ} t = (Ξ» _ M _ β adequacy-bottom (t Β· M)) lemma7-3 : {Ο : type} β (M : PCF β¨β© (Ο β Ο)) β (f : β¨ β¦ Ο β Ο β§ β» β©) β adequate (Ο β Ο) f M β adequate Ο (prβ (ΞΌ β¦ Ο β§) f) (Fix M) lemma7-3 {Ο} M f rel = adequacy-lubs iter-M iter-M-is-directed (Fix M) fn where iter-M : Lift π€β β β β¨ β¦ Ο β§ β» β© iter-M (n , β) = iter β¦ Ο β§ n f iter-M-is-directed : is-Directed (β¦ Ο β§ β») iter-M iter-M-is-directed = pointwise-family-is-directed ((β¦ Ο β§ βΉα΅αΆα΅α΅β₯ β¦ Ο β§) β») (β¦ Ο β§ β») (iter-c' β¦ Ο β§) (iter-is-directed' β¦ Ο β§) f fn : (n : Lift π€β β) β adequate Ο (iter β¦ Ο β§ (lower n) f) (Fix M) fn (zero , β) = adequacy-bottom (Fix M) fn (succ n , β) = adequacy-step (M Β· Fix M) (Fix M) fix-βΜ° (iter β¦ Ο β§ (succ n) f) IHβ where IH : adequate Ο (iter β¦ Ο β§ n f) (Fix M) IH = fn (n , β) IHβ : adequate Ο (iter β¦ Ο β§ (succ n) f) (M Β· (Fix M)) IHβ = rel (iter β¦ Ο β§ n f) (Fix M) IH adequacy-succ : {n : β} {Ξ : Context n} β (M : PCF Ξ ΞΉ) β (d : β¨ γ Ξ γ β» β©) β (f : β {A} β (x : Ξ β A) β PCF β¨β© A) β adequate ΞΉ (prβ β¦ M β§β d) (subst f M) β adequate ΞΉ (prβ β¦ Succ M β§β d) (subst f (Succ M)) adequacy-succ M d f (β , rel) = β , g where g : (p : is-defined (prβ β¦ Succ M β§β d)) β subst f (Succ M) β numeral (value (prβ β¦ Succ M β§β d) p) g p = β₯β₯-functor (Ξ» x β succ-arg x) (rel p) pred-lemma : β {n : β} {Ξ : Context n} {k : β} β {M : PCF Ξ ΞΉ} β M β' numeral k β (Pred M) β' numeral (pred k) pred-lemma {n} {Ξ} {zero} x = pred-zero x pred-lemma {n} {Ξ} {succ k} x = pred-succ x ifzero-lemma : {n : β} {Ξ : Context n} {k : β} (M : PCF Ξ ΞΉ) (Mβ : PCF Ξ ΞΉ) (Mβ : PCF Ξ ΞΉ) (f : β {A} β Ξ β A β PCF β¨β© A) β subst f M β numeral k β (d : β¨ γ Ξ γ β» β©) (M-is-defined : is-defined (prβ β¦ M β§β d)) (Ξ΄ : is-defined (β¦ ifZeroβ¦β (prβ β¦ Mβ β§β d) (prβ β¦ Mβ β§β d) k)) (Mβ-rel : adequate ΞΉ (prβ β¦ Mβ β§β d) (subst f Mβ)) (Mβ-rel : adequate ΞΉ (prβ β¦ Mβ β§β d) (subst f Mβ)) β subst f (IfZero M Mβ Mβ) β numeral (value (β¦ ifZeroβ¦β (prβ β¦ Mβ β§β d) (prβ β¦ Mβ β§β d) k) Ξ΄) ifzero-lemma {n} {Ξ} {zero} M Mβ Mβ f x d M-is-defined Ξ΄ (β , Mβ-rel) (β , Mβ-rel) = Ξ³ where Mβ-β : subst f Mβ β numeral (value (prβ β¦ Mβ β§β d) Ξ΄) Mβ-β = Mβ-rel Ξ΄ Ξ³ : subst f (IfZero M Mβ Mβ) β numeral (value (β¦ ifZeroβ¦β (prβ β¦ Mβ β§β d) (prβ β¦ Mβ β§β d) zero) Ξ΄) Ξ³ = β₯β₯-functor (Ξ» x β IfZero-zero (prβ x) (prβ x)) (binary-choice x Mβ-β) ifzero-lemma {n} {Ξ} {succ k} M Mβ Mβ f x d M-is-defined Ξ΄ (β , Mβ-rel) (β , Mβ-rel) = Ξ³ where Mβ-β : subst f Mβ β numeral (value (prβ β¦ Mβ β§β d) Ξ΄) Mβ-β = Mβ-rel Ξ΄ Ξ³ : subst f (IfZero M Mβ Mβ) β numeral (value (β¦ ifZeroβ¦β (prβ β¦ Mβ β§β d) (prβ β¦ Mβ β§β d) (succ k)) Ξ΄) Ξ³ = β₯β₯-functor (Ξ» x β IfZero-succ (prβ x) (prβ x)) (binary-choice x Mβ-β) adequacy-pred : {n : β} {Ξ : Context n} β (M : PCF Ξ ΞΉ) β (d : β¨ γ Ξ γ β» β©) β (f : β {A} β (x : Ξ β A) β PCF β¨β© A) β adequate ΞΉ (prβ β¦ M β§β d) (subst f M) β adequate ΞΉ (prβ β¦ Pred M β§β d) (subst f (Pred M)) adequacy-pred M d f (β , rel) = β , g where g : (p : is-defined (prβ β¦ Pred M β§β d)) β subst f (Pred M) β numeral (value (prβ β¦ Pred M β§β d) p) g p = β₯β₯-functor pred-lemma (rel p) adequacy-ifzero : {n : β} {Ξ : Context n} (M : PCF Ξ ΞΉ) (Mβ : PCF Ξ ΞΉ) (Mβ : PCF Ξ ΞΉ) (d : β¨ γ Ξ γ β» β©) (f : β {A} β (x : Ξ β A) β PCF β¨β© A) β adequate ΞΉ (prβ β¦ M β§β d) (subst f M) β adequate ΞΉ (prβ β¦ Mβ β§β d) (subst f Mβ) β adequate ΞΉ (prβ β¦ Mβ β§β d) (subst f Mβ) β adequate ΞΉ (prβ β¦ IfZero M Mβ Mβ β§β d) (subst f (IfZero M Mβ Mβ)) adequacy-ifzero {n} {Ξ} M Mβ Mβ d f (β , M-rel) Mβ-rel Mβ-rel = β , g where g : (p : is-defined (prβ β¦ IfZero M Mβ Mβ β§β d)) β subst f (IfZero M Mβ Mβ) β numeral (value (prβ β¦ IfZero M Mβ Mβ β§β d) p) g (M-is-defined , Ξ΄) = ifzero-lemma M Mβ Mβ f (M-rel M-is-defined) d M-is-defined Ξ΄ Mβ-rel Mβ-rel lemma7-4 : {n : β} {Ξ : Context n} {Ο : type} (M : PCF Ξ Ο) (d : β¨ γ Ξ γ β» β©) (f : β {A} β (x : Ξ β A) β PCF β¨β© A) (g : β {A} β (x : Ξ β A) β adequate A (extract x d) (f x)) β adequate Ο (prβ β¦ M β§β d) (subst f M) lemma7-4 {n} {Ξ} {.ΞΉ} Zero d f g = β , Ξ» p β β£ zero-id β£ lemma7-4 {n} {Ξ} {.ΞΉ} (Succ M) d f g = adequacy-succ M d f IH where IH : adequate ΞΉ (prβ β¦ M β§β d) (subst f M) IH = lemma7-4 M d f g lemma7-4 {n} {Ξ} {.ΞΉ} (Pred M) d f g = adequacy-pred M d f IH where IH : adequate ΞΉ (prβ β¦ M β§β d) (subst f M) IH = lemma7-4 M d f g lemma7-4 {n} {Ξ} {.ΞΉ} (IfZero M Mβ Mβ) d f g = adequacy-ifzero M Mβ Mβ d f IHβ IHβ IHβ where IHβ : adequate ΞΉ (prβ β¦ M β§β d) (subst f M) IHβ = lemma7-4 M d f g IHβ : adequate ΞΉ (prβ β¦ Mβ β§β d) (subst f Mβ) IHβ = lemma7-4 Mβ d f g IHβ : adequate ΞΉ (prβ β¦ Mβ β§β d) (subst f Mβ) IHβ = lemma7-4 Mβ d f g lemma7-4 {n} {Ξ} {.(_ β _)} (Ζ {n} {Ξ} {Ο} {Ο} M) d f g dβ Mβ x = Ξ³ where IH : adequate Ο (prβ β¦ M β§β (d , dβ)) (subst (extend-with Mβ f) M) IH = lemma7-4 M (d , dβ) (extend-with Mβ f) extended-g where extended-g : {A : type} (xβ : (Ξ β Ο) β A) β adequate A (extract xβ (d , dβ)) (extend-with Mβ f xβ) extended-g Z = x extended-g (S xβ) = g xβ i : subst (extend-with Mβ f) M οΌ subst (exts f) M [ Mβ ] i = subst-ext M Mβ f ii : subst (extend-with Mβ f) M βΜ° (subst f (Ζ M) Β· Mβ) ii = transportβ»ΒΉ (Ξ» - β - βΜ° (subst f (Ζ M) Β· Mβ)) i Ξ²-βΜ° Ξ³ : adequate Ο (prβ (prβ β¦ Ζ M β§β d) dβ) (subst f (Ζ M) Β· Mβ) Ξ³ = adequacy-step (subst (extend-with Mβ f) M) (subst f (Ζ M) Β· Mβ) ii (prβ (prβ β¦ Ζ M β§β d) dβ) IH lemma7-4 (_Β·_ {n} {Ξ} {Ο} {Οβ} M Mβ) d f g = IHβ (prβ β¦ Mβ β§β d) (subst f Mβ) IHβ where IHβ : adequate (Ο β Οβ) (prβ β¦ M β§β d) (subst f M) IHβ = lemma7-4 M d f g IHβ : adequate Ο (prβ β¦ Mβ β§β d) (subst f Mβ) IHβ = lemma7-4 Mβ d f g lemma7-4 {n} {Ξ} {Ο} (v x) d f g = g x lemma7-4 {n} {Ξ} {Ο} (Fix M) d f g = lemma7-3 (subst f M) (prβ β¦ M β§β d) IH where IH : (dβ : β¨ β¦ Ο β§ β» β©) (Mβ : PCF β¨β© Ο) β adequate Ο dβ Mβ β adequate Ο (prβ (prβ β¦ M β§β d) dβ) (subst (Ξ» {A} β f) M Β· Mβ) IH = lemma7-4 M d f g adequacy : (M : PCF β¨β© ΞΉ) (n : β) β prβ β¦ M β§β β οΌ Ξ· n β M β numeral n adequacy M n p = prβ iv β where i : adequate ΞΉ (prβ β¦ M β§β β) (subst ids M) i = lemma7-4 M β ids f where f : β {A} β (x : β¨β© β A) β adequate A (extract x β) (v x) f x = π-elim (β-gives-Context-is-non-empty x) ii : subst ids M οΌ M ii = sub-id M iii : adequate ΞΉ (prβ β¦ M β§β β) M iii = transport (adequate ΞΉ (prβ β¦ M β§β β)) ii i iv : adequate ΞΉ (Ξ· n) M iv = transport (Ξ» - β adequate ΞΉ - M) p iii \end{code}