Pages

Saturday, October 29, 2011

Extending Gforth with the Code Word

很久沒發文了,但一直都有記錄筆記的習慣,原本也是打算整理好發表的,但常常寫到一半就去做其他事了,所以積了不少未完成的稿XD 這次出清一篇筆記,來談談 forth 中的 code word。

一般對於 forth 系統的擴展有兩種方式,最方便的當然是定義新的 colon word,另一種則是實作比較低階的 code word。

code word 代表的是低階實作,也就是直接跟底層平台對話。以 lisp-based forth 為例,其實就是把 lisp vm 當作(虛擬)硬體平台,因此 code word 作用大概就是產生一堆 lisp form,而 x86 native forth 當然就是產生 x86 machine code 了。

簡單地說,code word 需要負責兩件事:

  • 產生 native code
  • 讓 forth 可以順利執行這些 native code

產生 native code 的工作通常會由一個 target assembler 負責。這也是為什麼一個完整的 forth system 多半會提供自己的 assembler。雖然 forth 已經是可擴展的設計,但在需要直接操作宿主平台時,可能會需要寫成 code word 比較方便。

比較麻煩的是第二點,讓 forth 可以順利執行的關鍵在於不能干擾系統運作。forth 本身雖然是 stack vm,但還是有幾個基本的暫存器,一般在 x86 上會對應到實際的暫存器。依照實作模型的不同,可能會需要佔用 2 至 5 個不等。在 code word 中必須妥善管理這幾個暫存器,不是單純 pushapopa 就可以解決的。最常見的狀況,就是維護 SP 的值 (forth 中的 SP 暫存器,非 x86 的),確保參數可以正常傳遞,不會發生 underflow;以分支指令來說可能需要修改 IP 的值,只要改錯暫存器就會發生災難。因此第一步就是找出這幾個暫存器的對應關係。

在一般的 forth 系統中,通常會提供一個叫做 see 的 disassembler,可以透過它來猜出系統的規劃。Gforth 套件提供了好幾種實作,由於接下來的實驗在不同實作中會有不同結果,為了方便解說只使用 gforth-fast。在 Gforth 中,第一個建議觀察的是什麼事都不會做的 noop

see noop
Code noop
( $804B1BF )  add     esi , # 4  \ $83 $C6 $4
( $804B1C2 )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804B1C5 )  mov     eax , ebx  \ $89 $D8
( $804B1C7 )  jmp     804B03C  \ $E9 $70 $FE $FF $FF
end-code

從這邊可以猜到不做事的時候,系統大概會使用 eaxebxesi,然後跳到某個位址繼續執行。因此觀察其他 word 的時候就可以先去除這幾個動作,找出真正關鍵的操作。接下來建議的是 dupdrop。這兩個 word 是基本的堆疊操作,可以直接找出 SP 在哪,甚至可以看出是否有加入 TOS (Top Of Stack) 的快取設計,也就是將 TOS 放在特定的暫存器以減少一次記憶體操作。

see drop
Code drop
( $804C836 )  add     edi , # 4  \ $83 $C7 $4
( $804C839 )  add     esi , # 4  \ $83 $C6 $4
( $804C83C )  mov     ebp , dword ptr [edi]  \ $8B $2F
( $804C83E )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804C841 )  mov     eax , ebx  \ $89 $D8
( $804C843 )  jmp     804B03C  \ $E9 $F4 $E7 $FF $FF
end-code

drop 的內容可以看到除了 noop 以外,還操作了 edi,沒有意外的話 SP 就是它了。同時也知道堆疊往低位址成長 (因為 drop 相當於做了一次 stack pop)。作為佐證可以再觀察一下 dup,應該會看到減少 edi 內容值的運算:

see dup
Code dup
( $804C85D )  sub     edi , # 4  \ $83 $EF $4
( $804C860 )  add     esi , # 4  \ $83 $C6 $4
( $804C863 )  mov     dword ptr 4 [edi] , ebp  \ $89 $6F $4
( $804C866 )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804C869 )  mov     eax , ebx  \ $89 $D8
( $804C86B )  jmp     804B03C  \ $E9 $CC $E7 $FF $FF
end-code

看起來的確有移動 edi 內容的操作。另外還看到奇怪的動作,把 edp 的內容搬進 stack top - 1 的位置,並不是移動到 stack top,推測 可能有 TOS 的設計。

