顯示具有 sicp 標籤的文章。 顯示所有文章
顯示具有 sicp 標籤的文章。 顯示所有文章

2015年1月8日 星期四

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++ 版本, 這篇讓我元氣大傷。

2014年11月21日 星期五

[books] - SICP 2nd edition

全名是: Structure and Interpretation of Computer Programs
簡體中文書名: 计算机程序的构造和解释
20131024 淘寶訂單 20131104 到手, 12 天才收到, 有點久。
費用 42 * 5.1 = 214.2 + 145 = 359.2 委託代買購得。

這本書有電子版本, 當然是英文的, 要不然我就不用花錢買中文的版本。

Peter Norvig, paul graham 給了 5 星評價。
簡體中文版本看來薄薄的, 可別以為是本小書, 整整有 472 頁, 所以紙質真的不怎麼樣 (薄的厲害, 我覺得用印表機得到的品質都比這本書好), 在上頭寫注記得小心點, 一不小心可能就劃破紙張。在閱讀上也有點困擾, 整本書歪斜的很厲害, 不好拿著看。

簡體中文版本出版日期: 2004 年 2 月 1 日, 我這本是 201306 第八刷, 原文書 1984 年出版,是美国麻省理工学院 (MIT) 多年使用的一本教材, 1996 年修订为第二版。

後來 MIT 开始用 python 教授此课,代替了原本的 Scheme: Why MIT switched from Scheme to Python

淘寶有些書是影印的版本, 還好這本不是, 我本來還擔心這本已經出版了這麼久的一段時間, 會買不到正版的, 不過看來這本書還有陸續再出版。

我的進度很緩慢, 不過我很有耐心和毅力, 忍住開發 os, qt for android, uefi 程式的相關誘惑, 專心看這本書, 慢慢地, 慢慢地, 我越來越可以看下去了, 速度也提升了一點點。她有什麼魔力讓我願意這樣做呢? ref 2 提到: 您没法从中学到如何开发一个网站,开发一个记事本,如何绘图,它完全是在锻炼程序员的基本能力,而不是“技术”。一言以蔽之, 就是在教怎麼寫程式。很推薦大一同學和程式初學者讀這本, 這本書並不是進階書而是入門書哦! 但這不表示它很好讀, 請有心理準備。和一般的程式語言書籍不同, 裡頭的數學味道很重, 幾乎都是數學題目, 牛頓法、最大公因數、微分, 有理數/複數的運算, 真是不習慣。更不習慣的是他所選用的語言是 lisp 系的 scheme, prefix syntax 讓人迷惑, 這是吸引我的最主要部份, 據說 2008 年已經改用 python (好像是 2009), 若是 python, 我也許就沒興趣了吧! 看著一堆小括號充滿螢幕, 真是有趣。

4.1.1 ~ 4.1.4 會寫一個 scheme interpreter, 我覺得還是照課本使用 scheme 來讀 sicp, 比較不會有和課本出入的地方。

這本教科書我讀來實在辛苦, 覺得很難, 所以讀得很慢, 不知道是不是因為簡體中文的翻譯, 我覺得又讓她更難讀了。译者裘宗燕老師學問應該很好, 不過翻譯可能不是他的強項 (他翻譯過很多不錯的原文書籍)。

In a production-quality Lisp system,
書中翻成 "在產品質量的 Lisp 系統裡", 說實在, 我得看原文才懂這句話。這英文不算難懂, 但要翻譯成通順的句子那就不容易了。

It calls apply-primitive-procedure to apply primitives;
書上翻譯: 它直接調用 apply-primitive-procedure 去應用基本過程
我把它改為: 它直接呼叫 apply-primitive-procedure 去執行 primitives procedure。

To define a variable, we search the first frame for a binding for the variable
我們需要在第一個框架查找該變量的約束
descent 改: 我們需要在第一個框架查找該變數的定義

還真的不好翻譯, 只看中文會看不懂, 查詢完原文後就好多了。

This computation will run much more slowly than a gcd procedure written in
Scheme, because we will simulate low-level machine instructions, such as
assign, by much more complex operations.

書上翻譯為:
因為我們是在模擬低級的機器指令, 例如 assign, 而使用的卻是比他高級得多的操作。
這句話也是怪怪的。

書中的句子有很多像是這樣的翻譯, 讀來不能算是輕鬆, 我偶爾得對照一下原文詞句。

就算翻譯的不算好, 但中文版本還是幫了我不少忙, 這本並沒有爛到完全看不懂, 大多時候還是可以理解翻譯後的意思, 沒有中文翻譯, 我無法那麼快瀏覽過一遍, 有些翻不好的地方如果不是關鍵處, 倒也無傷大雅。加上對照原文, 對於英文不好的我來說, 甚有幫助, 這是翻譯的價值。與其要求每個人把英文、日文、德文、法文學好, 才能吸收其中的專業知識, 倒不如用國家力量培養優秀的翻譯人員。



目录

前 言
第1章 构造过程抽象
1.1 程序设计的基本元素
1.2 过程与它们所产生的计算
1.3 用高阶函数做抽象
第2章 构造数据现象
2.1 数据抽象导引
2.2 层次性数据和闭包性质
2.3 符号数据
2.4 抽象数据的多重表示
2.5 带有通用型操作的系统
第3章 模块化、对象和状态
3.1 赋值和局部状态
3.2 求值的环境模型

