本來預定下一個主題是想聊一下 inner interpreter,結果歪到其他地方去了...

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

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

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

很明顯在 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,導致計算出錯的問題。

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

終於可以來看看 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 ;

來看看兩個條件的情況,執行順序會像是這樣 (省略中間推導過程不然寫不完了):
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 可以順利被組合進來,並且和其他積木合作良好。

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

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

問題來了,這個多出來的 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 和 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 ( )

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

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

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

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

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

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

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

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

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

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

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

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

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

: until
compile 0branch
here - ,
; immediate

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其實只要能理解 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 )
! ( )

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

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

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

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

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

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

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

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

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

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

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

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

Show more
Pawoo

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