表示的意味論

表示的意味論は、プログラムを数学的対象、典型的には構造化されたドメイン上の関数として解釈し、意味の構成的かつ機械に依存しない説明を提供します。

Definition

表示的意味論は、各プログラムに数学的対象（その表示）を割り当てます。これは、その部分の表示から構成的に定義され、再帰はドメインにおける最小不動点を介して解釈されます。

Scope

このトピックでは、各プログラム句が数学的ドメインの要素を示すスコット-ストラッチーのアプローチを扱います。これには、ドメイン理論、完備半順序、連続関数、再帰の最小不動点解釈、および表示的意味が観測可能な振る舞いとどの程度一致するかに関する完全抽象化が含まれます。

Core questions

• 任意の再帰と非停止をモデル化できる数学的構造とは何ですか？
• サブプログラムの意味から、どのようにして意味が構成的に構築されますか？
• 完全抽象化とは何ですか、そしてなぜそれを達成するのが難しいのですか？
• 表示的意味は操作的振る舞いとどのように関連していますか？

Key theories

ドメイン理論と不動点意味論

スコットのドメイン理論は、順序構造と連続関数を提供し、その中で再帰的定義は最小不動点として解釈され、自己参照プログラムに意味を与える問題を解決します。

完全抽象化

プロトキンによるLCFの研究は、表示的等価性が観測的等価性と正確に一致するかどうかという完全抽象化問題を提起し、その後の数十年にわたる研究を促すギャップを露呈しました。

Clinical relevance

表示的モデルは、言語の意味に対する正確で構成的な参照を提供し、プログラムの等価性や最適化に関する推論をサポートし、再帰や高階関数などの機能の設計に情報を提供します。また、ドメイン理論はプログラミング言語をより広範な数学や論理学と結びつけます。

History

言語の数学的記述に関するストラッチーの研究と、スコットによる1969年のドメインモデルの構築が、表示的意味論の出発点となり、1971年の彼らの論文で形式化されました。スコットのドメイン理論は1970年代を通じて成熟し、プロトキンによるLCFの分析は完全抽象化問題を明確にし、ゲーム意味論などのその後の発展を推進しました。

Debates

完全抽象化問題

中心的な問題は、表示的モデルが言語の観測可能な振る舞いを、それ以上でもそれ以下でもなく、正確に捉えることができるかどうかです。古典的なドメインモデルは、高階逐次言語に対してこれを達成できず、代替モデルが提案されるきっかけとなりました。

Key figures

• Dana Scott
• Christopher Strachey
• Gordon Plotkin
• Glynn Winskel

Seminal works

• scott1971
• scott1976
• plotkin1977
• winskel1993

Frequently asked questions

表示的意味論におけるドメインとは何ですか？

ドメインとは、典型的には増加列の極限を持つ半順序集合である数学的構造であり、再帰的および部分的な計算を連続関数の最小不動点としてモデル化できる設定を提供します。

完全抽象化とは何ですか？

意味論が完全に抽象的であるとは、2つのプログラムが振る舞い的に同一である場合にのみ、それらが同じ表示を持つことを意味します。つまり、モデルは振る舞い的に同一のプログラムを区別せず、区別可能なプログラムを混同しません。