PythonでForth処理系を書く！　その６（条件分岐 IF-ELSE-THEN）

条件分岐を実装する。

PythonでForth処理系を書く！その２（実装する機能） - Arantium Maestumでも言ったとおり、Forthの条件分岐構文は他の言語を知る人には多分だいぶ奇妙に見えるはず。

上記の記事からの再掲になるが、このような構文で：

1 IF 2 ELSE 3 THEN . CR

このような処理になる：

IFコマンドの時点でスタックの上が0以外ならELSEまで実行してからTHENにジャンプ、0ならELSEまでジャンプしてから実行を続ける

THENが「IFが満たされた場合に実行される処理」ではなく、「IF-ELSE分岐が終わって実行パスが合流するポイント」を表しているのがForthの特徴。THENではなくENDIFのほうがいいのではないかという意見も読んだことがあり、一理あると思う。

実装としてはこう：

github.com

ついでにこう（バグの修正）：

github.com

変更している箇所はcompilerとinterpreter。ここでようやく中間言語にコンパイルすることの利点が活きてくる。

compiler.py

まずはコンパイラの内部状態にあたらしく分岐に関連する情報を維持するスタックを用意：

def init_state():
    return {
            'tokens': [],
            'pos': 0,
            'codes': [],
            'branch': [],  #これを追加
            'end': False
            }

そのbranchスタックを使ってIF、ELSE、THENのトークンをコンパイルする各関数を定義する。

まずIF:

def run_if(state):
    state['branch'].append(len(state['codes']) + 1)
    state['codes'].extend(('IF', None))

出力するcodesにIFとNoneを載せる。

コンパイルが進んで対応するELSE（あるいはELSEがない場合はTHEN）に遭遇したときに、NoneをそのELSE/THENのコードの位置の値に書き換える。あとで書き換えられるようbranchスタックにNoneの位置（len(state['codes']) + 1）を載せておく。

次にELSE:

def run_else(state):
    if_pos = state['branch'].pop()
    state['codes'][if_pos] = len(state['codes']) + 2

    state['branch'].append(len(state['codes']) + 1)
    state['codes'].extend(('ELSE', None))

まずはbranchスタックから対応するIFのNoneの位置を取り出す。そのNoneをELSE以降のコードの位置（len(state['codes']) + 2）に書き換える。

ELSEで追加されるコードはIFと似たようなもの。ELSEとNoneで、NoneはELSEと対応するTHENのコードにジャンプするための位置情報。

最後にTHEN:

def run_then(state):
    else_pos = state['branch'].pop()
    state['codes'][else_pos] = len(state['codes'])

ELSEの前半部分とほぼ同一。branchスタックに載っているのが対応するELSEのNoneの位置（あるいはELSE部分がなくIF-THENだった場合はIFのNoneの位置）。

THENの場合はそこに到達した時点で分岐は終了しており、ジャンプする必要がないのでcodesにはなにも追加されない。

最後に定義した関数をprimitivesとして追加：

primitives = {
        '+': run_plus,
        '.': run_print,
        'CR': run_cr,
        'IF': run_if,
        'ELSE': run_else,
        'THEN': run_then,
        }

IF/ELSE/THENトークンに遭遇したらrun_if/run_else/run_then関数が呼び出されるようになる。

実はここでバグをいれて放置してしまった。「THENがコード追加しない」ということから何故か「primitivesに追加しなくてもオッケー」と思い込んでいて、最初のbranch mergeでは'THEN': run_thenの部分が抜けていた。不覚・・・

このコンパイラで

1 IF 2 ELSE 3 THEN . CR

このコードをコンパイルすると

['PUSH', 1, 'IF', 8, 'PUSH', 2, 'ELSE', 10, 'PUSH', 3, '.', 'CR', 'END']

こんな感じの中間言語に変換される。あるいはコード位置も追加でつけるなら：

 0 PUSH
 1 1
 2 IF
 3 8
 4 PUSH
 5 2
 6 ELSE
 7 10
 8 PUSH
 9 3
10 .
11 CR
12 END

PUSHの後の数字はスタックに載せるための数字、IFやELSEの後の数字はジャンプ先の位置だ。

ちなみにTHENトークンの情報はELSEのジャンプ先の数字になるので、THENというコード自体はコンパイル結果には現れないことがわかる。

次にこれをインタプリタが実行できるようにする。

interpreter.py

IFとELSEのコードを処理できるようにinterpreterに関数を追加する。

まずはIF:

def run_if(state):
    a = state['stack'].pop()
    if a == 0:
        state['pos'] = state['codes'][state['pos']+1]
    else:
        state['pos'] += 2

スタックの一番上をとり、その数が0であればジャンプ、そうでなければそのまま次のコードを処理していく。

IFのすぐあとはジャンプ先の位置情報なので、もしジャンプしない場合はそのコードも飛ばす必要があるのでstate['pos'] += 2になる。

ELSEの処理：

def run_else(state):
    state['pos'] = state['codes'][state['pos']+1]

IFの条件が0だった場合はELSEの先にジャンプするので、ELSEコードに到達したということはすでにIFからELSEの間のコードが走ったということ。なので、ELSEからTHENまでのトークンがコンパイルされた「ELSEブロック」を飛ばしてその先にジャンプする。

使ってみる

前回実装したREPLでいろいろといじっていみる：

Starting Forth REPL...
> 1 IF 2 ELSE 3 THEN . CR
2
> 0 IF 2 ELSE 3 THEN . CR
3
> 1 1 IF 2 THEN . CR
2
> 1 0 IF 2 THEN . CR
1
> 1 -1 + IF 0 ELSE 2 THEN . CR
2

ELSEが存在する場合、存在しない場合どちらでもうまく作動している。

IF-ELSE-THENのネスト：

> 0 1 IF IF 2 ELSE 3 THEN ELSE 4 THEN . CR
3
> 1 1 IF IF 2 ELSE 3 THEN ELSE 4 THEN . CR
2
> 0 0 IF IF 2 ELSE 3 THEN ELSE 4 THEN . CR
4

ややこしいが正しい挙動になっている。

IF-ELSE-THENの順序が間違っていたりするとエラー：

> 1 IF 5 THEN 3 ELSE 2 . CR
Traceback (most recent call last):
  File "main.py", line 36, in <module>
    run_repl()
....
    if_pos = state['branch'].pop()
IndexError: pop from empty list

異常系でどんな挙動になるかはまったく保証できない。今回はコンパイルエラー（ELSEが書き換えるべきIFのジャンプ先がbranchスタックに乗っていなかった）。今のところエラーハンドリングは改善の予定はない。めんどくさそう。

次回はDO-LOOP構文を追加して「繰り返し」処理を可能にする。