程式語言理論

程式語言理論cing4 sik1 jyu5 jin4 lei5 leon6（programming language theory，PLT）係電腦科學嘅一個子領域，包含研究程式語言呢樣嘢應該點樣設計、分析同埋分門別類嘅一套理論。

唔同程式嘅語言：低級程式語言（上）、C 程式語言（中）同埋 Python 程式語言（下）

程式語言係為咗俾用家可以俾命令落電腦而設嘅人工語言，為嘅係想要令電腦易用啲：原則上，電腦淨係識得睇完全由一串串 1 同 0 組成嘅機械碼（machine code），而呢啲一大串嘅 1 同 0 對一般人嚟講相當難明；電腦嘅設計者就創造出好似組合語言（asm）同高級程式語言等嘅程式語言－用呢啲語言寫成嘅源碼喺俾部電腦攞去行之前會轉化成機械碼，不過呢啲語言往往俾人設計成易睇過機械語言，令程式編寫呢家嘢易做啲。而隨住電腦科技嘅發展，廿一世紀初嘅電腦界出咗好多隻唔同嘅程式語言，每款程式語言都有獨特嘅功能。

程式語言理論做嘅就係嘗試比較唔同嘅程式語言：程式語言理論會用邏輯等形式化（formalized）－即係每個符號都有清晰定義，唔似得自然語言咁多歧義－嘅語言嚟表達唔同嘅程式語言，剖析唔同程式語言彼此之間喺解難能力上有乜嘢差異，例如係「某隻程式語言會唔會比起第啲語言更加擅長解某啲類型嘅問題」等嘅課題。呢啲理論思考會同數學、軟件工程、語言學同認知科學等嘅領域互相影響，而且對電腦應用－例如係新程式語言嘅設計噉－嚟講相當緊要。

背景

内文：程式語言同可讀性

睇埋：運算理論同有限狀態機

程式語言（programming language）係一類特殊嘅語言，用嚟教機械做運算同埋表達啲演算法（algorithm）嘅語義：响廿一世紀初，電子電腦靠嘅係用內部嗰啲－閒閒地數以十億計嘅－邏輯門（logic gate）嚟操控微弱電流做運算；而用家需要有某啲方法控制呢啲運算－發明程式語言嘅目的就正正係想令「教機械做運算」呢家嘢自動化，令到電腦變得更加易用。

語言等級

内文：低級程式語言同高級程式語言

機械語言（machine lanaguage）係最似電腦內部嘅實際運算嗰種程式語言，即係最低級（low-level）嘅程式語言－淨係用 1（有電過）同 0（冇電過）嘅二進制數字嚟表達嗮所有嘢，而組成一段機械碼嘅數字會包含嗮「要用啲乜嘢數據」同「要做啲乜嘢作業」等嘅資訊。

舉個例說明：假想依家有款機械語言，

• 款語言嘅每段命令都由 18 個數字組成，呢 18 個數字每一個都一係 1 一係 0（每一個呢啲數字成一個 bit），
  • 最頭嗰 7 個數字用二進制表達數據 A，
  • 跟住嗰 7 個數字用二進制表達數據 B，
  • 最尾嗰 4 個數字就表達要做乜（呢段就係所謂嘅行動碼；opcode）－0000 代表加，0001 代表減等等。

於是喺用呢種語言寫成嘅源碼入面，「0000011 0000100 0000」呢段碼係叫電腦計 3（用二進制寫係 11）加 4（用二進制寫係 100）嘅結果出嚟。

一般認為，機械語言有個重大缺點，就係可讀性（readability）低得好交關：就算係專業做資訊科技嘅人都普遍覺得機械語言好難睇，吓吓都係一大柞 1 同 0，而且當中多咗個 0 或者少噉咗個 0 就搞到成段碼都軭嗮；因為噉，人喺廿世紀中開始就有喺度創造多種嘅高級（high-level）程式語言，即係用形式化（簡單講就係高度精確）得嚟又易睇嘅方式，表達用家想電腦做嘅運算，出名嘅例子有 C 同相關嘅語言、Python 同埋 Java 呀噉－呢啲語言同低級程式語言一樣咁精確，會好似數學符號噉個個字都有固定嘅意思，但同時又會用自然語言嘅字（例如 if）或者一般人都識嘅常見數學符號（例如 x = a + b 噉嘅碼叫部電腦做加數），令到用呢啲語言寫出嚟嘅碼一般人都會睇得明。程式語言理論就係呢股趨勢嘅結果－電腦科學方面嘅工作者用數學、邏輯學同語言學嘅方法比較唔同嘅程式語言之間有乜異同，仲有係諗程式語言應該點設計、分析同分類。

句法同語義

内文：句法 (程式語言)同語義 (程式語言)

睇埋：邏輯同抽象句法樹

句法（syntax）同語義（semantics）係程式語言理論上兩個緊密相關嘅基礎概念，喺分析程式語言嗰陣成日都會提到。一隻程式語言嘅句法係指一柞規則，負責定義「响呢隻語言當中，邊啲符號組合算係結構上正確嘅陳述式」，定義嘅係一隻程式語言嘅「表面形式」；句法對應嘅係語義，語義係指一串電腦運算作業背後嘅邏輯或者數學結構；語義好多時係隻隻語言都完全一樣咁滯，不過唔同嘅程式語言往往會有唔同嘅句法，將同一款語義以唔同嘅樣表達出嚟；舉個例說明，想像以下呢串簡單嘅運算作業－

• 語義（背後嘅邏輯結構）：
  • 日常用語：「如果 a 呢個變數嘅數值大過 0（a > 0），噉就做作業 ${\text{A}}$（taskA）」；
  • 邏輯上嘅符號：a > 0 $\rightarrow$ taskA；
