本來想在年假期間再寫點什麼,結果搞到最後一天才送走最後一組來訪的親友...

下次來寫點跟 forth 的 inner interpreter 有關的東西好了

其實上次寫的那一串就有沾到邊了,雖然被我包裝成亂七八糟的樣子了...

話說回來,像 forth 這種應該在博物館或古籍中才有機會看到的東西,這年頭還用傳統工法來介紹也不曉得適不適合,網路上也沒有其他人寫的科普文可以作為方向上的參考... 說到底有多少人看到 forth 這個字會有反應的也很難說XD

目前在圈外流傳最廣的文章大概就是 jonesforth 了吧。如果有其他人看過,不曉得看完後的感想怎樣... 我個人來說是不太推薦一開始就去看那一篇

那種寫作方式對 forth 圈來說算是蠻新潮的,forth 圈內比較有系統性整理過的文件本來就不多,再加上大家自己都搞好幾套 forth,適合一起討論的系統不多,大概就是討論一些設計手法吧,拿到沒有文件的系統是常有的事

我當初找的資料大概也都是來自圖書館,forth dimensions 雜誌和新聞群組 (comp.lang.forth) 裡的討論。不小心神到的一些系統,想研究就是乖乖啃原始碼不然就通靈看看...

前幾天提到 jonesforth 後有點懷念,其實之前也只是隨便翻翻看看而已,想說找個時間再來看一下... 結果隨手一滑就看到一個實作問題XD

其實也不能說他錯,但基本上照著傳統做法來做的話,總是會期待要能滿足一些要求,例如要可以用某些 idiom 來寫程式之類的... 然後 jonesforth 的某部份實作好像會破壞相關的 idiom (沒有實測就是...)

我看到覺得有問題的是這一段

git.annexia.org/?p=jonesforth.

有興趣的人可以猜猜這種做法會導致什麼問題... 猜對沒有獎品但可以得到「老古懂」成就

要理解這個問題,或許至少要求用 forth 實作過稍微完整一點的程式,並實作過控制流程才會比較有感覺... 對,forth 的控制流程是可以自己實作出來的,就跟 lisp 一樣

從基本的分支流程結構 if else then、各種迴圈,甚至各種花式流程結構其實都是用 forth 本身實作出來的。實作內容會跟各家 forth 系統結構有關,沒有標準的實作方式,因此我說 jonesforth 的實作會導致一些限制,但也不能說他的做法是錯的。

而在 word set (可以想成基本積木) 的規劃上雖然也是沒有限制,多半還是會參考有在流通的標準,例如 forth-79/forth-83/ans,也就是我前面提到的「傳統做法」。

一般 forth 提供的控制結構,對於有其他語言經驗的人來說應該會不太習慣。例如基本的分支結構看起來像是:
<cond> if <true-part>
[ else <false-part> ]
then

最後的 then 在某些系統或許會改成 endif,但一般還是 then 比較常見。從程式語言語法設計的角度來理解或許會覺得很詭異,但容我再次強調:forth 不是一般意義的程式語言,也沒有像其他程式語言那樣的語法設計,想套用其他程式語言經驗只是找自己麻煩而已。

真的要從程式語言觀點來看的話,要說最接近的大概就是組合語言了 (不過一堆指令的組合算是程式語言嗎?)。實際上有組合語言經驗的人應該能很直覺理解為什麼 forth 的分支結構長這個樣子。先來看看組合語言版的寫法:
test r0
jz else
true-part
jmp then
else:
false-part
then:

對照著前面提到的 forth 分支結構可以很明顯看到兩種寫法幾乎可以直接轉換對應:(沒辦法畫 table 先將就著看)
;; asm forth
test r0
jz else ;; if
true-part
jmp then ;; else
else:
false-part
then: ;; then

以前有說過 forth 比較像是從組合語言中整理出來的某種 eDSL,大概就是這麼來的。

對熟悉組合語言的人來說,用假指令 (directive) 這個詞或許比起 eDSL 較容易理解。一般組譯器都會提供一些方便的假指令來節省開發時間,同時也多半會提供巨集功能以便開發新的假指令。

forth 說起來其實也就是在組合語言之上提供類似的機制而已。

