はじめに

前回の文章、「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_frame.lua

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 を返し、もしエラーが発生した場合はそのトークン（文字列）を返すこととします。

outerInterpreter.lua

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 行のテスト用辞書も用意しましたので、以下に示します。

tinyDict.lua

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 }

これを使って、通常の計算と、再帰を使って階乗を計算するワードを定義し、階乗計算を行ってみます。

ex_outerInterpreter.txt

> 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 のものと混同しやすいため、あえて -> というものにしています）。

tinyLuaForth.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

使い方のサンプルです。

ex_tinyLuaForth.txt

> 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 系言語を作成してみました。以下の記事もご覧になっていただければ幸いです。

38 行の Lua プログラムで Forth インタプリタを作る（内部インタプリタ 6 行、外部インタプリタ 32 行）