程式語言理論

程式語言理論（PLT）是計算機科學的一個分支，涉及程式語言及其各自特徵的設計，實現，分析，表征和分類。 它屬於計算機科學學科，既依賴於並影響數學，軟體工程，語言學甚至認知科學。 它是一個公認的計算機科學分支，也是一個活躍的研究領域，其成果發表在許多致力於PLT的期刊以及一般的計算機科學和工程出版物上。

基本介紹

• 中文名：程式語言理論
• 外文名：Programming language theory
• 縮寫：PLT

歷史

在某些方面，程式語言理論的歷史甚至早於程式語言本身的發展。由Alonzo Church和Stephen Cole Kleene在20世紀30年代開發的lambda演算被一些人認為是世界上第一種程式語言，儘管它旨在模擬計算而不是程式設計師向計算機系統描述算法的手段。 。許多現代函式式程式語言被描述為在lambda演算上提供“薄單板”，並且很多都很容易用它來描述。

將要發明的第一種程式語言是Plankalkül，它由Konrad Zuse在20世紀40年代設計，但直到1972年才公開（直到1998年才實現）。第一個廣為人知且成功的高級程式語言是Fortran，由John Backus領導的IBM研究團隊於1954年至1957年間開發。 FORTRAN的成功促成了科學家委員會的成立，以開發“通用”計算機語言;他們努力的結果是ALGOL 58.另外，麻省理工學院的John McCarthy開發了Lisp程式語言（基於lambda演算），這是學術界起源於成功的第一種語言。隨著這些初步努力的成功，程式語言成為20世紀60年代及以後的一個活躍的研究課題。從那時起程式語言理論史上的其他一些重要事件：

20世紀50年代

Noam Chomsky在語言學領域發展了喬姆斯基的等級制度;這一發現直接影響了程式語言理論和計算機科學的其他分支。

20世紀60年代

Simula語言由Ole-Johan Dahl和Kristen Nygaard開發;它被廣泛認為是面向對象程式語言的第一個例子; Simula還介紹了協同程式的概念。

1964年，Peter Landin是第一個意識到Church的lambda演算可用於編程程式語言的人。他介紹了“解釋”lambda表達式的SECD機器。

1965年，蘭丁引入了J運算元，基本上是一種延續形式。

1966年，Landin在他的文章The Next 700 Programming Languages中介紹了ISWIM，一種抽象的計算機程式語言。它在導致Haskell程式語言的語言設計中具有影響力。

1966年，CorradoBöhm介紹了程式語言CUCH（Curry-Church）。

1967年，克里斯托弗·斯特拉希（Christopher Strachey）發表了他有影響力的一套講座筆記“程式語言的基本概念”，介紹了術語R值，L值，參數多態和ad hoc多態。

1969年，J。Roger Hindley發表了“組合邏輯中對象的主體類型 - 方案”，後來推廣到了Hindley-Milner型推理算法。

1969年，Tony Hoare介紹了Hoare邏輯，這是一種公理語義。

1969年，威廉·艾爾文·霍華德（William Alvin Howard）觀察到，一種稱為“自然演繹”的“高級”證明系統可以直接在其直覺主義版本中被解釋為計算模型的類型變體，稱為lambda演算。這被稱為庫里 - 霍華德的對應。

20世紀70年代

1970年，達納斯科特首次發表他關於指稱語義學的著作。

1972年，開發了邏輯編程和Prolog，從而允許電腦程式表達為數學邏輯。

1974年，John C. Reynolds發現了F系統。它已經由數學邏輯學家Jean-Yves Girard於1971年發現。

從1975年開始，Gerald Jay Sussman和Guy Steele開發了Scheme程式語言，一種包含詞法範圍的Lisp方言，一個統一的命名空間，以及來自演員模型的元素，包括一流的延續。

Backus在1977年的ACM圖靈獎講座中抨擊了當前的工業語言狀態，並提出了一類新的程式語言，稱為功能級程式語言。

1977年，Gordon Plotkin介紹了編程可計算函式，這是一種抽象類型的函式式語言。

1978年，Robin Milner為ML程式語言引入了Hindley-Milner型推理算法。類型理論成為程式語言的一門學科，這種套用多年來在類型理論方面取得了巨大的進步。

20世紀80年代

1981年，Gordon Plotkin發表了關於結構化操作語義的論文。

1988年，吉爾斯·卡恩（Gilles Kahn）發表了關於自然語義學的論文。

由Alan Kay領導的Xerox PARC的科學家團隊開發了Smalltalk，這是一種以其創新開發環境而聞名的面向對象語言。

出現了過程計算，例如Robin Milner的通信系統微積分，以及C. A. R. Hoare的通信順序過程模型，以及類似的並發模型，例如Carl Hewitt的演員模型。

1985年，米蘭達的發布激發了對懶惰評估的純函式式程式語言的學術興趣。成立了一個委員會來定義一個開放的標準，導致1990年Haskell 1.0標準的發布。

Bertrand Meyer通過契約創建了方法設計，並將其合併到Eiffel程式語言中。

20世紀90年代

Gregor Kiczales，Jim Des Rivieres和Daniel G. Bobrow出版了“元對象協定的藝術”一書。

Eugenio Moggi和Philip Wadler介紹了使用monads來構造用函式式程式語言編寫的程式。

子學科和相關領域

有幾個研究領域，或者在程式語言理論中，或者對它有深遠的影響;其中許多都有相當大的重疊。此外，PLT還利用了許多其他數學分支，包括可計算性理論，範疇理論和集合論。

形式語義

形式語義是電腦程式和程式語言行為的正式規範。描述電腦程式的語義或“含義”的三種常用方法是指稱語義，操作語義和公理語義。

類型理論

類型理論是類型系統的研究;這是“通過根據他們計算的價值種類對短語進行分類來證明某些程式行為缺失的易處理的句法方法”。許多程式語言的特徵在於其類型系統的特徵。

程式分析和轉換

程式分析是檢查程式和確定關鍵特徵（例如缺少程式錯誤類別）的一般問題。程式轉換是將程式以一種形式（語言）轉換為另一種形式的過程。

比較程式語言分析

比較程式語言分析試圖根據程式語言的特徵將程式語言分為不同的類型;廣泛的程式語言類別通常稱為編程範例。

通用和元編程

元編程是高階程式的生成，其在執行時產生程式（可能以不同的語言或原始語言的子集）作為結果。

特定於域的語言

特定於域的語言是為有效地解決特定問題域中的問題而構建的語言。

編譯器構造

編譯理論是編寫編譯器的理論（或者更一般地說，是翻譯者）;將用一種語言編寫的程式翻譯成另一種形式的程式。傳統上，編譯器的操作分為語法分析（掃描和解析），語義分析（確定程式應該做什麼），最佳化（通過某些度量標準提高程式性能;通常執行速度）和代碼生成（在某種目標語言中生成和輸出等效程式;通常是CPU的指令集）。

運行時系統

運行時系統是指程式語言運行時環境及其組件的開發，包括虛擬機，垃圾收集和外部函式接口。