# 2018Q3 Homework 1
contributed by <`0xff07`>
---
## Stringification
C99 新增。可以將一個表示式轉化成一個字串。如：
```C
#define PRINT_EXPR(EXP) do{printf("%s\n", #EXP);}while(0)
int main()
{
PRINT_EXPR(return 0);
}
```
將輸出：
```shell
$ return 0
```
### 應用
#### `assert`
使用 `assert` 時，若 `assert` 內部的表示式不成立，會將該表示式顯示出來。
## Concatenation
使用 `##` 來表示。會把兩個表示式連接起來。跟巨集搭配使用可以有程式碼生成(code generation)的效果。
### 應用
### 程式碼生成
可以搭配巨集，簡化程式碼。藉此達成類似物件導向的功能。如：
```C
#define DECLARE_OBJECT(name) \
struct __##name##_node; \
typedef struct __##name##_node *name##_node; \
struct __##name##_node { \
name element; \
name##_node next; \
}; \
void append_##name(const name *X, name##_node *list); \
void delete_##name##_list(name##_node *list);
DECLARE_OBJECT(light)
DECLARE_OBJECT(rectangular)
DECLARE_OBJECT(sphere)
```
### Q：
為什麼不使用 `void*` 指標，如
```C
struct generic_node {
void *data;
struct generic_node *next;
};
```
並且把函式宣告成：
```C
void generic_append(void *data, struct generic_node **list)
```
並且在使用時都手動轉型呢？這樣也不用每有新的資料型態就需要手動增加一次 `DECLARE_OBJECT(some_new_type)`。或是有什麼維護上的考量嗎？
:::info
原本是想降低 dispatch 成本，避免用 polymorphism 手段，畢竟可重用的物件不多
:notes: jserv
:::
## _Genereric
C11 出現關鍵字。可以依照不同資料型態呼叫相應的函數。
## GNU/Linux Process Structure
複習 APUE 跟恐龍書
## 函式呼叫篇
### 「不純」的函數
跟數學上的函式比起來，C 語言的「函數」其中一個不一樣之處，是「有能力產生副作用」。如 I/O 類的函數除了回傳一個值，也會對進行輸入輸出。甚至可說 C 語言幾乎都是仰賴副作用進行的（如：回傳後將值儲存在變數中）。
### 沒有 First Class Function
參照[維基百科](https://en.wikipedia.org/wiki/First-class_function)中關於 First-class Function 的說明。簡略的說明：函數並不能像整數, 浮點數一樣任意地修改並回傳。這點使得 C 語言難做純的函數式程式設計。
有找到搭配 gcc 可以做到 [curry 的例子](https://zenhack.net/2013/09/04/first-class-functions-in-c-because-thats-totally-a-good-idea.html)。但嚴格來說 curried 後的結果並不是一個函數，而是將函數與變數暫存起來，並且強制在 call stack 插入記起來的變數。
查資料時發現 C 可以實作 [Y-Combinator](https://rosettacode.org/wiki/Category:C)。但目前還沒看懂這個程式。
## 遞迴呼叫篇
數學上即有遞迴的概念。 $\lambda-\text{calculus}$ 中所有合法的表示法 $\Lambda$ 為：
$$
\begin{cases}
\frac {x \in V}{x \in \Lambda} \newline\newline
\frac {M \in \Lambda \qquad N \in \Lambda}{(MN) \in \Lambda} \newline\newline
\frac {M \in \Lambda \qquad x \in V}{(\lambda x.M) \in \Lambda}
\end{cases}
$$
好處為「數學即程式」，只要數學上的遞迴定義寫出來，相應的程式也完成。
在函數式程式語言可以進行 program calculation 「推導」出新的演算法。另外，只要有是迭構地定義出來的資料結構，均可以有遞迴的構造。如 Haskell 的 `foldr` 。
函數式程式設計的其中一個重要精神是函數呼叫沒副作用。
遞迴有效能較慢的迷思，但編譯器最佳化有機會使兩者的編譯結果類似或相同。
### Q
費波那契遞迴解法的複雜度應該要是：
$$
O\left(\left(\frac {\sqrt{5} + 1}{2}\right)^n\right)
$$
而不是直播講義中的 $O(2^n)$ ？
:::info
太好了，請協助修正共筆，感謝
:notes: jserv
:::
有沒有可能把常用的費式數列值建好表存檔，需要使用時再 `mmap` 搬進程式中，以達成均攤 $O(1)$ 的時間呢？
### 指標的定義
> C99 [6.2.5] **Types**
>
> A pointer type may be derived from a function type, an object type, or an incomplete type, called the referenced type. A pointer type describes an object whose value provides a reference to an entity of the referenced type. A pointer type derived from the referenced type T is sometimes called ‘‘pointer to T’’. The construction of a pointer type from a referenced type is called ‘‘pointer type derivation’’.
「指標」指的是一個值能夠作為以下三種資料型態的參照之資料型態：
1. Function Type：即 function pointer, 指向一段可執行程式之起始點。
2. Object Type：即「任何佔據明確大小記憶體」的東西。如整數、
3. Incomplete Type：如僅有宣告，卻沒有定義的 `struct`
而相應地，那些「被參照」的資料形態，泛稱「referenced types」。
其中第 3. 可引申出「Forward Declaration」的開發技巧，如 oltk ：
```C
struct oltk; // 宣告 (incomplete type, void)
struct oltk_button;
typedef void oltk_button_cb_click(struct oltk_button *button, void *data);
typedef void oltk_button_cb_draw(struct oltk_button *button,
struct oltk_rectangle *rect, void *data);
struct oltk_button *oltk_button_add(struct oltk *oltk,
int x, int y,
int width, int height);
```
使用介面僅揭露於 `.h` 檔中，實作由 `.c` 決定。這樣做的另外一個好處是：若程式使用動態連結，則實作有修改時，僅需連結至新的實作，不用將整個程式重新編譯。如直播資料中的：
## Pointer vs. Array
下列 4 種的結果是相同的：
`x[4]`, `*(x + 4)`, `*(4 + x)`, `4[x]`
都是 `*(x + 4)`
若使用組合語言理解，不需感到意外。因為組合語言中 load 類的指令大多都是給定起始位址與 offset ，並將兩者相加計算出資料的位置。
## Linux 採用 LPD64
「指標有 8 個 byte」「整數有 4 個 byte」之類的講法，實際上是在指「[data model](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models)」。事實上不同的作業系統對數值的位元數目可以有不同規範，因此以上這些說法並不嚴謹。這些規範常用 I (Integer)、L(Long)、LL(Long Long)、P(Pointer) 等等英文後面附加數字說明。如 LP64 指 `long` 、 `long long` 、指標均為 64 位元。
Sign in with Wallet
Connect another wallet