把函數當做資料來用 (Callback functions)

為什麼要把函數當做資料來用? 以內建的排序函數為例

在任何稍大的程式當中, 幾乎都免不了要做排序的工作. 而任何程式語言, 也幾乎都不免俗地要提供一個內建的排序函數. 如果你喜歡寫程式, 或是為了學習, 自己寫排序程式當然很好; 但是如果你的首要目標是以排序來解決你其他的問題, 倒不如把寫排序函數的時間省下來, 認真學會如何用內建的排序函數. 多用程式, 少寫程式盡量站在巨人的肩膀上, 才能看得更高, 更遠.

如何使用內建的排序函數, 例如 c 語言當中的 qsort? 例如有一個記載著 "姓名", "學號", 及 "國文", "英文", "數學" 成績的陣列. 我們可能想按照學號排序; 也可能想按照總分排序. 但是如果想按照國/英/數三科成績各別排序一次呢? 如果想將成績倒過來排呢? 先不提呼叫的語法細節, 光是想想 呼叫者想做的事可以有多少種不同的變化, 就會發現這裡有些困難: 怎麼可能有一支排序程式可以對同一資料結構 (甚至對不同的資料結構), 按照不同的鍵來排序呢?

答案很明顯: 光是傳陣列給 qsort 還不夠, 呼叫者還必須告訴 qsort, 面對兩筆記錄要做比較的時候, 何者應該排前面, 何者應該排後面, 或是孰前孰後沒有關係 (例如分數相等的情況). 呼叫者不可能很體貼地替 qsort 完整地列出每一對記錄之間的先後關係 (總共有 n(n-1)/2 組先後關係要告訴 qsort), 把這一大串所有比較的結果預先餵給它吃, 而是要讓 qsort 隨自己高興, 臨時決定要抓那一對記錄來比較, 立即就可以知道呼叫者希望這一對記錄孰前孰後. 要給 qsort 一根釣竿, 而不是要送它兩條魚. 這個釣竿, 這個最重要的參數, 不是一個數字也不是一個陣列, 而是 一個函數, 姑且叫它 cmp. 呼叫者不知道 qsort 什麼時候高興起來會呼叫 cmp, 甚至不知道 qsort 要呼叫 cmp 幾次, 更不知道 qsort 呼叫 cmp 的時候會傳那一個值進去. 所以呼叫者只好告訴 qsort: 我已幫你準備好 cmp 這個函數, 它的入口在那裡, 使用 cmp 的時候要傳入幾個參數, 每個參數各別是那個型別, ... 等等; 至於何時要呼叫它, 要傳那一對參數給它, 就隨你高興吧. 也就是說, 我們要 將函數的位址當做參數, 傳給 qsort. main 把 cmp 當做參數丟給 qsort 用

這裡是使用內建排序函數的例子.

注意 perl 版, 根據手冊的要求, 傳入的其實不是函數的位址, 而是函數的名稱 (以型別來說是一個字串); 還有為了簡單起見, 它的參數名字固定就叫做 $a 與 $b. 這兩點讓 perl 版的排序稍微比較容易使用 (對不習慣將函數當做參數來傳的人而言); 但是另一方面也表示 perl 的排序函數並非一般的「將函數當做參數來傳」, 其實並不適合拿來在這裡當例子 :-)

如果資料的每一筆記錄都很大, 搬動這些記錄太花時間, 還可以考慮不要直接對原陣列排序. 先建立一個指標陣列或註標陣列, 裡面的元素指向原陣列的記錄, 然後對這個指標陣列或註標陣列排序, 這樣省時多了. 這樣的方式, 稱為 indirect sort 間接式的排序. 下面有範例.

