はじめに
先日、Lua 関係の調べ物をしていたら、偶然 Eduardo Ochs の "Boostrapping a Forth in 40 lines of Lua code" というページを見つけました。どうやら、この記事は 2008 年に出版された Lua Programming Gems に収められている記事（p.57〜）のようです。
一般的に、言語処理系はある程度の規模となります。小型と言われる Lua でも 2 万 4 千行程ありますし、Python では 7 万行を超えています。もちろん、世の中には１千万行を超えるプログラムも存在しています。また、行数は短いけれども複雑なプログラム・難解なプログラムというのも存在します。それでも、1 万行のプログラムより 100 行のプログラムの方が「読んでみよう」という気にさせます。
Ochs の記事は 40 行で mini-forth と呼ばれるものを作るプロジェクトのようです。Forth の処理系は小規模になることが知られていますが、たった 40 行で基盤部分（コア部分）を作るというのですから、なかなか魅力的です。
とはいうものの、実際の記事を読んでみると、これが結構分かりづらい。もう少し素直に実装できないのだろうか？と思い、Lua で Forth を作ってみようと思いました。
標準 FORTH 的、Lua Forth
「素直に実装」と書きましたが、Lua で Forth を作る場合、どのように実装するのが素直なのでしょうか？ここでは、標準的な Forth 処理系の実装を参考に、Lua での実装を考えてみます。なお、この文書では、参考資料として、井上外志雄の「標準 FORTH」共立出版（1985 年）を主に用いています。
内部インタプリタと外部インタプリタ
素直な実装を考える前に、まずは内部インタプリタと外部インタプリタについて説明します。Forth 処理系において、辞書構造や Forth プログラム（ワード）の実行と密接に関わるのが内部インタプリタで、外部インタプリタは内部インタプリタのドライバ的役割を担っています。そのため、素直な実装を考える場合、内部インタプリタを素直に実装する必要があります。
辞書の構造とワードの格納書式
標準的な Forth では、ワードは次のような形でメモリ中に保存されます。
+------------------------------------------------------------+
|ネーム・フィールド（ワード名の情報） |
+------------------------------------------------------------+
|リンク・フィールド（直前に定義されたワードを指す） |
+------------------------------------------------------------+
|コンピレーション・フィールド（最初に実行される機械語のアドレス） |
+------------------------------------------------------------+
|パラメタ・フィールド（ユーザー定義ワードなどで、プログラムの実態を格納）|
+------------------------------------------------------------+
ワードはリンクフィールドに格納されているアドレスにより、線形リストを構成し、これを Forth では辞書と呼んでいます。Forth プログラムの実行はワードを順次呼び出しつつ行われます。実行するべきワードの検索は、辞書の末尾より先頭にむかって線形探索することにより実現されています。
Lua では連想配列が使えますので、Dict という変数に辞書が格納されているとすれば、Dict["ワード名"] でワードを取り出せます。実に簡単です。よって、リンクフィールドは不要となります。この考え方を推し進めると、ネームフィールドも不要になります。しかし、デバッグの時などに活用できるので、今回は残します。
次に、コンピレーションフィールドについて考えます。今回は間接スレッディングによる Forth を想定しているので、このフィールドには実行される機械語を格納したアドレス値が格納されています。内部インタプリタはこのアドレスを読み、そこへジャンプします。
一方、今回作成する Lua インタプリタでは、機械語（もしくは Lua VM のバイトコード）は取り扱いません。コンピレーションフィールドの役割を考えると、実行すべきコードに関する情報が格納されているだけなので、今回は Lua の関数をこのフィールドに格納します。
最後のパラメタフィールドですが、これは単なる情報の配列です。よって、Lua による実装では単なるテーブルとして実装します。
これらをまとめると、Lua で Forth を実装する場合、ワードは次のように表現すれば、素直な実装と言えるのではないでしょうか。
word={
name="ワード名",
code=function() 実行するコード end,
param={ 格納する様々な値 }
}
例として、 乗算を行うコアワード * を定義し、辞書に格納してみます。
Dict["*"]={
name="*",
code=function()
local a,b=DS.Pop(),DS.Pop()
DS.Push(a*b)
end
}
ワード * には、パラメタフィールドはありませんので、param フィールドは nil です。DS はデータスタックを表し、DS.Push(),DS.Pop() でそれぞれデータスタックへプッシュ、ポップします。
NEXT について
内部インタプリタは伝統的に、コンピレーションフィールドに格納されたアドレスへジャンプすることによりワードの実行を行います。各ワードは最後に NEXT と呼ばれるアドレスへジャンプし、次のワードを実行します[2,3]。
つまり、標準的な Forth の内部インタプリタは、サブルーチンや関数のような形で、ひとつの塊にはなっておらず、ワードとの連携によりその機能を実現しています。Lua には関数外に完全に実行単位を移す機能が error 関数しか存在しません。error 関数を用いて longjunp に相当する機能を実装するのも面白そうですが、その機構を実装すると、おそらく外部インタプリタを含めて 40 行には収まりません。よって、今回は採用を見送ります。
また、NEXT 機能そのものについても、今回は実装せず、コードフィールドに格納されている関数を呼び出すだけです。そのため、各コアワードでも、最後に NEXT を実行する必要はありません。
コアワード以外のもの、つまりコロンにより定義されるものは、そもそも NEXT へジャンプせず、DOCOL、SEMIS をそれぞれ呼び出して、ワード呼び出し・復帰を実現します。そのため、今回作成する内部インタプリタでもこの機構は実現されます。
Lua による Forth の内部インタプリタの実装
以上を踏まえて、内部インタプリタを実装してみます。実行すべきスレッドは IP (Instruction Pointer) にその情報が格納されており、IP が指すワードを順次実行していくだけです。そのため、以下のような 6 行のコードで内部インタプリタを実現できます。
innerInterpreter=function(inThread)
IP={thread=inThread, index=1}
while IP.index<=#IP.thread do
local word=IP.thread[IP.index]; IP.index=IP.index+1; word.code()
end
end
ここでは行数を減らすために、圧縮してコードを書いています。Lua の場合、マルチステートメントが使えるため、行数にあまり意味がないのも事実ですが、本文書作成のきっかけとなった Boostrapping a Forth in 40 lines of Lua code でも似たような感じでコーディングしているので、今回はそれに従ってみたく思います。
使用例
実際にこの内部インタプリタを動かしてみましょう。内部インタプリタだけでは Forth システムは成り立ちませんので、テスト用の辞書を用意します。こちらも行数を圧縮して書いてみました。全 18 行です。
local dataStack,returnStack={},{}
local makePush=function(t) return function(v) table.insert(t,v) end end
local makePop =function(t) return function() return table.remove(t) end end
DS={Push=makePush(dataStack), Pop=makePop(dataStack)}
RS={Push=makePush(returnStack), Pop=makePop(returnStack)}
Dict={}
Dict.Add=function(inWord) Dict[inWord.name]=inWord end
docol=function() local newThread=IP.thread[IP.index-1].param
RS.Push(IP); IP={thread=newThread,index=1} end
readIP=function() return IP.thread[IP.index] end
incIP=function() IP.index=IP.index+1 end
Dict.Add { name="semis", code=function() IP=RS.Pop() end }
Dict.Add { name="lit", code=function() DS.Push(readIP()); incIP() end }
Dict.Add { name="*", code=function() local a,b=DS.Pop(),DS.Pop(); DS.Push(a*b) end }
Dict.Add { name="dup", code=function() local t=DS.Pop(); DS.Push(t); DS.Push(t) end }
Dict.Add { name=".", code=function() io.write(DS.Pop()); io.write(" ") end }
Dict.Add { name="cr", code=function() print() end }
Dict.Add { name="square", code=docol, param={Dict["dup"], Dict["*"], Dict["semis"]} }
ここまでのコードを使って、今回作成した Forth システムを使って、5 の 2 乗を計算して表示してみましょう。Forth プログラムは 5 dup * . cr となりますが、まだ外部インタプリタがありませんので、ハンドコンパイルでスレッドを作る必要があります。最後のワード cr は、改行を行うワードです。計算結果が Lua インタプリタのプロンプトと混ざらないように、追加しています。
ハンドコンパイル時に注意しなければならないのは、数値は直接埋め込まず、ワード lit (literal) をコンパイルし（といっても、Dict["lit"] と書くだけですが…）、その直後に数値を書く必要があります。具体的には次のようなテーブルを作り、innterInterpreter 関数に渡します。
> dofile "innerInterpreter.lua"
> dofile "testDict.lua"
> innerInterpreter {
Dict["lit"], 5, -- 5
Dict["dup"], -- DUP
Dict["*"], -- *
Dict["."], Dict["cr"] -- . CR
}
25
コロン定義のワード
今回作成した Forth システムでも、コロンを使ってユーザー定義ワードを作成できます。参考までに、testDict.lua の最終行にサンプルコードを入れておきました。コロン定義のワードを作るためには、code=docol とし、param フィールドにワードの定義を記述します。param フィールドの最後は semis ワードをコンパイル（配置）すれば、ワード定義完了です。最後に作成したワードを辞書に登録すれば、そのワードの定義完了です。
以下の例では、コロン定義された 2 乗を計算するワード square を用いて、2 * 5^2 を計算してみます。
> innerInterpreter {
Dict["lit"], 2, -- 2
Dict["lit"], 5, -- 5
Dict["square"], Dict["*"], Dict["."], Dict["cr"]
}
50
まとめ
Lua で Forth を実装する場合、どのような実装であれば素直な実装になるのかを考え、ワードや辞書の構造を見直しました。それに基づき内部インタプリタを作成しました。もともとが少ない行数で Forth システムを実装するという記事に触発されて書き始めましたので、本文書でも行数の圧縮を施していますが、Lua のコード 6 行で内部インタプリタを作成できました。
外部インタプリタも既に実装済みで、40 行以内におさまっています。こちらについては次の文書で説明したく思います。
参考文献：
- Boostrapping a Forth in 40 lines of Lua code, Eduardo Ochs, Lua Programming Gems, pp.57-pp.70, 2008.
- 標準 FORTH、井上外志雄、 共立出版、1985
- MOVING FORTH Part 1: Design Decisions in the Forth Kernel, Brad Rodriguez, The Computer Journal No.59, 1993.