Theory Values

section "Declarative semantics with tables as lists"

text‹
  The semantics that represents function tables as lists is largely obsolete,
  being replaced by the finite set representation. However, the proof
  of equivalence to the intersection type system still uses the version
  based on lists.
›
  
subsection "Definition of values for declarative semantics" 

theory Values
  imports Main Lambda
begin
  
datatype val = VNat nat | VFun "(val × val) list"

type_synonym func = "(val × val) list"

inductive val_le :: "val ⇒ val ⇒ bool" (infix ‹⊑› 52) 
  and fun_le :: "func ⇒ func ⇒ bool" (infix ‹≲› 52) where
  vnat_le[intro!]: "(VNat n) ⊑ (VNat n)" |
  vfun_le[intro!]: "t1 ≲ t2 ⟹ (VFun t1) ⊑ (VFun t2)" |
  fun_le[intro!]: "(∀ v1 v2. (v1,v2) ∈ set t1 ⟶ 
                       (∃ v3 v4. (v3,v4) ∈ set t2 
                        ∧ v1 ⊑ v3 ∧ v3 ⊑ v1 ∧ v2 ⊑ v4 ∧ v4 ⊑ v2))
                   ⟹ t1 ≲ t2"

type_synonym env = "((name × val) list)"

definition env_le :: "env ⇒ env ⇒ bool" (infix ‹⊑› 52) where 
  "ρ ⊑ ρ' ≡ ∀ x v. lookup ρ x = Some v ⟶ (∃ v'. lookup ρ' x = Some v' ∧ v ⊑ v')" 

definition env_eq :: "env ⇒ env ⇒ bool" (infix ‹≈› 50) where
  "ρ ≈ ρ' ≡ (∀ x. lookup ρ x = lookup ρ' x)"

end