和直接寫組合語言的差別在於 forth 只是一種寫程式的風格與概念,有自己虛擬平台、自己的處理器定義與記憶體布局。再加上處理器的定義簡單,很容易就能在各種真實的處理器上模擬出來,因此一般很常用在沒有標準工具鏈的客製平台。

回頭來說一下轉換的部份。

前面有說 forth 的控制結構也是由 forth 定義出來的,這在一般沒辦法讓你插手 parser 工作與操作 ast 的程式語言中是不容易辦到的。能做到的程式語言我也接觸不多,比較有名的大概就是 lisp 了,這也是 lisp macro 被很多人吹捧的原因之一。

lisp 並不是唯一具備這種能力的語言。forth 則是用了一種更簡單暴力的設計達成同樣目的:把自己變成 macro 就好了。當整個高階部份都是定義出來的,想隨意加入任何變更都只是舉手之勞。

以定義 if 為例,從前面看到 if 對應到組合語言的 jz else,一般在規劃 forth 原語 (primitive,可以想成 forth 處理器的指令集) 的時候,通常會有一個指令叫 0branch,正好對應到真實處理器的 jz 指令。

想想看,一個能讓你隨意操作低階指令的高階語言,自己加入特定結構會有什麼困難嗎?因此要自己定義 if 就簡單了,一般看起來像是這樣:
: if
compile 0branch
here
0 ,
; immediate

(提醒一下這寫法是我流 forth,裡面用到的 word 跟標準有點像但不保證一樣)

想到要解釋這短短的幾行定義其實有點頭痛,因為牽涉到的基礎概念還不少... 雖然我很熟了,但從來沒解釋給別人聽過難免會有漏掉的地方,來挑戰一下能不能講清楚吧。不曉得有多少人會認真看這一串,有看不懂的地方請盡量提出吧

要解識這幾行程式前先說明 forth word 的運作基礎概念。

在 forth 中,任何 word 在設計時都得考慮各種執行情境下要做什麼事。為什麼那麼麻煩呢?前面提到 forth 可以讓你插手 parser、compiler 和 interpreter 的工作,要具備這麼強大的 meta-programming 能力,需要考慮的東西當然不會少。

在 forth 的規格文件或系統文件 (如果有的話),針對某個 word 的說明通常會記載包括 interpretation / compilation / run-time 等不同情境下的運作行為。

當然一般情況只需要考慮 run-time semantics 的設計就足夠了,但在設計控制結構時必須像 lisp macro 那樣能操作 ast,而 forth 沒有 ast 怎麼辦呢?forth 的做法是直階讓你介入 compiler 的工作,允許你定義 code generation 的行為。沒有 ast 給你操作沒關係,你直接告訴我你最後想要什麼就好,大概是這樣的概念。

回到那段 forth 定義,forth 程式的排版基本上沒有限制 (因為沒有語法),所以我展開來一組一組簡單說明:

: \ 起始新定義並進入 compiling 狀態
if \ 命名為 if
compile \ 輸出後面指定代碼
0branch \ 也就是輸出 0branch
here \ 記錄目前的程式位置
\ 也就是 true-part 的開頭
0 , \ 佔位用的,讓 0branch 知道要移動到哪裡的 offset
\ 現在還不知道所以先填 0
; \ 結束定義,回到 interpreting 狀態
immediate \ 這個 word 在 compiling 狀態下要馬上執行 (不會被直接編譯進去)

(字數爆了只好分段寫)

簡單來說,看到 : ... ; immediate 的組合大致可以想成是在定義 compile-time 的行為。順帶一提 immediate 可以放在 if 後面到下一個 : 之間任何一個位置。像我習慣放在 ; 後面,而 jonesforth 則是放在 if 後面

下面是 jonesforth 的實作
git.annexia.org/?p=jonesforth.

寫法跟我的不完全一樣,但做的事其實是一樣的

這樣定義出來的 word,實際上使用和執行時會是什麼狀況呢?

假設有一段程式需要根據某種條件決定要不要工作:
: foo
if
." working" cr
then
;

