Lua
Forth

35 行の Lua プログラムで Forth インタプリタを作る(内部インタプリタ 6 行、外部インタプリタ 29 行)

はじめに

前回の文章、「6 行の Lua プログラムで、Forth の内部インタプリタを作る」では、内部インタプリタを作成しました。作成した内部インタプリタの動作確認として、実際の Forth プログラムを実行させましたが、ハンドコンパイルする必要がありました。

今回は外部インタプリタを作成します。これにより、ハンドコンパイルは不要となります。また、外部インタプリタを eval として、read-eval-print-loop を構成できるようにもなります。

外部インタプリタの仕事

外部インタプリタには 2 つのモードがあり、それぞれのモードで実現すべき機能が異なります。ひとつはインタプリタモードで、これはワードを起動する等して、計算などの処理を実行するモードです。もうひとつはコンパイルモードで、ワードの定義などはこのモードで実施されます。

インタプリタモードで行うべきこと

インタプリタモードでは、入力された文字列(トークン)により、以下のいずれかの処理を行います。

  • 数値が入力されたとき: その数値をデータスタックにプッシュします。
  • 数値以外の文字列が入力されたとき: その文字列をワード名とし、該当ワードを検索し、実行します。

例えば、 5 dup * . という文字列が入力された場合は、

トークン スタック 説明
5 数値なのでスタックに積む
dup 5 "dup" というワードを探して実行する(=スタックトップを複製する)
* 5 5 "*" というワードを探して実行する(=スタックの上から 2 つ取り出し、それらの積をプッシュする)
. 25 "." というワードを探して実行する(=スタックトップの値を表示する)

と処理され、最終的に 25 という数値が画面に表示されます。

コンパイルモードで行うべきこと

コンパイルモードでも、入力された文字列が数値でない場合、ワード名と解釈するのはインタプリタモードと同じです。コンパイルモードでは、現在コンパイル中のワードのパラメタフィールドにコンパイルした結果を順次書き込んでいきます。具体的には、以下の処理を行います。

  • 数値が入力されたとき: ワード "lit" をコンパイルし、その直後に該当の数値を配置します。
  • 数値以外の文字列が入力されたとき(=ワード名のとき): 該当ワードを検索し、もし、そのワードがイミディエイト属性(即時実行特性)を持つならば、そのまま実行し、そうでなければ、該当ワードへのポインタをパラメタフィールドの末尾に配置します。

例として、 : square dup * ; という文字列を処理してみます。外部インタプリタはインタプリタモードにて起動するため、最初は ":" というワードを実行することとなります。

":" を実行すると、

  1. 新しいワードの領域が作成され、
  2. 入力された文字列から次のトークンを読出し、それをワード名として設定し、
  3. そのワードのコンピレーションフィールドに docol を設定し、
  4. コンパイルモードへと移行、

します。

あとは、 * dup というワードがコンパイルされ(=各ワードへのポインタがパラメタフィールドに順次追加され)、最後に ";" というワードを処理することとなります。

";" というワードはイミディエイト属性を持つワードですので、コンパイルモードであろうが、ワード ";" を直ちに実行します。

ワード ";" では、

  1. ワード semis をコンパイルし、
  2. インタプリタモードへと移行、

します。

結果として、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
}

29 行で作る外部インタプリタ

以下に、今回作成した外部インタプリタのコードを示します。このコードは、もともとの趣旨より、前回の記事 同様、行数が少なくなるように圧縮してコーディングしています。

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)
    if token=="" then return nil end
    local t=tonumber(token); if t~=nil then return t else return token end
end
Mode="interpret"
outerInterpreter=function(inLine)
    Line=inLine; scanPos=1; local tokVal=GetToken()
    while tokVal do action[Mode][type(tokVal)](tokVal); tokVal=GetToken() end
end

tinyDict による動作テスト

前回および今回作成した、全 35 行からなる Forth システムが動作するのか、テストしてみましょう。Forth の場合、インタプリタだけでは何もできませんので、30 行のテスト用辞書も用意しましたので、以下に示します。

tinyDict.lua
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
compile=function(inWordName) table.insert(NewWord.param,Dict[inWordName]) end
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

> -- 次に階乗計算するワード fact を定義します
> outerInterpreter(": fact dup 1 > if dup 1 - fact * then ;")

> -- fact のテスト 5!=120 となれば OK.
> outerInterpreter("5 fact . cr")
 120

おわりに

毎回、外部インタプリタを起動するのも面倒なので、read-eval-print-loop (REPL)を行うスクリプト tinyLuaForth を載せておきます。使い方ですが、読み込みたい辞書ファイルの名前を引数として起動し、空行入力で終了します。

tinyLuaForth.lua
require "outerInterpreter"
tinyLuaForth=function(inDictFilePath)
    print "--- tiny LuaForth ---"; dofile(inDictFilePath)
    while true do
        local line=io.read(); if line=="" then print("bye."); break end
        outerInterpreter(line); print(" ok.")
    end
end

使い方のサンプルです。

ex_tinyLuaForth.txt
> dofile "tinyLuaForth.lua"
> tinyLuaForth("tinyDict.lua")
--- tiny LuaForth ---
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 というものを捉えていければ、と思っています。