要證實這一點,可以再看一下 swap+ 這幾個會影響 TOS 的 word。

see +
Code +
( $804B918 )  add     ebp , dword ptr 4 [edi]  \ $3 $6F $4
( $804B91B )  add     esi , # 4  \ $83 $C6 $4
( $804B91E )  add     edi , # 4  \ $83 $C7 $4
( $804B921 )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804B924 )  mov     eax , ebx  \ $89 $D8
( $804B926 )  jmp     804B03C  \ $E9 $11 $F7 $FF $FF
end-code

看來的確是把運算後的結果 (TOS) 直接放到 ebp 了,而不是放在記憶體中。拿到 SPTOS 後就可以試著增加一個 code word 看看了。首先用最簡單的 dup 操作來驗證前面的猜測,實作一個有相同操作的 _dup

code _dup
    bp di ) mov
    4 # di sub
    next
end-code

3 _dup .s

可以看到堆疊中的確出現兩個 3 了。不過看起來自己實作的 _dup 好像比原版的 dup 還要精簡一點。另外也可以寫個 _+ 看看:

code _+
    4 # di add
    di ) bp add
    next
end-code

2 3 _+ .s

結果也正確無誤,留下一個 5。到這邊已經可以做很多事了。不過偶爾可能會需要 RP,所以從 >r 找到 RP 放在記憶體的某處。查找的過程不再列出,同樣複製一個相同的 _>r 來驗證看看:

code _>r
    4 # $3c sp d) sub
    3c sp d) bx mov
    bp bx ) mov

    4 # di add
    di ) bp mov
    next
end-code

為了維護 return stack, >rr> 通常要平衡使用才不會破壞系統運作,所以我將自己實作的 _>r 搭配系統的 r> 一起使用,測試過可以正常執行。

除了這幾個重要的暫存器外,還有一個 IP,可以透過觀察 branch 找到,這裡就不再贅述了。不過還有一件重要的事需要特別提出來討論。在整理這篇筆記的過程中,我發現一個嚴重的問題:以前實驗的結果,在 0.7.0 版的 gforth-fast 可以正常運作,但換成 0.7.9 版卻無法動作,後來試了一下 0.6.2 也同用無法執行。查了文件才知道原因在於 c compiler 版本。由於不同版本的編譯器執行 register allocation 結果可能不同,會產生出完全不一樣的 forth vm,這點是特別要注意的。前面列出來的結果是在 gcc 4.4.4 建立出來的 gforth-fast 0.7.9 的環境重新實驗的。如果使用到的暫存器剛好都是自由的 (不被系統使用),換系統時就不需要再調整程式了。

雖然聽起來有點糟,但對我來說也不算什麼大問題就是了。畢竟 forth 在各系統間的相容性本來就不能期待,會想使用 code word 的人大概對正在使用的系統也有一定的掌握能力了,這樣程度的相容性問題應該都有能力處理。


會翻出這篇筆記,主要是看到有人做了一個 benchmark,gforth-fast 需要的時間是其他 forth 的好幾倍,想試試把幾個關鍵處改寫成 code word,看有沒有機會加速。最後實驗的結果是... 不行!

囧rz...

非但沒變快,反而更慢了XD 也許 Gforth 在切換成 code word 可執行環境時做了很多事,因此效能不如全部都使用 colon word;也許是 instruction miss 等原因造成的吧。這個一時興起的實驗提醒了我在選系統時要記得同時測試一下 code word 的使用,暫時還是先把 Gforth 的 assembler 當作 cross assembler 使用吧。

Friday, April 22, 2011

VOCABULARY in Forth

最近找了一些 Forth 的舊文章來看,也看了一些舊程式碼。在這些資料中發現很多以前沒學會的東西,正好趁這機會補習一下。這次要介紹的是 Forth 裡的 VOCABULARY

如果對 Forth 有一點瞭解,或者看過我以前翻譯的 PForth 教學,應該會知道 Forth 中的每一個執行單位叫做 word。相對於其他程式語言來說,就像是函式那樣的東西。Vocabulary 的意思是「詞彙」,簡單的說就是 word 的集合。更進一步,大概就像是 Library 的設計。

