---
# System prepended metadata

title: 程式語言期末考範圍
tags: [' 大三筆記', 程式語言]

---

---
tags: 程式語言, 大三筆記
---

# 程式語言期末考範圍

## Problem of Pointer

### Dangling pointers (Dangerous!! 💀💀💀🗣️🗣️🔥🔥☢️⚠️❌)
* 指標指向已被釋放的記憶體
* 例如：
    ```cpp=
    int* ptr1 = new int[100];
    int* ptr2 = ptr1;
    delete [] ptr1;
    // ptr2 is dangling

    *ptr2 // 💀💀💀
    ```

### Lost heap-dynamic variable (Waste!! 💀💀💀🗣️🗣️🔥🔥🚮🚯❌)
* 沒有指標指向被分配的記憶體，通常稱為 memory leaks, garbage
* 例如：
```cpp=
int* ptr1 = new int[10];
ptr1 = new int[20];
// int[10] is wasted 💀💀💀🚯🚯🚯
```

### Solution to dangling
* **Tombstone**
    * 指標不指向 heap 而是指向 Tombstone 結構，由該結構保管物件實際位址
    * 當物件被釋放後，Tombstone 結構仍然會存在，但實際位址設定為 nil
    * 即可避免存取到空指標
    * 浪費空間時間
* **Locks-and-keys**
    * 指標內存著 `(目標位址, key)`
    * 在 heap 內存著 `(variable, lock)`
    * 當記憶體被分配時：
        * 生成一個 **lock value**
        * 將其放入指標中的 **key** 及 heap 中的 **lock**
    * 當記憶體被釋放時：
        * 將 heap 的 **lock** 變成 **非法狀態** (通常為 0)
    * 當存取記憶體的時候：
        * 比較 **key** 和 **lock**
        * 相同代表存取合法，不同則不合法
    * 浪費空間時間

### Solution to memory leaks
* **Reference Counter**
    * 在每個分配的記憶體中增加一個 **counter**，代表有多少指標指向他
    * 當 **counter** 歸零時釋放該記憶體
    * 浪費空間時間
    * 當有閉環的時候會衝突
    ```cpp
    // 循環引用範例
    struct Node {
        Node *ptr;
    } a, b;
    
    a->ptr = b;
    b->ptr = a;
    ```

* **Garbage Collection**
    * 每個 heap 區塊都有額外的 bit 用以標記，初始為 true (is garbage)
    * 當運行時，指標開始指向 heap 區塊，被指向的區塊標記為 false (is not garbage)
    * 將所有標記為 true 的區塊彙整起來，就是可以使用的區塊
    * 可以解決循環引用的問題
    * GC 有時候會在你不想它發生的時間觸發（比如你在跑一個很吃效能的遊戲），而 GC 一啟動，整個程式會停下來做清理 → 出現延遲（lag）或卡頓
    * 「最需要時最失常，關鍵時刻不擔當。」

## Guarded Command

由 Dijkstra 提出，目標是支持一種新的程式設計方法論，使得在開發過程中能夠進行程式正確性的驗證

* 是並行程式語言機制的基礎（如 Ada）
* 基本概念：如果運算的評估順序並不重要，那麼程式就不應該指定一個固定的順序

::: warning
⚠️ 除了 Ada 之外，**沒有** 其他程式語言有類似的語法
:::

### Selection

以下使用 Dijkstra 當初提出的 Guarded Command Language (GCL) 來表示 psuedocode

```=
if <Boolean exp> -> <statement>
[] <Boolean exp> -> <statement>
 ...
[] <Boolean exp> -> <statement>
fi
```

* 執行到這東東時，計算所有的布林表達式
* 當有一個或多個表達式為真，隨機選一個 **( \<Boolean exp\> 為真，其後面的 \<statement\> 執行)** 
* 沒有敘述為真時，為 Runtime Error

~~考試括號內的東西不用抄~~
    
例如:

```=
if true -> statement1
[] false -> statement2
[] true -> statement3
fi
```

會從 `statement1` 和 `statement3` 之中選一個出來執行

<img src='https://hackmd.io/_uploads/SJKA4evGxe.png' height='500'>

### Loop

```=
do <Boolean exp> -> <statement>
[] <Boolean exp> -> <statement>
 ...
[] <Boolean exp> -> <statement>
od
```
    
* 執行到這東東時，計算所有的布林表達式
* 當有一個或多個表達式為真，隨機選一個表達式 (為真後面的statement執行後)，繼續迴圈
* 沒有敘述為真時，離開迴圈

<img src='https://hackmd.io/_uploads/HyezHlDMex.png' height='500'>


## C# Get Set

```csharp=
public class Date { // 定義一個 public class 名為 Date
    private int month = 10; // 設定 Date 內變數 month 初始值為 10
    public int Month // 設定 getset functions
    {
        get { return month; } // get::直接回傳 month 的值
        set { if ((value > 0) && (value < 13)) month = value; }
        // set::如果目標值介於 [1, 12] 內，將 month 設定為該值
    }
}

Date d = new Date(); // 宣告一個 Date 物件 d 並分配新的物件記憶體
d.Month = 2; // 設 d 的 month 為 2
Console.WriteLine(d.Month); // 輸出 d 的 month 值，輸出結果為 2                                        
```

