表示的意味論
表示的意味論は数学的構造によって形式化され、それはプログラミング言語の操作的意味論や表現とは独立している。
観測される動作が異なるプログラムは表示も異なる。
全ての要素は有限要素の順序列の上限である: 任意の要素に有限の計算手順で到達することを意味している。
領域は downward closed である
システム S に関する数学的表示は、初期の空の表示 ⊥S から始めて、表示近似関数 progressionS を使って S の表示(意味)を構築していくことでよりよい近似を作っていくことで構築される。これは以下のように表される:
DenoteS ≡ ∨i∈ω progressionS(⊥S).
ここで、progressionS は「単調」であるべきで、x≤y であるとき progressionS(x)≤progressionS(y) である。さらに一般化すると次のように表される。
もし ∀i∈ω xi≤xi+1 ならば progressionS(∨i∈ω xi) = ∨i∈ω progressionS(xi)
このような progressionS の特徴を ω-連続と呼ぶ。
表示的意味論では、DenoteS の方程式に従って表示(意味)を作成可能かどうかを主題とする。計算領域理論の基本的定理は、progressionS が ω-連続ならば、DenoteS が存在するというものである。
そこで、progressionS が ω-連続であることから以下が成り立つ:
progressionS(DenoteS) = DenoteS
これはつまり、DenoteS が progressionS の「不動点; fixed point」であることを意味する。
さらに、この不動点は progressionS の不動点の中で極小である。
関数型言語の表示的意味論の実例を次節に示す。
各システム S について、その意味論には progressionS 関数が存在する。システム S の表示(意味)は、∨i∈ωprogressionS(⊥S) であり、⊥S は s の初期構成である。