3.3 用变动数据做模拟
3.4 并发:时间是一个本质问题
3.5 流
第4章 元语言抽象
4.1 元循环求值器
4.2 Scheme的变形——惰性求值
4.3 Scheme的变形——非确定性计算
4.4 逻辑程序设计
第5章 寄存器机器里的计算
5.1 寄存器机器的设计
5.2 一个寄存器机器模拟器
5.3 存储分配和废料收集
5.4 显式控制的求值器
5.5 编译

這是本怎麼樣的書呢? 主要在教如何寫程式, 以及程式是怎麼樣的一個東西。前兩章對一個有涉獵程式的人來說, 大概都能明白, 也就是一般 c++ 程式入門書籍上都會談到的概念。

資料抽象 - 將資料結構和操作的函數分開, 形成一個黑箱, 資料結構的改變不會影響這些操作函數, 將修改程度降到最低。這不是一般的 c++ 程式書籍都會提到的資料封裝嗎。

用不同的資料結構來表示同一個抽象資料, 書中提到複數的例子, 可以用直角座標或是極座標 (很久沒聽到這名詞了吧?) 來表示複數, 但也必須要在這兩種資料結構做轉換。都是表示複數, 沒道理處理直角座標的程式碼無法在極座標上執行, 該怎麼做呢? 最直觀就是提供轉換的函式, 這不也是在程式設計中會看到的技巧。c++ 可以實作 cast operator 和這個觀念很類似。

再來型別轉換一多的話, 程式碼會太複雜, 能辨識出型別的操作函數不是很棒, 怎麼做? 加個 tag 判斷即可。這不就是 if/switch/case 的應用嗎?

if circle do_circle
else do_others 

而 c++ 為了消除太多 if/switch/case 導入了 virtual function, 這邊也用了類似表格法來處理這樣的問題, 類似 c 的 function pointer。這些技巧都不會因為用什麼語言而有所不同, 是基本中的基本。

但從第三章開始, 就不是一般程式設計書籍提到的東西了, 你曾經想過變數與變數值的對應是怎麼實作的嗎? 在 script language 裡頭, 執行一個 expression 時會發生怎麼樣的行為呢? 函式的參數如何替換成真正的值? 3.2 有個概括的說明。

而第四章第五章的 metacircular evaluator, register base machine 更不是容易見到的主題。我實在很懷疑這樣的書籍竟然只是定位在入門等級。

從第一章看起 ...

1.1.1 談 expression
1.1.4 利用 define 來建立 procedure (如同 c function)

1.1.5 談到了 applicative order, normal order, p13 練習 1.5 有個有趣的題目:

1.5.scm
1 (define (p) (p))
2
3 (define (test x y)
4   (if (= x 0)
5     0
6     y))

當執行 (p) 會怎麼樣, (p) 會先去找出 p 是什麼, 結果又找到 (p), 然後又去找 p 是什麼 ... 永遠都找不到, 這就是 applicative order。
而 normal order, 就很順利執行完畢, 因為 normal order 不需要把 p 計算出來, 有需要的時候在計算即可。

在 mit-scheme 可以使用 delay 這個函數來執行 normal order, (delay (p)) 就不卡住了。

ref:

1.1.6 conditional expressions and predicate, 就是 if/else 用法。

這樣讀過來之後, 就可以開始用 scheme 寫程式了。不過和 c 語言不同, 沒有 for/while loop 這種東西, 那替代品是什麼呢? 是讓人傷透腦筋的 recursive。

1.1.7 從牛頓法開始求根號 X, 正常人應該都忘記什麼是牛頓法, 只記得牛頓是誰吧?

square_root.scm
 1 (define (sqrt-iter guess x)
 2   (if (good-enough? guess x)
 3     guess
 4     (sqrt-iter (improve guess x)
 5                x)))
 6 
 7 (define (improve guess x)
 8   (average guess (/ x guess)))
 9 
10 (define (average x y)
11   (/ (+ x y) 2))
12 
13 (define (good-enough? guess x)
14   (< (abs (- (square guess) x)) 0.001))
15 
16 (define (sqrt x)
17   (sqrt-iter 1.0 x))   
18 
19 (sqrt 2)

in mit-scheme
2 error> (load "square_root.scm")

;Loading "square_root.scm"... done
;Value: 1.4142156862745097

書上有寫的東西就不說明了, 這種語法, 還真是不習慣。

1.2.1 linear recursion and iteration, 介紹 recursive 和 iteration, 書中用了兩個 factorial 來解釋。

factorial.scm
 1 ; recursive
 2 (define (factorial n)
 3   (if (= n 1)
 4     1
 5     (* n (factorial (- n 1)))))
 6 (factorial 5)
 7 
 8 ; iteration
 9 (define (factorial n)
10   (fact-iter 1 1 n))
11   
12 (define (fact-iter product counter max-count)
13   (if (> counter max-count)
14     product
15     (fact-iter (* counter product)
16                (+ counter 1)
17                max-count)))

iteration 的版本看起來好像是 recursive, 但這和 c 語言的 while, for loop 是一樣的概念。

1.2.3 介紹計算所需的時間, 計算所需要的記憶體空間。