以上是我一直以來對 Vocabulary 的理解。以前我還在念書時,想找個程式語言來學,卻糊裡糊塗入了 Forth 坑。但當時 Forth 並不是主流,不但買不到書,也找不到人教,很多東西就這樣斷章取義,隨意理解了。等到實際要用時才知道問題大條,趕緊花了點時間玩一下,原來誤會了那麼久的東西,其實是那麼簡單又強大的設計。

其實 Vocabulary 除了 Library 的功能之外,更重要的功能其實是 Namespace 的控制。

Forth 的核心設計有幾個重要的基礎元件,其中的 Dictionary 用來存放資料與新定義的 word。Vocabluary 可以將 Dictionary 中的 word 分組,並影響後續使用的搜尋順序。用比較現代一點的說法,其實就是 Namespace 與 Scope 機制。以下會簡單介紹一下 Forth 的 Vocabulary 設計與運作方式,參考資料來源是 GForth 附的程式碼與實驗結果。

在 Forth 系統誕生之時會提供一個最基礎的 Namespace,在這個 Namespace 裡就只有最基本的 Namespace 定義與管理工具,連基本的堆疊運算辦不到。以 GForth 為例,這個最基本的 Namespace 叫做 Root,只提供了 5 個 word:

order set-order forth-wordlist Forth words

其中比較重要的是 ORDERFORTH 這兩個 word。 ORDER 的作用是列出目前作用中的 Namespace,以及目前的定義空間; FORTH 是一個 Vocabulary,裡面定義了撰寫 Forth 程式會使用到的 word。先來看看 ORDER 的結果,在 GForth 中輸入 ORDER 會印出:

Forth Forth Root     Forth

這串訊息要分成三部份來看:

  1. 最左邊的 Forth:代表目前作用中,搜尋順序最高的 Vocabulary。依照以前的術語,這個位置代表 CONTEXT Vocabulary
  2. 最右邊的 Forth:代表目前的定義空間,所有新定義的 word 將會加入 Forth 這個 Vocabulary 中。依照以前的術語,叫做 CURRENT Vocabulary
  3. 中間的部份:一個 Vocabulary 清單,代表目前的搜尋順序。當系統在 Context Vocabulary 中找不到要執行的 word 時,就會依照這邊的順序一個一個找下去

以這個顯示結果來說,在 C++ 看到的可能是:

using namespace Root;
namespace Forth
{
  ...
}

這三個部份都是可以隨意改變的。在 Forth 中,每個 Vocabulary 其實也是一個可執行的 word,執行後的動作就是更新 Context Vocabulary。Forth 允許兩個同名的 word 定義在同一個 Vocabulary 或不同 Vocabulary。定義在同一個 Vocabulary 時,只會搜尋到最後定義的 word;而定義在不同 Vocabulary 時,就是靠 Context 決定會找到哪一個。

舉個簡單的例子來說明。假設我有 A 和 B 兩個 Vocabulary,其中 A 定義了兩個 foo:

: foo ( -- )
  ." in a" cr
  ;

: foo ( -- )
  ." in a (2)" cr
  ;

B 也定義了一個同名的 foo

: foo ( -- )
  ." in b" cr
  ;

假設我想執行 A 裡面的 foo,必須先切換 Context 到 A:

\ Set Context
A  ok

\ Exec foo
foo in a (2)
 ok

可以看到真正執行的是最後定義的 foo。若想執行 B 裡面的 foo,同樣也要先切換 B:

B  ok
foo in b
 ok

除了切換 Context 外,其他兩個部份也可以隨意設定。但在介紹方法之前得先引入幾個小工具。Forth 對於整個 Vocabulary 的管理提供了幾個小工具。比較重要的有 VOCABULARYONLYALSODEFINITIONS

VOCABULARY 可以建立新的 Vocabulary。以剛剛的例子來說,建立 A 與 B 的方法是:

vocabulary A  ok
vocabulary B  ok

ONLY 的意思是只搜尋 Root 這個 Vocabulary。在 GForth 中可以看到 ORDER 的結果是:

only  ok
order Root Root     Forth  ok

可以看到去除左右兩個 Vocabulary 後,中間的搜尋清單只剩下 Root。

ALSO 的意思是說,將目前的 Context Vocabulary 加入搜尋清單。加入以後,不管 Context 怎麼變動,都可以不受影響。以前面的例子繼續實驗。我把 A 加入搜尋清單後,再改變 Context,看看是否可以找到定義在 A 的 foo:

