# 2018q3 Homework1
contributed by <`letticee`>
>固定格式，請注意
>[name=課程助教][color=red]
## 為什麼要深入學習 C 語言？
## 開發工具和規格標準
* c 語言可以自己編譯自己，gnu 的 gcc 是用 c 寫的（一些 c++）
* c 跟 c++ 在發展的路上越差越多
e.g. c99 有的 designated initializer，c++沒有、是留給constructor去做
* 可對指標做+ - bitwose operator，不可* /
* ~~雙重指標~~ **指標的指標** pointer to pointer
---
## 指標篇
### typedef
- 範例
- 建立 PFI 作為一個指向「一個擁有兩個 char * 當作參數並回傳 int 的函式」的指標的別名
```c
typedef int (*PFI)(char *, char *);
```
- 未使用typedef
```c
int do_math(float arg1, int arg2) { return arg2; }
int call_a_func(int (*call_this)(float, int)) {
int output = call_this(5.5, 7);
return output;
}
int final_result = call_a_func(&do_math);
```
- 改寫：
```c
typedef int (*MathFunc)(float, int);
int do_math(float arg1, int arg2) { return arg2; }
int call_a_func(MathFunc call_this) {
int output = call_this(5.5, 7);
return output;
}
int final_result = call_a_func(&do_math);
```
[Wikipedia: typedef](https://zh.wikipedia.org/wiki/Typedef)
:::info
除了閱讀 Wikipedia，請務必詳閱 C99/C11 規格書描述
:notes: jserv
:::
- 呼叫地址為 0 的函式（？
```c
int main() {
typedef void (*funcptr)();
(* (funcptr) (void *) 0)();
}
```
- 0 這個地址在使用者層級不能隨意呼叫，所以會發生 segmentation fault 記憶體存取的錯誤
:::info
這限制來自 [MMU](https://en.wikipedia.org/wiki/Memory_management_unit)，請思考在 GNU/Linux 上對應的處理機制為何
:notes: jserv
:::
* 回傳 function pointer 的 function
```c
void ( *signal(int sig, void (*handler)(int)) ) (int);
```
(https://stackoverflow.com/questions/15739500/how-to-read-this-prototype)
* Q：signal 的用途？
* C99 [7.14.1.1] The signal function
* The signal function chooses one of three ways in which receipt of the signal number sig is to be subsequently handled.
### 一些名詞
- C99 [3.14] object
- region of data storage in the execution environment, the contents of which can represent values
- 有明確的大小 (cf. incomplete type)
- 資料：連續的記憶體
- undefined behavior
- e.g. i++++++ 丟到 compiler => ? 怎樣是對怎樣是錯
:::info
可參照 [未定義行為篇](https://hackmd.io/s/Skr9vGiQm)
:notes: jserv
:::
- C99 [6.2.5] imcomplete type
- An array type of unknown size is an incomplete type.
### pointer type
- 可能衍生自 function / object / incomplete type -- 稱作 referenced type - C99 [6.2.5]
- The construction of a pointer type from a referenced type is called ‘‘pointer type derivation’’. - C99 [6.2.5]
### 問題
:::warning
:question:
> 這是 C 語言只有 call-by-value 的實證，函式的傳遞都涉及到數值 why??
:::
### 指標的指標
```C=1
int B = 2;
void func(int *p) { p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
```
1
```
沒改到 A 的值，因為傳給 func 的參數是副本，lifetime 只在函式裡({ p = &B; })，ptrA 內含值其實是沒更動到的
```clike=1
int B = 2;
void func(int **p) { *p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(&ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
```
2
```
代入的 p 的 lifetime 是整個 main block
### Pointers vs. Arrays
- x[4], *(x + 4), *(4 + x), 4[x] 都是指到同一個位址
- C 沒有真正的陣列/矩陣
- C 提供操作多維陣列的機制，但實際上在記憶體的呈現只有一維
> [未完]
---
## 函式呼叫篇
- nested function in C：可以在一個 function 的定義裡宣告另一個function，但他的定義要定義在其他的 function 外面
- C 的 function call 一般狀況是有去有回（特殊情況才會有去無回）
- argument 參數 vs. parameter 參數
argument：型態
parameter：數值本身
- function return 的 value 放在暫存器，如果是 struct 就可能很大 => 在暫存器放 structure 的開頭位址
### malloc / free
- malloc() 要指定 size，會回傳指標。往往配置的空間會比預期的再大一點，因為會做 alignment
- free() 不用指定 size。若該指標是 null 則 free 不會動作。
- free完某 pointer 後做 pointer = NULL 可以避免 doubly free
- doubly free：compile 會過，但執行會出錯
- malloc_trim()：強制去 free
- free() 為效率考量可能不會馬上 free，但會導致系統可用空間變少
### 問題
:::warning
:question:
> [color=#b2050e]1. 為什麼 glibc 可以偵測出上述程式的 “double free or corruption” 呢？
>
> ~~因為執行完 free() 後，ptr的值會改變，已經不是當初 malloc() 分配記憶體時 ptr 指到的記憶體的開頭？~~
>
> 2.
> :::warning
> ```shell
> $ gcc -o infinite infinite.c -g
> $ gdb -q infinite
> Reading symbols from infinite...Reading symbols from /Users/waiting/infinite.dSYM/Contents/Resources/DWARF/infinite...done.
> done.
> (gdb) r
> Starting program: /Users/waiting/infinite
> [New Thread 0x1803 of process 569]
> During startup program terminated with signal ?, Unknown signal.
> (gdb) list
> 1 int func() {
> 2 static int count = 0;
> 3 return ++count && func();
> 4 }
> 5
> 6 int main() {
> 7 return func();
> 8 }
> (gdb) p count
> No symbol "count" in current context.
> ```
> :::
> macOS 的訊息長得不太一樣oAO
> Ubuntu 上 ok
:::info
參照 [Diagnosing Memory Heap Corruption in glibc with MALLOC_CHECK_](https://www.novell.com/support/kb/doc.php?id=3113982) 設定好環境變數，再做實驗
:notes: jserv
:::
---
## 遞迴呼叫篇
### iterate vs. recurse
### recursion 的類型
- tail recursion：
- 直接遞迴 (direct recursion)
- 線性遞迴 (linear recursion)
- 函式執行的最後一件事只能是遞迴呼叫
### [tail recursion 之重要性](https://notfalse.net/9/recursion#recursive-int-array-sum)
- 遞迴的每次呼叫需要額外的記憶體 (系統堆疊 stack frame)，來記錄每個遞迴的呼叫狀態，若遞迴呼叫過量使堆疊爆了，就會造成 Stack Overflow Error
- 尾端呼叫消除 (Tail Call Elimination, TCE) / 尾端呼叫最佳化 (Tail Call Optimization, TCO)
- 尾端遞迴，不增加新的系統堆疊，而是用每次執行的結果，直接更新函式內容
- 許多語言編譯器不支援尾端呼叫最佳化 (e.g. Java、Python)
- 尾端遞迴其實只是把迭代的迴圈變化和區域變數，放在方法的參數中傳遞罷了
- 一個函式，理論上必定存在兩種形式解法: 遞迴與非遞迴。
- 而尾端遞迴則能無痛轉換為非遞迴
- clang / gcc 都有能力對 tail recursion 的程式做最佳化，中間的那些遞迴的呼叫事實上就不存在了
---
## 前置處理器應用篇
---
## linked list 和非連續記憶體操作
---
Sign in with Wallet
Connect another wallet