Arantium Maestum

プログラミング、囲碁、読書の話題

PythonでForth処理系を書く! その7(繰り返し処理 DO-LOOP)

繰り返し処理を実装する。

PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも書いた通り、この構文の要素は3つあって:

  • DOでスタックに乗っている二つの整数を分岐のために使う

    • スタックから得たはじめの整数がループカウンタの開始値
    • スタックから得た次の整数がループカウンタの終了値
  • LOOPでループカウンタをインクリメントする

    • ループカウンタが終了値未満の場合はDO直後のコマンドまで後方ジャンプ
    • ループカウンタが終了値に達した場合はLOOP以降のコマンドを実行
  • DOとLOOPの間で使われるIは現在のループカウンタの値をスタックに乗せる

こんな使い方をする:

0 11 1 DO I + LOOP . CR

上記のコードは1以上11未満の整数をループ足し合わせて55を出力して改行する。

コード

github.com

IF-ELSE-THENと同じようにcompilerとinterpreterに変更を加える。

compiler.py

コンパイラにDO、LOOP、Iトークンに対応する関数を追加する。

DO:

def run_do(state):
    state['branch'].append(len(state['codes']) + 1)
    state['codes'].append('DO')

codesにはDOだけ載せ、branchスタックにそのあとの位置を載せる。(ループする場合に戻るべきジャンプ先)

LOOP:

def run_loop(state):
    do_pos = state['branch'].pop()
    state['codes'].extend(('LOOP', do_pos))

DOのコンパイルでbranchスタックに載せられた「ジャンプ先」をとり、LOOPコードと一緒にcodesに載せる。

I:

def run_i(state):
    state['codes'].append('I')

Iはそのままcodesに載せるだけ。

このとおり、compilerへの変更は非常に簡単。ループ条件はメインスタック上で管理されるので、処理のロジックはinterpreter側で実装されている。

interpreter.py

まずインタプリタの内部状態に新しくbranchスタックを追加する:

def init_state():
    return {
            'codes': [],
            'pos': 0,
            'stack': [],
            'branch': [], #新しく追加
            'end': False,
            }

IF-ELSE-THENの時にコンパイラには追加したが、今回はインタプリタにも必要。

ループカウンタの現在の値と終了値を保持するために使う。この二つをメインスタックにいれておくと、ループ中にスタックに値を追加するなどの処理と競合してしまう恐れがある。

DOの処理:

def run_do(state):
    a, b = state['stack'].pop(), state['stack'].pop()
    state['branch'].extend((b, a))
    state['pos'] += 1

スタックから二つの数字を取り、片方を開始時のループカウンタ、もう片方をループの終了値としてbranchスタックに入れる。

LOOPの処理:

def run_loop(state):
    a, b = state['branch'].pop(), state['branch'].pop()
    a += 1
    if a < b:
        state['branch'].extend((b, a))
        state['pos'] = state['codes'][state['pos']+1]
    else:
        state['pos'] += 2

branchスタックからループカウンタと終了値をとり、ループカウンタをインクリメントしてから比較。

  • ループカウンタが終了値以上なら終了
  • それ以外なら
    • ループカウンタ・終了値をbranchスタックに戻す
    • コンパイルされているループ元の位置にジャンプ

Iの処理:

def run_i(state):
    state['stack'].append(state['branch'][-1])
    state['pos'] += 1

branchスタックにあるループカウンタをメインスタックにも載せる(branchスタック側の値は載せたままで消費しない)。これでカウンタの値を利用した計算などができる。

使ってみる

まずはDOとLOOPだけで試してみる:

Starting Forth REPL...
> 5 0 DO 1 . LOOP CR
11111
> 0 5 DO 1 . LOOP CR
1

DO-LOOPは必ず一回は処理が走るので、0 5 DO 1 . LOOP CRのようにカウンタの開始値が終了値よりも大きい場合でも1 .の部分が一回実行されているのがわかる。

次にIも使ってみる:

> 5 0 DO I . CR LOOP
0
1
2
3
4
> 0 11 1 DO I + LOOP . CR
55
> 0 10 0 DO I 1 + + LOOP . CR
55

ループカウンタの値がちゃんと計算に使われている。

ちなみに0 10 0 DO I 1 + + LOOP . CRはループカウンタが0からはじまり10未満までループするなか、カウンタの値Iをインクリメントしてからこれまでの合計に足し合わせている。

次回は変数定義。