only forth also \ reset search list
A also          \ add A to search list
forth           \ set Context

\ current environment
order Forth a Forth Root     Forth

\ exec foo
foo in a (2)
 ok

看來的確可以自由配置搜尋清單。

最後一個是 DEFINITIONS,用來決定新定義的 word 該屬於哪一個 Vocabulary,執行後會把 Context Vocabulary 設定到 Current Vocabulary。以前面的例子來說,我想在 A 裡面定義一個 foo,可以這樣做

A definitions
: foo ( -- )
  ." in a" cr
  ;

Forth 的 namespace 設計很簡單,卻威力強大。只加了這幾個工具就可以產生一些好玩的應用。舉例來說,為了 debug 方便,我會在 word 定義中加上一些 log 訊息。有時候跑一次程式後再檢查 log 會比進入 debugger 有效率得多。例如:

: foo ( -- )
  \ ." >> enter foo" cr
  ." exec foo" cr
  \ ." << exit foo" cr
  ;

比較麻煩的是加了 log 就得移除,需要一直修改程式。利用 Forth 的特性,我可以在不同的 Vocabulary 設計一組外掛用的 wrapper word,專門用來顯示一些 log 訊息:

vocabulary tool
tool also definitions
: foo ( -- )
  ." exec foo" cr
  ;

vocabulary tool-debug
tool-debug definitions
: foo ( -- )
  ." >> enter foo" cr
  foo
  ." << exit foo" cr
  ;

可以看到我在 debug 用的也是同名的 foo,但因為定義在不同 Vocabulary,所以不會互相干擾。在一般情況下我可以正常地執行 foo:

only forth also definitions tool  ok
foo exec foo
 ok

需要追蹤執行流程時,就將新工具外掛進來

tool-debug  ok
foo >> enter foo
exec foo
<< exit foo
 ok

不需要 log 的話可隨時換回正常版的 foo。

雖然很容易就做到這樣有趣的效果,但其實這只是簡單的示範而已, 並不具太大的實用價值。要達到比較實用的程度,可能得搭配 Forth 的 DEFER word 機制,將 log 輸出功能設計成一個可抽換的 policy word,並在執行前決定要設置成哪一個 policy1。運作起來類似 late binding 的效果。

Forth 這麼古老2的東西 (其實不比 Lisp / Fortran 晚多少喔),竟然連 Namespace 管理機制都設計進去了,以現代程式語言的角度來看還真是一點都不退流行阿!而且 Forth 流行的時代,其實主要做一些硬體控制的工作,有複雜到需要加入 Namespace 機制嗎3?在那個高階語言都還不太流行的年代,天曉得這些前輩高人們怎麼想到的?


1. 應該很多人猜得到這是從哪本書借來的點子

2. 想瞭解 Forth 的誕生,可以參考 Forth - The Early Years (中譯) 這篇文章

3. 事實上就是有這個需要,希望以後有機會能介紹到這部份

Wednesday, February 16, 2011

Test post for source code

測試透過 emacs + muse 將程式碼發表到 blogger 上

隨便一段 python 程式

import os
import hashlib

dupes = {}

for path, dirs, files in os.walk(os.getcwd()):
    for file in files:
        filename = os.path.join(path, file)
        hash = hashlib.sha1(open(filename).read()).hexdigest()
        if hash in dupes:
            print 'linking "%s" -> "%s"' % (dupes[hash], filename)
            os.rename(filename, filename + '.bak')
            try:
                os.link(dupes[hash], filename)
                os.unlink(filename + '.bak')
            except:
                os.rename(filename + '.bak', filename)
            finally:
        else:
            dupes[hash] = filename

同場加映 perl source listing

#!/usr/bin/perl -w
use Digest::MD5 qw(md5_hex);
use Digest:SHA1 qw(sha1_hex);

if (@ARGV !=1)
{
    print "Usage: perl $0 <word to encrypt>\n";
    exit;
}
($var) = @ARGV;
print "\n$var (MD5)" . " : " . md5_hex("$var")."\n";
print "$var (SHA1)" . " : " . sha1_hex("$var")."\n";
void swap(int *a, int *b)
{
  int t=*a; *a=*b; *b=t;
}
void sort(int arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}