トイ言語実験日記（マクロと継続）
kb84tkhr
のあと、また１からトイ言語を書きたくなった。
小さなプログラミング言語処理系を書きながらちょこちょこ実験してみたい。
とりあえずのネタとしてはマクロと継続。
当分はスキャナ・パーザはなしで、評価器だけで作っていこう。
kb84tkhrフィボナッチとカウンタが実装できるだけの最小の評価器を書いてみた。
名前定義と条件分岐と再帰とクロージャ付きの関数だけを実装。
配列を使ったASTを自分で書いて実行する。
目が慣れればコードに見える（に違いない）。
run(["define", "fib", ["func", ["n"],
["if", ["=", "n", 0], 0,
["if", ["=", "n", 1], 1,
["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]]]]]])
assert run(["fib", 10]) == 55
run(["define", "make_adder", ["func", ["n"], ["func", ["m"], ["+", "n", "m"]]]])
assert run([["make_adder", 5], 6]) == 11
これが実行できるだけの機能以外付けないようにした。
とはいえこれでもうけっこういろいろ書けるはず。
足し算と引き算しかないのでかけ算は自分で書かないといけないけど。
割り算はちょっとがんばらないと書けない気がする。
kb84tkhrコードはまるごと貼り付けられるレベル。
39行。
# environment
def define(env, name, val):
env["vals"][name] = val
def get(env, name):
return env["vals"][name] if name in env["vals"] else get(env["parent"], name)
# evaluator
def eval(expr, env):
match expr:
case None | bool(_) | int(_): return expr
case str(name): return get(env, name)
case ["func", params, body]: return ["func", params, body, env]
case ["define", name, val]:
return define(env, name, eval(val, env))
case ["if", cnd, thn, els]:
return eval(thn, env) if eval(cnd, env) else eval(els, env)
case [func, *args]:
return apply(eval(func, env), [eval(arg, env) for arg in args])
def apply(f_val, args_val):
if callable(f_val): return f_val(args_val)
_, params, body, env = f_val
env = {"parent": env, "vals": dict(zip(params, args_val))}
return eval(body, env)
# runtime
builtins = {
"+": lambda args: args[0] + args[1],
"-": lambda args: args[0] - args[1],
"=": lambda args: args[0] == args[1],
}
top_env = {"parent": None, "vals": builtins}
def run(src):
return eval(src, top_env)
テストも書く。
コーナーケースとかまでは考えていない。
# tests
assert run(None) == None
assert run(5) == 5
assert run(True) == True
assert run(False) == False
run(["define", "a", 5])
assert run("a") == 5
assert run(["if", True, 5, 6]) == 5
assert run(["if", False, 5, 6]) == 6
assert run(["+", 5, 6]) == 11
assert run(["-", 11, 5]) == 6
assert run(["=", 5, 5]) == True
assert run(["=", 5, 6]) == False
assert run([["func", ["n"], ["+", 5, "n"]], 6]) == 11
run(["define", "fib", ["func", ["n"],
["if", ["=", "n", 0], 0,
["if", ["=", "n", 1], 1,
["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]]]]]])
assert run(["fib", 0]) == 0
assert run(["fib", 1]) == 1
assert run(["fib", 2]) == 1
assert run(["fib", 3]) == 2
assert run(["fib", 10]) == 55
run(["define", "make_adder", ["func", ["n"], ["func", ["m"], ["+", "n", "m"]]]])
assert run([["make_adder", 5], 6]) == 11
print("Success")
実際にはコードとテストをひとつのファイルに書いている。
実行してSuccessと表示されたら成功。
$ python toig.py
Success
すでにデバッグが地獄になることが見えているので最低限のエラー処理は入れるようにしよう。
そういう意味ではeval(expr, env)とrun(src)を分けたのも自衛策だった。
eval(expr, env=top_env)と書けばrun(src)はいらないんだけれども
意図してないところでeval(expr)と書いてしまうと変になるので。
文字列を渡して字句解析構文解析することもあるだろうということで引数はsrcという名前にした。
kb84tkhr以下のエラー処理を追加。
- 変数の二重定義
- 未定義の変数の参照
- 関数の引数の数の不一致
- 想定外の形の式
これくらいでもだいぶ助けになると思う。
テストでは、エラーになるかどうかだけを確認して、どういうエラーになるかまでは見ていない。
どういうエラーになるかまで見ていると、後で行った修正でエラーの出方が変わってしまい、テストが通らなくなることがしばしばあるので。
あと、こっそりdefineが右辺の値を返すようにしている。
schemeでは名前を返すかnullを返すのが普通な感じだけれども使い道が思いつかない。
a = b = 5が許されるなら["define", "a", ["define", "b", 5]]だって許されるのではないか。
ソース：https://github.com/koba925/toig/blob/add_error/toig.py
差分：https://github.com/koba925/toig/compare/minimum...add_error
kb84tkhr今後なにか実験をするとき、代入くらいはほしくなるはず。
代入できるようにすると、funcに（ifもかな）複数の式を並べて書きたくなるはず。
複数の式が並べて書けるようになると途中経過が知りたくなるはず。
ということでassignとdoとprintを実装した。
doは複数の式を並べるだけのもので、最後の式の値を返す。
スコープも作らない。
reduce使えば１行。
前回の結果を捨てる感じが出ているのではなかろうか。
case ["do", *exprs]:
return reduce(lambda _, e: eval(e, env), exprs, None)
func自体はひとつの式しか書けないままにしている。
なんかそのほうがピュアな感じが出るかと。
あとdefineとassignでスコープができてることを確認するテストを少し付けた。
ソース：https://github.com/koba925/toig/tree/assign_do_print
差分：https://github.com/koba925/toig/compare/add_error...assign_do_print
kb84tkhr代入を作ったらカウンタを作る。
assignが右辺の値を返すようにしたおかげで以前ならこう書かなければいけなかったものが
["define", "make_counter", ["func", [], ["do",
["define", "c", 0],
["func", [], ["do",
["assign", "c", ["+", "c", 1]],
"c"]]]]]
こう書けている。
["define", "make_counter", ["func", [], ["do",
["define", "c", 0],
["func", [], ["assign", "c", ["+", "c", 1]]]]]]
世の中なんでこうなっていないのかというと、
副作用のある式は本来値を返すべきではない（文であるべき）、ということだろうか。
しらんけど
kb84tkhrたぶん世の中がこうなっていないというのはうそ
kb84tkhrGemini Code Assistが事実上無制限に無償で使えるというので使ってみているのだけれど
GitHub CopilotやTabnineと比べて精度がかなり劣っている気がする。
このコードのバグを挙げてくれと聞いてみると４つ挙げてくれたが
どれも間違いでしかもかなり明らかな間違いだった。
Copilotに同じ質問をしてみたら、基本的には大丈夫だと前置きしたうえで
assignやgetでenvにループがあると無限ループしちゃうからチェックしたら？
とか
applyでcallableでないときはlistかどうか確認した方がよくない？
などと一理ある答えだった。
コード補完もいまひとつ。
CopilotやTabnineだと、え、なんでそんなことまでわかるの？という感じで
Tab押せば終わってしまうケースも多かったのだけれど
Geminiはこちらの意図をうまく読み取ってくれない感じ。
だからこそ無償で出してデータ集めようとしてるんだろうけど。
育ってくれるかなあ？
なにか設定がぬけてたりするんだろうかもしかして。
kb84tkhrテストの中で、今aがいくつでcは未定義で・・・とか考えてると破綻しそうだったり
ここだけちょっとテストしたいとかやりにくかったりとかするので
やっぱりテストは分けることにした。
環境を好きな時にリセットできるよう、環境の初期設定をinit_env()に入れた。
クラスを定義した方が自然なんだろうか。
自分で定義した変数とbuiltinsが混ざらないようにするため階層を分けている。
def init_env():
global top_env
top_env = {
"parent": {"parent": None, "vals": builtins.copy()},
"vals": {}
}
ソース：https://github.com/koba925/toig/tree/separate_tests
差分：https://github.com/koba925/toig/compare/assign_do_print...separate_tests
kb84tkhrさてマクロの実装に手を付けよう。
とはいってもASTが配列なので配列を扱えないとお話にならないのでまずは配列のサポートから。
最低限の機能をつけてあとは必要になったら付け足そう。
組み込み関数を追加。
配列を作るところくらいは特殊なことをしなきゃいけないかと思ったけど
引数が配列で渡されるのでそのまま返すだけだった。
特殊と言えば特殊だが。
"arr": lambda args: args,
"is_arr": lambda args: n_ary(1, lambda arr: isinstance(arr, list), args),
"len": lambda args: n_ary(1, lambda arr: len(arr), args),
"getat": lambda args: n_ary(2, lambda arr, ind: arr[ind], args),
"setat": setat,
"slice": slice,
あと+は既存のものがそのまま配列でも使えるので、これくらいあればやりたいことはできるだろう。
sliceはなくても自前で書けそうだがPythonのお力を拝借しておく。
上で呼び出されてる関数はこのあたり。
def n_ary(n, f, args):
assert len(args) == n, \
f"Argument count doesn't match: `{args}` @ n_ary"
return f(*args[0:n])
def setat(args):
assert len(args) == 3, \
f"Argument count doesn't match: `{args}` @ setat"
args[0][args[1]] = args[2]
return args[0]
def slice(args):
if len(args) == 1:
return args[0][:]
elif len(args) == 2:
return args[0][args[1]:]
elif len(args) == 3:
return args[0][args[1]:args[2]]
assert False, f"Invalid slice: args=`{args}` @ slice"
引数の数で処理を変えられるようにした方が便利かなあ？
そのためにはまず可変長の引数をうまくつかえるようにしないとか。
やりたくなったらやろう。
あとquote（クォート）を作った。
Noneと数とTrueとFalseだけではやっぱりマクロの書きようがないので。
Schemeではquoteだけど短縮形がないので"q"一文字にする。
def eval(expr, env):
match expr:
...
case ["q", expr]: return expr
...
exprをなにもせずに返すだけというもの。
run(["q", "abc"])とすると"abc"が返される。
run(["q", ["+", 5, 6]])とすると["+", 5, 6]が（11にならずに）そのまま返される。
本来の目的とはすこし違うけれどもちょっとした文字列代わりにも使える。
if __name__ == "__main__":
init_env()
run(["print", ["q", "hello"], ["q", "world"]])
これで例のメッセージが！
$ python toig.py
hello world
ソース：https://github.com/koba925/toig/tree/array_quote
差分：https://github.com/koba925/toig/compare/separate_tests...array_quote
kb84tkhr準備はできた気がするのでマクロ自体を作りこむ。
まずはmacroというキーワードでfuncとそっくりなものを作る。
...
case ["func", params, body]:
return ["func", params, body, env]
case ["macro", params, body]:
return ["macro", params, body, env]
...
作ったときのenvを覚えているので静的スコープになるわけだがその方がよいのかどうかはよくわからない。
funcだったらapplyする、のところでmacroも扱えるようにする。
...
case [op, *args]:
return eval_op(op, args, env)
...
def eval_op(op, args, env):
match eval(op, env):
case ["macro", params, body, macro_env]:
return eval(expand(body, params, args, macro_env), env)
case f_val:
return apply(f_val, [eval(arg, env) for arg in args])
def expand(body, params, args, env):
assert len(params) == len(args), \
f"Argument count doesn't match: `{args}` @ expand"
env = {"parent": env, "vals": dict(zip(params, args))}
return eval(body, env)
funcをapplyする時と違い、渡された引数を評価しないでexpandに渡しているところがひとつめのミソ。
expandは引数をそのまま環境に追加したらapply同様にbodyをevalして返す。
さらにexpandが返してきたものをASTとしてもう一度evalするところがふたつめのミソ。
これらによって動的にプログラムを書いて動かしているわけだ。
ソース：https://github.com/koba925/toig/tree/macro
差分：https://github.com/koba925/toig/compare/array_quote...macro
kb84tkhrマクロのいちばん簡単な例としてよく出てくるwhenを作る。
〇〇のときは××する、というもの。
要するにthenしかないif。
["when", ["not", ["=", "b", 0], ["/", "a", "b"]]と書いたら
["if", ["not", ["=", "b", 0]], ["/", "a", "b"], None]と変換してから実行する。
これをこう書く。
run(["define", "when", ["macro", ["cnd", "thn"],
["arr", ["q", "if"], "cnd", "thn", None]]])
これで["when", ["not", ["=", "b", 0]], ["/", "a", "b"]]と書けば
bが0でなければa÷bを、bが０だったらNoneを返してくれる。
（ここでこっそり*・/・notを追加で作っている）
これを関数も書けんじゃねとこんなふうに作ってしまうと、
run(["define", "when-f", ["func", ["cnd", "thn"],
["if", "cnd", "thn", None]]])
run(["when-f", ["not", ["=", "b", 0]], ["/", "a", "b"]])
実行したときにまず["not", ["=", "b", 0]]と["/", "a", "b"]を両方評価してから
"when-f"にapplyしようとするのでdivision by zeroになってしまう。
kb84tkhrマクロがどんな式を作ってくれてるのか見るためにexpandも追加している。
...
case ["expand", [op, *args]]:
return eval_expand(op, args, env)
...
def eval_expand(op, args, env):
match eval(op, env):
case ["macro", params, body, macro_env]:
return expand(body, params, args, macro_env)
case unexpected:
assert False, f"Macro expected: {unexpected} @ eval"
つまりexpandしたら評価せずにそのまま返しているだけ。
["expand", ["when", ["not", ["=", "b", 0]], ["/", "a", "b"]]]
を評価すれば
["if", ["not", ["=", "b", 0]], ["/", "a", "b"], None]
を返してくれる。
kb84tkhrもうひとつ簡単な例としてandとorを書いた。
andとorでマクロを使うのはショートサーキットを実現するため。
ショートサーキットとは["and", "a", "b"]としたとき、
"a"が偽なら"b"にかかわらず全体が偽になるので"b"は評価しない、というもの。
別法として["func", [], ...]で囲って遅延させてやるというのもあるがいちいちそう書くのも面倒。
when、and、orは今後も使いたくなりそうなので標準ライブラリにする。
といっても関数内でマクロ定義をrunしているだけ。
今の形ならこれで十分。
例によって環境を1階層分使って、組み込み関数やユーザ定義の名前と分離するようにしている。
def stdlib():
run(["define", "when", ["macro", ["cnd", "thn"],
["arr", ["q", "if"], "cnd", "thn", None]]])
run(["define", "and", ["macro", ["a", "b"], ["arr", ["q", "if"], "a", "b", False]]])
run(["define", "or", ["macro", ["a", "b"], ["arr", ["q", "if"], "a", True, "b"]]])
global top_env
top_env = {"parent": top_env, "vals": {}}
使うときはinit_env()とstdlib()を呼んでからrun()。
init_env()
stdlib()
run(["print", ["q", "hello"], ["q", "world"]])
ソース：https://github.com/koba925/toig/tree/and_or_stdlib
差分：https://github.com/koba925/toig/compare/macro...and_or_stdlib
kb84tkhrやってみて初めて気が付いたんだけれども、expandでは一段しかマクロを展開しない。
["expand", ["and", ["or", ["=", 5, 6], ["=", 7, 7]], ["=", 8, 8]]]
は
["if", ["or", ["=", 5, 6], ["=", 7, 7]], ["=", 8, 8], False]
になる。
与えられた引数を評価せずにそのまま置き換える、なので当然なんだけれども。
マクロを全部展開しきろうと思ったら再帰的にたどっていかないといけないのか。
実用的には１段で足りるので（むしろ全部展開されると見づらそう）全部展開は宿題にして進む。
kb84tkhrちょっと複雑な題材としてwhileをやってみる。
最初の版としては、こう書いたら、
["while", ["<", "a", 5], ["do",
["assign", "b", ["+", "b", ["arr", "a"]]],
["assign", "a", ["+", "a", 1]]]]]
こういうコードが出るようにしよう。
いろいろ気になるところはあるけどとりあえず。
["do",
["define", "loop", ["func", [],
["when", ["<", "a", 5],
["do",
["do",
["assign", "b", ["+", "b", ["arr", "a"]]],
["assign", "a", ["+", "a", 1]]],
["loop"]]]]],
["loop"]]
できあがりの式を見ながらマクロを書く。
["define", "while", ["macro", ["cnd", "body"], ["arr", ["q", "do"],
["arr", ["q", "define"], ["q", "loop"], ["arr",
["q", "func"], ["arr"], ["arr",
["q", "when"], "cnd",
["arr", ["q", "do"], "body", ["q", ["loop"]]]]]],
["q", ["loop"]]]]]
これが動くようになった。
["do",
["define", "a", 0],
["define", "b", ["arr"]],
["while", ["<", "a", 5], ["do",
["assign", "b", ["+", "b", ["arr", "a"]]],
["assign", "a", ["+", "a", 1]]]]]
次はこれを動かす。
["do",
["define", "r", ["arr"]],
["define", "c", ["arr"]],
["while", ["<", ["len", "r"], 3],
["do",
["assign", "c", ["arr"]],
["while", ["<", ["len", "c"], 3],
["assign", "c", ["+", "c", ["arr", "x"]]]],
["assign", "r", ["+", "r", ["arr", "c"]]]]]]
今は外側のwhileと内側のwhileがどちらもloopを定義しようとするのでエラーになる。
スコープを切ればいいだろう。
funcでくるんで即実行。JavaScriptでよく見かけるあれ。
直接whileの中でやってもいいけどそれだけやるマクロを書こう。
これでいいはず。
["define", "scope", ["macro", ["body"],
["arr", ["arr", ["q", "func"], ["arr"], "body"]]]]
whileの定義をくるむ。
["define", "while", ["macro", ["cnd", "body"], ["arr", ["q", "scope"],
["arr", ["q", "do"],
["arr", ["q", "define"], ["q", "loop"], ["arr",
["q", "func"], ["arr"], ["arr",
["q", "when"], "cnd",
["arr", ["q", "do"], "body", ["q", ["loop"]]]]]],
["q", ["loop"]]]]]]))
できた。
ソース：https://github.com/koba925/toig/tree/while_scope
差分：https://github.com/koba925/toig/compare/and_or_stdlib...while_scope
kb84tkhrwhileの定義はarrとqの嵐で少々見づらい。
quasiquote（準クォート）を作ろう。
quote（q）は引数を全く評価せずそのまま返し、arrは引数をすべて評価して返してくれるもの。
quasiquoteは基本的にはquoteなんだけれども、指定した部分だけは評価するというもの。
quoteがstrだとしたらquasiquoteはf-string（わかりづらい
quasiquoteでは長いのでqqとし、評価したい部分は!をつけることにする。
そうするとwhileはこんなふうに書けるはず。
["define", "while", ["macro", ["cnd", "body"], ["qq",
["scope", ["do",
["define", "loop", ["func", [],
["when", ["!", "cnd"], ["do", ["!", "body"], ["loop"]]]]],
["loop"]]]]]]
だいぶ見やすい。
def is_arr(elem): return isinstance(elem, list)
def eval_quasiquote(elem, env):
if not is_arr(elem): return elem
quoted = []
for e in elem:
match e:
case ["!", e]: quoted.append(eval(e, env))
case _: quoted.append(eval_quasiquote(e, env))
return quoted
これでできた。意外とシンプル。
ほかのマクロもqqで書き直す。
run(["define", "scope", ["macro", ["body"],
["qq", [["func", [], ["!", "body"]]]]]])
run(["define", "when", ["macro", ["cnd", "thn"],
["qq", ["if", ["!", "cnd"], ["!", "thn"], None]]]])
run(["define", "and", ["macro", ["a", "b"],
["qq", ["if", ["!", "a"], ["!", "b"], False]]]])
run(["define", "or", ["macro", ["a", "b"],
["qq", ["if", ["!", "a"], True, ["!", "b"]]]]])
andやorはかえって長くなってしまってるけれども見やすさはこちらの方が上、
・・・な気がする。
ソース：https://github.com/koba925/toig/tree/quasiquote
差分：https://github.com/koba925/toig/compare/while_scope...quasiquote
kb84tkhr次はfor e in [5, 6, 7]:的なやつを書いてみよう。
どうせ使うならwhileよりそっちのほうがいい。
こう書いたら
["for", "i", ["arr", 5, 6, 7], ["assign", "sum", ["+", "sum", "i"]]]
こう展開されるようにする。
動くことも確認。
["scope", ["do",
["define", "__index", 0],
["define", "i", None],
["while", ["<", "__index", ["len", ["arr", 5, 6, 7]]], ["do",
["assign", "i", ["getat", ["arr", 5, 6, 7], "__index"]],
["assign", "sum", ["+", "sum", "i"]],
["assign", "__index", ["inc", "__index"]]]]]]
ひとつ変数を導入する必要があって、["assign", "sum", ["+", "sum", "i"]]の中で使ってる変数とぶつからないようにしないといけないんだけれどもアンダースコアつけたくらいで逃げる。
展開前後を見比べてマクロを書く。
["define", "for", ["macro", ["e", "l", "body"], ["qq",
["scope", ["do",
["define", "__index", 0],
["define", ["!", "e"], None],
["while", ["<", "__index", ["len", ["!", "l"]]], ["do",
["assign", ["!", "e"], ["getat", ["!", "l"], "__index"]],
["!", "body"],
["assign", "__index", ["inc", "__index"]]]]]]]]]
qqがあるとやっぱり楽だなあ。
エラトステネスのふるいを書いてみた。
run(["define", "sieve", ["+",
["*", ["arr", False], 2],
["*", ["arr", True], 28]]])
run(["define", "j", None])
run(["for", "i", ["range", 2, 30],
["when", ["getat", "sieve", "i"],
["do",
["assign", "j", ["*", "i", "i"]],
["while", ["<", "j", 30], ["do",
["setat", "sieve", "j", False],
["assign", "j", ["+", "j", "i"]]]]]]])
run(["print", "sieve"])
run(["define", "primes", ["arr"]])
run(["for", "i", ["range", 0, 30],
["when", ["getat", "sieve", "i"],
["assign", "primes", ["append", "primes", "i"]]]])
run(["print", "primes"]) # → [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
range()追加とかしてたらbuiltinsやstdlibが太った。
この辺はコアじゃないから太ってもあまり気にしない。
builtins = {
...
"!=": lambda args: n_ary(2, op.ne, args),
...
"<=": lambda args: n_ary(2, op.le, args),
">=": lambda args: n_ary(2, op.ge, args),
...
}
...
def stdlib():
run(["define", "id", ["func", ["x"], "x"]])
run(["define", "inc", ["func", ["x"], ["+", "x", 1]]])
run(["define", "dec", ["func", ["x"], ["-", "x", 1]]])
run(["define", "unfoldl", ["func", ["x", "p", "h", "t"], ["do",
["define", "_unfoldl", ["func", ["x", "b"],
["if", ["p", "x"],
"b",
["_unfoldl", ["t", "x"], ["+", "b", ["arr", ["h", "x"]]]]]]],
["_unfoldl", "x", ["arr"]]]]])
run(["define", "range", ["func", ["s", "e"],
["unfoldl", "s", ["func", ["x"], [">=", "x", "e"]], "id", "inc"]]])
run(["define", "append", ["func", ["l", "a"], ["+", "l", ["arr", "a"]]]])
run(["define", "prepend", ["func", ["a", "l"], ["+", ["arr", "a"], "l"]]])
...
slice()はmatchで書けばいいじゃんと思って書き直し。
def slice(args):
match args:
case [arr]: return arr[:]
case [arr, start]: return arr[start:]
case [arr, start, end]: return arr[start:end]
case _: assert False, f"Invalid slice: args=`{args}` @ slice"
コミットを分けたりはしていない（誰に向かって言っているのか
ソース：https://github.com/koba925/toig/tree/for-in
差分：https://github.com/koba925/toig/compare/quasiquote...for-in
kb84tkhrlet（ぽいもの）も作ってみよう。
letはローカル変数を作る構文で、
["let", [["a", 5], ["b", 6]], ["+", "a", "b"]]
と書くと11になる。
上のletはこんな風に展開するようにする。
["scope", ["do",
["define", "a", 5],
["define", "b", 6],
["+", "a", "b"]]]
手でこう書いてもそう変わらないのでstdlibには入れないつもり。
[["a", 5], ["b", 6]]の処理と、doの中身の処理がこれまでよりも少し複雑になる。
[["a", 5], ["b", 6]]をdefineの並びに変換する処理は関数にする。
["define", "defines", ["func", ["bindings"],
["map", "bindings", ["func", ["b"], ["qq",
["define",
["!", ["first", "b"]],
["!", ["last", "b"]]]]]]]]
（mapはこっそりstdlib()に追加している）
この関数をどこに覚えておくかというと、マクロ内部に閉じ込めておく。
静的スコープにしているのでこれができる。
doの中身についてはこんな感じで書ければいいんだけれども、
["qq", ["scope", ["do", ["!", ["defines", "bindings"]], ["!", "body"]]]]]]])
これではこうなってしまう（doの後ろにカッコがひとつ多い）。
["scope", ["do", [
["define", "a", 5],
["define", "b", 6],
["+", "a", "b"]]]]
配列の+を使えばやってできないことはなくてたとえばこう書ける（後半のqq）。
["define", "let", ["macro", ["bindings", "body"], ["do",
["define", "defines", ["func", ["bindings"],
["map", "bindings", ["func", ["b"], ["qq",
["define",
["!", ["first", "b"]],
["!", ["last", "b"]]]]]]]],
["qq", ["scope", ["!", ["append",
["+",
["q", ["do"]],
["defines", "bindings"]],
"body"]]]]]]]
いちおうletの第一弾ができた。
kb84tkhrこのへんがめんどくさいので書きやすくする。
["qq", ["scope", ["!", ["append",
["+",
["q", ["do"]],
["defines", "bindings"]],
"body"]]]]
qqにunquote-splicingという機能をつける。
!!のときはappendの代わりに+を使う。
["do"]に[6, 7]をsplicingでくっつけると、["do", [6, 7]]とならずに["do", 6, 7]となる。
def eval_quasiquote(elem, env):
if not is_arr(elem): return elem
quoted = []
for e in elem:
match e:
case ["!", e]: quoted.append(eval(e, env))
case ["!!", e]:
vals = eval(e, env)
assert isinstance(vals, list), f"Cannot splice in quasiquote: {e}"
quoted += vals
case _: quoted.append(eval_quasiquote(e, env))
return quoted
!!の処理でassertを入れているのは警告よけ。
これでさっきの式がこう書ける。
["qq", ["scope", ["do",
["!!", ["defines", "bindings"]],
["!","body"]]]]
考えてみると、doの構文を["do", <expr>, <expr>, ...]とせずに、可変部分を配列にして["do", [<expr>, <expr>, ...]]としたほうがスジがよかったのかもしれない。ASTとしては。人間が読み書きすることを考えるとネストが浅くなる方がうれしいんだけれども。
なにはともあれ、マクロもちょっと書きやすくなってきたのでは。
ソース：https://github.com/koba925/toig/tree/let_qqspl
差分：https://github.com/koba925/toig/compare/for-in...let_qqspl
kb84tkhrcondを書いてみよう。
condはifの親戚のようなもので[<条件>, <式>, <式>, ...]という形を並べて、
条件に合ったところの式を評価するというもの。
["define", "fib", ["func", ["n"],
["if", ["=", "n", 0], 0,
["if", ["=", "n", 1], 1,
["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]]]]]]
と同じものをcondで書くとこうなる。
["define", "fib", ["func", ["n"],
["cond",
[["=", "n", 0], 0],
[["=", "n", 1], 1],
[True, ["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]]]]]]
条件をTrueにした行はほかがどれも実行されなかったときに実行される。
ifのelseにあたる部分。
このcondはこう展開されるようにする。
["if", ["=", "n", 0], 0,
["if", ["=", "n", 1], 1,
["if", True, ["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]],
None]]]]
if-Trueはもうちょっとキレイにできそうだけれども気が向いたら。
[<条件>, <式>, <式>, ...]と式を並べられるようにするかどうかも考えどころ。
今のところ式を並べるのはdoに任せているので、その原則を崩すかどうか。
kb84tkhrそしてcond自身も可変長の引数を取るのでまずは可変長引数を受け取れるようにしないと。
これも配列に入れてしまうという手はあるけど。
関数とかifとかはピュアな関数を扱っている限り複数の式を書ける必要がない。
condは複数の節を並べられるということに意味がある。
ということで並べて書ける意味が大きい。
ということにしておく。
可変長引数を試したいというだけだったりもする。
今まで
env = {"parent": env, "vals": dict(zip(params, args))}
の1行で済ませていたものを以下の関数を呼ぶようにした。
なんか急に膨れ上がったけれどもエラー処理の行数が多いせいで、じっさいやってることはたいしたことはない。
from itertools import zip_longest
def extend(env, params, args):
sentinel, new_env = object(), {}
for i, (param, arg) in enumerate(zip_longest(params, args, fillvalue=sentinel)):
match param:
case str(param):
assert arg is not sentinel, \
f"Argument count doesn't match: `{params}, {args}` @ extend"
new_env[param] = arg
case ["*", rest]:
assert i == len(params) - 1, \
f"Rest param must be last: `{params}` @ extend"
new_env[rest] = args[i:]; break
case unexpected:
assert param is not sentinel, \
f"Argument count doesn't match: `{params}, {args}` @ extend"
assert False, f"Unexpected param at extend: {unexpected}"
return {"parent": env, "vals": new_env}
とはいえもうちょっとなんとかならないかという気もする。
for i in range...とかあんまりやりたくないのだけれどかといってzip_longestとか若干やりすぎな気がしなくもない。
再帰で書いた方がいいかもしれない。
これで["macro", ["op", ["*", "r"]], ["+", ["arr", "op"], "r"]]みたいに書けるようになった。
expandだけでなくapplyでもextendを呼んでいるので、関数でも使える。
kb84tkhrそういえばmacroとかquasiquoteのテストを書いてなかったなと気が付いて付け足してみたら通らなかった。
["qq", ["!", ["+", 5, 6]]]という単純な式が正しく評価できない。
!の処理を配列の中でしか行ってなくて、最上位に!があるとダメ。
単に["arr", ["+", 5, 6]]と書けばいいだけなのでユースケースはないんだけれども気持ちわるいので直した。
def eval_quasiquote(expr, env):
def qqelems(elems):
quoted = []
for elem in elems:
match elem:
case ["!!", e]:
vals = eval(e, env)
assert isinstance(vals, list), f"Cannot splice in quasiquote: {e}"
quoted += vals
case _: quoted.append(eval_quasiquote(elem, env))
return quoted
match expr:
case ["!", elem]: return eval(elem, env)
case [*elems]: return qqelems(elems)
case _: return expr
本題に戻ってcondの実装。
ifとたいして変わらないのでstdlibには入れていない。
run(["define", "cond", ["macro", [["*", "clauses"]],
["do",
["define", "_cond", ["func", ["clauses"],
["if", ["=", "clauses", ["arr"]],
None,
["do",
["define", "clause", ["first", "clauses"]],
["define", "cnd", ["first", "clause"]],
["define", "thn", ["last", "clause"]],
["qq", ["if", ["!", "cnd"],
["!", "thn"],
["!", ["_cond", ["rest", "clauses"]]]]]]]]],
["_cond", "clauses"]]]])
できてる。
self.assertEqual(expanded(
["cond",
[["=", "n", 0], 0],
[["=", "n", 1], 1],
[True, ["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]]]]),
["if", ["=", "n", 0], 0,
["if", ["=", "n", 1], 1,
["if", True,
["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]],
None]]])
run(["define", "fib", ["func", ["n"],
["cond",
[["=", "n", 0], 0],
[["=", "n", 1], 1],
[True, ["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]]]]]])
self.assertEqual(run(["fib", 0]), 0)
self.assertEqual(run(["fib", 1]), 1)
self.assertEqual(run(["fib", 2]), 1)
self.assertEqual(run(["fib", 3]), 2)
self.assertEqual(run(["fib", 10]), 55)
ソース：https://github.com/koba925/toig/tree/cond_restparam
差分：https://github.com/koba925/toig/compare/let_qqspl...cond_restparam
kb84tkhrところで、現状のマクロはほとんど関数と同じ扱いでeval中にも存在しているのでファーストクラス。
関数の引数にしたり関数の戻り値にしたり配列に入れたりできる。
def test_macro_firstclass(self):
self.assertEqual(run([["func", ["op", "a", "b"], ["op", "a", "b"]], "and", True, False]), False)
self.assertEqual(run([["func", ["op", "a", "b"], ["op", "a", "b"]], "or", True, False]), True)
self.assertEqual(run([[["func", [], "and"]], True, False]), False)
self.assertEqual(run([[["func", [], "or"]], True, False]), True)
self.assertEqual(run(["map",
["arr", "and", "or"],
["func", ["op"], ["op", True, False]]]),
[False, True])
実用的な使い道があるのかというとあんまり自信ない。
kb84tkhrおもしろいマクロにアナフォリックマクロというのがあります。
アナフォリックとは代名詞のことです。
アナフォリックマクロifやwhileで条件を評価するとitなどの変数に条件節の評価結果が入り、その後の計算で使えるというもの。
たとえば["aif", ["dec", 1], 5, "it"]を評価するとitに["dec", 1]の評価結果である0が入り、0は偽とみなされるのでitつまり0がこの式の値となります。
マクロは簡単。条件節を先に評価してitを定義しているだけです。
スコープで囲んでいるのでifの外に出るとitは消えます。
run(["define", "aif", ["macro", ["cnd", "thn", "els"],
["qq", ["scope", ["do",
["define", "it", ["!", "cnd"]],
["if", "it", ["!", "thn"], ["!", "els"]]]]]]])
これだけだとなにがうれしいのってなるかと思いますがここではandとorでaifを使うようにしました。
JavaScriptなんかでfoo || "default value"のような書き方をして,fooがnull（偽に評価される）だったときのデフォルト値を指定するイディオムがあります。そういうことができるようになります。
if foo then foo else "default"みたいに処理してしまうとfooを２回評価する必要があるのでもったいなかったり、fooに副作用があると２回実行されてしまったりして不都合がありますがこの書き方だとfooは一度しか評価されません。
run(["define", "and", ["macro", ["a", "b"],
["qq", ["aif", ["!", "a"], ["!", "b"], "it"]]]])
run(["define", "or", ["macro", ["a", "b"],
["qq", ["aif", ["!", "a"], "it", ["!", "b"]]]]])
想定通り動きます。
self.assertEqual(printed(["scope", ["do",
["define", "foo", 5],
["print", ["or", "foo", ["q", "default"]]],
["assign", "foo", None],
["print", ["or", "foo", ["q", "default"]]]
]]), (None, "5\ndefault\n"))
2回評価されてないことまではテストしてませんけど。
awhileは作ってません。まあいいや。
kb84tkhr再帰で書いた方がいいかもしれない。
忘れてた。
やってみた。
def extend(env, params, args):
def new_env(params, args):
if params == [] and args == []: return {}
assert len(params), \
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"
return {param: args[0], **new_env(params[1:], args[1:])}
case ["*", rest]:
assert len(params) == 1, \
f"Rest param must be last: `{params}` @ extend"
return {rest: args}
case unexpected:
assert False, f"Unexpected param at extend: {unexpected}"
return {"parent": env, "vals": new_env(params, args)}
行数はあんまりかわってないけど技使いましたっていう感じがなくなってよくなった気がする。
配列をコピーしまくりではあるが何を今さらである。
根っこの配列と、どこからどこまでを使うのかという情報を持つようにした新しい配列型を作れば罪悪感が消せるかもしれないけれどもPythonの型をそのまま使うポリシーで進めてきてるのでそういうのはまた別でやろう。
ソース：https://github.com/koba925/toig/tree/extend_recursion
差分：https://github.com/koba925/toig/compare/first_class_macro...extend_recursion
kb84tkhrこのextendを見てるとエラーにする代わりにカリー化できそうな気がしてきた。
カリー化というのはたとえば"add"が["func", ["a", "b"], ["+", "a", "b"]]だったとして、["add", 5]と書いたときにエラーにするのではなくが["func", ["b"], ["+", 5, "b"]]という関数に評価してあげる機能のこと。手動で["define", "curried-add", ["func", ["b"], ["add", 5, "b"]]`と書いてもカリー化なので、自動カリー化という方がいいのかもしれない。そもそもこれはカリー化ではなくて部分適用というのかもしれない。
argsを全部使い果たしたのにparamsが残ってる場合はenvを拡張して関数本体を評価するのではなく、argsにある分だけenvに入れ、残ったparamsを引数に取る関数のクロージャに評価されるようにすればいいはずだ。
extend自身は関数本体を知らないので、呼び出し側と連携してやる必要がある。
extendは拡張されたenvと、残ったparamsを返し、paramsを全部使いきってるかどうかで呼び出し側が動作を変えてやればいいだろう。
可変長引数とは若干相性が悪い気がする・・・けど大丈夫そうかな。
やってみる。
def extend(env, params, args):
def _extend(params, args):
if params == [] and args == []: return [[], {}]
assert params != [], \
f"Argument count doesn't match: `{params}, {args}` @ extend"
match params[0]:
case str(param):
if args == []: return [params, {}]
rest_params, new_env = _extend(params[1:], args[1:])
return [rest_params, {param: args[0], **new_env}]
case ["*", rest]:
assert len(params) == 1, \
f"Rest param must be last: `{params}` @ extend"
return [[], {rest: args}]
case unexpected:
assert False, f"Unexpected param at extend: {unexpected}"
rest_params, new_env = _extend(params, args)
return [rest_params, {"parent": env, "vals": new_env}]
def expand(body, params, args, env):
rest_params, new_env = extend(env, params, args)
return ["macro", rest_params, body, new_env] if rest_params else eval(body, new_env)
def apply(f_val, args_val):
if callable(f_val): return f_val(args_val)
_, params, body, env = f_val
rest_params, new_env = extend(env, params, args_val)
return ["func", rest_params, body, new_env] if rest_params else eval(body, new_env)
マクロがカリー化できるとうれしいのかどうかよくわからないがやらないと不自然なのでやっておく。
これはマクロがファーストクラスだからかな。
self.assertTrue(run([[["func", ["n"], ["+", 5, "n"]]], 6]), 11)
run(["define", "add", ["func", ["a", "b"], ["+", "a", "b"]]])
self.assertEqual(run([["add", 5], 6]), 11)
self.assertEqual(run([[["add"], 5], 6]), 11)
run(["define", "add3", ["func", ["a", "b", "c"], ["+", ["+", "a", "b"], "c"]]])
self.assertEqual(run([["add3", 5], 6, 7]), 18)
self.assertEqual(run([["add3", 5, 6], 7]), 18)
self.assertEqual(run([[["add3", 5], 6], 7]), 18)
動いた。
残念ながら組み込み関数の評価時にはextendは使わないので組み込み関数は自動ではカリー化できないのでこんなテストに。
カリー化が本質的なところなのかピンと来ていないのでメインには組み込まないで様子を見る。
カリー化する計画はなくて関数の引数の順番もカリー化とあってないし。
たとえばmapはリストを先頭に書くようにしてた。ufcsとか意識して。
カリー化できると便利だなあ、という例が出てきたら考えよう。
コードは思ったより複雑化させずに動かせて満足している。
["add"]が"add"そのものに評価されるのはそれでいいのかという気分にもなっている。
（[[["add"], 5], 6]のこと)
ソース：https://github.com/koba925/toig/tree/autocurry
差分：https://github.com/koba925/toig/compare/extend_recursion...autocurry
kb84tkhrマクロ関連で実装してみたい機能はだいたい実装した気がする。
・・・で、evalするまえに全部マクロを展開する、というのをやろうと思ったのだがうまい実装が思いつかない。
evalする前にと言ってもマクロの中身はevalしなきゃいけないし。
事前のマクロ展開の構造はevalに似たものになるだろうとは想像してたけど、マクロ内の関数を呼び出すことを考えるとevalでできることはまるまるできる必要がある？
できることを制限してたりするんだっけ？
コンパイラだったら、マクロ展開用にインタプリタも持っている？
いったん寝かせよう。
kb84tkhrこんどはletccの実装にトライする。
["letcc", "skip-to", <式>]という式を評価すると現在の「継続」（continuation）にskip-toという名前でアクセスできるようになる。
「継続」はプログラムの実行状況みたいなもの。
継続は関数のように呼び出すことができて、["skip-to", 5]を評価するとあたかも["letcc", ...]が5を返したような状態になってプログラムが動き続ける。
もうすこし具体的に書けば、["print", ["letcc", "skip-to", <式>]]を評価したあと、["skip-to", 5]を評価すると、そのときプログラムのどこを評価中であってもこの式に戻ってきて["print", 5]が評価される、というわけ。
これがあるとループのbreakとかtry/catchだとかジェネレータだとかを自分で実装できるようになる。
はず。
程度のいいgotoみたいなものなので用法・用量にはご注意ください。
kb84tkhrで、letccをどうやって実装するか、つまり今どこにいるかをどうやって覚えておくかなんだけれども継続渡しスタイル（Continuation Passing Style：CPS）というのを使えばできるはず。
CPSの呼び出しは関数の呼び出しと違って、戻り値を返さない。というか戻ってこない。
その代わり、呼んだ先でやることやったらその結果を使ってこれを呼び出してね、とやる。
Node.jsが出たときコールバックのネストが深くなってコールバック地獄という言葉が使われてたけれども実はあれがCPSだったりする。
Pythonで実装するときは関数を使うしかないのだけれども戻り値は使わないというのが基本スタイルになる。
簡単な実例でいくと、継続渡しの加算はこういう関数になる。
def add_cps(a, b, cont): cont(a + b)
aとbを足したら、その結果をcontに渡してね、という意味。
cont(a + b)にreturnがついてないことに注意。戻り値は使わない。
これで5+6を計算して結果を出力したい場合はこのように使う。
add_cps(5, 6, lambda r: print(r))
11がprintされることはわかるだろう。
5+6+7ならこう。
add_cps(5, 6, lambda r: add_cps(r, 7, lambda r2: print(r2)))
もうすこし練習。
kb84tkhrすこし複雑な例。
def factorial_cps(n, cont):
if n == 0:
cont(1)
else:
factorial_cps(n - 1, lambda r: cont(n * r))
factorial_cps(5, lambda r: print(r))で120が出力される。
１ステップずつ追いかけてみる。
5だと死にそうなので2から。
factorial_cps(2, lambda r: print(r))
= factorial_cps(1, lambda r: (lambda r: print(r))(2 * r))
= factorial_cps(0, lambda r: (lambda r: (lambda r: print(r))(2 * r))(1 * r))
= (lambda r: (lambda r: (lambda r: print(r))(2 * r))(1 * r))(1)
= (lambda r: (lambda r: print(r))(2 * r))(1 * 1)
= (lambda r: print(r))(2 * 1)
= print(2)
日本語に訳すとこんな感じ。
2のfactorialを計算したらprintしてね
= 1のfactorialを計算したら2をかけてprintしてね
= 0のfactorialを計算したら1をかけて2をかけてprintしてね
= 0のfactorialは1です 0のfactorialに1をかけて2をかけてprintするよ
= 1に1をかけて2をかけてprintするよ
= 1に2をかけてprintするよ
= 2をprintするよ
CPSだとどうやってletccを実現できるのか。
factorial_cpsにすこし細工をして、途中でcontを覚えておくようにする。
def factorial_cps(n, cont):
global cc
if n == 0:
cont(1)
else:
if n == 3: cc = cont
factorial_cps(n - 1, lambda r: cont(n * r))
factorial_cps(5, lambda r: print(r))を実行すると120が出力されるのは同じだけれど、n=3のときのcontがccに保存されている。
これは日本語で言うと「3のfactorialを計算したら4をかけて5をかけてprintしてね」をccが覚えているということ。
3のfactorialは6だから、cc(6)としてやればあと4をかけて5をかけてprintしてくれるはず。
>>> cc(6)
120
ccは何度でも呼べるし、それどころか3のfactorialを渡してやる必要もない。何を渡しても4をかけて5をかけてprintしてくれる。
>>> cc(6)
120
>>> cc(6)
120
>>> cc(1)
20
このへんが「継続は関数のように呼び出すことができて、["skip-to", 5]を評価するとあたかも["letcc", ...]が5を返したような状態になってプログラムが動き続ける」を実現するしくみになる。
cc(1)で言えば、「あたかもfactorial_cps(3)の結果が1だったような状態になってプログラムが動き続け」ているわけ。
kb84tkhr今どこにいるかというのはASTのここ、という情報で、あとその時の環境を覚えておけばそこから評価を再開することができるようになると思うのだけれど、継続渡しで継続を積み重ねていくことが現在位置までASTを再構築していくことになってるんだと思う。
もしかしたら関数にして覚えるのではなくて普通の木を構築しながらでもいいのかもしれない。
そうするとどこで実際に評価するんだ？
kb84tkhrevalをCPSに書き直す前に予行演習をしておこう。
ifをCPSで書いてみる。こういうことになるだろうか。
def if_cps(cnd_cps, thn_cps, els_cps, cont):
cnd_cps(lambda cnd: thn_cps(cont) if cnd else els_cps(cont))
equal_cpsも作って試してみる。
def equal_cps(a, b, cont): cont(a == b)
if_cps(lambda cont: equal_cps(5, 5, cont),
・・・thn_cpsやels_cpsには何を入れたらいいんだろう？
"Yes"とか"No"が出力されるくらいでいいんだけど、thn_cpsやels_cpsは継続を受け取る関数だから"Yes"とか"No"ではない。
こういうことになる？
if_cps(lambda cont: equal_cps(5, 5, cont),
lambda cont: cont("Yes"),
lambda cont: cont("No"),
print)
if_cps(lambda cont: equal_cps(5, 6, cont),
lambda cont: cont("Yes"),
lambda cont: cont("No"),
print)
動いた。でもどうもしっくりきていない。
lambda cont: cont(xx)は関数を定義してみよう。
def const_cps(c): return lambda cont: cont(c)
if_cps(lambda cont: equal_cps(5, 5, cont),
const_cps("Yes"),
const_cps("No"),
print)
if_cps(lambda cont: equal_cps(5, 6, cont),
const_cps("Yes"),
const_cps("No"),
print)
今までlambda r: print(r)って書いてたけどただprintでよかった。
明示的になる、っていう意味がないことはないけど。
lambda cont: equal_cps(5, 6, cont)もなんとかしたいところ。
カリー化してくれるならequal_cps(5, 6)って書けば済んでしまうのに。
ああ、手動でカリー化すればいいのか。
def equal_cps2(a, b): return lambda cont: cont(a == b)
equal_cps2(5, 5)(lambda r: print(r))
equal_cps2(5, 6)(lambda r: print(r))
if_cps(equal_cps2(5, 5),
const_cps("Yes"),
const_cps("No"),
lambda r: print(r))
if_cps(equal_cps2(5, 6),
const_cps("Yes"),
const_cps("No"),
lambda r: print(r))
想定通り動く。見た目も多少すっきりした。
cnd_cpsを少しだけ複雑にしてみよう。
def add_cps2(a, b): return lambda cont: cont(a + b)
add_cps2(5, 6)(print)
if_cps(add_cps2(5, 6)(lambda r: equal_cps2(r, 11)),
const_cps("Yes"),
const_cps("No"),
print)
if_cps(add_cps2(5, 6)(lambda r: equal_cps2(r, 12)),
const_cps("Yes"),
const_cps("No"),
print)
動いてる。
こんな感じでいいんだろうか。
しっくりこなさがまだ解消していない気がする。
なにこれ。
kb84tkhrif_cpsはすべての引数をCPSで受け取っている。
if_cps(cnd_cps, thn_cps, els_cps, cont)
（まだカリー化してない形）
一方、equal_cpsは直接値を受け取っている。
equal_cps(a, b, cont): cont(a == b)
あまり考えてなかったけれどもequal_cpsもCPSで引数を受け取るべきなのか。
add_cpsも同様。
const_cpsは定数を渡すという機能だから除外だろう。
定数じゃなくて値を渡す、のかな。まあいいや今は。
そこまでやる？って気もするけど書けば書ける。
def equal_cps3(a_cps, b_cps):
return lambda cont: a_cps(lambda a: b_cps(lambda b:cont(a == b)))
equal_cps3(const_cps(5), const_cps(5))(print)
equal_cps3(const_cps(5), const_cps(6))(print)
if_cps(equal_cps3(const_cps(5), const_cps(5)),
const_cps("Yes"),
const_cps("No"),
print)
if_cps(equal_cps3(const_cps(5), const_cps(6)),
const_cps("Yes"),
const_cps("No"),
print)
なんとなく統一感が出た。もしかしてこれか？
add_cpsも値ではなく継続を値に取るようにする。
def add_cps3(a_cps, b_cps):
return lambda cont: a_cps(lambda a: b_cps(lambda b: cont(a + b)))
add_cps3(const_cps(5), const_cps(6))(print)
if_cpsもカリー化する。
def if_cps2(cnd_cps, thn_cps, els_cps):
return lambda cont: cnd_cps(lambda cnd: thn_cps(cont) if cnd else els_cps(cont))
if_cps2(
equal_cps3(add_cps3(const_cps(5), const_cps(6)), const_cps(11)),
const_cps("Yes"),
const_cps("No")
)(print)
if_cps2(
equal_cps3(add_cps3(const_cps(5), const_cps(6)), const_cps(12)),
const_cps("Yes"),
const_cps("No")
)(print)
これ、長いようなちょっとウザいような感じだけど、_cpsを取っちゃえばかなり普通の式に見える。
if(equal(add(const(5), const(6)), const(12)),
const("Yes"),
const("No")
)(print)
コールバック地獄みたいなものは少なくとも表面上は見えなくなった。
これっぽい。
const_cpsまで全部CPSにするのと、contをカリー化するのがポイント。
すぐできるかなと思ってたifで思った以上に悩まされたのでwhileとかもやってみよう。
kb84tkhrprint_cpsも作ったらもっと見やすくなるかな？と思ったけどそうは問屋が卸さなかった。
def print_cps(val_cps):
return lambda cont: val_cps(lambda val: (print(val), cont())[1])
print_cps(const_cps(5))(lambda: None)
print_cps(const_cps(5))(lambda: print_cps(const_cps(6))(lambda: None))
print_cps(if_cps2(
equal_cps3(add_cps3(const_cps(5), const_cps(6)), const_cps(11)),
const_cps("Yes"),
const_cps("No")
))(lambda: None)
print_cps(if_cps2(
equal_cps3(add_cps3(const_cps(5), const_cps(6)), const_cps(12)),
const_cps("Yes"),
const_cps("No")
))(lambda: None)
print_cpsは値を持たないという前提で引数なしのcontを受け取ることにしている。
それはいいとして、結局最後に(lambda: None)をつけないといけないとか、
続けて出力しようとしたときにlambda: print_cps(const_cps(6))とlambdaをつけなければいけないとかがいまひとつ。
すっきり書ける方法はあるかな？
なお(print(val), cont())[1]はprint(val)してcont()してcont()の値を返す式。
気持ちはprint(val); cont()のようなもの。
Pythonのlambdaではそういうの書けないので。
続くCPS呼び出しが、contの引数の数を把握していないといけないというのも気になってきた。
printには値を期待していないはずなのでcontに引数は不要なはず。
同じように、contに複数の引数がある場合も考えられる。
(lambda: None)とか(lambda r: r)とかprintって書くときは引数の数を合わせて書かないといけない。
受け取れればいいなら(lambda *r: r)ってする手もあるか。
kb84tkhr（関数名に_cps2とか_cps3とつけてわけわからなくなってきたので少しわかりやすく変える）
whileやってみようと言いつつif_cps_fullができたんならfoldl_cps_fullとかmap_cps_fullとかすぐ書けんじゃね？と思って始めたらけっこうハマった。
最初のバージョン。引数に直接値を取り、カリー化もしないもの。
これはいい。
def foldl_cps(l, f, init, cont):
if l == []:
cont(init)
else:
f(init, l[0], lambda r: foldl_cps(l[1:], f, r, cont))
foldl_cps([5, 6, 7], add_cps, 0, print)
次のバージョンはカリー化しただけ。
これもいい。
print("## foldl_cps_curried")
def foldl_cps_curried(l, f, init):
return lambda cont: (
cont(init) if l == []
else f(init, l[0])(lambda r: foldl_cps_curried(l[1:], f, r)(cont))
)
foldl_cps_curried([5, 6, 7], add_cps_curried, 0)(print)
で引数もCPS化しようとする。
うまくできたっぽいif_cps
こんな感じで呼びたい。
foldl_cps_full(const_cps([5, 6, 7]), add_cps_full, const_cps(0))(print)
配列はconst_cps([5, 6, 7])でいいのか？
これだとl[0]では取り出せないし、取り出せたとしても生の5が取り出されてしまう。
const_cps(5)が取り出されるべきな気がする。
じゃあconst_cps([const_cps(5), const_cps(6), const_cps(7)])って書くべきなのか？
試行錯誤しつつたどり着いたやり方はfirst（l[0]に相当）とrest（l[1:]に相当）を書くことだった。first_cps_full(const_cps([5, 6, 7]))でconst_cps(5)が取り出せる。
def first_cps_full(l_cps):
return lambda cont: l_cps(lambda l: cont(l[0]))
def rest_cps_full(l_cps):
return lambda cont: l_cps(lambda l: cont(l[1:]))
これとif_cps_fullを使うとなんかいい感じに書き換えられた。
def foldl_cps_full(l, f, init):
return if_cps_full(
equal_cps_full(l, const_cps([])),
init,
foldl_cps_full(rest_cps_full(l), f, f(init, first_cps_full(l)))
)
だめだった。
>>> foldl_cps_full(const_cps([5, 6, 7]), add_cps_full, const_cps(0))(print)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/workspaces/toig/cps.py", line 186, in foldl_cps_full
foldl_cps_full(rest_cps_full(l), f, f(init, first_cps_full(l)))
File "/workspaces/toig/cps.py", line 186, in foldl_cps_full
foldl_cps_full(rest_cps_full(l), f, f(init, first_cps_full(l)))
File "/workspaces/toig/cps.py", line 186, in foldl_cps_full
foldl_cps_full(rest_cps_full(l), f, f(init, first_cps_full(l)))
[Previous line repeated 995 more times]
File "/workspaces/toig/cps.py", line 184, in foldl_cps_full
equal_cps_full(l, const_cps([])),
^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded
無条件でfoldl_cps_fullを再帰呼び出ししているため。
こういうときはlambda:でくるんでやるんだってじっちゃんが言ってた。
ifの側で()をつけて剥いてあげる。
def if_cps_delayed(cnd_cps, thn_cps, els_cps):
return cnd_cps(lambda cnd: thn_cps() if cnd else els_cps())
def foldl_cps_delayed(l, f, init):
return if_cps_delayed(
equal_cps_full(l, const_cps([])),
lambda: init,
lambda: foldl_cps_delayed(rest_cps_full(l), f, f(init, first_cps_full(l)))
)
動いた。
kb84tkhr関連する関数を全部まとめるとこう。
名前の_fullとか_delayedは削ってある。
def const_cps(c):
return lambda cont: cont(c)
def equal_cps(a_cps, b_cps):
return lambda cont: a_cps(lambda a: b_cps(lambda b: cont(a == b)))
def add_cps(a_cps, b_cps):
return lambda cont: a_cps(lambda a: b_cps(lambda b: cont(a + b)))
def if_cps(cnd_cps, thn_cps, els_cps):
return cnd_cps(lambda cnd: thn_cps() if cnd else els_cps())
def first_cps(l_cps):
return lambda cont: l_cps(lambda l: cont(l[0]))
def rest_cps(l_cps):
return lambda cont: l_cps(lambda l: cont(l[1:]))
def foldl_cps(l, f, init):
return if_cps(
equal_cps(l, const_cps([])),
lambda: init,
lambda: foldl_cps(rest_cps(l), f, f(init, first_cps(l)))
)
foldl_cps(const_cps([5, 6, 7]), add_cps, const_cps(0))(print)
いい感じだ。
kb84tkhrfoldl_cpsができたならmap_cpsもできるはず。
素朴（？）なやつ。
こういうのも悪くはない気がしている。返り値使ってない感が出てて。
def map_cps(l, f, cont):
if l == []:
cont([])
else:
f(l[0], lambda r: map_cps(l[1:], f, lambda r2: cont([r] + r2)))
map_cps([5, 6, 7], lambda a, cont: add_cps(a, 1, cont), print)
カリー化したやつ。
lambdaが式ひとつしかかけないのがねえ。
def map_cps_curried(l, f_curried):
return lambda cont: (
cont([]) if l == [] else
f_curried(l[0])(lambda r: map_cps_curried(l[1:], f_curried)(lambda r2: cont([r] + r2))))
map_cps_curried([5, 6, 7], lambda a: add_cps_curried(a, 1))(print)
式を複数書きたいだけならタプルに入れる手がある。
文を書きたいときは内部関数を定義するくらいかなあ。
print("## map_cps_curried_def")
def map_cps_curried_def(l, f_curried):
def _map(l, cont):
if l == []:
cont([])
else:
f_curried(l[0])(lambda r: _map(l[1:], lambda r2: cont([r] + r2)))
return lambda cont: _map(l, cont)
map_cps_curried_def([5, 6, 7], lambda a: add_cps_curried(a, 1))(print)
カリー化までやるなら完全CPS化までもっていきたい。
しばらくうまく書けなくて悩んだけれども、配列を作るCPS関数が必要だった。
あと配列の連結にただの+を使おうとしてたというのもあった。
いろいろパーツが必要。
def array_cps_full(*es_cps_full):
return (const_cps([]) if es_cps_full == () else
es_cps_full[0](lambda r: add_cps_full(
const_cps([r]),
array_cps_full(*es_cps_full[1:]))))
array_cps_full()(print)
array_cps_full(const_cps(5))(print)
array_cps_full(const_cps(5), const_cps(6))(print)
array_cps_full(add_cps_full(const_cps(5), const_cps(6)))(print)
mapの実装では要素ひとつの配列を作るだけなので実はこれで用は足りるのだけれども。
練習を兼ねて。
def array_cps_full(e_cps_full):
return lambda cont: cont([e_cps_full(lambda r: r)])
できた。
def map_cps_delayed(l_cps, f):
return if_cps_delayed(
equal_cps_full(l_cps, const_cps([])),
lambda: const_cps([]),
lambda: add_cps_full(
array_cps_full(f(first_cps_full(l_cps))),
map_cps_delayed(rest_cps_full(l_cps), f)))
map_cps_delayed(
const_cps([5, 6, 7]),
lambda a_cps_full: add_cps_full(a_cps_full, const_cps(1))
)(print)
add_cps_fullをもう一段カリー化したらすっきりするかな？
def add_cps_full_more_curried(a_cps):
return lambda b_cps: lambda cont: a_cps(lambda a: b_cps(lambda b: cont(a + b)))
と定義すれば上のmap_cps_delayed呼び出しはこうなる。
map_cps_delayed(
const_cps([5, 6, 7]),
add_cps_full_more_curried(const_cps(1))
)(print)
でもadd_cps_full_more_curriedはfoldl_cps_delayedの引数としては使えない。
引数をふたつ取る関数を期待しているから。
lambda a, b: add_cps_full_more_curried(a)(b)って書いたり引数の数で２バージョン作ったりするのもちょっと気が進まないのでlambda a_cps_full: add_cps_full(a_cps_full, const_cps(1))でがまんする。
いい書き方思いついたら考える。
kb84tkhrfoldlを使ってmapを作ることもできる。
def map_cps_delayed_foldl(l_cps, f):
return foldl_cps_delayed(l_cps,
lambda acc_cps_full, e_cps_full: add_cps_full(
acc_cps_full,
array_cps_full(f(e_cps_full))),
const_cps([]))
map_cps_delayed_foldl(
const_cps([5, 6, 7]),
lambda a_cps_full: add_cps_full(a_cps_full, const_cps(1))
)(print)
この引数は生の値だっけCPSでくるんだ値だっけと混乱しているので引数にも_cpsとかつけてみた。
_cpsであるべきか_cps_fullであるべきかは揺れている。
_cpsは継続を返すよと言うことで_fullは継続を引数に取る関数だよと言うことだから意味は違ってる。
あまり気にしすぎないことにする。
kb84tkhrほったらかしになってたwhile_cpsを作ろう。
while_cps作るならless_cpsもあるのが自然かな。
equal_cpsとかadd_cpsと同じパターンなので共通化しておく。
_fullパターンだけ作る。
import operator as op
def binop_cps_full(op, a_cps, b_cps):
return lambda cont: a_cps(lambda a: b_cps(lambda b: cont(op(a, b))))
def equal_cps_full(a_cps, b_cps):
return binop_cps_full(op.eq, a_cps, b_cps)
def add_cps_full(a_cps, b_cps):
return binop_cps_full(op.add, a_cps, b_cps)
def less_cps_full(a_cps, b_cps):
return binop_cps_full(op.lt, a_cps, b_cps)
共通化したからと言って行が減るわけではないけれども。
kb84tkhrless_cpsができたらwhile_cpsはこんな風に使いた
while_cps_delayed(
less_cps_full(
less_cps_full(i, const_cps(5))って書きたいけど変数がない。
定義も代入もない。
やめとく？
もうちょっとやってみよう。
ミニ環境作るか。
env = {}
def set_cps_full(name, val_cps):
env[name] = val_cps
return val_cps
def get_cps_full(name):
return env[name]
set_cps_full("i", const_cps(5))(print)
get_cps_full("i")(print)
set_cps_full("i", add_cps_full(get_cps_full("i"), const_cps(6)))(print)
変数名はCPSで渡さなくていいよな。
スコープつけるとかしないのでまあこれでいけるのでは。
kb84tkhr改めて、while_cpsはこんな風に使いたい。
ifと違って条件を何度も評価する必要があるので条件も遅延させる必要がある。
while_cps_delayed(
lambda: less_cps_full(get_cps_full("i"), const_cps(5)),
lambda: do_cps_full(
print_cps_full(get_cps_full("sum")),
set_cps_full("sum", add_cps_full(get_cps_full("sum"), get_cps_full("i"))),
set_cps_full("i", add_cps_full(get_cps_full("i"), const_cps(1)))))
代入作るなら複文・・・じゃないな複式も必要か。なかなか。
こう・・・かな？
最後に評価した式の値を返すようにする。
内部関数の_do_cps_fullはfoldr_cpsと構造は同じなんだけれども*exprsは継続の配列で、foldr_cpsが期待している引数は配列の継続なので使えない。
rは最後のcont(r)だけで使われ、それまでは全部捨てられる。
def do_cps_full(*exprs):
def _do_cps_full(exprs, r, cont):
if len(exprs) == 0: cont(r)
else: exprs[0](lambda r: _do_cps_full(exprs[1:], r, cont))
return lambda cont: _do_cps_full(exprs, None, cont)
do_cps_full()(print)
do_cps_full(
set_cps_full("i", const_cps(5)),
set_cps_full("i", add_cps_full(get_cps_full("i"), const_cps(1)))
)(print)
get_cps_full("i")(print)
これでやっとwhile_cpsに着手できる。
というのはうそで本当は着手してからいろいろ必要なことに気づいて作ってたのでもうできている。
def while_cps_delayed(cnd_cps_delayed, body_cps_delayed):
def _while_cps_delayed(r, cont):
cnd_cps_delayed()(lambda cnd:
cont(r) if not cnd
else body_cps_delayed()(lambda r: _while_cps_delayed(r, cont)))
return lambda cont: _while_cps_delayed(None, cont)
set_cps_full("fac", const_cps(1))(lambda r: r)
set_cps_full("i", const_cps(1))(lambda r: r)
while_cps_delayed(
lambda: less_cps_full(get_cps_full("i"), const_cps(6)),
lambda: do_cps_full(
set_cps_full("fac", mul_cps_full(get_cps_full("fac"), get_cps_full("i"))),
set_cps_full("i", add_cps_full(get_cps_full("i"), const_cps(1)))))(print)
get_cps_full("i")(print)
get_cps_full("fac")(print)
ごちゃごちゃしてるけど_cps*と(lambda r: r)を取っちゃえばこれくらい。
(lambda r: r)は渡さなくても副作用は発生している。
許容範囲だろう。
set("fac", const(0))
set("i", const(0))
while(
lambda: less(get("i"), const(5)),
lambda: do(
set("fac", add(get("fac"), get("i"))),
set("i", add(get("i"), const(1)))))
get("i")(print)
get("fac")(print)
lambda:は取れないなあ。
マクロがあれば。
kb84tkhrところでgetとsetは意図的にCPSにしたわけではないんだけれども覚えてる値が継続なのでCPSのように見えているパターン。
evalの環境ではもうすこし複雑な関数になるけどなにか落とし穴はないだろうか？
kb84tkhrfactorial_cpsも完全CPS化。
def factorial_cps_delayed(n_cps_full):
return if_cps_delayed(
equal_cps_full(n_cps_full, const_cps(0)),
lambda: const_cps(1),
lambda: mul_cps_full(
n_cps_full,
factorial_cps_delayed(sub_cps_full(n_cps_full, const_cps(1)))))
factorial_cps_delayed(const_cps(5))(print)
そして途中で継続をキャプチャする版。
contは暗黙の引数になっているのでlambda cont:で明示的に継続を取り出す。
あとcontを保存するときもconst_cpsでラップする。
def factorial_cps_cc(n_cps_full):
return lambda cont: if_cps_delayed(
equal_cps_full(n_cps_full, const_cps(0)),
lambda: const_cps(1),
lambda: do_cps_full(
if_cps_delayed(
equal_cps_full(n_cps_full, const_cps(3)),
lambda: set_cps_full("cc", const_cps(cont)),
lambda: const_cps(None)
),
mul_cps_full(
n_cps_full,
factorial_cps_cc(sub_cps_full(n_cps_full, const_cps(1)))))
)(cont)
factorial_cps_cc(const_cps(5))(print) → 120
get_cps_full("cc")(const_cps(3)) → 60
できたな。
これくらいでletccが作れるか・・・？
ソース：https://github.com/koba925/toig/blob/cps_practice/cps.py
kb84tkhrいよいよevalをCPS化しようと思うのだが、CPSに変更しようとすると全面的に書き換えになるのでちょっと恐怖を感じる。
一度minimumに戻って試そう。
上位から修正していく。
runではsrcとtop_envをCPSにして、恒等関数に継続させる。
eval_cps以下、CPS呼び出しの関数名や変数名には_cpsをつけていく。
def cps(expr):
return lambda cont: cont(expr)
def identity(x): return x
def run(src):
return eval_cps(cps(src), cps(top_env))(identity)
eval_cpsでは、まずこの部分のテストを通すところから。
assert run(None) == None
assert run(5) == 5
assert run(True) == True
assert run(False) == False
cps1(lambda val1: cps2(lambda val2: ...))という形が頻発しそうなので関数にしておく。
（けどそんなにすっきりはしない・・・）
matchはif_cpsみたいに関数にできる気がしなかったので内部関数を作った。
def cpscall2(cps1, cps2, body):
return cps1(lambda val1: cps2(lambda val2: body(val1, val2)))
def eval_cps(expr_cps, env_cps):
def _eval(expr, env, cont):
match expr:
case None | bool(_) | int(_): return cont(expr)
...
return lambda cont: cpscall2(expr_cps, env_cps,
lambda expr, env: _eval(expr, env, cont))
次はこれ。
run(["define", "a", 5])
assert run("a") == 5
これでおｋ。
def eval_cps(expr_cps, env_cps):
def _eval(expr, env, cont):
match expr:
case str(name): return get(env, name)(cont)
case ["define", name, val]:
return define(env, name, eval_cps(cps(val), cps(env)))
defineのnameは直で使う。
define()やget()は修正なく使えている。
cpsから値を出したりcpsに戻したりしてるのが気になる。
完全CPSにする意味あるのかと半信半疑になりながら進む。
kb84tkhrif。
assert run(["if", True, 5, 6]) == 5
assert run(["if", False, 5, 6]) == 6
if_cpsは練習の時のを流用。
def if_cps(cnd_cps, thn_cps, els_cps):
return cnd_cps(lambda cnd: thn_cps() if cnd else els_cps())
def eval_cps(expr_cps, env_cps):
def _eval(expr, env, cont):
match expr:
case ["if", cnd, thn, els]:
return if_cps(eval_cps(cps(cnd), cps(env)),
lambda: eval_cps(cps(thn), cps(env)),
lambda: eval_cps(cps(els), cps(env)))(cont)
ソースは今ガワだけcps化して中身は都度都度cpsにしてるけど、最初から全部cpsにしておけば少しは片付くかな？
ここ。
eval_cps(cps(src), cps(top_env))(identity)
今はこのまま進める。
kb84tkhr次は組み込み関数。
assert run(["+", 5, 6]) == 11
assert run(["-", 11, 5]) == 6
assert run(["=", 5, 5]) == True
assert run(["=", 5, 6]) == False
apply中の組み込み関数とユーザ定義関数の見分け方は後に回す。
def apply_cps(f_val, args_val):
return f_val(args_val)
eval_cpsはmap_cpsさえあればこれでよさそうなんだけれども・・・
def eval_cps(expr_cps, env_cps):
def _eval(expr, env, cont):
match expr:
case [func, *args]:
return apply_cps(
eval_cps(cps(func), cps(env)),
map_cps(cps(args),
lambda arg_cps: eval_cps(arg_cps, cps(env)))
)(cont)
map_cpsを書くためにお膳立てがたくさん必要。
import operator as op
def binop_cps(op, a_cps, b_cps):
return lambda cont: a_cps(lambda a: b_cps(lambda b: cont(op(a, b))))
def equal_cps(a_cps, b_cps):
return binop_cps(op.eq, a_cps, b_cps)
def add_cps(a_cps, b_cps):
return binop_cps(op.add, a_cps, b_cps)
def sub_cps(a_cps, b_cps):
return binop_cps(op.sub, a_cps, b_cps)
def array_cps(*es_cps):
return (cps([]) if es_cps == () else
es_cps[0](lambda r: add_cps(
cps([r]),
array_cps(*es_cps[1:]))))
def first_cps(l_cps):
return lambda cont: l_cps(lambda l: cont(l[0]))
def rest_cps(l_cps):
return lambda cont: l_cps(lambda l: cont(l[1:]))
def foldl_cps(l_cps, f_cps, init_cps):
return if_cps(
equal_cps(l_cps, cps([])),
lambda: init_cps,
lambda: foldl_cps(rest_cps(l_cps), f_cps,
f_cps(init_cps, first_cps(l_cps)))
)
def map_cps(l_cps, f):
return foldl_cps(l_cps,
lambda acc_cps, e_cps: add_cps( acc_cps, array_cps(f(e_cps))),
cps([]))
報われるだろうか。
組み込み関数もCPSに。
builtins = {
"+": lambda args_cps: add_cps(first_cps(args_cps), first_cps(rest_cps(args_cps))),
"-": lambda args_cps: sub_cps(first_cps(args_cps), first_cps(rest_cps(args_cps))),
"=": lambda args_cps: equal_cps(first_cps(args_cps), first_cps(rest_cps(args_cps))),
}
ユーザ定義関数を動かそうとしてどん詰まっている
どこかなにかおかしい
おかしいのにテストが通ってしまったり
何もかも関数になってしまってるのでデバッグが地獄
どこまでをCPSでやってどこで橋渡しするとか
envには生の値を保存するのかCPS関数のまま保存するのか
kb84tkhrenvには生の値を保存するのかCPS関数のまま保存するのか
今までの実装は値をCPS関数のままenvに保存してたけど生の値を取り出してから保存しよう。
正しさとか美しさとかよりもまずはデバッグのしやすさ優先で。
生の値が見えるところが増えるのはありがたい。
このあたり。
環境周りはCPS化せずそのまま使う方針にしているので、defineやgetを呼びだすときにCPS関数と通常の関数の橋渡しをしている。
def eval_cps(expr_cps, env_cps):
def _eval(expr, env, cont):
match expr:
case str(name): return cont(get(env, name))
case ["define", name, val]:
eval_cps(cps(val), cps(env))(lambda v: define(env, name, v))
return cont(None)
ビルトイン関数ももとの姿に。
builtins = {
"+": lambda args: args[0] + args[1],
"-": lambda args: args[0] - args[1],
"=": lambda args: args[0] == args[1],
}
でapply周り。
def extend(env, params, args):
return {"parent": env, "vals": dict(zip(params, args))}
def apply_cps(f_val_cps, args_val_cps):
def _apply_cps(f_val, cont):
match f_val:
case ["func", params, body, env]:
new_env = args_val_cps(lambda args: extend(env, params, args))
return eval_cps(cps(body), cps(new_env))(cont)
case f if callable(f):
return args_val_cps(lambda args_val: cont(f(args_val)))
return lambda cont: f_val_cps(lambda f_val: _apply_cps(f_val, cont))
args_val_cps(lambda args: ...)などとして生の値を取り出すところはできるだけ減らしたいと思っているのだけれどもいったん動かすことを優先。
組み込み関数の判定も生の値にしてから行っている。
本当はこんな形に持って行きたいんだけれども。
return if_cps(callable_cps(f_val_cps),
lambda: _apply_builtin_func_cps(f_val_cps, args_val_cps),
lambda: _apply_user_func_cps(f_val_cps, args_val_cps))
だいぶ間が空いてしまったけれども当初の目的だったletccをやってみる。
これを動かそう。
assert run(["letcc", "skip-to", ["+", 5, 6]]) == 11
assert run(["letcc", "skip-to", ["+", ["skip-to", 5], 6]]) == 5
skip-toに継続を覚えてさせておくだけで、それを関数のように評価すると継続が実行される・・・かな？。
apply_cpsのしくみがそのまま使えそう。
skip-toを呼ばなければ普通に式を評価するだけ。
引数もapply_cpsの中で渡されるので配列に入った形になっている。
lambda args: ... args[0]で取り出す。
def eval_cps(expr_cps, env_cps):
def _eval(expr, env, cont):
match expr:
case ["letcc", name, body]:
return apply_cps(
cps(["func", [name], body, env]),
cps([lambda args: cont(args[0])]))(cont)
だめだった。
skip-toを評価して5を返してくれるのはいいんだけど、そのまま6を足す流れに戻ってしまった。
そりゃそうだ。
それまでにやってたことを忘れてもらう必要がある。
raiseで抜けるようにしよう。
例外にlambda: cont(args[0])を覚えさせてexceptで取り出して実行する。
class Skip(Exception):
def __init__(self, skip): self.skip = skip
def eval_cps(expr_cps, env_cps):
def _eval(expr, env, cont):
match expr:
case ["letcc", name, body]:
def skip(args): raise Skip(lambda: cont(args[0]))
return apply_cps(cps(["func", [name], body, env]), cps([skip]))(cont)
runでつかまえればいいかな？
不完全なことはわかってるけど（２回skipを呼んだら拾ってくれない）これで試す。
def run(src):
try:
return eval_cps(cps(src), cps(top_env))(identity)
except Skip as s:
return s.skip()
だめだった。
assert run(["letcc", "skip-to", ["+", 5, 6]]) == 11 # OK
assert run(["letcc", "skip-to", ["+", ["skip-to", 5], 6]]) == 5 # OK
assert run(["+", 5, ["letcc", "skip-to", ["skip-to", 6]]]) == 11 # だめ
３つめの式で<function>が返ってきてしまう。
そうなる？
kb84tkhrcontがわからん・・・
["+", 5, 6]を評価しながらデバッガで_evalに渡されたcontを見てみる。
見てみると言っても関数なのでそのままではわからないから呼んでみる。
["+", 5, 6]を評価するとき：
cont = <function identity at 0x7f6f4216cfe0>
cont(11) = 11
["+", 5, 6]を評価したら継続(identity)に値を渡すよ、ということなのでこれはOK。
つぎに5を評価するとき。
5を評価するときのcontは5を渡すと6を評価して+を評価して5と6に+を適用してidentityに値を渡す（結果は11）、という継続だと思っていたのだけれども
cont = <function array_cps.<locals>.<lambda> at 0x7f6f420f3ec0>
cont(5) = <function binop_cps.<locals>.<lambda> at 0x7f6f42178220>
なんなのこれ？
cont(5)は関数だというのでさらに呼び出してみる。
cont(5)(identity) =[5]
うーん。
すこしステップ実行を進めると
case None | bool(_) | int(_): return cont(expr)
からarray_cps内のadd_cpsを呼ぶ。
ここでやっていることはまさしくcont(5)なわけだけれども。
def array_cps(*es_cps):
return (cps([]) if es_cps == () else
es_cps[0](lambda r: add_cps(
cps([r]),
array_cps(*es_cps[1:]))))
そのまま実行を続けると11になるんだけれども。
cont(5)を単独で実行しても<function>が返されるだけでさらに呼んでも[5]が返ってくるだけ。
["+", 5, 6]の途中で終わってしまってるっぽい感じ。
return cont(expr)とreturnした後が大事？
contに続きの処理全部が入ってるわけじゃなくてreturnの後の処理は再現できないの？
なにかしたら再現できる？
ちょっと頭がついていかない。
kb84tkhrじゃあreturnを使わない素朴なCPSで書いたらどうなる？
minimumに戻って書き直す。
今回はそんなに大々的な書き換えは不要だった（letccは未実装）。
これくらいの変更で動いた。
# evaluator
def eval(expr, env, cont):
match expr:
case None | bool(_) | int(_): cont(expr)
case ["func", params, body]: cont(["func", params, body, env])
case str(name): cont(get(env, name))
case ["define", name, expr]:
eval(expr, env, lambda val: define(env, name, val))
cont(None)
case ["if", cnd_expr, thn_expr, els_expr]:
eval(cnd_expr, env, lambda cnd:
eval(thn_expr, env, cont) if cnd else
eval(els_expr, env, cont))
case [func_expr, *args_expr]:
eval(func_expr, env, lambda func_val:
map_cps(args_expr,
lambda arg_expr, c: eval(arg_expr, env, c),
lambda args_val: apply(func_val, args_val, cont)))
def foldl_cps(l, f, init, cont):
cont(init) if l == [] else \
f(init, l[0], lambda r: foldl_cps(l[1:], f, r, cont))
def map_cps(l, f, cont):
foldl_cps(l,
lambda acc, e, cont: f(e, lambda r: cont(acc + [r])),
[], cont)
def apply(func_val, args_val, cont):
match func_val:
case f if callable(f): cont(func_val(args_val))
case ["func", params, body_expr, env]:
env = {"parent": env, "vals": dict(zip(params, args_val))}
eval(body_expr, env, cont)
evalは値を返さなくなったのでrunでは変数を書き換える継続を渡している。
def run(src):
def save(val): nonlocal result; result = val
result = None
eval(src, top_env, save)
return result
ただしsetrecursionlimitを広げておかないと["fib", 10]がスタックオーバーフローする。
import sys
sys.setrecursionlimit(14000)
14000て。
そういえば完全CPSにトライしてた時は広げずに済んでたなあと気づくなど。
呼び出しは多かったはずなのに。
やっぱり継続がどこかで切れて継続しなくなってた？
ソース：https://github.com/koba925/toig/blob/minimum_naive_cps/toig.py
差分：https://github.com/koba925/toig/compare/minimum...minimum_naive_cps
kb84tkhrこれにletccをつける。
やってることは完全CPSのときと同じ。
runでは何度も継続が呼ばれてもいいようにループを回している。
class Skip(Exception):
def __init__(self, skip): self.skip = skip
def eval(expr, env, cont):
match expr:
case ["letcc", name, body]:
def skip(args): raise Skip(lambda: cont(args[0]))
apply(["func", [name], body, env], [skip], cont)
def run(src):
def save(val): nonlocal result; result = val
result, computation = None, lambda: eval(src, top_env, save)
while True:
try:
computation()
return result
except Skip as s:
computation = s.skip
あっさり動いた。
assert run(["letcc", "skip-to", ["+", 5, 6]]) == 11
assert run(["letcc", "skip-to", ["+", ["skip-to", 5], 6]]) == 5
assert run(["+", 5, ["letcc", "skip-to", ["skip-to", 6]]]) == 11
assert run(["letcc", "skip1", ["+", ["skip1", ["letcc", "skip2", ["+", ["skip2", 5], 6]]], 7]]) == 5
run(["define", "inner", ["func", ["raise"], ["raise", 5]]])
run(["define", "outer", ["func", [],
[ "letcc", "raise", ["+", ["inner", "raise"], 6]]]])
assert run(["outer"]) == 5
代入とか複式とかがないと面白い応用が思いつかない。
ソース：https://github.com/koba925/toig/blob/minimum_naive_cps_letcc/toig.py
差分：https://github.com/koba925/toig/compare/minimum_naive_cps...minimum_naive_cps_letcc
kb84tkhr素朴CPS版のCPSをカリー化してみたり値を返すようにしてみたりしても動く。
カリー化版：https://github.com/koba925/toig/tree/minimum_curried_cps
値を返す版：https://github.com/koba925/toig/tree/minimum_cps_return_value
完全CPS化でどっかおかしくしてるっぽい。
あるいは完全CPS化なんてできない？
なおカリー化だけしたものとか値を返すようにしたものとかは素朴CPS版よりたいしていい感じがしない。
完全CPS版か素朴CPS版かだな。
完全CPS化で一部いい感じに書けるところもあってやりたい気持ちが高まってたけど今は素朴CPS版でいいような気もしてきている。
kb84tkhr完全CPS版に戻ってもう一度見てみたけどなんでcont呼んでも継続が途中で切れてしまうのかやっぱりわからない。
未練がないことはないんだけれども素朴CPSで先へ進めよう。
素朴CPS版だとこんなふうに継続の入れ子で書かないといけないところが
case [func_expr, *args_expr]:
return eval(func_expr, env)(lambda func_val:
map_cps(args_expr, lambda arg_expr: lambda c: eval(arg_expr, env)(c))
(lambda args_val: apply(func_val, args_val)(cont)))
完全CPS版ならちょっと普通っぽく書けたりするのはよかったんだけど。
case [func, *args]:
f_val_cps = eval_cps(cps(func), cps(env))
args_val_cps = map_cps(
cps(args),
lambda arg_cps: eval_cps(arg_cps, cps(env)))
return apply_cps(f_val_cps, args_val_cps)(cont)
あとmatch_cpsが作れればもっとよかったんだけど。
動かないやつだけどソース：https://github.com/koba925/toig/tree/minimum_cps_letcc
kb84tkhrextendを再帰に書き換えたときの https://github.com/koba925/toig/tree/extend_recursion に戻ってletcc付き素朴CPS版の https://github.com/koba925/toig/blob/minimum_naive_cps_letcc/toig.py を見ながらちょっとずつCPSに書き換えていく。
テストをごっそりコメントアウトして、テストしたいところだけ戻しながら。
静的型付き言語だったらごっそり書き換えてからでないと動かせないけどPythonですから。
kb84tkhrこれを通す。
def test_primitives(self):
self.assertEqual(run(None), None)
self.assertEqual(run(5), 5)
self.assertEqual(run(True), True)
self.assertEqual(run(False), False)
letccを導入するまではこのrunで行こう。
def run(src):
def save(val): nonlocal result; result = val
result = None
eval(src, top_env, save)
return result
evalにcontを追加して、単なる値だったら継続を適用する。
returnは不要。
def eval(expr, env, cont):
match expr:
case None | bool(_) | int(_): cont(expr)
当分はstdlibはなし。
class TestToig(unittest.TestCase):
def setUp(self):
init_env()
# stdlib()
通った。
kb84tkhr次は変数の定義・参照・代入。
右辺にはまだ値しか書けない。
def test_define(self):
self.assertEqual(run(["define", "a", 11]), 11)
self.assertEqual(run("a"), 11)
self.assertTrue(fails(["define", "a", 6]))
self.assertTrue(fails("b"))
def test_assign(self):
self.assertEqual(run(["define", "a", 5]), 5)
self.assertEqual(run(["assign", "a", 11]), 11)
self.assertEqual(run("a"), 11)
self.assertTrue(fails(["assign", "b", 6]))
この版のdefineやassignでは右辺の値を返すようにしているので minimum_naive_cps_letcc 版とはすこし形が変わる。
getやassignはCPS化せずそのまま使う。
def eval(expr, env, cont):
match expr:
case str(name): cont(get(env, name))
case ["define", name, expr]:
eval(expr, env, lambda val: cont(define(env, name, val)))
case ["assign", name, expr]:
eval(expr, env, lambda val: cont(assign(env, name, val)))
通った。
kb84tkhrifもとりあえず最低限のテストで。
def test_if(self):
self.assertEqual(run(["if", True, 5, 6]), 5)
self.assertEqual(run(["if", False, 5, 6]), 6)
これはすぐ通る。
def eval(expr, env, cont):
match expr:
case ["if", cnd_expr, thn_expr, els_expr]:
eval(cnd_expr, env, lambda cnd:
eval(thn_expr, env, cont) if cnd else
eval(els_expr, env, cont))
組み込み関数を通す。このへん。
def test_builtin_math(self):
def test_builtin_equality(self):
def test_builtin_comparison(self):
def test_builtin_logic(self):
def test_print(self):
def test_array(self):
マクロとの分岐があったりしてちょっと複雑になっている。
必要なところだけ直す。
def eval(expr, env, cont):
match expr:
case [op_expr, *args_expr]:
eval(op_expr, env, lambda op: eval_op(op, args_expr, env, cont))
def eval_op(op, args_expr, env, cont):
match op:
case func:
map_cps(args_expr,
lambda arg_expr, c: eval(arg_expr, env, c),
lambda args: apply(func, args, cont))
def apply(func, args, cont):
if callable(func):
cont(func(args))
通った。
kb84tkhrユーザ定義関数。
練習で実装済みなのはここまで。
def test_func(self):
self.assertEqual(run([["func", ["n"], ["+", 5, "n"]], 6]), 11)
self.assertTrue(fails([["func", ["n"], ["+", 5, "n"]]]))
self.assertTrue(fails([["func", ["n"], ["+", 5, "n"]], 6, 7]))
組み込み関数でガワはできてるので実は修正箇所は少ない。
extendはCPSにせずそのまま使う。
def eval(expr, env, cont):
match expr:
case ["func", params, body]:
cont(["func", params, body, env])
def apply(func, args, cont):
if callable(func):
cont(func(args))
else:
_, params, body, env = func
env = extend(env, params, args)
eval(body, env, cont)
do。ここから未練習ゾーン。でもきっと大丈夫。
def test_do(self):
self.assertEqual(run(["do"]), None)
self.assertEqual(run(["do", 5]), 5)
self.assertEqual(run(["do", 5, 6]), 6)
self.assertEqual(printed(["do", ["print", 5]]), (None, "5\n"))
self.assertEqual(printed(["do", ["print", 5], ["print", 6]]), (None, "5\n6\n"))
作っててよかったfoldl_cps（わざとらしい）。
def eval(expr, env, cont):
match expr:
case ["do", *exprs]:
foldl_cps(exprs, lambda _, expr, c: eval(expr, env, c), None, cont)
マクロのCPS化。
いくつかまとめて修正しないとテストできない。
def test_quote(self):
self.assertEqual(run(["q", 5]), 5)
self.assertEqual(run(["q", ["+", 5, 6]]), ["+", 5, 6])
def test_macro(self):
self.assertEqual(expanded([["macro", [], ["q", "abc"]]]), "abc")
self.assertEqual(
expanded([["macro", ["a"], ["arr", ["q", "*"], "a", "a"]], ["+", 5, 6]]),
["*", ["+", 5, 6], ["+", 5, 6]])
run(["define", "build_exp", ["macro", ["op", ["*", "r"]],
["+", ["arr", "op"], "r"]]])
self.assertEqual(expanded(["build_exp", "+"]), ["+"])
self.assertEqual(expanded(["build_exp", "+", 5]), ["+", 5])
self.assertEqual(expanded(["build_exp", "+", 5, 6]), ["+", 5, 6])
修正箇所は多めだけれども淡々と。
def eval(expr, env, cont):
match expr:
case ["q", elem]: cont(elem)
case ["macro", params, body]:
cont(["macro", params, body, env])
case ["expand", [op_expr, *args_expr]]:
eval_expand(op_expr, args_expr, env, cont)
def eval_expand(op_expr, args_expr, env, cont):
def _eval_expand(op):
match op:
case ["macro", params, body, macro_env]:
expand(body, params, args_expr, macro_env, cont)
case unexpected:
assert False, f"Macro expected: {unexpected} @ eval_expand"
eval(op_expr, env, _eval_expand)
def eval_op(op, args_expr, env, cont):
match op:
case ["macro", params, body, macro_env]:
expand(body, params, args_expr, macro_env,
lambda expanded: eval(expanded, env, cont))
case func:
map_cps(args_expr,
lambda arg_expr, c: eval(arg_expr, env, c),
lambda args: apply(func, args, cont))
def expand(body, params, args, env, cont):
env = extend(env, params, args)
eval(body, env, cont)
あとはqqをやっつければ。
def test_qq(self):
self.assertEqual(run(["qq", 5]), 5)
self.assertEqual(run(["qq", ["+", 5, 6]]), ["+", 5, 6])
self.assertEqual(run(["qq", ["!", ["+", 5, 6]]]), 11)
self.assertEqual(run(["qq", ["*", 4, ["!", ["+", 5, 6]]]]), ["*", 4, 11])
self.assertEqual(run(["qq", ["+", ["!!", ["arr", 5, 6]]]]), ["+", 5, 6])
self.assertTrue(fails(["qq", ["+", ["!!", 5]]]))
whileで変換してたところを再帰で書き直す必要がある。たぶん。
そこはfoldlにまかせた。
ここが一番複雑かもしれんね。
def eval(expr, env, cont):
match expr:
case ["qq", elem]: eval_quasiquote(elem, env, cont)
def eval_quasiquote(expr, env, cont):
def splice(quoted, elem_vals, cont):
assert isinstance(elem_vals, list), \
f"Cannot splice: {elem_vals} @ eval_quasiquote"
cont(quoted + elem_vals)
def unquote_splice(quoted, elem, cont):
match elem:
case ["!!", e]:
eval(e, env, lambda e_val: splice(quoted, e_val, cont))
case _:
eval_quasiquote(elem, env,
lambda elem_val: cont(quoted + [elem_val]))
match expr:
case ["!", elem]: eval(elem, env, cont)
case [*elems]: foldl_cps(elems, unquote_splice, [], cont)
case _: cont(expr)
コア部分ができれはstdlibを解禁して残りのテストも全部通るはず。
class TestToig(unittest.TestCase):
def setUp(self):
init_env()
stdlib()
通った。
setrecursionlimitは270000。
フリーザ様にも近づこうかという勢い。
import sys
sys.setrecursionlimit(270000)
そしてletccの実装。
class Skip(Exception):
def __init__(self, skip): self.skip = skip
def eval(expr, env, cont):
match expr:
case ["letcc", name, body]:
def skip(args): raise Skip(lambda: cont(args[0]))
apply(["func", [name], body, env], [skip], cont)
def run(src):
def save(val): nonlocal result; result = val
result, computation = None, lambda: eval(src, top_env, save)
while True:
try:
computation()
return result
except Skip as s:
computation = s.skip
テストも通る。
def test_letcc(self):
self.assertEqual(run(["letcc", "skip-to", ["+", 5, 6]]), 11)
self.assertEqual(run(["letcc", "skip-to", ["+", ["skip-to", 5], 6]]), 5)
self.assertEqual(run(["+", 5, ["letcc", "skip-to", ["skip-to", 6]]]), 11)
self.assertEqual(run(["letcc", "skip1", ["+", ["skip1", ["letcc", "skip2", ["+", ["skip2", 5], 6]]], 7]]), 5)
run(["define", "inner", ["func", ["raise"], ["raise", 5]]])
run(["define", "outer", ["func", [],
[ "letcc", "raise", ["+", ["inner", "raise"], 6]]]])
self.assertEqual(run(["outer"]), 5)
できた！
ソース：https://github.com/koba925/toig/tree/cps
差分：https://github.com/koba925/toig/compare/cps_practice...cps
kb84tkhr代入も複式も書けるようになったのでletccのテストを増やそう。
と思って継続を後で使うパターンを書いてみたら早速失敗した。
def test_letcc_reuse(self):
run(["define", "add5", None])
self.assertEqual(run(["+", 5, ["letcc", "cc", ["do", ["assign", "add5", "cc"], 6]]]), 11)
self.assertEqual(run(["add5", 7]), 12)
self.assertEqual(run(["add5", 8]), 13)
run(["add5", 7])がNoneを返している。
このコードで例外をキャッチしてからの動作をデバッガで追いかけてみると、いったんはsave(12)が呼ばれるようだがその後なぜかresultの値が変わってしまうようだ。
saveはもう呼ばれないのに。saveがクロージャになっててrunのresultとは別物になってる？
nonlocalがついてても？
def run(src):
def save(val):
nonlocal result; result = val
result = None
computation = lambda: eval(src, top_env, save)
while True:
try:
computation()
return result
except Skip as s:
computation = s.skip
どこで値が変わってるのか見れないかと思ってresultをグローバル変数にしてみたら通ってしまった。
なにそれこわい。
とりあえずこれで進めようと思うけどもうちょっとキレイな渡し方はないものか。
せっかくreturn消せたからできればreturnで返すのはなしで。
result = None
def run(src):
def save(val):
global result; result = val
computation = lambda: eval(src, top_env, save)
while True:
try:
computation()
return result
except Skip as s:
computation = s.skip
``return的なものを書く。
このevalはreturnと書かなくても値を返すようになってるけど、これは関数の評価を途中で止めて呼び出し元に戻るというもの。
def test_letcc_return(self):
run(["define", "early-return", ["func", ["n"],
["letcc", "return", ["do",
["if", ["=", "n", 1], ["return", 5], 6],
7]]]])
self.assertEqual(run(["early-return", 1]), 5)
self.assertEqual(run(["early-return", 2]), 7)
returnしたら7は評価されない。
kb84tkhrこれをマクロにする。
funcという名前で定義できれば意識せずに使えるのだけれども残念ながらそういうことができるつくりにはなっていないのでruncという名前にした。
run(["define", "runc", ["macro", ["params", "body"], ["qq",
["func", ["!", "params"], ["letcc", "return", ["!", "body"]]]]]])
動く。
run(["define", "early_return_runc", ["runc", ["n"], ["do",
["if", ["=", "n", 1], ["return", 5], 6],
7]]])
self.assertEqual(run(["early_return_runc", 1]), 5)
self.assertEqual(run(["early_return_runc", 2]), 7)
入れ子にしても動いてるようだ。
run(["define", "early_return_runc2", ["runc", ["n"], ["do",
["if", ["=", ["early_return_runc", "n"], 5], ["return", 6], 7],
8]]])
self.assertEqual(run(["early_return_runc2", 1]), 6)
self.assertEqual(run(["early_return_runc2", 2]), 8)
次は例外処理っぽいのをやってみたい。
とりあえず深い階層から脱出するだけのを書いてみる。
def test_letcc_escape(self):
run(["define", "riskyfunc", ["func", ["n", "escape"], ["do",
["if", ["=", "n", 1], ["escape", 5], 6],
7]]])
run(["define", "middlefunc", ["func", ["n", "escape"], ["do",
["riskyfunc", "n", "escape"],
8]]])
run(["define", "parentfunc", ["func", ["n"],
["letcc", "escape", ["middlefunc", "n", "escape"]]]]])
self.assertEqual(run(["parentfunc", 1]), 5)
self.assertEqual(run(["parentfunc", 2]), 8)
やってることはあまりreturnと変わらないしescapeを渡して回らないといけないのであまり便利そうではない。
マクロ化するのも難しそう。
kb84tkhrexceptで例外を捕まえて何かするような機能にしてみる。
def test_letcc_except(self):
run(["define", "raise", None])
run(["define", "riskyfunc", ["func", ["n"], ["do",
["if", ["=", "n", 1], ["raise", 5], None],
["print", 6]]]])
run(["define", "middlefunc", ["func", ["n"], ["do",
["riskyfunc", "n"],
["print", 7]]]])
run(["define", "parentfunc", ["func", ["n"], ["do",
["letcc", "escape", ["do",
["assign", "raise", ["func", ["e"], ["escape", ["do",
["print", "e"]]]]],
["middlefunc", "n"],
["print", 8]]],
["print", 9]]]])
self.assertEqual(printed(["parentfunc", 1]), (None, "5\n9\n"))
self.assertEqual(printed(["parentfunc", 2]), (None, "6\n7\n8\n9\n"))
raiseをやりたいことをやって脱出する関数として定義した。
引数で渡すのをやめて外部の変数に定義している。
なので入れ子にはできない。
kb84tkhr上のparentfuncをこんな感じで書けるようにマクロを作りたい。
exceptはただの飾り。
run(["define", "parentfunc", ["func", ["n"], ["do",
["try", ["do",
["middlefunc", "n"],
["print", 8]],
"except", "e", ["do",
["print", "e"]]],
["print", 9]]]])
そんなに難しくない。
exceptの項はただ無視しているので何が書いてあっても通る。
エラーを報告する機能を付けたら親切かもしれない。
run(["define", "try", ["macro", ["try-expr", "_", "exc-var", "exc-expr"], ["qq",
["letcc", "escape", ["do",
["assign", "raise", ["func", [["!", "exc-var"]],
["escape", ["!", "exc-expr"]]]],
["!", "try-expr"]]]]]])
exceptにパターンマッチがあったらうれしいかもしれない。
やりすぎかもしれない。
kb84tkhrtry-exceptが入れ子になっていても動くようにする。
run(["define", "nested", ["func", ["n"], ["do",
["try", ["do",
["if", ["=", "n", 1], ["raise", 5], None],
["print", 6],
["try", ["do",
["if", ["=", "n", 2], ["raise", 7], None],
["print", 8]],
"except", "e", ["do",
["print", ["q", "exception inner try:"], "e"]]],
["if", ["=", "n", 3], ["raise", 9], None],
["print", 10]],
"except", "e", ["do",
["print", ["q", "exception outer try:"], "e"]]],
["print", 11]]]])
raiseを覚えておいて戻すようにすれば大丈夫だろう。
マルチスレッドとか知らない子。
run(["define", "try", ["macro", ["try-expr", "_", "exc-var", "exc-expr"], ["qq",
["scope", ["do",
["define", "prev-raise", "raise"],
["letcc", "escape", ["do",
["assign", "raise", ["func", [["!", "exc-var"]],
["escape", ["!", "exc-expr"]]]],
["!", "try-expr"]]],
["assign", "raise", "prev-raise"]]]]]])
エラーを報告する機能を付けてみた。
組み込み関数を追加。
def error(args):
assert False, f"{' '.join(map(str, args))}"
builtins = {
...
"error": lambda args: error(args)
}
実はraiseの初期値をerrorを呼ぶ関数にしてやるだけだった。
def test_letcc_try(self):
run(["define", "raise", ["func", ["e"],["error", ["q", "Raised outside of try:"], "e"]]])
self.assertTrue(fails(["raise", 5]))
例外処理はこれくらいで満足。
kb84tkhrジェネレータを作ってみよう。
こんな感じに動くやつ。
def g567():
yield 5
yield 6
yield 7
g = g567()
print(g.__next__())
print(g.__next__())
print(g.__next__())
print(g.__next__()) # => StopIteration
原理的にはこんな感じ。
ジェネレータ内でyieldするときは毎回nextに居場所を覚えておいて、nextを呼ぶたびに次のyieldまで実行しては抜ける。
run(["define", "next", None])
run(["define", "start", ["func", [],
["letcc", "yield", ["do",
["letcc", "cc", ["do", ["assign", "next", "cc"], ["yield", 5]]],
["letcc", "cc", ["do", ["assign", "next", "cc"], ["yield", 6]]],
["letcc", "cc", ["do", ["assign", "next", "cc"], ["yield", 7]]],
["letcc", "cc", ["do", ["assign", "next", "cc"], ["yield", None]]]]]]])
self.assertEqual(run(["start"]), 5)
self.assertEqual(run(["next", None]), 6)
self.assertEqual(run(["next", None]), 7)
self.assertEqual(run(["next", None]), None)
ジェネレータから抜けると最初のletccがNoneを返す。
例外を返すようにはしていない。
この流れで例外がちゃんと動くかかなり自信ない。
そもそも終了時に例外ってのがめんどくさくねと思っていたりする。
ジェネレータにNoneを返させたいときとか困るけど。
kb84tkhrさてこのジェネレータは簡単に破綻する。
["+", ["start"], ["next", None]]を評価するとyieldは["start"]の継続から実行を再開しようとするのだけれどもstartの継続というのは["next", None]を評価してstartの結果と加算するということなのでnextの中でyieldすると無限ループに入ってしまう。
# infinite loop
self.assertEqual(run(["+", ["+", ["start"], ["next", None]], ["next", None]]), 18)
こっちもNotebookLMに音声概要つくらせてみた
区切りがついたら更新しよう
kb84tkhrちょっとずつ書き換えていく。
まずは繰り返し実行してるletccを関数にして、こっちをyieldにする。
継続の方はydという名前にした。
run(["define", "yd", None])
run(["define", "next", None])
run(["define", "yield", ["func", ["x"],
["letcc", "cc", ["do",
["assign", "next", "cc"],
["yd", "x"]]]]])
run(["define", "start", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["yield", 5],
["yield", 6],
["yield", 7],
["yield", None]]]]])
やってることは変わらないので無限ループは直っていない。
kb84tkhr無限ループになるのは、nextしてyieldが呼ばれたらstartから実行が続いてしまうのが問題なので、nextの続きに戻ってくるようにする。
yieldを実行したあとnextしたらyieldの続きに戻ってくるのと同じことをすればいい。
run(["define", "yd", None])
run(["define", "nx", None])
run(["define", "yield", ["func", ["x"],
["letcc", "cc", ["do",
["assign", "nx", "cc"],
["yd", "x"]]]]])
run(["define", "next", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["nx", None]]]]])
run(["define", "start", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["yield", 5],
["yield", 6],
["yield", 7],
["yield", None]]]]])
これで無限ループしなくなった。
self.assertEqual(run(["+", ["+", ["start"], ["next"]], ["next"]]), 18)
startでひとつめの値を返すのが気持ち悪くなってきたのでちょっと直す。
run(["define", "yd", None])
run(["define", "nx", None])
run(["define", "yield", ["func", ["x"],
["letcc", "cc", ["do",
["assign", "nx", "cc"],
["yd", "x"]]]]])
run(["define", "next", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["nx", None]]]]])
run(["define", "start", ["func", ["g"],
["assign", "nx", "g"]]])
run(["define", "g", ["func", ["_"], ["do",
["yield", 5],
["yield", 6],
["yield", 7],
["yield", None]]]])
run(["start", "g"])
self.assertEqual(run(["+", ["+", ["next"], ["next"]], ["next"]]), 18)
ydやnxがグローバル変数なのでこれでは複数のジェネレータを作ることができない。
全部クロージャに入れてしまってnextを返すようにした。
単純極まりない解決方法だけれどもごちゃごちゃ試行錯誤した結果結局これだった、て感じ。
ふたつのジェネレータを作って動かす。
run(["define", "g234", ["func", [], ["do",
["define", "yd", None],
["define", "nx", None],
["define", "yield", ["func", ["x"],
["letcc", "cc", ["do",
["assign", "nx", "cc"],
["yd", "x"]]]]],
["define", "next", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["nx", None]]]]],
["assign", "nx", ["func", ["_"], ["do",
["yield", 2],
["yield", 3],
["yield", 4],
["yield", None]]]],
"next"]]])
run(["define", "g567", ["func", [], ["do",
["define", "yd", None],
["define", "nx", None],
["define", "yield", ["func", ["x"],
["letcc", "cc", ["do",
["assign", "nx", "cc"],
["yd", "x"]]]]],
["define", "next", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["nx", None]]]]],
["assign", "nx", ["func", ["_"], ["do",
["yield", 5],
["yield", 6],
["yield", 7],
["yield", None]]]],
"next"]]])
run(["define", "n234", ["g234"]])
run(["define", "n567", ["g567"]])
self.assertEqual(run(["+", ["+", ["n234"], ["n234"]], ["n234"]]), 9)
self.assertEqual(run(["+", ["+", ["n567"], ["n567"]], ["n567"]]), 18)
ふたつ作っても動いた。
kb84tkhrもう少し複雑になっても動くかな？
run(["define", "gsum", ["func", ["gen"], ["do",
["define", "_gsum", ["func", ["next"],
["aif", ["next"], ["+", "it", ["_gsum", "next"]], 0]]],
["_gsum", ["gen"]]]]])
self.assertEqual(run(["gsum", "g234"]), 9)
self.assertEqual(run(["gsum", "g567"]), 18)
動いた。
kb84tkhr複数のジェネレータに対応した暁にはこんな呼び出しになるものと思ってたんだけど
run(["define", "gen", ["start", "g234"]])
self.assertEqual(run(["next", "gen"]), 2)
self.assertEqual(run(["next", "gen"]), 3)
self.assertEqual(run(["next", "gen"]), 4)
クロージャが全部覚えててくれるのでstartやnextは不要だった。
run(["define", "gen", ["g234"]])
self.assertEqual(run(["gen"]), 2)
self.assertEqual(run(["gen"]), 3)
self.assertEqual(run(["gen"]), 4)
戻ってきたものをジェネレータと思うか次の値を求める関数だと思うかで名づけが変わってくるなあ。
なおこうすれば当初想定の呼び出し方法でも動くよ！（意味なし
run(["define", "start", ["func", ["gfunc"], ["gfunc"]]])
run(["define", "next", ["func", ["g"], ["g"]]])
ジェネレータ関数に引数を渡すことを考えると、gsumに渡すのはジェネレータ関数じゃなくてできあがったジェネレータのほうがいいね
run(["define", "g3", ["func", ["n"], ["do",
["define", "yd", None],
["define", "nx", None],
["define", "yield", ["func", ["x"],
["letcc", "cc", ["do",
["assign", "nx", "cc"],
["yd", "x"]]]]],
["define", "next", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["nx", None]]]]],
["assign", "nx", ["func", ["_"], ["do",
["yield", "n"],
["assign", "n", ["+", "n", 1]],
["yield", "n"],
["assign", "n", ["+", "n", 1]],
["yield", "n"],
["yield", None]]]],
"next"]]])
run(["define", "n234", ["g3", 2]])
run(["define", "n567", ["g3", 5]])
self.assertEqual(run(["+", ["+", ["n234"], ["n234"]], ["n234"]]), 9)
self.assertEqual(run(["+", ["+", ["n567"], ["n567"]], ["n567"]]), 18)
run(["define", "gsum", ["func", ["gen"],
["aif", ["gen"], ["+", "it", ["gsum", "gen"]], 0]]])
self.assertEqual(run(["gsum", ["g3", 2]]), 9)
self.assertEqual(run(["gsum", ["g3", 5]]), 18)
当然マクロ化する。
これはstdlibに入れた。
run(["define", "gfunc", ["macro", ["params", "body"], ["qq",
["func", ["!", "params"], ["do",
["define", "yd", None],
["define", "nx", None],
["define", "yield", ["func", ["x"],
["letcc", "cc", ["do",
["assign", "nx", "cc"],
["yd", "x"]]]]],
["define", "next", ["func", [],
["letcc", "cc", ["do",
["assign", "yd", "cc"],
["nx", None]]]]],
["assign", "nx", ["func", ["_"], ["do",
["!", "body"],
["yield", None]]]],
"next"]]]]])
run(["define", "g3", ["gfunc", ["n"], ["do",
["yield", "n"],
["assign", "n", ["+", "n", 1]],
["yield", "n"],
["assign", "n", ["+", "n", 1]],
["yield", "n"]]]])
run(["define", "gsum", ["func", ["gen"],
["aif", ["gen"], ["+", "it", ["gsum", "gen"]], 0]]])
self.assertEqual(run(["gsum", ["g3", 2]]), 9)
self.assertEqual(run(["gsum", ["g3", 5]]), 18)
yield側を複雑にしても大丈夫だろうか。
木をwalkしてみる。
run(["define", "walk", ["gfunc", ["tree"], ["do",
["define", "_walk", ["func",["t"], ["do",
["if", ["is_arr", ["first", "t"]],
["_walk", ["first", "t"]],
["yield", ["first", "t"]]],
["if", ["is_arr", ["last", "t"]],
["_walk", ["last", "t"]],
["yield", ["last", "t"]]]]]],
["_walk", "tree"]]]])
run(["define", "gen", ["walk", ["q", [[[5, 6], 7], [8, [9, 10]]]]]])
self.assertEqual(printed(["awhile", ["gen"], ["print", "it"]]),
(None, "5\n6\n7\n8\n9\n10\n"))
動いた。
よく動くねえ（おまえがいうな
継続とマクロがどうなってるのかもう想像もできません
なおこっそりawhileを追加している。
whileにitを付け足してもいいんだけど、ifにitを付け足すことはできないので統一感的にawhileという名前にした。
（aifをifとして定義してしまうともともとのifの方で処理されてしまってマクロが動かない）
kb84tkhr配列をジェネレータにするagenを作ったら・・・
run(["define", "agen", ["gfunc", ["a"], ["for", "e", "a", ["yield", "e"]]]])
ジェネレータ用のforを作る。
run(["define", "gfor", ["macro", ["e", "gen", "body"], ["qq",
["scope", ["do",
["define", "__stdlib_gfor_gen", ["!", "gen"]],
["define", ["!", "e"], None],
["while", ["!=", ["assign", ["!", "e"], ["__stdlib_gfor_gen"]], None],
["!", "body"]]]]]]])
self.assertEqual(printed(["gfor", "n", ["agen", ["q", [2, 3, 4]]],
["print", "n"]]),
(None, "2\n3\n4\n"))
引数に入ってくるgenはまだ評価されてないままなので一度評価してやらないとジェネレータにならない。
ちょっとつまづいた。
なお配列にNoneが入っているとそこで終わってしまいますすみません
kb84tkhrforとかwhileとか出てきたのでbreakとかcontinueも気になるけれども、ジェネレータからの流れで簡易な並行処理をやっておきたい。ジェネレータでもふたつの処理が並行してちょっとずつ動いているわけで、しくみの半分はできているようなもの。あとは複数のタスクを動かしてやるしくみがあればいい。
run(["define", "tasks", ["arr"]])
run(["define", "add-task", ["func", ["t"],
["assign", "tasks", ["append", "tasks", "t"]]]])
run(["define", "start", ["func", [],
["while", ["!=", "tasks", ["arr"]], ["do",
["define", "next-task", ["first", "tasks"]],
["assign", "tasks", ["rest", "tasks"]],
["when", ["next-task"], ["add-task", "next-task"]]]]]])
run(["define", "three-times", ["gfunc", ["n"], ["do",
["print", "n"],
["yield", True],
["print", "n"],
["yield", True],
["print", "n"],
]]])
run(["add-task", ["three-times", 5]])
run(["add-task", ["three-times", 6]])
run(["add-task", ["three-times", 7]])
self.assertEqual(printed(["start"]), (None, "5\n6\n7\n5\n6\n7\n5\n6\n7\n"))
yieldで明示的に他のタスクが動くタイミングを作ってやるので協調的な並行処理ってやつになる。
gfuncをもうちょっといじって["yield"]で済むようにしてもいいけどまあいいや。
kb84tkhrというわけでwhileにbreakとcontinueを実装する。
run(["define", "while", ["macro", ["cnd", "body"], ["qq",
["scope", ["do",
["define", "break", None],
["define", "continue", ["func", [],
["when", ["!", "cnd"], ["do", ["!", "body"], ["continue"]]]]],
["letcc", "cc", ["do", ["assign", "break", "cc"], ["continue"]]]]]]]])
run(["do",
["define", "a", 0],
["define", "b", ["arr"]],
["while", ["<", "a", 10], ["do",
["when", ["=", "a", 5], ["break", None]],
["assign", "a", ["+", "a", 1]],
["when", ["=", "a", 3], ["continue"]],
["assign", "b", ["+", "b", ["arr", "a"]]],
]]])
self.assertEqual(run("a"), 5)
self.assertEqual(run("b"), [1, 2, 4, 5])
ちょっと想定外だったんだけれども実はcontinueの実現にはletccはいらなかった。
awhileも同様。
whileとawhileでほとんど同じコード書くのはもったいないんだけれどもいいアイデアが浮かばず。
whileを使ってawhileを書く、ってことができればいいんだけどそうもいきそうにない。
run(["define", "awhile", ["macro", ["cnd", "body"], ["qq",
["scope", ["do",
["define", "break", None],
["define", "continue", ["func", [], ["do",
["define", "it", ["!", "cnd"]],
["when", "it", ["do", ["!", "body"], ["continue"]]]]]],
["letcc", "cc", ["do", ["assign", "break", "cc"], ["continue"]]]]]]]])
forもやる。
今のforは中でwhileを使っていて、breakはそのままでも動くんだけれどもcontinueはそのまま次のループに入ってしまうためインデックスを増やすところまでスキップされてしまって無限ループになる。
run(["define", "for", ["macro", ["e", "l", "body"], ["qq",
["scope", ["do",
["define", "__stdlib_for_index", 0],
["define", ["!", "e"], None],
["while", ["<", "__stdlib_for_index", ["len", ["!", "l"]]], ["do",
["assign", ["!", "e"], ["getat", ["!", "l"], "__stdlib_for_index"]],
["!", "body"],
["assign", "__stdlib_for_index", ["inc", "__stdlib_for_index"]]]]]]]]])
whileを使わないようにするしかないかな？
run(["define", "for", ["macro", ["e", "l", "body"], ["qq",
["scope", ["do",
["define", "__stdlib_for_index", 0],
["define", ["!", "e"], None],
["define", "break", None],
["define", "continue", ["func", [], ["do",
["assign", "__stdlib_for_index", ["inc", "__stdlib_for_index"]],
["go"]]]],
["define", "go", ["func", [],
["when", ["<", "__stdlib_for_index", ["len", ["!", "l"]]],
["do",
["assign", ["!", "e"], ["getat", ["!", "l"], "__stdlib_for_index"]],
["!", "body"],
["continue"]]]]],
["letcc", "cc", ["do", ["assign", "break", "cc"], ["go"]]]]]]]])
self.assertEqual(run(["do",
["define", "sum", 0],
["for", "i", ["arr", 5, 6, 7, 8, 9], ["do",
["when", ["=", "i", 7], ["continue"]],
["when", ["=", "i", 9], ["break", None]],
["assign", "sum", ["+", "sum", "i"]]]],
"sum"]), 19)
このへん書いてて気づいたんだけれどもaifとかawhileをマクロの中で使うのはあんまりよくなさそう。
いつのまにかitが生えてたり書き換えられてたりするわけだから。
明にitを使うようなマクロならいいけれどもor使っただけのつもりなのにitが変わってたらびっくりするな。
ちょっと手間をかけて["while", ["define", "it", ...], ...]みたいに書くくらいがいい加減？
そうすると二重定義を防ぐ用に毎回のループでスコープ切らないと・・・って今もうそうなってるか。
kb84tkhrgforは何も変更しなくてもbreak・continueできる。
self.assertEqual(printed(["gfor", "n", ["agen", ["q", [2, 3, 4, 5, 6]]],
["do",
["when", ["=", "n", 5], ["break", None]],
["when", ["=", "n", 3], ["continue"]],
["print", "n"]]]),
(None, "2\n4\n"))
これはwhileのbreak・continueがそのまま使えてる例。
forもこうなればいいのだけれども。
run(["define", "gfor", ["macro", ["e", "gen", "body"], ["qq",
["scope", ["do",
["define", "__stdlib_gfor_gen", ["!", "gen"]],
["define", ["!", "e"], None],
["while", ["!=", ["assign", ["!", "e"], ["__stdlib_gfor_gen"]], None],
["!", "body"]]]]]]])
bodyを実行した後なにもしないで次のループに進んでいいのがforとの違い。
forはカウンタを更新してやらないといけない。
forは抹消してgforをforに昇格するのがいいのかもしれない。
kb84tkhrやっとcommitした。
今までずっとletccのテストのつもりだった。
これくらい動いたらまあまあ大丈夫ぽいと思っていいのでは。
ソース：https://github.com/koba925/toig/tree/letcc
差分：https://github.com/koba925/toig/compare/cps...letcc
kb84tkhrこれをなんとかする。
本来CPSっていうのはコールスタックが深くならなくて済むはずの考え方なのでrecursionlimitを上げないでも動くようにしたい。
import sys
sys.setrecursionlimit(270000)
練習モードに戻って。
これはn=500くらいで"RecursionError: maximum recursion depth exceeded"になる。
def factorial_cps(n, cont):
if n == 1:
cont(1)
else:
factorial_cps(n - 1, lambda r: cont(n * r))
こんな感じで再帰呼び出しが深くなっていくので。
factorial(4, print)
= factorial(3, λ r1: print(4 * r1))
= factorial(2, λ r2: (λ r1: print(4 * r1))(3 * r2))
= factorial(1, λ r3: (λ r2: (λ r1: print(4 * r1))(3 * r2))(2 * r3))
= (λ r3: (λ r2: (λ r1: print(4 * r1))(3 * r2))(2 * r3))(1)
= (λ r2: (λ r1: print(4 * r1))(3 * r2))(2 * 1)
= (λ r1: print(4 * r1))(3 * (2 * 1))
= print(4 * (3 * (2 * 1)))
トランポリンという技を使うと再帰を深くせずに済む。
kb84tkhrトランポリンで書き直すとこうなる。
継続を引数にして続きに進む代わりにlambdaを返し、ループに戻ってからlambdaを評価するようにしている。
継続もlambdaを返している（lambda r: lambda: の部分）。
def factorial_cps_trampoline(n, cont):
if n == 1:
return lambda: cont(1)
else:
return lambda: factorial_cps_trampoline(n - 1, lambda r: lambda: cont(n * r))
def trampoline(computation):
while callable(computation):
computation = computation()
もとの書き方ではlambda r: cont(n * r)の入れ子が深くなってRecursionErrorになっていた。
こんどの書き方ではlambda r: lambda: cont(n * r)という形になっているので、計算しないでいったんlambda:のまま返しているのでコールスタックが深くならない。
これも手動で評価してみる。
factorial(4, print)
= λ: factorial(3, λ r1: λ: print(4 * r1))
これがcomputationとなってtrampolineに渡される。
computationを評価すると再帰が深くならずにすぐにlambdaが返される。
継続は長くなっているけれども再帰が深くなっているわけではない。
computation()
= (λ: factorial(3, λ r1: λ: print(4 * r1)))()
= factorial(3, λ r1: λ: print(4 * r1))
= λ: factorial(2, λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))
これがまたcomputationとなって評価を繰り返す。
computation()
= (λ: factorial(2, λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2)))()
= factorial(2, λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))
= λ: factorial(1, λ r3: λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * r3)) # → computation
computation()
= (λ: factorial(1, λ r3: λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * r3)))()
= factorial(1, λ r3: λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * r3))
= λ: (λ r3: λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * r3))(1) # → computation
nが1になって基底のcont(1)が呼ばれた。
ここからは継続が評価されていく。
毎回呼んではすぐにlambdaが返されるの繰り返し。
computation()
= (λ: (λ r3: λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * r3))(1))()
= (λ r3: λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * r3))(1)
= λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * 1) # → computation
computation()
= (λ: (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * 1))()
= (λ r2: λ: (λ r1: λ: print(4 * r1))(3 * r2))(2 * 1)
= λ: (λ r1: λ: print(4 * r1))(3 * (2 * 1)) # → computation
computation()
= (λ: (λ r1: λ: print(4 * r1))(3 * (2 * 1)))()
= (λ r1: λ: print(4 * r1))(3 * (2 * 1))
= λ: print(4 * (3 * (2 * 1))) # → computation
computation()
= (λ: print(4 * (3 * (2 * 1))))()
= print(4 * (3 * (2 * 1))) # → computation
というわけでRecursionErrorを防ぐことができる。
まわりくどいけど。
>>> trampoline(factorial_cps_trampoline(1500, print))
48119977967797748601669900935813797818348080406726138081308559411630575189001095591292230585206733851868464009619343585194052091124618166270271481881393331431627962810299844149333789044689395510487167879769325303699470467829234399263326545652860748605075746366928323606645492277541120083438086727369377887676000211405318480244354207419604864176969950581435222198851194568984095705945549589054568321792338919149442985919957734792959402499096845643020401869381175603964424333222114125974374817804242633309769804293952870034619354125014210045647664063240162007560108665290568646128342557147350985358724154623253371867470765120422073867963935775258692109753041762094343569050497470353531764481503174750911858230906998361066084787758316110585736013365377431860738572261325738233656835271947352695180865573043834027955539012765489372645042504406597752357481931532872356635411224578334040522294746402829585458478708778346379431862368824819009177091444034885941394319343910223168655869761799669075059527608502465593181398566214786801211651657222004123456498258513120359126022843038535083709796101565934859483203933443308601475813108363074118562404412420191947127585482919172173045961122122701434297870691932154082986945954748251105782181586397275820342101470457300633590139512919549474113721711616912519714191760699935509810254849967087635936181176363954224186031346682928878492872249485456690138831610135377916327940503701400290125509132140782614640495733518048670983360134097860364762638658894873174499870133559364805443430831459505987809215393353387232078177562975021460595422358573128085417162336030235138652735438053034531962620811566019896879275257163988352090874930346115518331202927263708446729394381879888839549731876978682249320628599631628662375508826209854754631984276392670919216923002770077734756077549035942976209159416211581439461484509549370357486770276807687544580164314647595031368948490282897173328013518435758700056425922638411889496527975846052717958044813737086806600171993703579485864029383208714528950303253881360812631162134750100307772634337467012820470715650810714689905121432259528505483053930402217400686061612471659630192434864094539828085677465383026128353771071152304197549798870706139893609140045659756285435787771636258253666592102151236142132724425850991205720020493660580896600891888594659612927724357866265934517615841298789154462249169688860092640284756382431746120357767933119589280468687348061788072986362788582227019465263474828590646048451070702923434422714349595857654843699542321849363652767771978314681013589442955219879702008068934096624650625769705233333462826013860098698155180331145365652453482955497979915586438474687345677874451117702250441711504844638414485210092261397271970571029038581873069951161330495772310508760528249706514238384269808639507080418298318311361373628512041716415196868334254119137139589149597210032153545941114666530498906529240798164804007394775927836045668573993316428972539932745757171947402454257142633700815922407278403640595355142075599446056337986717212316223257763412164180899532722039383244462511410346646148863397237096276822656157561194665545757017429842404840309758925618650507921043007241637877939825811059339138925526124514467627126548126795078784022672860886251974581362141782786407402896309678008909663263987018538107050886193489012497405005820727271232733728141775132722013860591169620692789290456794698409808557447756701311883266010859016027592252397754508251628808293537776536569608111330584797160694847898923196743970244451842702266403326317319092117151143971679500042590269255093130215984418097418435474300467281949798227102529873732749027992079700287275900856241172902880909546551703263202853584498085358955307673717177961902081098618729046348849060249600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
https://github.com/koba925/toig/blob/minimum_naive_cps_letcc/toig.py をtrampolineに書き換える。
今は["fib", 10]を計算するためにsetrecursionlimitを14000にしている。
今まで継続を渡して次の評価を実装してたところは全部return lambda: をつけてトランポリンに返す。
渡す継続もlambdaを返すように lambda ...: lambda: ...とlambdaを入れる。
defineのところははどうすればいい？
case ["define", name, expr]:
eval(expr, env, lambda val: define(env, name, val))
cont(None)
evalはlambdaを返してくるだけだからトランポリンに戻さないと何も起こらないし、かといってevalの式にreturn lambda: つけちゃうとreturn lambda: cont(None)が呼ばれない。
そもそもの書き方がよくなかったり？
こうかな？
case ["define", name, expr]:
return lambda: eval(expr, env, lambda val: lambda: [
define(env, name, val),
cont(None)][1])
トランポリン前のソースに戻ってこのやり方にしてみる。
case ["define", name, expr]:
eval(expr, env, lambda val: [define(env, name, val), cont(None)][1])
動いたのでこのやり方で。
runをトランポリンに書き換える。
最後は値を返してくるようになるのでsaveを作らなくてよくなっている。
ちょっと皮肉。
def run(src):
computation = lambda: eval(src, top_env, lambda result: result)
while callable(computation):
try:
computation = computation()
except Skip as s:
computation = s.skip
return computation
setrecursionlimitなしでも動いた。
["fib", 25]でも大丈夫。時間はかかる。
ソース：https://github.com/koba925/toig/tree/minimum_trampoline
差分：https://github.com/koba925/toig/compare/minimum_naive_cps_letcc...minimum_trampoline
kb84tkhrではtoig本体で。
現在のlimitは270000。
import sys
sys.setrecursionlimit(270000)
継続を呼んでいるところをどこどこreturn lambda:に変えていく。
runは上で書いたものと同じで大丈夫。
今回、factorialのように継続がいったんlambda:を返すようにはしなかった。
return lambda: factorial_cps_trampoline(n - 1, lambda r: lambda: cont(n * r))
というのは評価器の中ではeval内でたびたびcont()という形で呼び出しの連鎖が止まるので、実験用のfactorialのようにどんどん深く呼び出されるということがなさそうだから。
以下のfactorialで["factorial", 1500]も計算できている。
run(["define", "factorial", ["func", ["n"],
["if", ["=", "n", 1],
1,
["*", "n", ["factorial", ["-", "n", 1]]]]]])
ソース：https://github.com/koba925/toig/tree/trampoline
差分：https://github.com/koba925/toig/compare/trampoline_sample...trampoline
kb84tkhrマクロ・継続のネタはとりあえずこれくらいかなあ。
次は字句解析と構文解析をつけよう。
だいぶ長くなったので別のスクラップで。
kb84tkhr継続、今はlambdaで渡しているけど`["func", ["result"], ...]という形で渡せないだろうかと考え中。
できないことはないと思うんだけれどもいざやってみるとこういうところすらどう書いていいものか、ってなる。
def eval(expr, env, cont):
match expr:
case None | bool(_) | int(_): cont(expr)
即cont(expr)を評価するわけだからこんな感じなの？
継続には何を渡せばいいの？
def eval(expr, env, cont):
match expr:
case None | bool(_) | int(_): eval(["cont", "expr"], env, ???)
exprはもう値になっているんだからapply呼べばいいのか？
いや、contも評価しないといけないしやっぱり継続に何を渡せばいいのかわからない。
def eval(expr, env, cont):
match expr:
case None | bool(_) | int(_): apply(cont, expr, ???)
なんか無限ループになりそうな気もするし。
ということで悩み中。
kb84tkhr生成AIの意見も聴きながら地道に修正していったら原型をとどめないレベルになってやっと動いた。
evalの中は大きく二つに分かれている。
- 式を
evalして値にしていく部分（後半） - 値ができたら次の計算に進む部分（前半）
あんまりうまく言い表せてない気がするが。
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
def eval(expr, env, cont):
if is_value(expr):
if cont == ["$halt"]: return expr
match cont:
case ["$if", thn_expr, els_expr, next_cont]:
if expr:
return eval(thn_expr, env, next_cont)
else:
return eval(els_expr, env, next_cont)
case ["$define", name, next_cont]:
define(env, name, expr)
return eval(expr, env, next_cont)
case ["$call", args_expr, call_env, next_cont]:
return eval(
args_expr[0],
call_env,
["$args", expr, args_expr[1:], [], call_env, next_cont])
case ["$args", func_val, args_expr, args_val, call_env, next_cont]:
if args_expr == []:
return eval(
["$apply", func_val, args_val + [expr]],
call_env,
next_cont)
else:
return eval(
args_expr[0],
call_env,
["$args", func_val, args_expr[1:], args_val + [expr], call_env, next_cont])
case _:
assert False, f"Invalid continuation: {cont}"
else:
match expr:
case ["func", params, body]:
return eval(["func", params, body, env], env, cont)
case str(name):
return eval(get(env, name), env, cont)
case ["define", name, expr]:
return eval(expr, env, ["$define", name, cont])
case ["if", cnd_expr, thn_expr, els_expr]:
return eval(cnd_expr, env, ["$if", thn_expr, els_expr, cont])
case ["$apply", func_val, args_val]:
match func_val:
case f if callable(f):
return eval(func_val(args_val), env, cont)
case ["func", params, body_expr, closure_env]:
closure_env = new_scope(closure_env)
for param, arg in zip(params, args_val):
define(closure_env, param, arg)
return eval(body_expr, closure_env, cont)
case _:
assert False, f"Invalid function: {expr}"
case [func_expr, *args_expr]:
return eval(func_expr, env, ["$call", args_expr, env, cont])
case _:
assert False, f"Invalid expression: {expr}"
kb84tkhrこういった継続を["func", ["cnd"], ["if", "cnd", ...]]に直すのではなくて
case ["if", cnd_expr, thn_expr, els_expr]:
eval(cnd_expr, env, lambda cnd:
eval(thn_expr, env, cont) if cnd else
eval(els_expr, env, cont))
いったん["$if", thn_expr, els_expr, cont]という継続にして
case ["if", cnd_expr, thn_expr, els_expr]:
return eval(cnd_expr, env, ["$if", thn_expr, els_expr, cont])
cnd_exprが値になったところでその値を使って次の計算に進む、とか
case ["$if", thn_expr, els_expr, next_cont]:
if expr:
return eval(thn_expr, env, next_cont)
else:
return eval(els_expr, env, next_cont)
こういった再帰呼び出しを
def eval_args(args_expr, env, cont):
def _eval_args(exprs, acc):
if exprs == []:
cont(acc)
else:
eval(exprs[0], env, lambda val:
_eval_args(exprs[1:], acc + [val]))
_eval_args(args_expr, [])
こんな風に翻訳したりとかしている。
case ["$args", func_val, args_expr, args_val, call_env, next_cont]:
if args_expr == []:
return eval(
["$apply", func_val, args_val + [expr]],
call_env,
next_cont)
else:
return eval(
args_expr[0],
call_env,
["$args", func_val, args_expr[1:], args_val + [expr], call_env, next_cont])
まだ完全に吞み込めた感じはしてなくて、["$if", thn_expr, els_expr, cont]のような専用の形で継続を表すのではなくて["func", ["cnd"], ["if", "cnd", ...]]のような形の継続にして継続の評価にもevalを使うってのはほんとにできないのか、["$if", thn_expr, els_expr, cont]である必然性はあるのか、ってあたりは説明できない。
まだ修正漏れとかミスってるところとかあるんじゃないかという気もする。
いじりながらしみこんでくるのを待とう。
kb84tkhr若干無理やりeval()の呼び出しという形を保ってきたけれどもどう見てもステートマシンです本当にありがとうございました。
def eval(expr, env, cont):
def apply_cont():
nonlocal expr, env, cont
match cont:
case ["$if", thn_expr, els_expr, next_cont]:
if expr:
expr, cont = thn_expr, next_cont
else:
expr, cont = els_expr, next_cont
case ["$define", name, next_cont]:
define(env, name, expr)
cont = next_cont
case ["$call", args_expr, call_env, next_cont]:
expr, env, cont = args_expr[0], call_env, [
"$args", expr, args_expr[1:], [], call_env, next_cont
]
case ["$args", func_val, args_expr, args_val, call_env, next_cont]:
args_val += [expr]
if args_expr == []:
expr, env, cont = [
"$apply", func_val, args_val
], call_env, next_cont
else:
expr, env, cont = args_expr[0], call_env, [
"$args", func_val, args_expr[1:], args_val, call_env, next_cont
]
case _:
assert False, f"Invalid continuation: {cont}"
def eval_expr():
nonlocal expr, env, cont
match expr:
case ["func", params, body]:
expr = ["func", params, body, env]
case str(name):
expr = get(env, name)
case ["define", name, expr]:
cont = ["$define", name, cont]
case ["if", cnd_expr, thn_expr, els_expr]:
expr, cont = cnd_expr, ["$if", thn_expr, els_expr, cont]
case ["$apply", func_val, args_val]:
match func_val:
case f if callable(f):
expr = func_val(args_val)
case ["func", params, body_expr, closure_env]:
closure_env = new_scope(closure_env)
for param, arg in zip(params, args_val):
define(closure_env, param, arg)
expr, env = body_expr, closure_env
case _:
assert False, f"Invalid function: {expr}"
case [func_expr, *args_expr]:
expr, cont = func_expr, ["$call", args_expr, env, cont]
case _:
assert False, f"Invalid expression: {expr}"
while True:
if is_value(expr):
if cont == ["$halt"]: return expr
apply_cont()
else:
eval_expr()
ふたかたまり＋ループに分けてみたけどまだちょっとかたまりが大きい気もする。
ここにマクロとかletccとか付け足していくならもう一段分けた方がいいかもしれない。
呼び出しがループになってsetrecursionlimit()が不要になったのはとてもよい。
トランポリンいらず。
というかこれはトランポリンなのかもしれない。
kb84tkhrかたまりの大きさはこれくらいが好み。
apply_cal()→apply_args()のつながりがちょっとだけ見づらくなってるかもしれない。
行数がさらに増えたけど。
def eval(expr, env, cont):
def apply_cont():
nonlocal expr, env, cont
def apply_if(thn_expr, els_expr, next_cont):
nonlocal expr, cont
if expr:
expr, cont = thn_expr, next_cont
else:
expr, cont = els_expr, next_cont
def apply_define(name, next_cont):
nonlocal cont
define(env, name, expr)
cont = next_cont
def apply_call(args_expr, call_env, next_cont):
nonlocal expr, env, cont
expr, env, cont = args_expr[0], call_env, [
"$args", expr, args_expr[1:], [], call_env, next_cont
]
def apply_args(func_val, args_expr, args_val, call_env, next_cont):
nonlocal expr, env, cont
args_val += [expr]
if args_expr == []:
expr, env, cont = [
"$apply", func_val, args_val
], call_env, next_cont
else:
expr, env, cont = args_expr[0], call_env, [
"$args", func_val, args_expr[1:], args_val, call_env, next_cont
]
match cont:
case ["$if", thn_expr, els_expr, next_cont]:
apply_if(thn_expr, els_expr, next_cont)
case ["$define", name, next_cont]:
apply_define(name, next_cont)
case ["$call", args_expr, call_env, next_cont]:
apply_call(args_expr, call_env, next_cont)
case ["$args", func_val, args_expr, args_val, call_env, next_cont]:
apply_args(func_val, args_expr, args_val, call_env, next_cont)
case _:
assert False, f"Invalid continuation: {cont}"
def eval_expr():
nonlocal expr, env, cont
def apply(func_val, args_val):
nonlocal expr, env, cont
match func_val:
case f if callable(f):
expr = func_val(args_val)
case ["func", params, body_expr, closure_env]:
closure_env = new_scope(closure_env)
for param, arg in zip(params, args_val):
define(closure_env, param, arg)
expr, env = body_expr, closure_env
case _:
assert False, f"Invalid function: {expr}"
match expr:
case ["func", params, body]:
expr = ["func", params, body, env]
case str(name):
expr = get(env, name)
case ["define", name, expr]:
cont = ["$define", name, cont]
case ["if", cnd_expr, thn_expr, els_expr]:
expr, cont = cnd_expr, ["$if", thn_expr, els_expr, cont]
case ["$apply", func_val, args_val]:
apply(func_val, args_val)
case [func_expr, *args_expr]:
expr, cont = func_expr, ["$call", args_expr, env, cont]
case _:
assert False, f"Invalid expression: {expr}"
while True:
if is_value(expr):
if cont == ["$halt"]: return expr
apply_cont()
else:
eval_expr()
nonlocal書きたくねえ
kb84tkhrnonlocal書きたくねえ
というわけでクラスに書き換えた。
そこだけってのもなんなので全体的に。
selfもあんまり書きたくはないのだけれどもステートマシンならこっちの方が自然なんだろう。
nonlocal憎し
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()
kb84tkhrこれをベースに、同じようなルートでマクロや継続を実装してみよう。
それなりに長くなりそうなのでスクラップを分けて。