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

# 程式語言期末考範圍

## Problem of Pointer

### Dangling pointers (Dangerous!! 💀💀💀🗣️🗣️🔥🔥☢️⚠️❌)
* 指標指向已被釋放的記憶體
* 例如：

    int* ptr1 = new int[100];
    int* ptr2 = ptr1;
    delete [] ptr1;
    // ptr2 is dangling

    *ptr2 // 💀💀💀

### Lost heap-dynamic variable (Waste!! 💀💀💀🗣️🗣️🔥🔥🚮🚯❌)
* 沒有指標指向被分配的記憶體，通常稱為 memory leaks, garbage
* 例如：

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** 歸零時釋放該記憶體
* 浪費空間時間
* 當有閉環的時候會衝突

    // 循環引用範例
    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

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

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);
}


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

class A {};
class B: A {};

### Polymorphism
* 優點：開發與維護時更容易擴展
* 範例：

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

常見錯誤 :

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

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

## Java Threading

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 跑完