Jserv's blog

以 C 語言實做 Functional Language 的 Currying

在電腦科學的領域，Functional Language 的 Currying (也譯作「Curry 化」) 的正規定義為：(出自 [Wikipeida])

「把接受多個參數的函數變換成接受一個單一參數(最初函數的第一個參數)的函數，並且返回接受餘下的參數而且返回結果的新函數的技術。

此技術的命名係紀念 Christopher Strachey 以邏輯學家 Haskell B. Curry (1900-1982，師法自數學家 David Hilbert，Haskell Funcational Language 也是以他命名)，由 Moses Schönfinkel 和 Gottlob Frege 兩位所提出。本文試著以 C 語言模擬出 Currying 的特性，語法層面較為接近 Lisp 與 Prolog，為避免與 C 語言程序性思維的 function (函式) 用語混淆，當談及 Functional programming 時，本文特別將 "function" 寫作「函數」。

在 functional programming 中，絕大部分都在操作函數，也就是「操作函數的函數」或是「產生函數的函數」一類的行為，而 Currying function 則在當其參數不足時，先行合成另一個函數去處理其他參數，直到參數量足夠時，再行計算結果。舉例來說：

let f x y = x - y

這裡定義函數 f 有兩個參數：x 與 y，回傳兩者的差值，再行合成新的函數 f' 如下：

let f' = f 3

這裡的函數 f' 為 (f 3) 的回傳值，只有單一參數，功能為 f'(x) = 3 - x。前者函數 f(x, y) 就是 uncurried function，接受兩個元素的 tuple，那麼，只接受一個參數的函數，也就是不需要 tuple，即函數 f'(x)，就稱為 curried function (Currying 對應的被動態描述)。具體來說，f(3, 2) = 3 - 2 = 1 表示將 (3, 2) 帶入 f(x, y)，而，函數 f' 的回傳值是個函數，先行「記住」了常數 3，而當再接受另一個參數 (如常數 2) 時，會將常數 3 取出與給定的參數作運算 (也就是 3 - 2)。所以整個過程可這麼思考：

[函數定義] f x y = x - y
f(x, y) = x - y
[函數定義] f' = f 3
f'(x) = 3 - x
f'(2) 的返回值 = f(3, 2)

看似平凡不過的推導，但在電腦科學的意義卻是非凡，因為這讓簡化的理論模型，如只接受單一參數的 lambda 得以處理多個參數的函數，當談及 Y Combinator 或者隱喻的遞迴操作，皆從此出發，進而開始璀璨的新頁，不過本文無意深入探索 Functional language，先行省略。

關鍵思維就是，上一個 Functor 處理參數的結果產生了下一個 Functor，下一個 Functor 繼續處理下一個參數，產生下一個 Functor，如此推廣下去。我們可進一步思考，Currying 的動作基本上就是讓一個函數得以 partially applied (術語為 partial application)，藉由新合成的函數作為回傳值，事實上，在 C++ STL (Standard Template Library) 與 C++ library [Loki] 中，即大量導入此思維，而在 Functional language 如 Lisp，給定的函數後可有一串參數，如 x, y, z, ...，我們可先行 partially apply 任意數量 (1 到 N 個) 的參數，獲得預期的功能，將功能本身予以抽象化處理。這樣的思維對真實環境下，應用程式的處理有什麼助益呢？舉例來說，檔案系統的操作，可能會有以下的行為：

• 計算所有檔案長度的總和
• 尋找目錄下最大或最小的檔案
• 尋找重複內容的檔案

我們可發現，這些操作在探訪目錄結構 (visit directory tree) 的同時，必須參照、累積或修改些中間的資料與資料表示法，倘若一味增加額外的變數，以利在探訪目錄時得以傳遞額外的資訊，雖能解決問題，但，如此一來，會使負責尋訪目錄結構樹的程式變得相當複雜，更難以一般性地使用。那麼，若導入 Currying function 的思維，可更優雅地處理，以下是 Ruby 語言的表示法，Ruby 的設計摻入了 functional programming 的元素在內，支援以函數形式的回傳方式，所以，我們可撰寫如下的通用性目錄樹尋訪：

def walk_dir(path_str, fun)
  path = Pathname.new(path_str)
  path.children.each do |entry|
    if entry.directory?
      fun = walk_dir(entry, fun)
    elsif entry.file?
      fun = fun.call(entry)
    end
  end
  return fun
end

如此一來，可封裝目錄操作，並一致化的處理，所以，若要實做取得目錄下所有檔案的空間，可這麼寫：

def cur_sum(sum)
 return lambda {|file| (file==nil) ? sum : cur_sum(sum + file.size)}
end

稍後再傳遞給尋訪的處理，如下：

puts walk_dir(ARGV[0], cur_sum(0)).call(nil)

同理，我們也可透過相近的手法，處理其他目錄層次的操作。不僅目錄尋訪可採用 Currying function 手法，對於資料庫也可，比方說知名的 Java ORM (Object-relational mapping) framework -- [hibernate] 裡頭的 Criteria Queries 就能應用 Currying 的形式如下：

SessionFactory.newSession(..).
    newQuery(…).
        setParameter(…).
            setParameter(…)

即具有 Curry, Factory Chain 的形式特性。C++ 語言層面並未有 functional programming 的成份，但可透過模擬的方式處理，前述的 C++ STL 與 Loki 就是箇中經典範例，為此，台灣知名的技術作家 [jjhou] 曾多次撰文著述探討極其複雜的實作，集結於「泛型程式設計與 STL」主題，不過本文採用另一種輕巧的方式，並採用簡潔的 C 語言來實做。

