前言
學 C/C++ 語言的，慢慢進階後大概就會開始學習所謂的資料結構跟演算法。資料結構這裡，一般除了靜態的陣列外，慢慢的會開始學習動態的記憶體配置的技術例如 malloc(), free()... 這些動態記憶體配置跟釋放的指令。再利用這些函數，跟系統要記憶體或用完後歸還記憶體。
老實說，其實最近不斷的在練習跟精進這些 C 語言的技巧。畢盡，這是主要吃飯的工具。但是，這個版是不準備放任何 C/C++ 語言的任何東西的，因為網路上 C/C++ 的素材真的太氾濫了，這種入門等級的，實在無需我們出來浪費網路的資源。
但是，來個 FORTH 語言版本的這種程式碼，倒是十分的樂意！除了讓我更熟悉外，也可以加減推廣 FORTH 語言囉。所以來篇這樣的部落格文吧！
結構體 struct
struct 這個東西其實是很 C 語言風格的，用來在記憶體裡面建構跟堆砌起一些所需的特定資料結構。因為 C/C++ 語言畢盡是個編譯式的傳統語言，所以語法都會希望能像 Pascal 那樣，把資料抽出來，透過抽象化條列清楚。剩下的事就是編譯器的事了。
FORTH 則認為沒有這個必要，假如你對問題了解得夠深入的話，這些都是多餘的。最明顯的例子是 FORTH 的核心組成，詞典，本身就是多線條 Linked List 的資料結構。可是翻開 FORTH 系統的原始碼來看看 (FORTH 的系統本身的構成，大部分也是用 FORTH 語言寫的) 你看不到如 struct 這般的語法結構，可是依舊，系統的 Linked List 組成的詞典可以非常簡潔漂亮兼兼顧未來擴充的彈性。
但是就學習的觀點來看， struct 還是值得去定義它的。因為畢盡目前市面上的所有資料結構的教學書籍，都是以 C/C++ 為主的，如果有 struct 的結構，這時候程式碼才容易互相參考跟了解。同時對於初學者而言，struct 確實可以讓資料結構的使用跟定義呈現得非常的清楚跟易於學習。
所以這裡來仿效 C語言，為 FORTH 定義一些結構體 struct 的指令吧。這樣方便之後為學習目的來練習各種不同形式的資料結構的建立，也當作練功，練功，練功。
FORTH Struct 目標語法
利用三個指令來定義 struct 結構，一個 size@ 指令來取出所定義的結構大小
struct <struct-name>
用來起始 struct 結構的定義，後面接這個 struct 結構體的名稱
item <item-name> ( size --)
用來建構結構體內每個資料結構項目，後面接這個資料結構項目的名稱。前面必須告知這個資料結構項目所需要的大小
end-struct
用來結束所有 struct 的定義
<struct-name> size@
用來取出此完成定義的結構體大小，單位為 bytes.
範例如下，定義一個唱片專輯 Album 的結構體，裏面依序為： 1 cells 大小的 ID 資料項目，20 個 chars 的字串字元 AlbumName 專輯名稱， 1 cells 大小的歌曲數目 #Songs，1 cells 大小的專輯總時間 TotalTime 單位為秒，最後是一個浮點數 1 floats 大小的 專輯價格 price
struct Album
1 cells item ID
20 chars item AlbumName
1 cells item #Songs
1 cells item TotalTime
1 floats item price
end-struct
FORTH Struct 使用方式
我們這個結構體，實際上只是一種 offset 表格，結合了指標變數，它幫我們保存並索引計算 struct 結構體的位置而已，不會真的幫我們保留記憶體空間。
所以要用時，要先指明你的真實資料位於何處。
例如，我們可以把真實結構體建在 FORTH 的字典中
create Pure-HayleyWestenra Album size@ allot
在字典內定義一個紐西蘭美聲天后 Hayley Westenra 的經典專輯 Pure 資料結構體，並以 Album size@ 的大小預留字典空間。
要使用前須先指明，你的結構資料體到底在哪裡？把那個結構資料體的位置變成「現用」
在這個例子，須先將 Pure-HayleyWestnera 設為「現用」的結構體。就很簡單，利用 ! store 將位址存入 Album 中即可。
Pure-HayleyWestenra Album !
這時候 Album ID 就會自動幫我們算出「現用」結構體中， ID 項目的真實位址。
所以將 11223344 的辨識碼放入 Album 結構體中的 ID 位置為
11223344 Album ID !
取出「現用」結構體中， ID 項目的內容為
Album ID @
將價格 350 以浮點數放入「現用」 Album 結構體中 price 的位置
350E0 Album price f!
取出「現用」 Album 結構體中的 price 資料
Album price f@
FORTH Struct 程式碼解說
剛剛解說過語法了，為了打造這樣的語法跟自動幫我們計算每個項目的 offset 位置，所以
: struct ( "name" -- here offset)
create 0 , ( addr0) here
0 , ( size) 0
;
首先， create 會取出 struct 後面的字，在 FORTH 的字典造新詞。這個詞如果被執行的話，會將 Body ，也就是資料區的位址放上來。
0 , 先在 Body 資料區編譯一個 1 cells 的零進來，這個位置放的就是未來指向 struct 結構體的位址，所以它其實是個指標變數。
所以當我們說 Pure-HayleyWestenra Album ! 就會把 Pure-HayleyWestenra 這個結構體的位址存在這裡，把這個結構體當作現用。
接下來， here 將接續的位址先提出來，保存在參數堆疊上。因為這個位址就是接下來另一個 0 , 的位址，用來保存結構體的大小 size 資訊。因為結構體的大小需到最後 end-struct 時才能完全知道的。所以這裡為什麼先填零來預留。同時here 把位址保存下來，直到最後 end-struct 時，完全確定結構體大小後，可以把最終的 size 填到這個位址中。
最後，在堆疊放上 0，當作 offset 的起始。
所以 struct 做了下面的事
1. 造新詞。
2. 為新詞預留兩個空間，第一個空間是個指標變數，用來指向要運作的結構體位址。第二個空間放此結構體的大小， end-struct 結構體定義結束後這個最終的大小就會放到這裡。
3. 在堆疊上放兩個數字，第一個是結構體 size 的位址，給最後 end-struct 時收尾用。第二個是 offset ，給遇到 item 指令時計算偏移量時使用。
: item ( offset size "name" -- offset')
create over , +
does> ( struct-addr offset-addr -- item-addr)
@ swap @ +
;
這個是用來計算結構體裡面每個 item 的記憶體偏移量的。
item-address = struct-addr0 + item-offset
每個 item 的實際位址 = struct結構體的起始位址 + item的記憶體位移量
這個 item 有兩個動作：編譯時的動作跟執行時的動作。
create 如同前面所說的，會將 item後面的字取出來造新詞，這是編譯時的動作。造完新詞後，要記得，根據我們的語法此時堆疊上有三個資料：一個是 here 時所留下 size 的位址，一個是 offset ，最後一個是這個 item 所需要的大小 bytes 數目。
over , 會將目前的 offset 存入 item 所造新詞的 body 資料區中。 之後的 + 就是更新新的 offset' = offset + item-size
根據我們的語法設計，操作 item 時需要這樣
Pure-HayleyWestenra Album ! 先將結構體的位址指出來並存入，
然後 Album ID 就可以得到此結構體特定 item 的位址。
does> 之後，就是執行時的動作。 @ 會將這個 item 的 offset 給取出來。 swap 會把 Album 的位址換過來，這個位址是個指標變數，指向真正結構體的位址。所以 @ 得到真正結構體的位址。
最後的 + 完成了： item-address = struct-addr0 + item-offset
: end-struct ( here offset --)
swap ! ( store size)
;
最後的 end-struct ，直接了當，最後的 offset 其實就是這個結構體的最終大小。所以 swap ! 存入 size 的位址中。
Linked List 結構
除了id, 和 name 字串資料外，重點是需要一個指標變數 'next 指向下一個 Linked List 結構體的節點位址。
所以
struct linkList
1 cells item id
1 cells item 'name
1 cells item 'next
end-struct
資料就一個數字 id, 跟一個 'name 字串指標，指向字串 name 的位址。
動態跟靜態記憶體配置
這裡要再來說明一下的，一般而言，假如一個程式在執行的時候，所有的記憶體位置跟變數位置，大小，都是確定的，不會再更動了，這種叫做靜態記憶體配置。但是假如程式在執行的時候，所使用的資料，變數，陣列，字串，... 都是隨著當時的需求，不斷地被配置，回收，配置，回收... 這種的過程叫做動態記憶體配置。
在 C語言裡面， 使用者利用 malloc(), free(), realloc() ... 這幾個函數來跟系統要求配置記憶體跟釋放或是重新配置記憶體，C++ 用的是 new/delete。至於像 python, java, ... 這類的語言，動態記憶體配置是系統內建的，使用者無需操心。
在現今的語言中，動態記憶體配置，幾乎已經是像呼吸空氣一樣，必備的了。但是要謹記，有得就有失，動態記憶體配置，真的是需要的嗎？這答案倒是未必！
舉例來說，動態記憶體配置，有下列的缺點。
- 記憶體配置的過程中，這不是免費的，系統需要浪費時間幫你尋找可用的記憶體空間跟位置給你。假如是非常頻繁地不斷配置，跟釋放記憶體。這將大幅的降低程式的效能。
- 頻繁的配置，釋放的過程，很容易造成記憶體碎裂化。最後系統可能要花大量的時間垃圾收集跟重整記憶體，而造成效能的低落。假如是即時控制，突然無法預期的系統記憶體重整，立即拖垮了即時系統所最需要的精準時間反應。
- 假如系統配置給你的記憶體指標處理不當，該歸還未歸還，甚至是丟失了。最後就是一堆 Memory Leak 記憶體洩漏，最後變成不穩定的程式碼整個崩潰掉囉。軟體的可靠度變成非常有問題的呢！
有種種的缺點，所以基本上 FORTH 本身最早被發明出來的時候，是不用這種方式的。 FORTH 喜歡的方式，主要是靜態記憶體配置，也就是在編譯時，所有記憶體的使用位置就確立了。
因為這樣的方式， 也使得 FORTH 語言所撰寫出來的程式碼，具有高度的可靠度。沒有 Memory Leak 那些煩人的問題，也不會犧牲效率，在那邊配置記憶體，又釋放記憶體的。浪費時間。
那彈性呢？
FORTH 本身就是交談式的環境，本身就是ㄧ個作業系統。例如現在想做 1000 個元素的矩陣運算，很簡單的 create Array-Data 1000 floats allot 這幾個指令，系統立刻就以靜態的方式在 FORTH 的字典奉上 1000 個浮點數字空間給你。你可以自由地拿來做運算，用完了再 forget 還回去就好(或用 marker 的方式來清空字典的空間)。
在 FORTH 的系統下 malloc(), free(), realloc() 這種動態的記憶體管理方式，其實是看不出有任何優點的。
筆者在前前公司也接觸過用 FORTH 來控制 ion implanter 的大型程式專案。數十萬行的程式碼，裡面全都是靜態的方式來管理所有的記憶體，不但沒有什麼困難，而且也得到絕佳的軟體穩定度。
但是，因為現代的 FORTH，也逐漸地無法像以前一樣，一個系統吃天下，而是要跟其他的作業系統共存。現今的作業系統，還是以 malloc(), free()... 這種架構的方式來靈活的使用記憶體。所以 ANSI FORTH 標準，還是制定了 allocate, free, resize 這三個動態記憶體配置的指令的規範，來銜接現今作業系統對動態記憶體管理的方式。
我們的 gFORTH 完全符合規範，有支援這三個指令。所以我們可以利用這幾個指令，寫出非常 C-Like ，一般資料結構課程裡的動態 Linked List 結構囉。
雖然是不太經典 FORTH 的風格，但也順便來練習一下動態記憶體配置的技術囉！
ALLOCATE ( u -- a-addr ior)
跟系統要求 u bytes 的記憶體，回傳所配置的記憶體位置 a-addr，跟成功與否的 ior。成功的話 ior 為零，非零的話為失敗，且其值為 error-code。
FREE ( a-addr -- ior)
跟系統歸還之前所配置的，位於 a-addr 的記憶體。成功的話 ior 為零，非零的話為失敗，且其值為 error-code。
所以，要配置我們的 linked List ，程式碼為
: allocElement ( --)
linkList size@ allocate throw
linkList !
;
linkList size@ 取出 struct 資料結構的大小， allocate 要求系統配置記憶體， 假如 ior 不為零的話， throw 會將拋出去給外層的 error-catcher 錯誤處理函式去捕捉跟錯誤處理。 沒錯誤的話將被配置到的位址 linkList ! 存入 linkList 裏的指標中當作現用，以提供給後續使用。
Linked List 的處理
這裡我們先定義兩個指標變數 'tail 跟 'prev
'tail 永遠指向我們的 list 結構的尾巴節點。 (你要說它是頭，也可以的) 所以當要走訪 list 裡的所有節點時，一切從這裡開始。
'prev 則是用在走訪 list 節點時，當找到特定元素時， 'prev 會指向上一個 list 節點的位置。這樣，當我們要刪除特定 list 節點，或插入 list 節點時，這些節點連接的修復跟建立，會變成非常的方便。
對於這兩個指標變數，因為是來標誌 list 結構位置的，所以採用 value 的方式來定義變數，這樣會比較清楚。然後跟 C的用法一至， 內容0的時候可視為 null，代表沒有值。
所以
0 value 'tail
0 value 'prev
接下來來定義一下，如何將新元素附加到 list 裡面呢？
: appendElement ( --)
'tail linkList 'next !
linkList @ to 'tail
;
假定，現用的 list 元素位置存在 linkList 結構體中。我們想把這個現用的 list 元素，加入 list 的鏈結裡面。
因為 'tail 指標變數會指向我們 list 的尾巴節點啊 (你要說這是頭也可以，我自己習慣後面加進來的節點叫尾巴)。 所以把現在的 list 元素的尾巴(最後一個節點的位置)，放到現用 list 結構體的 'next
然後再更新現用的 list 元素節點位置放到指標變數 'tail 中，這樣加進去就收工囉！
要如何走訪 list 元素呢？
: nextElement ( --)
linkList 'next @ linkList !
;
從現用的 list 結構體中的 'next ，取出所連結的下個節點。把它變成現用的 list 結構體，這樣就走訪至下個節點囉。
如何尋找特定 id 的 list 元素呢?
: searchID ( id --)
0 to 'prev
'tail linkList !
begin linkList @ ( not null?)
while linkList id @ over =
if drop exit then
linkList @ to 'prev
nextElement
repeat drop
;
先將 'prev 上個元素節點位置變成 null，然後把 'tail 所指的節點位置變成現用 list結構體。
跳到 while-repeat 迴圈，假如現用list結構體不是 null 的話，檢查一下現用 list 的 id 是不是我們要的？ 是的話就找到囉，直接 exit 離開囉。不是的話就是要繼續走訪下個元素節點，先將現在的元素節點位置放到 'prev，然後 nextElement 走訪下個元素節點。
最後什麼都沒找到的話現用 list 結構體的位置會是 null，離開迴圈。
可以找尋特定元素了，所以現在我們可以開始真的來加資料囉！
: newElement ( id 'name --)
over searchID
linkList @ ( found?)
if linkList 'name ! drop
else allocElement appendElement
linkList 'name !
linkList id !
then
;
給定 id, 及 name 字串的位址。將這筆資料加入 list 鏈結中。
首先先 searchID，找看看是不是資料其實已經存在了。如果現用 list 結構體位址不是 null， 那就是找到了。所以只要簡單的把 'name 字串的位址以新的位址取代就好。
如果現用 list 結構體位址是 null， 那就是沒有在 list 鏈結中，可以放心的 allocElement 跟系統要個新的 list結構體的空間，然後 appendElement 把它連進 list 鏈結裡面。然後把 name 字串位址資料， id資料放進去新要到的空間中。
刪除資料，那當然沒問題的！
: deleteElement ( id --)
searchID
linkList @ ( found?)
if linkList 'next @ ( save 'next to stack!)
linkList @ free throw
'prev ( not tail element?)
if 'prev linkList !
linkList 'next !
else to 'tail then
then
;
先 searchID 找看看資料是不是存在，不存在那當然什麼事都不用做。
如果找到了，找到的 list 元素節點位置會放在現用的 list 結構體，所以先 linkList 'next @ 取出它下一個元素節點的位置，放在參數堆疊暫放一下。
linkList @ free 來把現用 list 結構體的空間釋放出去！
檢查一下 'prev ，如果它不是 null ，那我們可以把上個元素節點變現用，然後把剛剛放在堆疊上，下一個元素節點的位置存入 'next，這樣新的連結就被修復囉。
如果 'prev 是 null，表示找到要刪除的現用 list 其實是最後一個元素節點 (尾巴 'tail)，所以只要把 'tail 指向剛剛堆疊上所存放的，下一個元素的節點位置，這樣就收工啦。
最後，很重要的，走訪 list 連結裡的所有元素，並列印它們的所有資料
: printAll ( --)
'tail linkList ! cr
begin linkList @ ( not null?)
while linkList id @ ." id = " . cr
linkList 'name @ ." name = " count type cr cr
nextElement
repeat
;
一切從 'tail， list 連結的尾巴節點開始。所以先把它變成現用。
然後 while-repeat 迴圈，只要現用 list 結構體節點位址不為 null 零，那就取出 id, name 字串來做列印。 列印完畢後 nextElement 走訪下個 list 元素節點。
結果測試
先建立所要用的靜態字串
create frank ," Frank Lin"
create sean ," Sean Lin"
create lydia ," Lydia Lin"
create gary ," Gary Hung"
然後用 newElement 來依序建立 list 元素跟他們的連結
111 frank newElement
222 sean newElement
333 lydia newElement
444 gary newElement
printAll 可以訪問所有的 List 元素的節點並印出內容
333 searchID 搜尋 ID = 333 的元素節點，取出並印出它的名字內容
222 deleteElement 刪除 ID = 222 的節點
運作非常完美
原始程式列表
\
\ Linked List
\ 2022.10.24 Frank Lin
\
\ struct
: struct ( "name" -- here offset)
create 0 , ( addr0) here
0 , ( size) 0
;
\ struct structure
\ body: | addr0 | size |
\
: item ( offset size "name" -- offset')
create over , +
does> ( struct-addr offset-addr -- item-addr)
@ swap @ +
;
\ item structure
\ body: | offset |
\
: end-struct ( here offset --)
swap ! \ store size
;
: size@ ( struct-addr -- size)
cell+ @
;
\ define a offset table for struct
struct linkList
1 cells item id
1 cells item 'name
1 cells item 'next
end-struct
0 value 'tail
0 value 'prev
: allocElement ( --)
linkList size@ allocate throw
linkList !
;
: appendElement ( --)
'tail linkList 'next !
linkList @ to 'tail
;
: nextElement ( --)
linkList 'next @ linkList !
;
: searchID ( id --)
0 to 'prev
'tail linkList !
begin linkList @ ( not null?)
while linkList id @ over =
if drop exit then
linkList @ to 'prev
nextElement
repeat drop
;
: newElement ( id 'name --)
over searchID
linkList @ ( found?)
if linkList 'name ! drop
else allocElement appendElement
linkList 'name !
linkList id !
then
;
: deleteElement ( id --)
searchID
linkList @ ( found?)
if linkList 'next @ ( save 'next to stack!)
linkList @ free throw
'prev ( not tail element?)
if 'prev linkList !
linkList 'next !
else to 'tail then
then
;
: printAll ( --)
'tail linkList ! cr
begin linkList @ ( not null?)
while linkList id @ ." id = " . cr
linkList 'name @ ." name = " count type cr cr
nextElement
repeat
;
\ define strings
create frank ," Frank Lin"
create sean ," Sean Lin"
create lydia ," Lydia Lin"
create gary ," Gary Hung"
\ build list elements
111 frank newElement
222 sean newElement
333 lydia newElement
444 gary newElement
Xxx
留言列表
