表示的意味論

計算機科学における表示的意味論（ひょうじてきいみろん、英: Denotational Semantics）とは、プログラミング言語の意味を形式的に記述する形式意味論（プログラム意味論）の一つの枠組みである。初期には「数理的意味論」（mathematical semantics）、「スコット＝ストレイチー意味論」（Scott–Strachey semantics）のようにも呼ばれた。表示的意味論では、記述された言語の各語句に、表示的意味（denotation）、すなわちプログラム全体の意味に対してその中に現れる各語句が担う役割を表す数学的対象（object）、を与える方法をとる^[1]。

表示的意味論の起源は、1960年代のクリストファー・ストレイチーやデイナ・スコットの研究である。ストレイチーやスコットが開発した本来の表示的意味論は、プログラムの表示（意味）を入力を出力にマッピングする関数に変換するものである。後にこれはプログラムの表示（意味）を定義するには非力であることが証明され、例えば再帰定義関数・データ構造を表現できないことが判明した。これを解決するため、スコットはより汎用的な領域理論に基づいた表示的意味論を提案した^[2]。その後、研究者らはPower Domainsに基づいた手法を提案し、並行システムの意味論の困難さを克服する努力をしている^[3]。

概要

表示的意味論は、クリストファー・ストレイチーが1964年に形式言語記述言語（formal language description language）に関するIFIP作業部会のために書いた論文"Towards a formal semantics"に始まる。この論文は、抽象構文を関数（便宜的に関数は型無しラムダ計算で表現されていた）へ写像し、関数の合成で定義された意味関数を導入し、不動点組合せ演算子 Y を使ってループの意味を表示させるものであった。ここで理論的に問題であったのは、プログラムの要素の表示的意味（denotation）は、形式的には、型無しのラムダ計算（type-free lambda calculus）に写像される形になっていたが、その肝心の型無しのラムダ計算の数学的モデルがわかっていないということであった。これは、すなわち、不動点組合せ演算子 Y は操作的に規則として解釈することはできたが、表示的意味としてなにか関数を表すと考えることができなかった^[4]。

1969年に至って、ストレイチーの理論に興味を抱いたデイナ・スコットは、ストレイチーとの共同研究の末、当初期待していなかった型無しラムダ計算のモデルについて、結局、型無しラムダ計算が実は数学的モデルを持つことを発見することになった。その後すぐに、スコットは、意味の記述法の基礎となる領域理論を構築した。

不動点意味論

表示的意味は、システムが行うことを表現する数学的オブジェクトを探すことに関心がある。この理論は計算の数学的領域（ドメイン）を利用する。そのような領域の例として完備半順序集合などがある。

関係 x≤y は、x が y に計算的に発展する可能性があることを意味する。表示が完備半順序集合の要素ならば、例えば f≤g は f が定義されている全ての値について g と等しいことを意味する。

計算領域は次のような特徴を持つ:

下限の存在: 領域には必ず ⊥ で表される要素が含まれ、領域内の任意の要素 x について ⊥≤x が成り立つ。
上限の存在: 計算を続けると表示は洗練されるが、限界を持つべきである。そのため、 $\forall i\in \omega$ $x_{i}\leq x_{i+1}$ としたとき、上限 $\vee _{i\in \omega }x_{i}$ が存在する。これを $\omega$ -完全と呼ぶ。
有限要素は可算: 有向集合 A について ∨A が存在し $x\leq \vee A$ であるとき、 $x\leq a$ であるような $a\in A$ が存在する。そのとき、要素 x は有限であるという（領域理論的に言えば、isolated）。換言すれば、x に到達あるいは x を超えるのに有限のプロセスで可能であるなら、x は有限である。
全ての要素は有限要素の順序列の上限である: 任意の要素に有限の計算手順で到達することを意味している。
領域は downward closed である

システム S に関する数学的表示は、初期の空の表示 ⊥_S から始めて、表示近似関数 progression_S を使って S の表示（意味）を構築していくことでよりよい近似を作っていくことで構築される。これは以下のように表される:

Denote_S ≡ ∨_i∈ω progression_Sⁱ(⊥_S).