筆者模仿的對象是 Common Lisp 的語法，可參考其 cookbook 的 [Functions] 一節，筆者期望透過 C 語言模擬的 Currying 可如下操作：

typedef int (*intf)();

static int add(int x, int y) { return (x + y); }
static int sub(int x, int y) { return (x - y); }
 
int main()
{
        intf ret;

        ret = curry(add, 1);
        printf("* (funcall (curry #'+ 1) 1)\n"
               "%d\n", (*ret)(1));

        ret = curry(sub, 2);
        printf("* (funcall (curry #'- 2) 3)\n"
               "%d\n", (*ret)(3));
        return 0;
}

筆者定義 intf 這個描述整數型態的 function pointer (容筆者囉唆一下，這當然是指 C 語言的語意)，在 main() 中建立一個實體 ret，並試著賦予以下操作：

        ret = curry(add, 1);
        printf("* (funcall (curry #'+ 1) 1)\n"
               "%d\n", (*ret)(1));

這形式就符合前述「上一個 Functor 處理參數的結果產生了下一個 Functor，下一個 Functor 繼續處理下一個參數，產生下一個 Functor」，而且 curry() 的回傳值就是一個新的 function pointer，用以模擬「函數」的動作。那我們該如何實做這樣將 functional programming 與 C 語言橋接的 curry() function 呢？筆者的作法如下：

static char code[18] = {
        0x55,                   /* push   %ebp */
        0x89, 0xe5,             /* mov    %esp, %ebp */

        0xff, 0x75, 0x08,       /* pushl  0x8(%ebp) */
        0x6a, 0,                /* push   $0x0 */
        0xe8, 0, 0, 0, 0,       /* call <code+13> */
        0x83, 0xc4, 0x08,       /* add $0x8, %esp */

        0xc9,                   /* leave */
        0xc3                    /* ret */
};

int (*curry(intf Func, int arg))()
{
        *(char*)(code + 7) = (char) arg;
        *(int*)(code + 9) = (int) Func - ((int) code + 9 + 4);
        return ((intf) code);
}

顯然，這段程式碼僅能在 IA32 上執行，不過要移植到其他平台，應該是相對單純的動作 (RISC 架構的話，stack 處理可簡化)。我們要掌握 Currying function 的形式與語意，所以筆者先建立一段 shellcode 範本，也就是 char code[]，將 Currying 的函數參數在 curry() function 中預先植入，並將函式本身的進入點也寫入 caller。不過，真正的技巧在於 IA32 stack 的處理，兩年前筆者在 [深入淺出 Hello World] Part II 的演講中已有提及，這裡再作簡要複習。

如上圖，IA32 的 stack 是段連續的記憶體空間的陣列表示，透過 stack 可用以支援 C 語言型態的程序呼叫，而所謂的 C 語言 function call，在 IA32 上，就是透過 %ebp 與 %esp 這兩個暫存器的操作來實現，示意圖如下：

當有新的項目堆入 (push) 到 IA32 stack 時，%esp 暫存器的內含值將會遞減，並將新項目寫入於 stack 的頂端；反之，當 pop 操作時，%esp 暫存器的內含值會遞增，並屏除頂端的項目。在 IA32 的規範，%ebp 為 frame / base pointer，%esp 為 stack pointer，通用暫存器 %eax 則用以表示 function 的回傳值，詳細的運作模式，可參閱 [x86 Assembly Guide]。

在筆者的 shellcode 範本：

static char code[18] = {
        0x55,                   /* push   %ebp */
        0x89, 0xe5,             /* mov    %esp, %ebp */

        ...
        0xc9,                   /* leave */
        0xc3                    /* ret */
};

省略的部份是 Currying function 的 function body 呼叫動作，而前半段稱為 prologue，後半段則是 epilogue。將 C 語言的程序呼叫對應到 IA32 stack 時，prologue 顧名思義，就是「序幕」的意思，即程序 / function 的開頭，有兩個動作需優先於其他動作前完成：

• 保存 caller (呼叫者 function) 的 frame pointer，存放到 IA32 stack，其組合語言就是 "push %ebp"
• 將目前的 stack pointer 設定為 callee (被呼叫的 function) 的 frame pointer，對應的組合語言就是 "movl %esp, %ebp"

另一方面，epilogue 顧名思義，就是「尾聲」的意思，即程序 / function 的結尾，考量到 C 語言函式呼叫的情境，必須在回傳前，針對 callee 的 stack frame 作處理。通常得進行以下三個動作：

• 將目前的 frame pointer (也就是 callee 的) 設定為 caller 的 stack pointer，對應的組合語言是 "movl %ebp, %esp"
• 自之前存放於 IA32 stack 的值取出，回復 caller 的 stack frame，對應的組合語言是 "popl %ebp"，不過，在 80286 以後 (含)，這兩個指令可被單一指令取代："leave"
• 當準備妥當後，"ret" 指令就可被執行，以返回 caller。注意，當 "leave" 指令被執行後，stack pointer 會指向 caller function 中透過 "call" 指令所推入 IA32 stack 的返回位址，因此，"ret" 指令實際上是自 IA32 stack 作 pop 出返回位址並跳躍到該位址執行，也就是 "pop eip" 的動作。

所以，筆者張羅了包含完整 C 語言 function 的 shellcode，並在 curry() function 中作 function pointer / parameter 給定內含值的動作，就是為了「合成函數」形式的模擬。完整的程式碼可參閱 [curry.c]，執行結果如下：

$ gcc -xc curry.c && ./a.out
* (funcall (curry #'+ 1) 1)
2
* (funcall (curry #'- 2) 3)
-1

當然，這只是一個出發點，實務上可推廣到目錄檔案操作一類的應用。
由 jserv 發表於 June 19, 2008 02:55 AM