這裡的 : 如同前面的說明,會進入 compiling 狀態,這個狀態下大部份的 word 都不做事,就是乖乖被編譯器吃進去變成新 word 的韭菜而已,但這當然只是預設情況。當出現了一個能介入 compiler 工作的 if 後狀況就不同了。

這個 if 由於有了 immediate buff 所以突破了 compiler 防線,在這個狀態下也能執行,所以原本預定進行編譯 foo 的流程會在這邊出現插曲:會偷偷插入一個 0branch 和一個 offset 0 進去 foo 裡面,同時會記錄當下的位置 (由 here 負責),*暫時*放到 data stack 裡

這一段有個關鍵是:data stack 雖然一般是 run-time 程式之間交流參數與資料用的,但在 compile-time 也是可以借用一下,只是得保證在編譯結束回到 interpreting 狀態時,原則上 stack 狀態也要還原... 當然這是原則上,不還原通常是有其他目的,這些變化就不在這邊深入了。

而這裡的 if 在編譯期間偷執行,竟然還在 data stack 偷偷留下一個~~孽種~~ here (當下程式位置),到底會掀起什麼波瀾呢?請待下回... 或下下回... 能解開這個謎底就好了XD

順帶一題 ans94 標準建議提供一個 control stack 分開處理,但也因此需要增加用來操作 control stack 的 word,因此若有機會去看 gforth 這類 ans forth 的控制流程實作,大概會看到額外的 control stack 的操作...

不曉得有沒有人覺得怪怪的,既然 提到 if 了,那 else 和 then 怎麼不一起解釋呢?這樣前面舉的範例 foo 也只能講一半不是嗎?

我也知道可能有點怪,但還是想嘗試看看這樣的解釋順序,主要是想強調 if 跟 else 或 then 未必要同時出現。

這個觀念在其他程式語言中大概很少看到。不管是 if / else / then,或是其他如迴圈等控制結構,在 forth 中都是獨立被定義出來的一個 word,只是剛好在某幾個 word 互相組合搭配下可以完成特定的流程控制。

也因此實作控制流程在 forth 中也算是稍微進階一點的議題,主要是需要考慮到這些流程控制積木在動作時帶來的影響要如何管理。再加上這些積木並沒有限制要怎麼搭配,組合出來的情況又更多了,其中只要有積木沒設計好,搭配起來就可能爆炸。

這次看到 jonesforth 中的實作問題就是屬於這一類,會導致某種常見的組合出現問題。如果不會用到會爆炸的組合,那當然就沒問題了,只是一些常見的流程可能就要用其他方式來實作了

Follow

其實只要能理解 if 的實作,那麼其他流程控制的做法應該就能理解了,不過都開了頭還是把 then 也講一下吧。以下是我流的 then 實作:
: then
here over -
swap !
; immediate

(突然發現 if 的解釋有個地方寫錯了,下面解釋時一併修正)

大部份 跟 if 一樣就不多說了。前面的 if 偷偷留下的 here,其實是那個佔位用的 0 的位置,因為 true part 必須寫完才知道 false 時應該跳到哪去,所以這個工作就交給最後出現的 then 來計算。而計算完的 offset 是要回存給 0branch 用的,因此 if 得留下記錄好讓 then 知道要回存到哪裡。

執行的過程如下 (括號中是 stack 狀態,orig 代表 if 留下的位置)
: then ( orig )
here ( orig curr )
over ( orig curr orig )
- ( orig offset )
swap ( offset orig )
! ( )

最後透過 ! 把計算好的 offset 值回存到原本放了 0 的位置,如此一來在條件為 false 時,0branch 就會知道要跳到後面的什麼位置。

前面提到這些流程控制積木可以隨意搭配以產生各種花式流程。事實上這個 then 的用法並不完全只用來搭配 if,而是任何在編譯期間會留下一個位置讓 then 來計算 offset 並回填的 word。

這裡其實點到了 jonesforth 實作問題的第二個關鍵:由於存在其他可能可以跟 then 搭配的 word (先不管組合出來的流程是否符合預期),在 jonesforth 中剛好會在某種流程組合下,讓 then 跟 if 以外的 word 互動,導致計算了不對的 offset 並回存到非預期的位置 (同時也讓另一組搭配出現非預期結果)

基礎知識其實到這邊應該差不多了。