1.3.2 介紹 lambda, 不過我覺得 the roots of lisp 解釋的比較好。

(lambda (x) (+ x 4)) 這個是 function。

((lambda (x) (+ x 4)) 5) => 9 這叫 function call。
5 是 argument (引數), x 是 parameter (參數), (+ x 4) function body。

lambda 建立的是一個沒有名字的函數, 要使用這個函數就要用上述的那個語法。配合上 define, 就可以將這個 function 對應到一個名字。

(define plus4 (lambda (x) (+ x 4)))

也可以寫成

(define (plus4 x) (+ x 4))

這是一種語法糖衣。

let 也是一種 lambda 的語法糖衣。

page 42
(define (f x y)
((lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y))
(- 1 y)))

(define (f x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a))
(* y b)
(* a b))))

let 的功能, 可以由 lambda 來提供。

1.3.3 將一個 procedure 當作參數傳給一個 procedure

1.3.4 傳回一個 procedure, 這還真難懂, 花了我好些時間。

(define (average-damp f)
  (lambda (x) (average x (f x))))

真的很難懂吧!

first-class elements:

  • They may be named by variables.
  • They may be passed as arguments to procedures.
  • They may be returned as the results of procedures.
  • They may be included in data structures.65

符合這些條件的 function 就稱為 first-class function, 又是一個流行的名詞。當然符合這些條件的 object 就是 first-class object, 當然符合這些條件的 people 就是 first-class people XD

這是由 the British computer scientist Christopher Strachey (1916-1975) 幫我們整理出來的概念。



2.1.1 p56 介紹了 pair, 有相關的操作函數 cons, car, cdr, list (p66, 為了方便使用 cons, scheme 提供了 list) p57 最下面的註解解釋了 cons, car (Contents of Address part of Register, cdr (Contents fo Decrement part of Register) 這幾個奇怪的名稱。

2.1.3 p61 實作了 cons, car, cdr。

(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1 -- CONS" m))))
dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))

(car (cons x y))
(cdr (cons x y))

cons 會傳回一個 procedure, 就是 dispatch, 再用來和 car, cdr 一起運作。

2.2.1 p67 提到 (cadr [arg]) = (car (cdr [arg])) 這樣的縮寫方式, 免得寫很多 car, cdr ...

2.2 Hierarchical Data and the Closure Property, 這個 Closure 不是你想的那種, 這是指這個資料結構可以一直的串下去。





