Pages

Saturday, October 31, 2009

Test Yourself

超過半年沒新文章了XD

每次看著空虛的 blog 就想把一些庫存丟出來充充版面,但有些內容過了該發表的時間點就沒什麼動力寫完,只好繼續讓 blog 就這樣晾著。沒寫文章的這陣子,程式也沒多寫,大概都把時間耗在 plurk 和 irc 上了 (也撥了一些時間看看土曜劇和晨間劇啦)。倒是最近遇到一個想用 forth 寫輸入法的狂熱份子,又喚醒我心中的 forth 魂了。

forth 毫無疑問是我最喜愛的程式語言,但本 blog 的 forth 分類卻只有屈指可數的兩篇文章。實在是因為我除了把 forth 當作頭腦體操外,根本很少使用 forth 來寫正式的程式 (而且功力也差...)。話雖如此,閒暇時仍舊會在 google 上搜尋相關資料,思考著怎麼利用在 forth 中的體會,幫助其他開發工作。但大多數時間還是抱著好玩的心態來看 forth,偶爾想到就會找出來玩一下。

這次嘗試了 reva 這套 forth engine,雖然提供了很多方便的函式庫,但卻不相容於 ANS 標準,所以一開始吃了不少苦頭。花了一點時間看了實作,再把以前在 pforth 上寫的練習程式移植到 reva 後,慢慢搞清楚 reva 與 ans 之間的差異了 (有些 word 的確方便多了)。

另外就是玩一下 ffi 的部份。第一個練習就是來個 vte,根據 caleb 提供的範例程式改寫一下 (去掉 turnkey 的部份):

" libvte.so" lib libvte

0 func: vte_terminal_new
8 func: vte_terminal_fork_command

needs ui/gtk2
~gtk2