當初在沒人帶的情況下自己亂研究一堆實作,看完也只覺得就是組合語言寫法的封裝版而已。一直到發現控制結構竟然不是像其他語言那樣要求固定型式組合,而是可以隨意搭配後,好像打開新的大門。

其實在高階語言中常見的流程控制結構,從組合語言的觀點來看就是跳來跳去的各種組合而已。一般處理器可能會提供各種花式跳法 (根據各種 flag/status 狀態決定怎麼跳),但在 forth 中基本上只需要對應兩種最基本的跳躍指令:jz 與 jmp,再搭配前面介紹過的簡單堆疊操作,就可以組合出各種流程控制結構了。

前面說明的 if 會在條件為 false (或 0) 的時候往前跳過一段程式,因此基本上只是 jz 的高階封裝:包括直接對應 jz 的 forth 原語 0branch 以及一個數值 offset。而對於 jmp 的處理也有類似的結構,分別是原語 branch 以及高階封裝 ahead。雖然叫 ahead 但基本上是根據 offset 決定怎麼跳,因此往前往後都可以,相當於 c 的 goto 語法。

這個 ahead 就是另一個可以跟 then 搭配的對象。由於是無條件跳躍,除了用在 else 的實作外 (用來直接跳過 false part),也可以用來實作多行註解之類的應用,相當於 c 的 0 ... 結構。

其實在一般的實作中,分支與迴圈等這類常見結構做的事有不少重複,所以與原語之間多半還有一層中間指令,避免需要重覆寫同樣的計算。不過這屬於跟原問題無關的實作細節了,雖然 jonesforth 的實作會導致抽不出中間指令,但不是什麼大問題就是。

開場白有點長,但總算輪到正戲上場了。這個問題的核心其實是迴圈結構的變化組合會出問題,有了開場白瞭解基礎知識後,接下來的說明應該可以加速一下。

其實在理解分支結構的設計後,要再設計個迴圈結構應該也是信手拈來了。在 forth 中的基本迴圈寫起來像這個樣子:
begin
<body>
<cond> until

翻譯成大家比較熟悉的 c-like 語法如下:
do {
<body>;
} while (!<cond>);

這段程式碼的動作大家應該都很熟了,就是執行到某個位置後,根據條件固定回到前面特定位置,反覆執行。

在 forth 裡的實作非常簡單,差不多就是把前面的 if then 倒過來寫而已,差別在於 then 寫到前面的話,計算 offset 的工作得移到後面的 if 來處理了。下面同樣是我流實作:
: begin
here
; immediate

: until
compile 0branch
here - ,
; immediate

如果有實作出前面提到的中間指令,這些高階結構單純就是中間指令的排列組合而已。

除了 0branch 外,另一個 branch 指令也有常見的對應結構:
begin
<body>
again

翻譯以後看起來像這樣:
while (1) {
<body>
}

同樣提供我流實作:
: again
compile branch
here - ,
; immediate

嗯,看起來跟 until 有 87% 像。

正戲開始那麼久,主角 while 總算要登場了。while 出現在另一種常用迴圈結構中:
begin
<body-1>
<cond> while
<body-2>
repeat

同樣翻譯一下:
while (1) {
<body-1>
if (!<cond>) break;
<body-2>
}

就如同在 c 版本裡看到的,while 出現的地方其實隱含了一個 if 的動作,實作也真的就是如此而已:同樣透過介入 compiler 工作的手法,把 while 替換成 if。

將這個結構解碼以後看起來會像是這樣:
begin
<body-1>
<cond> if
<body-2>
again
then

這些都是在前面介紹過的東西。重點來了,這邊其實是兩種控制流程,迴圈與條件分支的基本組合。

在前面的說明可以知道實作控制結構的重點在於計算跳躍指令需要的 offset:透過其中一個指令留下來的路標,讓另一個指令來計算距離。

問題出在 forth 只想用簡單的 stack 來管理這些計算工作的話,怎麼判斷路標是誰留下來的就是關鍵了。

