recursive 加上 callback function

花很多時間理解一段程式碼, 再花一段時間寫篇文章, 如果可能的話, 再花點時間分享這個心得。我很享受這樣的過程, 要是能以此維生, 那就更好了。不過就像邂逅一流的美女, 得有一流的運氣, 我沒有這樣的運氣, 只能想辦法擠出時間, 在冗長的工作時間中偷點小確幸。

這是 sicp 5.2 assemble 的程式, 難倒我也。

g.scm 是我簡化的版本。用來說明這個 recusive + callback 的想法。如果你想轉腦袋瓜看這程式, 我建議你先試著用半個小時看看這程式, 如果看懂了就不用看這篇, 看不懂再來看, 可能才有點體會我在寫什麼。

一個 recursive 程式, 可能難不倒你, 如果再加上 callback function 那真是難倒人, 我的腦袋轉了好幾轉, 終於搞懂了。

extract-labes 接受兩個參數, 一個 list, 一個 procedure, 這個 procedure 接受兩個參數, 而這個 procedure 還會呼叫自己, 你很少這麼寫程式吧? g.scm L15 就是要傳進去的 procedure receive, L18 則是在傳入的 receive 再呼叫傳進去的 receive, 你應該糊塗了, 沒關係, 我也是, 直接看程式碼。

g.scm

 1 (define (assemble controller-text)
 2(extract-labels controller-text
 3  (lambda (insts labels)
 4(display "\ninsts/labels: +++\n");
 5(display insts)
 6(display "\n")
 7(display labels)
 8(display "\n++++++\n");
 9    ))) 
10
11 (define (extract-labels text receive)
12   (if (null? text)
13       (receive '() '())
14       (extract-labels (cdr text)
15        (lambda (insts labels)
16          (let ((next-inst (car text)))
17            (if (symbol? next-inst)
18                (receive insts
19                         (cons (make-label-entry next-inst
20                                                 insts)
21                               labels))
22                (receive (cons (make-instruction next-inst)
23                               insts)
24                         labels)))))))
25 
26 (define (make-label-entry label-name insts)
27   (cons label-name insts))
28 
29 (define (make-instruction text)
30   (cons text '()))
31 
32 (assemble
33   '(
34      test-b  
35      (assign a (reg b))
36      (assign b (reg t))
37      gcd-done
38    )
39 )

我們來 "人工" 追蹤整個呼叫流程, 我把每一層會傳給 extract-labels 的參數, 還有 next-inst, 以及傳入的 receive procedure 都描述出來。

第一層

(extract-labels 
1    '(test-b  
2     (assign a (reg b))
3     (assign b (reg t))
4     gcd-done)
)

(define (assemble controller-text)
  (extract-labels controller-text
receive-1
11 (lambda (insts labels)
12   (display "\ninsts/labels: +++\n");
13   (display insts)
14   (display "\n")
15   (display labels)
16   (display "\n++++++\n")))

第一層 L1~4 是第一次傳給 extract-labels 的參數一 (一個 list, 就是 text)
第一層 L11~16 是第一次傳給 extract-labels 的參數二 (一個 procedure 接受兩個參數, 就是 receive - receive-1)

第二層

extract-labels 
1  '(
2    (assign a (reg b))
3    (assign b (reg t))
4    gcd-done
5   )

99 next-inst: (car text) = test-b
(
receive-2
21  lambda (insts labels)
22  (let ((next-inst (car text)))
23    (if (symbol? next-inst)
24      (receive insts (cons (make-label-entry next-inst insts) labels))
25      (receive (cons (make-instruction next-inst) insts) labels)))
)

第二層 L1~5 是第一次傳給 extract-labels 的參數一 (一個 list, 就是 text)
第二層 L11~16 是第一次傳給 extract-labels 的參數二 (一個 procedure 接受兩個參數, 就是 receive - receive-2)
L99 的 next-inst 很重要, 所以也一起列了出來, 最後追蹤執行流程時, 會用到這個。

