はじめに
前回の文章、「6 行の Lua プログラムで、Forth の内部インタプリタを作る」では、内部インタプリタを作成しました。作成した内部インタプリタの動作確認として、実際の Forth プログラムを実行させましたが、ハンドコンパイルする必要がありました。
今回は外部インタプリタを作成します。これにより、ハンドコンパイルは不要となります。また、外部インタプリタを eval として、read-eval-print-loop を構成可能です。
追記：ソースコードを GitHub（https://github.com/iigura/tinyLuaForth）に置きました。興味のある方は実際に動かしてみて下さい。
注：当初は「35 行の Lua プログラムで Forth インタプリタを作る（内部インタプリタ 6 行、外部インタプリタ 29 行）」というタイトルで掲載しておりましたが、トークンの評価順序が一般の Forth とは異なっていました。今回はそれを修正しました。結果、外部インタプリタが 3 行増加し、合計 38 行となりました（ただし、辞書の方は見直しを行い、30 行から 2 行減って全 28 行となりました）。関連して、トークンの評価順序に関する部分についての記述も修正しました。その他、説明不足な部分についても文章を追加し、誤字脱字等の修正も行いました。
外部インタプリタの仕事
外部インタプリタには 2 つのモードがあり、それぞれのモードで実現すべき機能が異なります。ひとつはインタプリタモードで、これはワードを起動する等して、計算などの処理を実行するモードです。もうひとつはコンパイルモードで、ワードの定義などはこのモードで実施されます。
インタプリタモードで行うべきこと
インタプリタモードでは、入力された文字列（トークン）により、以下のいずれかの処理を行います。
- 登録済みのワードと同名の文字列であっとき： その文字列をワード名とし、該当ワードを検索・実行します。
- 同名のワードがない場合： 数値として解釈することを試みます。数値であると判断された場合には、その値をデータスタックにプッシュします。
- それ以外の場合： 未定義のワードとしてエラーを出します（が、この場合どのように処理するのかは各処理系に委ねられています）。
例えば、 5 dup * . という文字列が入力された場合は、
| トークン | スタック | 説明 |
|---|---|---|
| 5 | 5 というワードは存在せず、数値として解釈できるのでスタックに積む | |
| dup | 5 | "dup" というワードを探して実行する（＝スタックトップを複製する） |
| * | 5 5 | "*" というワードを探して実行する（＝スタックの上から 2 つ取り出し、それらの積をプッシュする） |
| . | 25 | "." というワードを探して実行する（＝スタックトップの値を表示する） |
と処理され、最終的に 25 という数値が画面に表示されます。
コンパイルモードで行うべきこと
コンパイルモードでも、トークンの解釈の順序はインタプリタモードと同じです。しかし、コンパイルモードでは、それらのワードや数値を実行したりスタックに積むのではなく、現在コンパイル中のワードのパラメタフィールドに、コンパイルした結果を順次書き込んでいきます。具体的には、以下の処理を行います。
- ワード名が入力されたとき：そのワードがイミディエイト属性（即時実行特性）を持つならば、そのまま実行し、そうでなければ、該当ワードへのポインタをパラメタフィールドの末尾に配置します。
- 数値が入力されたとき： ワード "lit" をコンパイルし、その直後に該当の数値を配置します。
例として、 : square dup * ; という文字列を処理してみます。外部インタプリタはインタプリタモードにて起動するため、最初は ":" というワードを実行することとなります。
":" を実行すると、
- 新しいワードの領域が作成され、
- 処理系へ入力された文字列から次のトークンを読出し、それをワード名として設定し、
- そのワードのコンピレーションフィールドに docol を設定し、
- コンパイルモードへと移行、
します。
あとは、 * dup というワードがコンパイルされ（＝各ワードへのポインタがパラメタフィールドに順次追加され）、最後に ";" というワードを処理することとなります。
";" というワードはイミディエイト属性を持つワードですので、コンパイルモードであろうが、ワード ";" を直ちに実行します（つまり、単に記述しただけでは、ワード ; はコンパイルされません）。
ワード ";" では、
- ワード semis をコンパイルし、
- インタプリタモードへと移行、
します。
結果として、コンピレーションフィールドに docol が設定され、パラメタフィールドにはコンパイルされた dup, * , semis という列を持つ square というワードが作成されます。
外部インタプリタの設計
ここで作成する外部インタプリタも、Ochs の mini-forth に倣い、モードを文字列で持つようにします。
それぞれのモードで実行される処理は action テーブルで持つこととします。また、各モードにおいて、ワードの場合と数値の場合で処理を変更する必要があります。そのため、該当のトークンの値を、ワード名ならば文字列、数値として解釈できるならばその数値とすると、action テーブルは以下のように記述できます。
action={}
action.interpret={
number=function(inNumber) データスタックへプッシュ end,
string=function(inWordName) ワードを検索し、実行する end
}
action.compile={
number=function(inNumber)
ワード lit をコンパイルし、
定義中のワードのパラメタフィールドの末尾に該当の数値を配置
end,
string=function(inWordName)
inWordName を検索し、
そのワードがイミディエイト属性を持つならば、そのワードを実行、
そうでなければ、定義中のワードのパラメタフィールドの末尾にそのワードへのポインタを配置
end
}
32 行で作る外部インタプリタ
以下、今回作成した外部インタプリタのコードを示します。このコードは、もともとの趣旨より、前回の記事 同様、行数が少なくなるように圧縮してコーディングしています。
関数 outerInterpreter() は入力された 1 行文の文字列を受け取り、エラーがなければ nil を返し、もしエラーが発生した場合はそのトークン（文字列）を返すこととします。
require "innerInterpreter"
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)}
local execWord=function(inWordName) innerInterpreter({Dict[inWordName]}) end
local action={};
action.interpret={number=DS.Push, string=execWord}
action.compile ={
number=function(inValue) local ins=table.insert
ins(NewWord.param,Dict["lit"]); ins(NewWord.param,inValue)
end,
string=function(inWordName)
if Dict[inWordName].immediate then execWord(inWordName)
else table.insert(NewWord.param,Dict[inWordName]) end
end
}
function GetToken() local token
token,scanPos=string.match(Line,"^([ \t]*)()", scanPos)
token,scanPos=string.match(Line,"^([^ \t]*)()",scanPos)
return token~="" and token or nil -- token!="" ? token : nil
end
Mode="interpret"
outerInterpreter=function(inLine)
Line=inLine; scanPos=1; local token=GetToken()
while token do local tokVal = Dict[token] and token or tonumber(token)
if tokVal then action[Mode][type(tokVal)](tokVal); token=GetToken()
else return token end
end
return nil
end
tinyDict による動作テスト
前回および今回作成した、全 38 行からなる Forth システムが動作するのか、テストしてみましょう。Forth の場合、インタプリタだけでは何もできませんので、28 行のテスト用辞書も用意しましたので、以下に示します。
Dict={}
Dict.Add=function(inWord) Dict[inWord.name]=inWord end
local docol=function() local newThread=IP.thread[IP.index-1].param
RS.Push(IP); IP={thread=newThread,index=1} end
local readIP=function() return IP.thread[IP.index] end
local incIP=function() IP.index=IP.index+1 end
local compile=function(inWordName) table.insert(NewWord.param,Dict[inWordName]) end
local compileEmptySlot=function() table.insert(NewWord.param,"EMPTY_SLOT") end
Dict.Add { name=":", immediate=true, code=function()
NewWord={code=docol, name=GetToken(), param={}}
Dict[NewWord.name]=NewWord; Mode="compile" end }
Dict.Add { name="semis", code=function() IP=RS.Pop() end }
Dict.Add { name=";", immediate=true, code=function()
compile("semis"); Dict[NewWord.name]=NewWord; Mode="interpret" end }
Dict.Add { name="0branch", code=function()
if DS.Pop()==0 then IP.index=IP.index+readIP() else incIP() end end }
Dict.Add { name="if", immediate=true, code=function()
compile("0branch"); RS.Push(#NewWord.param+1); compileEmptySlot() end }
Dict.Add { name="then", immediate=true, code=function()
local p=RS.Pop(); NewWord.param[p]=#NewWord.param+1-p end }
Dict.Add { name="lit", code=function() DS.Push(readIP()); incIP() end }
Dict.Add { name="dup", code=function() local t=DS.Pop(); DS.Push(t); DS.Push(t) end }
Dict.Add { name="-", code=function() local a,b=DS.Pop(),DS.Pop(); DS.Push(b-a) end }
Dict.Add { name="*", code=function() local a,b=DS.Pop(),DS.Pop(); DS.Push(a*b) end }
Dict.Add { name=">", code=function() local a,b=DS.Pop(),DS.Pop();
if b>a then DS.Push(-1) else DS.Push(0) end end }
Dict.Add { name=".", code=function() local t=DS.Pop(); io.write(" "); io.write(t) end }
Dict.Add { name="cr", code=function() print() end }
これを使って、通常の計算と、再帰を使って階乗を計算するワードを定義し、階乗計算を行ってみます。
> dofile "outerInterpreter.lua"
> dofile "tinyDict.lua"
> -- 5 dup * を計算してみます。最後の cr は改行を行うワードです（. だけだと改行しないので）
> outerInterpreter("5 dup * . cr")
25
nil
> -- 最後の nil は全てのトークンが正しく評価できたという意味です。
> -- 次に階乗計算するワード fact を定義します
> outerInterpreter(": fact dup 1 > if dup 1 - fact * then ;")
nil
> -- fact のテスト 5!=120 となれば OK.
> outerInterpreter("5 fact . cr")
120
nil
おまけの REPL
毎回、外部インタプリタを起動するのも面倒なので、read-eval-print-loop (REPL)を行うスクリプト tinyLuaForth.lua を載せておきます。使い方ですが、読み込みたい辞書ファイルの名前を引数として起動し、空行入力で終了します（当初掲載していたバージョンではプロンプトがありませんでしたが、修正にあたり、本バージョンではプロンプトを表示するようにしました。プロンプトは > としたかったのですが、Lua のものと混同しやすいため、あえて -> というものにしています）。
require "outerInterpreter"
tinyLuaForth=function(inDictFilePath)
print "--- tiny LuaForth 1.2 ---"; dofile(inDictFilePath)
while true do io.write("-> ")
local line=io.read(); if line=="" then print("bye."); break end
local result=outerInterpreter(line)
print(result==nil and " ok." or "unknown word '"..result.."'")
end
end
使い方のサンプルです。
> dofile "tinyLuaForth.lua"
> tinyLuaForth("tinyDict.lua")
--- tiny LuaForth 1.1 ---
-> 5 dup * .
25 ok.
-> : square dup * ;
ok.
-> 5 square .
25 ok.
-> : cube dup square * ;
ok.
-> 5 cube .
125 ok.
-> : fact dup 1 > if dup 1 - fact * then ;
ok.
-> 5 fact .
120 ok.
->
bye.
>
外部インタプリタから戻って来ると print("ok.") を実行しているので、今回はワード cr の実行は必要ありません。
まとめ
前回と今回にわたり、Eduardo Ochs の "Boostrapping a Forth in 40 lines of Lua code" に触発されて、40 行程度の Forth システムを、できるだけ素直な実装で作成してみました。より素直な実装方法や、エレガントな実装方法がありましたら、コメントなどいただけると助かります。
今回、作成した Lua による Forth インタプリタには、標準の Forth とは異なる部分があります。例えば、辞書に連想配列を使用しているため、そのままでは FORGET が実現できません。一方、モダンな部分も自然に実装されており、ひとつは、Lua で取り扱うことができる情報であれば何でもプッシュ・ポップできる点です（もちろん、トークンの解釈部分のを修正する必要がありますが…）。これらを踏まえて、Lua で作る Forth というものも考えてみたく思います。それはもしかすると、factor とか mops という言語に近いものになるのかもしれませんが、個人的には、もっとゆるく、Lua で実装するが故に、素直にかつ簡単に実装できる範囲で Lua Forth というものを捉えていければ、と思っています。
後日談
実際に Lua で Forth 系言語を作成してみました。以下の記事もご覧になっていただければ幸いです。