程式語言理論

**程式語言理論**（ | ）係電腦科學嘅一個子領域，包含研究程式語言呢樣嘢應該點樣設計、分析同埋分門別類嘅一套理論。

程式語言係為咗俾用家可以俾命令落電腦而設嘅人工語言，為嘅係想要令電腦易用啲：原則上，電腦淨係識得睇完全由一串串 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 呀噉呢啲語言同低級程式語言一樣咁精確，會好似數學符號噉個個字都有固定嘅意思，但同時又會用自然語言嘅字（例如 <code>if</code>）或者一般人都識嘅常見數學符號（例如 `x = a + b` 噉嘅碼叫部電腦做加數），令到用呢啲語言寫出嚟嘅碼一般人都會睇得明。**程式語言理論**就係呢股趨勢嘅結果電腦科學方面嘅工作者用數學、邏輯學同語言學嘅方法比較唔同嘅程式語言之間有乜異同，仲有係諗程式語言應該點設計、分析同分類。

## 句法同語義

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



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

喺思考點樣設計程式語言嗰陣，有一點係好重要嘅：一隻程式語言實會有若干款嘅算子（operator；指一隻程式語言入面行為似函數噉嘅嘢，例如「加減」或者「比較兩個數嘅大細」呀噉）；比較複雜嘅算子通常都有得由簡單啲或者「基礎」啲嘅算子嗰度「砌」出嚟；舉個簡單例子，想像家陣一隻程式語言要有陳述式嚟做「比較兩個數值」嘅運算需要用到 `=`（等如）、`>`（大過）、`<`（細過）、`>=`（大過或者等如）... 等等嘅算子，查實呢啲算子冚唪唥都可以齋靠 `<` 就砌到嗮出嚟：
*假設家陣款語言乜都冇，但經已
*#能夠理解到乜嘢係 `<`（細過；`lessThan`）同 `not`（邏輯非），
*#識得做 `if... then...` 噉嘅條件決策，同埋
*#處理到布林（真定假）嘅輸入輸出；
*`>=`（大過或者等如）可以定義做：
*:
```c
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`」係假。
*而 `=`（等如）就可以噉樣定義：
*:
```c
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)3M 嘅定義係「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).