トイ言語実験日記５（中間コードインタプリタ）
kb84tkhr小ネタやってる間に夏休みに入ったのでちょっと大物に手を出してみよう
いったん中間コードにコンパイルしてから仮想マシンで実行する形式にするよ！
といっても性能向上を狙っているわけではなくて
実はletccの実装はこっちのが簡単なんじゃね？というのを確かめたい
あとコード生成の原理を理解できてるか確かめたい
コンパイラ系の本はざっと目を通したくらいで自分で書いたことはないので
はじめてなので０から書いていく
例によって最小限の実装で
できるだけ仮想マシンに仕事をさせてコード生成は楽をするつもり
mainブランチのEvaluatorを置き換えられるくらいまでいくといいな
あとletccは当初の狙いだしやってみたい
末尾再起最適化まではできるかもしれない
ただマクロが書ける気はしていない
kb84tkhr仮想マシンはスタックマシンとして実装する
初心者はスタックマシンがいいらしいので
まずは定数をスタックに積むだけのものを作る
class Compiler:
def __init__(self):
self._code = []
def compile(self, expr):
self._expr(expr)
return self._code
def _expr(self, expr):
match expr:
case None | bool(_) |int(_):
self._code.append(["const", expr])
case unexpected:
assert False, f"Unexpected expression: {unexpected}"
class VM:
def __init__(self):
self._stack = []
def execute(self, code):
for inst in code:
match inst:
case ["const", val]:
self._stack.append(val)
case unexpected:
assert False, f"Unexpected instruction: {unexpected}"
assert len(self._stack) == 1, "Unused stack left: {self.stack}"
return self._stack[0]
def test_run(expr):
vm = VM()
print(f"Source:\n{expr}")
code = Compiler().compile(expr)
print("Code:")
for i, inst in enumerate(code):
print(f"{i:3}: {inst}")
print(f"Result:\n{vm.execute(code)}\n")
test_run(None)
test_run(True)
test_run(False)
test_run(5)
↓
Source:
None
Code:
0: ['const', None]
Result:
None
Source:
True
Code:
0: ['const', True]
Result:
True
Source:
False
Code:
0: ['const', False]
Result:
False
Source:
5
Code:
0: ['const', 5]
Result:
5
ガワとしてはこんなところでは
kb84tkhr覚書
Compiler.compile()はASTを中間コードにする
中間コードは単なるPythonの配列で（いつもどおり）
インストラクションも単なるPythonの配列
バイトで表現したりはしない
今はまだコードが短すぎてイメージがわかないかもしれないけれども
[['const', None]]は['const', None]というインストラクションがひとつだけ並んだコード
'const'がオペコードでNoneがオペランド
'const'はオペランドをそのままスタックに積むという命令
このへんでインストラクションを作っている
match expr:
case None | bool(_) |int(_):
self._code.append(["const", expr])
VM.execute()は中間コードを読んで実行する
'const'だったらオペランドをそのままスタックに積む
match inst:
case ["const", val]:
self._stack.append(val)
中間コードを最後まで実行したらスタックのいちばん上を返す
ちゃんとしてればスタックには１個だけ要素が残っているはず
assert len(self._stack) == 1, "Unused stack left: {self.stack}"
return self._stack[0]
以上です
kb84tkhrスタックマシンといえば四則演算・・・だけど足し算と等号だけ
仮想マシンに演算のインストラクション add・sub・equalを追加する
スタックから値を取り出しては演算して答えをスタックに積む
それがスタックマシン
ツリーウォーク式でも簡単に計算できるASTになっているのにそれをわざわざ逆ポーランド式に書き換えてるんだから無駄なことをしてるような気もしないでもないけれども
（本ではたいていASTを作らず構文解析してそのまま中間コードを出してる気がする）
class VM:
ops = {
"add": lambda s: s.append(s.pop() + s.pop()),
"sub": lambda s: s.append(s.pop() - s.pop()),
"equal": lambda s: s.append(s.pop() == s.pop())
}
...
def execute(self, code):
for inst in code:
match inst:
...
case ["op", op]:
VM.ops[op](self._stack)
...
add・sub・equalそれぞれ個別にインストラクションにすると後でmatchがえげつないことになりそうなのでopというインストラクションにまとめた
コンパイラ側は仮想マシンが計算できるよう、値をスタックに積むコードを出力してから演算のインストラクションを出力する
_expr(expr)はexprをコンパイルするんだけれどももうすこし詳しく言うと「exprを計算して結果をスタックに積むコードを出力する」ということなので_expr(expr)を何度も呼ぶだけでどんどんスタックに積むコードになる
あと、仮想マシンがスタックをpopする順番を考慮してスタックには逆順に積んでいることに注意。
class Compiler:
...
def _expr(self, expr):
match expr:
...
case [op, *args]:
self._op(op, args)
...
def _op(self, op, args):
for arg in args[-1::-1]:
self._expr(arg)
self._code.append(["op", op])
_expr()の再帰呼び出しのおかげで入れ子も処理できるようになっている
test_run(["add", 5, 6])
test_run(["add", 5, ["add", 6, 7]])
↓
Source:
['add', 5, 6]
Code:
0: ['const', 6]
1: ['const', 5]
2: ['op', 'add']
Result:
11
Source:
['add', 5, ['add', 6, 7]]
Code:
0: ['const', 7]
1: ['const', 6]
2: ['op', 'add']
3: ['const', 5]
4: ['op', 'add']
Result:
18
kb84tkhr次は条件分岐かな
VMに、指定したアドレス（ここでは配列の添え字）にジャンプする機能と、スタックのトップが偽のときだけジャンプするインストラクションを追加する
コードを先頭から順番に実行すればいいというわけではなくなるので、今実行しているところ（IP: Instruction Pointer）を覚えておき、これをインクリメントしたりジャンプ先のアドレスに設定したりする
また、プログラムが終わったことを示す["halt"]というインストラクションを追加して、IPが["halt"]を指すまで回り続けるwhileループとした
ループを止めたいだけならコードの最後まで届いたかどうかで判断できるのだけれども、「プログラムの最後にジャンプしたい」ときの飛び先として["halt"]を置いたという意味合いもある
class VM:
def __init__(self):
self._stack = []
self._ip = 0
def execute(self, code):
while (inst := code[self._ip]) != ["halt"]:
match inst:
...
case ["jump", addr]:
self._ip = addr
continue
case ["jump_if_false", addr]:
if not self._stack.pop():
self._ip = addr
continue
...
self._ip += 1
assert len(self._stack) == 1, "Unused stack left: {self.stack}"
return self._stack[0]
コンパイラの方ではバックパッチという技を使う
これはややこしいので後で書くとして、細かいところではコードの最後に["halt"]をつけたり、これから書き込もうとしているアドレス（配列の長さと一致する）を返す_current_addr()を作ったりしている
class Compiler:
def compile(self, expr):
self._expr(expr)
self._code.append(["halt"])
return self._code
def _expr(self, expr):
match expr:
case None | bool(_) |int(_):
self._code.append(["const", expr])
case ["if", cnd, thn, els]:
self._if(cnd, thn, els)
case [op, *args]:
self._op(op, args)
case unexpected:
assert False, f"Unexpected expression: {unexpected}"
def _if(self, cnd, thn, els):
self._expr(cnd)
els_jump = self._current_addr()
self._code.append(["jump_if_false", None])
self._expr(thn)
end_jump = self._current_addr()
self._code.append(["jump", None])
self._set_operand(els_jump, self._current_addr())
self._expr(els)
self._set_operand(end_jump, self._current_addr())
def _set_operand(self, ip, operand):
self._code[ip][1] = operand
def _current_addr(self):
return len(self._code)
実行するとこうなる
Source:
['if', ['equal', 5, 5], 6, 7]
Code:
0: ['const', 5]
1: ['const', 5]
2: ['op', 'equal']
3: ['jump_if_false', 6]
4: ['const', 6]
5: ['jump', 7]
6: ['const', 7]
7: ['halt']
Expected Result: 6
Actual Result : 6
['if', ['equal', 5, 5], 6, 7]を例にとって_if(self, cnd, thn, els)がどうコンパイルされるか見ていく
まず出力されたコードの理解
0: ['const', 5] # if式の開始＆条件式(cnd)の実行
1: ['const', 5] #
2: ['op', 'equal'] # 等しいかどうかをスタックに積む
3: ['jump_if_false', 6] # 結果が偽なら結果式(thn)をスキップするためアドレス6に飛ぶ
4: ['const', 6] # 結果式の実行
5: ['jump', 7] # 代替式(els)をスキップするためアドレス7に飛ぶ
6: ['const', 7] # 代替式の実行
7: ['halt'] # 次の式の開始
コンパイルの様子
まず条件の式をコンパイルする
self._expr(cnd)
5を積んで5を積んで比較し、等しいかどうかをスタックに積むコードが出力される
0: ['const', 5]
1: ['const', 5]
2: ['op', 'equal']
つぎがバックパッチの前半
els_jump = self._current_addr()
self._code.append(["jump_if_false", None])
['jump_if_false', 6]を出力したいんだけれども飛び先がアドレス6かどうかはまだわからないのでわからないまま['jump_if_false', None]を出力する
あとでこのNoneを書き換えるので、書き換えたいインストラクションのアドレスをels_jumpに覚えておく
次に結果式（thn）をコンパイルしたら・・・
self._expr(thn)
２回めのバックパッチの準備
説明は省略
end_jump = self._current_addr()
self._code.append(["jump", None])
次に代替式（els）のコードを出力するわけだけれどもここがjump_if_falseの飛び先になる
そこで現在のアドレスを取得して、jump_if_falseの飛び先を更新してやる
これにて（ひとつめの）バックパッチ完了
self._set_operand(els_jump, self._current_addr())
で代替式（els）のコードを出力したら
self._expr(els)
２回目のバックパッチ
self._set_operand(end_jump, self._current_addr())
というわけ
kb84tkhr変数やります
コンパイルして実行する系の本だとたいてい変数の表を作ってどこに値が保存してあるか管理するようになっている気がするけどここではおなじみのEnvironmentをそのまま使う
とにかくVMに仕事させてコンパイルは簡単に
まだスコープの考え方は不要だけどどうせすぐ必要になるのでこの形で
はい
class VariableNotFoundError(Exception):
def __init__(self, name):
self._name = name
class Environment:
def __init__(self, parent=None):
self._parent = parent
self._vals = {}
def define(self, name, val):
self._vals[name] = val
return val
def assign(self, name, val):
if name in self._vals:
self._vals[name] = val
return val
elif self._parent is not None:
return self._parent.assign(name, val)
else:
raise VariableNotFoundError(name)
def get(self, name):
if name in self._vals:
return self._vals[name]
elif self._parent is not None:
return self._parent.get(name)
else:
raise VariableNotFoundError(name)
VMに環境を持たせて、Environmentのメソッドを呼ぶだけの新しいインストラクションを追加
class VM:
...
def __init__(self):
self._stack = []
self._ip = 0
self._env = Environment()
def execute(self, code):
self._stack = []
self._ip = 0
while (inst := code[self._ip]) != ["halt"]:
match inst:
...
case ["def", name]:
self._env.define(name, self._stack[-1])
case ["set", name]:
self._env.assign(name, self._stack[-1])
case ["get", name]:
self._stack.append(self._env.get(name))
...
なぜ__init__()で初期化した_stack_や_ipをまたあらためてexecute()で初期化しているかというと、VMオブジェクトを使いまわすようになったから
せっかく変数を定義しても次の式を実行するときには忘れちゃいました、では困るので
というわけで実行周りも少し修正
def test_run(vm, expr, expected):
...
result = vm.execute(code)
...
vm = VM()
test_run(vm, ["define", "a", ["add", 5, 6]], 11)
test_run(vm, "a", 11)
コンパイラも該当のインストラクションを出力するだけ
class Compiler:
...
def _expr(self, expr):
match expr:
...
case str(name):
self._code.append(["get", name])
case ["define", name, val]:
self._expr(val)
self._code.append(["def", name])
case ["assign", name, val]:
self._expr(val)
self._code.append(["set", name])
...
つぎ行きましょう
kb84tkhrここで関数に進んでもいいんだけれどもprintとseqを作っておく
printはVMのインストラクションとして追加する
スタックのトップをprintしてNoneをスタックに積むだけ
Pythonのlambdaは式がひとつしか書けないので苦肉の策として配列に入れている
[None, None]が返されるが戻り値は使われないので問題ない
class VM:
ops = {
...
"print": lambda s: [print(s.pop()), s.append(None)]
}
...
test_run(vm, ["print", 5], None)
↓
Source:
['print', 5]
Code:
0: ['const', 5]
1: ['op', 'print']
2: ['halt']
Expected Result: None
5
Actual Result : None
ただしこれまで作ってきたprintとは互換性がない
引数がひとつしか取れないので
がんばればできると思うけど今はがんばらない
kb84tkhrseqも特に難しいところはない
class Compiler:
...
def _expr(self, expr):
match expr:
...
case ["seq", *exprs]:
self._seq(exprs)
...
def _seq(self, exprs):
for expr in exprs:
self._expr(expr)
if expr is not exprs[-1]:
self._code.append(["pop"])
順番に式をコンパイルしていくだけ
ただしそれだけだと式の結果がスタックに積みあがってしまうので、最後の式以外は結果を捨ててしまう → pop
popはpop()するだけ
class VM:
...
def execute(self, code):
...
while (inst := code[self._ip]) != ["halt"]:
match inst:
...
case ["pop"]:
self._stack.pop()
...
複数の式をまとめて実行できる
test_run(vm, ["seq", ["print", 5], ["print", 6]], None)
test_run(vm, ["seq", ["define", "x", 5], ["define", "y", 6], ["add", "x", "y"]], 11)
↓
Source:
['seq', ['print', 5], ['print', 6]]
Code:
0: ['const', 5]
1: ['op', 'print']
2: ['pop']
3: ['const', 6]
4: ['op', 'print']
5: ['halt']
Output:
5
6
Expected Result: None
Actual Result : None
Source:
['seq', ['define', 'x', 5], ['define', 'y', 6], ['add', 'x', 'y']]
Code:
0: ['const', 5]
1: ['def', 'x']
2: ['pop']
3: ['const', 6]
4: ['def', 'y']
5: ['pop']
6: ['get', 'y']
7: ['get', 'x']
8: ['op', 'add']
9: ['halt']
Output:
Expected Result: 11
Actual Result : 11
kb84tkhrいよいよ関数
さすがにこれはひと仕事になる
できるだけ仕事は仮想マシンに押し付けてコンパイラは簡単にする作戦を継続
- 仮想マシンに
func（クロージャを生成してスタックに積む）、call（関数を呼ぶ）、ret（関数から戻る）のインストラクションを追加する - コンパイラは関数を見つけたら本体をコンパイルして
funcのインストラクションを出力 - 呼ぶときは引数と関数をスタックに積んで
callのインストラクションを出力
コンパイラが関数を見つけたら
class Compiler:
def _expr(self, expr):
match expr:
...
case ["func", params, body]:
self._func(params, body)
...
本体をコンパイルしてfuncのインストラクションを出力する
...
def _func(self, params, body):
skip_jump = self._current_addr()
self._code.append(["jump", None])
func_addr = self._current_addr()
self._expr(body)
self._code.append(["ret"])
self._set_operand(skip_jump, self._current_addr())
self._code.append(["func", func_addr, params])
本体をコンパイルするんだけれどもただそこでコンパイルするだけでは実行されてしまうのでバックパッチを使って本体部分をスキップしてfuncまで飛ぶ
funcは関数の先頭のアドレスと関数のパラメータリストをオペランドに取ることにする
そんな自由になんでもオペランドに取っていいのという気もするけれどもまあ
ちゃんとやるならこの関数のアドレスはどこ、パラメータリストはこう、みたいなのを別途表にしておいて表を参照しながらコードにしていくんだと思う
そのうちやるかもしれない
やらないかもしれない
何をオペランドにとって何をスタックに積んでおくのかの基準はまだちょっとわかってない
全部スタックに積んでインストラクションはオペランドを取らないことにしてもいいのかもしれない
そのうちわかるかもしれない
本体をコンパイルしたら最後にretのインストラクションを出力していることにも注意
retは呼び出し元に戻る命令
仮想マシン側ではfuncのインストラクションが出てきたらクロージャつまり関数のアドレスと、パラメータリストと、環境をセットにしたものをスタックに積む
class VM:
...
def execute(self, code):
...
while (inst := code[self._ip]) != ["halt"]:
match inst:
...
case ["func", addr, params]:
self._stack.append(["closure", addr, params, self._env])
...
今度は関数を呼ぶ側
case [op, *args]:はそのまま使って、_op()の中で直接インストラクションを書くか関数呼び出しにするか振り分けている
関数呼び出しにする場合はop部分をコンパイルしてcallのインストラクションを出力
class Compiler:
...
def _expr(self, expr):
match expr:
...
case [op, *args]:
self._op(op, args)
...
...
def _op(self, op, args):
for arg in args[-1::-1]:
self._expr(arg)
if isinstance(op, str) and op in VM.ops:
self._code.append(["op", op])
else:
self._expr(op)
self._code.append(["call"])
あと仮想マシン側にcallの処理をつければ関数が呼び出せる
はず
ちょっとここの実装はうまくない気がしている
これまでの実装と非互換があるしなんとなくキレイじゃない
しかし進む
呼び出し用に別のスタックを追加
実はスタックひとつでもできたんだけれども分けた方がすっきりする
class VM:
...
def __init__(self):
...
self._call_stack = []
...
callの処理は細切れに説明
def execute(self, code):
...
while (inst := code[self._ip]) != ["halt"]:
match inst:
...
case ["call"]:
self._call()
continue
...
def _call(self):
match self._stack.pop():
case ["closure", addr, params, env]:
クロージャからアドレスとパラメータリストと環境を取り出す
args = [self._stack.pop() for _ in params]
スタックから実引数の値を取り出す
スタックにはパラメータと同じ数の値が積まれているものと信じている
self._call_stack.append([self._ip + 1, self._env])
あとで戻ってこれるように、コールスタックに次のインストラクションのアドレスと現在の環境を積んでおく
self._env = Environment(env)
for param, val in zip(params, args):
self._env.define(param, val)
新しいスコープを作って、パラメータと値から変数を定義する
self._ip = addr
関数のアドレスに飛ぶ
case unexpected:
assert False, f"Unexpected call: {unexpected}"
へんな形だったらエラーにする
Evaluatorの_applyと対比させるとイメージしやすいかもしれない
class Evaluator:
def eval(self, expr, env):
match expr:
...
case [func, *args]:
return self._apply(
self.eval(func, env),
[self.eval(arg, env) for arg in args])
...
def _apply(self, f_val, args_val):
...
_, params, body, env = f_val
new_env = Environment(env)
for param, arg in zip(params, args_val):
new_env.define(param, arg)
return self.eval(body, new_env)
動かす
test_run(vm, ["seq",
["define", "myadd", ["func", ["a", "b"], ["add", "a", "b"]]],
["myadd", 5, 6]
], 11)
↓
Source:
['seq', ['define', 'myadd', ['func', ['a', 'b'], ['add', 'a', 'b']]], ['myadd', 5, 6]]
Code:
0: ['jump', 5]
1: ['get', 'b']
2: ['get', 'a']
3: ['op', 'add']
4: ['ret']
5: ['func', 1, ['a', 'b']]
6: ['def', 'myadd']
7: ['pop']
8: ['const', 6]
9: ['const', 5]
10: ['get', 'myadd']
11: ['call']
12: ['halt']
Output:
Expected Result: 11
Actual Result : 11
想定通り
kb84tkhrフィボナッチや
test_run(vm, ["seq",
["define", "fib", ["func", ["n"],
["if", ["equal", "n", 0], 0,
["if", ["equal", "n", 1], 1,
["add", ["fib", ["sub", "n", 1]], ["fib", ["sub", "n", 2]]]]]]],
["fib", 10]
], 55)
↓
Source:
...
Expected Result: 55
Actual Result : 55
カウンタも動く
test_run(vm, ["seq",
["define", "make_counter", ["func", [], ["seq",
["define", "c", 0],
["func", [], ["assign", "c", ["add", "c", 1]]]]]],
["define", "counter1", ["make_counter"]],
["define", "counter2", ["make_counter"]],
["print", ["counter1"]],
["print", ["counter1"]],
["print", ["counter2"]],
["print", ["counter2"]],
["print", ["counter1"]],
["print", ["counter2"]]
], None)
↓
Source:
...
Output:
1
2
1
2
3
3
Expected Result: None
Actual Result : None
kb84tkhrこれにて一件落着
とはいかなくて
test_run(vm, ["seq",
["define", "myadd", ["func", ["a", "b"], ["add", "a", "b"]]],
["myadd", 5, 6]
], 11)
は動いても
test_run(vm, ["define", "myadd", ["func", ["a", "b"], ["add", "a", "b"]]], 11)
test_run(vm, ["myadd", 5, 6], 11)
は動かない
ひとつめのtest_run()が終わったときにはもう["define", "myadd", ["func", ["a", "b"], ["add", "a", "b"]]]をコンパイルした中間コードは捨てられちゃってるから！
ぜーんぶひとつのseqにまとめてしまえばなんでも動かせることは動かせるんだけれどもstdlib()みたいなことができなくなるしなんたってREPLが作れない（ずっと作ってないけど
ので以前のコードを覚えておいて再利用できるしくみを導入する必要がある
すぐ思いつく選択肢はふたつ
コンパイルしたコードをVM._codeの末尾にappendしていく
→
appendされることを前提にアドレスを計算する必要がある
appendしたアドレスを覚えておいて実行させるときに指定してやる必要がある
VM._codeを２次元配列にして、関数を呼ぶときは何番目のコードのアドレスいくつ、という形で呼ぶ
→
アドレスはそのままでいいが、「関数」に「何番目のコード」かも覚えさせておく必要がある
実行時にも何番目のコードを実行するのか指定する必要がある（たいていは最後に追加したコードでよさそうな気はする）
さて
kb84tkhr
VM._codeを２次元配列にして、関数を呼ぶときは何番目のコードのアドレスいくつ、という形で呼ぶ
こっちで進めよう
こっちの方が小回りが利きそう
今までexecute(code)でcodeを実行していたのを２段階に分ける
load(code)で仮想マシンにコードを追加し、execute()で最後に追加したコードを実行する
こういう形
vm = VM()
code = Compiler().compile(expr)
vm.load(code)
vm.execute()
最後に追加したコードだけでいいのかどうかわからないが必要な使い方も思いつかないのでこれで
必要になったらload(code)がコードの番号を返してexecute(ncode)で指定した番号のコードを実行するようにすればいいだろう
コードを（複数）覚えておくためのself._codesと、現在実行中のコードを指すself._ncodeを追加
def __init__(self):
self._codes = []
...
self._ncode = 0
self._ip = 0
...
コードを追加する
def load(self, code):
self._codes.append(code)
コードの実行
あちこちいじっているけれども関数関連ではaddrの代わりに[ncode, addr]を使うようにしているだけ
jump系は他のコードに飛ぶことはないのでaddrだけ扱っておけば足りる
def execute(self):
...
self._ncode = len(self._codes) - 1
self._ip = 0
while (inst := self._codes[self._ncode][self._ip]) != ["halt"]:
match inst:
...
case ["func", addr, params]:
self._stack.append(["closure", [self._ncode, addr], params, self._env])
...
case ["call"]:
self._call()
continue
case ["ret"]:
[self._ncode, self._ip], self._env = self._call_stack.pop()
continue
...
def _call(self):
match self._stack.pop():
case ["closure", [ncodes, addr], params, env]:
args = [self._stack.pop() for _ in params]
self._call_stack.append([[self._ncode, self._ip + 1], self._env])
self._env = Environment(env)
for param, val in zip(params, args):
self._env.define(param, val)
self._ncode, self._ip = [ncodes, addr]
case unexpected:
assert False, f"Unexpected call: {unexpected}"
テスト用のコードもちょっと書き換えて
def run(vm, expr):
print(f"\nSource:\n{expr}")
code = Compiler().compile(expr)
print("Code:")
for i, inst in enumerate(code):
print(f"{i:3}: {inst}")
print("Output:")
vm.load(code)
return vm.execute()
def test_run(vm, expr, expected):
result = run(vm, expr)
print(f"Expected Result: {expected}")
print(f"Actual Result : {result}")
assert expected == result
vm = VM()
...
run(vm, ["define", "myadd", ["func", ["a", "b"], ["add", "a", "b"]]])
test_run(vm, ["myadd", 5, 6], 11)
できた
Source:
['define', 'myadd', ['func', ['a', 'b'], ['add', 'a', 'b']]]
Code:
0: ['jump', 5]
1: ['get', 'b']
2: ['get', 'a']
3: ['op', 'add']
4: ['ret']
5: ['func', 1, ['a', 'b']]
6: ['def', 'myadd']
7: ['halt']
Output:
Source:
['myadd', 5, 6]
Code:
0: ['const', 6]
1: ['const', 5]
2: ['get', 'myadd']
3: ['call']
4: ['halt']
Output:
Expected Result: 11
Actual Result : 11
kb84tkhrclass Compiler: ... def _op(self, op, args): for arg in args[-1::-1]: self._expr(arg) if isinstance(op, str) and op in VM.ops: self._code.append(["op", op]) else: self._expr(op) self._code.append(["call"])...
ちょっとここの実装はうまくない気がしている
これまでの実装と非互換があるしなんとなくキレイじゃない
はじめの方でadd・sub・equalをインストラクションとして実装したのを引きずってたけれども結局のところ組み込み関数として実装するのがよさそう
コンパイラはなんでもかんでも関数としてcallする
シンプル
class Compiler:
...
def _op(self, op, args):
for arg in args[-1::-1]:
self._expr(arg)
self._expr(op)
self._code.append(["call"])
仮想マシン側
既存の実装と同じように組み込み関数として環境に入れる
class VM:
def __init__(self):
self._env = Environment()
self._load_builtins()
def _load_builtins(self):
builtins = {
"add": lambda s: s.append(s.pop() + s.pop()),
"sub": lambda s: s.append(s.pop() - s.pop()),
"equal": lambda s: s.append(s.pop() == s.pop()),
"print": lambda s: [print(s.pop()), s.append(None)]
}
for name, func in builtins.items():
self._env.define(name, func)
self._env = Environment(self._env)
_call()ではスタックのトップを見てcallableだったら呼ぶ
だけ
def _call(self):
match self._stack.pop():
case f if callable(f):
f(self._stack)
self._ip += 1
...
opの処理は不要になったのでここは消す
case ["op", op]:
VM.ops[op](self._stack)
これでおしまいですか？
おしまいです
test_run(vm, ["add", 5, 6], 11)
動きます
Source:
['add', 5, 6]
Code:
0: ['const', 6]
1: ['const', 5]
2: ['get', 'add']
3: ['call']
4: ['halt']
Output:
Expected Result: 11
Actual Result : 11
すっきりしたしEvaluatorとの互換性も上がったはず！
kb84tkhr
Evaluatorとの互換性も上がったはず！
ということで構文解析付きの処理系のEvaluatorをCompilerとVMで置き換えてみた
あとInterpreterを書き換え
class Interpreter:
def __init__(self):
self._vm = VM()
def go(self, src):
ast = Parser(src).parse()
code = Compiler().compile(ast)
self._vm.load(code)
return self._vm.execute()
これでこういうコードが動かせるようになった
i = Interpreter()
i.go("""
fib := func (n) do
if n == 0 then 0
elif n == 1 then 1
else fib(n - 1) + fib(n - 2) end
end;
print(fib(10))
""")
テストもほぼ動く
ここ以外
# self.assertEqual(self.printed("print()"), (None, "\n"))
# self.assertEqual(self.printed("print(5, 6)"), (None, "5 6\n"))
これは想定内（とかいいつつテストが失敗してから気づいた
あんま関係ない（と思う）んだけど、変数が見つからなかったときにVariableNotFoundErrorが上がるようになったのでエラーをテストするメソッドを書き換えた
def fails(self, src):
try:
self.i.go(src)
except (AssertionError, VariableNotFoundError):
return True
else:
return False
Python 3.12なのでexcept AssertionError | VariableNotFoundError:と書けると思うんだけどどうしてもエラーを取れなかった
Traceback (most recent call last):
File "/workspaces/toig/test_toig.py", line 54, in test_sequence
self.assertTrue(self.fails(";"))
^^^^^^^^^^^^^^^
File "/workspaces/toig/test_toig.py", line 18, in fails
except AssertionError | VariableNotFoundError:
TypeError: catching classes that do not inherit from BaseException is not allowed
なぜだろう
issubclass(VariableNotFoundError, BaseException)はTrueなのになあ
kb84tkhrもとのファイルに戻って機能追加
今回は末尾呼び出し最適化からやってみよう
というのはcallのあとがretだったら末尾、でいいよねーと軽く考えていたから
なのでこれくらいで済むだろうと
def _call(self):
match self._stack.pop():
...
case ["closure", [ncodes, addr], params, env]:
args = [self._stack.pop() for _ in params]
if self._codes[self._ncode][self._ip + 1] != ["ret"]:
self._call_stack.append([[self._ncode, self._ip + 1], self._env])
self._env = Environment(env)
for param, val in zip(params, args):
self._env.define(param, val)
self._ncode, self._ip = [ncodes, addr]
...
これはこれで動くんだけれども漏れがある
thn式は本来末尾位置なんだけれどもcallのあとはjumpなので上のコードでは末尾と判定されない
ということは、コンパイラの方で考える必要がありそう
コンパイラ側でやるにしても、今のコンパイラはthn式の評価中っていう情報はもってないし
いま末尾だよーといって上から教えてやるしかないかな
コンパイラからVMにここは末尾だよと伝えるにはcallのオペランドにするか別インストラクションにするか
kb84tkhr末尾になりうるのは関数本体・thn式・els式・seq式の最後の式、かな
引数として持ちまわる感じだろうか
そこら中に引数が必要になるけど、オブジェクトのプロパティにすると戻し問題が発生しそう
envと同じ
根幹は_op()
is_tailならcall_tailのインストラクションを出力する
引数かどうかをオペランドで持たせるようにすると既存のコードの書き換えが発生するのでとりあえず新しいインストラクションを追加する方針で
argsやopは末尾位置ではないのでis_tailをFalseにして_expr()を呼ぶようにする
def _op(self, op, args, is_tail):
for arg in args[-1::-1]:
self._expr(arg, False)
self._expr(op, False)
if is_tail:
self._code.append(["call_tail"])
else:
self._code.append(["call"])
関数本体は末尾
def _func(self, params, body):
skip_jump = self._current_addr()
self._code.append(["jump", None])
func_addr = self._current_addr()
self._expr(body, True) # ここ
self._code.append(["ret"])
self._set_operand(skip_jump, self._current_addr())
self._code.append(["func", func_addr, params])
seqの最後の式は、seq全体が末尾にあれば末尾
def _seq(self, exprs, is_tail):
if len(exprs) == 0: return
for expr in exprs[:-1]:
self._expr(expr, False)
self._code.append(["pop"])
self._expr(exprs[-1], is_tail) # ここ
thnやelsはif全体が末尾にあれば末尾
def _if(self, cnd, thn, els, is_tail):
self._expr(cnd, False)
els_jump = self._current_addr()
self._code.append(["jump_if_false", None])
self._expr(thn, is_tail) # ここ
end_jump = self._current_addr()
self._code.append(["jump", None])
self._set_operand(els_jump, self._current_addr())
self._expr(els, is_tail) # ここ
self._set_operand(end_jump, self._current_addr())
defineやassignの値部分は非末尾（だよな？
def _expr(self, expr, is_tail):
match expr:
case None | bool(_) |int(_):
self._code.append(["const", expr])
case ["func", params, body]:
self._func(params, body)
case str(name):
self._code.append(["get", name])
case ["define", name, val]:
self._expr(val, False) # ここ
self._code.append(["def", name])
case ["assign", name, val]:
self._expr(val, False) # ここ
self._code.append(["set", name])
case ["seq", *exprs]:
self._seq(exprs, is_tail)
case ["if", cnd, thn, els]:
self._if(cnd, thn, els, is_tail)
case [op, *args]:
self._op(op, args, is_tail)
case unexpected:
assert False, f"Unexpected expression: {unexpected}"
トップレベルの式は非末尾（引き継ぐべきコールスタックがないので
def compile(self, expr):
self._expr(expr, False)
self._code.append(["halt"])
return self._code
call_tailインストラクションの追加
コールスタックを使いまわすだけでcallとほぼ同じなのでフラグを渡して使いまわす
class VM:
...
def execute(self):
...
while (inst := self._codes[self._ncode][self._ip]) != ["halt"]:
match inst:
...
case ["call"]:
self._call(False)
continue
case ["call_tail"]:
self._call(True)
continue
...
def _call(self, is_tail):
match self._stack.pop():
...
case ["closure", [ncodes, addr], params, env]:
args = [self._stack.pop() for _ in params]
if not is_tail: # ここ
self._call_stack.append([[self._ncode, self._ip + 1], self._env])
if len(self._call_stack) > 1000: # ここも
assert False, "Call stack overflow"
self._env = Environment(env)
for param, val in zip(params, args):
self._env.define(param, val)
self._ncode, self._ip = [ncodes, addr]
...
if len(self._call_stack) > 1000の判定は末尾再帰がうまくいっているかどうかてすとするためにわざとつけたチェック
kb84tkhrテストだよー
els式で末尾呼び出し
run(vm, ["define", "loop_els", ["func", ["n"],
["if", ["equal", "n", 0], 0, ["loop_els", ["sub", "n", 1]]]
]])
call_tailになっている
Source:
['define', 'loop_els', ['func', ['n'], ['if', ['equal', 'n', 0], 0, ['loop_els', ['sub', 'n', 1]]]]]
Code:
0: ['jump', 15]
1: ['const', 0]
2: ['get', 'n']
3: ['get', 'equal']
4: ['call']
5: ['jump_if_false', 8]
6: ['const', 0]
7: ['jump', 14]
8: ['const', 1]
9: ['get', 'n']
10: ['get', 'sub']
11: ['call']
12: ['get', 'loop_els']
13: ['call_tail'] ← ここ
14: ['ret']
15: ['func', 1, ['n']]
16: ['def', 'loop_els']
17: ['halt']
Output:
10000回ループ
test_run(vm, ["loop_els", 10000], 0)
大丈夫
Source:
['loop_els', 10000]
Code:
0: ['const', 10000]
1: ['get', 'loop_els']
2: ['call']
3: ['halt']
Output:
Expected Result: 0
Actual Result : 0
thn式、seq式の最後の式でも同様に想定通り動作
末尾位置じゃないと
run(vm, ["define", "loop_not_tail", ["func", ["n"],
["if", ["equal", "n", 0], 0, ["add", ["loop_not_tail", ["sub", "n", 1]], 1]]
]])
call_tailにならない
Source:
['define', 'loop_not_tail', ['func', ['n'], ['if', ['equal', 'n', 0], 0, ['add', ['loop_not_tail', ['sub', 'n', 1]], 1]]]]
Code:
0: ['jump', 18]
1: ['const', 0]
2: ['get', 'n']
3: ['get', 'equal']
4: ['call']
5: ['jump_if_false', 8]
6: ['const', 0]
7: ['jump', 17]
8: ['const', 1]
9: ['const', 1]
10: ['get', 'n']
11: ['get', 'sub']
12: ['call']
13: ['get', 'loop_not_tail']
14: ['call'] # ここ
15: ['get', 'add']
16: ['call_tail'] # ここが`call_tail`になっても役に立たない
17: ['ret']
18: ['func', 1, ['n']]
19: ['def', 'loop_not_tail']
20: ['halt']
Output:
実行すると
run(vm, ["loop_not_tail", 10000])
コールスタック溢れました
AssertionError: Call stack overflow
自分自身を呼んでいるかは関係ない
run(vm, ["define", "even", ["func", ["n"],
["if", ["equal", "n", 0], True, ["odd", ["sub", "n", 1]]]
]])
run(vm, ["define", "odd", ["func", ["n"],
["if", ["equal", "n", 0], False, ["even", ["sub", "n", 1]]]
]])
ちゃんと末尾呼び出し最適化になっている
（だから末尾再帰最適化とは言わないようにしている）
Source:
['define', 'even', ['func', ['n'], ['if', ['equal', 'n', 0], True, ['odd', ['sub', 'n', 1]]]]]
Code:
0: ['jump', 15]
1: ['const', 0]
2: ['get', 'n']
3: ['get', 'equal']
4: ['call']
5: ['jump_if_false', 8]
6: ['const', True]
7: ['jump', 14]
8: ['const', 1]
9: ['get', 'n']
10: ['get', 'sub']
11: ['call']
12: ['get', 'odd']
13: ['call_tail'] ← ここ
14: ['ret']
15: ['func', 1, ['n']]
16: ['def', 'even']
17: ['halt']
Output:
Source:
['define', 'odd', ['func', ['n'], ['if', ['equal', 'n', 0], False, ['even', ['sub', 'n', 1]]]]]
Code:
0: ['jump', 15]
1: ['const', 0]
2: ['get', 'n']
3: ['get', 'equal']
4: ['call']
5: ['jump_if_false', 8]
6: ['const', False]
7: ['jump', 14]
8: ['const', 1]
9: ['get', 'n']
10: ['get', 'sub']
11: ['call']
12: ['get', 'even']
13: ['call_tail'] ← ここ
14: ['ret']
15: ['func', 1, ['n']]
16: ['def', 'odd']
17: ['halt']
Output:
末尾呼び出し版のフィボナッチも
run(vm, ["define", "fib_tail", ["func", ["n"], ["seq",
["define", "rec", ["func", ["k", "a", "b"],
["if", ["equal", "k", "n"],
"a",
["rec", ["add", "k", 1], "b", ["add", "a", "b"]]]
]],
["rec", 0, 0, 1]
]]])
run(vm, ["print", ["fib_tail", 10000]])
動作する
Source:
['define', 'fib_tail', ['func', ['n'], ['seq', ['define', 'rec', ['func', ['k', 'a', 'b'], ['if', ['equal', 'k', 'n'], 'a', ['rec', ['add', 'k', 1], 'b', ['add', 'a', 'b']]]]], ['rec', 0, 0, 1]]]]
Code:
0: ['jump', 30]
1: ['jump', 21]
2: ['get', 'n']
3: ['get', 'k']
4: ['get', 'equal']
5: ['call']
6: ['jump_if_false', 9]
7: ['get', 'a']
8: ['jump', 20]
9: ['get', 'b']
10: ['get', 'a']
11: ['get', 'add']
12: ['call']
13: ['get', 'b']
14: ['const', 1]
15: ['get', 'k']
16: ['get', 'add']
17: ['call']
18: ['get', 'rec']
19: ['call_tail']
20: ['ret']
21: ['func', 2, ['k', 'a', 'b']]
22: ['def', 'rec']
23: ['pop']
24: ['const', 1]
25: ['const', 0]
26: ['const', 0]
27: ['get', 'rec']
28: ['call_tail']
29: ['ret']
30: ['func', 1, ['n']]
31: ['def', 'fib_tail']
32: ['halt']
Output:
Source:
['print', ['fib_tail', 10000]]
Code:
0: ['const', 10000]
1: ['get', 'fib_tail']
2: ['call']
3: ['get', 'print']
4: ['call']
5: ['halt']
Output:
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
ふう
kb84tkhr最近はだいぶGemini 2.5 Proさんのお世話になっている
コードを丸ごと食べさせてレビューしてもらったり
ウソをつくこともあるけれどもレビュアーとしてはとても優秀
「それだとthnの末尾呼び出し最適化が抜けますよ？」「seqの最後の式はTrueじゃなくてis_tail`渡すんじゃない？」くらいのレベルで見てくれる
なかなかすごい
だれかがこのコード書いて自分にレビュー依頼してきてもちょっと理解しきれない気がする
kb84tkhrさてletccやるか
letccが作りやすいんじゃないかってことで中間コードインタプリタ方式をやってみたわけだからここ大事
コンパイラ側ではletccが来たらまず継続をスタックに積み、次にnameというパラメタをひとつだけ持ち、bodyを本体に持つ関数をスタックに積んでcallする
つまりnameというパラメータに継続が入った状態でbodyを実行しているということ
letccは由緒正しいSchemeではcall/ccまたはcall-with-current-continuationというけれどもまさしくそのとおりだ
letccという名前もletがlambdaの糖衣構文に過ぎないことを考えればやってることをちゃんと表してはいるのだけれども
class Compiler:
...
def _expr(self, expr, is_tail):
match expr:
...
case ["letcc", name, body]:
self._letcc(name, body, is_tail)
...
...
def _letcc(self, name, body, is_tail):
cont_jump = self._current_addr()
self._code.append(["cc", None])
self._func([name], body)
if is_tail:
self._code.append(["call_tail"])
else:
self._code.append(["call"])
self._set_operand(cont_jump, self._current_addr())
ccでcallのあとのアドレスを覚えさせているのは、letccの継続を呼ぶとletccの次の式から実行が再開されることに対応している
次はVM側
「継続」と言ったけれども継続とは何ぞや
この実装では、実行中のアドレスと、環境と、スタックと、コールスタックをまとめて保存したもの
ループを回るときに持ち越される情報はこれしかないので、これを取っておけばいつでもその状態に戻せるというわけ
環境と違ってスタックは配列で記録しているので、保存するときにはまるごとコピー（[:]）している
class VM:
...
def execute(self):
...
while (inst := self._codes[self._ncode][self._ip]) != ["halt"]:
match inst:
...
case ["cc", addr]:
self._stack.append(["cont",
[self._ncode, addr], self._env, self._stack[:], self._call_stack[:]])
...
callされたのが（closureではなくて）継続だった場合、スタックには継続に渡された引数が入っているはずなのであとで使うためにpopしておく
現在のスタックは捨てられてしまうので
その後、アドレス・環境・スタック・コールスタックを上書きして、さきほど取っておいた値をあらためてスタックに積みなおす
この値が継続の値となる
やはりスタックはまるごとコピーする
継続を再利用するときに書き換わっていると困るので
class VM:
...
def _call(self, is_tail):
match self._stack.pop():
...
case ["cont", [ncodes, addr], env, stack, call_stack]:
val = self._stack.pop()
self._ncode, self._ip = [ncodes, addr]
self._env = env
self._stack = stack[:]
self._stack.append(val)
self._call_stack = call_stack[:]
...
想定通りコンパイルできてて動いてる
test_run(vm, ["letcc", "skip-to", ["add", ["skip-to", 5], 6]], 5)
↓
Source:
['letcc', 'skip-to', ['add', ['skip-to', 5], 6]]
Code:
0: ['cc', 11]
1: ['jump', 9]
2: ['const', 6]
3: ['const', 5]
4: ['get', 'skip-to']
5: ['call']
6: ['get', 'add']
7: ['call_tail']
8: ['ret']
9: ['func', 2, ['skip-to']]
10: ['call']
11: ['halt']
Output:
Expected Result: 5
Actual Result : 5
関数を飛び越えて継続したり継続を再利用しても動いてる
run(vm, ["define", "inner", ["func", ["raise"], ["raise", 5]]])
run(vm, ["define", "outer", ["func", [],
[ "letcc", "raise", ["add", ["inner", "raise"], 6]]]])
test_run(vm, ["outer"], 5)
run(vm, ["define", "add5", None])
test_run(vm, ["add", 5, ["letcc", "cc", ["seq", ["assign", "add5", "cc"], 6]]], 11)
test_run(vm, ["add5", 7], 12)
test_run(vm, ["add5", 8], 13)
CPSやステートマシンの実装の時よりは動きそう感がある
気がする
kb84tkhr再帰で書いたインタプリタから始めて
継続を実装するためにCPSとかステートマシンとか中間コードインタプリタとかやってきたわけだけれども
再帰では続きの計算がコールスタックに隠れてしまって取り出せないので自前のデータ構造とループで書き換えるということをやってたわけだな
再帰をループで書き換えるという意味では深さ優先探索（Depth First Search: DFS）を思い出す
そう考えなおしたらまた別の実装がないだろうか
kb84tkhr環境と違ってスタックは配列で記録しているので、保存するときにはまるごとコピー（[:]）している
やはりスタックはまるごとコピーする
継続を再利用するときに書き換わっていると困るので
環境みたいに値とポインタを持つオブジェクトでスタックを持てばコピーしなくていいんだろうね？
こんなクラスを作ったらself._stack = stack[:]の代わりにself._stack = stack.clone()と書いてスタック全体のコピーは避けられるようになる
class Stack:
class Node:
def __init__(self, val, prev):
self._val = val
self._prev = prev
def __repr__(self) -> str:
return f"Node({self._val!r})"
def __init__(self):
self._top = None
self._len = 0
def __len__(self):
return self._len
def __iter__(self):
node = self._top
while node is not None:
yield node._val
node = node._prev
def __repr__(self) -> str:
return f"Stack({", ".join(map(str, self))})"
def clone(self):
new_stack = Stack()
new_stack._top = self._top
new_stack._len = self._len
return new_stack
def is_empty(self):
return self._top is None
def push(self, val):
self._top = Stack.Node(val, self._top)
self._len += 1
def peek(self):
assert self._top is not None, "Peeking from empty stack"
return self._top._val
def pop(self):
assert self._top is not None, "Poping from empty stack"
val = self._top._val
self._top = self._top._prev
self._len -= 1
return val
どっちがいいかはシラネ
今どきはポインタ使ったデータ構造より配列の方が速いことが多いらしいし
でもPythonの配列は速くないし
さらにがんばるとpush()やpop()のたびにあたらしいStackオブジェクトを返すようにしてイミュータブルなデータ構造でスタックを表すこともできるようになるはず
でも"add": lambda s: s.push(s.pop() + s.pop()),みたいな書き方と相性よくなくない？と思ってやめた
うまくすっきり書けるかなあ
続きは配列による表現に戻って進める
kb84tkhrマクロやってみる
動くまでのイメージができてないけど
今回は実行中にマクロ展開するわけにはいかないだろう（たぶん
VMに渡す時点ですべてマクロ展開が終わってないとね
VMがコンパイラ呼ぶ、みたいなこともできなくはないかもしれないけど
まずは普通（と想像されるとおり）に実装する
普通にインタプリタでマクロ作ったときもあらかじめ全部マクロ展開してみようと思って一度挫折してるんだよな
展開するときにはCompilerの中でVM.executeするんだろうなあ
VMもまっさらのVMではなくて定義済みの関数とかは使えないといけない
まずVMを作っておいてCompilerに渡してやる必要がある？
quasiquoteとかどうなんの
マクロの中でマクロ呼んでたらさらに入れ子でVM.executeする？
ほんとに動くのかそれで
VMは._ipひとつしか持ってないし
あらたなVMのインスタンスを作って、定義済みの関数なんかはコピーしてやってから使う？
いや、execute()ごとにアドレス・スタック・コールスタックを持つようにするほうがいいか？
kb84tkhrまずガワから作ろう
Expanderクラスを作り、ASTをいったんExpander.expand()してからCompilerに渡す
Expander.expand()は渡されたASTをほとんどそのまま返すんだけれども、[<マクロ>, ...]という形のASTを受け取ったときだけマクロを展開して返す
いろいろ足りなくていいからまずは最低限そういう動きをするところまで
マクロを定義するのはいったん置いておき、組み込み関数と同じようにして組み込みマクロをPythonで書いておく
class Expander:
def __init__(self):
self._menv = Environment()
self._menv.define("when", lambda cnd, body: ["if", cnd, body, None])
self._menv.define("when2", lambda cnd, body: ["when", cnd, body])
マクロ展開の本体
[op, *args]でopが名前でその名前のマクロが_menvに存在したら
そのマクロをargsを引数にして呼び出す
返ってきた結果がまたマクロかもしれないのでさらにself._expr()で（マクロなら）展開する
def expand(self, expr):
return self._expr(expr)
def _expr(self, expr):
match expr:
...
case [op, *args] :
if isinstance(op, str) and op in self._menv:
macro = self._menv.get(op)
return self._expr(macro(*args))
else:
...
...
inを使えるようにEnvironmentにメソッドを追加している
try-catchでも書けたけどすっきりしなかった
class Environment:
def __contains__(self, name):
try:
self.get(name)
return True
except VariableNotFoundError:
return False
それ以外の式は、マクロが出てくる可能性のあるところは展開してから返す
def _expr(self, expr):
match expr:
case None | bool(_) |int(_):
return expr
case ["func", params, body]:
return ["func", params, self._expr(body)]
case str(name):
return expr
case ["define", name, val]:
return ["define", name, self._expr(val)]
case ["assign", name, val]:
return ["assign", name, self._expr(val)]
case ["seq", *exprs]:
return ["seq"] + [self._expr(expr) for expr in exprs]
case ["if", cnd, thn, els]:
return ["if", self._expr(cnd), self._expr(thn), self._expr(els)]
case ["letcc", name, body]:
return ["letcc", name, self._expr(body)]
case [op, *args]:
if isinstance(op, str) and op in self._menv:
...
else:
return [op] + [self._expr(arg) for arg in args]
case unexpected:
assert False, f"Unexpected expression: {unexpected}"
exprをそのままCompilerに渡さず、いったんexpand()してから渡す
def run(vm, expr):
print(f"\nSource:\n{expr}")
expanded = Expander().expand(expr)
print(f"Expanded:\n{expanded}")
code = Compiler().compile(expanded)
...
できてるみたい
test_run(vm, ["when", ["equal", 5, 5], 6], 6)
test_run(vm, ["when", ["equal", 5, 6], "notdefinedvar"], None)
test_run(vm, ["add", 7, ["when", ["equal", 5, 5], 6]], 13)
test_run(vm, ["when2", ["equal", 5, 5], 6], 6)
test_run(vm, ["when2", ["equal", 5, 6], "notdefinedvar"], None)
実行結果から展開前後の式だけ抜粋
Source:
['when', ['equal', 5, 5], 6]
Expanded:
['if', ['equal', 5, 5], 6, None]
Source:
['when', ['equal', 5, 6], 'notdefinedvar']
Expanded:
['if', ['equal', 5, 6], 'notdefinedvar', None]
Source:
['add', 7, ['when', ['equal', 5, 5], 6]]
Expanded:
['add', 7, ['if', ['equal', 5, 5], 6, None]]
Source:
['when2', ['equal', 5, 5], 6]
Expanded:
['if', ['equal', 5, 5], 6, None]
Source:
['when2', ['equal', 5, 6], 'notdefinedvar']
Expanded:
['if', ['equal', 5, 6], 'notdefinedvar', None]
kb84tkhrユーザ定義のマクロの実装に入る
とりあえずquoteの実装
def _expr(self, expr):
match expr:
...
case ["q", elem]:
return expr
...
return exprするcaseはまとめて最後にcase _: return exprでもいいと思うけれどもとりあえず安全のため個別に書く
class Compiler:
def _expr(self, expr, is_tail):
match expr:
...
case ["q", elem]:
self._code.append(["const", elem])
...
test_run(vm, ["q", 5], 5)
test_run(vm, ["q", ["add", 5, 6]], ["add", 5, 6])
できた
Source:
['q', 5]
Expanded:
['q', 5]
Code:
0: ['const', 5]
1: ['halt']
Output:
Expected Result: 5
Actual Result : 5
Source:
['q', ['add', 5, 6]]
Expanded:
['q', ['add', 5, 6]]
Code:
0: ['const', ['add', 5, 6]]
1: ['halt']
Output:
Expected Result: ['add', 5, 6]
Actual Result : ['add', 5, 6]
kb84tkhr次はVMにマクロを展開させるしくみを入れる
マクロ定義
["define", "my_macro", ["macro", ["a"], ...]]のように定義したいところだけれども右辺がマクロなのかどうか判定するのがめんどくさそう
あとでアイデアが浮かぶかもしれないけどとりあえず専用の構文を作る
クロージャに何か覚えておく、みたいなのはなしで仮引数のリストと本体だけ覚えておく
defmacroはマクロ展開したら用済みなので消えてほしいんだけれども消えるのは無理なのでNoneを返している
def _expr(self, expr):
match expr:
...
case ["defmacro", name, params, body]:
self._menv.define(name, ["macro", params, self._expr(body)])
return None
...
マクロ展開
["macro", params, body]の形だったらVMを作って実引数を評価しないまま仮引数と結び付けて定義したらマクロ本体をコンパイルして実行し、結果を返す
def _expr(self, expr):
match expr:
...
case [op, *args] :
if isinstance(op, str) and op in self._menv:
macro = self._menv.get(op)
return self._expr(self._macro(macro, args))
else:
return [op] + [self._expr(arg) for arg in args]
...
def _macro(self, macro, args):
match macro:
case m if callable(m):
return self._expr(m(*args))
case ["macro", params, body]:
vm = VM()
for param, arg in zip(params, args):
vm._env.define(param, arg)
code = Compiler().compile(body)
vm.load(code)
expanded = vm.execute()
return expanded
今の道具立てではたいしたことはできないが
test_run(vm, ["seq",
["defmacro", "foo", [], ["q", ["add", 5, 6]]],
["foo"]
], 11)
展開はされた
Source:
['seq', ['defmacro', 'foo', [], ['q', ['add', 5, 6]]], ['foo']]
Expanded:
['seq', None, ['add', 5, 6]]
Code:
0: ['const', None]
1: ['pop']
2: ['const', 6]
3: ['const', 5]
4: ['get', 'add']
5: ['call']
6: ['halt']
Output:
Expected Result: 11
Actual Result : 11
None周りがちょっともったいない感じだがそこは織り込み済み
引数がうまく扱われているかはまだわからない
がいったんコミットする
kb84tkhrunquoteとunquote_splicingを実装する
ただのquoteはいずれ使いづらくなるのでqにquasiquoteの仕事をさせることにする
配列がなくてもquasiquoteがあればそこそこマクロ書けるし
なんとなくqの名前をquoteに変えた
短くしてもそれほど嬉しさは増さなかった気がするので
unquoteとunquote_splicingもそのままの名前を使おう
unquote_splicingはさすがに長いけど
Expanderは流すだけ
class Expander:
def _expr(self, expr):
match expr:
...
case ["quote", elem]:
return ["quote", self._quote(elem)]
...
def _quote(self, expr):
match expr:
case ["unquote", elem]:
return ["unquote", self._expr(elem)]
case ["unquote_splicing", elem]:
return ["unquote_splicing", self._expr(elem)]
case _: return expr
Compilerでがんばる
_quoteの構造はいままでと同じで、評価する代わりにコードを出力していく
splicingの処理では、左から順番に見ていってスタックに積み、素直に配列に足していくと逆順になってしまうのでスタックのいちばん上とその次を入れ替えるswapという演算を追加している
あと、配列の末尾に要素を付け足すappendも
class Compiler:
def _expr(self, expr, is_tail):
match expr:
...
case ["quote", elem]:
self._quote(elem)
...
def _quote(self, expr):
def _quote_elements(elems):
self._code.append(["const", []])
for elem in elems:
match elem:
case ["unquote_splicing", e]:
self._expr(e, False)
self._code.append(["get", "swap"])
self._code.append(["call"])
self._code.append(["get", "add"])
self._code.append(["call"])
case e:
self._quote(e)
self._code.append(["get", "swap"])
self._code.append(["call"])
self._code.append(["get", "append"])
self._code.append(["call"])
match expr:
case ["unquote", elem]: return self._expr(elem, False)
case [*elems]: return _quote_elements(elems)
case elem: self._code.append(["const", elem])
class VM:
def _load_builtins(self):
def swap(s): s[-1], s[-2] = s[-2], s[-1]
builtins = {
...
"swap": swap,
...
"append": lambda s: s.append(s.pop() + [s.pop()]),
...
}
unquote・unquote_splicing・その入れ子を試すテストケース
test_run(vm, ["seq",
["defmacro", "foo", ["a", "b"], ["quote",
["add", ["unquote_splicing", ["quote",
[["unquote", "a"], ["unquote", "b"]]]]]]],
["foo", ["sub", 8, 5], ["sub", 7, 6]]
], 4)
展開された
Source:
['seq', ['defmacro', 'foo', ['a', 'b'], ['quote', ['add', ['unquote_splicing', ['quote', [['unquote', 'a'], ['unquote', 'b']]]]]]], ['foo', ['sub', 8, 5], ['sub', 7, 6]]]
Expanded:
['seq', None, ['add', ['sub', 8, 5], ['sub', 7, 6]]]
...
Expected Result: 4
Actual Result : 4
kb84tkhrGeminiさんにコードレビューをお願いしたところ、「独創的」だけどちゃんと動くと評価されました
普通はExpanderでやるんだってさ
はーなるほどね
そうするとCompiler以降はquasiquote的な処理はいらなくなると
それは思いつかなかった なんでかな
Expanderはマクロを展開するだけとしか思ってなかったからか
配列扱うようにもしてなかったし
やってみよう
kb84tkhrまずは配列を使えるようにしないといけない
いまのところ、ただ配列をつくれればいいだけだから
いつもどおり組み込み関数のarrayを作って・・・
ダメか
今までと違って組み込み関数側では引数の数がわからないのでスタックからいくつpopしていいか判断がつかない
丸ごと配列にしてからスタックに積む？・・・こともできそうにないかなあ
["array", N]というインストラクションを作って、スタックの上位N個を配列にしてスタックに積む、ということにしよう
["array", 5, 6, 7]だったら5、6、7を順番にスタックに積んで、["array", 3]を実行するとスタックに[5, 6, 7]が残るという寸法
ほかの値は5なりNoneなりそのまま書いてやればそのままスタックに積んでくれるんだけれども[5, 6, 7]って書いちゃうと6, 7という引数を5という関数に適用しちゃうので・・・
スマートじゃない気はするが
例によって式をただの配列じゃなくてほかの型にすれば配列をただ[5, 6, 7]と書けるようになるんだけれどもそれはそれで式を手書きするときに面倒
構文解析ありならそれも可
こんな感じ
class Expander:
...
def _expr(self, expr):
match expr:
...
case ["array", *elems]:
return ["array"] + [self._expr(elem) for elem in elems]
...
...
class Compiler:
...
def _expr(self, expr, is_tail):
match expr:
...
case ["array", *elems]:
self._array(elems)
...
...
def _array(self, elems):
for elem in elems: self._expr(elem, False)
self._code.append(["array", len(elems)])
...
class VM:
...
def execute(self):
...
while (inst := self._codes[self._ncode][self._ip]) != ["halt"]:
match inst:
...
case ["array", size]:
arr = [self._stack.pop() for _ in range(size)]
self._stack.append(list(reversed(arr)))
...
これが
test_run(vm, ["array", ["add", 5, 6], ["add", 7, 8]], [11, 15])
こうなる
Source:
['array', ['add', 5, 6], ['add', 7, 8]]
Expanded:
['array', ['add', 5, 6], ['add', 7, 8]]
Code:
0: ['const', 6]
1: ['const', 5]
2: ['get', 'add']
3: ['call']
4: ['const', 8]
5: ['const', 7]
6: ['get', 'add']
7: ['call']
8: ['array', 2]
9: ['halt']
Output:
Expected Result: [11, 15]
Actual Result : [11, 15]
さてquoteは楽に書けるのか
この方式ではquasiquoteはexpand()中にarrayとquoteに展開されてしまい、compile()時にはなくなってしまう
quoteはquasiquoteで書けるからquasiquoteをquoteという名前にしてquasiquoteはなくしてしまおうと思ったけれどもそれ以上に意味合いが変わってしまったのでquoteは残してquasiquoteはquasiquoteで作ることにする
class Expander:
...
def _expr(self, expr):
match expr:
...
case ["quasiquote", elem]:
return self._quasiquote(elem)
...
def _quasiquote(self, expr):
def _quote_elements(elems):
arr = ["array"]
for elem in elems:
match elem:
case ["unquote_splicing", e]:
expanded = self._expr(e)
assert isinstance(expanded, list) and len(expanded) > 0, \
f"Cannot splice: {expanded}"
arr += expanded[1:]
case e:
arr += [self._quasiquote(e)]
return arr
match expr:
case ["unquote", elem]: return elem
case [*elems]: return _quote_elements(elems)
case elem: return ["quote", elem]
展開中の動作は違うけど結果は同じ
Expanderだけで済んでるのはいいことだろう 配列はいずれ作るだろうし
こっちの実装で進める
kb84tkhr今の実装はマクロを展開するたびにまっさらのVMを作るので、事前に関数を定義しておいても使うことができない
VMを使いまわしてユーザ定義関数をマクロ内で使えるようにする
Expanderは上位からVMを受け取ってそれを使う
class Expander:
def __init__(self, vm):
self._vm = vm
def _macro(self, macro, args):
match macro:
case m if callable(m):
return self._expr(m(*args))
case ["macro", params, body]:
self._vm._env = Environment(self._vm.env())
for param, arg in zip(params, args):
self._vm._env.define(param, arg)
code = Compiler().compile(body)
self._vm.load(code)
expanded = self._vm.execute()
return expanded
いままでrun()等で行っていた処理をInterpreterクラスとして書き換えた
別にこうしないといけないというわけではないがそろそろ潮時かなと
ExpanderにVMを渡している
class Interpreter:
def __init__(self):
self._vm = VM()
def __repr__(self) -> str:
return f"Interpreter({self._vm})"
def go(self, expr):
expanded = Expander(self._vm).expand(expr)
code = Compiler().compile(expanded)
self._vm.load(code)
return self._vm.execute()
いままで同様に展開後のASTやコンパイル済みコードを表示しながら実行するメソッドも作っているけど省略
マクロ展開でユーザ関数を使うテスト
i = Interpreter()
i.go_verbose(["define", "my_add", ["func", ["a", "b"], ["add", "a", "b"]]])
i.go_test(["seq",
["defmacro", "bar", ["a", "b"], ["my_add", "a", "b"]],
["bar", ["sub"], [7, 6]]
], 1)
Source:
['define', 'my_add', ['func', ['a', 'b'], ['add', 'a', 'b']]]
Expanded:
['define', 'my_add', ['func', ['a', 'b'], ['add', 'a', 'b']]]
Code:
0: ['jump', 6]
1: ['get', 'b']
2: ['get', 'a']
3: ['get', 'add']
4: ['call_tail']
5: ['ret']
6: ['func', 1, ['a', 'b']]
7: ['def', 'my_add']
8: ['halt']
Output:
Source:
['seq', ['defmacro', 'bar', ['a', 'b'], ['my_add', 'a', 'b']], ['bar', ['sub'], [7, 6]]]
Expanded:
['seq', None, ['sub', 7, 6]]
Code:
0: ['const', None]
1: ['pop']
2: ['const', 6]
3: ['const', 7]
4: ['get', 'sub']
5: ['call']
6: ['halt']
Output:
Expected Result: 1
Actual Result : 1
kb84tkhrさて今のままだとマクロの定義が１回のrun()の間だけしか残ってないという致命的な問題がある。
._menvをVM側に覚えさせてrun()が終わっても忘れないようにする
VM側
class VM:
def __init__(self):
...
self._menv = Environment()
def menv(self):
return self._menv
Expander側
組み込みマクロの定義も消した
class Expander:
def _expr(self, expr):
match expr:
...
case ["defmacro", name, params, body]:
self._vm.menv().define(name, ["macro", params, self._expr(body)])
return None
...
case [op, *args] :
if isinstance(op, str) and op in self._vm.menv():
macro = self._vm.menv().get(op)
return self._expr(self._macro(macro, args))
...
消した組み込みマクロをテストで復活させる
今まではこれやってもすぐ忘れてしまうのでダメだった
i.go_verbose(["defmacro", "when", ["cnd", "body"], ["quasiquote",
["if", ["unquote", "cnd"], ["unquote", "body"], None]
]])
i.go_verbose(["defmacro", "when2", ["cnd", "body"], ["quasiquote",
["when", ["unquote", "cnd"], ["unquote", "body"]]
]])
定義と実行が分かれても動く
i.go_test(["when", ["equal", 5, 5], 6], 6)
i.go_test(["when", ["equal", 5, 6], "notdefinedvar"], None)
定義と実行が分かれても動く
i.go_verbose(["define", "my_add", ["func", ["a", "b"], ["add", "a", "b"]]])
i.go_verbose(["defmacro", "bar", ["a", "b"], ["my_add", "a", "b"]])
i.go_test(["bar", ["sub"], [7, 6]], 1)
kb84tkhr今のままだとマクロが展開されるたびにマクロ本体がコンパイルされ、VMにload()されてしまうのでCPUもメモリも無駄にしている
defmacroの時点でマクロをコンパイルしてload()し、展開時には実行するだけにして無駄を防ぐようにする
VMではこれまで、一番最後にload()したコードを実行するようにしていたが、以前にload()したコードも実行する必要が出てきたのでexcecute()で何番目のコードを実行するか指定できるようにする
何番目のコードかはload()が返すようにする
class VM:
def load(self, code):
self._codes.append(code)
return len(self._codes) - 1
def execute(self, ncode=None):
...
self._ncode = len(self._codes) - 1 if ncode is None else ncode
...
マクロ定義時にはbodyをコンパイルしてVMにロードしておき、ncodeとパラメータリストを覚えさせておく
関数みたいに生成時の環境を覚えておく必要ってないんじゃ？と思っている
スコープも作らないし
たとえ関数内でマクロを作ってもグローバルに使えてしまうけれども
逆にローカルで定義された関数や変数は見えないけれども
大人ならトップレベルで定義するよねということにしておく
トップレベルじゃなければエラーにするのが筋かもしれないがそこらへんは重視してないのでスルー
class Expander:
...
def _expr(self, expr):
match expr:
...
case ["defmacro", name, params, body]:
return self._defmacro(name, params, self._expr(body))
...
def _defmacro(self, name, params, body):
code = Compiler().compile(body)
ncode = self._vm.load(code)
self._vm.menv().define(name, ["macro", ncode, params])
return None
マクロ展開時は覚えさせておいたコードをncodeを使って呼ぶようにする
def _macro(self, macro, args):
match macro:
...
case ["macro", ncode, params]:
self._vm._env = Environment(self._vm.env())
for param, arg in zip(params, args):
self._vm._env.define(param, arg)
expanded = self._vm.execute(ncode)
return expanded
これでいいのか少々心配だけれどもテストは通ったのでcommit
kb84tkhr関数内でマクロ定義しても意味がない実装なのはいいとして
マクロ内で関数を定義して使うのはちゃんと動くのか？
動かない理由はないけれども
以前の実装だとこういうことができてたわけだが
["define", "let", ["macro", ["bindings", "body"], ["seq",
["define", "defines", ["func", ["bindings"],
["map", "bindings", ["func", ["b"], ["qq",
["define",
["!", ["first", "b"]],
["!", ["last", "b"]]]]]]]],
["qq", ["scope", ["seq",
["!!", ["defines", "bindings"]],
["!","body"]]]]]]]
これ動かそうと思ったら足りないものがいろいろと
配列関係の組み込み関数
def _load_builtins(self):
def get_at(s):
arr = s.pop(); index = s.pop(); s.append(arr[index])
def slice_(s):
arr = s.pop(); start = s.pop(); end = s.pop(); step = s.pop()
s.append(arr[slice(start, end, step)])
builtins = {
...
"get_at": get_at,
"slice": slice_,
...
}
ユーティリティ関数・マクロ
i.go_verbose(["define", "first", ["func", ["l"], ["get_at", "l", 0]]])
i.go_verbose(["define", "rest", ["func", ["l"], ["slice", "l", 1, None, None]]])
i.go_verbose(["define", "last", ["func", ["l"], ["get_at", "l", -1]]])
i.go_verbose(["define", "append", ["func", ["l", "a"], ["add", "l", ["array", "a"]]]])
i.go_verbose(["define", "foldl", ["func", ["l", "f", "init"],
["if", ["equal", "l", ["array"]],
"init",
["foldl", ["rest", "l"], "f", ["f", "init", ["first", "l"]]]]]])
i.go_verbose(["define", "map", ["func", ["l", "f"],
["foldl", "l", ["func", ["acc", "e"], ["append", "acc", ["f", "e"]]], ["array"]]]])
i.go_verbose(["defmacro", "scope", ["body"],
["quasiquote", [["func", [], ["unquote", "body"]]]]])
これだけ揃ってletが書ける
i.go_verbose(["defmacro", "let", ["bindings", "body"], ["seq",
["define", "defines", ["func", ["bindings"],
["map", "bindings", ["func", ["b"], ["quasiquote",
["define",
["unquote", ["first", "b"]],
["unquote", ["last", "b"]]]]]]]],
["quasiquote", ["scope", ["seq",
["unquote_splicing", ["defines", "bindings"]],
["unquote","body"]]]]]])
i.go_test(["let", [["a", 5], ["b", 6]], ["add", "a", "b"]], 11)
動いた
考え方は間違ってはいない、と思っていいのかな
（よいかどうかは知らない）
kb84tkhr動いた、とかしれっと言ってるけど実は大バグを直している
こっちのコミットが先
arrを継ぎ足していくところ
def _quasiquote(self, expr):
def _quote_elements(elems):
arr = ["array"]
for elem in elems:
match elem:
case ["unquote_splicing", e]:
arr = ["add", arr, self._expr(e)]
case _:
arr = ["add", arr, ["array", self._quasiquote(elem)]]
return arr
match expr:
case ["unquote", elem]: return elem
case [*elems]: return _quote_elements(elems)
case elem: return ["quote", elem]
実行時につぎ足さないといけないのに、展開中につぎ足そうとしておかしなことをしていた
これくらいでも動いてなかった
i.go_verbose(["define", "my_array", ["func", [], ["array", 5, 6]]])
i.go_test(["quasiquote", ["add", ["unquote_splicing", ["my_array"]]]], ["add", 5, 6])
だいぶ頭がついていかなくなってるよね
kb84tkhrマクロはできたことにして次進もう
あとはなんだ
rest引数か
例によって仕事はVMにさせるとして、extend()はどっかから持ってくるとして、問題はここだ
args = [self._stack.pop() for _ in params]
引数の個数が可変になるのでparamsの数だけpopすればいい、というものではなくなる
案１：pushした引数の個数をcallのオペランドに追加する
案２：最初に何か目印（["arg_end"]とか)をpushしてから引数を積む
案３：ひとつの配列にまとめてから積む
VMっぽいのは案１な気がする
案２はインストラクションをシンプルに保つという意味はある
このへん見たら配列をばらして渡した後くっつけなおしてるだけなのではと思って案３もありかも？と思ったけど、ひとつひとつの引数を評価してからくっつけなきゃいけないからそうもいかないか
schemeのlambda x ...を思い浮かべてそういうのもありかなと思ったんだけど
class Compiler:
def _op(self, op, args, is_tail):
for arg in args[-1::-1]: # こことか
self._expr(arg, False)
self._expr(op, False)
if is_tail:
self._code.append(["call_tail"])
else:
self._code.append(["call"])
class VM:
def _call(self, is_tail):
match self._stack.pop():
...
case ["closure", [ncodes, addr], params, env]:
args = [self._stack.pop() for _ in params] # こことか
...
self._env = Environment(env)
for param, val in zip(params, args):
self._env.define(param, val)
self._ncode, self._ip = [ncodes, addr]
...
案１でいく
callが引数の数を受け取ってその数だけスタックから取ってくるようにする
class VM:
def execute(self, ncode=None):
...
while (inst := self._codes[self._ncode][self._ip]) != ["halt"]:
match inst:
...
case ["call", nargs]:
self._call(nargs, False)
continue
case ["call_tail", nargs]:
self._call(nargs, True)
continue
...
def _call(self, nargs, is_tail):
match self._stack.pop():
...
case ["closure", [ncodes, addr], params, env]:
args = [self._stack.pop() for _ in range(nargs)]
...
コンパイラ側は引数をいくつスタックに積んだかをオペランドに入れて渡す
class Compiler:
def _op(self, op, args, is_tail):
for arg in args[-1::-1]:
self._expr(arg, False)
self._expr(op, False)
if is_tail:
self._code.append(["call_tail", len(args)])
else:
self._code.append(["call", len(args)])
関数を呼んだらextend()がいつもと同じように仕事をする
class VM:
def _call(self, nargs, is_tail):
match self._stack.pop():
...
case ["closure", [ncodes, addr], params, env]:
...
self._env = Environment(env)
self._extend(params, args)
self._ncode, self._ip = [ncodes, addr]
...
def _extend(self, params, args):
if params == [] and args == []: return
assert len(params) > 0, \
f"Argument count doesn't match: `{params}, {args}`"
match params[0]:
case str(param):
assert len(args) > 0, \
f"Argument count doesn't match: `{params}, {args}`"
self._env.define(param, args[0])
self._extend(params[1:], args[1:])
case ["*", rest]:
rest_len = len(args) - len(params) + 1
assert rest_len >= 0, \
f"Argument count doesn't match: `{params}, {args}`"
self._env.define(rest, args[:rest_len])
self._extend(params[1:], args[rest_len:])
case unexpected:
assert False, f"Unexpected param: {unexpected}"
こういうのが動くようになった
i.go_test([["func", [["*", "rest"]], "rest"]], [])
i.go_test([["func", ["a", ["*", "rest"]], ["array", "a", "rest"]], 5], [5, []])
i.go_test([["func", ["a", ["*", "rest"]], ["array", "a", "rest"]], 5, 6], [5, [6]])
i.go_test([["func", ["a", ["*", "rest"]], ["array", "a", "rest"]], 5, 6, 7], [5, [6, 7]])
i.go_test([["func", [["*", "args"], "a"], ["array", "args", "a"]], 5], [[], 5])
i.go_test([["func", [["*", "args"], "a"], ["array", "args", "a"]], 5, 6], [[5], 6])
i.go_test([["func", [["*", "args"], "a"], ["array", "args", "a"]], 5, 6, 7], [[5, 6], 7])
i.go_test([["func", [["*", "args"], "a", "b"], ["array", "args", "a", "b"]], 5, 6, 7], [[5], 6, 7])
i.go_test([["func", ["a", ["*", "args"], "b"], ["array", "a", "args", "b"]], 5, 6, 7], [5, [6], 7])
i.go_test([["func", ["a", "b", ["*", "args"]], ["array", "a", "b", "args"]], 5, 6, 7], [5, 6, [7]])
kb84tkhrせっかくだから組み込み関数も可変長引数に対応させよう
組み込み関数が可変長引数に対応したら["array", ...]を組み込み関数にできるはず
もとはといえば引数がいくつあるかわからないので["array", ...]を特殊形式にしたのだから
callでは組み込み関数の引数にスタックだけでなく引数の個数も渡す
def _call(self, nargs, is_tail):
match self._stack.pop():
case f if callable(f):
f(nargs, self._stack)
self._ip += 1
渡された個数は使ったり使わなかったり
def _load_builtins(self):
def get_at(_, s):
arr = s.pop(); index = s.pop(); s.append(arr[index])
def slice_(_, s):
arr = s.pop(); start = s.pop(); end = s.pop(); step = s.pop()
s.append(arr[slice(start, end, step)])
builtins = {
"__builtins__": None,
"add": lambda _, s: s.append(s.pop() + s.pop()),
"sub": lambda _, s: s.append(s.pop() - s.pop()),
"equal": lambda _, s: s.append(s.pop() == s.pop()),
"not_equal": lambda _, s: s.append(s.pop() != s.pop()),
"array": lambda n, s: s.append([s.pop() for _ in range(n)]),
"get_at": get_at,
"slice": slice_,
"print": lambda _, s: s.append(print(s.pop()))
}
コンパイル時に["array", ...]を特別扱いしていた箇所は削除
class Compiler:
def _expr(self, expr, is_tail):
match expr:
...
# case ["array", *elems]: # 不要
# self._array(elems) # 不要
...
よし
kb84tkhrところで
_load_builtins()が太ってきたし
ビルトイン関数がVMそのものにとって必須というわけではないし
そろそろVMから追い出そう
どう書くのがいいかなあ
正直ただの関数の集まりなのでクラスはいらないんだけど
なにかまとまりにはしたいし他との統一感もあるのでクラスにはしておこう
別ファイルにする手もあるけどまあ流れで
単純にクラスで分けるとこうなるけどせっかくパーツを分けたのに
load()が巨大化したままなのはちょっともにょる
class Builtins:
@staticmethod
def load(env):
def get_at(_, s):
arr = s.pop(); index = s.pop(); s.append(arr[index])
def slice_(_, s):
arr = s.pop(); start = s.pop(); end = s.pop(); step = s.pop()
s.append(arr[slice(start, end, step)])
builtins = {
"__builtins__": None,
...
"print": lambda _, s: s.append(print(s.pop()))
}
for name, func in builtins.items():
env.define(name, func)
ほんとうはこんなふうに書きたい
でもbuiltins = { ... }の中でBuiltins.get_atを参照できない
@staticmethodで1行使うのは嫌だがあきらめる
@staticmethod def get_at()って書けたらいいのに
class Builtins:
@staticmethod
def get_at(_, s): ...
@staticmethod
def set_at(_, s): ...
builtins = { ... }
def load(env):
for name, func in builtins.items():
env.define(name, func)
builtinsの中でBuiltins.get_at等を参照しようとするとこうなる
class Builtins:
@staticmethod
def get_at(_, s):
arr = s.pop(); index = s.pop(); s.append(arr[index])
@staticmethod
def slice_(_, s):
arr = s.pop(); start = s.pop(); end = s.pop(); step = s.pop()
s.append(arr[slice(start, end, step)])
builtins = {}
@staticmethod
def load(env):
for name, func in Builtins.builtins.items():
env.define(name, func)
Builtins.builtins = {
"__builtins__": None,
"add": lambda _, s: s.append(s.pop() + s.pop()),
"sub": lambda _, s: s.append(s.pop() - s.pop()),
"equal": lambda _, s: s.append(s.pop() == s.pop()),
"not_equal": lambda _, s: s.append(s.pop() != s.pop()),
"array": lambda n, s: s.append([s.pop() for _ in range(n)]),
"get_at": Builtins.get_at,
"slice": Builtins.slice_,
"print": lambda _, s: s.append(print(s.pop()))
}
get_at()やslice_()をクラスの外で定義するのもいいんだけど
ていうかそれがいいんだけどほんとは
PEP8さんが関数と関数の間も２行空けようとするでしょ？
（だからフォーマッタ使ってないんだけど）
なんかPythonはクラスの外で関数定義するのはおすすめじゃないですよーって言われてる気がするんだよな
もにょるなー
だいたいですよ
Pythonがlambdaをいじめるからこうなるんですよ
こんな風に書かせてくれれば
"slice": lambda _, s:
arr = s.pop(); start = s.pop(); end = s.pop(); step = s.pop()
s.append(arr[slice(start, end, step)])
まあそのへんにして
VMクラスはすっきりする
class VM:
def __init__(self):
...
self._env = Environment()
Builtins.load(self._env)
self._env = Environment(self._env)
...
だからよしとする
kb84tkhrマクロでも可変長引数を扱えるようにここも直す
def _macro(self, macro, args):
match macro:
case ["macro", ncode, params]:
self._vm._env = Environment(self._vm.env())
for param, arg in zip(params, args):
self._vm._env.define(param, arg)
expanded = self._vm.execute(ncode)
return expanded
そういえば、ここはとりあえずの実装でVMの中身を見せてしまっててよくないからあとでリファクタリングしようと思ってたところだった
いっしょにやってしまう
スコープ作って引数をローカル変数のように定義してやってからexecute()してるわけだけれども
あれ、スコープ作ってるけど作ったスコープ捨ててないな
これってスコープがたまっていくんじゃね？
i.go_verbose(["seq",
["when", ["equal", 5, 5], 5],
["when", ["equal", 5, 5], 6],
["when", ["equal", 5, 5], 7],
["func", [], 5]
])
たまってくわー
スコープ捨てなきゃだわー
スコープ作って引数をローカル変数のように定義してやってからexecute()してスコープを捨てる
どう書くか
_extend()を外から呼べるようにして、あとnew_scope()とかdrop_scope()とかも作ってやればいいんだけれどもまだちょっと中が見えすぎてるような気がするなー
それくらいならいいのかなー
_envを直でいじるよりはずっといいけど
あるいはexecute()の引数にparamsとargsを追加しちゃう？
それはexecute()に役割持たせすぎか
ひとつめの案かなあ
_menvはmenv()で半分見せてるしそれに比べれば隠せてるとは言える
むしろenv()とset_env()を作る方が統一感があるのかも？
いや、_menv()は見せずにdefine_macro()とかで見せるのがいいのか？
こっちはおいとくか・・・？
なんか非対称だが
class VM:
# def env(self): # 消す
# return self._env # 消す
def menv(self): # 残す
return self._menv # 残す
...
def new_scope(self):
self._env = Environment(self._env)
def drop_scope(self):
assert isinstance(self._env, Environment)
assert self._env._parent is not None
self._env = self._env._parent
def extend(self, params, args): # _expandから改名
...
お膳立てが整ったら
class Expander:
def _macro(self, macro, args):
match macro:
# case m if callable(m):
# return self._expr(m(*args))
case ["macro", ncode, params]:
self._vm.new_scope()
self._vm.extend(params, args)
expanded = self._vm.execute(ncode)
self._vm.drop_scope()
return expanded
...
「組み込みマクロ」はなくなったので不要なコードを削除
i.go(["defmacro", "rest_param", ["a", ["*", "rest"]], ["quasiquote",
["array", ["quote", ["unquote", "a"]], ["quote", ["unquote", "rest"]]]
]])
i.go_test(["rest_param", ["add", 5, 1]],
[["add", 5, 1], []])
i.go_test(["rest_param", ["add", 5, 1], ["add", 6, 1], ["add", 7, 1]],
[["add", 5, 1], [["add", 6, 1], ["add", 7, 1]]])
できてるみたい
Source:
['rest_param', ['add', 5, 1]]
Expanded:
['array', ['quote', ['add', 5, 1]], ['quote', []]]
Code:
...
Output:
Expected Result: [['add', 5, 1], []]
Actual Result : [['add', 5, 1], []]
Source:
['rest_param', ['add', 5, 1], ['add', 6, 1], ['add', 7, 1]]
Expanded:
['array', ['quote', ['add', 5, 1]], ['quote', [['add', 6, 1], ['add', 7, 1]]]]
Code:
...
Output:
Expected Result: [['add', 5, 1], [['add', 6, 1], ['add', 7, 1]]]
Actual Result : [['add', 5, 1], [['add', 6, 1], ['add', 7, 1]]]
kb84tkhrコア機能はだいたいこれで実装したんじゃないかと思って構文解析入れようと思ったけど再帰マクロが書けなくて行き詰っている
i.go_verbose(["defmacro", "rec_macro", ["n"],
["if", ["equal", "n", 0],
0,
["quasiquote", ["add", ["unquote", ["rec_macro", ["sub", "n", 1]]], 1]]
]
])
i.go_test(["rec_macro", 3], 3)
VariableNotFoundError: rec_macro
defmacroを処理している途中ではrec_macroはまだ定義されていないので["rec_macro", ["sub", "n", 1]]が展開されず['get', 'rec_macro']というインストラクションが出力されてしまい、マクロ展開しようとしたVMはそんな関数ないよと言ってエラーにしてしまう
これはけっこう根本的な問題か・・・？
シンプルでいい感じに実装できてると思ってたけど大きく見直しが必要かもしれない
kb84tkhrあきらめてこんなふうにヘルパー関数を定義して使うことはできる
i.go_verbose(["defmacro", "rec_macro", ["n"], ["seq",
["define", "rec", ["func", ["n"],
["if", ["equal", "n", 0],
0,
["quasiquote", ["add", ["unquote", ["rec", ["sub", "n", 1]]], 1]]
]
]],
["rec", "n"]
]])
i.go_test(["rec_macro", 3], 3)
Source:
['rec_macro', 3]
Expanded:
['add', ['add', ['add', 0, 1], 1], 1]
...
これで常に対応できるかな・・・？
これでもそこまでひどい仕様ってことはない気がするけどちょっと寝かせてみよう
kb84tkhrやりたいことは今回作った中間コードインタプリタに構文解析をつけるってことなんだけど
まずやりやすいように整えていこう ぼちぼちと
tail_call_optimizationブランチから作業を続ける
そろそろファイルも分割するといいかなあ
スキャナ・パーザ・環境あたりは共用できるくらいにしてみたい
（ツリーウォーク）インタプリタ版と中間コードインタプリタ版を混在させられたりしないかな
この関数はツリーウォークで動かしておいてこっちは中間コードに落とすとか
まあそれは先のステップ
ic_rest_paramからファイルを持ってきたりファイル分割したりして比較しやすくしよう
やむを得ず変わっちゃったとこ以外にも気まぐれで変更しちゃったとことかあるんで
qをquoteにしたりとか
まずは持ってきてファイルを分割するところだけ
余り修正はしない（ちょっとやってしまったが
このタイミングで修正を入れても差分が埋もれてしまうので
従来の処理系のソースのファイル名は"toig"で始まり、中間コードインタプリタを実装したソースは"ici"で始まるようにした
原始的
circular importにならないような修正は入れた
kb84tkhrEnvironment関連から手を付ける
iciでこんな修正をしているのでtoig側に反映する
- 見つからなかったときは
VariableNotFoundErrorを投げるようにした -
__repr__()の表示を見やすくした -
inが使えるよう__contains__()を実装した -
define()やassign()がvalを返すようにした -
extend()をVM側に実装した
ここらへんを揃えるとici_environment.pyは不要になってtoig_environment.pyで代用できるようになる
ici.py
from toig_environment import Environment
from ici_evaluator import Expander, Compiler, VM
...
ici_evaluator.py
from toig_environment import Environment
...
kb84tkhr気まぐれで文法を変えたところはこれくらいだったかな・・・
置換でOKなひとたち
テストも含めて置換
置換しすぎには注意
arr→array
q→quote
qq→quasiquote
!→unquote
!!→unquote_splicing
忘れものがありませんように
kb84tkhrん？arrayを組み込み関数にしたつもりだったけど、特殊形式としての処理が残ってて想定通り動いてないぞ？
テストは動いてるけど想定どおりには動いてないってやつだなあ
誰だよレビューしたのは（いません
んー今直した方がいいかなあ
やっとくか
class Expander:
def _expr(self, expr):
match expr:
...
# case ["array", *elems]:
# return ["array"] + [self._expr(elem) for elem in elems]
...
class Compiler:
def _expr(self, expr, is_tail):
match expr:
...
# case ["array", *elems]:
# self._array(elems)
...
# def _array(self, elems):
# for elem in elems: self._expr(elem, False)
# self._code.append(["array", len(elems)])
class VM:
def execute(self, ncode=None):
...
while (inst := self._codes[self._ncode][self._ip]) != ["halt"]:
match inst:
...
# case ["array", size]:
# arr = [self._stack.pop() for _ in range(size)]
# self._stack.append(list(reversed(arr)))
...
この辺の処理を削除しても全部関数として扱うときに同じように処理される
まあ見つけてよかった
kb84tkhriciの方に足りない組み込み関数を追加
まるごと
# Builtins
def _get_at(_, s):
arr = s.pop(); index = s.pop(); s.append(arr[index])
def _set_at(_, s):
arr = s.pop(); index = s.pop(); val = s.pop()
arr[index] = val
s.append(val)
def _slice(_, s):
arr = s.pop(); start = s.pop(); end = s.pop(); step = s.pop()
s.append(arr[slice(start, end, step)])
def _set_slice(_, s):
arr = s.pop(); start = s.pop(); end = s.pop(); step = s.pop(); val = s.pop()
arr[start:end:step] = val
s.append(val)
def _error(n, s):
assert False, f"{' '.join(map(str, [s.pop() for _ in range(n)]))}"
_builtins = {
"__builtins__": None,
"add": lambda _, s: s.append(s.pop() + s.pop()),
"sub": lambda _, s: s.append(s.pop() - s.pop()),
"mul": lambda _, s: s.append(s.pop() * s.pop()),
"div": lambda _, s: s.append(s.pop() // s.pop()),
"mod": lambda _, s: s.append(s.pop() % s.pop()),
"neg": lambda _, s: s.append(-s.pop()),
"equal": lambda _, s: s.append(s.pop() == s.pop()),
"not_equal": lambda _, s: s.append(s.pop() != s.pop()),
"less": lambda _, s: s.append(s.pop() < s.pop()),
"greater": lambda _, s: s.append(s.pop() > s.pop()),
"less_equal": lambda _, s: s.append(s.pop() <= s.pop()),
"greater_equal": lambda _, s: s.append(s.pop() >= s.pop()),
"not": lambda _, s: s.append(not s.pop()),
"array": lambda n, s: s.append([s.pop() for _ in range(n)]),
"is_array": lambda _, s: s.append(isinstance(s.pop(), list)),
"len": lambda _, s: s.append(len(s.pop())),
"get_at": _get_at,
"set_at": _set_at,
"slice": _slice,
"set_slice": _set_slice,
"is_name": lambda _, s: s.append(isinstance(s.pop(), str)),
"print": lambda n, s: s.append(print(*[s.pop() for _ in range(n)])),
"error": _error
}
class Builtins:
@staticmethod
def load(env):
for name, func in _builtins.items():
env.define(name, func)
Builtins周りはいまだにどう書くのが見栄えするか揺れている（見栄え
テストは手を抜いた
既存のテストを通すときにテストされるだろうきっと
すくなくとも既存のテストは動いている（それはそう
kb84tkhrCompilerで"assign"の左辺に配列要素やスライスが来た場合に組み込み関数に読み替える処理を入れておく
構文解析でやってもよかった気もするけど既存の処理にとりあえず合わせて
なんでだっけ？
構文解析ではとりあえず左辺も式として読んでおく、みたいなやり方であとは評価でがんばってくれ、みたいな感じだったかな
VMの方でもできるかもしれないけどここでやるほうがシンプルかな・・・
class Compiler:
def _expr(self, expr, is_tail):
match expr:
...
case ["assign", left, right]:
self._assign(left, right)
...
def _assign(self, left, right):
match left:
case name if is_name(name):
self._expr(right, False)
self._code.append(["set", name])
case ["get_at", arr, idx]:
self._op("set_at", [arr, idx, right], False)
case ["slice", arr, start, end, step]:
self._op("set_slice", [arr, start, end, step, right], False)
case _:
assert False, f"Invalid assign target: {left}"
テストはこれくらいで。
i.go_test(["array"], [])
i.go_test(["array", 5], [5])
i.go_test(["array", ["add", 5, 6], ["add", 7, 8]], [11, 15])
i.go_test(["define", "a", ["array", 5, 6, 7]], [5, 6, 7])
i.go_test(["assign", ["get_at","a", 1], 8], 8)
i.go_test("a", [5, 8, 7])
i.go_test(["assign", ["slice","a", 1, 3, None], ["array", 2, 3, 4]], [2, 3, 4])
i.go_test("a", [5, 2, 3, 4])
あとはマクロ関連かなー
なお再帰マクロを実現する方法についてはまだ特にアイデアなし
そのへんは関数を使って書き換えてみるつもりでいる
で["define", "foo", ["macro", ...]]と["defmacro", "foo", ...]の非互換をどうするか
既存の処理系にdefmacroを導入して互換性を取り、テストもdefmacroに書き換えることにする
expand()周りはごまかせるかなあ？
見かけが同じになるだけで意味論はだいぶ違うので
ファーストクラスマクロとか実現できないものはあきらめる
構文解析ではすなおにdefmacroを解釈して
class Parser:
def _sequence(self):
exprs = [self._defmacro()]
while self._current_token == ";":
self._advance()
exprs.append(self._defmacro())
return exprs[0] if len(exprs) == 1 else ["seq"] + exprs
def _defmacro(self):
if self._current_token != "defmacro":
return self._define_assign()
self._advance()
name = self._advance()
self._consume("(")
params = self._comma_separated_exprs(")")
self._consume("do")
body = self._expression()
self._consume("end")
return ["defmacro", name, params, body]
def _define_assign(self):
...
Evaluatorでdefineに読み替えてやる
ほんとならdefmacroをマクロで書きたいような糖衣構文
class Evaluator:
def _eval_expr(self):
assert isinstance(self._expr, Expr)
match self._expr.elems:
...
case ["defmacro", name, params, body]:
self._expr = Expr(["define", name, ["macro", params, body]])
...
そうするとこれが
def test_macro(self):
self.assertEqual(self.expanded("macro () do quote(abc) end ()"), "abc")
self.assertEqual(
self.expanded("macro (a) do quasiquote unquote(a) * unquote(a) end end (5 + 6)"),
["mul", ["add", 5, 6], ["add", 5, 6]])
self.go("build_exp := macro (op, *r) do quasiquote unquote(op)(unquote_splicing(r)) end end")
self.assertEqual(self.expanded("build_exp(add)"), ["add"])
self.assertEqual(self.expanded("build_exp(add, 5)"), ["add", 5])
self.assertEqual(self.expanded("build_exp(add, 5, 6)"), ["add", 5, 6])
self.assertEqual(self.go("macro (*a, b) do quasiquote [quote(unquote(a)), quote(unquote(b))] end end (5)"), [[], 5])
self.assertEqual(self.go("macro (*a, b) do quasiquote [quote(unquote(a)), quote(unquote(b))] end end (5, 6)"), [[5], 6])
self.assertEqual(self.go("macro (*a, b) do quasiquote [quote(unquote(a)), quote(unquote(b))] end end (5, 6, 7)"), [[5, 6], 7])
self.assertEqual(self.go("macro (a, *b, c) do quasiquote [quote(unquote(a)), quote(unquote(b)), quote(unquote(c))] end end (5, 6, 7)"), [5, [6], 7])
こうなる
無名マクロはないのですべてdefmacroで定義する
def test_defmacro(self):
self.go("defmacro foo () do quote(abc) end")
self.assertEqual(self.expanded("foo()"), "abc")
self.go("""
defmacro sq (a) do quasiquote unquote(a) * unquote(a) end end
""")
self.assertEqual(
self.expanded("sq(5 + 6)"),
["mul", ["add", 5, 6], ["add", 5, 6]])
self.go("defmacro build_exp (op, *r) do quasiquote unquote(op)(unquote_splicing(r)) end end")
self.assertEqual(self.expanded("build_exp(add)"), ["add"])
self.assertEqual(self.expanded("build_exp(add, 5)"), ["add", 5])
self.assertEqual(self.expanded("build_exp(add, 5, 6)"), ["add", 5, 6])
self.go("defmacro rest2 (*a, b) do quasiquote [quote(unquote(a)), quote(unquote(b))] end end")
self.assertEqual(self.go("rest2(5)"), [[], 5])
self.assertEqual(self.go("rest2(5, 6)"), [[5], 6])
self.assertEqual(self.go("rest2(5, 6, 7)"), [[5, 6], 7])
self.go("defmacro rest3 (a, *b, c) do quasiquote [quote(unquote(a)), quote(unquote(b)), quote(unquote(c))] end end")
self.assertEqual(self.go("rest3(5, 6, 7)"), [5, [6], 7])
今はどちらでも動くので両方書いてある
中間コードインタプリタに入れ替えた後も既存処理系用に無名マクロを使った定義を残しておきたいけどうまい書き方はあるかな
ここ以外のテストは単にdefmacroに書き換えている