---
# System prepended metadata

title: 程式語言_2025_林佳志

---

# 程式語言_2025_林佳志
## Ch1
- 語言評估標準：
  - 可讀性（Readability）：程式易於閱讀和理解
  - 可寫性（Writability）：程式易於撰寫
  - 可靠性（Reliability）：是否符合規格
  - 成本（Cost）：總體開發與維護成本
  
- 可讀性（Readability）：
  - 功能數量合理
  - 相同目的不該有太多寫法（e.g.i=i+1, i++, i+=1）
  - 運算子重載最少化：避免語意混淆
  - 正交性（Orthogonality）：少數原始架構可以自由組合，所有組合都是合法的
  - 有足夠的內建資料型態
  - 語法一致性：關鍵字、區塊結構定義明確
- 可寫性（Writability）：
  - 簡潔與正交：少量規則就能組合出需要的功能
  - 抽象能力：在忽略細節下可以定義複雜結構
  - 表達力：語言提供便捷的操作方式
- 可靠性（Reliability）：
  - 類別檢查：避免型別錯誤
  - 例外處理：攔截並處理錯誤
  - 別名（Aliasing）：不同變數指向相同記憶體位置
  - 可讀與可寫性間的平衡
- 成本（Cost）：訓練成本、開發成本、執行成本、維護成本
- 其他標準：
  - 可攜性（Portability）：是否能跨平台
  - 通用性（Generality）：是否適用多種應用
  - 定義的明確性
- 語言設計會受到硬體馮紐曼架構的影響，語言的風格會決定軟體設計的方法
- 馮紐曼架構：
  - 程式與資料都存在記憶體中
  - CPU順序為「取指令->解碼->執行」
- 程式語言分類：
  - 指令式（Imperative）：//，C、C++、Java、JS、VB.NET
  - 函數式（Functional）：LISP、Scheme、ML
  - 邏輯式（Logic）：Prolog
  - 標記混合式（Markup/Programming hybrid）：HTML、JSTL
- 設計取捨
  - 可靠性 VS 效率：Java陣列界線檢查，安全但慢
  - 可讀性 VS 可寫性：APL能做到複雜的操作，但可讀性差
  - 可寫性 VS 可靠性：C++指標強但不安全

- 實做方法
  - 編譯（Compilation）：翻譯成機器碼，執行快
  - 直譯（Pure Interpretation）：由直譯器逐行執行，開發方便但速度慢
  - 混合（Hybrid）：轉為中間碼再部分編譯
21 22 23 24 25



## Ch2 Describing syntax semantics

- 語法（Syntax）：表達式、敘述、程式單元的「結構」
- 語意（Semantics）：表達式、敘述、程式單元的「意義」
- 語法和語意構成程式語言的完整定義
- 語言（Language）：一組句子的集合
- 句子（Sentence）：某個字母表上的一串字元
- 記號（Token）：語素的類別（e.g. identifier）
- 語素（Lexeme）：語言中最低層級的語法單位（e.g.*, sum, begin）

- 辨識器（Recognizers）：能夠判斷輸入字串是否為程式語言
- 產生器（Generators）：能夠產生語言中的句子
 
- 上下文無關語法（Context-Fre Grammars）：BNF（Backus-Naur Form），用於描述自然語言語法
e.g.
  ```cpp
  C：
  sum = 3 + 4;
  ```
  ```BNF
  BNF：
  <expresion> -> <identifier> = <number> + <number>
  <identifier> -> sum
  <number> -> 3|4
  ```
- BNF：用來描述語言語法規則的表示法，用非終結符號和終結符號來定義程式語言的結構
- 非終結符號（nonterminal symbols 或 nonterminals）：以抽象概念用來表示語法結構的類別，通常以<...>表示
- 終結符號（terminal symbols）：語素或token，實際程式的符號
- 在BNF中，左邊（LHS）是非終結符號，右手邊（RHS）是終結符號和非終結符號組合而成的字串
- 文法（Gramar）：規則有限的非空集合
- 開始符號（start symbol）：開始推導語法的非中斷符號
     
  ```BNF
  Ex1:
  <ident_list> → x, <ident_list>
         → x, y, <ident_list>
         → x, y, z
  ```
  ```BNF
  Ex2:
  rules: <logic_expr> → x > y
       <stmt> → z = 1
       <if_stmt> → if <logic_expr> then <stmt>
           → if x > y then <stmt>
           → if x > y then z = 1
  ```
- BNF允許多選一，能描述單敘述或複合敘述的結構，e.g. 
  ```BNF 
  <stmt> -> <single_stmt> | begin <stmt_list> end
  ```
     
- 語法上的list結構通常用於遞迴描述，e.g.
  ```BNF 
  <ident_list> → ident | ident, <ident_list>
  ```
- 推導（derivation）：重複應用規則，從開始符號推導到只有終結符號的句子，e.g.
  ```BNF
  <ident_list> → x, <ident_list>
         → x, y, <ident_list>
         → x, y, z
  ```    
- Example Grammar：
  ```BNF
  <program> → <stmts>
  <stmts> → <stmt> | <stmt> ; <stmts>
  <stmt> → <var> = <expr>
  <var> → a | b | c | d
  <expr> → <term> + <term> | <term> - <term>
  <term> → <var> | const
  ```
  
- Example Derivation
  ```BNF
  <program> => <stmts> => <stmt>
  => <var> = <expr>
  => a = <expr>
  => a = <term> + <term>
  => a = <var> + <term>
  => a = b + <term>
  => a = b + const
  ```  
- 推導（Derivations）：
  - 句型 (sentential form)：推導過程中出現的任意符號串。
  - 句子 (sentence)：只包含終結符號的句型。
  - 左推導 (leftmost derivation)：每一步都展開最左邊的非終結符號。（註：推導沒有限定方向）  
  e.g.BNF：
  ```BNF
  <expr> → <term> + <term>
  <term> → <var>
  <var> → a | b
  ```
  - leftmost derivation：
  ```BNF
  <expr> → <term> + <term>
  → a + <term>
  → a + b
  ```
  - rightmost derivation：
  ```BNF  
  <expr> → <term> + <term>
  → <term> + b
  → a + b
  ```  