第三層

extract-labels 
     '(
       (assign b (reg t))
       gcd-done
      )

next-inst: (car text) = (assign a (reg b))
(
receive-3
  lambda (insts labels)
  (let ((next-inst (car text)))
    (if (symbol? next-inst)
      (receive insts (cons (make-label-entry next-inst insts) labels))
      (receive (cons (make-instruction next-inst) insts) labels)))
)

第四層

extract-labels 
     
     '(
       gcd-done
      )

next-inst: (car text) = (assign b (reg t))
(
receive-4
  lambda (insts labels)
  (let ((next-inst (car text)))
    (if (symbol? next-inst)
      (receive insts (cons (make-label-entry next-inst insts) labels))
      (receive (cons (make-instruction next-inst) insts) labels))))

第五層

extract-labels 
     '(
      )

next-inst: (car text) = gcd-done
(

receive-5
  lambda (insts labels)
  (let ((next-inst (car text)))
    (if (symbol? next-inst)
      (receive insts (cons (make-label-entry next-inst insts) labels))
      (receive (cons (make-instruction next-inst) insts) labels))))

由於這次傳給 extract-labels 的是 '(), 所以 receive 要發動了, 重點是 receive 是如何發動? 這是 recursive 的發動, 很精彩哦!

receive   是 receive-5
next-inst 是 gcd-done
insts     是 '()
labels    是 '()

所以變成這樣

(receive insts (cons (make-label-entry next-inst insts) labels))
=>

(receive '() (cons (make-label-entry 'gcd-done '()) '()))
=>

(receive '() (cons (gcd-done) '()))
=>