另例: 回想微積分裡的「二分逼近法求根」 (bisection method for root finding), 觀念很簡單: 想求 f(x)=0 的根, 例如 f(x)=x^3 - 2 好了 (也就是要求三次根號 2), 已知 f 連續, 且 f(1) < 0 而 f(2) > 0 異號, 那麼可以求 1 與 2 的平均值代入 f 看看結果大於 0 還是小於 0, ... 寫一個迴圈就很容易表達這個演算法. 如果要把這個演算法寫成一個函數 (叫做 bisection 好了), 需要把那些參數傳入這個函數呢? 呼叫 bisection 的時候, 你至少需要提供兩個初始的猜測值給它 (上面的 1 與 2, 代入 f 必須得到相反的符號); 但最重要的是你需要告訴 bisection 到底要求那個函數的根. 這裡有 librep/perl/c 等三個版本的 bisection 函數範例.

以下是常見的「函數當做參數」的場合

數值方法: 方程式求根, 微分, 積分, 微分方程的解,...
資料結構/演算法裡面的「比較函數」. 像排序需要一個「比較函數」就屬此類.
需要在特定場合 (例如滑鼠按下的時候) 但不知確切時刻, 跳出來處理事件的副程式. GUI 環境最常見; 又如 c 語言的 atexit 與 signal 也都屬於這類. 這類被當做參數傳來傳去的那個函數, 在不同的文獻/手冊裡有不同的名字, 例如 event handler, signal handler, callback, hook 等.
其他: 像是 functional programming 類的語言最常把函數當做參數來傳遞

把函數放入陣列當中

上面排序的例子當中, 有些重複出現的程式碼, 看來有點礙眼. 好的程式設計師應該具有懶惰的美德 -- 看到重複出現, 需要剪貼/複製的程式碼, 就應該警覺到這裡可能有更簡潔的寫法. 那許多個 if ... else if ... 說穿了只是在做 dispatch 發配的工作. 我們想做的事, 其實不過就是查表 -- 根據字串不同的值來決定要將那一個函數傳給排序副程式. 何不建立一個 "代碼名稱/函數入口" 的對照表? 如此就可以用迴圈到陣列裡面搜尋使用者輸入的代碼, 而在同一位置找到想要的那一個「比較函數」入口.

改良版的排序範例. 這個版本主要有兩項改變: (1) 使用 indirect sort (2) 建立函數名稱與入口的對照表 function dispatch table.

把函數當做傳回值

同樣地, 函數的傳回值平時都是簡單的整數, 浮點數, 字串; 有些函數的傳回值則是結構或陣列; 但還有一些場合, 如果傳回值可以是一個函數, 程式則會簡單很多. 例如「求導函數」這個動作, 輸入的是一個函數, 而輸出的也是一個函數. 範例中 deriv 這種奇怪的函數 (以其他函數為它的參數; 以其他函數為它的傳回值) 會用在什麼場合呢? 例如用牛頓法求方程式 f 的根當中, 就需要知道 f 的導函數才能計算下一回合的近似值; 但是如果 newton 函數要求使用者除了輸入 f 之外, 還要輸入 f' 那就太麻煩使用者了.

Closure

作業

請參考手冊, 學會使用 c 的 qsort, atexit 與 signal, 或是 perl 的 sort, grep 與 map, 或是 librep 的 sort, mapcar, filter 與 delete-if.
請修改排序範例程式當中 -c ch 的功能, 當國文成績相同時, 以英文成績決定先後順序.
呼叫你所學語言的排序函數 (不准自己寫排序程式) 對一串二位數字排序, 但是要先比較個位數部分; 如果個位數部分相同, 才比較十位數部分. 例如 71 25 42 68 92 37 40 19 56 要排成 40 71 42 92 25 56 37 68 19

一些程式語言的相關語法

知道這些觀念之後, 還必須知道: 如何在您要使用的程式語言裡面 (1) 取得函數的位址, 把它變成資料 (2) 已有一個函數的位址, 如何呼叫它。 "函數的位址" 這種東西, 在不同的語言裡面, 有不同的名稱。如果知道在這個語言裡面, 這個觀念的專有名詞叫什麼, 會比較容易 google 相關的教學文件。以下是針對一些我恰巧知道的語言, 所做的簡單摘要。

在 octave 當中, 用字串或 @ 符號取得 function handle, 用 feval 求值。例如要計算 2.71828^2 可以寫 f="exp" ; feval(f,2) 或 f=@exp ; feval(f,2)