表示的意味論
表示的意味論は領域理論を使って型を領域と解釈する。領域理論はモデル理論からの派生と見ることもでき、そこから型理論や圏論とも関連付けられる。計算機科学では、抽象解釈、プログラム検証、関数プログラミングと関係が深く、モナド(Monads)の概念などとも関連がある。また、継続の概念は、歴史的には手続き型プログラムの制御フロー(goto文)などの意味論を与えるために見出された。
プログラミング言語の表示的意味論の重要な観点として、合成性(Compositionality)がある。合成性とは、プログラムの表示が、各部分の表示の組み合わせで構築されることを意味する。例えば、式 "<expression1> + <expression2>" を考えて見よう。この場合の合成性は、<expression1> の意味と <expression2> の意味から "<expression1> + <expression2>" の意味が導かれることを意味する。
表示的意味は、システムが行うことを表現する数学的オブジェクトを探すことに関心がある。この理論は計算の数学的領域(ドメイン)を利用する。そのような領域の例として完備半順序集合などがある。
関係 x≤y は、x が y に計算的に発展する可能性があることを意味する。表示が完備半順序集合の要素ならば、例えば f≤g は f が定義されている全ての値について g と等しいことを意味する。
計算領域は次のような特徴を持つ:
下限の存在: 領域には必ず ⊥ で表される要素が含まれ、領域内の任意の要素 x について ⊥≤x が成り立つ。
上限の存在: 計算を続けると表示は洗練されるが、限界を持つべきである。そのため、 ∀ i ∈ ω {\displaystyle \forall i\in \omega } x i ≤ x i + 1 {\displaystyle x_{i}\leq x_{i+1}} としたとき、上限 ∨ i ∈ ω x i {\displaystyle \vee _{i\in \omega }x_{i}} が存在する。これを ω {\displaystyle \omega } -完全と呼ぶ。
有限要素は可算: 有向集合 A について ∨A が存在し x ≤ ∨ A {\displaystyle x\leq \vee A} であるとき、 x ≤ a {\displaystyle x\leq a} であるような a ∈ A {\displaystyle a\in A} が存在する。そのとき、要素 x は有限であるという(領域理論的に言えば、isolated)。換言すれば、x に到達あるいは x を超えるのに有限のプロセスで可能であるなら、x は有限である。