由前面的說明可以知道 begin 和 if 都會留下一個路標,分別讓 again 與 then 計算。而在這種組合中,begin 留下的路標在被用來計算前,stack 中會再放入 if 留下的路標,導致接下來的 again 看到錯誤的路標而做出錯誤的計算:
begin ( mark-begin )
if ( mark-begin mark-if )
again ( mark-begin <-- X )
then

forth 的解決方法很直覺,只要 again 計算時正確取到 begin 留下的路標就好,只要在計算前調整一下順序就能解決問題:
begin ( mark-begin )
if ( mark-begin mark-if )
swap ( mark-if mark-begin )
again ( mark-if )
then ( )

這樣一來大家都能找到正確的路標,產生正確的控制流程。

問題來了,這個多出來的 swap 要讓誰做呢?原本出現在附近的 if 和 again 都不包含 swap 的操作,而且說到底這是 compiler 的工作,一般單純使用迴圈的時候是很難理解到這些 compile-time 運作的,問題還是得在 compile-time 內解決。begin 和 then 都太遠了,只能從 if 和 again 找個倒楣鬼來負責。

嗯,就決定是你了!出來吧〜
: while
compile if
swap
; immediate

: repeat
compile again
compile then
; immediate

在更複雜的迴圈中,可能會出現更多條件判斷來改變迴圈流程,這時原本的 begin ... while ... repeat 就不太夠用了。

在已經看過解碼版程式後,要建構新流程只是小事,當然最理想的狀況還是可以沿用現有的積木,盡量避免一遇到新流程就產生新的積木。

來看看兩個條件的情況,執行順序會像是這樣 (省略中間推導過程不然寫不完了):
begin ( mark-begin )
if-1 ( mark-begin mark-if-1 )
swap ( mark-if-1 mark-begin )
if-2 ( mark-if-1 mark-begin mark-if-2 )
swap ( mark-if-1 mark-if-2 mark-begin )
again ( mark-if-1 mark-if-2 )
then-2 ( mark-if-1 )
then-1 ( )

寫成封裝版的時候就有好幾種寫法了,但為了看起來對稱一點我習慣寫成這樣:
begin
<cond-1> while
<cond-2> while
again
then
then

看起來我流實作的 while 可以順利被組合進來,並且和其他積木合作良好。

終於可以來看看 jonesforth 的 while 實作了。其實經過前面漫長的推導,答案已經很明顯了:

git.annexia.org/?p=jonesforth.

188 : WHILE IMMEDIATE
189 ' 0BRANCH , \ 這三行相當於 if
190 HERE @
191 0 ,
192 ;
193
194 : REPEAT IMMEDIATE
195 ' BRANCH , \ 這三行相當於 again 中間夾一個 swap
196 SWAP
197 HERE @ - ,
198 DUP \ 這三行相當於 then
199 HERE @ SWAP -
200 SWAP !
201 ;

很明顯在 jonesforth 的實作中選了另一個倒楣鬼,把多出來的 swap 交給 repeat 來做。

這在簡單版本的迴圈中是沒問題的,反正 swap 前後各有一個指令,誰做都一樣;但只要在迴圈中多加一個條件判斷:
begin ( mark-begin )
if-1 ( mark-begin mark-if-1 )
if-2 ( mark-begin mark-if-1 mark-if-2 )
swap ( mark-begin mark-if-2 mark-if-1 )
again ( mark-begin mark-if-2 <-- X )
then-2
then-1

只要沒有維持將 begin 留下的 mark 移到 stack 最上面,就會出現讓 again 吃到錯誤的 mark,導致計算出錯的問題。

修正方法應該不必多說,一路看過來的應該都知道怎麼修改了。

花了兩天總算把這個 bug 講完了。

由於這是 compile-time 的 bug,寫程式的時候如果不清楚 forth 原理,單純當成一般程式語言來使用的話,大概很難找出原因,只會發現迴圈老是跳到奇怪的地方。

雖然原本是想看一下有沒有什麼有趣的東西,結果翻了幾行就看到這問題,後面大概暫時不會再看下去了吧。不曉得那麼多人從 jonesforth 做各種衍生版本與移植時,有沒有修掉這個問題?如果只是單純玩玩,而沒有真的拿來開發一些比較完整的應用的話,大概很難踩到吧...

Sign in to participate in the conversation
Pawoo

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!