### 與一般的 function 有什麼不同
寫入 Month 的時候，值是經由 set function
讀入 Month 的時候，值是經由 get function

C++ 沒有這個語法

## Runtime Stack
畫出以下程式的 runtime stack
```cpp=
void A(int);
void B(int);
void C(int);

void A(int x) {
    int y;
    C(x);
}

void B(int r) {
    int s, t;
    A(t);
}

void C(int q) { }

int main() {
    int p;
    B(p);
}
```
![image](https://hackmd.io/_uploads/H1NG-rwGgl.png)

### Activation record (AR)
一個 subprogram 包含一個 AR，內部有以下資訊：
* 區域變數 (Local)
* 參數 (Parameter)
* 控制連結 (Dynamic link)
    * 指向 caller 的 AR 最上層
    * 可表示實際執行時的呼叫路徑
    * 用於在副程式結束執行後交還控制權、並釋放記憶體
    > 誰叫我，我就回哪兒
* 靜態連結 (Static link)
    * 用來讓巢狀函數（nested functions）能夠存取其靜態外層函數中的變數。
    * 指向原始碼中包住自己的函數
    * 利用 pascal 做範例：
        ```pascal=
        procedure A;
          var x: integer;
          procedure B;
            procedure C;
            begin
              x := 10;
            end;
          begin
            C;
          end;
        begin
          B;
        end;

        // 當 C 在執行時要找 x：
        // C 找不到
        // 往 static link 到 B → 也沒有
        // 再往 static link 到 A → 找到 x
        ```
    * Standard C 沒有 lambda 功能，因此根本沒有 static link，~~所以我不知道老師的考古在 static link 三小~~
    * 但 C++ 有，只要有類似這種巢狀函數功能的語言都會使用到 static link
* 回傳位址 (Return address)


### Dynamic Chains

* Dynamic Chains 是由 stack 中所有 activation record 的 dynamic link 連結起來的集合。
* 它代表目前程式執行時的呼叫歷史，也叫做呼叫鏈（call chain），顯示了「誰呼叫誰」的順序。

### Local Offset

* local offset 是本地變數或參數在 activation record 中相對於該記錄起始位置的位移量。
* 編譯器在編譯時期決定這個偏移量，使得執行時能快速且正確地存取變數。

## Data Abstraction

資料抽象化的優點:
* Modifiability：提供無副作用的區域修改
* Reliability：增加程式的可靠性，不會有被更動而產生的重大危害
* Separate compilable：可以分開來編譯

## OOP 繼承
### Inheritance
* 優點：Reuse
* 範例：
```cpp=
class A {};
class B: A {};
```

### Polymorphism
* 優點：開發與維護時更容易擴展
* 範例：
```cpp=
class A { virtual void f(); };
class B: A { virtual void f(); };

B b;
A &a = b;
a.f();

A* ptr = &b;
ptr->f();
```

## Nested Classes

常見錯誤 :

```cpp
class A {
    B b1; // 錯誤: Compiler 還沒讀到 Class B 的定義
    class B {
        // …
    };
    B b2;
};

class C {
    class D {
        C a ; // 錯誤: Compiler 還沒讀完 Class C 的完整定義，無法建立實體
        C *p; // 合法
    };
    B b;   // 錯誤: Class B 的使用範圍只能在 Class A 裡面
    B *bp; // 錯誤: Class B 的使用範圍只能在 Class A 裡面
};
```

## C++ Class Var & Func
* Class variable：`static int i;` for each class
* Instance variable：`int i;` for each object
* Class method：`static void f();` for each class
* Instance method：`void f();` for each object

## C++ OOP Access Control
* private (class 內部和 friend class 可見)
* protected (private + 子類別可見)
* public (protected + 外部可見)

## OOP Binding
### Static
* 在 comile time 時做 Binding
* 速度最快
* 難以 extend 
* 用於：
    * C++ default binding
    * Java private function (不支持 overriding)
###  Dynamic
* 在 runtime 時做 Binding
* 開發與維護時更容易擴展
* 速度慢
* 用於：
    * Polymorphism
    * Java default binding (final function 不是)
    * C# default binding
    * Ada classwide types

## C++ Template
```cpp=
template <class type, int size>
class stack {
    type *stackPtr;
    stack () {
        stk_ptr = new int [size];
        max_len = size - 1;
        top = -1;
    }
};
```

## Java Threading
```java=
class MyThread extends Thread // MyThread 繼承 Thread
    public void run () // thread 啟動時跑的第一個 function
    {
        // ...
    }
}

Thread myTh = new MyThread(); // new MyThread 的 object myTh
myTh.start(); // 開始啟動 thread myTh
myTh.join(); // 等待 myTh 跑完
```
