表示的意味論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/30 16:28 UTC 版)
ナビゲーションに移動 検索に移動計算機科学における表示的意味論（ひょうじてきいみろん、英: 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 が成り立つ。
- 上限の存在: 計算を続けると表示は洗練されるが、限界を持つべきである。そのため、
出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。- 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.
- 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.
- 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.
- 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.
- 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
- 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
- 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
- Clinger, William Douglas (1981-05-01). “Foundations of Actor Semantics” (英語). AI Technical Reports (1964 - 2004) (Massachusetts Institute of Technology). AITR-633.
- Allison, L. (1986). A Practical Introduction to Denotational Semantics. Cambridge University Press. ISBN 978-0-521-31423-7
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- Roscoe, Bill (April 2005). The Theory and Practice of Concurrency. Prentice-Hall
- 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.
- （邦訳：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 – 小型言語の完全な表示的意味論
表示的意味論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/13 22:25 UTC 版)
「Communicating Sequential Processes」の記事における「表示的意味論」の解説
CSPの主な表示的モデルとして、トレースモデル、安定失敗モデル、失敗/発散モデルの3つがある。プロセス表現とこれらモデルとの意味論的マッピングがCSPの表示的意味論となる。 トレースモデルは、そのプロセスが扱う一連のイベント（トレース）でプロセス表現の意味を定義する。例えば、 t r a c e s ( S T O P ) = { ⟨ ⟩ } {\displaystyle traces\left(STOP\right)=\left\{\langle \rangle \right\}} 何故なら S T O P {\displaystyle STOP} は何のイベントも扱わないから t r a c e s ( a → b → S T O P ) = { ⟨ ⟩ , ⟨ a ⟩ , ⟨ a , b ⟩ } {\displaystyle traces\left(a\rightarrow b\rightarrow STOP\right)=\left\{\langle \rangle ,\langle a\rangle ,\langle a,b\rangle \right\}} 何故ならプロセス ( a → b → S T O P ) {\displaystyle (a\rightarrow b\rightarrow STOP)} は、何のイベントも扱わない場合、イベント a {\displaystyle a} を受け付ける場合、イベント a {\displaystyle a} を受け付けた後でイベント b {\displaystyle b} を受け付ける場合の3つのケースがありうるから より形式的に表せば、プロセス P {\displaystyle P} のトレースモデルでの意味は t r a c e s ( P ) ⊆ Σ ∗ {\displaystyle traces\left(P\right)\subseteq \Sigma ^{\ast }} として定義される。すなわち、 ⟨ ⟩ ∈ t r a c e s ( P ) {\displaystyle \langle \rangle \in traces\left(P\right)} （ t r a c e s ( P ) {\displaystyle traces\left(P\right)} は空のシーケンスを含む） s 1 ⌢ s 2 ∈ t r a c e s ( P ) ⟹ s 1 ∈ t r a c e s ( P ) {\displaystyle s_{1}\smallfrown s_{2}\in traces\left(P\right)\implies s_{1}\in traces\left(P\right)} （ t r a c e s ( P ) {\displaystyle traces\left(P\right)} はプレフィックスで閉じている） ここで、 Σ ∗ {\displaystyle \Sigma ^{\ast }} は考えられる全てのイベントの有限な並びの集合である。 安定失敗モデルはトレースモデルを拒絶集合（refusal set）で拡張したものである。拒絶集合とは、プロセスが実行を拒絶できるイベントの集合 X ⊆ Σ {\displaystyle X\subseteq \Sigma } である。失敗（failure）は ( s , X ) {\displaystyle \left(s,X\right)} という対で表される。ここで s {\displaystyle s} はトレース、 X {\displaystyle X} は拒絶集合であり、トレース s {\displaystyle s} が実行されたときそのプロセスが拒絶するイベント群を表す。安定失敗モデルにおけるプロセスの観測された振る舞いは、 ( t r a c e s ( P ) , f a i l u r e s ( P ) ) {\displaystyle \left(traces\left(P\right),failures\left(P\right)\right)} という対で表される。例えば、 f a i l u r e s ( ( a → S T O P ) ◻ ( b → S T O P ) ) = { ( ⟨ ⟩ , ∅ ) , ( ⟨ a ⟩ , { a , b } ) , ( ⟨ b ⟩ , { a , b } ) } {\displaystyle failures\left(\left(a\rightarrow STOP\right)\Box \left(b\rightarrow STOP\right)\right)=\left\{\left(\langle \rangle ,\emptyset \right),\left(\langle a\rangle ,\left\{a,b\right\}\right),\left(\langle b\rangle ,\left\{a,b\right\}\right)\right\}} f a i l u r e s ( ( a → S T O P ) ⊓ ( b → S T O P ) ) = { ( ⟨ ⟩ , { a } ) , ( ⟨ ⟩ , { b } ) , ( ⟨ a ⟩ , { a , b } ) , ( ⟨ b ⟩ , { a , b } ) } {\displaystyle failures\left(\left(a\rightarrow STOP\right)\sqcap \left(b\rightarrow STOP\right)\right)=\left\{\left(\langle \rangle ,\left\{a\right\}\right),\left(\langle \rangle ,\left\{b\right\}\right),\left(\langle a\rangle ,\left\{a,b\right\}\right),\left(\langle b\rangle ,\left\{a,b\right\}\right)\right\}} 失敗/発散モデルは、失敗モデルを発散（divergence）を扱えるよう拡張したものである。失敗/発散モデルにおけるプロセスは ( f a i l u r e s ⊥ ( P ) , d i v e r g e n c e s ( P ) ) {\displaystyle \left(failures_{\perp }\left(P\right),divergences\left(P\right)\right)} という対で表され、 d i v e r g e n c e s ( P ) {\displaystyle divergences\left(P\right)} は発散を生じさせる全トレースの集合である。また、 f a i l u r e s ⊥ ( P ) = f a i l u r e s ( P ) ∪ { ( s , X ) | s ∈ d i v e r g e n c e s ( P ) } {\displaystyle failures_{\perp }\left(P\right)=failures\left(P\right)\cup \left\{\left(s,X\right)\vert s\in divergences\left(P\right)\right\}} が成り立つ。
※この「表示的意味論」の解説は、「Communicating Sequential Processes」の解説の一部です。
「表示的意味論」を含む「Communicating Sequential Processes」の記事については、「Communicating Sequential Processes」の概要を参照ください。
- 表示的意味論のページへのリンク
