指稱語義

在計算機科學中，指稱語義是透過構造表達其語義的(叫做指稱(denotation)或意義的)數學物件來形式化計算機系統的語義的一種方法。程式語言的形式語義的其他方法包括公理語義和操作語義。指稱語義方式最初開發來處理一個單一計算機程式定義的系統。後來領域擴充套件到了由多於一個程式構成的系統，比如網路和併發系統。指稱語義起源於 克里斯托弗·斯特雷奇 和 Dana Scott 在1960年代的工作。在 Strachey 和 Scott 最初開發的時候，指稱語義把計算機程式的指稱(意義)解釋為對映輸入到輸出的函式。後來證明對於允許包含遞迴定義的函式和資料結構，這樣的元素的程式的指稱(意義)定義太受限制了。為了解決這個困難，Scott 介入了基於域的指稱語義的一般性方法。後來的研究者介入了基於冪域的方法，來解決併發系統的語義的問題。粗略的說，指稱語義關注找到代表程式所做所為的數學物件。這種物件的蒐集叫做域。例如，程式(或程式段)可以被偏函式，或演員事件圖想定，或用環境和系統之間的博弈表示: 它們都是域的一般性例子。指稱語義的一個重要原則是“語義應當是複合性的”: 程式段的指稱應當建立自它的子段的指稱。最簡單的例子是: “3 + 4”的意義確定自“3”、“4”和“+”的意義。指稱語義最初被開發為把函式式和順序式程式建模為對映輸入到輸出的數學函式的框架。本文第一節描述在這個框架內開發的指稱語義。後續章節處理多型、併發等問題。遞迴程式的語義.在本節中我們概覽作為指稱語義的最初主題的函式式遞迴程式的語義。問題如下。我們需要給予程式如階乘函式的定義以語義function factorial(n:Nat):Nat ≡ if (n==0)then 1 else n*factorial(n-1)。這個階乘程式的意義應當是在自然數上一個函式，但是由於它的遞迴定義，如何以複合方式理解它是不明白的。在遞迴的語義中，域典型的是偏序，它可以被理解為已定義性(definedness)的次序。例如，在自然數上的偏函式的集合可以給出為如下次序:給定偏函式 f 和 g，設“f≤g”意味著“在 f 定義的所有值之上 f 一致於 g”。通常假定這個域的某個性質，比如鏈的極限的存在性(po)和一個底元素。偏函式的偏序有一個底元素，完全未定義函式。它還有鏈的最小上界。各種額外性質經常是合理的和有用的:在域理論條目中有更詳盡細節。我們特別感興趣於在域之間的“連續”函式。它們是保持次序結構和保持最小上界的函式。在這種設定下，型別被指示為域，而域的元素粗略的捕獲了型別的元素。給予帶有自由變數的一個程式段的指稱語義，依據它從它的環境型別的指稱到它的型別的指稱的連續函式。例如，段落 n*g(n-1) 有型別 Nat，它有兩個自由變數: Nat 型別的n 和 Nat -&gt; Nat 型別的 g。所以它的指稱將是連續函式formula_1。在這個偏函式的次序下，可以如下這樣給出階乘程式的指稱。首先，我們必須開發基本構造如 if-then-else, ==, 和乘法的指稱。還必須開發函式抽象和應用的指稱語義。程式段λ n:N. if (n==0)then 1 else n*g(n-1)可以接著被給予作為在偏函式的域之間的連續函式的一個指稱formula_2。階乘程式的指稱被定義為函式 "F" 的最小不動點。它因此是域 formula_3 的一個元素。這種不動點存在的原因是 "F" 是連續函式。一種版本的Tarski不動點定理聲稱在域上的連續函式有最小不動點。證明不動點定理的一種方式給出了為什麼以這種方式給出遞迴的語義合適的直覺認識，所有在域 "D" 的帶有底元素 ⊥ 的連續函式 "F:D→D" 都有不動點，它給出自⊔i∈N"Fi"(⊥)。這裡的符號 "Fi" 指示 "F" 的 "i" 次應用。符號“⊔”意味著“最小上界”。把這個鏈的構件認為是“迭代”的有益的。在上述階乘的情況下，我們有在偏函式的域上的函式 "F"。所以這個鏈的最小上界是完全定義的階乘函式(它湊巧是全函式)。指稱語義的發展.透過研究程式語言的更精細的構造和不同的計算模型，指稱語義已經發展起來了。狀態的指稱語義.狀態(比如堆)和命令特徵可以直接用上述指稱語義來建模。下面列出的所有教科書都有詳情。關鍵想法是把命令當作在某個狀態域上的偏函式。“x:=3”的指稱是使一個狀態成為帶有 3 被賦值給 x 的狀態。順序算符“;”被指示為函式複合。不動點構造被用來給予迴圈構造如“while”的語義。在建模有區域性變數的程式的時候事情變得更加困難。一種途徑是不在使用域，轉而把型別解釋為從世界的範疇到域的範疇的函子。程式被指示為在這些函子之間的自然連續函式。資料型別的指稱.很多程式語言允許使用者定義遞迴資料型別。例如，數的列表的型別可以指定為datatype list = Cons of (Nat, list) | Empty.本節只處理不能變更的泛函資料型別。常規程式語言將典型的允許這種遞迴列表的元素被變更。另一個例子: 無型別 lambda 演算的指稱為datatype D = (D → D)“解域方程”問題關注找到建模這類資料型別的域。有一種途徑，粗略的說把所有域的蒐集自身當作一個域，並接著在這裡解這個遞迴定義。下面的教科書給出詳情。多型資料型別是定義時帶有引數的資料型別。比如 α lists 的型別被定義為datatype α list = Cons of (α, list) | Empty.數的列表，接著是有型別 Nat list，而字串的列表有型別 String list。一些研究者開發了多型性的域理論模型。其他研究者還在構造性集合論內建模了引數化多型。詳情可見下面列出的教科書。一個新近研究領域已經涉及了基於程式語言的物件和類的指稱語義。受限複雜性的程式的指稱語義.隨著基於線性邏輯的程式語言的開發，指稱語義已經被給予了線性使用(證明網、一致空間)和多項式時間複雜性的語言。非確定性程式的指稱語義.要給出非確定性程式順序程式指稱語義，研究者已經開發出了冪域理論。對冪域構造寫上 "P"，域 "P"("D") 是指示為 "D" 的型別的非確定性計算的域。在非確定性域理論模型中在公正性和無界性上有困難。確定性的冪域。併發性的指稱語義.很多研究者爭論說域理論模型不捕獲併發計算的本質。為此介入各種新模型。在 1980 年代早期，人們開始使用指稱語義的方式給予併發語言以語義。例子包括Will Clinger 關於演員模型的工作；Glynn Winskel 關於事件結構和petri網的工作 ；和 Francez, Hoare, Lehmann 和 de Roever (1979) 關於CSP 的跟蹤語義的工作。對所有這些工作的質詢仍在研究中。最近，Winskel 和其他人已經提議了 profunctor 範疇作為併發的域理論。順序性的指稱語義.順序程式語言 PCF 的完全抽象問題是在指稱語義中長時間的重要的開放問題。PCF 的困難在它是絕對的順序語言。例如，在 PCF 中無法定義並行或函式。為此如上述介紹的使用域的方式，產生了不是完全抽象的指稱語義。這個開放問題在1990年代隨著博弈語義和涉及邏輯關係的技術的發展基本解決了。 詳情請CF語言。源到源轉換的指稱語義.把一個程式語言轉換成另一個語言經常是有用的。例如一個併發程式語言可被轉換成程序演算；高階程式語言可以被轉換成位元組碼(實際上，常規指稱語義可以被看作把程式語言解釋成域的範疇的內部語言)。在這個語境中，來自指稱語義的概念，不如完全抽象，有助於滿足安全關注。完全抽象.完全抽象的概念關心程式的指稱語義是否精確的匹配它的操作語義。完全抽象的關鍵性質有:我們希望在操作語義和指稱語義之間的額外想要的性質有:在指稱語義中長期存在的重點是完全抽象存在於歸納型別中，特別是自然數的型別，作為接受用做遞迴的一種方法的型別。這個問題的傳統解釋是作為系統 PCF語言的語義。在 1990年代成功的用博弈語義為 PCF 提供了完全抽象模型，導致了對指稱語義的工作在方式上的根本改變。語義與實現.依據 Dana Scott [1980]:“語義確定一個實現不是必需的，它應該為證實一個實現是正確的提供標準。”依據 Clinger [1981]:“常規順序程式語言的形式語義通常自身可以被解釋為提供了一個(不充分)的這個語言的實現。雖然形式語義不必須總是提供這種實現，相信語義必須提供一個實現導致了關於併發語言的形式語義的混淆。當程式語言的語義中的無界非確定性被稱為蘊涵了這個程式語言不可能被實現被提出的時候這種混淆是明顯痛苦的。”指稱語義的早期歷史.如前面提到過的，這個領域最初由 Christopher Strachey 和 Dana Scott 在 1960年代，接著由 Joe Stoy 在 1970年代於“Oxford University Computing Laboratory”的“Programming Research Group”開發。Montague文法是英語的理想片段的某種形式的指稱語義。同其他計算機科學領域的聯絡.某些指稱語義的著作把型別解釋為域理論意義上的域，因而可以被看作模型論的分支，導致了同類型論和範疇論的聯絡。在計算機科學內與抽象釋義、程式驗證和函數語言程式設計有聯絡，數語言程式設計語言中的單子(monad)。特別是，指稱語義使用了續體(continuation)來依據函數語言程式設計語義表達順序程式設計中的控制流。