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 應該會有全新的認識...吧,我想。

Thursday, February 12, 2009

Line wrap in Emacs

在大部份的編輯器中,對付太長的文字列通常用的是自動換行 (line wrap),就我目前所知,在 Emacs 中有以下幾種不同方式可以選擇:

Line wrap

預設行為即是一般常見的 line wrap。在這種環境下的文字內容並不會被更動,僅在顯示時將超出視窗邊界的部份顯示在下一行,同時在換行處加上一個記號 (如箭頭標示處):

在切割視窗時情況不同:

可以設定一下得到相同行為:

(setq truncate-partial-width-windows nil)

Truncation

打開 truncate line 以後,超出視窗邊界的部份不顯示,同時會在邊界處顯示一個特殊符號作為識別 (與 line wrap 時用的符號不同)。一般適合在寫程式的時候使用

M-x toggle-truncate-lines

也可以寫到 .emacs

(setq default-truncate-lines t)

為了方便可以設個快速鍵:

(global-set-key [f11] 'toggle-truncate-lines)

Filling text

fill 是破壞性操作,會根據 fill-column 的值強制在特定位置插入換行字元。手動操作時只需要按下 M-q 即可,或是乾脆啟用 auto fill:

M-x auto-fill-mode

fill-column

換行寬度可以自行修改,因為設定 fill-column 要求一個數值當作參數,:

C-u 60 M-x set-fill-column

C-u 60 C-x f

fill-prefix

fill-prefix 的內容會自動加到被修改的文字列前面,預設為 nil (代表換行後前面不加任何字)。假設 fill-prefix"... ",則換行後會在該列最前面加上 "... "

設定這個參數可以用 set-fill-prefixC-x .,要注意的是這個動作會將游標所在位置前的同列文字設為 fill-prefix,若在斷行處操作,則整列文字都會被採用。因此我建議透過 eval 方式設定:

M-: (setq fill-prefix "... ")

或乾脆寫進 .emacs

fill prefix 對於整理程式碼註解很有幫助,但對於一般文字也許會造成困擾。要取消 fill-prefix 只需要找個空行再設定一次即可 (minibuf 會顯示 "fill-prefix cancelled")

Long line mode

相較於 fill mode,long line mode 則是溫和的非破壞性操作,只是在顯示上調整成 fill mode 的效果 (soft newline),並不會真的插入換行 (hard newline):

M-x longlines-mode

但顯示與實際內容畢竟有差別,可以將真正的換行處以特殊符號表示以資識別:

M-x longlines-show-hard-newlines

在處理長文字列的顯示上,Emacs 提供了豐富的設定以應付各種需求。就我個人來說,對於一般的文章我習慣用 line wrap 型式顯式;而在編輯程式碼的時候,這種方式反而會破壞縮排的視覺效果,這時改用 truncation 就很適合了。至於 long line mode,我到現在還沒用過。當然,一般編輯程式碼的時候很少會出現超長的程式碼 (也許寫 gtk 程式時例外XD),閱讀上非常不便。非不得已的時候,我會想辦法在 80 columns 內先斷行 (以前留下來的習慣@@),非超出視窗不可的部份,就交給強大的編輯器來處理吧!

Reference

Thursday, February 5, 2009

透過 Outline mode 編輯 Muse 文稿內容

前陣子在使用 muse 撰寫筆記的時候,總覺得要找標題不太方便,似乎也沒辦法透過 speedbar 顯示大綱,玩了半天就想到了 outline mode 這個好東西,剛好語法是一樣的,只要簡單配置一下就可以帶來很大的方便。測試了一下後加了一些設定:

(add-hook 'muse-mode-hook
 '(lambda ()
    (outline-minor-mode t)))

(define-key muse-mode-map (kbd "<f5>")  'outline-up-heading)
(define-key muse-mode-map (kbd "<f6>")  'outline-backward-same-level)
(define-key muse-mode-map (kbd "<f7>")  'outline-forward-same-level)
(define-key muse-mode-map (kbd "<f8>")  'outline-next-heading)
(define-key muse-mode-map (kbd "<f12>") 'outline-toggle-children)
(define-key muse-mode-map (kbd "C-<f12>") 'outline-mark-subtree)

(define-key muse-mode-map (kbd "C-<f5>") 'outline-promote)
(define-key muse-mode-map (kbd "C-<f6>") 'outline-move-subtree-up)
(define-key muse-mode-map (kbd "C-<f7>") 'outline-move-subtree-down)
(define-key muse-mode-map (kbd "C-<f8>") 'outline-demote)

在進入 muse mode 的同時也啟用 outline minor mode,並設定一些快速鍵以便快速在各個標題之間定位。事後在調整內容次序時,還可以整個 subtree 一起調整,不必再笨笨地用 copy & paste 修改了。