cons 最主要就是一個 pair 結構, (cons 1 (cons 2 (cons 3 '() ))) 這樣的資料結構就是由這些 pair 一個一個串接起來, 別小看這麼簡單的東西, 這除了可以表達很直觀的 sequence 結構外, 還可以看做是一顆樹的結構。在 3.3.2 還會用這個來表示 queue, 用這樣的方式:



很難懂, 我花了一天才搞懂這個 queue 的表達方式。
ref: http://descent-incoming.blogspot.tw/2014/08/implement-queue-by-mit-scheme.html

2.3.3 以集合 (sets) 為範例, 以 list (排序和未排序兩種 list) 和 tree 為資料結構, 實作加入一個元素到集合裡頭, 某個元素是否在這個集合, 找出差集和聯集。

scheme 當然沒有類似 c 的 struct 這種東西, 書中用 list 來模擬 tree。

2.4.3 有提到一個 message passing 的設計方式。

3.1 這節在描述 assginment 和 local 變數的行為。
3.1.1 導入了 set! 用來做 assginment。

3.1.3 說明了 functional programming 和 imperative programming。

functional programming wiki 上的解釋
In computer science, functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

函數式編程(英語:Functional programming)或者函式程式設計,又稱泛函編程,是一種編程典範,它將電腦運算視為數學上的函式計算,並且避免使用程式狀態以及易變物件。

相信你看得一頭霧水。來看 sicp 3.1.1 的解釋:

sicp 3.1.3
Programming without any use of assignments, as we did throughout the first two chapters of this book, is accordingly known as functional programming.

函數式程式設計原來就是這樣定義, 之前都搞不懂。網路有些文章還寫像數學函數那樣來寫程式 (大概都是抄 wiki 的吧), 數學函式我知道, 但還是不知道什麼是函數式程式。看些討論講得好神, 不過基本就是這樣。而採用 assignments 的稱為 imperative programming。沒用 assignments 的就是函數式程式設計

不過我覺得書上提到的 assignment 比較像是使用 c 的 static variable 作 assignment 的動作。

難怪在這前兩章的範例程式時, 就覺得哪裡怪怪的, 沒錯, 我都沒看到 assignment 的概念。原來沒 assignment 也是可以寫程式的。

自制編程語言 page 7 寫的更直接: 「變數值無法被更改」的語言就是函數式編程語言。我覺得這更容易理解, 一句話道出 functional programdming 真諦。

factorial_1.scm functional programming
1 (define (factorial n)
2   (define (iter product counter)
3     (if (> counter n)
4       product
5       (iter (* counter product)
6             (+ counter 1))))
7     (iter 1 1))
8 
9 (factorial 5)

factorial_2.scm imperative programming
 1 (define (factorial n)
 2   (let ((product 1)
 3         (counter 1))
 4     (define (iter)
 5       (if (> counter n)
 6         product
 7         (begin (set! product (* counter product))
 8                (set! counter (+ counter 1))
 9                (iter))))
10     (iter)))
11 
12 (factorial 6)

上述程式碼便是分別展示這兩種編程方式。

3.2 在說明引進 assignment 之後, 整個程式的運作模型。很重要, 也很難理解, 我花了不少時間在這邊。

3.2.1 說明了當定義一個 procedure (在 scheme 只能用 lambda 產生一個 procedure), 或使用 define (這只是一個語法糖衣, 實際是用 lambda 產生一個 procedure) 產生一個 procedure 時, 怎麼將這個 procedure 和該名字關聯在一個環境裡。而這個 procedure object 包含兩部份, 一個是 procedure code 本身 (含型式參數部份), 一個是環境 (可能是一個指到某個環境的指標)。

在呼叫這個 procedure 時, 傳入的真正參數是怎麼和 procedure 的參數產生關聯, 這時後會建立一個新的環境/frame, 而呼叫這個 procedure 的環境便成為這個新環境的上層環境。

這節一開始我並沒有完全看懂, 而是看懂 4.1 metacircular evaluator source code 這部份的程式碼時, 我回頭看了好幾次才看懂。也因為 bind 被翻譯成約束, 有些句子也成為閱讀障礙, 建議對照原文, 應該會比較清楚。

雖然翻譯有些問題, 但我還是覺得中文版本幫上不少忙, 當然有原文對照會比較好些。若是沒有中文版本, 我閱讀的速度絕對不能這麼快。

這裡的解釋很重要, 是變數代換和 procedure 求值的關鍵, 若真看不懂, 只好看 4.1 metacircular evaluator source code。兩相對照, 相得益彰。

關鍵點有兩個:
  1. evaluate 一個 procedure 時, 建立 procedure object (一個 pair, 其中是 function body, 另一個是環境指標, 指到某個環境), 環境指標的上層環境是誰也要清楚。
  2. apply 一個 procedure 時, 環境是怎麼建立 (會建立一個新環境), 上層環境是誰? 如何將變數值對應到函式的參數。

(define (square x) (* x x)) 這是 evaluate
(square 5) 這是 apply

3.2.2, 3.2.3 3.2.4 以三個實際的程式碼, 分別說明了, 環境如何建立, 對應的變數如何與實際的變數值對應起來, 不算好懂, 得花點腦力才行。不過這個觀念很重要, 可以得知變數是怎麼關聯起來的, 為什麼同名稱的變數不會互相干擾, 獨立對應到不同的值。

要搞懂 interpreter, 3.2 這部份的東西要有清楚的認知。

3.2.3 的例子:

withdraw.scm
 1 (define (make-withdraw balance)
 2   (lambda (amount)
 3     (if (>= balance amount)
 4       (begin (set! balance (- balance amount))
 5              balance)
 6       "Insufficient funds")))
 7
 8 (define W1 (make-withdraw 100))
 9 (W1 50)
10 (W1 20)

說明環境怎麼用來維護 balance 這個局部變數, 有點像是 c 的 static 變數。

3.3.1 則介紹了 set-car!, set-cdr! 來改變一個 list。

change_list
 1 1 ]=> (define alist (list 1 2))
 2
 3 ;Value: alist
 4
 5 1 ]=> (display alist)
 6 (1 2)
 7 ;Unspecified return value
 8
 9 1 ]=> (set-car! alist 5)
10
11 ;Unspecified return value
12
13 1 ]=> (display alist)
14 (5 2)
15 ;Unspecified return value

3.4 concurrency: Time is of the essence 提出撰寫 concurrency 程式的問題, 以及利用 mutex 來處理共享資源。在目前這麼流行的 thread 環境中, 這些都是大家朗朗上口的概念, 但這本書可是很早就討論了這些東西, 而就算大家朗朗上口這些概念, 把 thread 程式寫好也不是件容易的事。

chapter4 是很精彩的一章, 4.1 要寫出一個 metacircular evaluator, 講白話就是用 lisp 寫出一個 lisp interpreter, 這裡的實作當然是 scheme。基本上只要讀到 4.1.4 就有個可以執行 scheme 的 interpreter, 是不是很興奮阿! 這可說是我讀這本書的最大動力了, 好久好久以前就想知道 interpreter 是怎麼做的。

如果你覺得 chapter 1, 2, 3 已經很難, 那我得告訴你, 這章更難, 得要有花更多時間的心理準備, 不過好消息是: 這章不是最難的, 後面那章更難。

我飛快閱讀過前面三章, 略過習題, 就是為了可以儘快看到這章。我把精力花在 4.1.1 ~ 4.1.4, 並以 c++ 實作了相同的版本。也許這樣講誇張了點, 光讀這四小結的時間可抵上 1, 2 章。

只要讀完這四個小節, 就可以寫出四則運算、自訂變數、函式呼叫、判斷式的直譯器, The unix programming environment 可是用了一章 (第八章) 在講這些東西, 應該是最簡單的文件了。不過我得先告訴你, 我可是花了至少一個月的時間才真的搞懂, 研究直譯器真的很有趣, 但真的很花時間、精力。

4.1.5

