# 2018q1 第 9 週測驗題
###### tags:`mrwenwei`,`shaimejump520`
contributed by <`mrwenwei`>, <`shaimejump520`>
* [第九週測驗題](https://hackmd.io/FJ1WAslLSIahP7diUKhG1A?view)
### 第1題
原程式碼：
```clike=
#include <math.h>
#include <stdio.h>
double powDoubleFloat(double base, float power) {
return pow(base, power);
}
int main() {
double (*powFloatDouble)(float, double) =
(double (*)(float, double)) & *** & powDoubleFloat;
printf("(0.99)^100: %lf \n", powDoubleFloat(0.99, 100));
printf("(100)^0.99: %lf \n", powFloatDouble(100, 0.99));
printf("(0.99)^100: %lf \n", powFloatDouble(0.99, 100));
return 0;
}
```
:::success
延伸問題:
1. 依據 IEEE 754 規範，解釋為何輸出如此;
2. 程式碼第 7 和第 8 行的 `& *** &` 做了什麼事？請參閱 C99/C11 規範並解釋;
3. 參考 [Fast Exponentiation Algorithms](http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/fastexp.pdf)，實作 [Fixed-point arithmetic](https://en.wikipedia.org/wiki/Fixed-point_arithmetic) 版本的 `pow` 函式並驗證;
:::
* 用 GDB 進行分析( test.c 內包含上述程式碼 )
```
gcc test.c -o test -lm -g
gdb -tui test
```
注意！若要使用 GDB ，在編譯時要加入 `-g` 參數。
GDB 時加入 `-tui` 參數，可以在 debug 時顯示 source code
:::info
可嘗試使用 [cgdb](https://cgdb.github.io/)，有更好的顯示
:notes: jserv
:::
將 breakpoint 設在第3行，可以方便觀察 function parameter 的傳入值：
```
powDoubleFloat (base=5.5355285709140466e-315, power=5.84860315e+35)
```
發現在第 11 行的 function call，其參數的傳入值，已與我們預想的 base = 100.0, power = 0.99 有很大的出入
base $= 5.5355285709140466\ \times10^{-315}$ 為非常小的數字，趨近於 ０ 所以再取 ０ 的 power（$5.84860315\times10^{35}$）次，也會是 ０
#### 那為何參數的傳入值會與我們預想的差這麼多呢？
* 先回想，function 的呼叫，首先會將 return address 置入 stack 中，再**將 parameter 依序也放入 stack 中**，真正進入到 function 的執行片斷時，會先**再反序將參數從 stack 中取出**，問題便出在這裡了！
:::warning
這說法不精確！請用 [System V Application Binary InterfaceAMD64 Architecture Processor Supplement](https://software.intel.com/sites/default/files/article/402129/mpx-linux64-abi.pdf) 來解釋，網路上有很多討論仍以「直覺」猜測，卻不是參照第一手材料和搭配實驗來分析。
:notes: jserv
:::
* `powFloatDouble(100, 0.99)`，我們先將 值為 100 的 float(**32-bits**) 與值為 0.99 的 double(**64-bits**) 放入 stack 中，而後先取出一個 float(**32-bits**) 再取出一個 double(**64-bits**)，按照 stack 的性質，我們已經取出了與我們設想不同的數值進行運算了
* 用敘述的太沒有畫面，來讓 GDB 講給我們聽吧：
> 結果詳閱了上方老師給的文件後，根據內述的函式參數傳遞方式實際用 GDB 操作後，發現與設想的不太相同，目前尚未找到原因來解釋，將繼續實驗嘗試 [name=shaimejump520]
#### `& *** &` 之謎：
* C99 [6.5.3.2] **Address and indirection operators**
* &*E is equivalent to E (even if E is a null pointer), and &(E1[E2]) to ((E1)+(E2)).
* It is always true that if E is a function designator or an lvalue that is a valid operand of the unary & operator, *&E is a function designator or an lvalue equal to E. If *P is an lvalue and T is the name of an object pointer type, *(T)P is an lvalue that has a type compatible with that to which T points.
* 經由上述，我們可以將程式中第 8 行中的 `& *** &` 視為 `*`，綜合來說， 7 8 行的宣告為：宣告一個 pointer of function `powFloatDouble` 其 return type 為 double 而參數為 float 及 double ，而該指標指向一個已被隱含轉型的 function `powDoubleFloat`
* 其實規格書中提到的最耐人尋味的，也就是上面第一句 `&*E is equivalent to E (even if E is a null pointer)`，講到即使 E 是 null pointer，亦符合等價的規則！
* 我們知道，若是我們對 null pointer 取值會產生錯誤，然而若是對 null pointer 取值再取地址，卻能夠正確的回傳
* 對此我們做了個小實驗：
```clike=
#include <stdio.h>
int main(){
int *ptr = 0;
printf("%p", &*ptr); //(nil)
fflush(stdout);
int a = *ptr; //segmentation fault
printf("%p", &a);
return 0;
}
```
* 對此的解釋為，compiler 在編譯時會自己將 `&*ptr` 等價 `ptr` ，並不會實際執行先取值再對值取地址的動作，所以在第 3 行的地放可以正確執行，而在第 10 行就真正執行的對 null pointer 取值的動作，所以導致程式執行出錯。
如此的設計也是符合常理，程式執行時不至於虛耗在那些並無意義的取值取址中。
---
### 測驗 `2`
考慮到以下採用 [Functional Programming](https://en.wikipedia.org/wiki/Functional_programming) 風格開發的 singly-linked list 程式:
```Clike
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
/* integer linked list type */
typedef struct __int_list const *const int_list_t;
static int_list_t const Nil = NULL; /* empty list */
/* singly linked list element */
typedef struct __int_list {
int_list_t next;
int32_t const val;
} node_t;
/* A pointer to where we are about to store the result of computation */
typedef void *const CPS_Result;
/* prototypes for the continuations */
typedef void (*MakeListCallback)(int_list_t list, CPS_Result res);
void make_list(uint32_t const arr_size,
int32_t const array[],
int_list_t lst,
MakeListCallback const cb,
CPS_Result res);
typedef void (*ReversedListCallback)(int_list_t rlist, CPS_Result res);
void reverse(int_list_t list,
int_list_t rlist,
ReversedListCallback const cb,
CPS_Result res);
typedef void (*VoidMappable)(int32_t const val);
void void_map_array(VoidMappable const cb,
uint32_t const size,
int32_t const *const arr);
void list2array(int_list_t list, CPS_Result res);
/* reverse a list and then store it in an array */
void reverse_toarray(int_list_t list, CPS_Result res) {
reverse(list, Nil, list2array, res);
}
static void print_val(int32_t const val) { printf("%d ", val); }
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
int main(int argc, char *argv[]) {
int32_t arr[] = {99, 95, 90, 85, 80, 20, 75, 15, 10, 5};
uint32_t const arr_size = ARRAY_SIZE(arr);
int32_t res[arr_size];
/* call make_list and pass reverse_toarray as the "continuation" */
make_list(arr_size, arr, Nil, reverse_toarray, res);
/* print out the reversed array */
void_map_array(print_val, arr_size, res);
printf("\n");
return 0;
}
/* construct a linked list from an array */
void make_list(uint32_t const arr_size,
int32_t const arr[],
int_list_t lst,
MakeListCallback const cb,
CPS_Result res) {
if (!arr_size) {
cb(lst, res);
return;
}
make_list(arr_size - 1, arr,
&(node_t){.val = arr[arr_size - 1], .next = lst}, cb, res);
}
/* transform a linked list into an array */
void list2array(int_list_t list, CPS_Result res) {
if (Nil == list)
return;
int32_t *array = res;
array[0] = list->val;
list2array(list->next, array + 1);
}
void reverse(int_list_t list,
int_list_t rlist, /* reversed list */
ReversedListCallback const cb,
CPS_Result res) {
if (Nil == list) {
cb(rlist, res);
return;
}
reverse(list->next, &(node_t) K1, cb, res);
}
/* iterate over an array and performs action cb on each element */
void void_map_array(VoidMappable const cb,
uint32_t const size,
int32_t const *const arr) {
if (!size)
return;
cb(arr[0]);
void_map_array(cb, K2, K3);
}
```
程式輸出為 `5 10 15 75 20 80 85 90 95 99`，也就是將輸入的數值順序予以反轉，過程中不需要 malloc/free，請補完上述程式碼。
K1 = ?
* `(a)` {.val = list->val, .next = list}
* `(b)` {.val = list->val, .next = rlist}
* `(c)` {.val = rlist->val, .next = list}
* `(d)` {.val = rlist->val, .next = rlist}
K2 = ?
* `(a)` size - 1
* `(b)` size
* `(c)` size + 1
K3 = ?
* `(a)` arr - 1
* `(b)` arr
* `(c)` arr + 1
:::success
延伸題目:
1. 解釋上述程式碼的運作，並且透過修改和實驗，理解 functional programming (FP) 風格;
2. 比照 FP，改寫上述程式碼，實作出 quick sort，同樣不得配置 heap memory (也就是不得用 malloc/free);
3. 測試這樣的 integer list 和 non-intrusive linked list 的效能差異;
:::
#### 1. 解釋上述程式碼的運作，並且透過修改和實驗，理解 functional programming (FP) 風格
首先必須先瞭解一下程式運作的邏輯，先看一下 reverse() 這個 function。他會將傳進去的 singly linked list 反轉後將結果轉成 array 存在 main() 中先宣告好的 res 中。而他的過程是透過巧妙的遞迴實作完成，下面以圖示說明：
* 第一次呼叫時將原始的 list 傳進去，紅色部分為指標處。
### list:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 99 | <ref> }", width=1.2, color=red]
b [label="{ <data> 95 | <ref> }"];
c [label="{ <data> 90 | <ref> }"];
d [label="..." shape=box];
e [label="{ <data> 5 | <ref> }",width=1.2];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->e
}
```
* 進入遞迴第一次時將 list->next 放在第一個參數傳了進去，而比較特別的地方是的第二個參數的部分直接將一個 node_t 型態的 linked list 初始化為 val = 目前紅色指標處的 value，next = NULL (rlist 一開始為 NULL)，也就是下一層遞迴裡的 rlist。
### list:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 95 | <ref> }", width=1.2, color=red]
b [label="{ <data> 90 | <ref> }"];
c [label="{ <data> 85 | <ref> }"];
d [label="..." shape=box];
e [label="{ <data> 5 | <ref> }",width=1.2];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->e
}
```
### rlist:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 99 | <ref> }", width=1.2, color=red]
b [label="{ NULL }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
}
```
* 進第二層遞迴時又將 list->next 傳了進去，第二項參數的 rlist 的 val 初始化為 list->val ，也就是 95，next 再接回去原來傳進來的 rlist，就會變成下圖：
### list:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 90 | <ref> }", width=1.2, color=red]
b [label="{ <data> 85 | <ref> }"];
c [label="{ <data> 80 | <ref> }"];
d [label="..." shape=box];
e [label="{ <data> 5 | <ref> }",width=1.2];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->e
}
```
### rlist:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 95 | <ref> }", width=1.2, color=red]
b [label="{ <data> 99 | <ref> }"];
c [label="{ NULL }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
}
```
* 一直到最後 rlist 就會是 list 的反轉了：
### rlist:
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 5 | <ref> }", width=1.2, color=red]
b [label="{ <data> 10 | <ref> }"];
c [label="..." shape=box];
d [label="{ <data> 99 | <ref> }"];
e [label="{ NULL }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
c:ref:c -> d:data [arrowsize=1.2];
d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
}
```
* 終止條件成立時會呼叫一開始傳進去的 list2array() 並將 rlist 轉成 array 存在 res 中，完成 function。
* 故第一題的 K1 就是 ‘{.val = list->val, .next = rlist}’ ， 而 void_map_array 是將 array 內的 data 印出來，K2 為遞迴終止條件的變數，故應為 size-1，K3 等同於 arr[i++] 的功能，因此為 arr+1。
* 一開始在看這份 code 時覺得很不習慣，所有的事情都從遞迴以及傳遞參數之間完成，每個功能都拆開來撰寫，上網搜尋了一下 [Functional Programming](https://en.wikipedia.org/wiki/Functional_programming) 各類相關資料，發現大致上有幾個特點：
* 一個運算用的 function 大多只包含條件式以及遞迴呼叫。
* [higher-order functions](https://en.wikipedia.org/wiki/Higher-order_function) 主要有兩個特點：
* function 可當作參數傳入 function 之中。
* function 可以 return function.
* [lazy evaluation](https://en.wikipedia.org/wiki/Lazy_evaluation) ：當變數被定義時不會立即 evaluate，而是等待要使用時才 evaluate 並儲存已計算的結果，所以不會重複 evaluate 同一個定義。
* 不支援 flow Controls，像是迴圈以及 If-Else 條件判斷式，只使用 function 及 function 呼叫。
[Side Effect](https://en.wikipedia.org/wiki/Side_effect_(computer_science))
:::warning
關於 FP，可對照看之前報告 [MapReduce with POSIX Thread](https://hackmd.io/s/Hkb-lXkyg)，注意裡頭引用的論文
:notes: jserv
:::
#### 2. 比照 FP，改寫上述程式碼，實作出 quick sort，同樣不得配置 heap memory (也就是不得用 malloc/free)
回憶一下 [quicksort](http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php) 演算法的流程：
* 選定數列中的一個值當作 pivot ，而選擇的方法可以是隨機選，也可以是挑出陣列的第一項，當然也可以使用 [median of medians](https://en.wikipedia.org/wiki/Median_of_medians) 確保每次選的 pivot 都是接近中位數的數，以降低 quicksort 遞迴次數。
* 從數列的頭到尾對每個數比較，若大於 pivot 則將其置於右方，剩下的則置於 pivot 左方。
* 對左右兩邊的數列分別都再做上述步驟(也就是遞迴)，一直到數列個數為 0 或 1 時結束遞迴。
開始實作演算法的部份，由於 functional progamming 的程式碼有一個很大的特色是：當一個變數建立出來後就不可以在更動他的值，在 C語言中也就是 const 型態的變數，這樣的限制也讓程式碼寫起來相當的不習慣。
我們先嘗試寫了一個 partition 的function:
```clike=
__list_strct partition( int_list_t cur,
int_list_t llist,
int_list_t pivot,
int_list_t rlist) {
if(Nil == cur) {
__list_strct r = {.left = llist, .right = rlist};
return r;
}
/* Put the numbers which are larger than pivot into right. */
if(cur->val > pivot->val) {
return partition(cur->next, llist, pivot,
&(node_t){.val = cur->val, .next = rlist});
}
return partition(cur->next, &(node_t){.val = cur->val, .next = llist}, pivot, rlist);
}
```
回傳值的型態是一個包含兩個 list 指標的 struct，目的是要呼叫 partition 這個 function 後可以拿到兩個分完堆的 list。
```clike=
typedef struct list_strct {
int_list_t left;
int_list_t right;
} __list_strct;
```
然而這樣的作法出現了問題，儘管我們在 partition() 內測試了 function 內容都確定沒寫錯，但當 function return 後做下一步的執行就會出現難以預料的結果或是 segmentation fault，連多一個 printf 都會讓結果截然不同，這樣的結果讓我們困惑，因此我們決定使用睡眠 debug 法則，就這樣睡掉了幾天之後才發現我們犯了一個錯誤。
先觀察一下這行程式碼：
```clike=
/* integer linked list type */
typedef struct __int_list const *const int_list_t;
```
他的意思是定義了一個 int_list_t 的宣告方式，他可以宣告一個本身是 const 的指標並且指向一個 const 的變數。
也就是說如果我們將他當作一個 function 的宣告，則這個 function 就可以被視為是一個 const 的變數，也就是回傳的結果必須固定不變，然而如果每次迴傳都式不同的變數時就會發生錯誤。這裡也讓我們想起 functional programming 的初衷，因此繼續修改程式碼。
Sign in with Wallet
Connect another wallet