トイ言語実験日記３（ステートマシンでマクロと継続）
kb84tkhr
これをベースに、同じようなルートでマクロや継続を実装してみよう。
それなりに長くなりそうなのでスクラップを分けて。
kb84tkhrベース（再掲）
class Environment:
def __init__(self, parent=None):
self._parent = parent
self._vals = {}
def define(self, name, val):
self._vals[name] = val
def get(self, name):
if name in self._vals:
return self._vals[name]
elif self._parent is not None:
return self._parent.get(name)
assert False, f"name '{name}' is not defined"
def is_value(expr):
match expr:
case None | bool(_) | int(_): return True
case ["func", _params, _body, _env]: return True
case f if callable(f): return True
case _: return False
class Evaluator:
def __init__(self, expr, env, cont):
self._expr = expr
self._env = env
self._cont = cont
def eval(self):
while True:
if is_value(self._expr):
if self._cont == ["$halt"]: return self._expr
self._apply_val()
else:
self._eval_expr()
def _apply_val(self):
match self._cont:
case ["$if", thn_expr, els_expr, next_cont]:
self._apply_if(thn_expr, els_expr, next_cont)
case ["$define", name, next_cont]:
self._apply_define(name, next_cont)
case ["$call", args_expr, call_env, next_cont]:
self._apply_call(args_expr, call_env, next_cont)
case ["$args",
func_val, args_expr, args_val,
call_env, next_cont]:
self._apply_args(func_val, args_expr, args_val,
call_env, next_cont)
case _:
assert False, f"Invalid continuation: {self._cont}"
def _apply_if(self, thn_expr, els_expr, next_cont):
if self._expr:
self._expr, self._cont = thn_expr, next_cont
else:
self._expr, self._cont = els_expr, next_cont
def _apply_define(self, name, next_cont):
self._env.define(name, self._expr)
self._cont = next_cont
def _apply_call(self, args_expr, call_env, next_cont):
self._expr, self._env, self._cont = args_expr[0], call_env, [
"$args",
self._expr, args_expr[1:], [],
call_env, next_cont
]
def _apply_args(self,
func_val, args_expr, args_val,
call_env, next_cont):
args_val += [self._expr]
if args_expr == []:
self._expr, self._env, self._cont = [
"$apply", func_val, args_val
], call_env, next_cont
else:
self._expr, self._env, self._cont = args_expr[0], call_env, [
"$args",
func_val, args_expr[1:], args_val,
call_env, next_cont
]
def _eval_expr(self):
match self._expr:
case ["func", params, body]:
self._expr = ["func", params, body, self._env]
case str(name):
self._expr = self._env.get(name)
case ["define", name, val_expr]:
self._expr, self._cont = val_expr, \
["$define", name, self._cont]
case ["if", cnd_expr, thn_expr, els_expr]:
self._expr, self._cont = cnd_expr, \
["$if", thn_expr, els_expr, self._cont]
case ["$apply", func_val, args_val]:
self._apply_func(func_val, args_val)
case [func_expr, *args_expr]:
self._expr, self._cont = func_expr, \
["$call", args_expr, self._env, self._cont]
case _:
assert False, f"Invalid expression: {self._expr}"
def _apply_func(self, func_val, args_val):
match func_val:
case f if callable(f):
self._expr = func_val(args_val)
case ["func", params, body_expr, closure_env]:
closure_env = Environment(closure_env)
for param, arg in zip(params, args_val):
closure_env.define(param, arg)
self._expr, self._env = body_expr, closure_env
case _:
assert False, f"Invalid function: {self._expr}"
class Interpreter:
def __init__(self):
self.env = Environment()
builtins = {
"+": lambda args_val: args_val[0] + args_val[1],
"-": lambda args_val: args_val[0] - args_val[1],
"=": lambda args_val: args_val[0] == args_val[1],
"print": lambda args_val: print(*args_val),
}
for name in builtins:
self.env.define(name, builtins[name])
self.env = Environment(self.env)
def run(self, src):
return Evaluator(src, self.env, ["$halt"]).eval()
135行ある。
最初のスクラップのeval()のときはこんなこと言ってた。
コードはまるごと貼り付けられるレベル。
39行。
できることは変わってないんだけれども。
kb84tkhrassignを追加した。
class Environment:
...
def assign(self, name, val):
if name in self._vals:
self._vals[name] = val
elif self._parent is not None:
self._parent.assign(name, val)
else:
assert False, f"name '{name}' is not defined"
class Evaluator:
...
def _apply_val(self):
match self._cont:
...
case ["$assign", name, next_cont]:
self._apply_assign(name, next_cont)
...
...
def _apply_assign(self, name, next_cont):
self._env.assign(name, self._expr)
self._cont = next_cont
...
def _eval_expr(self):
match self._expr:
...
case ["assign", name, val_expr]:
self._expr, self._cont = val_expr, \
["$assign", name, self._cont]
...
...
assert run(["assign", "a", 7]) == 7
assert run("a") == 7
assert run([["func", [], ["assign", "a", 8]]]) == 8
assert run("a") == 8
seqを追加した。
class Evaluator:
...
def _apply_val(self):
match self._cont:
...
case ["$seq", exprs, next_cont]:
self._apply_seq(exprs, next_cont)
...
...
def _apply_seq(self, exprs, next_cont):
if exprs == []:
self._cont = next_cont
else:
self._expr, self._cont = exprs[0], ["$seq", exprs[1:], next_cont]
...
def _eval_expr(self):
match self._expr:
...
case ["seq", *exprs]:
self._expr, self._cont = None, \
["$seq", exprs, self._cont]
...
...
assert run(["seq", 5, 6]) == 6
でカウンターを作ったらあからさまなバグが見つかったので修正。
関数本体を評価した後、環境を元に戻していなかったので["define", "counter1", ["make_counter"]]でcounter1がクロージャ内に定義されててローカル変数のような扱いになってしまい、すぐに忘れられてしまっていた。
関数の評価が終わったら環境を戻す、というのを継続に入れた。
あ、引数がひとつもないと動いてなかったのも直したんだった。
class Evaluator:
...
def _apply_val(self):
match self._cont:
...
case ["$restore_env", env, next_cont]:
self._env, self._cont = env, next_cont
...
def _apply_call(self, args_expr, call_env, next_cont):
if args_expr == []:
self._expr, self._env, self._cont = [
"$apply", self._expr, []
], call_env, next_cont
else:
self._expr, self._env, self._cont = args_expr[0], call_env, [
"$args",
self._expr, args_expr[1:], [],
call_env, next_cont
]
...
def _apply_func(self, func_val, args_val):
match func_val:
...
case ["func", params, body_expr, closure_env]:
...
self._expr, self._env, self._cont = body_expr, closure_env, \
["$restore_env", self._env, self._cont]
...
...
run(["define", "make_counter", ["func", [], ["seq",
["define", "c", 0],
["func", [], ["assign", "c", ["+", "c", 1]]]]]])
run(["define", "counter1", ["make_counter"]])
run(["define", "counter2", ["make_counter"]])
assert run(["counter1"]) == 1
assert run(["counter1"]) == 2
assert run(["counter2"]) == 1
assert run(["counter2"]) == 2
assert run(["counter1"]) == 3
assert run(["counter2"]) == 3
ステートマシンってだいぶ気を使わないとちゃんと動かなくね？
まだ修正漏れとかミスってるところとかあるんじゃないかという気もする。
まさしくそれ。
まあでもちょっとパターン見えてきたかも。
kb84tkhrテストを分ける。
こんな風に書いたらsetUp()が呼ばれないうちに勝手にrun()が動いてエラーになるので何事かと思ったらTestCase.run()というのがもともと存在してた。
class TestToig(unittest.TestCase):
def setUp(self):
self.i = Interpreter()
def run(self, src):
return self.i.run(src)
def test_primary(self):
self.assertEqual(self.run(None), None)
go()と名前を変えた。
kb84tkhr配列を扱えるようにしようと思ったらexprが配列のときASTなのか値なのか見分けがつかないっていう根本的な問題発生
ピンチ
ASTクラスでも作るかなあ
kb84tkhr考え中に思い付いたことを済ませる。
とりあえず配列以外のbuiltinsをつけてしまう。
よくみたら $call と $args は同じことをやってるのでまとめる。
ついでに、関数とクロージャが両方"func"という名前だったのでクロージャを"closure"という名前にする（今までは要素の個数だけで判別していて、特に困るわけではなかったのだが）。
kb84tkhrExprクラスを作った。
生の値NoneとかTrueとかintとか["closure", params, body, env]は評価済みの値の時だけ使って、それ以外の時はExprでラップする。
というマークするだけの役割なのでdataclassが合いそう。
dataclassのプロパティには型がいるので型ヒントもつけておく。
警告よけの意味もある。
from typing import Callable
from dataclasses import dataclass
ValueType = None | bool | int | Callable | list
@dataclass
class Expr:
elems: ValueType
class Expr(list): passのようにlistを継承する作戦もあったかも。
matchとかisinstanceが思った通り動いてくれればそっちのがもっと簡単か？
listのメソッドも使えるし。
Evaluator。
_exprにはExprか生の値が入ってるということを表現。
class Evaluator:
def __init__(self, expr, env, cont):
self._expr: Expr | ValueType = expr
self._env = env
self._cont = cont
def eval(self):
while True:
if isinstance(self._expr, Expr):
self._eval_expr()
else:
if self._cont == ["$halt"]: return self._expr
self._apply_val()
評価済みかどうかはExprかどうかを見ればよくなった。
あと大事なのはExprじゃなくなるところ。
Expr(None)とかExpr(True)とかExpr(5)とかExpr(["func", params, body])とかExpr(callable)とかのときはExprじゃない生の値を返す。
def _eval_expr(self):
assert isinstance(self._expr, Expr)
match self._expr.elems:
case bool(_) | int(_) | None:
self._expr = self._expr.elems
case f if callable(f):
self._expr = self._expr.elems
case ["func", params, body]:
self._expr = ["closure", params, body, self._env]
case str(name):
self._expr = self._env.get(name)
あと組み込み関数を適用するときも。
def _apply_func(self, elems_val):
func_val, args_val = elems_val[0], elems_val[1:]
match func_val:
case f if callable(f):
self._expr = func_val(args_val)
...
あとはもれなくExprでくるまれているようにする。
継続もContでくるむ必要があるか？と思ったけどやらなくてよさそう。
kb84tkhr組み込み関数を追加すれば・・・
def setat(args):
args[0][args[1]] = args[2]
return args[2]
def slice_(args):
arr, start, end, step = args
return arr[slice(start, end, step)]
def set_slice(args):
arr, start, end, step, val = args
arr[start:end:step] = val
return val
class Interpreter:
builtins = {
...
"arr": lambda args: args,
"is_arr": lambda args: isinstance(args[0], list),
"len": lambda args: len(args[0]),
"get_at": lambda args: args[0][args[1]],
"set_at": setat,
"slice": slice_,
"set_slice": set_slice,
...
}
配列が動くようになったはず！
self.go(["define", "a", ["arr", 5, 6, ["arr", 7, 8]]])
self.assertEqual(self.go("a"), [5, 6, [7, 8]])
self.assertEqual(self.go(["get_at", "a", 1]), 6)
self.assertEqual(self.go(["get_at", "a", -1]), [7, 8])
self.assertEqual(self.go(["get_at", ["get_at", "a", 2], 1]), 8)
self.assertEqual(self.go(["set_at", "a", 1, 9]), 9)
self.assertEqual(self.go("a"), [5, 9, [7, 8]])
よしできた
kb84tkhrマクロ路線に戻ってquoteの実装。
def _eval_expr(self):
match self._expr.elems:
...
case ["q", expr]:
self._expr = expr
...
かんたんなことがかんたんにできることは大切。
exprをExprで囲んでいないのが本質。
def test_quote(self):
self.assertEqual(self.go(["q", 5]), 5)
self.assertEqual(self.go(["q", ["add", 5, 6]]), ["add", 5, 6])
※eval_expr()とapply_val()を入れ替えたりしてるのでdiffはよくわからない状態になっている（よくある（よくない
kb84tkhrdataclassにするとデバッガでちょっと見やすくなるということに気づいたんだけれどもじゃあEnvironmentもdataclassにしたらいいのか？
なんか違う気がするので__repr__()書くことにした。
class Environment:
def __repr__(self):
return f"{
"builtins" if "__builtins__" in self._vals else self._vals
} > {self._parent}"
class Interpreter:
builtins = {
"__builtins__": None,
"add": lambda args: args[0] + args[1],
...
多少なりとも見やすくなるようひと工夫入れている
__repr__()のお作法として正しいのかはよくわからない
kb84tkhrqq作るかmacro作るか
qqからいくかな
qで書いたマクロをqqに書き換えるのは手戻りだし一度やってるし
じゃあqいるのかって話
たまにはいるかもしれない
qqはかなり大物になりそうな気がしている
段階踏んでいこう
まずはこれを通す。
まだquasiquoteらしいことはしてないけど配列をひとつずつ見ていく構造を作るのが主眼。
def test_quasiquote(self):
self.assertEqual(self.go(["qq", 5]), 5)
self.assertEqual(self.go(["qq", ["add", 5, 6]]), ["add", 5, 6])
self.assertEqual(self.go(["qq", ["mul", 4, ["add", 5, 6]]]), ["mul", 4, ["add", 5, 6]])
self.assertEqual(self.go(["qq", ["mul", ["add", 5, 6], 7]]), ["mul", ["add", 5, 6], 7])
こう？
def _eval_expr(self):
...
case ["qq", expr]:
self._expr, self._cont = expr, ["$qq", self._cont]
...
def _apply_val(self):
match self._cont:
...
case ["$qqelems", elems, elems_done, next_cont]:
self._apply_qq_elems(elems, elems_done, next_cont)
...
def _apply_quasiquote(self, next_cont):
match self._expr:
case []:
self._expr, self._cont = [], next_cont
case [first, *rest]:
self._expr = first
self._cont = ["$qq", ["$qqelems", rest, [], next_cont]]
case _:
self._cont = next_cont
def _apply_qq_elems(self, elems, elems_done, next_cont):
elems_done += [self._expr]
match elems:
case []:
self._expr, self._cont = elems_done, next_cont
case [first, *rest]:
self._expr = first
self._cont = ["$qq", ["$qqelems", rest, elems_done, next_cont]]
case _:
assert False, f"Invalid quasiquote elements: {elems}"
通った。
_apply_quasiquote() と _apply_qq_elems() がだいぶ重複してる感じするけどとりあえずこのまま進む。
整理できるかどうかはquasiquoteひととおり実装してからかな。
kb84tkhr次はunquote (!)の処理を入れる。
self.assertEqual(self.go(["qq", ["!", ["add", 5, 6]]]), 11)
self.assertEqual(self.go(["qq", ["mul", 4, ["!", ["add", 5, 6]]]]), ["mul", 4, 11])
self.assertEqual(self.go(["qq", ["mul", ["!", ["add", 5, 6]], 7]]), ["mul", 11, 7])
["!", expr]だったらExpr(expr)を評価してやるだけだった。
def _apply_quasiquote(self, next_cont):
match self._expr:
case []:
self._expr, self._cont = [], next_cont
case ["!", expr]:
self._expr = Expr(expr)
self._cont = next_cont
case [first, *rest]:
self._expr = first
self._cont = ["$qq", ["$qqelems", rest, [], next_cont]]
case _:
self._cont = next_cont
構造さえできてれば実は簡単だったって話なんだけれども実は構造がおかしくて上の記事も何度も書き直してる。
unquoteのテストがなかったので、quasiquoteの処理中にいつのまにかただのquoteの処理になってしまってても気づけなかった。
こんどは大丈夫な気がしてるんだけれどもテストケースが足りてるかまあまあ自信がない。
がいったんここでcommitしておく。
kb84tkhrunquote-splicingに進む。
self.assertEqual(self.go(["qq", ["add", ["!!", ["arr", 5, 6]]]]), ["add", 5, 6])
self.assertTrue(self.fails(["qq", ["add", ["!!", 5]]]))
_apply_qq_elems()で配列の項をひとつ処理した後、spliceかどうかを判断できるよう継続にフラグを追加して、[["!!", elem], *rest]の形だったらTrue、そうでなければFalseをセットする。
def _apply_val(self):
match self._cont:
case ["$qq", next_cont]:
self._apply_quasiquote(next_cont)
case ["$qq_elems", splicing, elems, elems_done, next_cont]:
self._apply_qq_elems(splicing, elems, elems_done, next_cont)
def _apply_quasiquote(self, next_cont):
match self._expr:
case ["!", expr]:
self._expr = Expr(expr)
self._cont = next_cont
case [["!!", elem], *rest]:
self._expr = Expr(elem)
self._cont = ["$qq_elems", True, rest, [], next_cont]
case [first, *rest]:
self._expr = first
self._cont = ["$qq", ["$qq_elems", False, rest, [], next_cont]]
case _:
self._cont = next_cont
def _apply_qq_elems(self, splicing, elems, elems_done, next_cont):
if splicing:
assert isinstance(self._expr , list), f"Cannot splice: {self._expr}"
elems_done += self._expr
else:
elems_done += [self._expr]
match elems:
case []:
self._expr, self._cont = elems_done, next_cont
case [["!!", elem], *rest]:
self._expr = Expr(elem)
self._cont = ["$qq_elems", True, rest, elems_done, next_cont]
case [first, *rest]:
self._expr = first
self._cont = ["$qq", ["$qq_elems", False, rest, elems_done, next_cont]]
case _:
assert False, f"Invalid quasiquote elements: {elems}"
結局、_apply_quasiquote()と_apply_qq_elems()をひとつにまとめられそうな気はしていないんだけれども、せめて重複を減らすくらいのことはできないか。
あと、配列の先頭にunquote-splicingが来た時の処理を忘れそうになってたのでテストを追加。
これ処理できなくてよければ重複感が少し減ったんだけれども。
あるいは["qq", ["!", ["add", 5, 6]]]をあきらめても。
self.assertEqual(self.go(["qq", [
["!!", ["arr", 3]],
4,
["!!", ["arr", 5]],
6]]), [3, 4, 5, 6])
いったんコミットしてから考える。
kb84tkhrすごいじたばたしながら状態遷移書いてるわけだけれども、これ他人が読んで読めるんだろうか
自分でも1ヶ月もすればわかんなくなってそうな気がする
チューリングさんはあんな単純な状態遷移機械でセルフ実行できるインタプリタ書いたんだからもうびっくりですよ
コンピュータもないのに！
全部頭の中でとかおかしい
kb84tkhrせめて重複を減らすくらいのことはできないか。
こんなもんかな。
def _apply_val(self):
match self._cont:
case ["$qq", next_cont]:
self._apply_quasiquote(next_cont)
case ["$qq_elems", splicing, elems, elems_done, next_cont]:
elems_done = self._qq_add_element(elems_done,splicing)
self._apply_qq_elems(elems, elems_done, next_cont)
...
def _apply_quasiquote(self, next_cont):
match self._expr:
case ["!", expr]:
self._expr = Expr(expr)
self._cont = next_cont
case [*elems]:
self._apply_qq_elems(elems, [], next_cont)
case _:
self._cont = next_cont
def _qq_add_element(self, elems_done, splicing):
if splicing:
assert isinstance(self._expr , list), f"Cannot splice: {self._expr}"
return elems_done + self._expr
else:
return elems_done + [self._expr]
def _apply_qq_elems(self, elems, elems_done, next_cont):
match elems:
case []:
self._expr, self._cont = elems_done, next_cont
case [["!!", elem], *rest]:
self._expr = Expr(elem)
self._cont = ["$qq_elems", True, rest, elems_done, next_cont]
case [first, *rest]:
self._expr = first
self._cont = ["$qq", ["$qq_elems", False, rest, elems_done, next_cont]]
case _:
assert False, f"Invalid quasiquote elements: {elems}"
_qq_add_element()からelems_doneに要素を追加する箇所を抜き出し、_qq_add_element()に共通部分だけを残して_apply_quasiquote()から_qq_add_element()を（継続で渡すのではなく）直接呼ぶようにした。
状態ごとにひとつの関数っていう思い込みがあって_apply_quasiquote()から_qq_add_element()を呼びだすっていう考えになかなか至れなかった。
kb84tkhrマクロの実装に進む。
func()と同じようなもんじゃねと思ってたけどかなり苦労した。
["func"]と["closure"]分けたけど["macro"]に対していい名前は思いつかない。
["mclosure"]としておいた。別に名前変えなくてもいいかもしれない。
def _eval_expr(self):
assert isinstance(self._expr, Expr)
match self._expr.elems:
...
case ["func", params, body]:
self._expr = ["closure", params, body, self._env]
case ["macro", params, body]:
self._expr = ["mclosure", params, body, self._env]
...
話が簡単なexpandから。
マクロを展開するだけのテストとか調査とか用。
マクロ部分だけ評価したら、引数は評価せずにそのまま環境につっこんでbodyを評価する。
環境を元に戻す$restore_envも忘れずに。
def _eval_expr(self):
match self._expr.elems:
...
case ["expand", [op_expr, *args_expr]]:
self._expr, self._cont = Expr(op_expr), \
["$expand", args_expr, self._env, self._cont]
...
def _apply_val(self):
...
match self._cont:
...
case ["$expand", args_expr, call_env, next_cont]:
self._apply_expand(args_expr, call_env, next_cont)
...
def _apply_expand(self, args_expr, call_env, next_cont):
match self._expr:
case ["mclosure", params, body_expr, mclosure_env]:
mclosure_env = mclosure_env.extend(params, args_expr)
self._expr, self._env, self._cont = (
Expr(body_expr), mclosure_env,
["$restore_env", call_env, next_cont]
)
case unexpected:
assert False, f"Cannot expand: {unexpected}"
環境につっこんで、の処理はところどころで出てくるのでEnvironmentクラスのメソッドにした。
class Environment:
...
def extend(self, params, args):
new_env = Environment(self)
for param, arg in zip(params, args):
new_env.define(param, arg)
return new_env
こんな風に呼ぶと
i.run(["print", ["expand", [
["macro", ["a", "b"], ["qq", ["add", ["!", "a"], ["!", "b"]]]],
["add", 5, 6], 7]]])
こう出力される。
['add', ['add', 5, 6], 7]
引数として与えた["add", 5, 6]が11にならないでそのまま出てきてることに注意。
kb84tkhr本当のマクロの処理に進む。
expandする部分は同じで、それを評価してやればよい。
applyやcallで扱う対象が関数だけじゃなくなったので名前を変えておく(func → op)。
def _eval_expr(self):
match self._expr.elems:
...
case ["$apply", op_val, args_val]:
self._apply_op(op_val, args_val)
case [op_expr, *args_expr]:
self._expr, self._cont = Expr(op_expr), \
["$call", args_expr, self._env, self._cont]
...
順番から言って次は$callかな
最初の項がmclosureだったら残りはなにもせずそのまま渡せばいいわけだが
どこで分けようか
$callと$argsに分けて作ってたのをわざわざくっつけたけれども
分けなおすのが素直？
という思考回路を経てこんなふうに。
$callと$argsで大部分は同じ処理なので別関数にくくりだしている。
$callではマクロだったら引数にはなにもしないで$applyに渡している。
def _apply_val(self):
...
match self._cont:
...
case ["$call", args_expr, call_env, next_cont]:
self._apply_call(args_expr, call_env, next_cont)
case ["$args", op_expr, args_expr, args_val, call_env, next_cont]:
self._apply_args(op_expr, args_expr, args_val, call_env, next_cont)
...
def _apply_call(self, args_expr, call_env, next_cont):
match self._expr:
case ["mclosure", _params, _body_expr, _mclosure_env]:
self._expr, self._env, self._cont = (
Expr(["$apply", self._expr, args_expr]), call_env, next_cont
)
case op_val:
self._apply_arg(op_val, args_expr, [], call_env, next_cont)
def _apply_args(self, op_val, args_expr, args_val, call_env, next_cont):
args_val += [self._expr]
self._apply_arg(op_val, args_expr, args_val, call_env, next_cont)
def _apply_arg(self, op_val, args_expr, args_val, call_env, next_cont):
if args_expr == []:
self._expr, self._env, self._cont = (
Expr(["$apply", op_val, args_val]), call_env, next_cont
)
else:
self._expr, self._env, self._cont = (
Expr(args_expr[0]),
call_env,
["$args", op_val, args_expr[1:], args_val, call_env, next_cont]
)
stdlib()（ただしletcc導入前）もだいたい取り込んで動いてる
kb84tkhrrest引数にも対応して、letやcondのマクロも動くようになった。
letccに進もう。
rest引数に対応するにはextendを書き換えるだけ。
ここは継続が関係してこないところなので以前のコードをメソッドに書き換えれば済む。
def extend(self, params, args):
def _extend(params, args):
if params == [] and args == []: return {}
assert len(params) > 0, \
f"Argument count doesn't match: `{params}, {args}` @ extend"
match params[0]:
case str(param):
assert len(args) > 0, \
f"Argument count doesn't match: `{params}, {args}` @ extend"
env.define(param, args[0])
_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}` @ extend"
env.define(rest, args[:rest_len])
_extend(params[1:], args[rest_len:])
case unexpected:
assert False, f"Unexpected param at extend: {unexpected}"
env = Environment(self)
_extend(params, args)
return env
普通に上からコードが書けるって楽だなあ
kb84tkhr["letcc", name, body]が出てきたらnameに環境と継続を覚えさせてbodyを評価する。
def _eval_expr(self):
...
match self._expr.elems:
...
case ["letcc", name, body]:
self._env.define(name, ["cont", self._env, self._cont])
self._expr = Expr(body)
...
覚えさせたものは関数ではないけれども関数のなかまとして処理。
引数は1個で省略可とした。["continue"]で済むように。
値を_exprに入れて、_envと_contを戻しているだけ。
def _apply_op(self, op_val, args_val):
match op_val:
...
case ["cont", env, cont]:
val = args_val[0] if args_val else None
self._expr, self._env, self._cont = val, env, cont
...
うーん、これだけで動いてしまう気がする・・・
def test_letcc(self):
self.assertEqual(self.go(["letcc", "skip-to", ["add", 5, 6]]), 11)
self.assertEqual(self.go(["letcc", "skip-to", ["add", ["skip-to", 5], 6]]), 5)
self.assertEqual(self.go(["add", 5, ["letcc", "skip-to", ["skip-to", 6]]]), 11)
self.assertEqual(self.go(["letcc", "skip1", ["add", ["skip1", ["letcc", "skip2", ["add", ["skip2", 5], 6]]], 7]]), 5)
self.go(["define", "inner", ["func", ["raise"], ["raise", 5]]])
self.go(["define", "outer", ["func", [],
[ "letcc", "raise", ["add", ["inner", "raise"], 6]]]])
self.assertEqual(self.go(["outer"]), 5)
動いた Σ(ﾟﾛﾟ)
しかし継続を再利用しようとすると動かなかった。
def test_letcc_reuse(self):
self.go(["define", "add5", None])
self.assertEqual(self.go(["add", 5, ["letcc", "cc", ["seq", ["assign", "add5", "cc"], 6]]]), 11)
self.assertEqual(self.go(["add5", 7]), 12)
self.assertEqual(self.go(["add5", 8]), 13)
追っかけてみると継続の中身が変わっていた。
犯人はここ。
def _apply_args(self, op_val, args_expr, args_val, call_env, next_cont):
args_val += [self._expr]
self._apply_arg(op_val, args_expr, args_val, call_env, next_cont)
args_val = args_val + [self._expr]に書き換えて解決。
んーこれでいいか気になってたところではあったんだけど。
これでtryもジェネレータも並列処理も動くし。
1記事でできてしまったな・・・
kb84tkhrマクロと継続ができたので、字句解析・構文解析までやった処理系の評価器を入れ替えてみたい。
見比べてみると、配列への代入を作ってなかった。
この部分。
def eval_assign(left, expr, env, cont):
def _eval_assign(val):
match left:
case str(name):
return cont(assign(env, name, val))
case ["getat", arr, idx]:
return eval_expr(arr, env,
lambda arr_val: eval_expr(idx, env,
lambda idx_val: cont(setat([arr_val, idx_val, val]))))
case ["slice", arr, start, end, step]:
return eval_expr(arr, env,
lambda arr_val: eval_expr(start, env,
lambda start_val: eval_expr(end, env,
lambda end_val: eval_expr(step, env,
lambda step_val: cont(set_slice(
[arr_val, start_val, end_val, step_val, val]))))))
assert False, f"Invalid assign target: {left} @ eval_assign"
なんか力技でやってる感じだけどうまく書けるかな？
力技でやればできるとは思うけど、力技感が３倍増くらいしそう。
あとscopeをマクロじゃなくて特殊形式で定義してたけどこれはそのままでも動くかもしれない。
動かなかったらやろう。
kb84tkhrやってることは引数をひとつずつ評価してsetatやset_sliceに渡してやることだから関数の処理に似てるんだよな・・・
うまく関数の処理を使いまわせないかな・・・
ていうか関数呼べばいいだけじゃね？
ってなっている
kb84tkhrいや、そもそも構文解析で配列への代入をset_atとかset_sliceに読み替えてやればいいだけ？
kb84tkhrとりあえず既存の構文解析を使えるように、評価器の方で仕事をすることにした。
def _eval_expr(self):
assert isinstance(self._expr, Expr)
match self._expr.elems:
...
case ["assign", left, val_expr]:
self._eval_assign(left, val_expr)
...
def _eval_assign(self, left, val_expr):
match left:
case name if is_name(name):
self._expr, self._cont = Expr(val_expr), \
["$assign", name, self._cont]
case ["get_at", arr, idx]:
self._expr = Expr(["set_at", arr, idx, val_expr])
case ["slice", arr, start, end, step]:
self._expr = Expr(["set_slice", arr, start, end, step, val_expr])
case _:
assert False, f"Invalid assign target: {left} @ eval_assign"
これで済んでいるみたい。
def test_array_set(self):
self.go(["define", "a", ["arr", 5, 6, 7, 8, 9]])
self.assertEqual(self.go(["assign", ["get_at", "a", 1], True]), True)
self.assertEqual(self.go("a"), [5, True, 7, 8, 9])
self.assertEqual(self.go(["assign", ["slice", "a", 3, None, None], ["arr", 10, 11]]), [10, 11])
self.assertEqual(self.go("a"), [5, True, 7, 10, 11])
kb84tkhrこれに組み込んでみようと思うわけだが
２か所直してから手を付けよう
kb84tkhrひとつめ。
上でやった_eval_assign()の修正をこっちにもあてる。
def eval_assign(left, expr, env, cont):
match left:
case str(name):
return lambda: eval_expr(expr, env, lambda val: cont(assign(env, name, val)))
case ["getat", arr, idx]:
return eval_expr(["setat", arr, idx, expr], env, cont)
case ["slice", arr, start, end, step]:
return eval_expr(["set_slice", arr, start, end, step, expr], env, cont)
assert False, f"Invalid assign target: {left} @ eval_assign"
すっきりした。
テストがひとつ失敗するので直した。
aifのカスタム文法を導入したときの修正漏れ。
なんで気づかなかったかなあ。
def test_letcc_generator(self):
run("""
g3 := gfunc (n) do
yield(n); n = inc(n);
yield(n); n = inc(n);
yield(n)
end;
gsum := func (gen) do aif gen() then it + gsum(gen) else 0 end end
""")
ふたつめ。
letcc cc do break = cc; loop() doneのようにいったん継続を変数に覚えさせてからbreakに代入してたが無駄だった。
いきなりletcc break do ... doneでいいはず。
ただしbreakが見える範囲でloop()を定義する必要がある。
continueの方もそうできるといいんだけれどもできなかった。
run("""
__stdlib_while := macro (cnd, body) do qq scope
continue := val := None;
letcc break do
loop := func() do
letcc cc do continue = cc end;
if !(cnd) then val = !(body); loop() else val end
end;
loop()
end
end end end
#rule [while, __stdlib_while, EXPR, do, EXPR, end]
""")
awhile、forも同様に修正。
kb84tkhr組み込んだ。
あんまり言うことはないかな
マージする、という感じではない気がしたのでコピペでやった
kb84tkhr半分だけクラスというのも気持ち悪いので全面的にクラスで書いた。
カスタムルールは結局辞書に追加して読むだけだったのでただのdictでもよかったんだけれどもなんとなく型を作った。
class CustomRules(dict): pass
組み込み関数と標準ライブラリはクラスを分けた。
おかげでInterpreterクラスはこじんまりと。
class BuiltIns:
def __init__(self, env):
self._env = env
def load(self):
...
class StdLib:
def __init__(self, interpreter):
self._interpreter = interpreter
def _run(self, src):
self._interpreter.run(src)
def load(self):
self._run("__stdlib__ := None")
...
class Interpreter:
def __init__(self):
self._env = Environment()
BuiltIns(self._env).load()
self._env = Environment(self._env)
self._custom_rule = CustomRules()
StdLib(self).load()
self._env = Environment(self._env)
def parse(self, src):
return Parser(src, self._custom_rule).parse()
def run(self, src):
return Evaluator(self.parse(src), self._env, ["$halt"]).eval()
ほかは機械的に書き換えたくらい。だったと思う。
kb84tkhrテストをちまちま直してるときに、letとcondはもうちょっとカスタム文法でそれっぽくできんじゃね？と思ったのでやってみた。
let。
def test_let4(self):
self.go("""
_let4 := macro(*bindings, body) do
i := 0; defines := arr();
while i < len(bindings) do
defines = defines + arr(
qq !(bindings[i]) := !(bindings[i + 1]) end
);
i = i + 2
end;
qq scope
!!(defines); !(body)
end end
end
#rule [let4, _let4, *[var, NAME, is, EXPR], do, EXPR, end]
""")
self.assertEqual(self.go("let4 do 5 end"), 5)
self.assertEqual(self.go("""
let4
var a is 5
var b is 6
do
a + b
end
"""), 11)
最初、var a := 5って書かせようとしたけどaだけ読んでほしいところでa := 5まで読んじゃうのでやめた。
NAMEで指定している個所だけど、式を読みこんでから名前かどうか判定してるのでそうなる。
最初から１トークンしか読まないようにしてもいいんだろうけど。
cond。
def test_cond2(self):
self.go("""
_cond := macro(*clauses) do
__cond := func (clauses) do
if clauses == [] then None else
cnd := first(clauses); clauses := rest(clauses);
thn := first(clauses); clauses := rest(clauses);
qq
if !(cnd) then !(thn) else !(__cond(clauses)) end
end
end
end;
__cond(clauses)
end
#rule [cond, _cond, *[case, EXPR, then, EXPR], end]
""")
self.go("""
fib := func (n) do
cond
case n == 0 then
0
case n == 1 then
1
case True then
fib(n - 1) + fib(n - 2)
end
end
""")
if - then - elseとほとんど変わらなくて存在意義はないけど。
switchみたいなのつくった方が存在価値が出るかもしれない。
kb84tkhrそんなことより末尾呼び出し最適化をやれ、という声が聞こえてきた気がする。
再帰からCPSに書き換えてスタックのオーバーフローはなくなったんだけれどもその分は継続が長くなっている。
こんなプログラムを動かしてちょっと放置すると
loop := func () do loop() end;
loop()
すぐにギガバイト単位でメモリを消費する。
vscode@c64204c692f5:/workspaces/toig$ top
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
18885 vscode 20 0 3483312 3.0g 3456 R 100.0 38.8 4:13.70 python
マクロで作ったwhileループも中では同じように再帰しているのでやっぱりメモリを消費する。
kb84tkhrこんなコードの実行中の継続を
loop := func (n) do if n > 0 then loop(n - 1) end end;
loop(3)
関数呼び出しの継続を作るところでprintして観察する。
def _apply_op(self, op_val, args_val):
match op_val:
...
case ["closure", params, body_expr, closure_env]:
print(self._cont)
closure_env = closure_env.extend(params, args_val)
self._expr, self._env, self._cont = Expr(body_expr), closure_env, \
["$restore_env", self._env, self._cont]
...
こんな感じ。
['$seq', [], ['$halt']]
['$restore_env', {'n': 3} > ...,
['$restore_env', {'loop': ...} > ...,
['$seq', [], ['$halt']]]]
['$restore_env', {'n': 2} > ...,
['$restore_env', {} > {'n': 3} > ...,
['$restore_env', {'loop': ...} > ...,
['$seq', [], ['$halt']]]]]
['$restore_env', {'n': 1} > ...,
['$restore_env', {} > {'n': 2} > ...,
['$restore_env', {'n': 2} > ...,
['$restore_env', {} > {'n': 3} > ...,
['$restore_env', {'n': 3} > ...,
['$restore_env', {'loop': ...},
['$seq', [], ['$halt']]]]]]]]
ループが終わるとこれにしたがって環境を戻していくわけだけれども、ただ環境を戻していくだけだから途中の$restore_envはあってもなくても変わらない。
一番内側の['$restore_env', {'loop': ...}, ['$seq', [], ['$halt']]]だけ実行されればよい。
つまり$restore_envしようとしたとき、現在の継続が$restore_envであれば新たに$restore_envを重ねる必要はないということ。
ループのたびに$restore_envがふたつずつ増えているのは、関数呼び出しだけでなくifのthenやelseのところでscopeを使って新たなスコープを作っている分もあるため。
ここも手を入れる必要がありそう。
kb84tkhrやってみたらできた。
def _apply_op(self, op_val, args_val):
match op_val:
...
case ["closure", params, body_expr, closure_env]:
closure_env = closure_env.extend(params, args_val)
if not isinstance(self._cont, list) or \
self._cont[0] != "$restore_env":
self._cont = ["$restore_env", self._env, self._cont]
self._expr, self._env = Expr(body_expr), closure_env
...
あとscopeとexpandの処理も同様に。
・・・なんでmclosureの処理では$restore_envしてないんだっけ？
おかしくね？
とりあえず動かしてみる。
['$seq', [], ['$halt']]
['$restore_env', {'loop': ...} > ..., ['$seq', [], ['$halt']]]
['$restore_env', {'loop': ...} > ..., ['$seq', [], ['$halt']]]
['$restore_env', {'loop': ...} > ..., ['$seq', [], ['$halt']]]
動いたし継続が伸びなくなった。
テストも動いた。
kb84tkhr・・・なんでmclosureの処理では$restore_envしてないんだっけ？
おかしくね？
そういえばmclosureもclosureと同じだよねって思って最初は$restore_envありから始めたような気もするんだよな・・・なんだっけかな
いちど事実をつかもう
このへんで環境をprintしておけばしっぽがつかめるんじゃないかな
def _apply_op(self, op_val, args_val):
match op_val:
...
case ["mclosure", params, body_expr, mclosure_env]:
mclosure_env = mclosure_env.extend(params, args_val)
self._expr, self._env, self._cont = Expr(body_expr), mclosure_env, \
["$meval", self._env, self._cont]
print(self._env)
これでこのコードを実行する
おお、使い道がないと思われてたwhenの居場所がここに
loop := func (n) do when n > 0 do loop(n - 1) end end;
loop(3)
あれ？
{'cnd': ['greater', 'n', 0], 'thn': ['loop', ['sub', 'n', 1]]} > stdlib > builtins > None
{'cnd': ['greater', 'n', 0], 'thn': ['loop', ['sub', 'n', 1]]} > stdlib > builtins > None
{'cnd': ['greater', 'n', 0], 'thn': ['loop', ['sub', 'n', 1]]} > stdlib > builtins > None
{'cnd': ['greater', 'n', 0], 'thn': ['loop', ['sub', 'n', 1]]} > stdlib > builtins > None
考えてみるとloop()から帰るごとに環境リセットされるからこれじゃわからんのか
マクロだけ並べたほうがいいか
when 1 > 0 do when 1 > 0 do when 1 > 0 do None end end end
なんの異常もない
{'cnd': ['greater', 1, 0], 'thn': ['__stdlib_when', ['greater', 1, 0], ['__stdlib_when', ['greater', 1, 0], None]]} > stdlib > builtins > None
{'cnd': ['greater', 1, 0], 'thn': ['__stdlib_when', ['greater', 1, 0], None]} > stdlib > builtins > None
{'cnd': ['greater', 1, 0], 'thn': None} > stdlib > builtins > None
ちゃんと読も
ここでself._exprにマクロ本体を入れて、環境もマクロのクロージャにして、継続は$mevalで、現在の環境と継続を覚えている
case ["mclosure", params, body_expr, mclosure_env]:
mclosure_env = mclosure_env.extend(params, args_val)
self._expr, self._env, self._cont = Expr(body_expr), mclosure_env, \
["$meval", self._env, self._cont]
$mevalでは値になったマクロ本体をもう一度Exprで囲んで評価されるようにして、環境と継続をさっき保存したものに戻して・・・
あ、ここでもう環境が戻ってるのか
マクロ本体を展開したらもとの環境で評価しないとな
そりゃそうか
case ["$meval", mclosure_env, next_cont]:
self._expr, self._env, self._cont = (
Expr(self._expr), mclosure_env, next_cont
)
でも変数名がmclosure_envはおかしいな
$callに合わせてcall_envにしよう
case ["$meval", call_env, next_cont]:
self._expr, self._env, self._cont = (
Expr(self._expr), call_env, next_cont
)
kb84tkhr書いてはみたけど自信がないのでこれで末尾呼び出し最適化になってる？とAIさんに聞いてみたところseqの最後の式のところで末尾呼び出し最適化が働きませんよと言われた
そうなん？
seqで関数呼び出しするようにちょっと書き換えて継続を見る
loop := func (n) do if n > 0 then n = n - 1; loop(n) end end;
loop(3)
ほんまや・・・
['$restore_env', {'loop': ...} > ..., ['$seq', [], ['$halt']]]
['$restore_env', {} > {'n': 2} > {'loop': ...} > ..., ['$seq', [], ['$restore_env', {'loop': ...} > ..., ['$seq', [], ['$halt']]]]]
['$restore_env', {} > {'n': 1} > {'loop': ...} > ..., ['$seq', [], ['$restore_env', {} > {'n': 2} > {'loop': ...} > ..., ['$seq', [], ['$restore_env', {'loop': ...} > ..., ['$seq', [], ['$halt']]]]]]]
['$restore_env', {} > {'n': 0} > {'loop': ...} > ..., ['$seq', [], ['$restore_env', {} > {'n': 1} > {'loop': ...} > ..., ['$seq', [], ['$restore_env', {} > {'n': 2} > {'loop': ...} > ..., ['$seq', [], ['$restore_env', {'loop': ...} > ..., ['$seq', [], ['$halt']]]]]]]]]
最後の式を評価するときに$seqはずしてやればいいよとAIさん
def _apply_seq(self, exprs, next_cont):
match exprs:
case []:
self._cont = next_cont
case [expr]:
self._expr, self._cont = Expr(expr), next_cont
case [expr, *rest]:
self._expr, self._cont = Expr(expr), ["$seq", rest, next_cont]
できた
['$restore_env', {'loop': ...} > ..., ['$halt']]
['$restore_env', {'loop': ...} > ..., ['$halt']]
['$restore_env', {'loop': ...} > ..., ['$halt']]
['$restore_env', {'loop': ...} > ..., ['$halt']]
すごいなAIさん・・・
自分じゃまったく気づいてなかったし
もしこれが自分が書いたコードじゃなかったら読む気がするかどうかすら危うい
これも世の中のコードを学習してパターン認識で「このへんじゃね」ってやってるんだろうか
ちょっとそんなレベルじゃない気がしてしまうけど
とはいえそもそも本当の末尾呼び出し最適化になっていませんと言われて提示された修正を試したら動かず、問い詰めていったら最後にはあなたの実装が正しかったです、ってなったりして完全に信用するわけにもいかないなあ、という面もある
（実は本当に末尾呼び出し最適化できてなくてAIをむりやり説き伏せただけという可能性もないではない）
ちなみにGemini 2.5 Proに聞いてます
Flashだとやっぱり考察が甘いけど、会話を積み重ねればある程度結果を引き出せる感触はある
kb84tkhr末尾再起最適化が動いてるかどうか、ってなんかテスト書けるのかなあ
継続の深さをつねに監視しておくようにするとか？
とりあえず無限ループ回しても使用メモリが増えないことは確認した
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
24023 vscode 20 0 337496 34748 11136 R 100.0 0.4 5:40.40 python
このスクラップはこのへんでひと区切りかなあ
つぎ何やろうか