(receive '() ((gcd-done)) )

這時候的 receive 是誰呢?

receive   是 receive-4
next-inst 是 (car text) = (assign b (reg t))
insts     是 '()
labels    是 ((gcd-done))

(receive (cons (make-instruction next-inst) insts) labels)
=>

(receive (cons (make-instruction (assign b (reg t)) ) '() ) ((gcd-done)) )
=>

(receive (cons ((assign b (reg t))) '() ) ((gcd-done)) )
=>

(receive (((assign b (reg t))) ) ((gcd-done)) )

一樣要問: 這時候的 receive 是誰呢?

receive   是 receive-3
next-inst 是 next-inst: (assign a (reg b))
insts     是 (((assign b (reg t))))
labels    是 ((gcd-done))

再來一次:

(receive (cons (make-instruction next-inst) insts) labels)
=>

(receive (cons (make-instruction (assign a (reg b)) ) (((assign b (reg t)))) ) ((gcd-done)) )
=>

L1 (receive (cons ((assign a (reg b)) ) (((assign b (reg t)))) ) ((gcd-done)) )

L1 相當於以下的結果

1 ]=> (cons '((assign a (reg b)) ) '(((assign b (reg t))))  )
;Value 11: (((assign a (reg b))) ((assign b (reg t))))

=>
(receive (((assign a (reg b))) ((assign b (reg t)))) ((gcd-done)) )

N 問: 這時候的 receive 是誰呢?

receive   是 receive-2
next-inst 是 next-inst: test-b
insts     是 (((assign a (reg b)))  ((assign b (reg t))))
labels    是 ((gcd-done))

再次推導出:

(receive insts (cons (make-label-entry next-inst insts) labels))
=>

(receive insts (cons (make-label-entry test-b (((assign a (reg b)))  ((assign b (reg t)))) ) labels))
=>

(receive insts (cons (make-label-entry 'test-b '(((assign a (reg b)))  ((assign b (reg t)))) ) labels))
=>

(receive insts (cons (test-b ((assign a (reg b))) ((assign b (reg t))))  labels) )
=>

(receive insts (cons (test-b ((assign a (reg b))) ((assign b (reg t))))  ((gcd-done))  ) )
=>

(receive insts (cons '(test-b ((assign a (reg b))) ((assign b (reg t))))  '((gcd-done))  ) )
=>

(receive insts ((test-b ((assign a (reg b))) ((assign b (reg t)))) (gcd-done)) )
=>

(receive 
  (((assign a (reg b)))  ((assign b (reg t)))) 
  ((test-b ((assign a (reg b))) ((assign b (reg t)))) (gcd-done)) 
)

恭喜, 最後結果出來了

(receive 
  (((assign a (reg b)))  ((assign b (reg t))))                     <- insts
  ((test-b ((assign a (reg b))) ((assign b (reg t)))) (gcd-done))  <- label
)

N+1 問: 這時候的 receive 是誰呢? receive 是 receive-1; next-inst 是 ... 沒有
next-inst 了。 receive-1 很單純把 insts, labels 印出來, 不必再辛苦的轉腦袋了。

insts/labels: +++
(((assign a (reg b))) ((assign b (reg t))))
( (test-b ((assign a (reg b))) ((assign b (reg t))) )  (gcd-done))
++++++

呼! 終於追完了, 這下你可知道 gdb 的辛苦了。這個技巧有什麼好處值得我們這樣傷腦筋呢? 這樣的寫法可以不必回傳一個 (insts, labels) 的資料結構, 就把傳入的 '(test-b (assign a (reg b)) (assign b (reg t)) gcd-done) list 從中取出 insts, labels, sicp 5.2 另外提供了傳回 (insts, labels) 的寫法, 有興趣的朋友可以參考。

recursive_callback.cpp 這是我用 c++ 寫的版本, 使用了 virtual function, function object 來達成這樣的技巧。

這個範例把 string str="x51ca2yz"; 數字和英文字母分開印出來, 這麼簡單的工作用這種技巧處理變成超級複雜。

recursive_callback.cpp

 1 // ref: http://www.scheme.com/tspl4/further.html#./further:h4
 2 #include <string>
 3 #include <iostream>
 4 
 5 // use function object, virtual function.
 6 
 7 using namespace std;
 8 
 9 //typedef void (*Recv)(string &a, string &b);
10 class Recv
11 {
12   public:
13     virtual void operator() (const string &num, const string &str)=0;
14 };
15 
16 class Recv1:public Recv
17 {
18   public:
19     virtual void operator() (const string &num, const string &str)
20     {
21       cout << "num: " << num << endl;
22       cout << "str: " << str << endl;
23     }
24   private:
25     char next_char_;
26     Recv *recv_;
27 };
28 
29 class Recv2:public Recv
30 {
31   public:
32     Recv2(Recv *recv, char nc)
33     {
34       next_char_ = nc;
35       recv_ = recv;
36     }
37     virtual void operator() (const string &num, const string &str)
38     {
39       string tmp_str;
40       tmp_str.push_back(next_char_); 
41 #ifdef MORE_INFO
42       std::cout << "next_char_:" << next_char_ << endl;
43       std::cout << "num: " << num << endl;
44       std::cout << "str: " << str << endl;
45 #endif
46 
47       if ('0' <= next_char_ && next_char_ <= '9')
48       {
49         string new_str = num + tmp_str;
50         (*recv_)(new_str, str);
51       }
52       else // non num
53       {
54         string new_str = str + tmp_str;
55         (*recv_)(num, new_str);
56       }
57     }
58   private:
59     char next_char_;
60     Recv *recv_;
61 };
62 
63 void extract(const string &s, Recv *receive)
64 {
65   if (s.length() == 0)
66   {
67     string e1, e2;
68     (*receive)(e1, e2);
69   }
70   else
71   {
72     Recv2 recv2(receive, s[0]);
73     extract(s.substr(1), &recv2);
74   }
75 }
76 
77 void assemble(string &str)
78 {
79   Recv1 recv1;
80   extract(str, &recv1);
81 }
82 
83 int main(int argc, char *argv[])
84 {
85   string str="x51ca2yz";  
86 
87   cout << str << endl;
88   assemble(str);
89   return 0;
90 }

t.cpp 則是另外一個版本, 用了 c++11 lambda, std::function, function template 來做到類似的事情。我本來以為只需要 lambda 和 function pointer 的宣告就可以搞定, 但是因為用到 capture-list, 似乎只能宣告成 template, 本來以為這樣就可以收工, 但是因為傳進去的兩個 receive function 不是同一個, 所以出動了我不認識的 std::function。而因為用了 std::function 就不能帥氣的以 lambda 方式傳給 extract function, 就需到 L98, 將這個 lambda function 先透過 std::function 變成一個 function object, 再傳給 extract。重新使用 std::function 來宣告, ref L 15, L32 的 lambda function 可以直接傳入, 果然帥氣多了。

我雖然搞懂了, 但是要我以這種思維來寫程式, 呃 ... 我功力還不夠。自從學了 c++11 後, 連自己都看不懂自己在寫什麼了。

t.cpp

 1 // ref: http://kheresy.wordpress.com/2010/05/27/c0x%EF%BC%9Alambda-expression/
 2 #include <vector>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <string>
 6 #include <typeinfo>
 7 #include<functional>
 8 
 9 using namespace std;
10 
11 typedef void (*Recv)(const string &n, const string &s);
12 
13 //template<typename Func>
14 //void extract(const string &str, Func receive)
15 void extract(const string &str, std::function<void(const string&, const string&)> receive)
16 {
17   if (str.length() == 0)
18   { 
19     string e1, e2;
20     receive(e1, e2);
21   }
22   else
23   {
24     // ref: http://www.cnblogs.com/ttss/p/4100917.html
25     // std::function<int(int ,int)>func=add;
26     //   <int(int,int)>是实例化模板参数,表示返回值为int,函数参数为2个,(int,int),
27     //   即int(*pfunc)(int ,int )类型的函数
28 
29     extract
30     (
31       str.substr(1), 
32       [&](const string &n, const string &s)
33       { 
34         char next_ch = str[0];
35         string tmp_str;
36 
37         tmp_str.push_back(next_ch);
38 
39   #ifdef MORE_INFO
40         cout << "n: " << n << endl;
41         cout << "s: " << s << endl;
42         cout << "next_ch: " << next_ch << endl;
43   #endif
44 
45         if ('0' <= next_ch && next_ch <= '9')
46         {
47           string new_str = n + tmp_str;
48   #ifdef MORE_INFO
49           cout << "new_str: " << new_str << endl;
50           cout << "===========" << endl;
51   #endif
52           receive(new_str, s);
53         }
54         else
55         {
56           string new_str = s + tmp_str;
57   #ifdef MORE_INFO
58           cout << "new_str: " << new_str << endl;
59           cout << "===========" << endl;
60   #endif
61           receive(n, new_str);
62         }
63       }
64     
65     
66     );
67   }
68 }
69 
70 void assemble(string &str)
71 {
72   extract(str, 
73           [] (const string &n, const string &s) 
74           { 
75             cout << n << endl;
76             cout << s << endl;
77           }
78          );
79 }
80 
81 int main(int argc, char *argv[])
82 {
83   auto func = [&] (const string &n, const string &s) 
84   { 
85     cout << n << endl;
86     cout << s << endl;
87   };
88 
89   string str="x51ca2yz";
90   cout << str << endl;
91   //extract(str, func);
92   assemble(str); 
93   return 0;
94 }

據說這種手法叫作 CPS, 請參考 http://www.scheme.com/tspl4/further.html#./further:h4
為了畫出那個漂亮的 callback, 還有兩個 c++ 版本, 這篇讓我元氣大傷。

人體汽肛 - 風馳電掣, 人車一體

blog 文章

2015年1月8日星期四