(eval '(* 5 5) user-initial-environment)
(eval (cons '* (list 5 5)) user-initial-environment)

eval 需要帶入一個環境

4.1.6 提到了 internal definitions, 看以下的程式碼:

(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
)

雖然在 even? 內用到 odd?, 但這應該難不倒你, 這個程式可以正常執行。

Exercise 4.19.

(let ((a 1))
(define (f x)
(define b (+ a x))
(define a 5)
(+ a b))
(f 10))

這個呢? (f 10) 會得到 20 還是 16 還是發出錯誤訊息? 難倒你了吧? 在 mit-scheme 是發出錯誤訊息, 我也喜歡這樣的實作方式。

4.4 引入了 logic programming, 我對這個主題很陌生, 有了 functional programming 還有個 logic programming, 4.4 給了一個例子說明什麼是 logic programming。不過你以為這樣就結束了嗎? 4.4.* 計劃要打造出一個 logic programming 的 interpreter, 哇 ... 一定要這麼猛嗎? 我快要投降了。

chapter 5 則更進一步, 打造一台模擬機器, 讓你在上頭跑 scheme 的程式。和 java 的 virtual machine (stack base) 不同, sicp 介紹的是 register base machine。這章也是要燃燒很多的腦力, 難度比第四章略難。

5.1 介紹了計算 GCD, factorial 的機器設計流程。

5.1.1 用了一個描述暫存器機器的語言, 如下:

gcd
1 (controller
2  test-b
3    (test (op =) (reg b) (const 0))
4    (branch (label gcd-done))
5    (assign t (op rem) (reg a) (reg b))
6    (assign a (reg b))
7    (assign b (reg t))
8    (goto (label test-b))
9  gcd-done)

這是用來描述一個計算 GCD 的機器, 只要把暫存器 a, b 存入兩個數字, 機器運算後, 會在暫存器 a 得到這兩個數的 GCD。

5.1.4 提到使用 stack 來實作 recursive。用了 gcd, factorial 來說明這兩個 recursive 的不同。

gcd 只是很單純將原來的問題簡化為另外的 gcd 計算; 而 factorial 則需要計算出另外的 (n-1)!, 並需要這個 (n-1) 的結果。gcd 的計算不需要用上 stack 來支援 recursive, factorial 則需要 stack 來支援 recursive。這個小節最後還以 fibonacci 來說明 double recursion 的概念。

5.2 實作模擬器程式碼, 跑一下哪個 GCD 機器。程式碼難到嚇人, 我這 scheme 初學者完敗在 5.2.2 的 extract-labels, recursive callback function 真的難倒我。

看懂這段程式碼後, 我寫了一篇文章: recursive 加上 callback function

透過程式碼了解其基本精神後, 我大概知道要怎麼寫一個類似 qemu 的模擬器了。

5.4 將寫出一個 explicit-control evaluator, 用來執行 4.1 的那個 metacircular evaluator, 真是太酷了!

有一個 scheme chip, 可參考:
Batali, J. et al. "The Scheme-81 Architecture—System and Chip." Proc. Conference on Advanced Research in VLSI, P. Penfield Jr. ed., MIT, 1982, pp. 69-77.
不過我找不到文章內容。

5.5 提到編譯這個主題, 和 5.4 的 interpreter 對照, 兩個不同的執行方式, 可以體會其中的優缺點。

5.5.7 會示範如何將 compile 後的 code 載入到模擬的機器執行。

這章一樣是要花費很大的時間、腦力, 本科系的朋友應該會很喜歡這些主題。

網路上有很多本書的討論訊息, 但如果你沒看過這本書, 應該還是不知道這本書在說什麼 (我認為是他們沒有完全讀完這本書, 再強調一次, 本書我覺得不好讀, 相當接近我讀的 os 書籍難度; 如果你聽過程式設計師的自我修養 - 連結、載入、程式庫這本書, 我覺得 sicp 比這本還難讀, 自我修養我覺得不算難讀), 希望這篇文章能讓你了解個大概, 也能吸引你去讀這本書。當然沒有哪本書是一定非讀不可, 你總是可以從其他地方或取相同的知識, 要得到本書的知識也並非要從本書開始。網路評價很好的書籍也並非就一定要讀。

這兩篇評論寫的很好, 一看就知道是有看過整本書的人所寫:

1996 的書過時了嗎? 我不認為, 光是第四章、第五章就值回票價。你去哪找兩章就可以講解/完成一個 interpreter 和 register base machine 的書。

相關資料

nil cannot work: http://stackoverflow.com/questions/9115703/null-value-in-mit-scheme
使用 '() 來代替 nil

ref:
  1. SICP读书笔记 (1) : http://kidneyball.iteye.com/blog/922953
  2. 老赵书托 (2): 计算机程序的构造与解释
  3. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I by John McCarthy:
    htmlpdfpdf2.
  4. sicp code: http://mitpress.mit.edu/sicp/code/index.html
  5. 有一段 Alan J. Perlis 文章的翻譯。
  6. SICP in Python
  7. SICP 解题集
  8. sicp epub version
  9. 線上課程
簡體中文字幕 sicp 課程:
http://v.youku.com/v_show/id_XNTMxODY1NTg4.html

這是課程的其中一部分, 有興趣的朋友可自行搜尋其他部份。




2014年10月27日 星期一

scheme interpreter by c++

看完 sicp 4.1 時, 真是興奮, 原來 scheme interpreter 就是這樣完成的, 我辛苦搞懂了 scheme 的程式碼 (我整理了一系列看懂 sicp 4.1 的《心得》), 想用 c/c++ 實作一個簡單版本, 畢竟 c++ 一直以來是我很喜歡的語言。

由於 scheme 語法很簡單 (對比 c 語法之流), 給了我信心, 我深信我一定做的出來, 但這只是錯覺, 寫 compiler/interpreter 真的比較難, 是有他的道理的。

c++ 的版本比我想得還難, 我一下子就遇到 scanner 的困難, 沒想到我特地找了 s-expression 來練習, 還是無法實作 scanner, s-expression 已經算是很簡單的了。

把 (+ 1 2) 變成

(
+
1
2
)

產生這樣的 token list 不難, 難的是怎麼把它變成 scheme 的 list 資料結構。
ex: (+ ( * 2 3) 1) => + * 2 3 1
而 car + * 2 3 1
得到 +

(car (cdr + * 2 3 1) )
要得到 * 2 3
這樣的資料結構。

ref:
https://github.com/descent/simple_scheme/blob/master/s_eval.cpp
Cell *read(TC &tokens)

這裡需要用到 recursive 的觀念, 並不是很好想。

sicp 4.1 的實作並沒有以 BNF 的形式來處理, 似乎不需要用 BNF 的方式, 直接就可以寫出整個 parser, 沒有符號表, 沒有 AST, 當然那個 recursive 一樣很複雜。

(How to Write a (Lisp) Interpreter (in Python)) 內文給我了一些提示, 真難得有繁體中文翻譯: http://reborn2266.blogspot.tw/2011/11/how-to-write-lisp-interpreter-in-python.html

可惜的是我還不夠聰明到可以用 python code 推出 c++ 的版本, 直到 Lisp interpreter in 90 lines of C++ 這篇文章的 source code 一舉為我解除疑惑。

除了幫我解決 scanner 的疑惑外, 還幫我解決了 Cell 這個資料結構的問題, 我想了好幾天, 總是卡在某個地方無法突破。不過最後我重新改寫成較類似 scheme cons 的 pair, 不需要使用 std::list, c++ 標準程式庫的東西我得慢慢移掉才行, 這次的改寫讓我一次完成兩個功能; std::map 則是我下階段要移掉的東西。

完成一個 interpreter 並沒有想像中的容易, 光是最簡單的計算機, 就得使用上編譯器教科書上的理論, 否則應該是很難寫出來, 如果你靠自己克服了這難題, 想必你一定是個聰明的傢伙。

UNIX 编程环境 (Brian W.Kernighan, Rob Pike) 第八章在談一個計算機怎麼寫, 其中使用了 lex, yacc。

Stroustrup Programming: Principles and Practice using C++ (這本有 Second Edition, 談及 c++11, c++14) 6, 7 章也在談怎麼寫一個計算機, 沒有使用 lex/yacc。C++ 程序设计原理与实践 (Programming: Principles and Practice using C++ 的簡體中文版本 - 第一版) p 109 提到: 「這是 50 年來的經驗, 想要一夜打破 50 年來的經驗不是個好主意。」

1+2*3 也許很難處理, 我本來以為 (+ 1 (* 2 3)) 會好一點, 是好一點, 不過依然不是件簡單的事情。

一開始的目的就只打算完成四則運算, (+ 1 2 3), (+ (* 2 3) 6) 之類的, 沒想到也花了好大一番功夫才搞定。

這是兩階段的學習, 我先把 scheme 的實作版搞懂, 才來實作 c++ 版本的四則運算。

https://github.com/descent/simple_scheme
tag three_op

在 branch origin/new_cell 我重新實作了 Cell, 使用 Cell *get_cell(const char *val, ProcType proc) 來從 array 得到一個 Cell, 而不是用 malloc/new 來得到一個 Cell, 這是為什麼呢? 容我賣個關子, 若你大概看了這個版本, 應該會覺得這是個很像 c 的 c++ 程式, 事實上, 這是刻意的, 因為我不想使用太多 c++ 的特性, 怕到時候會有問題。

在這個版本之後, 我有了 cdr, car, cons 可以用, 後來的程式碼幾乎就是把 sicp 的 code 抄過來。為什麼要改寫 struct Cell? 因為我被 car, cdr 整個搞亂了, 套用原來的 Cell 結構, 我很難做到 car, cdr 的功能, 老是把 car, cdr 的結果搞錯, 我並沒有完全使用 Lisp interpreter in 90 lines of C++ 的程式碼, 我只需要 scanner 和 Cell 這部份, 打通之後就可以繼續下去; 新的 Cell 幾乎大量使用指標操作, 沒有 std::list, 整個速度應該提升不少。

再來的困難是環境, 有點複雜, 和 sicp metacircular evaluator 的實作不同, 我有 std::map 可以用, 實作環境輕鬆多了。

lambda 的實作我認為最困難, 只要過了這關, 後面的 define, if, cond, set!, begin 根本就是照抄 sicp 的 code。

我就是照著 sicp metacircular evaluator 這系列, 一步步完成 c++ 版本。其中花了不少精神, 總算小有所成。

這個程式在 linux 平台開發/測試, 再來的版本就有點挑戰性, 我滿懷能量, 準備完成它, 這是個集我所學大成的計劃, 取名為作業系統之前的 scheme

後來在開發了《simple c++ 標準程式庫》後, 我總共有了
  1. linux
  2. bare-metal rpi2
  3. bare-metal stm32f407
  4. bare-metal p103 模擬器
  5. x86 16bit mode bare-metal
  6. x86 16bit mode ms dos
  7. uefi
這麼多的實作版本。

uefi scheme

這是其他人開發的 c++ 版本:
http://www.open-open.com/lib/view/open1352593340668.html

其 soure code:
https://github.com/zoowii/SchemeRuntime

我的版本:
https://github.com/descent/simple_scheme

ref:

2014年8月17日 星期日

implement queue by mit-scheme

這是 sicp 3.3.2 節的程式碼

queue.scm
 1 (define (front-ptr queue) (car queue))
 2 (define (rear-ptr queue) (cdr queue))
 3 (define (set-front-ptr! queue item) (set-car! queue item))
 4 (define (set-rear-ptr! queue item) (set-cdr! queue item))
 5 (define (empty-queue? queue) (null? (front-ptr queue)))
 6 (define (make-queue) (cons '() '()))
 7 (define (front-queue queue)
 8   (if (empty-queue? queue)
 9     (error "FRONT called with an empty queue" queue)
10     (car (front-ptr queue))))
11 
12 (define (insert-queue! queue item)
13   (let ((new-pair (cons item '())))
14     (cond ((empty-queue? queue)
15            (set-front-ptr! queue new-pair)
16            (set-rear-ptr! queue new-pair)
17            queue)
18           (else
19             (set-cdr! (rear-ptr queue) new-pair)
20             (set-rear-ptr! queue new-pair)
21             queue))))
22             
23 (define (delete-queue! queue)
24   (cond ((empty-queue? queue)
25          (error "DELETE! called with an empty queue" queue))
26         (else
27           (set-front-ptr! queue (cdr (front-ptr queue)))
28           queue)))
29 
30 (define q1 (make-queue))
31 (insert-queue! q1 5)
32 (insert-queue! q1 6)
33 (insert-queue! q1 7)

我被 cons 的 pair 搞亂, 花了一天才看懂這程式碼。而且很難得的畫了一些圖來說明 (畫這些圖形還真是難倒我, 醜了些, 大家將就看些)。



這是所使用的資料結構, cons 會建立一個 pair, 像上圖的長方形, 有兩個點, 指向另外的 pair。

(define q1 (make-queue))




(insert-queue! q1 5)




(insert-queue! q1 6)

寄件者 sicp-queue



(insert-queue! q1 7)



經過每個圖片與程式碼的對照, 應該可以理解為什麼程式會寫成這個樣子。

L23 的 delete-queue 相對也就很好理解了。

使用這樣的寫法是因為效率的因素, 不需要一次又一次的呼叫 cdr 來取最後的元素, 就算使用 scheme 還是可以兼顧效率的。

若在面試上考 queue 並且不限制語言的話, 用 lisp 系寫出來, 面試官會對你印象深刻吧!


2014年7月8日 星期二

sicp: 開發工具 - mit-scheme

這本書使用的語言是 scheme, 是 lisp 的一種方言, scheme 有很多實作品, 書是 mit press, 我自然找了 mit-scheme 來用, 也是 gnu 的產品之一, 在 ms windows, linux 都可以使用; guile 也是 gnu 的 scheme 實作品。

據聞在最後一堂課時, 使用的 scheme 是 DrScheme (目前已更名為 Racket), 我沒有特別研究那個好, 只是這本書是 mit press, 我當然找 mit-scheme 來用, 書上也多少會提到 mit-scheme 有哪些 feature, 正好也是這本書的範例可以使用的功能。

其他的 Scheme implementations: http://community.schemewiki.org/?scheme-faq-standards#implementations

雖然有很多的 scheme 實作, 不過 4.1 的 metacircular evaluator 範例我在 guile, chicken 的 scheme 實作品上都無法順利執行, 若不想修改程式碼, 還是跑在 mit-scheme 比較保險。

這篇不是 scheme 的教學, 我都還不會怎麼可能寫得出教學文, 這只是在說明如何使用 mit-scheme 的開發環境和比較常用的功能。

想學 lisp 很久了, 這次就靠這本書來學習吧, scheme 也可以啦, 反正都是那種很多小括弧的東西。本書並不是專門用來教學 scheme, 只會提到範例程式中所需要的語法, 不過這樣也算夠用, 要深入的話還得參考相關 scheme 書籍。

如果要編譯 mit-scheme 可以從 http://www.gnu.org/software/mit-scheme/ 下載 Portable C 的版本, 我希望你不需要用到這招, 我在 gentoo 上需要這麼做, http://www.gnu.org/software/mit-scheme/liarc-build.html 這裡有編譯方法。

linux/debian 安裝還是用 apt-get:

apt-get install mit-scheme

windows 的安裝應該難不倒你, 你都挑了這麼冷門的東西來學, 應該和我一樣, 是個品味很特別的程式員。

最好也安裝一下說明文件, 這東西很冷門的, 幾乎找不到什麼網路教學文章, 自己 K 文件吧!

apt-get install mit-scheme-doc

執行: mit-scheme

descent@debian-vm:~$ mit-scheme

會跑出一個 mit-scheme 環境, 可以輸入程式碼, 結果會立刻跑出來, 很像 dos 下的 etbasic。

mit-scheme
 1 descent@deb64:/media/sdb1/descent/git/blog_articles/lisp$ mit-scheme
 2 MIT/GNU Scheme running under GNU/Linux
 3 Type `^C' (control-C) followed by `H' to obtain information about interrupts.
 4 
 5 Copyright (C) 2011 Massachusetts Institute of Technology
 6 This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or
 7 FITNESS FOR A PARTICULAR PURPOSE.
 8 
 9 Image saved on Friday August 30, 2013 at 4:37:34 PM
10   Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/x86-64 4.118 || Edwin 3.116
11 
12 1 ]=> (+ 1 2 3)
13 
14 ;Value: 6
15 
16 1 ]=> 

L12 就是我輸入的程式碼。

說真的, 我還真不習慣在一個 interpretation 環境下開發程式, 。

文件上建議使用 Edwin 來輸入 scheme 程式, edwin 很類似 emacs, 有除錯器的功能。
file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/Edwin.html#Edwin
說明如何使用 edwin。

我敢打賭, 你要是沒用過 emacs, 絕對恨透了 edwin 這東西, 難用到暴。還是先回到 interpretation 環境下。

mit-scheme document
file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/index.html
這文件最好先看一下, 要不然還真的不知道怎麼使用 interpretation 環境下的操作方式。

ctrl+c q exit mit-scheme
(exit) 也可以離開 mit-scheme。

(quit) 不是離開, 而是在背景執行 mit-scheme, fg 就可以把畫面叫回來。

(load "filename.scm")
可以載入一個 scheme 檔案。

4.1 Compilation Procedures
file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/Compilation-Procedures.html#Compilation-Procedures
(cf "foo")

不像 c compiler 一樣, 可以很乾脆的產生一個執行檔。他產生的 binary 只是讓 interpretation 環境載入用。

再回到開頭的 edwin, 它很難用, 不過我還是比較常用這個, 因為那個 interpretation 環境我覺得更難用。

file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/Edwin-Scheme-Evaluation.html#Edwin-Scheme-Evaluation
會說明如何執行在 edwin 敲入的程式碼。簡單點就是在你要執行的程式碼後面按下 ctrl+x ctrl+e。

M-o 會計算檔案中所有的 express。

edwin 很類似 emacs, 所以連按鍵都很類似。

ctrl+x ctrl+f 可以載入檔案。
ctrl+x ctrl+c 離開 edwin。
ctrl+x ctrl+s 存檔。

C-@ mark
C-x C-x 可以查看 mark 的位置, 不知道意思的話, mark 完之後一直按 C-x
M-w copy
C-w delete

C-x b switch buffer
C-x k kill buffer

C-x o 切換 window
C-x 2 分割成兩個 window
C-x 0 (數字0) 關掉游標在的那個 window

edwin REPL mode:
M-x repl 可進入 REPL mode

這東西太冷門了, 希望有人因為我這篇文章一起來學習 scheme。

scheme compiler: CHICKEN Scheme, 這東西可以產生一個獨立的執行檔, 真是太酷了。

用 apt-get 搞定它。

apt-get install chicken-bin

編譯用法:
http://wiki.call-cc.org/man/4/Using%20the%20compiler

最簡單的用法, 來個階乘測試:

factorial_1.scm
 1 (define (factorial n)
 2   (define (iter product counter)
 3     (if (> counter n)
 4       product
 5       (iter (* counter product)
 6             (+ counter 1))))
 7     (iter 1 1))
 8 
 9 (write (factorial 5))
10 (newline)

csc factorial_1.scm

descent@deb64:3.1.3$ ./factorial_1 
120

要先產生出 c souce code 也行, 文件拉到最下方, 麻煩多了。

mit-scheme 教學:
  1. http://faculty.csie.ntust.edu.tw/~ywu/cs4001301/MITScheme_tutorial.pdf
  2. http://faculty.csie.ntust.edu.tw/~ywu/cs4001301/Scheme_tutorial.pdf
  3. Simply Scheme, second edition
  4. The Little Schemer book
  5. http://www.cs.rpi.edu/academics/courses/fall05/ai/scheme/starting.html
  6. Scheme 語言概要(上/下):
    http://www.ibm.com/developerworks/cn/linux/l-schm/index1.html
    http://www.ibm.com/developerworks/cn/linux/l-schm/index2.html
  7. http://blog.csdn.net/zzulp/article/category/682234
  8. MIT Scheme 的基本使用:
    http://www.math.pku.edu.cn/teachers/qiuzy/progtech/scheme/mit_scheme.htm

ref:
as script:
http://snippets.dinduks.com/mit-scheme-run-a-script
http://vepa.in/technology/mit-scheme-unix-scripts-and-cgi

scheme < script.scm | grep ";Value:" | sed "s/;Value: /Result: /" 
scheme-run () { scheme < $1 | grep ";Value:" | sed "s/;Value: /Result: /" } 

Petite Chez Scheme (從 Scheme 编程环境的设置得知, 據說效能很好):
http://scheme.com/download/index.html#sec:petitechezscheme