Brendan Hart 2019-2020 We define PCF types and terms, substitution as in PLFA, and the big step semantics. https://plfa.github.io/ \begin{code} {-# OPTIONS --safe --without-K #-} open import UF.PropTrunc module PCF.Lambda.AbstractSyntax (pt : propositional-truncations-exist) where open PropositionalTruncation pt open import MLTT.Spartan data Vec (X : ๐คโฬ ) : โ โ ๐คโ ฬ where โจโฉ : Vec X zero _โ_ : {n : โ} โ Vec X n โ X โ Vec X (succ n) data Fin : (n : โ) โ ๐คโฬ where zero : โ {n} โ Fin (succ n) succ : โ {n} โ Fin n โ Fin (succ n) data type : ๐คโฬ where ฮน : type _โ_ : type โ type โ type infixr 1 _โ_ Context : โ โ ๐คโฬ Context = Vec type data _โ_ : {n : โ} โ Context n โ type โ ๐คโฬ where Z : โ {n : โ} {ฮ : Context n} {ฯ : type} โ (ฮ โ ฯ) โ ฯ S : โ {n : โ} {ฮ : Context n} {ฯ ฯ : type} โ ฮ โ ฯ โ (ฮ โ ฯ) โ ฯ data PCF : {n : โ} (ฮ : Context n) (ฯ : type) โ ๐คโฬ where Zero : {n : โ} {ฮ : Context n} โ PCF ฮ ฮน Succ : {n : โ} {ฮ : Context n} โ PCF ฮ ฮน โ PCF ฮ ฮน Pred : {n : โ} {ฮ : Context n} โ PCF ฮ ฮน โ PCF ฮ ฮน IfZero : {n : โ} {ฮ : Context n} โ PCF ฮ ฮน โ PCF ฮ ฮน โ PCF ฮ ฮน โ PCF ฮ ฮน ฦ : {n : โ} {ฮ : Context n} {ฯ ฯ : type} โ PCF (ฮ โ ฯ) ฯ โ PCF ฮ (ฯ โ ฯ) _ยท_ : {n : โ} {ฮ : Context n} {ฯ ฯ : type} โ PCF ฮ (ฯ โ ฯ) โ PCF ฮ ฯ โ PCF ฮ ฯ v : {n : โ} {ฮ : Context n} {ฯ : type} โ ฮ โ ฯ โ PCF ฮ ฯ Fix : {n : โ} {ฮ : Context n} {ฯ : type} โ PCF ฮ (ฯ โ ฯ) โ PCF ฮ ฯ infixl 1 _ยท_ Fin-0-is-empty : ยฌ Fin 0 Fin-0-is-empty i = Fin-gives-is-nonzero i where is-nonzero : โ โ ๐คโฬ is-nonzero 0 = ๐ is-nonzero (succ n) = ๐ Fin-gives-is-nonzero : {n : โ} โ Fin n โ is-nonzero n Fin-gives-is-nonzero zero = โ Fin-gives-is-nonzero (succ i) = โ Context-is-non-empty : {n : โ} โ Context n โ ๐คโฬ Context-is-non-empty โจโฉ = ๐ Context-is-non-empty (ฮ โ ฯ) = ๐ โ-gives-Context-is-non-empty : {n : โ} {ฮ : Context n} {ฯ : type} โ ฮ โ ฯ โ Context-is-non-empty ฮ โ-gives-Context-is-non-empty Z = โ โ-gives-Context-is-non-empty (S x) = โ lookup : {n : โ} โ Context n โ Fin n โ type lookup โจโฉ i = ๐-elim (Fin-0-is-empty i) lookup (ฮ โ x) zero = x lookup (ฮ โ x) (succ n) = lookup ฮ n count : {n : โ} {ฮ : Context n} โ (f : Fin n) โ ฮ โ lookup ฮ f count {0} {โจโฉ} i = ๐-elim (Fin-0-is-empty i) count {succ n} {ฮ โ x} zero = Z count {succ n} {ฮ โ x} (succ f) = S (count f) ext : โ {m n} {ฮ : Context m} {ฮ : Context n} โ (โ {A} โ ฮ โ A โ ฮ โ A) โ (โ {ฯ A} โ (ฮ โ ฯ) โ A โ (ฮ โ ฯ) โ A) ext f Z = Z ext f (S t) = S (f t) rename : โ {m n} {ฮ : Context m} {ฮ : Context n} โ (โ {A} โ ฮ โ A โ ฮ โ A) โ (โ {A} โ PCF ฮ A โ PCF ฮ A) rename f Zero = Zero rename f (Succ t) = Succ (rename f t) rename f (Pred t) = Pred (rename f t) rename f (IfZero t tโ tโ) = IfZero (rename f t) (rename f tโ) (rename f tโ) rename f (ฦ t) = ฦ (rename (ext f) t) rename f (t ยท tโ) = rename f t ยท rename f tโ rename f (v x) = v (f x) rename f (Fix t) = Fix (rename f t) exts : โ {m n} {ฮ : Context m} {ฮ : Context n} โ (โ {A} โ ฮ โ A โ PCF ฮ A) โ (โ {ฯ A} โ (ฮ โ ฯ) โ A โ PCF (ฮ โ ฯ) A) exts f Z = v Z exts f (S t) = rename (_โ_.S) (f t) subst : โ {m n} {ฮ : Context m} {ฮ : Context n} โ (โ {A} โ ฮ โ A โ PCF ฮ A) โ (โ {A} โ PCF ฮ A โ PCF ฮ A) subst f Zero = Zero subst f (Succ t) = Succ (subst f t) subst f (Pred t) = Pred (subst f t) subst f (IfZero t tโ tโ) = IfZero (subst f t) (subst f tโ) (subst f tโ) subst f (ฦ t) = ฦ (subst (exts f) t) subst f (t ยท tโ) = subst f t ยท subst f tโ subst f (v x) = f x subst f (Fix t) = Fix (subst f t) extend-with : {n : โ} {m : โ} {ฮ : Context n} {ฮ : Context m} {A : type} (N : PCF ฮ A) โ (โ {A} โ ฮ โ A โ PCF ฮ A) โ (โ {B} โ (ฮ โ A) โ B โ PCF ฮ B) extend-with N f Z = N extend-with N f (S x) = f x replace-first : {n : โ} (A : type) (ฮ : Context n) (N : PCF ฮ A) โ (โ {B} โ (ฮ โ A) โ B โ PCF ฮ B) replace-first A ฮ N Z = N replace-first A ฮ N (S t) = v t _[_] : {n : โ} {ฮ : Context n} {ฯ A : type} โ PCF (ฮ โ A) ฯ โ PCF ฮ A โ PCF ฮ ฯ _[_] {n} {ฮ} {ฯ} {A} M N = subst (replace-first A ฮ N) M numeral : โ {n} {ฮ : Context n} โ โ โ PCF ฮ ฮน numeral zero = Zero numeral (succ n) = Succ (numeral n) peano-axiom-for-PCF : โ {n ฮ k} โ numeral {n} {ฮ} zero โ numeral (succ k) peano-axiom-for-PCF {n} {ฮ} {k} p = transport f p โ where f : PCF ฮ ฮน โ ๐คโฬ f Zero = ๐ f (Succ _) = ๐ f (Pred _) = ๐ f (IfZero _ _ _) = ๐ f (_ ยท _) = ๐ f (v _) = ๐ f (Fix _) = ๐ \end{code}