ここで、progression_S は「単調」であるべきで、x≤y であるとき progression_S(x)≤progression_S(y) である。さらに一般化すると次のように表される。

もし ∀i∈ω x_i≤x_i+1 ならば progression_S(∨_i∈ω x_i) = ∨_i∈ω progression_S(x_i)

このような progression_S の特徴を ω-連続と呼ぶ。

表示的意味論では、Denote_S の方程式に従って表示（意味）を作成可能かどうかを主題とする。計算領域理論の基本的定理は、progression_S が ω-連続ならば、Denote_S が存在するというものである。

そこで、progression_S が ω-連続であることから以下が成り立つ:

progression_S(Denote_S) = Denote_S

これはつまり、Denote_S が progression_S の「不動点; fixed point」であることを意味する。

さらに、この不動点は progression_S の不動点の中で極小である。

関数型言語の表示的意味論の実例を次節に示す。

階乗関数の例

関数 factorial が以下のように定義されているとする:

factorial ≡ λ(n)if (n==0)then 1 else n*factorial(n-1)

factorial の graph とは、引数と値のペアの順序集合であり、以下のようになる:

graph(factorial) = {<n, factorial(n)>|n∈ω} = {<0,1>,<1,1>,<2,2>,<3,6>,<4,24>…}

factorial プログラムの表示（意味） Denote_factorial は、以下のように構築される:

Denote_factorial = graph(factorial) = ∪_i∈ω progression_factorialⁱ({})

ここで

progression_factorial(g) ≡ λ(n)if (n==0)then 1 else n*g(n-1)

ただし、progression_factorial は不動点演算子であり、極小不動点 Denote_factorial は次のようになる:

Denote_factorial = progression_factorial(Denote_factorial)

また、progression_factorial は、ω-連続である。

完全抽象化

プログラムの表示的意味論と操作的意味論が合致するかどうかを論じる際に、完全抽象化の概念が関わってくる。完全抽象化の特徴は次の通りである。

抽象性: 表示的意味論は数学的構造によって形式化され、それはプログラミング言語の操作的意味論や表現とは独立している。
正当性: 観測される動作が異なるプログラムは表示も異なる。
完全性: 表示が異なるプログラムは観測される動作も異ならなければならない。

その他に表示的意味論と操作的意味論について保持するのが望ましい特徴は以下の通りである。

構築可能性: 意味モデルは、直観的に構成可能な要素のみから構築可能であるべきである。形式的に表現すれば、全要素は有限要素の有向集合の上限でなければならない。
進歩性: 各システム S について、その意味論には progression_S 関数が存在する。システム S の表示（意味）は、∨_i∈ωprogression_Sⁱ(⊥_S) であり、⊥_S は s の初期構成である。
完全抽象性: 意味モデルのあらゆる射はプログラムの表示であるべきである。

表示的意味論での長年の懸案は、再帰データ型のある場合の完全抽象化であった。特に再帰に利用可能な自然数型である。この問題は従来、PCF（プログラミング言語）（英語版）の意味論の構築の問題として捉えられてきた。1990年代、ゲーム意味論によって PCF の完全抽象モデルが構築され、表示的意味論の手法に根本的な変化をもたらした。

合成性

プログラミング言語の表示的意味論の重要な観点として、合成性（Compositionality）がある。合成性とは、プログラムの表示が、各部分の表示の組み合わせで構築されることを意味する。例えば、式 "<expression₁> + <expression₂>" を考えて見よう。この場合の合成性は、<expression₁> の意味と <expression₂> の意味から "<expression₁> + <expression₂>" の意味が導かれることを意味する。

並行性の表示的意味論

並行性に関する表示的意味論としては、プロセス代数に基づくものなどがある。表示的意味論の並行性への拡張は困難であることが証明されている（無制限の非決定性参照）。

計算機科学の他の領域との関連

表示的意味論は領域理論を使って型を領域と解釈する。領域理論はモデル理論からの派生と見ることもでき、そこから型理論や圏論とも関連付けられる。計算機科学では、抽象解釈、プログラム検証、関数プログラミングと関係が深く、モナド（Monads）の概念などとも関連がある。また、継続の概念は、歴史的には手続き型プログラムの制御フロー（goto文）などの意味論を与えるために見出された^[5]。

