Semantics of Loops lwhile b do cllcomm is a fixed-point of Fgf∈Σ→Σ，Aoe.i(lIccomm）it=true otherwise However,not every F∈(E→∑)→(E→∑)has a fixed-point,, and some may have more than one. We need to lay some structures over the set∑→∑i,to ensure that F has at least one fixed-point. Denotational Semantics
Semantics of Loops ~while b do ccomm is a fixed-point of F def = λf ∈ Σ → Σ⊥. λσ ∈ Σ. ( fy(~ccomm σ) if ~bboolexp σ = true σ otherwise However, not every F ∈ (Σ → Σ⊥) → (Σ → Σ⊥) has a fixed-point, and some may have more than one. We need to lay some structures over the set Σ → Σ⊥, to ensure that F has at least one fixed-point. Denotational Semantics
Partially Ordered Sets A relation p is reflexive on S iff Vx E S.xpx transitive iff xpyAypz=xpz antisymmetric iff xpyaypxx=y symmetric iff xpy=ypx Eis a preorder on S iff is reflexive on S and tansitive is a partial order on s iff Eis a preorder on S and antisymmetric A posel S S with a partial order on S A discretely ordered S S with lds as a partial order on S f is monotone from S to T iff fST and Vx.yES.x三y=fxg1V y is upper bound of X √xEX.X三y where y e S and X三S 4口，8,4E，4至+39a0 Denotational Semantics
Partially Ordered Sets A relation ρ is reflexive on S iff ∀x ∈ S.x ρ x transitive iff x ρ y ∧ y ρ z ⇒ x ρ z antisymmetric iff x ρ y ∧ y ρ x ⇒ x = y symmetric iff x ρ y ⇒ y ρ x v is a preorder on S iff v is reflexive on S and tansitive v is a partial order on S iff v is a preorder on S and antisymmetric A poset S S with a partial order v on S A discretely ordered S S with IdS as a partial order on S f is monotone from S to T iff f ∈ S → T and ∀x, y ∈ S. x v y ⇒ f x v 0 f y y is upper bound of X ∀x ∈ X. x v y where y ∈ S and X ⊆ S Denotational Semantics
Partially Ordered Sets A relation p is reflexive on S iff Vx E S.xpx transitive iff xpyAypz=xpz antisymmetric iff xpyaypxx=y symmetric iff xpy→ypx Eis a preorder on S iff is reflexive on S and tansitive is a partial order on S iff is a preorder on S and antisymmetric A poset S S with a partial order E on S A discretely ordered S S with lds as a partial order on S f is monotone from S to T iff f∈S→T andx.yES.x三y=IxC fy y is upper bound of X XEX.X三y where yE S and Xc S Denotational Semantics
Partially Ordered Sets A relation ρ is reflexive on S iff ∀x ∈ S.x ρ x transitive iff x ρ y ∧ y ρ z ⇒ x ρ z antisymmetric iff x ρ y ∧ y ρ x ⇒ x = y symmetric iff x ρ y ⇒ y ρ x v is a preorder on S iff v is reflexive on S and tansitive v is a partial order on S iff v is a preorder on S and antisymmetric A poset S S with a partial order v on S A discretely ordered S S with IdS as a partial order on S f is monotone from S to T iff f ∈ S → T and ∀x, y ∈ S. x v y ⇒ f x v 0 f y y is upper bound of X ∀x ∈ X. x v y where y ∈ S and X ⊆ S Denotational Semantics
Partially Ordered Sets A relation p is reflexive on S iff Vx E S.xpx transitive iff xpyAypz→xPZ antisymmetric iff xpyaypxx=y symmetric iff xpy=ypx Eis a preorder on S iff is reflexive on S and tansitive is a partial order on S iff is a preorder on S and antisymmetric A posel S S with a partial order on S A discretely ordered S S with lds as a partial order on S f is monotone from S to T iff fST and Vx.yES.x三y=fxg1 y is upper bound of X VxEX.X三y where y e S and X三S 4口日+三4元+39a0 Denotational Semantics
Partially Ordered Sets A relation ρ is reflexive on S iff ∀x ∈ S.x ρ x transitive iff x ρ y ∧ y ρ z ⇒ x ρ z antisymmetric iff x ρ y ∧ y ρ x ⇒ x = y symmetric iff x ρ y ⇒ y ρ x v is a preorder on S iff v is reflexive on S and tansitive v is a partial order on S iff v is a preorder on S and antisymmetric A poset S S with a partial order v on S A discretely ordered S S with IdS as a partial order on S f is monotone from S to T iff f ∈ S → T and ∀x, y ∈ S. x v y ⇒ f x v 0 f y y is upper bound of X ∀x ∈ X. x v y where y ∈ S and X ⊆ S Denotational Semantics
Partially Ordered Sets A relation p is reflexive on S iff Vx E S.xpx transitive iff xpyAypz=xpz antisymmetric iff xpyaypxx=y symmetric iff xpy→ypx Eis a preorder on S iff is reflexive on S and tansitive is a partial order on S iff is a preorder on S and antisymmetric A poset S S with a partial order on S A discretely ordered S S with lds as a partial order on S f is monotone from S to T iff f∈S→T andx.yES.x三y=IxC fy y is upper bound of X XEX.X三y where yE S and Xc S Denotational Semantics
Partially Ordered Sets A relation ρ is reflexive on S iff ∀x ∈ S.x ρ x transitive iff x ρ y ∧ y ρ z ⇒ x ρ z antisymmetric iff x ρ y ∧ y ρ x ⇒ x = y symmetric iff x ρ y ⇒ y ρ x v is a preorder on S iff v is reflexive on S and tansitive v is a partial order on S iff v is a preorder on S and antisymmetric A poset S S with a partial order v on S A discretely ordered S S with IdS as a partial order on S f is monotone from S to T iff f ∈ S → T and ∀x, y ∈ S. x v y ⇒ f x v 0 f y y is upper bound of X ∀x ∈ X. x v y where y ∈ S and X ⊆ S Denotational Semantics