• 唔同程式語言嘅句法（用乜符號嚟表達呢串語義）會唔同：

C、C++、C♯:	Python:	MATLAB:	Lisp:	PostScript:
if (a > 0) { taskA; }	if a > 0: taskA	if (a > 0) taskA; end	(if (> a 0) (taskA))	a 0 gt { taskA } if

理論上，如果有個人設計一隻新嘅程式語言，佢大可以將隻語言設計成用「-」（句法）嚟表達「加」呢個算術作業（語義）－不過，因為啲人多數習慣咗用 - 嚟表達「減」，噉樣做會搞到啲人好唔慣，變相令隻語言冇咁好用。

「砌」算子

内文：算子 (編程)

睇埋：公理

喺思考點樣設計程式語言嗰陣，有一點係好重要嘅：一隻程式語言實會有若干款嘅算子（operator；指一隻程式語言入面行為似函數噉嘅嘢，例如「加減」或者「比較兩個數嘅大細」呀噉）；比較複雜嘅算子通常都有得由簡單啲－或者「基礎」啲－嘅算子嗰度「砌」出嚟；舉個簡單例子，想像家陣一隻程式語言要有陳述式嚟做「比較兩個數值」嘅運算－需要用到 =（等如）、>（大過）、<（細過）、>=（大過或者等如）... 等等嘅算子，查實呢啲算子冚唪唥都可以齋靠 < 就砌到嗮出嚟：

• 假設家陣款語言乜都冇，但經已
  1. 能夠理解到乜嘢係 <（細過；lessThan）同 not（邏輯非），
  2. 識得做 if... then... 噉嘅條件決策，同埋
  3. 處理到布林（真定假）嘅輸入輸出；
• >=（大過或者等如）可以定義做：

   public static boolean greaterThanOrEqualTo(int a, int b) {
     return not(lessThan(a, b));
   }
  

  如果 a < b，噉 lessThan(a, b) 會出 1（真），而 return not(lessThan(a, b)) 會跟住令呢個子程序會出 0，而噉就定義到 >=－因為a < b 就表示「a >= b」係假。

• 而 =（等如）就可以噉樣定義：

   public static boolean equalTo(int a, int b) {
     if (greaterThanOrEqualTo(a, b))
       return greaterThanOrEqualTo(b, a);
     else
       return false;
   }
  

  如果 b = a，greaterThanOrEqualTo(a, b)（上面定義咗）會出 1（真），而跟住 greaterThanOrEqualTo(b, a) 又會出 1，於是 return greaterThanOrEqualTo(b, a) 就會令個子程序會出 1，如果 greaterThanOrEqualTo(a, b) 或者 greaterThanOrEqualTo(b, a) 是但一個出 0（假），噉成個子程序就會出 0。

... 如此類推。

Λ 演算

内文：Λ 演算

睇埋：可運算函數

Λ 演算（lambda calculus）係一種用嚟將可運算函數表達出嚟嘅語言。Λ 演算具有圖靈完整性（Turing completeness），即係任何能夠計嗮 Λ 演算表示到嘅運算嘅運算機械能夠計到任何圖靈機計得到嘅嘢，所以程式語言理論好興攞 Λ 演算嚟做共同語言－即係用 Λ 演算表示程式語言嘅語義。

Λ 演算嘅起始點係函數（function）：Λ 演算將一個函數想像成一個「黑盒」，會攞若干個輸入，跟住俾出某啲輸出，而輸入同輸出之間會成某啲特定嘅關係，例：f(x) = x + 1 當中嘅 $f$ 可以想像成「攞 $x$ 呢個數值做輸入，計 $x+1$，再俾後者出嚟做輸出」，複雜啲嘅函數可以用同一道理想像。Λ 演算會將每一段運算（程式語言想表達嘅語義）表達成一段段好似以下噉嘅「句子」－每句嘢最左手邊都有個「$\lambda$」符號，表示句嘢係 Λ 演算，$\lambda$ 跟住後面嘅係個輸入（程式參數），而輸入後面隔一點嘅係輸出，當中個輸出要以「同輸入成乜關係」嘅形式寫出嚟：

$(\lambda x.x+1)$－輸入：$x$；輸出：$x+1$。

$(\lambda x.\lambda y.x+y)$－輸入：$x$ 同 $y$；輸出：$x+y$。

$(\lambda x.x+1)3$－輸入：$x=3$；輸出：$x+1=4$。

$M:=x+1,(\lambda x.M)3$－$M$ 嘅定義係「$x+1$」；輸入：$x=3$；輸出：$x+1=4$。

• 定義自然數：

  $0=\lambda f.\lambda x.x$

  $1=\lambda f.\lambda x.f\ x$

  $2=\lambda f.\lambda x.f\ (f\ x)$

  $3=\lambda f.\lambda x.f\ (f\ (f\ x))$

  $...$

... 等等。進一步嘅 Λ 演算仲有得砌埋條件運算式等嘅嘢出嚟。

環境

變數

内文：變數 (編程)

控制流程

内文：控制流程

編程範式

函數編程

内文：函數編程

邏輯編程

内文：邏輯編程

指令式編程

内文：指令式編程

物件導向編程

内文：物件導向編程

睇埋

• 程式編寫
• 語言學
• 加利化

文獻

• Abadi, Martín and Cardelli, Luca. A Theory of Objects. Springer-Verlag.

拎

• Lambda the Ultimate, a community weblog for professional discussion and repository of documents on programming language theory.
• Great Works in Programming Languages. Collected by Benjamin C. Pierce (University of Pennsylvania).