PythonでForth処理系を書く！　その３（最低限の機能）

PythonでForth処理系を書く！その２（実装する機能） - Arantium Maestum

でも書いた通り、まずは以下の機能を最低限として実装する：

整数をスタックに乗せる
スタックから二つの整数をとり、それらを足し合わせた整数をスタックに乗せる
スタックから整数をひとつとり、その数を標準出力に表示する
標準出力に改行を表示する

実行できるコードはこんな感じだ：

1 2 + . CR

簡単な実装

まずはできるだけ簡単に実装してみる：

s = '1 2 + . CR'

stack = []
for token in s.split():
    try:
        stack.append(int(token))
        continue
    except ValueError:
        pass
    if token == '+':
        a, b = stack.pop(), stack.pop()
        stack.append(a+b)
    elif token == '.':
        print(stack.pop(), end='')
    elif token == 'CR':
        print()

ハードコードされたforthコードをsplitでトークンに分け、forループで一つ一つのトークンごとにtry-except/if-elseでトークンタイプをチェックして実行していく。

今回実装する機能だけだったらこれで充分かもしれない。ただ、密結合な上にフローをかなり単純視している（具体的にはトークンとインタプリタの動作に１対１の対応があることを前提としてしまっている）ので、今後の機能追加が容易ではない。

拡張しやすくなるように、どのような異なる機能・段階があるのかを明確にする形で分割してみる。

分割した実装

github.com

まずはインタプリタの全体を統括するmain.py:

import tokenizer
import compiler
import interpreter

if __name__ == '__main__':
    with open('samples/sample1.forth') as f:
        s = ' '.join(f)
    tokens = tokenizer.tokenize(s)
    code_list = compiler.compile(tokens)
    interpreter.interpret(code_list)

分割した個別のトークナイザ・コンパイラ・インタプリタをインポートして使っている。一つのポイントとしては、全体としてはインタプリタなのだが、トークンを直接インタプリタに渡すのではなく、インタプリタが実行しやすいような中間言語にコンパイルするステップが入っていること。このコンパイルステージが今後の条件分岐や変数定義などでは非常に便利になる。

tokenizer.pyの実装:

def tokenize(s):
    return s.split()

非常に簡単。スペースで分割するだけ。トークンも特にクラス化せず、ただの文字として扱う。

compiler.py:

def compile(tokens):
    code_list = []
    for token in tokens:
        code_list.extend(compile_token(token))
    code_list.append('END')
    return code_list

def compile_token(token):
    if is_int(token):
        return ('PUSH', int(token))
    d = {'+':'PLUS', '.':'PRINT', 'CR':'CR'}
    return (d[token], )

def is_int(s):
    try:
        int(s)
    except ValueError:
        return False
    return True

トークンが数字だったらスタックに乗せるようにPUSH Xという二つのコードにコンパイル。それ以外（+, ., CR）はそれぞれ一つのコードにコンパイルする。

トークンが数字かどうかの判定もコンパイラ部分で行っているが、トーケナイザ部分で判定してその情報をトークンに持たせる手もある。あまり関係ないが、個人的にPythonの「文字列がInt化できるか判定」イディオムはあまり好きではない・・・

コンパイラの吐く中間言語を受け取り、実行していくinterpreter.py:

def interpret(code_list):
    counter = 0
    stack = []
    while True:
        if code_list[counter] == 'END':
            break
        elif code_list[counter] == 'PUSH':
            stack.append(code_list[counter+1])
            counter += 2
        elif code_list[counter] == 'PLUS':
            a, b = stack.pop(), stack.pop()
            stack.append(a+b)
            counter += 1
        elif code_list[counter] == 'PRINT':
            print(stack.pop(), end='')
            counter += 1
        elif code_list[counter] == 'CR':
            print()
            counter += 1

スタック（Pythonのリスト）に数字をappendしたりpopしたりしながら中間言語の指示を実行していく。

これで元々のサンプル：

1 2 + . CR

を実行することはもちろん、今後の機能を追加していくのもかなりやりやすくなった。だが、実はもう一つリファクタするべきポイントがある。コンパイラとインタプリタの両方で、状態をデータ構造に保存するようにしたい。

次回はその理由と実装の話。