# 程式語言 - 林佳志
[toc]
## Chapter 1: PRELIMINARIES
### 語言評估標準（四大指標）
* Readability：程式易讀
* Writability：程式易寫
* Reliability：程式可靠（符合規格）
* Cost：總成本（訓練、撰寫、維護、執行）
#### Readability（可讀性）
* **簡潔性**：功能集合不過多
* **最少重複功能**：例如 C++ 中有 `count++`, `++count`, `count+=1` 都是一樣 → 反而變複雜
* **最少運算子多載**
* **正交性(Orthogonality)**：少量基本元素能以一致方式組合
* **資料型別完整、語法一致、自我解釋**
例：C 用 `{}`、Ada 用 `if ... end if`，後者更清楚。
#### Writability（可寫性）
* 簡單一致（語法不多卻能表達豐富）
* 支援抽象化（例如函式、類別）
* 表達能力強（多種運算子、內建函式）
#### Reliability（可靠性）
* **型別檢查**：避免型別錯誤
* **例外處理**：錯誤可被攔截處理
* **別名(Aliasing)**：同一記憶體不同名稱會降低可靠性
* **可讀/可寫性** 會影響可靠性：語言太怪，容易出錯。
#### 成本與其他標準
* 成本包含訓練、編譯、執行、維護
* 可靠性差會提高成本
* 其他標準：
* **可移植性(Portability)**：不同平台能運作
* **通用性(Generality)**：應用範圍廣
* **明確性(Well-definedness)**：定義精確完整
#### 電腦架構與語言設計
* **主要影響：Von Neumann Architecture**
* 記憶體儲存資料與指令
* CPU 與記憶體間傳資料
* 對應語言：Imperative（命令式語言）
* 例：變數像記憶體格子，迴圈像重複取指令
* **瓶頸(Von Neumann Bottleneck)**：CPU比記憶體快太多 → 傳輸速度成限制
### 程式設計方法論影響
* 1950s–60s：效率導向 → FORTRAN
* 1970s：可讀性導向 → 結構化程式設計（C）
* 1980s：資料導向、物件導向（OOP）
### 語言類別
* **Imperative**：命令式（C、Java）
* **Functional**：函數式（LISP、F#）
* **Logic**：邏輯式（Prolog）
* **Markup/Hybrid**：標記與程式混合（HTML+JSTL）
### 語言設計取捨
* **可靠 vs 執行效率**（Java陣列檢查安全但慢）
* **可讀 vs 可寫**（APL語法短但難讀）
* **靈活 vs 可靠**（C++指標強但危險）
### 語言實作方法
1. **編譯(Compilation)** → 翻成機器碼 → 快
2. **直譯(Pure Interpretation)** → 一行一行執行 → 慢
3. **混合(Hybrid)** → 先轉中介碼再執行（例：Java bytecode）
* **JIT (Just-In-Time)** → 執行時才編譯，提高效率
* **Preprocessor (前置處理)** → 如 `#include`, `#define`
### 程式開發環境
* **UNIX**：早期系統 + 工具集合
* **Visual Studio .NET**：適用 C#、VB.NET
* **NetBeans**：Java 的開發環境
## Chapter 3: DESCRIBING SYNTAX AND SEMANTICS
### 語法與語意的基本概念
* **Syntax（語法）**：程式的形式結構 → 決定語言中「哪些寫法是合法的」。
* **Semantics（語意）**：程式的意義 → 決定「程式實際執行會做什麼」。
* 語法與語意的定義可供以下人使用：
* 語言設計者
* 編譯器實作者
* 程式設計師（理解程式運作）
### 語法描述的基本名詞
* **Sentence（句子）**：由字母表組成的字串
例：`int sum = a + b;`
* **Language（語言）**：句子的集合
例：所有合法的 C 程式句子。
* **Lexeme（字素）**：語言中最小的語法單位
例：`int`、`sum`、`=`
* **Token（記號）**：字素的分類
例：`int` 屬於「關鍵字 token」、`sum` 屬於「識別字 token」
### 語言的形式定義方式
* **Recognizer（辨識器）**
* 判斷輸入的字串是否屬於語言
* 例：編譯器中的語法分析器（Syntax Analyzer）
* **Generator（產生器）**
* 能夠「生成」語言中合法的句子
* 透過比對產生規則可檢查語法是否正確
### BNF 與 Context-Free Grammar（上下文無關文法）
* **Context-Free Grammar (CFG)**：
由 Noam Chomsky 提出，用來描述自然或程式語言結構。
* **BNF (Backus-Naur Form)**：
John Backus 為 ALGOL 語言設計的描述語法方法。
* **BNF 與 CFG 等價**：都是用來產生語言結構的「產生規則」。
#### 範例
```bnf
<expression> → <identifier> = <number> + <number>
<identifier> → sum
<number> → 3 | 4
```
對應的程式：`sum = 3 + 4;`
### BNF 的基本元素
* **非終端符號 (Nonterminal)**：
用於代表語法結構類別，如 `<expr>`、`<stmt>`
* **終端符號 (Terminal)**：
語言中實際出現的符號或字
* **產生式 (Rule)**：
`<左邊> → <右邊>`，表示如何組合語法結構
#### 範例
```bnf
<assignment> → <identifier> = <expression>
<identifier> → x | y | z
<expression> → <identifier> + <identifier> | <identifier>
```
### 語法推導（Derivation）
* 從 **起始符號 (Start Symbol)** 開始
* 重複套用產生規則直到只剩下終端符號
* 得到的字串稱為 **句子 (Sentence)**
#### 範例
```bnf
<stmt> → <var> = <expr>
<var> → a | b | c
<expr> → <term> + <term>
<term> → const | <var>
```
推導過程：
```
<stmt>
→ a = <expr>
→ a = <term> + <term>
→ a = b + const
```
結果：`a = b + const`
### 左推導與右推導
* **Leftmost derivation**：每次展開最左邊的非終端符號
* **Rightmost derivation**：展開最右邊的非終端符號
* 同一語法可能有多種推導方式
#### 範例：
```
<expr> → <term> + <term>
<term> → <var>
<var> → a | b
```
左推導：`<expr> → a + b`
右推導：`<expr> → a + b`
→ 結果相同，但推導順序不同。
### Parse Tree（語法樹）
* 用階層式方式表示推導過程
* 根節點是起始符號
* 葉節點是最終的終端符號
範例：`a = b + const`
```
<program>
└─ <stmts>
└─ <stmt>
├─ <var> → a
├─ =
└─ <expr>
├─ <var> → b
├─ +
└─ const
```
### 模糊性（Ambiguity）
* 一個文法若能產生「相同句子但有兩棵不同語法樹」，即為 **模糊文法**。
→ 對編譯器而言會造成「語法歧義」。
#### 範例：
```
<expr> → <expr> <op> <expr> | const
<op> → / | -
```
句子：`const - const / const`
可能有兩種解讀方式，因此是模糊的。
### 消除模糊：運算子優先與結合性
* **修正版文法**
```
<expr> → <expr> - <term> | <term>
<term> → <term> / const | const
```
→ 明確定義了減法比除法的「外層結構」。
* **結合性（Associativity）**
* 左結合：`(a + b) + c`
* 右結合：`a + (b + c)`
#### 範例：
```bnf
<expr> -> <expr> + const | const // unambiguous
```
### if-then-else 模糊與解法
模糊例：
```bnf
<stmt> -> if (<expr>) <stmt> | if (<expr>) <stmt> else <stmt>
```
→ `if (x>0) if (y>0) z=1 else z=-1`
會不確定 else 屬於哪個 if。
✅ **解法：區分 matched / unmatched**
```bnf
<stmt> -> <matched> | <unmatched>
<matched> -> if (<cond>) <stmt> else <matched> | <other_stmt>
<unmatched> -> if (<cond>) <stmt> | if (<cond>) <matched> else <unmatched>
```
### EBNF（Extended BNF）
EBNF 是 BNF 的改良版，讓語法更簡短清晰。
| 符號 | 功能 | 範例 |
| ----- | ------- | ----------- |
| `[ ]` | 可選 | `<proc_call> → ident [(<expr_list>)]` |
| `( )` | 選擇 | `<term> → <term> (+ \| -) const` |
| `{ }` | 重複0次或多次 | `<ident> → letter {letter \| digit}` |
#### 對比範例
BNF：
```bnf
<expr> → <expr> + <term> | <expr> - <term> | <term>
```
EBNF：
```bnf
<expr> → <term> {(+ | -) <term>}
```
### 靜態語意（Static Semantics）
* 指「與語法有關但不屬於句子結構」的規則
* 例如：
* 變數必須先宣告後使用
* 運算元類型要相容
* CFG（上下文無關文法）無法完全描述這些 → 需額外機制
### Attribute Grammar（屬性文法）
* 在文法規則中加入屬性（Attribute）與規則（Rule）
→ 幫助描述靜態語意檢查。
* 每個節點有：
* **Synthesized Attribute（自下而上傳遞）**
* **Inherited Attribute（自上而下傳遞）**
#### 範例
```
<assign> → <var> = <expr>
<expr> → <var> + <var> | <var>
<var> → A | B | C
```
屬性：
```
<expr>.actual_type ← <var>[1].actual_type
<expr>.expected_type ← <assign>.expected_type
Predicate:
<var>[1].actual_type == <var>[2].actual_type
```
### 語意描述的三種方法
| 方法 | 概念 | 特點 |
| -------------------------- | ------------ | --------- |
| **Operational Semantics** | 模擬程式實際執行步驟 | 直觀但複雜 |
| **Denotational Semantics** | 用數學函數描述狀態變化 | 抽象、可證明正確性 |
| **Axiomatic Semantics** | 用邏輯斷言驗證程式正確性 | 用於程式驗證 |
### Operational Semantics（操作語意）
* 以「執行過程」定義語意
* 虛擬機模擬記憶體與指令變化
* 適用於教學與語言手冊說明
#### 例：
```
if (x > 0) then y := 2 else y := 3
```
狀態變化：
```
{x=1, y=0} → {x=1, y=2}
```
### Denotational Semantics（指稱語意）
* 由 Scott 與 Strachey 提出
* 用數學函數映射語法 → 意義
* 對每個語言結構定義「對應的數學對象」
* 可用於證明程式正確性
#### 範例：
```
Me(2 + 3, s) = 5
Me(x + y, s) = s(x) + s(y)
```
若 `s = {x=2, y=3}`，則結果 `5`
### Axiomatic Semantics（公理語意）
* 使用邏輯斷言（Assertions）描述程式執行前後的狀態
* 常用於**程式驗證（Program Verification）**
#### 格式：
```
{P} statement {Q}
```
P：前置條件
Q：後置條件
意思是：「如果在執行 S 之前，條件 P 成立，那執行完後，條件 Q 一定成立。」
#### 範例：
```
x := x + 1
Postcondition: x > n
Weakest Precondition: x = n
```
#### Weakest Precondition
有時候我們知道要的 結果 (Q)，
但還不知道執行前要滿足什麼條件 (P)。
這時就用 Weakest Precondition 來「推回去」。
範例：
```
x := x + 1
Postcondition: x > 5
```
要保證結果成立，我們要找出最弱的條件（即「剛好足夠」的前提）：
```
Weakest Precondition: x > 4
```
因為只要在執行前 x > 4，執行後 x + 1 > 5 一定成立。
### 主要公理與推論規則
* **Assignment Rule**
`{Q[x→E]} x := E {Q}`
→ 在 Q 中將 x 取代為 E
* **Sequence Rule**
`{P1} S1 {P2}`，`{P2} S2 {P3}` ⇒ `{P1} S1; S2 {P3}`
* **Selection Rule**
`{B ∧ P} S1 {Q}`, `{¬B ∧ P} S2 {Q}` ⇒ `{P} if B then S1 else S2 {Q}`
* **Loop Rule**
利用不變式（Invariant）I 來驗證迴圈正確性
### Assignment Rule（最重要的公理）
對於賦值語句：
```
x := E
```
若要證明 `{P} x := E {Q}` 成立，
你可以在 **Q 裡面把 x 換成 E**：
```
{Q[x ← E]} x := E {Q}
```
#### 範例：
```
x := y + 1
Postcondition: x > 5
```
在 Q 中把 `x` 換成 `y + 1`：
```
{y + 1 > 5} x := y + 1 {x > 5}
```
所以執行前只要滿足 `y > 4`，執行後就會滿足 `x > 5`。
### Sequence Rule（序列規則）
兩段連續程式：
```
{P1} S1 {P2}
{P2} S2 {P3}
——————————————
{P1} S1; S2 {P3}
```
意思是：
> 若第一段保證 P2，第二段保證 P3，則整體保證 P3。
#### 範例：
```
{true} x := 1 {x = 1}
{x = 1} y := x + 2 {y = 3}
———————————————
{true} x := 1; y := x + 2 {y = 3}
```
### Selection Rule（if-else 規則）
```
{B ∧ P} S1 {Q}
{¬B ∧ P} S2 {Q}
——————————————
{P} if B then S1 else S2 {Q}
```
意思是：
> 若條件 B 為真時執行 S1 能得到 Q，
> 且條件 B 為假時執行 S2 也能得到 Q，
> 則整個 if-else 敘述都能保證 Q。
#### 範例：
```
{true}
if (x > 0) then y := 1 else y := -1
{(x > 0 → y = 1) ∧ (x ≤ 0 → y = -1)}
```
### Loop Rule（while 規則）
這是最難的部分，但你可以這樣理解：
```
{P} while B do S end {Q}
```
要證明一個迴圈正確，需要找出一個「**不變條件** (Loop Invariant, I)」。
Loop Invariant 是指「無論迴圈跑幾次，這條件永遠都成立」。
#### Loop Invariant 的四個條件：
1. **初始化時成立**（P ⇒ I）
2. **每次執行迴圈主體後仍成立**（{I ∧ B} S {I}）
3. **跳出迴圈時能推導出結果**（I ∧ ¬B ⇒ Q）
4. **迴圈一定會終止**（需有變數遞減或上升）
#### 範例（遞增計數）：
```
x := 0;
while (x < 10) do
x := x + 1;
end
```
想要證明 `{true} while (x < 10) do x := x + 1 {x >= 10}`
Loop Invariant 可選：`I: x <= 10`
| 條件 | 說明 |
| ------- | ---------------------------------------- |
| 初始時成立 | x=0 ⇒ x ≤ 10 ✅ |
| 迴圈內仍成立 | 若 x ≤ 10 且 x < 10，執行 x := x+1 → x ≤ 10 ✅ |
| 結束時推出結果 | ¬(x < 10) ⇒ x ≥ 10 ✅ |
| 會終止 | 每次 x 增加 1 ✅ |
### 三種語意方式比較
| 方法 | 優點 | 缺點 |
| ---------------- | ------- | ---------- |
| **Operational** | 直觀、易理解 | 太細節、依賴機器模型 |
| **Denotational** | 嚴謹、可數學化 | 太抽象、不易實作 |
| **Axiomatic** | 可證明正確性 | 難以覆蓋所有語法 |
### Summary
* BNF 與 Context-Free Grammar：用於描述語法結構
* Attribute Grammar：補足語法結構的語意資訊
* 三大語意描述法：
* **Operational**（以行為定義）
* **Denotational**（以數學函數定義）
* **Axiomatic**（以邏輯推論定義）
## Chapter 5: NAMES, BINDINGS, AND SCOPES
### Introduction
* 命令式語言是以 Von Neumann 架構為基礎的抽象
* 包含記憶體與處理器兩部分
* 變數（Variable）是記憶體單元的抽象
* 設計變數與名稱時需考量：
* scope（作用範圍）
* lifetime（生命週期）
* type checking（型別檢查）
* initialization（初始化）
* type compatibility（型別相容性）
### Names（名稱）
* 名稱（Name）是程式語言中用來指代變數、函數或物件的字串。
* 設計問題：
* 是否區分大小寫（case sensitive）
* 特殊字（special words）是否為保留字（reserved words）或關鍵字（keywords）
範例：
```cpp
int Value = 10;
int value = 20; // 在 C++ 中不同變數，因為區分大小寫
```
```python
if = 5 # Python 錯誤，if 為保留字
```
### Name Length（名稱長度）
* 名稱太短會影響可讀性。
* 語言規定：
* C99：無長度上限，但僅前 63 字有效；外部名稱最多 31 字元
* C#、Java：無限制，全部有效
* C++：無限制，但實作上通常有限制
* 範例：
* userProfileSettingsForApplicationX()
* userProfileSettingsForApplicationY()
### Special Characters（特殊字元）
* PHP：變數必須以 `$` 開頭，例如 `$username = "JohnDoe"`
* Perl：開頭符號代表變數類型
* `$scalar`（純量）
* `@array`（陣列）
* `%hash`（雜湊）
* Ruby：
* `@name` → instance variable
* `@@classname` → class variable
### Case Sensitivity（大小寫敏感性）
* C、C++、Java、C# 為大小寫敏感語言。
* 缺點：
* 可讀性下降，容易混淆（例如 totalAmount vs TotalAmount）
* 在 C++、Java、C# 中更嚴重，因為內建名稱常為混合大小寫（如 IndexOutOfBoundsException）。
* 其他語言則不區分大小寫。
### Special Words（特殊字）
* 幫助可讀性，用於分隔程式結構。
* 區分兩種：
* **Keyword（關鍵字）**：僅在特定情境下具特殊意義。
* **Reserved word（保留字）**：不能作為自訂名稱使用。
* 保留字過多會造成名稱衝突，例如 COBOL 有超過 300 個保留字。
### Variables（變數）
* 變數是記憶體單元的抽象。
* 每個變數可用一組屬性描述：
1. Name（名稱）
2. Address（位址）
3. Value（值）
4. Type（型別）
5. Lifetime（生命週期）
6. Scope（作用範圍）
### Variable Attributes（變數屬性）
* **Name**：並非所有變數都有名稱（例如暫存器、匿名物件）。
* **Address**：變數所在的記憶體位置。
* 不同時間、不同位置可能有不同位址。
* 若兩個名稱指向同一個位址，稱為 **alias（別名）**。
* Alias 常由 pointer、reference、或 union 造成，會降低程式可讀性。
### Type 與 Value
* **Type（型別）**
* 決定變數可取的值範圍與可執行的運算。
* 對浮點數而言，型別也決定精度。
* **Value（值）**
* 記憶體位置內實際儲存的內容。
* l-value（左值）：位址
* r-value（右值）：內容
### Binding（繫結）
* Binding 是實體與屬性之間的關聯。
例如：變數與型別、變數與值、符號與運算的關聯。
* Binding Time（繫結時間）：繫結發生的時間點。
### Possible Binding Times（可能的繫結時間）
| 時間點 | 內容 |
| ----- | ----------------------- |
| 語言設計時 | 將運算符號繫結到運算操作（如 `+` 表加法） |
| 語言實作時 | 定義資料型別如何表示（例如浮點數格式） |
| 編譯期 | 將變數繫結到型別（例如 C、Java） |
| 載入期 | 將靜態變數繫結到記憶體位置 |
| 執行期 | 將非靜態區域變數繫結到記憶體 |
### Static vs Dynamic Binding
* **Static Binding（靜態繫結）**
* 繫結在執行前完成，執行期間不再改變。
* 例：
```cpp
void greet() { cout << "Hello!"; }
int main() { greet(); } // greet 在編譯期就確定
```
* **Dynamic Binding（動態繫結）**
* 執行時期才決定繫結。
* 例：
```cpp
class Base { virtual void show() { cout << "Base"; } };
class Derived : public Base { void show() override { cout << "Derived"; } };
int main() { Base* ptr = new Derived(); ptr->show(); } // 執行期才決定呼叫 Derived::show
```
### Type Binding（型別繫結）
* 兩個問題：
* 型別如何指定？
* 何時進行繫結？
若為靜態繫結，型別可透過下列方式決定：
* **Explicit Declaration（明確宣告）**
* 由程式明確指出變數型別。
* 例：`int x;`
* **Implicit Declaration（隱含宣告）**
* 未明確宣告時，語言根據慣例自動推定型別。
* 例：Python、Perl、JavaScript、Basic、Ruby、PHP
優缺點：
* 優點：可寫性高
* 缺點：可靠性下降（可能誤判型別）
### Type Inferencing（型別推斷）
* 編譯器根據變數使用情境自動判斷型別。
* C# 範例：
```csharp
var number = 42; // 編譯器自動推斷 number 是 int
```
* ML、Haskell、F# 也使用相同概念。
### Dynamic Type Binding（動態型別繫結）
* 在執行時期透過指定值決定型別。
* 常見於 Python、Ruby、PHP、JavaScript。
* 範例：
```js
list = [2, 4.33, 6];
list = 17.3; // 型別於執行時改變
```
* 優點：彈性高
* 缺點：需動態型別檢查、執行成本高、編譯期無法偵錯。
### Storage Binding and Lifetime（儲存繫結與生命週期）
* **Allocation（配置）**：從可用記憶體池取得空間
* **Deallocation（釋放）**：將記憶體歸還
變數的 lifetime 是其與記憶體綁定的時間長度。
### Variable Lifetime 分類
1. **Static Variable（靜態）**
* 於執行前繫結並在整個程式期間維持。
* 優點：效率高（直接位址存取）、可保留歷史值。
* 缺點：缺乏彈性、無法遞迴。
* 例：
```cpp
static int count = 0;
```
2. **Stack-dynamic Variable（堆疊動態）**
* 宣告時才配置，離開區塊即釋放。
* 優點：支援遞迴、節省記憶體。
* 缺點：有配置與釋放開銷、不可保留歷史值。
* C 的區域變數即屬此類。
3. **Explicit Heap-dynamic Variable（顯式堆積動態）**
* 以程式語句明確分配與釋放。
* 例：
```cpp
int* ptr = new int(5);
delete ptr;
```
* 優點：支援動態記憶體管理
* 缺點：效率低、容易出錯（如記憶體洩漏）
4. **Implicit Heap-dynamic Variable（隱含堆積動態）**
* 由指派語句自動決定生命週期。
* 範例（JavaScript）：
```js
let list = [1, 2, 3];
list = "new string"; // 原記憶體自動釋放
```
* 優點：彈性高
* 缺點：效率低、容易出現隱藏錯誤
### Scope（作用範圍）
* 變數可見的程式區域稱為 scope。
* 區域變數：在程式單元內宣告。
* 非區域變數：在外層宣告但可被內層使用。
* 全域變數：可被所有單元存取。
scope 規則決定名稱參照到哪個變數。
### Static Scope（靜態作用範圍）
* 根據程式文本結構決定變數的可見性。
* 查找過程：
1. 先從當前區域搜尋。
2. 若找不到，向外層逐層尋找，直到全域區域。
外層稱為 **靜態祖先（static ancestor）**，最接近者為 **靜態父層（static parent）**。
範例（JavaScript）：
```js
function outer() {
var a = 10;
function inner() {
var b = 20;
console.log(a); // a 取自 outer()
}
inner();
}
outer();
```
### Scope Hiding（遮蔽）
* 內層定義相同名稱變數會遮蔽外層變數。
* 範例：
```cpp
int x = 10;
void func() {
int x = 20; // 遮蔽外層 x
cout << x; // 輸出 20
}
```
### Block Scope（區塊範圍）
* ALGOL 60 引入區塊概念，可在區塊內重新定義名稱。
* C 與 C++ 支援此特性；Java 和 C# 禁止在同一方法內重複名稱。
* 範例：
```java
public void method() {
int count = 10;
if (true) {
int count = 20; // 錯誤，Java 不允許同名變數
}
}
```
### The LET Construct（區域繫結結構）
* 在函數式語言中常見（如 Scheme、ML、F#）。
* 結構分兩部分：
1. 第一部分：名稱與值的繫結。
2. 第二部分：使用這些名稱。
Scheme 範例：
```scheme
(let ((x 5)
(y 10))
(+ x y))
```
ML 範例：
```ml
let val x = 5
val y = 10
in
x + y
end;
```
F# 範例：
```fsharp
let x = 5
let y = 10
x + y
```
### Declaration Order（宣告順序）
* C99、C++、Java、C# 允許在區塊中任意位置宣告變數。
* C99、C++、Java：變數作用範圍從宣告開始至區塊結尾。
* C#：整個區塊有效，但仍需先宣告再使用。
* C++、Java、C# 可在 for 迴圈中宣告：
```cpp
for (int i = 0; i < 10; i++) {
// i 僅在迴圈內有效
}
```
### Global Scope（全域範圍）
* C、C++、PHP、Python 等允許在函式外宣告全域變數。
* C/C++：宣告（declaration）與定義（definition）區分。
```cpp
// a.cpp
extern int x; // 宣告
// b.cpp
int x = 10; // 定義
```
* PHP 全域變數可透過 `$GLOBALS` 陣列或 `global` 關鍵字使用。
```php
$x = 10;
function test() {
global $x;
$x = 20;
}
```
* Python 全域變數需在函式中明確宣告：
```python
x = 10
def func():
global x
x = 20
```
### Evaluation of Static Scoping（靜態作用範圍的評價）
* 優點：可預測、容易理解
* 缺點：大型程式中易造成過度存取，結構混亂
### Dynamic Scope（動態作用範圍）
* 根據執行時的呼叫鏈決定變數可見性。
* 當前執行的所有活躍子程式的變數都可見。
範例：
```js
function big() {
function sub1() { var x = 7; sub2(); }
function sub2() { console.log(x); } // 動態範圍會取 sub1 的 x
sub1();
}
big();
```
### Comparison of Static vs Dynamic Scope
| 類型 | 決定時機 | 查找方式 | 優點 | 缺點 |
| ----------- | ----------- | ----------- | ----------- | ----------- |
| 靜態作用範圍 | 編譯期 | 依文字結構 | 易於理解 | 彈性低 |
| 動態作用範圍 | 執行期 | 依呼叫順序 | 方便測試 | 難以追蹤、型別檢查困難 |
### Scope and Lifetime
* Scope 與 Lifetime 相關但不同。
* 例：
```cpp
void func() {
static int count = 0; // 生命週期長，作用範圍僅限此函式
count++;
cout << count;
}
```
* 每次呼叫 count 都會累加，但外部無法存取。
### Referencing Environment（參照環境）
* 一個語句可見的所有名稱集合。
* 靜態語言中：由區域與外層可見變數組成。
* 動態語言中：由所有活躍的子程式變數組成。
範例（JavaScript）：
```js
function outer() {
var a = 10;
function inner() {
var b = 20;
console.log(a + b);
}
inner();
}
```
參照環境為 {a, b}。
### Named Constants（具名常數）
* 常數在繫結到記憶體時即固定值。
* 優點：提升可讀性與可維護性。
* 可用於參數化程式。
* C++、Java：表達式可在執行期繫結。
* C#：有兩種常數：
* const：編譯期繫結
* readonly：執行期繫結
### Summary
* 名稱設計需考慮大小寫敏感性與特殊字。
* 變數具備六項屬性：名稱、位址、值、型別、生命週期、作用範圍。
* Binding 為實體與屬性間的繫結，依時間分靜態與動態。
* 變數依生命週期分為 static、stack-dynamic、explicit heap-dynamic、implicit heap-dynamic。
* Scope 決定名稱可見範圍，靜態與動態各有優缺。
* 強型別語言能偵測所有型別錯誤，提升可靠性。
## Chapter 6: DATA TYPES
### Introduction
* 資料型別（Data Type）定義了一組資料物件及可在其上執行的操作。
* **Descriptor（描述子）**：變數的屬性集合，例如型別、大小、範圍、位址。
* **Object（物件）**：資料型別的具體實例（實際存在於記憶體中的值）。
* 各種資料型別的設計問題：
* 有哪些操作被允許？
* 操作如何被定義與指定？
### Primitive Data Types（基本資料型別）
* 幾乎所有語言都提供一組基本資料型別。
* 基本型別：不由其他型別組成。
* 有些直接反映硬體設計，有些則需要軟體支援。
### Integer（整數）
* 幾乎完全對應硬體的整數格式。
* 語言中可能有多種不同大小的整數型別。
* 例：Java 提供四種帶號整數型別：
* byte (8-bit)
* short (16-bit)
* int (32-bit)
* long (64-bit)
### Floating Point（浮點數）
* 模擬實數，但僅為近似值。
* 用於科學運算語言中，通常提供至少兩種：
* float（單精度）
* double（雙精度）
* 通常採用硬體的浮點格式。
* IEEE 754 為常見的浮點數標準。
### Complex（複數）
* 某些語言支援複數型別，例如 C99、Fortran、Python。
* 每個值包含兩個浮點數：
* 實部（real part）
* 虛部（imaginary part）
* Python 寫法：
```python
z = 7 + 3j
```
### Decimal（十進位數）
* 主要用於商業應用（例如金額計算）。
* COBOL 為代表性語言；C# 也支援 decimal 型別。
* 儲存固定小數位數（BCD 編碼）。
* 優點：精確
* 缺點：範圍有限、記憶體使用效率低。
### Boolean（布林值）
* 最簡單的資料型別。
* 僅有兩個值：true、false。
* 雖可用單一 bit 表示，但實作時常以 byte 儲存以提升可讀性。
### Character（字元）
* 字元以數字編碼方式儲存。
* 常見編碼：
* ASCII（7-bit）
* Unicode（16-bit, UCS-2）
* Unicode（32-bit, UCS-4）
* Java、C#、JavaScript 採用 Unicode。
* Fortran 2003 開始支援 32-bit Unicode。
### Character String Types（字串型別）
* 字串是由字元組成的序列。
* 設計問題：
* 字串是否為基本型別？或只是字元陣列的特殊形式？
* 字串長度是固定還是可變？
### String Operations（字串操作）
常見操作包括：
* 指派與複製
* 比較（=、>、<）
* 串接（Concatenation）
* 子字串取用（Substring）
* 模式比對（Pattern Matching）
### String Types in Common Languages
* C / C++：非基本型別，以 char 陣列實作並透過函式庫操作。
* Fortran、Python：基本型別，支援直接操作。
* SNOBOL4：以字串操作為核心，支援進階模式比對。
* Java：透過 String 類別實現。
* Perl、JavaScript、Ruby、PHP：內建正規表示式比對功能。
### String Length Options（字串長度選擇）
* **Static（靜態長度）**：在宣告時固定（如 COBOL、Java String）。
* **Limited Dynamic（有限動態）**：有最大長度，實際長度可變（C, C++）。
* **Dynamic（完全動態）**：可隨程式執行變化（Perl、JavaScript）。
### String Implementation（字串實作）
* **Static**：於編譯期確定長度與位置。
* **Limited Dynamic**：執行期需要長度描述子。
* **Dynamic**：需動態配置與釋放記憶體，成本最高。
### Ordinal Types（序數型別）
* 可與正整數一一對應的型別。
* 範例：
* 整數 (integer)
* 字元 (char)
* 布林 (boolean)
* 允許以順序或比較方式操作。
### Enumeration Types（列舉型別）
* 以名稱定義所有可能值。
* 範例：
```csharp
enum days { mon, tue, wed, thu, fri, sat, sun };
```
* 設計考量：
* 是否允許重複名稱？
* 是否允許與整數自動轉換？
* 優點：
* 提高可讀性（使用名稱代替數字）。
* 提高可靠性（可檢查範圍與運算）。
* Java、C# 的列舉比 C++ 更安全，因為不會自動轉換為整數。
### Array Types（陣列型別）
* 陣列是**同質（homogeneous）** 的資料集合。
* 每個元素以索引（index）識別。
定義：
```
array_name(index_list) → element
```
### Array Design Issues
* 索引型別是否合法？
* 是否要檢查索引範圍？
* 索引範圍何時決定？
* 何時配置記憶體？
* 是否允許不規則（ragged）或矩形（rectangular）多維陣列？
* 陣列元素是否可初始化？
* 是否支援 slice（切片）操作？
### Array Indexing（索引）
* Fortran、Ada 使用括號 `()`
* C、Java 使用方括號 `[]`
* Ada 保持函式呼叫與索引一致（皆使用 `()`）
### Array Index Types（索引型別）
* Fortran、C：僅允許整數索引。
* Java：僅允許整數型別。
* 範圍檢查：
* C、C++、Perl、Fortran：不強制檢查。
* Java、C#、ML：強制檢查。
### Array Binding Categories（陣列繫結種類）
1. **Static**
* 索引範圍與儲存於編譯時決定。
* 優點：效率高（無需動態配置）。
2. **Fixed Stack-Dynamic**
* 索引範圍固定，但配置於執行期宣告時完成。
3. **Fixed Heap-Dynamic**
* 索引範圍固定，但記憶體從堆積分配。
4. **Heap-Dynamic**
* 索引範圍與大小於執行期可變。
* 優點：彈性高（可動態擴張）。
### Array Initialization（初始化）
* 可於宣告時初始化：
```cpp
int list[] = {4, 5, 7, 83};
char name[] = "freddie";
```
* Java：
```java
String[] names = {"Bob", "Jake", "Joe"};
```
### Heterogeneous Arrays（異質陣列）
* 元素可為不同型別。
* 支援語言：Perl、Python、Ruby、JavaScript。
### Array Operations（陣列操作）
* APL 提供最強大的陣列運算（矩陣運算與反向操作等）。
* Python 支援串接、成員檢查與 list comprehension。
* Ruby 亦支援串接操作。
### Rectangular vs Jagged Arrays
* **Rectangular Array**：各行列元素數相同。
* **Jagged Array**：每列元素數不同（陣列中的陣列）。
* C、C++、Java 支援 jagged array。
* F#、C# 同時支援 rectangular 與 jagged。
### Array Slices（切片）
* Slice 是陣列的子結構參照。
* 只存在於支援陣列操作的語言中。
* 範例（Python）：
```python
vector = [2, 4, 6, 8, 10, 12]
print(vector[2:5]) # [6, 8, 10]
```
### Array Implementation（陣列實作）
* 陣列存取由**存取函式（access function）** 計算實體位址。
* 一維陣列：
```
address(list[k]) = address(list[lower_bound]) + ((k - lower_bound) * element_size)
```
* 多維陣列可使用 row-major（按列）或 column-major（按欄）方式配置。
### Associative Arrays（關聯陣列）
* 無序集合，以「鍵（key）」作為索引。
* 常見於腳本語言：Perl、Python、Ruby、Lua。
* Perl 範例：
```perl
%hi_temps = ("Mon" => 77, "Tue" => 79, "Wed" => 65);
$hi_temps{"Wed"} = 83;
delete $hi_temps{"Tue"};
```
### Record Types（紀錄型別）
* 紀錄是**異質（heterogeneous）** 的資料集合。
* 每個欄位以名稱識別。
* 設計問題：
* 欄位存取語法？
* 是否允許省略上層名稱？
範例：
```cpp
struct Employee {
string name;
int age;
double salary;
};
```
### Records in COBOL
* 使用層級號碼顯示巢狀結構：
```
01 EMP-REC.
02 EMP-NAME.
05 FIRST PIC X(20).
05 LAST PIC X(20).
02 HOURLY-RATE PIC 99V99.
```
### Record Field References
* COBOL：
```
FIRST OF EMP-NAME OF EMP-REC
```
* 現代語言（C、Java）：使用「.」運算子
```
emp.name
```
* 可省略上層名稱（elliptical reference）只要不造成歧義。
### Record vs Array
* Record：用於異質資料集合，存取以名稱進行。
* Array：用於同質資料集合，存取以索引進行。
* 陣列存取較慢（索引動態）；紀錄存取較快（欄位固定）。
### Tuple Types（元組型別）
* 類似紀錄，但元素**無名稱**。
* Python、ML、F# 均支援。
* Python：
```python
myTuple = (3, 5.8, 'apple')
a, b, c = myTuple
```
* 元組不可變（immutable）。
### List Types（列表型別）
* Lisp、Scheme：以括號表示：
```
(A B C D)
(A (B C) D)
```
* 代碼與資料使用相同表示方式。
* 基本操作：
* CAR：回傳第一個元素
* CDR：回傳其餘元素
* CONS：將元素加入清單前端
* LIST：建立新清單
ML 中：
```
[1, 3, 5]
3 :: [5, 7] => [3, 5, 7]
```
Python 中：
```
myList = [3, 5.8, "grape"]
del myList[1]
[x*x for x in range(6) if x%3==0] # [0,9,36]
```
### Union Types（聯合型別）
* 同一變數可在不同時間儲存不同型別的值。
* 設計問題：是否應強制型別檢查？
* **Free Union（自由聯合）**：不檢查型別（C、C++）。
* **Discriminated Union（帶判別聯合）**：有型別指示器（ML、F#、Haskell）。
範例（F#）：
```fsharp
type intReal =
| IntValue of int
| RealValue of float
```
### Pointer and Reference Types（指標與參照）
* 指標變數的值是記憶體位址或特殊值 nil。
* 用於間接取值或動態記憶體管理。
設計問題：
* 指標變數與目標的生命週期如何協調？
* 是否允許任意型別指標？
* 是否同時支援 reference？
### Pointer Operations
* **Assignment**：設定指標內容。
* **Dereferencing**：取指標指向位置的值。
* C++：
```cpp
int x = 10;
int* ptr = &x;
cout << *ptr; // 10
```
### Pointer Problems
1. **Dangling Pointer（懸掛指標）**：指向已釋放記憶體的指標。
2. **Lost Heap Variable（記憶體洩漏）**：動態分配後失去參照。
### Pointer Safety Techniques
* **Tombstone**：使用中介指標，指標失效後 tombstone 設為 nil。
* **Locks-and-Keys**：使用配對的 key 與 lock，確保指標有效。
### Heap Management（堆積管理）
* 回收未使用記憶體是執行期的重要工作。
* 方法：
* **Reference Counting（參照計數）**：每個物件紀錄被參照次數，歸零時釋放。
* 缺點：需額外空間與時間，遇到循環參照無法處理。
* **Mark-Sweep（標記清除）**：定期標記可達物件並清除垃圾。
* 缺點：早期版本會造成執行延遲，改進版採增量回收。
### Type Checking（型別檢查）
* 確保運算元與運算子型別相容。
* 若不相容但允許自動轉換，稱為 **coercion**。
* 錯誤運算稱為 **type error**。
靜態檢查：編譯時進行。
動態檢查：執行時進行。
### Strong Typing（強型別）
* 語言若能保證所有型別錯誤都被偵測，即為強型別語言。
* 例：
* C、C++：非強型別（可略過檢查）
* Java、C#：幾乎強型別
* ML、F#：完全強型別
### Type Equivalence（型別等價）
* 判斷兩個變數的型別是否相同。
* 兩種方式：
* **Name Equivalence（名稱等價）**：僅在使用相同名稱宣告時相等。
* **Structure Equivalence（結構等價）**：型別結構完全相同即相等。
* Name 等價：容易實作但限制多。
* Structure 等價：彈性高但實作複雜。
### Theory and Data Types（理論基礎）
* 型別理論（Type Theory）研究資料型別的形式定義。
* 實務分支：商業語言中的資料型別。
* 抽象分支：以 lambda calculus 為基礎。
* 型別系統由：
* 型別集合
* 型別規則（由屬性文法或型別映射定義）
### Summary
* 資料型別決定了語言的風格與可用性。
* 基本型別：整數、浮點、布林、字元等。
* 使用者自訂型別：列舉、子範圍、陣列、紀錄、聯合、指標。
* 陣列與紀錄為主要的聚合資料型別。
* 指標提供彈性但帶來安全問題。
* 強型別語言能偵測所有型別錯誤，提升可靠性。
## Chapter 7: EXPRESSIONS AND ASSIGNMENT STATEMENTS
### Introduction
* **Expressions（運算式）** 是程式中用來描述計算的基本單位。
* 要了解運算式的行為，必須熟悉：
* 運算子優先順序（operator precedence）
* 運算子結合性（operator associativity）
* 運算元求值順序（operand evaluation order）
* 命令式語言的核心是「**指派敘述（assignment statement）**」，用來改變變數值。
### Arithmetic Expressions（算術運算式）
* 由運算子（operators）、運算元（operands）、括號與函式呼叫所組成。
* 其設計重點包括：
1. 運算子優先順序
2. 運算子結合性
3. 運算元求值順序
4. 是否有副作用（side effects）
5. 運算子多載（operator overloading）
6. 型別混用（mixed-mode expressions）
### Operators（運算子種類）
* **一元運算子（unary）**：一個運算元
例：`++x`、`x++`
* **二元運算子（binary）**：兩個運算元
例：`a + b`、`a == b`
* **三元運算子（ternary）**：三個運算元
例（C 語言）：`(a > b) ? a : b`
### Operator Precedence Rules（運算子優先順序）
運算子優先順序決定當相鄰運算子不同時的求值順序。
常見順序：
1. 括號 `()`
2. 一元運算子 `++`, `--`, `-`
3. 乘除 `*`, `/`
4. 加減 `+`, `-`
例如：
```
int result = 5 + 3 * 2; // 先算 3*2，再加 5，結果為 11
```
### Operator Associativity Rules（運算子結合性）
運算子結合性決定**相同優先等級**的運算子求值方向。
常見規則：
* 大部分為左結合（left-to-right）
* `**`（次方）通常為右結合（right-to-left）
* FORTRAN 的一元運算子採右結合
APL 語言特殊：所有運算子同等優先，皆為右結合。
括號可用來覆蓋優先順序與結合性。
### Expressions in Different Languages
* **Ruby**：所有運算子皆為方法，可被覆寫。
* **Scheme / Lisp**：所有運算皆為函式呼叫。
例：`(+ a (* b c))` 等同於 `a + (b * c)`。
### Conditional Expressions（條件運算式）
* C、C++、Java 皆提供條件運算子 `?:`。
```c
average = (count == 0) ? 0 : sum / count;
```
等同於：
```c
if (count == 0)
average = 0;
else
average = sum / count;
```
### Operand Evaluation Order（運算元求值順序）
1. 變數：取記憶體中儲存的值。
2. 常數：直接使用常數或從指令中取值。
3. 括號表達式：先完全求值再回傳結果。
4. 函式呼叫：最複雜，因為可能有副作用。
### Functional Side Effects（副作用）
* 副作用是函式執行時改變了其他運算元或非區域變數的情況。
* 問題範例：
```c
a = 10;
b = a + fun(&a); // fun() 若改變 a，結果取決於求值順序
```
### 處理副作用的兩種方式
1. **語言禁止副作用**
* 不允許函式修改兩向參數或非區域變數。
* 優點：安全、容易理解。
* 缺點：限制彈性。
2. **固定運算元求值順序**
* 例如 Java 要求「左至右」求值。
* 缺點：減少編譯器最佳化空間。
### Referential Transparency（參照透明性）
* 若兩個相同值的運算式可在任何位置互換而不改變程式行為，則具**參照透明性**。
範例：
```
result1 = (fun(a) + b) / (fun(a) - c);
temp = fun(a);
result2 = (temp + b) / (temp - c);
```
若 `fun(a)` 無副作用，則 `result1 == result2`，否則不成立。
* 具參照透明性的語言（如純函數式語言）較容易分析與驗證正確性。
### Operator Overloading（運算子多載）
* 指相同的運算子可用於多種資料型別。
例：`+` 可用於整數加法與字串串接。
* 優點：增加可讀性與自然性。
* 缺點：
* 可能降低可讀性（不易分辨用途）。
* 可能隱藏錯誤（少一個運算元時編譯器無法偵測）。
例（Python）：
```python
3 + 5 # 數值加法
"Hi" + "!" # 字串串接
```
C++、C#、F# 允許使用者自訂運算子多載。
### Type Conversions（型別轉換）
* **Narrowing conversion**：轉換成較小範圍型別（如 float → int）。
* **Widening conversion**：轉換成較大範圍型別（如 int → float）。
### Mixed-Mode Expressions（混合型運算式）
* 當運算元型別不同時會自動進行轉換。
* **Coercion（強制轉換）**：編譯器自動插入型別轉換程式碼。
* 缺點：降低型別檢查能力。
* 大部分語言允許數值型混合運算。
* ML、F# 等函數式語言不允許 coercion。
### Explicit Type Conversions（明確型別轉換）
* 程式設計師主動指定轉型。
* C 語言稱為「casting」：
```c
(int) angle;
```
* F# 使用類似函式呼叫語法：
```fsharp
float(sum)
```
### Errors in Expressions（運算式錯誤）
* 可能原因：
* 除以零（division by zero）
* 溢位（overflow）
* 許多執行環境不會自動攔截此類錯誤，需由語言或開發者自行處理。
### Relational and Boolean Expressions（關係與布林運算式）
* **Relational operators**：比較兩運算元，結果為布林值。
例：`==`, `!=`, `<`, `<=`, `>`, `>=`
* 不同語言使用不同符號：
* Pascal：`<>`
* FORTRAN：`.NE.`
* Ruby：`==`（含型別轉換）與 `eql?`（不含轉換）
* JavaScript、PHP 提供 `===` 與 `!==`，不進行型別轉換。
* **Boolean operators**：`&&`, `||`, `!`
注意：C 語言無布林型別，以 `0` 代表 false，非零代表 true。
### Short-Circuit Evaluation（短路求值）
* 若運算結果已可確定，則可跳過剩餘求值。
* 範例：
```c
if (x != 0 && y / x > 2)
```
若 `x == 0`，第二個條件不會被執行。
* 範例中若未採短路求值，可能造成除以零錯誤。
### Short-Circuit Evaluation in Languages
* C、C++、Java：`&&`、`||` 採短路求值。
* 但 `&`、`|` 為位元運算，不短路。
* Python、Ruby、Perl、ML、F# 全部邏輯運算皆採短路求值。
* 注意：短路求值可能影響副作用的發生順序。
例：
```c
(a > b) || (b++ / 3)
```
### Assignment Statements（指派敘述）
* 一般語法：
```
<target_var> <assign_operator> <expression>
```
* 常見形式：
* `=` （Fortran、C、Java）
* `:=` （Ada、Pascal）
C 語言區分等號與相等：
```
= → 指派
== → 比較
```
### Conditional Targets（條件目標）
* Perl 特有的條件式指派：
```perl
($flag ? $total : $subtotal) = 0;
```
等價於：
```perl
if ($flag) { $total = 0; } else { $subtotal = 0; }
```
### Compound Assignment Operators（複合指派運算子）
* 簡化常見運算：
```
a = a + b;
```
可寫成：
```
a += b;
```
* ALGOL 最早引入，C 系語言全面採用。
### Unary Assignment Operators（一元指派運算子）
* C 系語言支援自增與自減運算：
```
sum = ++count; // count 先加一再指派給 sum
sum = count++; // 先指派再加一
```
* 也可單獨使用：
```
count++;
-count++;
```
### Assignment as an Expression（指派運算式）
* 在 C、Perl、JavaScript 中，指派語句可作為運算式使用。
例：
```c
while ((ch = getchar()) != EOF) { ... }
```
* `ch = getchar()` 的結果同時被指派與測試。
* 缺點：可能導致難以閱讀與副作用。
### Multiple Assignments（多重指派）
* Perl、Ruby、Lua 支援一次指派多個變數：
```perl
($first, $second, $third) = (20, 30, 40);
($first, $second) = ($second, $first); // 交換值
```
### Assignment in Functional Languages（函數式語言中的指派）
* 在純函數式語言中，名稱僅代表值，不可改變。
* ML 使用 `val` 繫結：
```
val fruit = apples + oranges;
```
* F# 使用 `let`：
```
let fruit = apples + oranges
```
每次新的 `val` 或 `let` 會建立新的繫結，而非修改原值。
### Mixed-Mode Assignment（混合型指派）
* 不同型別間的指派。
* Fortran、C、Perl、C++：允許任意數值型轉換。
* Java、C#：僅允許「擴大轉換（widening）」。
* Ada：完全禁止自動轉換。
### Summary
* 運算式描述程式中的運算行為。
* 主要設計議題：
* 優先順序與結合性
* 副作用與短路求值
* 型別轉換與多載
* 指派語句是命令式語言的核心，負責更新記憶體中的變數值。
* 函數式語言則以不可變（immutable）值與繫結取代指派概念。
Sign in with Wallet
Connect another wallet