: =exit callback gtk_main_quit ;
: main ( -- ) init
 GTK_WINDOW_TOPLEVEL gtk_window_new dup dup
 vte_terminal_new
 dup 0 0 0 0 0 0 0 vte_terminal_fork_command drop
 2dup _add
 z" child-exited" ['] =exit _connect drop
 z" delete-event" ['] =exit _connect drop
 gtk_widget_show_all gtk_main ;
main bye

直接翻譯自原本的 c 程式,除了變數都透過 stack 來操作外,看起來實在沒什麼不同。事實上也不過是把 forth 當作 libvte.so 的外殼,透過交談式界面來操作,相當方便。執行結果如圖:

有了 ffi 後,原本在 c 世界的資源都可以拿來利用了,而且寫起來也有趣多了。即使不特別用 forth 風格來撰寫,當作 c 來寫也不是太困難的事,實作邏輯很相近 (就像很多人拿 c++ 來寫 c 一樣...)。


話說回來,forth 提供的語法其實比 c 豐富很多,應該要被歸類在比 c 還高階的語言才對阿!思考到這裡,想起以前嘗試過用 forth 實作 Higher-order Function,就是企圖在 forth 中使用高階的工具。

其實剛接觸 forth 時一直都是當作比較方便的組合語言來學。看了 Joel 的文章後,覺得在其他語言也應該享受到 HOF 的方便,再加上那時也學了一陣子程式設計,正好試試看是不是比 Joel 大一時還厲害 (笑)。不過 Python 或 Perl 這幾個常用的語言早就內建類似的工具了,最後就找了 c 和 forth 來玩。c 的版本很多人玩過,我就不再多說了,還是聊聊 forth 吧。

有嘗試過用 functional 風格寫 c 的人應該會知道這兩種不同程式風格不是那麼容易結合,一方面是 lisp 的設計讓這些高階運算很容易達成;而以凡事以 list 為運算對象的概念,也跟 c 不太一樣。但在 forth 裡卻很容易跨越這層隔闔,雖然 list 物件得另外實作出來,但偷懶一點還是可以用 stack 來模擬的。只要把前置式語法改為後置式語法,也許很多在 functional 世界發展成熟的設計手法就可以直接搬到 forth 使用了。

以 Currying 來說,在 forth 裡再自然不過了。c 的實作可以參考 jservthinker 的魔法,而 forth 呢,其實在標準的 word 中就有不少是帶有 currying 風,如 0<0=1+2/ 以及 cell+cells。大概因為太自然了,即使 forth 圈沒有刻意使用 currying 來稱呼 (就我所知是沒有),幾乎是平常就在做的事。以 Wikipedia 上舉的例子來說明:

Take the function f(x,y) = y / x.
To evaluate f(2,3), first, replace x with 2.
Since the result is a new function in y, this function g(y) can be defined as
g(y) = f(2,y) = y / 2.
Next, replacing the y argument with 3,
provides the result, g(3) = f(2,3) = 3 / 2.

在 forth 中可以寫成:

: f ( y x -- n ) / ;
: g ( y -- n ) 2 f ;

3 2 f . cr
3 g . cr

透過 forth compiler 直接將參數 (也就是 2) 編譯到 forth dictionary 中,往後使用 g 時就會自動將 2 傳給 f。可以看到在 forth 裡使用 currying 有多麼自然。

那麼其他的 HOF 呢?回到 Test Yourself 這篇文章,文中第一題出現的 accumulate,可以在 SICP 的 2.2 節看到,事實上就是 fold-right。在 python 中有個很像的工具,叫做 recude (但 reduce 應該是 fold-left),摺疊的方向是不同的。要自己實作一個來用也不難,根據這裡提供的 Haskell 程式:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

可以知道 foldr 的實作關鍵在於從 list 的右邊開始摺疊,以遞迴的想法來說就是先呼叫到底,直到遇到終止條件 (empty list) 再開始回頭計算。釐清這個想法後就可以翻譯成 forth 程式,但為了方便,先定義一些方便的小工具:

hex EFABCD constant nil
: car ( addr -- n ) @ ;
: cdr ( addr -- addr' ) 1 cells + ;
: null? ( addr -- t ) @ nil = ;

因為偷懶不想實作 list object,這邊先用陣列來模擬,在最後塞一個 nil 作為辨識用。 carcdrnull? 的定義可以參考 lisp,而且也可以看到這裡的 cdr 用到了上面提到的 currying。有了這些工具後就可以輕鬆地翻譯 accumulate 了:

: foldr ( addr init xt -- n )
 rot dup null? if 2drop        ( null list, left init on the TOS and return )
     else over >r              ( store f )
             dup car >r        ( store x )
             cdr -rot recurse  ( exec "foldr f z xs" )
         r> r> execute         ( exec "f x n" )
     then ;

: accumulate foldr ;

這裡參考了 haskell 使用的符號,在每一行後面加上註解,可以對照著 wikipedia 給的範例程式和 accumulate 的 scheme 程式看,對於初次接觸 forth 程式的人應該會有幫助。但要注意的是,這裡只是示範性質的實作,畢竟 forth 的內涵跟 c 一樣是個 stack,遞迴深度過深還是會發生 stack overflow 的。

有了 accumulate 後,原題的平方和就可以很輕鬆地 組裝 出來了:

: square ( n -- n' ) dup * ;
: addsq ( a b -- n ) square + ;
: sum-of-square ( list -- n ) 0 ['] addsq accumulate ;

這裡又可以看到 currying 啦!接著只要丟一個 list 就可以了

create list 1 , 2 , 3 , 4 , 5 , nil ,

list sum-of-square . cr

執行完應該可以看到螢幕上出現答案 55。

以上使用的應該可以在任何一個相容 ANS 標準的 forth engine 執行,我自己用的是 pForthficl。裡面用到的一些基本字用法可以參考以前翻譯的教學

建構出基本工具後就可以來寫 SICP 上的作業了。這個題目希望用 accumulate 實作出 sum 和 product,對於學習過函數式程式語言的人應該都不陌生。用 forth 寫起來會像這樣:

: sum     ( list -- n ) 0 ['] + accumulate ;
: product ( list -- n ) 1 ['] * accumulate ;

把剛剛產生的資料餵進去看看:

list sum     . cr
list product . cr

可以看到螢幕上出現 15 和 120。這裡的 product 其實就是 factorial,但一般會設計成接受一個整數參數,而不是一個 list。不過只要稍微包裝一下 product 就可以產生出 factorial 了:

: scratch ( -- addr ) pad 4 cells + ;
: seq ( n -- addr ) scratch swap 1+ 1 do
 i over ! cell+ loop nil swap ! scratch ;
: fact ( n -- n' ) seq product ;

5 fact . cr

到目前為止除了 foldr 比較長一點,其他都是短短的程式。在 forth 的世界中,一般就是這樣透過基本字來組合來建構出複雜的程式,所以也有人說 forth 就像程式語言中的樂高積木一樣。但要設計出好用、好組裝的積木,就需要經驗了。太大的積木不好用,而且複雜不容易維護,所以重新拆解成更小單元;抽出來的積木不好重複利用,則需要重新分析所有程式的演算法核心性質。仔細一想,這不就是 refactoring 的概念嘛!但對於使用 forth 的人來說,不需要別人推廣也不用特別學習,很自然地就在做這件事,好像古老的技術思維又和現代連結上了,而且一點也不會過時。

進一步思考下去,fold 的出現其實也是在對演算法進行分解後,得到的通用工具。其他還有 map、filter 和 zip 等小工具,就像前面提過的,這些成熟的演算也可以回饋到 forth 程式來使用。其實從以前就覺得 forth 有許多資料和程式實作技巧並不是很透明,也不像主流語言這樣持續發展且容易取得;一方面關注的人也不多就是。雖然對於推廣 forth 不太有興趣,不過從現在的技術中找出連結,引入可用的工具,對於 forth 應該會有全新的認識...吧,我想。