(P15)
- 剖析樹（Parse Tree）：或稱語法樹（Syntax Tree），一種階層式表示推導的方式
  ![image](https://hackmd.io/_uploads/rJDTsJLTxl.png)

- 推導（Derivation）：從文法 → 產生程式碼，目的是生成合法字串
- 剖析（Parsing）：從程式碼 → 反推出剖析樹，目的是驗證字串是否合法

- 歧義（Ambiguity）：若且唯若一個文法能產生一個句子，且該句子有兩棵以上不同的剖析樹，則該文法是有歧義的（ambiguous）
  e.g.下圖中的 `const - const / const` 有 `( const - const ) / const` 和 `const - ( const / const )`兩種剖析樹
  ![image](https://hackmd.io/_uploads/rJo0RJ86el.png)

- 無歧異表達式文法（Unambiguous Expression Grammar）：將上述程式碼的文法規則修改為無歧異
  ![image](https://hackmd.io/_uploads/ByqqeeUpgx.png)
- 剖析能藉由建立出不同的剖析樹來找出歧異，用文法規則推導的話，只能用枚舉法來做檢查
- 運算子結合律（Associativity of Operators）：`a + b + c`
  - Ambiguous: (a + b) + c or a + (b + c)
    ```BNF
    <expr> -> <expr> + <expr> | const
    ```
  - Unambiguous: (a + b) + c
    ```BNF
    <expr> -> <expr> + const | const
    ```
- 選擇文法（if-then-else）：e.g. `if (x > 0) if (y > 0) z=1 else z = -1`
  - Ambiguous:
    ```BNF
    <stmt> -> <if_stmt>
    <if_stmt> -> if (<logic_expr>) <stmt> 
           | if (<logic_expr>) <stmt> else <stmt>
    ```
    此表達式有兩種剖析樹：
    ```java
    (1)
    if (x > 0)
      if (y > 0)
        z = 1;
      else
        z = -1;

    (2)
    if (x > 0)
      if (y > 0)
        z = 1;
    else
      z = -1;
    ```
  - Ambiguous:
    ```BNF
    <stmt> -> <matched> | <unmatched>
    <matched> -> if (<logic_expr>) <stmt> else <matched>
           | <other_stmt>
    <unmatched> -> if (<logic_expr>) <stmt> 
           | if (<logic_expr>) <matched> else <unmatched>
    ```
（P21）
- Extended BNF（EBNF）：
  - 選擇部分用 \[ \] 表示，e.g. `<proc_call> -> ident [(<expr_list>)]`
  - RHS的替代選項用 ( … | … ) 表示，e.g. `<term> → <term> (+|-) const`
  - 重複用 \{ \} 表示，e.g. `<ident> → letter { letter | digit }`

- BNF and EBNF
  ```BNF
  <expr> → <expr> + <term>
       | <expr> - <term>
       | <term>
  <term> → <term> * <factor>
       | <term> / <factor>
       | <factor>
  ```

  ```BNF
  <expr> → <term> {(+ | -) <term>}
  <term> → <factor> {(* | /) <factor>}
  ```
- EBNF 的變化
  - 選項寫成多行
    ```BNF
    <digit> -> 0 | 1 | 2
    ```
    ```BNF
    <digit> : 0
    | 1
    | 2
    ```
  - 使用 : 代替 ->
  - 使用 opt 表示可選，e.g.
  `<if_stmt> : "if" <expr> "then" <stmt> ["else" <stmt>]`
  `<if_stmt> : "if" <expr> "then" <stmt> "else" <stmt>opt`

  - 使用 oneof 表示多選，e.g.
  `<bool_const> : "true" | "false“`
  `<bool_const> : oneof "true" "false`

- 靜態語意（Static Semantics）：上下文無關文法無法完整描述所有語法，例如：
  - 描述起來麻煩：如運算元的型別
  - 非上下文無關：變數必須先宣告才能使用

- **屬性文法**（Attribute Grammar）：
  - 在 CFG 上加入額外資訊，將部分語意附加在語法樹節點上，用於：
    - 指定靜態語意
    - 編譯器設計（用來做靜態語意檢查）
  - 定義：屬性文法是 CFG 𝐺 = (𝑆,𝑁,𝑇,𝑃) 的擴充：
    - 每個文法符號 𝑥 有一組屬性值 𝐴(𝑥)。
    - 每條規則都有函數定義該規則中非終結符的某些屬性
    - 每條規則有（可能為空的）述詞，用來檢查屬性一致性
  - **綜合（synthesized）屬性**：
    ```
    S(X₀) = f(A(X₁), …, A(Xₙ))
    ```
  - **繼承（Inherited）屬性**：
    ```
    I(Xⱼ) = f(A(X₀), …, A(Xₙ)) （對 i ≤ j ≤ n）
    ```
  - 葉節點最初帶有 **內生（intrinsic）**。
  - 語法：
    ```BNF
    <assign> -> <var> = <expr>
    <expr> -> <var> + <var> | <var>
    <var> A | B | C
    ```
  - actual_type（綜合屬性 Synthesized Attribute）：由下往上傳遞，表示一個語法節點實際的資料型別，e.g. `<var>`、`<expr>` 具有綜合屬性
  - expected_type（繼承屬性 Inherited Attribute）：由上往下傳遞，表示某節點在語境中應該具備的型別，e.g.`<expr>` 具有繼承屬性
  ![image](https://hackmd.io/_uploads/BkjfBSppxe.png)

- **操作語意**（Operational Semantics）：
  - 藉由在機器上執行敘述來描述意義
  ![image](https://hackmd.io/_uploads/rkfLUBp6lg.png)

- **指稱語意**（Denotational Semantics）：
  - 用數學的方式定義程式的意義，不描述「怎麼執行」，而是用函數對映說明「結果是什麼」
  - 為每個語言實體定義一個數學對象，透過「解釋函數」把語法結構轉成這些數學對象
  - 認為程式的意義只取決於變數的值，而不是執行的步驟
  - 優點是描述嚴謹，可用來證明程式正確性或語言設計分析
  - 程式狀態＝所有目前變數的值
  `s = {<i1, v1>, <i2, v2>, …, <in, vn>}`
  - VARMAP：給定變數名與狀態，回傳該變數目前值
  `VARMAP(i_j, s) = v_j`
   
- **公理語意**（Axiomatic Semantics）：
  - 以謂詞邏輯為基礎，原始目標是**形式化驗證**（verification）
  - 為各種敘述定義公理或推論規則，邏輯敘述稱為**斷言**（assertions）
  - **前置條件**（precondition）：語句前的斷言，描述變數間的關係與約束
  - **後置條件**（postcondition）：語句前的斷言，執行後真確的性質
  - **最弱前置條件**（weakest precondition）是能保證後置條件的最不嚴苛前置條件，e.g.
    ```
    x := x + 1;
    Postcondition: x > n
    Weakest Precondition: x = n
    ```
    ```
    a = b + 1  {a > 1}
    One possible precondition: {b > 10}
    Weakest precondition: {b > 0}
    ```
  - 證明流程：程式整體的後置條件是要求的結果，**由後往前**推到第一敘述，若第一敘述的前置條件等於要求，則程式正確
  ![image](https://hackmd.io/_uploads/ByeGHCaTll.png)

  - Sequences：把 S1、S2 兩段串接，以中介斷言連結，e.g.{P1} S1 {P2}、{P2} S2 {P3}
  - Selection：if B then S1 else S2
  `{B and P} S1 {Q}, {(not B) and P} S2 {Q}
   {P} if B then S1 else S2 {Q}`
  - Loops：規則需要迴圈不變式 I
    ![image](https://hackmd.io/_uploads/HJpgUR6axe.png)
  
  - 操作語意（Operational Semantics）：以**已編碼的演算法**定義狀態變化
  - 指稱語意（Denotational Semantics）：以**嚴謹的數學函數**定義狀態變化
  
## Ch5 NAMES, BINDINGS, AND SCOPES
### 名稱（Name）
- 設計考量：
  - 是否區分大小寫：區分（C、java、C#）、不區分（pascal）
  - 長度限制：現代語言通常沒有
  - 特殊字元規則：PHP 要 $ 開頭、Perl 用不同符號區分型態、Ruby 用 @、@@ 區分實例變數與類別變數。
  - 保留字（Reserved Word）：不能拿來當變數名（e.g. if, for）
  - 關鍵字（Keyword）：只有在特定語境中有特殊意義

### 變數（Variable）
- 每個變數具有六種屬性（attributes）：
	- **Name**：不是所有變數都有名稱（例如匿名變數）
 	- **Address**：變數在記憶體中的位置
 	- **Value**：變數目前存放的內容 ==（會考）==
		- **L-value**（左值）：變數的「位址」
		- **R-value**（右值）：變數的「內容」
 	- **Type**：決定變數可存放的值與可用的操作
 	- **Lifetime**：變數與特定記憶體位置綁定的時間範圍
		- Allocation（配置）：從可用記憶體中取得一個儲存格
		- Deallocation（釋放）：把儲存格歸還給系統
 	- **Scope**：在哪裡可以被看見

### 綁定（Binding）：
- 實體（entity）與屬性（attribute）之間的關聯，例如：
	- 變數與它的型別或值之間的關係
  - 運算與符號之間的關係（例如 + 對應到加法）
- **綁定時間**（binding time）：綁定發生的時間點，可能發生於：

	| 綁定階段   | 說明            | 範例                  |
	| ------ | ------------- | ------------------- |
	| 語言設計階段 | 語言的基本規則       | `+` 表示加法            |
	| 語言實作階段 | 決定資料在記憶體的表現方式 | 浮點數 IEEE754         |
	| 編譯階段   | 決定變數型別        | `int x;`            |
	| 載入階段   | 分配靜態變數空間      | `static int n;`     |
	| 執行階段   | 動態建立記憶體       | `int *p = new int;` |

#### Static and Dynamic Binding ==（會考）==
- **靜態綁定**（Static binding）：在執行前就已發生（編譯時），且在整個執行過程中不會改變
  - eg.C的靜態變數 
	- 型別可以透過 **顯式（explicit）** 或 **隱式（implicit）** 宣告決定
- **動態綁定**（Dynamic binding）：在執行期間發生，可因資料內容或執行環境而改變

#### Explicit/Implicit Declaration ==（會考）==
- Static binding下的宣告
- **顯式宣告**（explicit declaration）：透過程式語句明確宣告變數型別，e.g. `int x = 10;`
- **隱式宣告**（implicit declaration）：透過語言預設規則自動推斷型別，而不是明確宣告，e.g. `var number = 42`
	- 提供隱式宣告的語言：Python、Perl、JavaScript、Basic、Ruby、PHP
	- 優點：提高撰寫便利性
	- 缺點：降低可靠性

### Dynamic Type Binding
- 使用的語言：JavaScript、Python、Ruby、PHP、C#（部分支援）
- 透過賦值語句（assignment statement）指定型別，如：
	```javascript!
	list = [2, 4.33, 6, 8];
	list = 17.3;
	```
- 優點：靈活性高（適合泛型、快速開發）
- 缺點：執行期檢查成本高（需動態檢查型別）、編譯器難以提前發現型別錯誤

### 變數生命週期（Variable Lifetime）
- **靜態變數**（Static variables）：
	- **靜態繫結 + 明確宣告**
	- 在執行前就綁定記憶體位置，且整個程式執行期間都保持不變
	- 例如：C 與 C++ 函式中的 static 變數
	-優點：
		-高效率（直接位址存取）
		-支援需記憶狀態的副程式
	- 缺點：缺乏彈性（無法遞迴使用）
	
- **Stack-dynamic**（堆疊動態變數） ==（會考）==：
	- **動態繫結 + 明確宣告**
	- 最常用，函式呼叫時建立，才會為變數建立儲存綁定
	- 如果是純量變數（scalar），除「位址」外的屬性都是靜態綁定的
	- 例如：C 的區域變數（未使用 static 關鍵字）、Java 的方法區域變數
	- 優點：允許遞迴（recursion）、節省記憶體空間
	- 缺點：分配與釋放的開銷、子程式無法保留歷史狀態、存取較慢
	
- **Explicit heap-dynamic**（顯式堆動態變數） ==（會考）==
	- **動態繫結 + 明確宣告**
	- 由程式設計師明確指示在執行期間分配與釋放
	- 通常透過指標或參考操作，例如 C++ 中的 new 與 delete，或 Java 中的物件（由 JVM 自動管理）
	```cpp
	int* ptr = new int(5);  // 動態配置記憶體
	delete ptr;             // 手動釋放記憶體
	```
	- 優點：支援動態記憶體管理
	- 缺點：效率低、容易出錯（如記憶體洩漏）

- **Implicit heap-dynamic**（隱式堆動態變數） ==（會考）==：
	- **動態繫結 + 隱含宣告**
	- 分配與釋放是由賦值語句（assignment）自動觸發
	- 所有屬性都是動態的
		```javascript
		let list = [1, 2, 3];   // list 分配陣列
		list = "new string";    // list 被重新分配成字串
		```
	- 優點：高度彈性
	- 缺點：效率低（因為屬性需隨時檢查與調整）、錯誤偵測能力弱


### Scope（作用範圍）
- 決定變數名稱如何被解析與連結：
	- **Local variables**（區域變數）：在該程式單元中宣告的變數
	- **Nonlocal variables**（非區域變數）：在外部宣告，但在此單元中可見的變數
	- **Global variables**（全域變數）：一種特殊的非區域變數

#### **Static Scope**： ==（會考）==
- 根據程式的文字結構決定，要讓變數名稱對應到某個宣告，編譯器需搜尋宣告區塊
- 問題：
	- 大多數時候，變數可被過度訪問（太多範圍可見）。
	- 當程式演化時，結構會被破壞，原本區域的變數變成全域，子程式也傾向變成全域而非巢狀
- **搜尋順序**：由內層往外層依序查找，直到找到為止
	- 靜態祖先（static ancestors）：外層的靜態區域
	- 靜態父層（static parent）：最近的外層的靜態區
```javascript!
 function outer() {
     var a = 10;
     function inner() {
         var b = 20;
         console.log(a);  // 在靜態作用範圍下，a 是 outer 函式內部的變數
    }
     inner();
 }
 outer();
```
- 如果同名變數在較近範圍被重新宣告，外層同名變數會被隱藏（hide）
```CPP
 int x = 10;
 void func() {
 int x = 20;  // 這個 x 遮蔽了外部的 x
 std::cout << x;  // 輸出 2
 }
```
- 區塊：在程式內建立靜態作用範圍的一種機制
	- 同個區塊定義同名變數，在 C 與 C++ 是合法的，但在 Java 與 C# 中是非法的
	```C
	void sub() {
		int count;
		while (...) {
			int count;
			count++;
		}
	}
	```
	
	```java
	public class Example {
		 public void method() {
			int count = 10;
	 		if (someCondition) {
	 			int count = 20;  // 這行程式碼在 Java 中是非法的，因為同一個方法內不能有同名的區域變數
			}
	 	}
	}
	```

#### LET
- 大多數函數式語言都有 let 結構
- 在靜態作用範圍中建立暫時的變數綁定，執行完區塊後，變數就消失
- let 有兩個部分：
	- 第一部分：將名稱綁定到值（binding）
	- 第二部分：使用這些已綁定的名稱進行運算
	- e.g.`(let ((x 5) //x 被綁定到 5` 
	      `    (y 10)) // y 被綁定到 10`
				`    (+ x y)) //使用 x 和 y 進行計算`

#### Declaration Order（宣告順序）
- C99、C++、Java、C# 都允許變數宣告出現在任何語句可出現的位置
	- C99、C++、Java：所有區域變數的作用範圍（scope）從宣告開始直到該區塊結束
	- C#：
		- 任何變數在區塊中的作用範圍是整個區塊，不論宣告出現在哪裡
		- 不過變數仍必須在使用之前宣告

- **Global Scope**：
	- C、C++、PHP、Python允許在函式外面宣告變數
	- C、C++ 區分：
		- **宣告（declaration）：只描述變數屬性**
		- **定義（definition）：同時分配儲存空間**
	```CPP	
	// a.cpp
	extern int x;   // 宣告變數 x 在另一檔案定義

	// b.cpp
	int x = 10;     // 定義變數 x 並分配記憶體
	```
- PHP：變數預設是「區域性的」，如果要讓函式能修改全域變數，需用 global 或 $GLOBALS
- Python：全域變數可以在函式中被參照，但要在函式內修改它，必須使用 global 聲明
	```python
	x = 10  # 全域變數
	def func():
		global x
		x = 20  # 修改全域變數
	```

#### **Dynamic Scope**（動態作用域）： ==（會考）==
- 基於程式的呼叫順序，而非文本結構
- 對變數的參照會沿著呼叫鏈（call chain）往回搜尋，直到找到該變數的宣告位置為止
- 優點：方便
- 缺點：
	- 當子程式執行時，其變數對所有呼叫的子程式都可見
	- 無法靜態檢查型別
	- 可讀性差：無法從程式文本靜態判斷變數的型別
	![image](https://hackmd.io/_uploads/rkPlw-MClx.png=100%X)
		- Static Scoping：
			- sub2 在 big 裡面定義
			- sub2 沒有 x，向外找 → 找到 big 的 x = 3
			- 靜態綁定 → x = 3
		- Dynamic Scoping：
			- big() → sub1() → sub2()（依照實際的呼叫順序）
			- 當 sub2 執行時，它會回溯呼叫堆疊
			- 在 sub1 的中有 x = 7。
			- 動態綁定 → x = 7

### Scope and Lifetime ==（會考）==
![image](https://hackmd.io/_uploads/S1sInZzRxg.png)
- Scope（作用域）：在「哪裡」可見
	- e.g. count 只能在 func() 函式內使用
- Lifetime（生命週期）：在「何時」存在
	- e.g. static int count 在第一次呼叫時建立，之後一直存在，直到程式結束才釋放

### 參照環境（Referencing Environments）
- 某一個敘述（statement）中，所有可見變數所形成的集合
- 在**靜態作用域語言**中，參照環境由：當前區塊的區域變數，以及所有外層區塊中仍可見的變數組成
- 在**動態作用域語言**中，參照環境是：目前副程式的區域變數，加上所有活躍中的副程式之中可見的變數


## Ch6 DATA TYPES
### 基本資料型別（primitive data types） ==（會考）==
- 不是由其他型別定義出來的型別
- **Integer**：幾乎完全對應到硬體，所以轉換很簡單
- **Floating Point**：浮點數用來表示實數，但只是近似值
- **Complex**（複數）：
	- 有些語言（如 C99、Fortran、Python）支援複數型別
	- 每個複數由兩個浮點數組成：實部（real part）與虛部（imaginary part）
	- 在 Python 中，複數為`(7 + 3j)`，其中 7 是實部，3 是虛部
- **Decimal**：
	- 主要用於商業應用（如金錢計算）
	- 儲存方式為固定數量的十進位數字，通常以BCD形式表示
	- 優點（Advantage）：高精確度
	- 缺點（Disadvantages）：範圍有限、浪費記憶體空間
- **Boolean**：兩個元素（true or false），通常以一個位元組（byte）實作，可讀性高
- **Character**：以數值編碼（ASCII, Unicode）形式儲存
- String：字元序列組成的值
	- C 與 C++：不是基本型別
	- SNOBOL4、Fortran 與 Python：為基本型別
	- Java：String 類別提供基本型別功能
	- 靜態長度（Static）：COBOL、Java 的 String 類別
	- 限制性動態長度（Limited Dynamic Length）：用特殊字元（例如 '\0'）來標示字串結尾，而不是儲存長度，C 和 C++
	- 動態長度（Dynamic）：無最大值，SNOBOL4、Perl、JavaScript、Python
	- 編譯期描述符（Compile-time descriptor）：用於靜態字串
		- 記錄：字串、長度、位址
	- 執行期描述符（Run-time descriptor）：用於限制性動態字串
		- 記錄：最大長度、當前長度、位址
	![image](https://hackmd.io/_uploads/rJAZyXfRgl.png)

### Array Types ==（會考）==
- 陣列（Array）：一種同質（homogeneous）資料集合
- 每個元素的位置可由相對於第一個元素的索引（index）識別
- 下標範圍檢查（Range checking）：
	- C、C++、Perl、Fortran：不執行範圍檢查
	- Java、ML、C#：執行範圍檢查
- 下標綁定（Subscript Binding）：
	- Static：下標範圍在編譯時期靜態綁定，記憶體配置於執行前完成
		- 優點：效率高（無需動態配置）
	- Fixed Stack-Dynamic：下標範圍在編譯期決定，但配置在宣告時於堆疊進行
		- 優點：空間效率高（釋放自動化）
	- Fixed Heap-Dynamic ==（會考）==：類似 fixed stack-dynamic，但使用heap分配，綁定在配置時進行（使用者要求時），配置完成後固定
	- Heap-Dynamic：下標範圍與記憶體分配皆為動態的，並且可多次改變
		- 優點：彈性高（陣列可在執行期間成長或縮小）
- C / C++：
	- 含 static 修飾詞的陣列：靜態（static）
	- 無 static 修飾詞的陣列 → 固定堆疊動態（fixed stack-dynamic）
	- 提供固定堆積動態（fixed heap-dynamic）陣列
- C#：提供 ArrayList 類別支援固定堆積動態（fixed heap-dynamic）
- Slice：
	```python
	vector = [2,4,6,8,10,12,14,16]
	mat = [[1,2,3],[4,5,6],[7,8,9]]
	vector[3:6]  # => [8,10,12]
	mat[0][0:2]  # => [1,2]
	```
- 陣列位址公式：address(list[k]) = address(list[lower_bound]) + ((k - lower_bound) * element_size)

### 關聯式陣列（Associative Arrays）
- 可以用鍵（key）取值，e.g. 字典（Dictionary）、map

### 紀錄型別（Record Types）
- 紀錄是一種異質集合（heterogeneous aggregate），即每個欄位可以有不同型別C
```C
struct Student {
    char name[20];
    int age;
    float score;
};
```

### 元組型別（Tuple Types）
- 像紀錄一樣能包多種資料，但沒有欄位名稱，常用於函式回傳多個值
```python
person = ("Alice", 20, 95.5)
```

### 串列型別（List Types）
- 在語言如 Lisp、Scheme、Python 中常見，串列是可以增刪元素的動態結構
```Python
nums = [1, 2, 3, 4]
nums.append(5)
```

### 聯集型別（Union Types）
- 允許同一個變數在不同時間存放不同型別的值，但要小心型別安全問題
```C
union number {
    int i;
    float f;
};
```

### 指標與參考型別（Pointer and Reference Types）
- 指標存放「記憶體位址」，可間接操作資料
- 常見問題：
	- **Dangling pointer**（懸空指標）：一個指標仍然存在，但它指向的記憶體位置已經被釋放或重用
	- Memory leak（記憶體洩漏）：記憶體還在，但失去了它的指標
- 在 Java、C# 中，用reference代替指標，較安全

### Strong Typing（強型別）
- 語言能夠嚴格檢查型別，確保型別錯誤一定會被偵測出來，避免在執行期出問題
- 強型別：不允許不同型別之間的隱式錯誤轉換，python、java、C#
- 弱型別：允許你做一些型別不合邏輯的事，C、C++、JavaScript

## Ch7 EXPRESSIONS AND ASSIGNMENT STATEMENTS
- 表達式（Expression）：程式語言中指定運算的基本手段，e.g. int result = 5 + 3 * 2
### 算術表達式（Arithmetic Expression）
- 由運算子、運算元、括號和函數呼叫組成
	- 一元運算子（Unary）：只有一個運算元，e.g. ++x, x++
	- 二元運算子（Binary）：有兩個運算元，e.g. a + b, a && b
	- 三元運算子（Ternary）：有三個運算元，e.g. int x = (a > b) ? a : b;
- 運算子**優先順序**規則（operator **precedence** rules）：定義不同優先級的「相鄰」運算子執行順序，典型順序為：括號 > 一元運算子 > ** > *, / > +, - （==會考==）
- 運算子**結合性**規則（Operator **Associativity** Rule）：定義相同優先級的相鄰運算子執行順序，通常為左到右（** 為右到左，e.g. 2 ** 3 ** 2 = 2^(3 ^ 2) = 512）（==會考==）
- **條件表達式** (**Conditional Expressions**)：C 系列語言（C, C++, Java 等）支援，e.g. average = (count == 0)? 0 : sum / count
- 運算元求值順序（Operand Evaluation Order）：
	- 變數：從記憶體存取值
	- 常數：從記憶體或機器指令中
	- 括號表達式：優先計算內部
	- 函數呼叫：最不穩定
- 函數副作用（Functional side effects）：
	- 當函數改變了雙向參數（傳位址／參考）或非區域變數時發生
	- 例如表達式中的函數修改了另一個運算元，就會影響結果
	- e.g. b = a + fun(&a)
	- 解法有兩種：
		1. 透過定義來避免副作用：
			- 函數不允許雙向參數、修改非區域變數
			- 優點：絕對有效
			- 缺點：喪失靈活性
		2. 語言定義固定運算元求值順序：
			- 缺點：限制了編譯器的最佳化空間
			- Java強制規定由左至右求值
- 參考透明性（Referential Transparency）：程式中任何兩個具有相同值的運算式，都可以互相替換，而不影響程式行為（==會考==）
	- result1 = (fun(a) + b) / (fun(a) - c)
	- temp = fun(a); result2 = (temp + b) / (temp - c)
	- 具有參考透明性的話，result1 會等於 result2
	- 優點：程式語意更容易理解

### 運算子多載（Overloaded Operators）（==會考==）
- 一個運算子用於多種用途，e.g. + 可用於整數和浮點數
- 降低可讀性、降低編譯器偵錯能力
- C++, C# 允許使用者自定義多載運算子
- 優點：合理使用可以提升可讀性
- 缺點：使用者可能定義出荒謬的運算，並且會降低可讀性

### 型別轉換（Type Conversions）
- Narrowing conversion（縮小轉換）：危險，將物件轉換為無法包含原始型別所有值的型別，e.g. float 轉 int
- Widening conversion（擴大轉換）：安全，將物件轉換為至少能包含原始型別所有近似值的型別，e.g. int 轉 float
- Mixed-mode expression：運算元型別不同的運算式
	- Coercion：隱式（自動）型別轉換
	- 缺點：降低了編譯器偵測型別錯誤的能力
	- 大多數語言中，數值型別會自動進行擴大轉換
- 顯式型別轉換（Explicit Type Conversions）
	- Casting：C語言中的轉型
	- e.g. (int) angle

### 運算式中的錯誤
- Inherent limitations of arithmetic：算術原本的限制
	- e.g. Division by zero（除以零）
- Limitations of computer arithmetic：電腦算術的限制
	- e.g. Overflow（溢位）

### 關係與布林運算式
- 關係運算式（Relational Expressions）：使用關係運算子比較數值，回傳布林值
- Operator symbols：符號各語言不同，e.g. !=, /=, <>, # 都是不等於
- 布林運算式（Boolean Expressions）：運算元是布林值，結果也是布林值，e.g. &&, ||, !
- Odd characteristic of C：C 語言的一個怪異特性
	- e.g. a < b < c 意思是 (a < b) < c，前面計算出 0 或 1 再和 c 比大小

### 短路求值（Short Circuit Evaluation）（==會考==）
- 運算結果在未評估完所有運算元時就已確定
- e.g. (13 * a) * (b / 13 - 1)，如果 a 是 0 就不需要算後面了
- e.g. while (index <= length) && (LIST[index] != value)，有前面的判斷可以避免超出索引值的錯誤發生
- C, C++, Java：一般布林運算子（&&, ||）支援短路，但位元運算子（&, |）不支援
- 潛在問題：e.g. (a > b) || (b++ / 3)，若 a > b 為真，後面的 b++ 永遠不會執行，b 就不會加 1

### 賦值語句（Assignment Statements）
- 語法：<目標變數> <賦值運算子> <運算式>
- 運算子： = （Fortran, C, Java 等）
- 壞的做法： = 被多載為相等（所以C語系用==）
- Conditional targets：Perl 允許條件式目標
	- e.g. ($flag ? $total : $subtotal) = 0
	- 如果 flag 為真，則 $total = 0，否則 $subtotal = 0
- 複合賦值運算子（Compound Assignment Operators）：指定常用賦值形式的簡寫方法，e.g. a += b
- Unary assignment operators：C 語言系結合了遞增／遞減與賦值
	- sum = ++count： count 先加 1，再賦值給 sum
	- sum = count++： count 先賦值給 sum，然後 count 再加 1
	- count++：count 加 1
	- -count++：count 先加 1，然後取負值
- 賦值作為運算式（Assignment as an Expression）：賦值語句本身會產生一個結果，可以當作運算元
	- e.g. while ((ch = getchar()) != EOF) { ... }
	- getchar() 執行後賦值給 ch，然後把 ch 的值再拿去跟 EOF 比較
	- 缺點：產生另一種運算式副作用
- 多重賦值（Multiple Assignments）：
	- Perl, Ruby, Lua 允許多重賦值，e.g. ($first, $second, $third) = (20, 30, 40);
	- Interchange（Swap）：交換數值變得很合法且簡單，e.g. ($first, $second) = ($second, $first);
		- e.g. Python：a, b = b, a
- 函數式語言中的賦值：函數式語言中的識別字只是數值的名稱
	- ML 使用 val 綁定名稱，e.g. val fruit = apples + oranges，後面再出現 val fruit 的話就是新的名稱
	- F#的 let 類似 val，但 let 會建立一個新的作用域
- 混合模式賦值（Mixed-Mode Assignment）：
	- C、C++：任何數值型別都可以賦值給任何數值變數（自動轉）
	- C#：只允許擴大轉換的自動賦值

## Ch8 STATEMENT LEVEL CONTROL STRUCTURES
- 控制結構（Control Structure）：包含一個「控制敘述」以及該敘述所控制的「執行語句」（==會考==）
	- 控制結構有多重入口是壞的設計，通常被現代語言禁止
### 選擇敘述（Selection Statements）（==會考==）
- 提供在兩條或多條執行路徑中進行選擇的方法，兩大類別：
	- 雙向選擇器（Two-way selectors）
		- e.g. if (條件) { 當條件為真時執行這裡 } else { 當條件為假時執行這裡 }
	- 多向選擇器（Multiple-way selectors）
		- e.g. switch (數值) { case 1: ... break; case 2: ... break; default: ... break; }
#### 雙向選擇敘述（Two-Way Selection Statements）
- 一般形式：
	- if 控制運算式
	- then 子句
	- else 子句
- 控制運算式（The Control Expression）：如果沒有使用 then 保留字，控制運算式通常放在括號中
	- Python、C++：控制運算式可以是數字，e.g. if(1)
	- 大部分語言：控制運算式必須是布林值
- 子句形式（Clause Form）：then 和 else 子句可以是單一敘述或複合敘述
	- Perl：所有子句必須用大括號 {} 界定
	- Python：使用縮排（indentation）來定義子句
- 巢狀選擇器（Nesting Selectors）：
	- Java 靜態語意規定 else 與其最近的前一個 if 匹配
	- e.g.下列 java 程式碼中的else 和 if (count == 0) 配對
		```java
		if (sum == 0)
			if (count == 0)
				result = 0;
		else result = 1;
		```
	- 若要強制改變語意，可以使用複合敘述（加括號）
	- Ruby：使用敘述序列作為子句，每個 if 都有對應的 end
	- Python：透過 if、else 的縮排來做配對
- 選擇器運算式（Selector Expressions）：
	- 在 ML、F#、Lisp 中，選擇器是一個運算式，if會回傳數值，因此需要 else 子句做搭配，then 和 else 子句回傳的值型別必須相同，e.g.
	```F#
	let y = 
		if x > 0 then x
		else 2 * x
	```

#### 多向選擇敘述（Multiple-Way Selection Statements）
- 允許在任意數量的敘述或敘述群組中選擇一個
- C、C++、Java、JavaScript：
	```cpp
	switch (expression) {
		case const_expr1: stmt1;
		…
		case const_exprn: stmtn;
		[default: stmtn+1]
	}
	```
- C語言 switch 敘述的設計選擇：
	- 控制運算式只能是整數型別
	- 可選擇的片段可以是敘述序列、區塊或複合敘述
	- 在該結構的一次執行中，可以執行任意數量的片段（沒有寫 break，繼續往下執行下一個 case）
	- default 子句用於未列出的值（如果沒有 default則略過）
- C#：
	- 有靜態語意規則，不允許隱式執行超過一個片段
	- 每個可選擇片段必須以無條件分支（goto 或 break）結束
	- 控制運算式和 case 常數可以是字串（strings）
	```csharp
	string number = “two”;
	switch (number)
	{
	    case “one”:
	        Console.WriteLine("One");
	        break;
	    case “two”:
	        Console.WriteLine("Two");
	        break;
	    default:
	        Console.WriteLine("Other number");
	        break;
	}
	```
- 實作多向選擇器
	- 多重條件分支（就像一堆 if-else），可以作為雙向選擇器的直接擴展
	```python
    if count < 10 : bag1 = True
    elif count < 100 : bag2 = True
    elif count < 1000 : bag3 = True
	```
	- 將 case 值儲存在表格中，並對表格進行線性搜尋
	- 當 case 超過十個時，可以使用 case 值的雜湊表（hash table）

### 迭代敘述（Iterative Statements）
- 透過迭代（iteration）或遞迴（recursion）重複執行敘述或複合敘述
#### 計數器控制迴圈（Counter-Controlled Loops）：
- 計數迭代敘述有一個迴圈變數，以及指定初始值、終止值和步進值（stepsize）
- 基於 C 的語言：`for ([初始] ; [條件] ; [更新]) statement`
	- 沒有明確的迴圈變數、迴圈內的一切都可以更改
	- 第一個運算式評估一次，但其他兩個每次迭代都會評估
	- C++ 允許初始運算式可以包含變數定義（範圍是從定義到迴圈主體結束）
- python：
	```Python
	for loop_variable in object: 
	    loop body
	[else:
	    else clause]
	```
	- object 是一個範圍（range），例如列表 [2, 4, 6] 
	- 迴圈變數會在每次迭代中取得給定範圍內的指定值
	- else 子句是選用的，如果迴圈正常終止（沒被 break）就會執行

#### 邏輯控制迴圈（Logically-Controlled Loops）
- 基於一個布林運算式做重複
- C 和 C++ 都有前測和後測形式，其中控制運算式可以是算式：
	- while (control_expr) ... 和 do ... while (control_expr)
- Java：控制運算式必須是布林值

#### 使用者自訂迴圈控制
- 使用者可以自行決定跳出的位置（頭尾之外）
- C、C++、Python、Ruby、C# 有無條件、無標籤的出口 break
- Java、Perl 有無條件、有標籤的出口，Java 是 break label，Perl 是 last
- C、C++、Python 有無標籤的控制敘述 continue，會跳過當前迭代的剩餘部分，但不離開迴圈
- Java 和 Perl 有有標籤版本的 continue

#### 資料結構的迭代
- 透過資料結構中的元素數量做迭代，用來走訪資料結構
- 呼叫一個迭代器（iterator）函式，該函式以某種選擇的順序回傳下一個元素
- C：for (p=root; p==NULL; traverse(p)) { }

### 無條件分支（Unconditional Branching）（==會考==）
- 將執行控制權轉移到程式中的指定位置，會嚴重影響可讀性，e.g. goto
- C# 提供 goto 敘述，有些語言（例如 Java）不支援 goto 敘述

### 守衛命令（Guarded Commands）
- 同時檢查所有條件，如果有好幾個都成立，隨機選一個執行
- 支援一種新的程式設計方法論，該方法論支援開發過程中的驗證
	- 基本概念：如果評估順序不重要，程式就不應該指定順序
	- 形式：`if <Boolean expr> -> <statement> [] ... fi`
	- 語意：當結構被抵達時，評估所有布林運算式：
		- 如果超過一個為真，非決定性地（non-deterministically） 選擇一個
		- 如果沒有一個為真，則為執行時期錯誤（runtime error）

#### 迴圈守衛命令（Loop Guarded Command）
- 形式：`do <Boolean> -> <statement> [] ... od`
- 語意：對於每次迭代，評估所有布林運算式：
	- 如果超過一個為真，非決定性地選擇一個，然後再次開始迴圈
	- 如果沒有一個為真，退出迴圈

#### 理由
- 證明控制敘述與程式驗證之間的連結是緊密的
- 使用 goto 敘述是不可能進行驗證的
- 僅使用選擇和邏輯前測迴圈是可能進行驗證的
- 僅使用守衛命令進行驗證相對簡單

## Ch9 SUBPROGRAMS
- 子程式：（==會考三要素==）
	- 每個子程式都有單一的入口點
	- 在執行被呼叫的子程式期間，呼叫它的程式會暫停（suspended）
	- 當子程式執行終止，控制權會回到呼叫者（caller）
- 定義：
	- 子程式呼叫是對執行子程式的顯式請求
	- 標頭（header）：包括名稱、子程式種類和形式參數，e.g. def my_func(x, y):
	- 參數輪廓（parameter profile）：又稱簽章（signature），參數的數量、順序和型別，e.g. 傳入兩個整數
	- 協定（protocol）：輸入 + 輸出的規格
	- C 和 C++ 中的函式宣告通常稱為原型（prototypes）
	- 子程式宣告提供協定，但不會定義實際功能

### 參數
- **形式參數**（Formal parameter）：列在子程式標頭中的虛擬變數，並在子程式中使用，e.g. add(x, y) 的 x 和 y（==會考==）
- **實際參數**（Actual parameter）：子程式呼叫敘述中使用的數值或位址，e.g. add(3, 5) 的 3 和 5（==會考==）
- 參數間的對應：
	- 位置對應（Positional）：實際、形式參數透過位置綁定，e.g. func(10, 20)
		- 安全且有效
	- 關鍵字對應（Keyword）：實際參數需指定形式名稱，e.g. func(height=20, width=10)
	- 優點：參數可以以任何順序出現，從而避免參數對應錯誤
	- 缺點：使用者必須知道形式參數的名稱
- 在某些語言中，形式參數可以有預設值，e.g. def func(x=10)
- 在 C++ 中，預設參數必須出現在最後，因為參數是按位置關聯的
- Python：def add_numbers(*args)，使用 *args 來接收多個參數
- Lua：function print_args(...)，使用 ... 來接收多個參數

### 程序（Procedures）與函式（Functions）
- 子程式有兩種類別：
- 程序：像數學的 $f(x) = y$，給輸入就回傳輸出，理論上不該改變外界狀態
- 函式：結構上類似程序，但在語意上是模仿數學函式

### 區域參考環境（Local Referencing Environments）
- 區域變數可以是堆疊動態（stack-dynamic）或靜態（static）
- 堆疊動態（stack-dynamic）：
	- 優點：
		- 支援遞迴
		- 子程式間可以共享區域變數
	- 缺點：
		- 分配/釋放、初始化的時間成本
		- 間接定址、子程式無法保留過去紀錄
- 靜態（static）：
	- 優點和缺點與前者相反

### 參數傳遞模式
- 輸入模式（In mode）：傳入的值不會改變原變數
- 輸出模式（Out mode）：傳入位址，函式負責填值進去
- 輸入輸出模式（Inout mode）：傳入列表，修改後原列表改變
![image](https://hackmd.io/_uploads/Sk8qqWjfbl.png)
- 物理移動數值（Physically move a value）：修改數字副本，不影響原變數
- 移動數值的存取路徑 (Move an access path to a value)：傳參考，原列表會被修改

### Pass-by-Value（In Mode） （==會考==）
- 傳值：實際參數的值被用來初始化對應的形式參數
- 通常透過複製實作
- 優點：安全
- 缺點：需要額外的儲存空間、實際移動成本可能很高

### Pass-by-Result（Out Mode）
- 傳結果：當參數按結果傳遞時，沒有數值傳送到子程式
- 對應的形式參數作為區域變數，當控制權回到呼叫者時，其值透過物理移動傳送到呼叫者的實際參數
- 問題：出現 sub(p1, p1) 情況會發生混亂
- 程式碼展示如何模擬這個過程：建立一個臨時變數 temp，函式修改 temp，最後再把 temp 的值塞回 y
![image](https://hackmd.io/_uploads/rkO-TWsMZl.png)

### Pass-by-Value-Result（Inout Mode）（==會考==）
- 傳值-結果（輸入輸出模式）：或稱為傳複製 （pass-by-copy），形式參數有區域儲存空間
- 程式碼先把外部變數 y 複製給 temp （Value），函式修改 temp，函式結束時再把 temp 複製回 y （Result）

![image](https://hackmd.io/_uploads/S1P6abjMWg.png)

### Pass-by-Reference（==會考==）
- 傳參考（輸入輸出模式）：傳遞存取路徑，也稱為傳共享 （pass-by-sharing）
- 優點：傳遞過程效率高（無需複製和重複儲存）
- 缺點：潛在的非預期副作用、非預期的別名 （aliases）
![image](https://hackmd.io/_uploads/HJJdAZjGZx.png)

| 參數傳遞方式 | 機制 | 特性 | 適用場景 |
| :--- | :--- | :--- | :--- |
| **Pass by Value**<br>(傳值) | 呼叫函式時，傳遞的是參數的**副本**。函式內部的改變**不會**影響原變數。 | • 原變數和函式內的參數是獨立的，互不影響。<br>• 傳遞較大的資料結構（如陣列）時，會有高額的記憶體複製開銷。 | • **參數是唯讀**的場景。<br>• 確保原始變數不會被函式意外修改。 |
| **Pass by Result**<br>(傳結果 / Out Mode) | 呼叫函式時不傳值，參數在函式內部進行操作，**回傳結果時**才會**複製**回原變數。 | • 函式內部的參數在使用前**未初始化**。<br>• 僅在回傳時更新原變數。<br>• 若多個參數指向同一變數（Aliasing），可能會有同步性問題。 | • **原始值不重要**，但結果需要回寫時適用。<br>• 例如：單純的計算輸出或轉換操作。 |
| **Pass by Value-Result**<br>(傳值-結果 / Inout Mode) | 呼叫函式時傳遞**副本**進去，函式操作後，結束時再將結果**複製**回原變數。 | • 結合了 Pass by Value 和 Pass by Result。<br>• 函式執行期間參數與原變數分開，但結束時會同步。<br>• 又稱為 Pass-by-Copy。 | • 需要**讀取並修改**變數的場景。<br>• 例如：累積結果或中間值的計算。 |
| **Pass by Reference**<br>(傳參考 / Inout Mode) | 呼叫函式時，傳遞的是參數的**引用或位址**，函式內部**直接操作**原變數。 | • 呼叫時**沒有資料複製**的開銷（高效率）。<br>• 函式內部的修改會**即時**且**直接**影響原變數。<br>• 需注意別名（Alias）與副作用問題。 | • 需要**直接操作原變數**的場景。<br>• 例如：修改大型資料結構、共享變數的多執行緒操作。 |

### Pass-by-Name（==會考==）
- 傳名（輸入輸出模式）：透過文字替換
- 形式參數在呼叫時綁定到存取方法，但實際綁定到數值或位址是在被引用或賦值時才發生
- 允許延遲綁定的靈活性
![image](https://hackmd.io/_uploads/Sk31lMjM-x.png)

### 參數傳遞方法
- 參數溝通是透過執行時期堆疊（run-time stack）進行
- 傳參考是最容易實作的，只有位址被放在堆疊中
![image](https://hackmd.io/_uploads/rkN6ezsGWe.png)
- C：
	- 傳值（Pass-by-value）
	- 傳參考是透過將指標（pointers）作為參數來達成
![image](https://hackmd.io/_uploads/HJBBWzjzWx.png)
- C++：
	- 和前面C相同，但多了傳參考語法
![image](https://hackmd.io/_uploads/HkGUZzsGbg.png)
- Java：
	- 所有參數都是傳值
	- 物件參數是傳遞參考的值（傳遞參考值的副本，還是可以操控物件）
![image](https://hackmd.io/_uploads/S1IyGMifZg.png)
- C#：
	- 預設傳值
	- 傳參考是透過在形式參數和實際參數前都加上 ref 來指定
![image](https://hackmd.io/_uploads/SkrgMzoGbx.png)
- Python：
	- 使用傳賦值（pass-by-assignment）：
	- 如果傳的是可變物件（如 List），函式內修改會影響外面（像傳參考）
	- 如果傳的是不可變物件（如 Int, String），函式內修改會變成一個新物件，不影響外面（像傳值）
- 多維陣列作為參數：
	- 如果多維陣列被傳遞給子程式且分開編譯，編譯器需要知道陣列的宣告大小以建立儲存映射函式
	- 程式設計師必須在實際參數中包含除第一個下標外的所有宣告大小

### 綁定方式：
#### Shallow binding （==會考==）
- 淺層綁定：執行傳遞子程式的呼叫敘述的環境（在哪裡呼叫，就用哪裡的變數）

#### Deep binding （==會考==）
- 深層綁定：被傳遞子程式定義時的環境（在哪裡出生，就用哪裡的變數）

#### Ad hoc binding
- 隨機綁定：呼叫敘述傳遞子程式時的環境

### 間接呼叫子程式
- 在 C 和 C++ 中，這類呼叫是透過函式指標（function pointers）達成的
- C：使用 void (*funcPtr)() 宣告指標，根據使用者輸入決定指向 sayHello 還是 sayGoodbye
- C#：方法指標被實作為物件，稱為委派（delegates）
	- 多播委派：一個委派可以儲存、呼叫多個位址

### 重載子程式（Overloaded Subprograms）
- 同一參考環境中與另一個子程式同名的子程式
- e.g. add(int a, int b)、add(float a, float b)

### 泛型子程式（Polymorphic Subprogram） （==會考==）
- **泛型子程式**（Polymorphic／Generic Subprograms）：在不同啟動中接受不同型別的參數，e.g. List \<T\>
- **子型別多型**（Subtype polymorphism）：宣告一個變數是 T 型別（父類別），子型別多型能接受 T 本身或 T 的子類別 （==會考==）
- C++：
	- 泛型子程式的版本是在呼叫時隱式建立的
	- 泛型子程式前面有 template 子句
	![image](https://hackmd.io/_uploads/HJL6tMoGZl.png)
- Java：
	- Java 的泛型參數必須是類別（Classes），不能是基本型別（如 int）
	- Java 泛型方法只實例化一次（Type Erasure）
	- E.G. `public static <T> T doIt(T[] list) { }`
	![image](https://hackmd.io/_uploads/SkuU9fszbx.png)

### 閉包（Closure） （==會考==）
- 閉包：一個子程式及其被定義時的參考環境
- 如果子程式可以從程式的任意位置被呼叫，則需要參考環境
- JavaScript 閉包範例：
![image](https://hackmd.io/_uploads/SkFThGsfbg.png)
- C# 閉包範例：
![image](https://hackmd.io/_uploads/SyglaMjf-x.png)

### 協程（Coroutines） （==會考==）
- 協程：擁有多個入口點並自行控制它們的子程式
	- 協程呼叫稱為 resume
	- 也稱為對稱控制（symmetric control）：呼叫者和被呼叫的協程處於更平等的基礎上
![image](https://hackmd.io/_uploads/BkkDTfiz-e.png)
![image](https://hackmd.io/_uploads/HJFDpGsfZe.png)
![image](https://hackmd.io/_uploads/HJ1O6fifZe.png)


## Ch10 Implementing Subprograms
### 啟動紀錄（Activation record）
- **啟動紀錄**（Activation record）：執行中子程式的非程式碼部分的格式（==會考==）
- 啟動紀錄實例（activation record instance）：啟動紀錄的具體範例
![image](https://hackmd.io/_uploads/rkUT6tpGZe.png)
![image](https://hackmd.io/_uploads/HkMJ0tTz-e.png)
![image](https://hackmd.io/_uploads/r19mCKpGWl.png)
- **動態鏈結**（Dynamic link）：指向呼叫者的啟動紀錄實例頂端 （==會考==）
- **環境指標**（Environment Pointer）：由執行時期系統維護，總是指向當前執行程式單元的啟動紀錄實例的基底 （==會考==）
- **動態鏈**（dynamic chain）：堆疊中在特定時間點的所有動態鏈結的集合 （==會考==）
- **local_offset**：區域變數可以透過其與啟動紀錄開頭的偏移量 (offset) 來存取 （==會考==）
- **靜態鏈**（static chain）：連接特定啟動紀錄實例的靜態鏈結串列 （==會考==）
- **靜態鏈結**（static link）：子程式 A 的啟動紀錄中的靜態鏈結指向 A 的靜態父層的啟動紀錄實例（==會考==）

### 動態作用域
- 深層存取（Deep Access）：透過搜尋動態鏈上的啟動紀錄實例來尋找非區域參考
	- 鏈的長度無法靜態決定
- 淺層存取（Shallow Access）：將區域變數放在一個中心位置
![image](https://hackmd.io/_uploads/rkkZrc6MZe.png)


## Ch11 Abstract Data Types and Encapsulation Concepts
### Concept of abstraction （==會考==）
- **抽象化**（Abstraction）：實體表現形式只包含最重要的屬性
- 過程抽象化：透過子程式（函式）來支援
- 資料抽象化：省略型別的實作方式
#### 資料抽象化（Data Abstraction） 
- 抽象資料型別（ADT）：一種使用者定義的資料型別，它滿足以下兩個條件：
	- 對使用這些物件的程式單元是隱藏的
	- 該型別的宣告以及對該型別物件操作的協定（介面），都包含在一個單一的語法單元中
- 優點： 
	- 可靠性（Reliability）：透過隱藏資料表示方式，使用者無法直接存取或修改該型別物件的程式
	- 名稱衝突的可能性降低
	- 有助於可修改性（modifiability）
- 建構子（Constructors）：用來初始化實例資料成員的函式
- 解構子（Destructors）：在實例被銷毀後負責清理的函式
### 封裝（Encapsulation）（==會考==）
- 將資料（屬性）與操作這些資料的程式碼（方法/函式），包裹在一個單一的語法單元（通常是 Class 類別）之中
- 資訊隱藏（Information Hiding）：
	- 隱藏細節：將物件內部的運作細節和資料結構隱藏起來，不讓外部直接存取或修改
	- 開放介面：只提供特定的公開方法（Public methods）讓外部使用

## Ch12 Support for Object-Oriented Programming
- 繼承（Inheritance）：
- 動態繫結（Dynamic Binding）：多型變數可以定義在類別中，它能夠參考（或指向）該類別的物件及其任何後代物件（==會考==）
- 抽象方法（Abstract method）：不包含定義的方法
- 抽象類別（Abstract class）：包含至少一個虛擬方法的類別