出典・脚注

^ Mosses(1990 p.563
^ S. Abramsky and A. Jung: Domain theory. In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, vol. III. Oxford University Press, 1994. (ISBN 0-19-853762-X)
^ Gordon Plotkin. A powerdomain construction SIAM Journal of Computing. September 1976.
^ Mosses(1990) pp.609-610
^ Reynolds, John C. (1993-11-01). “The discoveries of continuations” (英語). LISP and Symbolic Computation 6 (3): 233–247. doi:10.1007/BF01019459. ISSN 1573-0557. https://www.cs.cmu.edu/afs/cs/user/jcr/ftp/histcont.pdf.

参考文献

Milne, R.E.; Strachey, C. (1976). A theory of programming language semantics. ISBN 978-1-5041-2833-9
Stoy, Joseph E. (1977). Denotational Semantics: The Scott-Strachey Approach to Programming Language Semantics. MIT Press. ISBN 978-0262191470
Dijkstra, Edsger W. (1976). A Discipline of Programming. Prentice-Hall series in automatic computation. Englewood Cliffs, N.J.. ISBN 0-13-215871-X. OCLC 1958445
Apt, Krzysztof R.; de Bakker, J. W. (1976) (English). Exercises in denotational semantics. Afdeling Informatica. Amsterdam: Mathematisch Centrum. OCLC 63400684
De Bakker, J.W. (1976). “Least Fixed Points Revisited” (英語). Theoretical Computer Science 2 (2): 155–181. doi:10.1016/0304-3975(76)90031-1. https://linkinghub.elsevier.com/retrieve/pii/0304397576900311.
Smyth, Michael B. (1978). “Power domains”. J. Comput. Syst. Sci. 16: 23–36. doi:10.1016/0022-0000(78)90048-X.
Hoare, C. A. R. (1978-08-01). “Communicating Sequential Processes”. Communications of the ACM 21 (8): 666–677. doi:10.1145/359576.359585. ISSN 0001-0782. https://doi.org/10.1145/359576.359585.
Milne, George; Milner, Robin (1979-04-01). “Concurrent Processes and Their Syntax”. Journal of the ACM 26 (2): 302–321. doi:10.1145/322123.322134. ISSN 0004-5411. https://doi.org/10.1145/322123.322134.
Francez, Nissim; Hoare, C.A.R; Lehmann, Daniel J; De Roever, Willem P (1979). “Semantics of nondeterminism, concurrency, and communication” (English). Journal of Computer and System Sciences 19 (3): 290–308. ISSN 0022-0000. OCLC 4640928019. https://hdl.handle.net/1874/24888.
Kahn, G. (1979-06-01) (英語). Semantics of concurrent computation: proceedings of the international symposium, Évian, France, July 2-4, 1979. Lecture Notes in Computer Science. Berlin: Springer Berlin Heidelberg. ISBN 978-3-540-09511-8. LCCN 79-15956. OCLC 5101221. https://books.google.com/books?id=lLgqAQAAIAAJ
- Lynch, Nancy; Fischer, Michael J. (1979). “On describing the behavior of distributed systems”. Kahn 1979
- Schwartz, Jerald (1979). “Denotational semantics of parallelism”. Kahn 1979
- Wadge, William (1979). “An extensional treatment of dataflow deadlock”. Kahn 1979
Back, Ralph-Johan (1980). de Bakker, Jaco. ed (英語). Semantics of unbounded nondeterminism. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 51–63. doi:10.1007/3-540-10003-2_59. ISBN 978-3-540-39346-7. OCLC 476017025. https://link.springer.com/chapter/10.1007%2F3-540-10003-2_59
Park, David (1980). Bjøorner, Dines. ed. On the semantics of fair parallelism. 86. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 504–526. doi:10.1007/3-540-10007-5_47. ISBN 978-3-540-10007-2. http://link.springer.com/10.1007/3-540-10007-5_47
Clinger, William Douglas (1981-05-01). “Foundations of Actor Semantics” (英語). AI Technical Reports (1964 - 2004) (Massachusetts Institute of Technology). AITR-633. https://hdl.handle.net/1721.1/6935.
Allison, L. (1986). A Practical Introduction to Denotational Semantics. Cambridge University Press. ISBN 978-0-521-31423-7. https://books.google.com/books?id=uIdF11msK58C
America, P.; de Bakker, J.; Kok, J.N.; Rutten, J. (1989). “Denotational semantics of a parallel object-oriented language”. Information and Computation 83 (2): 152–205. doi:10.1016/0890-5401(89)90057-6. https://ir.cwi.nl/pub/1602.
Schmidt, David A. (1994). The Structure of Typed Programming Languages. MIT Press. ISBN 978-0-262-69171-0
Korff, Martin; Ribeiro, Leila (1995-01-01). “Concurrent Derivations as Single Pushout Graph Grammar Processes” (英語). Electronic Notes in Theoretical Computer Science 2: 177–186. doi:10.1016/S1571-0661(05)80194-X. ISSN 1571-0661. https://www.sciencedirect.com/science/article/pii/S157106610580194X.
Thati, Prasanna; Talcott, Carolyn; Agha, Gul (2004). Rattray, Charles; Maharaj, Savitri; Shankland, Carron. eds. “Techniques for Executing and Reasoning about Specification Diagrams” (英語). Algebraic Methodology and Software Technology (Berlin, Heidelberg: Springer): 521–536. doi:10.1007/978-3-540-27815-3_39. ISBN 978-3-540-27815-3. https://link.springer.com/chapter/10.1007%2F978-3-540-27815-3_39.
Baeten, J. C. M. (2005-05-23). “A brief history of process algebra” (英語). Theoretical Computer Science 335 (2): 131–146. doi:10.1016/j.tcs.2004.07.036. ISSN 0304-3975. https://www.sciencedirect.com/science/article/pii/S0304397505000307.
Baeten, J. C. M. (1989). “Algebra and communicating processes” (English). AMAST. Algebraic methodology and software technology. 1st international conference : proceedings, Iowa, USA, 1989: 35–38. https://research.tue.nl/en/publications/algebra-and-communicating-processes.
Jifeng, He; Hoare, C. A. R. (2005). Van Hung, Dang; Wirsing, Martin. eds. “Linking Theories of Concurrency” (英語). Theoretical Aspects of Computing – ICTAC 2005 (Berlin, Heidelberg: Springer): 303–317. doi:10.1007/11560647_20. ISBN 978-3-540-32072-2. https://link.springer.com/chapter/10.1007%2F11560647_20.
Aceto, Luca (June 2005). Gordon, Andrew D.. ed. Algebraic Process Calculi: The First Twenty Five Years and Beyond. BRICS Notes Series. This volume contains short contributions from the workshop on "Algebraic Process Calculi: The First Twenty Five Years and Beyond", held in the period August 1-5, 2005, at the University Residential Centre of Bertinoro, Forlì, Italy. BRICS publications. ISSN 0909-3206. NS-05-3. https://www.brics.dk/NS/05/3/BRICS-NS-05-3.pdf
Roscoe, Bill (April 2005). The Theory and Practice of Concurrency. Prentice-Hall. http://www.cs.ox.ac.uk/people/bill.roscoe/publications/68b.pdf
Mosses, Peter D. (1990-01-01). Van leeuwen, JAN. ed. “CHAPTER 11 - Denotational Semantics” (英語). Handbook of theoretical computer science Vol.B : Formal Models and Semantics (Amsterdam: Elsevier): 575–631. doi:10.1016/b978-0-444-88074-1.50016-0. ISBN 978-0-444-88074-1. https://www.sciencedirect.com/science/article/pii/B9780444880741500160.
- （邦訳：Peter D. Mosses（著）、山田眞市（編）「表示的意味論」『コンピュータ基礎理論ハンドブックⅡ 形式モデルと意味論』、丸善株式会社、1994年。）

外部リンク

Denotational Semantics by Lloyd Allison
Structure of Programming Languages I: Denotational Semantics by Wolfgang Schreiner
Denotational Semantics: A Methodology for Language Development by David Schmidt
Presentation by Josh Cogliati
HQL by H. Hernan Moraldo – 小型言語の完全な表示的意味論