トイ言語実験日記２（構文解析とカスタム文法）
kb84tkhr
の続き。
toigに字句解析と構文解析をつけよう。
minilangとはちょっと違う感じにしたいけどどうするかな。
- マクロと継続、それらで実現した一部の機能を仕様に取り込む
- すべて式
- endで終わるスタイル
これくらい考えてみよう。
kb84tkhrスキャナやパーザの書き方も、少しはこれまでと変えてみたい。
これまでほとんどクラスを作らずに来てるので、クラスなしで一度書いてみようか。
大きなクロージャを作るか、引数で持ちまわるか。
kb84tkhr今まで書いたテストは残しておいてスキャナ・パーザを書いたところからテストを追加していこう。
テキストのソースを読んで実行する関数をrun()にしたい気がするから今までのrunをevalに変えてevalはeval_exprにする。
とりあえずこんな感じでスタート。
あちこちにnonlocalを書かないといけないようでは面倒だなあ。
耐えられなくなったら引数で持ちまわるように書き換えよう。
def scanner(src):
def advance():
nonlocal pos; pos += 1
def current_char():
return src[pos] if pos < len(src) else "$EOF"
def append_char():
nonlocal token
token += current_char()
advance()
def next_token():
while current_char().isspace(): advance()
nonlocal token
token = ""
match current_char():
case "$EOF": return "$EOF"
case c if c.isnumeric():
while current_char().isnumeric(): append_char()
return int(token)
pos = 0; token = ""
return next_token
def parse(src):
next_token = scanner(src)
return next_token()
def eval(expr):
computation = lambda: eval_expr(expr, top_env, lambda result: result)
while callable(computation):
try:
computation = computation()
except Skip as s:
computation = s.skip
return computation
def run(src):
return eval(parse(src))
if __name__ == "__main__":
init_env()
stdlib()
print(run("5"))
これを通す。
def test_primitives(self):
self.assertEqual(run("None"), None)
self.assertEqual(run("5"), 5)
self.assertEqual(run("True"), True)
self.assertEqual(run("False"), False)
こんな感じ。
def is_name_first(c): return c.isalpha() or c == "_"
def is_name_rest(c): return c.isalnum() or c == "_"
def name():
match token:
case "None": return None
case "True": return True
case "False": return False
case _ : return token
def next_token():
while current_char().isspace(): advance()
nonlocal token
token = ""
match current_char():
case "$EOF": return "$EOF"
case c if is_name_first(c):
append_char()
while is_name_rest(current_char()): append_char()
return name()
case c if c.isnumeric():
while current_char().isnumeric(): append_char()
return int(token)
kb84tkhr変数の定義・参照を作る。
defineじゃなくて:=で変数を定義することにする。全部式にする作戦なので。
等号は=でもいいんだけど==にするかなあ？Pythonと行き来してると間違うので。
じゃあ代入は=か。::=とか？
字句解析上はとりあえず記号が並んだものはすべてトークンということにしてしまおう。
知らないトークンはparserで気づけるはずだし。
破綻したらていねいに書く。破綻しそうな気もする。
def word(is_rest):
append_char()
while is_rest(current_char()): append_char()
def name():
word(is_name_rest)
match token:
case "None": return None
case "True": return True
case "False": return False
case _ : return token
def next_token():
while current_char().isspace(): advance()
nonlocal token
token = ""
match current_char():
case "$EOF": return "$EOF"
case c if is_name_first(c):
return name()
case c if c.isnumeric():
word(str.isnumeric)
return int(token)
case c if is_punctuation(c):
word(is_punctuation)
return token
:=は右結合。
def parse(src):
def parse_expr():
return parse_define()
def parse_define():
left = parse_primary()
if next_token() == ":=":
return ["define", left, parse_expr()]
return left
def parse_primary():
return next_token()
next_token = scanner(src)
return parse_expr()
現状できるテストはこれくらい。
実は今まで["define", 6, 5]のエラーをチェックしていなかったのでチェックするようにした。
def test_define(self):
self.assertEqual(run("x := 5"), 5)
self.assertEqual(run("x"), 5)
self.assertEqual(run("y := z := 6"), 6)
self.assertEqual(run("y"), 6)
self.assertEqual(run("z"), 6)
self.assertTrue(fails("6 := 5"), 5)
kb84tkhr代入を=にするんだったら組み込み関数の名前を変えないと。
ほかの組み込み関数もまとめて名前を変えてしまおう。
演算子と関数を共存させたいので。
builtins = {
"add": lambda args: n_ary(2, op.add, args),
"sub": lambda args: n_ary(2, op.sub, args),
"mul": lambda args: n_ary(2, op.mul, args),
"div": lambda args: n_ary(2, op.truediv, args),
"equal": lambda args: n_ary(2, op.eq, args),
"not_equal": lambda args: n_ary(2, op.ne, args),
"less": lambda args: n_ary(2, op.lt, args),
"greater": lambda args: n_ary(2, op.gt, args),
"less_equal": lambda args: n_ary(2, op.le, args),
"greater_equal": lambda args: n_ary(2, op.ge, args),
"not": lambda args: n_ary(1, op.not_, args),
...
}
これを通す。
def test_assign(self):
self.assertEqual(run("x := y := 5"), 5)
self.assertEqual(run("x = 6"), 6)
self.assertEqual(run("x"), 6)
self.assertEqual(run("x = y = 7"), 7)
self.assertEqual(run("x"), 7)
self.assertEqual(run("y"), 7)
self.assertTrue(fails("z = 5"))
self.assertTrue(fails("6 = 5"))
パーザをごそごそ書き直す。
やっていることはあまり変わっていないくて3分の2くらいはリファクタしてる感じ。
def parse(src):
def advance():
nonlocal current_token
prev_token = current_token
current_token = next_token()
return prev_token
def parse_binary_right(ops, sub_elem):
left = sub_elem()
if (op := current_token) in ops:
advance()
return [ops[op], left, parse_binary_right(ops, sub_elem)]
return left
def parse_expr():
return parse_define_assign()
def parse_define_assign():
return parse_binary_right({
":=": "define",
"=": "assign"
}, parse_primary)
def parse_primary():
return advance()
next_token = scanner(src)
current_token = next_token()
return parse_expr()
kb84tkhr破綻しそうな気もする。
間違いなく破綻するよね。((とすら書けないし。気づけよ。
というわけでやっぱり個別に書かざるを得ない？
今はこれだけで済む。増えてきたらどう書くのがかっこいいのか。
case ":":
append_char()
if current_char() == "=": append_char()
case "=":
append_char()
":"だけのトークンはまだないけど・・・いいか。
kb84tkhr次は;で式を並べよう。
式の最後にセミコロン、ではなく、左辺を評価して右辺を評価して右辺を返す左結合の演算子と考えることにする。優先度は最低・・・かな？
なんでも式、ってしたんだからこういう考え方も悪くはなかろう。
最後がセミコロンで終わったらエラーになる。
def test_sequence(self):
self.assertEqual(run("x := 5; y := 6"), 6)
self.assertEqual(run("x"), 5)
self.assertEqual(run("y"), 6)
self.assertEqual(run("x = 6; y = 7; z := 8"), 8)
self.assertEqual(run("x"), 6)
self.assertEqual(run("y"), 7)
self.assertEqual(run("z"), 8)
self.assertTrue(fails(";"))
parseしたらdoにする。
二項演算子として書いてもいいけどdoは３つ以上の式も書けるからそれを生かす書き方で。
そうすると多項演算子ということになるのかな？
case "=" | ";":
append_char()
...
def parse_sequence():
exprs = [parse_define_assign()]
while current_token == ";":
advance()
exprs.append(parse_define_assign())
return exprs[0] if len(exprs) == 1 else ["do"] + exprs
...
next_token = scanner(src)
current_token = next_token()
return parse_sequence()
kb84tkhr四則演算・カッコ・比較演算を実装する。
ここはできるとわかってるところなのでさらっと。
これだけ通した。
def test_builtin_comparison(self):
self.assertTrue(run("5 + 8 == 6 + 7"))
self.assertFalse(run("5 + 6 == 6 + 7"))
self.assertFalse(run("5 + 8 != 6 + 7"))
self.assertTrue(run("5 + 6 != 6 + 7"))
self.assertTrue(run("5 + 7 < 6 + 7"))
self.assertFalse(run("5 + 8 < 6 + 7"))
self.assertFalse(run("5 + 8 < 5 + 7"))
self.assertFalse(run("5 + 7 > 6 + 7"))
self.assertFalse(run("5 + 8 > 6 + 7"))
self.assertTrue(run("5 + 8 > 5 + 7"))
self.assertTrue(run("5 + 7 <= 6 + 7"))
self.assertTrue(run("5 + 8 <= 6 + 7"))
self.assertFalse(run("5 + 8 <= 5 + 7"))
self.assertFalse(run("5 + 7 >= 6 + 7"))
self.assertTrue(run("5 + 8 >= 6 + 7"))
self.assertTrue(run("5 + 8 >= 5 + 7"))
self.assertEqual(run("x := 5 + 8 == 6 + 7"), True)
self.assertEqual(run("x"), True)
def test_add_sub(self):
self.assertEqual(run("5 + 6 + 7"), 18)
self.assertEqual(run("18 - 6 - 7"), 5)
self.assertEqual(run("x := 5 + 6"), 11)
self.assertEqual(run("x"), 11)
def test_mul_div_mod(self):
self.assertEqual(run("5 * 6 * 7"), 210)
self.assertEqual(run("210 / 6 / 7"), 5)
self.assertEqual(run("216 / 6 % 7"), 1)
self.assertEqual(run("5 + 6 * 7"), 47)
self.assertEqual(run("5 * 6 + 7"), 37)
def test_neg(self):
self.assertEqual(run("-5"), -5)
self.assertEqual(run("-5 * 6"), -30)
self.assertEqual(run("5 * -6"), -30)
def test_paren(self):
self.assertEqual(run("(5 + 6) * 7"), 77)
self.assertEqual(run("5 * (6 + 7)"), 65)
self.assertEqual(run("(5) + 6"), 11)
self.assertTrue(fails("(5"))
parse_はなんか冗長な気がしてきたので消した。
全部parse()の中にいるわけだし。
むしろ見やすくなった気がする。
全部parse()の中に入れてしまおうという作戦は思いのほかうまくいっている。
nonlocalもほとんどでてこないし。
parse()がやたらと長いってことくらいかな。
eval_も全部eval()の中に入れればいいのか？
kb84tkhrand、or、notをサポートする。
andとorはマクロで定義されたものなので組み込みの関数とは違うけれどもたぶん気にすることはないだろう。
優先度は低めに。
コード上は特に意識することなく。
def define_assign():
return binary_right({
":=": "define", "=": "assign"
}, or_)
def or_():
return binary_left({"or": "or"}, and_)
def and_():
return binary_left({"and": "and"}, not_)
def not_():
return unary({"not": "not"}, comparison)
def comparison():
return binary_left({
"==": "equal", "!=": "not_equal",
"<": "less", ">": "greater",
"<=": "less_equal", ">=": "greater_equal"
}, add_sub)
def add_sub():
return binary_left({
"+": "add", "-": "sub"
}, mul_div_mod)
大丈夫だった。
def test_or(self):
self.assertTrue(run("5 == 5 or 5 == 5"))
self.assertTrue(run("5 == 5 or 5 != 5"))
self.assertTrue(run("5 != 5 or 5 == 5"))
self.assertFalse(run("5 != 5 or 5 != 5"))
self.assertEqual(run("5 or x"), 5)
self.assertEqual(run("False or 5"), 5)
self.assertTrue(run("False or False or True"))
self.assertFalse(run("False or False or False"))
self.assertEqual(run("x := True or False"), True)
self.assertEqual(run("x"), True)
def test_and(self):
self.assertTrue(run("5 == 5 and 5 == 5"))
self.assertFalse(run("5 == 5 and 5 != 5"))
self.assertFalse(run("5 != 5 and 5 == 5"))
self.assertFalse(run("5 != 5 and 5 != 5"))
self.assertEqual(run("True and 5"), 5)
self.assertEqual(run("0 and x"), 0)
self.assertTrue(run("True or True and False"))
self.assertFalse(run("(True or True) and False"))
def test_not(self):
self.assertFalse(run("not 5 == 5"))
self.assertTrue(run("not 5 != 5"))
self.assertFalse(run("not True and False"))
self.assertTrue(run("not (True and False)"))
kb84tkhrifを作ろう。式で。
if 条件節1 then 結果節1 elif 条件節2 then 結果節2 ... else 代替節 endの形にする。
endを書かなきゃいけないのは面倒だけどthenがあるのは気分がいい。
elseは書かないといけないのにthenがない、っていうのは気持ち悪い気がしてた。
優先度はどう考えたらいいんだ？
:=や=よりは高くしたい。x := if a then b else c endみたいに書きたいし。
条件節・結果節・代替節を囲んでいるからカッコみたいなものと考えればいいだろうか。
じゃあprimaryに入る？
def primary():
if current_token == "if":
advance(); return if_()
if current_token == "(":
advance(); expr = expression(); consume(")")
return expr
return advance()
def if_():
cnd = expression()
consume("then")
thn = expression()
if current_token == "elif":
advance()
return ["if", cnd, thn, if_()]
if current_token == "else":
advance()
els = expression()
consume("end")
return ["if", cnd, thn, els]
consume("end")
return ["if", cnd, thn, None]
とするとこうなる。
def test_if(self):
self.assertEqual(run("if 5; True then 6; 7 end"), 7)
self.assertEqual(run("if 5; False then 6; 7 end"), None)
self.assertEqual(run("if 5; True then 6; 7 else 8; 9 end"), 7)
self.assertEqual(run("if 5; False then 6; 7 else 8; 9 end"), 9)
self.assertEqual(run("if 5; True then 6; 7 elif 8; True then 9; 10 else 11; 12 end"), 7)
self.assertEqual(run("if 5; False then 6; 7 elif 8; True then 9; 10 else 11; 12 end"), 10)
self.assertEqual(run("if 5; False then 6; 7 elif 8; False then 9; 10 else 11; 12 end"), 12)
self.assertEqual(run("-if 5; True then 6; 7 end"), -7)
self.assertTrue(fails("if True end"))
self.assertTrue(fails("if True then"))
self.assertTrue(fails("if True then 5 else"))
-if ... endは一瞬違和感を感じるけどこれがやりたかったことなはず。
kb84tkhr結果節・代替節は変数定義の微妙な問題を避けるためにスコープを作っている。
evalのifに入れても同じだけれども、evalは単一の機能を持つパーツの集まりとして書く方がいい気がしている。構文解析でパーツを組み合わせてあげればいいのだから。
直接ASTを書くスタイルだと書きやすくしたいというのもあるのだけれども。
kb84tkhrwhileも中身はマクロだけど構文にしてしまおう。
while 条件 do 本体 endでいいかな。
ifより簡単。
def primary():
match current_token:
case "(":
advance(); expr = expression(); consume(")")
return expr
case "if":
advance(); return if_()
case "while":
advance(); return while_()
return advance()
def while_():
cnd = expression()
consume("do")
body = expression()
consume("end")
return ["while", cnd, ["scope", body]]
複数行に分けて書きたくなるコードは初めてかな？
def test_while(self):
self.assertEqual(run("""
i := sum := 0;
while i < 10 do
sum = sum + i;
i = i + 1
end;
sum
"""), 45)
i = i + 1やsumの後ろにセミコロンを書きたくなってしまうが書いてはいけない。
;は演算子で右辺が必要だから。
whileのマクロではbreakを使えるようにしているけれども関数呼び出しの形になるのでまだ使えない。
kb84tkhrwhileも式なのだからなにか値を返すようにしよう。マクロの方の修正。
最後に評価した値を返すようにする。
マクロの方の修正になる。
valに値を覚えておいて条件が偽になったときにvalを返すよう。
eval(["define", "while", ["macro", ["cnd", "body"], ["qq",
["scope", ["do",
["define", "break", None],
["define", "val", None],
["define", "continue", ["func", [],
["if", ["!", "cnd"],
["do", ["assign", "val", ["!", "body"]], ["continue"]],
"val"]]],
["letcc", "cc", ["do", ["assign", "break", "cc"], ["continue"]]]]]]]])
あんまり必然性がないけどさっきのテストはこう書いても通るようになる。
i := sum := 0;
while i < 10 do
sum = sum + i;
i = i + 1;
sum
end
end;からセミコロンを取ったり、i = i + 1にセミコロンをつけたりしなければいけないのは少々面倒。
だからセミコロンを演算子として扱うのは流行らないんだなきっと。
実装的には美しい気がしているんだけど。
実用性は度外視だからこのまま進む。
kb84tkhrこう書くのとはどれくらい違うかな。
全然違うような、意外と変わらないような。
["do",
["define", "i", 0],
["define", "sum", 0],
["while", ["less", "i", 10], ["do",
["assign", "sum", ["add", "sum", "i"]],
["assign", "i", ["add", "i", 1]],
"sum"]]]
そういえばifで代替節がない場合を書いてしまったのでwhenのマクロは不要になってる。
stdlibで他の関数・マクロを書くのに使ってるので消すことはできないけど。
マクロも扱えるようにしてstdlibを書き換えたら消せるだろう。
aifとかawhileもif (it = ...) then ... endみたいな書き方することにして消しちゃうかなあ・・・？
便利な時は便利なんだけど。
むしろifって書いてあったらaifにしちゃうか？
andやorでいつのまにかitが生えてたり外側のitを隠しちゃったりしているのはよくないと思っている。
kb84tkhrwhileのマクロではbreakを使えるようにしているけれども関数呼び出しの形になるのでまだ使えない。
いや、関数呼び出しを実装してなくてもbreakやcontinueのASTを作ってやればいいのか。
その方が文法的にもそれっぽくなるし。
使えないところで使ってしまった時のエラーが若干意味不明になりそうだけれども何を今さらである。
形はbreak 値 endかなあ。endはつけたくないけどつけないと何か破綻しそうな気がする・・・いや、前置の単項演算子と見ればnotと変わらんか？
優先順位は;と=・:=の間かな。
break a = 5などと書くこともあるかもしれないけど a = break 5とは書かないだろうから。
break 5; 6と書いたら5でbreakすることになるけどびっくりしないよな。
どうしても6を返したかったらbreak (5; 6)とすればいい。
そうするとこうか。
def sequence():
exprs = [break_continue()]
while current_token == ";":
advance()
exprs.append(break_continue())
return exprs[0] if len(exprs) == 1 else ["do"] + exprs
def break_continue():
if current_token == "break":
advance()
return ["break", define_assign()]
if current_token == "continue":
advance()
return ["continue"]
return define_assign()
いけた。
def test_break_continue(self):
self.assertEqual(run("""
i := sum := 0;
while True do
if i == 5 then i = i + 1; continue end;
if i >= 10 then break sum end;
sum = sum + i;
i = i + 1
end
"""), 40)
whileで最後に評価した式の値を返すよりもbreakの値を返す方が使い道がありそう。
run("break 5")などとするとそんな変数はないよと言われる。
AssertionError: Undefined variable: `break` @ get
見なかったことにする。
kb84tkhr突然env周りを書き直したくなった。
こういうところでenvの中身を直接いじってるのはよくないなと。
define使って定義すればいいじゃない。
top_env = None
def init_env():
global top_env
top_env = {"parent": top_env, "vals": builtins.copy()}
top_env = {"parent": top_env, "vals": {}}
というわけでこうした。
def new_env(): return {"parent": None, "vals": {}}
def new_scope(env): return {"parent": env, "vals": {}}
top_env = new_env()
def init_env():
global top_env
for name, func in builtins.items(): define(top_env, name, func)
top_env = new_scope(top_env)
extend()でもenvの中身を直接いじってたのでdefineを呼ぶようにした。
def extend(env, params, args):
if params == [] and args == []: return {}
assert len(params) > 0, \
f"Argument count doesn't match: `{params}, {args}` @ extend"
match params[0]:
case str(param):
assert len(args) > 0, \
f"Argument count doesn't match: `{params}, {args}` @ extend"
define(env, param, args[0])
extend(env, params[1:], args[1:])
case ["*", rest]:
assert len(params) == 1, \
f"Rest param must be last: `{params}` @ extend"
define(env, rest, args)
case unexpected:
assert False, f"Unexpected param at extend: {unexpected}"
new_scope()にあたることもextend()内でやってたけれども呼び出し側に移した。
これは必ずしもこっちの方がいいわけではない気もするけど、new_scope()も加えてenvを扱うための基本操作がそろった感じがするので。
def apply(func, args, cont):
if callable(func):
return lambda: cont(func(args))
else:
_, params, body, env = func
env = new_scope(env); extend(env, params, args)
return lambda: eval_expr(body, env, cont)
extendはenv操作のライブラリのつもりでdefineやgetの近くに置いてたけどそうじゃなくてevalやapplyの側に属する操作かもしれない。
ていうかきっとそうだ。
というわけで場所を移した。
なんか整理がついてすっきり。
あとついでにこっそりdefineで二重定義のチェックを外した。
def define(env, name, val):
# assert name not in env["vals"], \
# f"Variable already defined: `{name}` @ define"
env["vals"][name] = val
return val
実験用にはこのチェックがない方が便利なので。
kb84tkhrこれは最小evalにも反映するべきだろうということで反映した。
# environment
def new_env(): return {"parent": None, "vals": {}}
def new_scope(env): return {"parent": env, "vals": {}}
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 = new_scope(env)
for param, arg in zip(params, args_val): define(env, param, arg)
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 = new_env()
for name in builtins: define(top_env, name, builtins[name])
top_env = new_scope(top_env)
def run(src):
return eval(src, top_env)
applyでやってることが明確になったと思う。
満足。
kb84tkhr関数呼び出しを作る。
取り立てて難しいところはない・・・よな？
restパラメータは関数定義の方だし・・・
じゃあこれで。
ループで回しているのはfunction_returns_function(5)(6)のような形にも対応するため。
def call():
op = primary()
while current_token == "(":
advance()
op = [op] + args()
return op
def args():
args = []
if current_token != ")":
args.append(expression())
while current_token == ",":
advance()
args.append(expression())
consume(")")
return args
def primary():
...
組み込み関数も、ユーザ定義関数も呼び出せる。
addは+という演算子にもなっているけれども影響はない。
self.assertEqual(run("add(5; 6, 7; 8)"), 14)
self.assertEqual(run("inc(5; 6)"), 7)
呼び出しの記法とASTの形はマクロでも同じなので実はマクロも呼び出せる。
self.assertEqual(run("and(True, False)"), False)
それどころかこんなのまで動いてしまう。
self.assertEqual(run("""
i := sum := 0;
awhile(True,
if i == 5 then i = i + 1; continue end;
if i >= 10 then break sum end;
sum = sum + i;
i = i + 1)
"""), 40)
awhileにしてるのは、whileだとwhile ... do ... endとして構文解析してしまうのでエラーになってしまうから。
awhileどうするかはまだ考え中。
kb84tkhradvance()を呼びだす場所をちょっと悩んでいる。
ここだけ見ると、advance()はif_()の中で呼ぶ方が素直じゃねって気がする。
case "while":
advance(); return while_() # advance() をここではなく
...
def if_():
# ここで呼ぶ
cnd = expression()
...
ただ、カッコの処理との統一感的にはadvance()してからif_()を呼びたい気持ち。
case "(":
advance(); expr = expression(); consume(")")
return expr
case "if":
advance(); return if_()
expression()の先頭でadvance()を呼ぶわけにいかないから。
カッコのときはadvance()してから処理を呼び、if_()のときは処理の中でadvance()を呼ぶことになにか納得感の行く説明ができればそうしたい気もする。
カッコはexpressionの一部じゃないからなあ。
それくらいでいいのかなあ。
これはあたためておく。
kb84tkhrさて次はlambdaを・・・と思ったけどどんな形にしよう？
func (param1, param2, ...) do ... endかな？
カッコがあるならdoはいらない？とするとfunc (param1, param2, ...) ... end？
endなしだと困るかな？困りそうだな・・・
それともカッコを取ってfunc param1, param2, ... do ... endかな？
これは呼び出しと見かけが違ってくるからやめとこう。
func (param1, param2, ...) ... endで。
パラメータの列は式が並んでるものとみる。
ほんとうはもっと細かく作ることもできるんだけど。
restパラメータの*の扱いとかもあるので。
式の並びと見ればcall()と共用できる。
後で配列を扱うときにも使えるはず。
def comma_separated_exprs(closing_token):
cse = []
if current_token != closing_token:
cse.append(expression())
while current_token == ",":
advance()
cse.append(expression())
consume(closing_token)
return cse
call()はこうなる。
def call():
op = primary()
while current_token == "(":
advance()
op = [op] + comma_separated_exprs(")")
return op
restパラメータの*は前置の単項演算子と見てunary_minus()のところに入れる。
def unary_ops():
return unary({"-": "neg", "*": "*"}, call)
パラメータの解析を教養にしたおかげでユーザ関数はこれくらいで書ける。
def primary():
...
case "func":
advance(); return func_()
...
def func_():
consume("(")
params = comma_separated_exprs(")")
body = expression()
consume("end")
return ["func", params, body]
ちゃんと呼び出せるし
def test_func(self):
self.assertEqual(run("func (a, b) a + b end (5, 6)"), 11)
self.assertEqual(run("func (*args) args end ()"), [])
self.assertEqual(run("func (*args) args end (5)"), [5])
self.assertEqual(run("func (*args) args end (5, 6)"), [5, 6])
self.assertEqual(run("func (*(args)) args end (5, 6)"), [5, 6])
おかしな書き方はちゃんとエラーになる（evalでチェックされる）。
エラーメッセージが的確かはおいておくとして。
self.assertTrue(fails("*a"))
self.assertTrue(fails("func (a, b) a + b"))
self.assertTrue(fails("func a, b) a + b end (5, 6)"))
self.assertTrue(fails("func (a, b a + b end (5, 6)"))
self.assertTrue(fails("func (a b) a + b end (5, 6)"))
self.assertTrue(fails("func (a, b + c) a + b end (5, 6)"))
kb84tkhr self.assertEqual(run("func (*args) args end (5, 6)"), [5, 6])
お気づきだろうか。
なにもしてないけど配列はそれなりに使える。
全部組み込み関数だから。
ジェネレータだって作れる。
def test_array(self):
self.assertEqual(run("arr()"), [])
self.assertEqual(run("arr(5; 6)"), [6])
self.assertEqual(run("arr(5; 6, 7; 8)"), [6, 8])
self.assertTrue(run("is_arr(arr())"))
self.assertFalse(run("is_arr(1)"))
self.assertEqual(run("len(arr(5, 6, 7))"), 3)
self.assertEqual(run("getat(arr(5, 6, 7), 1)"), 6)
self.assertEqual(run("setat(arr(5, 6, 7), 1, 8)"), [5, 8, 7])
self.assertEqual(run("slice(arr(5, 6, 7), 1, 2)"), [6])
self.assertEqual(printed("""
a := arr(5, 6, 7);
g := agen(a);
print(g(), g(), g())
"""), (None, "5 6 7\n"))
自分はさっきまで気づいてなかった。
kb84tkhrそれでいいような気もしないでもないけれども配列リテラルとインデックス表記にも対応する。
スライスもやる？
配列リテラルはこれだけ。楽ちん！
def primary():
match current_token:
...
case "[":
advance(); elems = comma_separated_exprs("]")
return ["arr"] + elems
...
さっきのテストを配列リテラルに書き換えて。
def test_array(self):
self.assertEqual(run("[]"), [])
self.assertEqual(run("[5; 6]"), [6])
self.assertEqual(run("[5; 6, 7; 8]"), [6, 8])
self.assertTrue(run("is_arr([])"))
self.assertFalse(run("is_arr(1)"))
self.assertEqual(run("len([5, 6, 7])"), 3)
スライスの表記を使わないならインデックス表記はcall()を書き換えてこれで済む。
def call_index():
target = primary()
while current_token in ("(", "["):
match current_token:
case "(":
advance()
target = [target] + comma_separated_exprs(")")
case "[":
advance()
target = ["getat", target, expression()]
consume("]")
return target
2次元配列とか関数の配列とかそういうのも動く。
self.assertEqual(run("[5, 6, 7][1]"), 6)
self.assertEqual(run("[[5, 6, 7], [15, 16, 17], [25, 26, 27]][1]"), [15, 16, 17])
self.assertEqual(run("[[5, 6, 7], [15, 16, 17], [25, 26, 27]][1][2]"), 17)
self.assertEqual(run("[add, sub][0](5, 6)"), 11)
self.assertEqual(run("func (a, b) [a, b] end)(5, 6)[1]"), 6)
スライスの表記に対応しようとするとけっこう面倒だ。
そこら中省略可能だから。
:でなければ式のはずだから式を読む
]が来ていれば終わり、ASTを返す
:でなければエラー
的なことを繰り返していく。
そこら中省略可能とは言え[]はエラーであることと、[1]のような形はスライスではないことには注意。
愚直に書いたらこうなった。
def index_slice(target):
start = end = step = None
if current_token == "]":
assert False, f"Invalid index/slice: `{current_token}` @ index_slice"
if current_token != ":":
start = expression()
if current_token == "]":
advance()
return ["getat", target, start]
if current_token != ":":
assert False, f"Invalid index/slice: `{current_token}` @ index_slice"
advance()
if current_token == "]":
advance()
return ["slice", target, start, end, step]
if current_token != ":":
end = expression()
if current_token == "]":
advance()
return ["slice", target, start, end, step]
if current_token != ":":
assert False, f"Invalid index/slice: `{current_token}` @ index_slice"
advance()
if current_token == "]":
advance()
return ["slice", target, start, end, step]
if current_token != ":":
step = expression()
if current_token == "]":
advance()
return ["slice", target, start, end, step]
assert False, f"Invalid index/slice: `{current_token}` @ index_slice"
なかなか死ねる。
愚直に書いたらと言ったけれどもあれは嘘。これしか思いつかない。
よい書き方があったら教えてほしい。
slice()にも手を入れた。
組み込みのslice()を使うので名前を変えている。
構文解析側で引数は必ず３つ書くようにしたので実はmatchしなくてもよいのだけれども既存のテストが通らなくなるので残した。
最初から字句解析・構文解析ありで作るとこの辺は違ってきそうだ。
人間にはわかりやすく、evalはシンプルに、そのために字句解析と構文解析ががんばる、という構図。
def slice_(args):
match args:
case [arr]: return arr[:]
case [arr, start]: return arr[start:]
case [arr, start, end]: return arr[start:end]
case [arr, start, end, step]: return arr[slice(start, end, step)]
case _: assert False, f"Invalid slice: args=`{args}` @ slice"
テストもなかなか。
def test_array_index_slice(self):
run("a := [5, 6, 7, 8, 9]")
self.assertTrue(fails("a[]"))
self.assertEqual(run("a[1]"), 6)
self.assertEqual(run("a[:])"), [5, 6, 7, 8, 9])
self.assertTrue(fails("a[1,]"))
self.assertEqual(run("a[1:])"), [6, 7, 8, 9])
self.assertEqual(run("a[1:4])"), [6, 7, 8])
self.assertEqual(run("a[:4])"), [5, 6, 7, 8])
self.assertTrue(fails("a[1:2,]"))
self.assertEqual(run("a[3:1:-1])"), [8, 7])
self.assertEqual(run("a[:1:-1])"), [9, 8, 7])
self.assertEqual(run("a[3::-1])"), [8, 7, 6, 5])
self.assertEqual(run("a[1:4:])"), [6, 7, 8])
self.assertEqual(run("a[::-1])"), [9, 8, 7, 6, 5])
self.assertEqual(run("a[:3:])"), [5, 6, 7])
self.assertEqual(run("a[1::])"), [6, 7, 8, 9])
self.assertEqual(run("a[::])"), [5, 6, 7, 8, 9])
self.assertTrue(fails("a[1:2:3,"))
self.assertEqual(run("a[0;3:0;1:0;-1])"), [8, 7])
全部カバーしてるかな、という心配はあるけれどもこれくらい通ればまあまあ大丈夫なのでは。
kb84tkhrあとはsetat()を=で書けるようにすれば配列関係は完成。
構文解析はできててa[1] = 8と書くと["assign", ["getat", "a", 1], 8]というASTになる。
これを評価できるようにする。
今のコード。
case ["assign", name, expr]:
return lambda: eval_expr(expr, env,
lambda val: cont(assign(env, name, val)))
ここではnameの名の通り、変数名が入ることしか考えていなかった。
["getat", A, B]だったらAのB番目に値を代入するようにしてやる。
def eval_expr(expr, env, cont):
match expr:
...
case ["assign", left, expr]:
return lambda: eval_assign(left, expr, env, cont)
...
def eval_assign(left, expr, env, cont):
def eval_assign(val):
match left:
case str(name):
return cont(assign(env, name, val))
case ["getat", arr, idx]:
return eval_expr(arr, env,
lambda arr_val: eval_expr(idx, env,
lambda idx_val: cont(setat([arr_val, idx_val, val]))))
assert False, f"Invalid assign target: {left} @ eval_assign"
return lambda: eval_expr(expr, env, eval_assign)
今までsetat()は左辺の配列全体を返していたけれどもそれだとa[1] = a[3] = 2とか書いたときに変だな。
右辺を返すべき。
def setat(args):
assert len(args) == 3, \
f"Argument count doesn't match: `{args}` @ setat"
args[0][args[1]] = args[2]
return args[2]
できた。
2次元配列になってもこれで動いてしまうので楽しい。
def test_array_set(self):
run("a := [5, 6, 7]")
self.assertEqual(run("a[0; 1] = True or False"), True)
self.assertEqual(run("a"), [5, True, 7])
run("a := [[5, 6, 7], [15, 16, 17], [25, 26, 27]]")
self.assertEqual(run("a[1] = []"), [])
self.assertEqual(run("a"), [[5, 6, 7], [], [25, 26, 27]])
self.assertEqual(run("a[0][2] = 8"), 8)
self.assertEqual(run("a"), [[5, 6, 8], [], [25, 26, 27]])
self.assertTrue(fails("5 + 6 = 7"))
kb84tkhrいろいろ書いたのでそろそろマクロやるか。
今回の実験ではここがヤマだと思っている。
先にqとqqを試しておく。
新たな記法は入れず普通に関数の形で書くならなにもしなくてもいける・・・？
def test_q(self):
self.assertEqual(run("q(5)"), 5)
self.assertEqual(run("q(None)"), None)
self.assertEqual(run("q(foo)"), "foo")
self.assertEqual(run("q([5, 6])"), ["arr", 5, 6])
self.assertEqual(run("q(add(5, 6))"), ["add", 5, 6])
self.assertEqual(run("q(5 + 6)"), ["add", 5, 6])
ふむ。
そうなるだろうなという感じ。
q(5 + 6)が ["add", 5, 6]になるあたりはなにかあるかもしれない。
qqはどうか。
!!や構文あたりも気になるところ。
def test_qq(self):
self.assertEqual(run("qq(5)"), 5)
self.assertEqual(run("qq(None)"), None)
self.assertEqual(run("qq(foo)"), "foo")
self.assertEqual(run("qq([5, 6])"), ["arr", 5, 6])
self.assertEqual(run("qq(add(5, 6))"), ["add", 5, 6])
self.assertEqual(run("qq(5 + 6)"), ["add", 5, 6])
self.assertEqual(run("qq(!(add(5, 6)))"), 11)
self.assertEqual(run("qq(add(5, !(6 ; 7)))"), ["add", 5, 7])
self.assertEqual(run("qq(!(5 + 6))"), 11)
self.assertEqual(run("qq(5 + !(6; 7))"), ["add", 5, 7])
self.assertEqual(run("qq(add(!!([5, 6])))"), ["add", 5, 6])
self.assertEqual(run("qq(add(5, !!([6])))"), ["add", 5, 6])
self.assertEqual(run("qq(if a == 5 then 6; 7 else !(8; 9) end)"),
["if", ["equal", "a", 5], ["scope", ["do", 6, 7]], ["scope", 9]])
5 + !!([6, 7])みたいなことはできないけどそれなりになんとかはなっている気がする。
これくらいで実際にマクロ書いてみるか。
kb84tkhrstdlib()で定義しているマクロを書き換えていこう。
# eval(["define", "scope", ["macro", ["body"],
# ["qq", [["func", [], ["!", "body"]]]]]])
run("scope := macro (body) qq(func () !(body) end ()) end")
def test_scope(self):
self.assertEqual(printed("""
a := 5;
scope(a := 6; print(a));
print(a)
"""), (None, "6\n5\n"))
動いた。幸先よし。
関数の表記になるのは微妙だけど。
構文解析もカスタマイズできるようにしたりできるのかな。
今は構文の構造とパーザの構造ががっつり対応してるから無理。
もっとデータにすれば動的に変更できるかもだけど。
話は変わってfuncでscopeを定義するってなんか逆な気もする。
scopeと:=を組み合わせてfuncを作れないものか？
もうちょっとなにか要りそうだけど。
kb84tkhrちょっとまてよ
こういう１からASTを組み上げるような書き方ってできるのか？
["define", "scope", ["macro", ["body"],
["arr", ["arr", ["q", "func"], ["arr"], "body"]]]]
直訳するとこうだけれどもこれはダメ。
run("scope := macro (body) [[q(func), [], body]] end")
パーザはfuncの次には(が来ると思ってるところ)が来てるのでエラー。
qの中にはちゃんと式として成り立っているものを書かないといけない。
じゃあってんでqの中にちゃんと書いてやろうとするとbodyは評価してやらないといけないので元のqqを使った書き方に戻ってしまう。
それともqqで書くという約束でなんでも書けてしまうんだろうか。
それならそれでいいけど。
実際のところ、今まで書いたマクロの多くはまるごとqqなのでなんとかなりそうな気がしている。
そうでないマクロ、たとえばletは書けるだろうか。
eval(["define", "let", ["macro", ["bindings", "body"], ["do",
["define", "defines", ["func", ["bindings"],
["map", "bindings", ["func", ["b"], ["qq",
["define",
["!", ["first", "b"]],
["!", ["last", "b"]]]]]]]],
["qq", ["scope", ["do",
["!!", ["defines", "bindings"]],
["!","body"]]]]]]])
直訳してみる。
直訳でも書けたのは朗報。
run("""
let := macro (bindings, body)
defines := func (bindings)
map(bindings, func (b)
qq(!(first(b)) := !(last(b)))
end)
end;
qq(scope(!!(defines(bindings)); !(body))
end
""")
しかしこれが動かない。
self.assertEqual(run("let([[a, 5], [b, 6]], a + b)"), 11)
なぜか。
expandしたASTを見てみる。
['scope',
['do',
['define', 'a', 'r'],
['define', 'arr', 5],
['define', 'arr', 6],
['add', 'a', 'b']]]
なにこれ
あー
bindingsには[["a", 5], ["b", 6]]が入ってるのが期待なんだけど、実は["arr", ["arr", "a", 5], ["arr", "b", 6]]]が入ってるってわけかーそうかー
でも['define', 'a', 'r']ってどういうこと？
first("arr")が"a"でlast("arr")が"r"ってことか！
オモロ
オモロとか言ってる場合じゃない。
えーとこれは設計の根幹の問題でASTを配列で書いてるから配列になんか目印をつけないと見分けがつかないという。
AST用のクラスでも作って配列はまんま配列としておけばキレイにできたわけだが。
今回は小手先でかわす。
要は"arr"を飛ばして呼んでやればいいわけなので。
run("""
let := macro (bindings, body)
defines := func (bindings)
map(bindings[1:], func (b)
qq(!(b[1]) := !(b[2]))
end)
end;
qq(scope(!!(defines(bindings)); !(body)))
end
""")
まあletもクリアできたことにしよう。
letが書けるなら既存のマクロは全部書き換えられそうな気がする。
kb84tkhrところで
let := macro (bindings, body)
defines := func (bindings)
map(bindings, func (b)
qq(!(first(b)) := !(last(b)))
はmacroやfuncの右側がなんか寒々しい。
{とか:とかついてるのに慣れてるからだろうけど。
doでもつける？
let := macro (bindings, body) do
defines := func (bindings) do
map(bindings, func (b) do
qq(!(first(b)) := !(last(b)))
まあ落ち着くっちゃあ落ち着く。
カッコで終わりは明確なんだからdoは冗長だけど。
あと関数ってほんとはdoじゃない気がするんだよなー
isとかequalsの方が本来の意味に近い気がするんだけどでもここに書くとそぐわない
たとえばこういう形で定義するなら完全にisだと思うんだが
func add (a, b) is a + b end
とりあえず慣れの問題ということでそのままにして進む。
kb84tkhrところでところで
カッコが増えてくるとシンタックスハイライトが恋しい
文字列の中だとシンタックスハイライトが利かなくてカッコを自分で数えないといけない
ファイルに書くようにしたらシンタックスハイライト利くかな
let := macro (bindings, body)
defines := func (bindings)
map(bindings[1:], func (b)
qq(!(b[1]) := !(b[2]))
end)
end;
qq(scope(!!(defines(bindings)); !(body)))
end
これだけのファイルを作ってみたらJuliaと判定されてそこそこシンタックスハイライトが利いている
endでインデントが下がったりする
Juliaってこんなんだっけ？
ここでjuliaを指定したらどうなるかな
let := macro (bindings, body)
defines := func (bindings)
map(bindings[1:], func (b)
qq(!(b[1]) := !(b[2]))
end)
end;
qq(scope(!!(defines(bindings)); !(body)))
end
おっそれなりにハイライトされてる
funcがハイライトされてないのが残念
macroはハイライトされたのに！
そういう気持ち悪さもあるのでこのまま進む。
テストのお手軽さというのも捨てがたい。
次だな次。次でいろいろやろう。
自分でLSP書くというのも楽しいかもしれない。
できるかどうかは知らんけど。
kb84tkhrということはもらったASTを直接書き換えちゃうマクロもできるわけだな
うれしい応用はぱっとは思いつかないけどなんか邪悪なことができそうな気がする
run("""
force_minus := macro (expr)
expr[0] = q(sub); expr
end
""")
self.assertEqual(run("force_minus(5 + 6)"), -1)
ASTが書き換わっていることを確認
run("""
force_minus := macro (expr)
expr[0] = q(sub); expr
end
""")
ast = parse("force_minus(5 + 6)")
import pprint
pprint.pprint(ast)
print(eval(ast))
pprint.pprint(ast)
出力結果
['force_minus', ['add', 5, 6]]
-1
['force_minus', ['sub', 5, 6]]
とはいえ本当にASTそのものを書き換えてしまうのはあまりにも邪悪すぎる気がするのでいったんコピーしておくくらいがいいのかもしれない
run("""
force_minus := macro (expr)
e := expr[:]; e[0] = q(sub); e
end
""")
大丈夫
['force_minus', ['add', 5, 6]]
-1
['force_minus', ['add', 5, 6]]
本当にASTそのものを書き換えてしまうのはあまりにも邪悪すぎる気がする
いやこれって考えてみたらマクロを展開するたびにASTを置き換えていけば2回目以降は展開済みのASTで評価できるってことじゃない？
マクロの中で一部置き換えるのとは違う話になるけど
kb84tkhrやってみる！
思ったほどややこしくせずに済んだ。
replace_and_eval()がメインで、置き換えてから評価している。
そのためにexpr全体を渡してもらう必要がある。
def eval_expr(expr, env, cont):
match expr:
...
case [op_expr, *args_expr]:
return lambda: eval_op(expr, op_expr, args_expr, env, cont)
...
def eval_op(expr, op_expr, args_expr, env, cont):
def replace_and_eval(expanded):
nonlocal expr; expr[:] = expanded
return lambda: eval_expr(expr, env, cont)
def _eval_op(op):
match op:
case ["macro", params, body, macro_env]:
return lambda: expand(body, params, args_expr, macro_env,
replace_and_eval)
...
正しく動いているか。
FAIL: test_macro_firstclass (test_eval.TestProblems.test_macro_firstclass)
----------------------------------------------------------------------
Traceback (most recent call last):
File "/workspaces/toig/test_eval.py", line 447, in test_macro_firstclass
self.assertEqual(eval(["map",
AssertionError: Lists differ: [False, False] != [False, True]
このテストで失敗してた。
self.assertEqual(eval(["map",
["arr", "and", "or"],
["func", ["op"], ["op", True, False]]]),
[False, True])
andとorでmapしようとしてるんだけれども、andでmapしたときに["op", True, False]が書き換えられてマクロでなくなってしまうのでorの番が来てもあらためて展開されない、というわけ。
毎回展開するのをやめたらこういうことが発生するのは想定内っちゃあ想定内。
ただうっかり使っちゃったときに気づけるかというところが心配。
エラーにできるかなあ？あんまりいいアイデアは思いつかない。
それはそれとして
速くなってるかな？
マクロ使っててベンチマークになりそうなtest_sieve()で30までの素数を求めているところ100までにして試す。
通常版
Ran 1 test in 4.463s
置き換え版
Ran 1 test in 4.066s
あれあんまり変わってない
もっとちゃんと確かめよう。
これでベンチマークする。
時間とexpand回数を測って、実行後のASTも出力。
内側のループの中でもマクロを（わざわざ）使った。
そういえばまだ
きっとこれではっきりするだろう。
import pprint, timeit
eval(["define", "n", 200])
eval(["define", "sieve", ["add",
["mul", ["arr", False], 2],
["mul", ["arr", True], ["sub", "n", 2]]]])
eval(["define", "j", None])
eval(["define", "inc_by", ["macro", ["x", "by"],
["qq", ["assign", ["!", "x"], ["add", ["!", "x"], ["!", "by"]]]]]])
ast = ["for", "i", ["range", 2, "n"],
["when", ["getat", "sieve", "i"],
["do",
["assign", "j", ["mul", "i", "i"]],
["while", ["less", "j", "n"], ["do",
["setat", "sieve", "j", False],
["inc_by", "j", "i"]]]]]]
expand_count = 0
print(timeit.timeit("eval(ast)", number=1, globals=globals()))
print(expand_count)
eval(["define", "primes", ["arr"]])
eval(["for", "i", ["range", 0, "n"],
["when", ["getat", "sieve", "i"],
["assign", "primes", ["append", "primes", "i"]]]])
eval(["print", "primes"])
pprint.pprint(ast)
通常版を走らせた結果
965回expandして7.5秒くらい。
7.471212527001626
965
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
['for',
'i',
['range', 2, 'n'],
['when',
['getat', 'sieve', 'i'],
['do',
['assign', 'j', ['mul', 'i', 'i']],
['while',
['less', 'j', 'n'],
['do', ['setat', 'sieve', 'j', False], ['inc_by', 'j', 'i']]]]]]
置き換え版
expand()は9回に激減したけど時間はほぼ同じ。
実行するたびに所要時間がゆれるので誤差の範囲。
えー
7.415850976991351
9
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
[['func',
[],
['do',
['define', '__stdlib_for_index', 0],
['define', 'i', None],
['define', 'break', None],
['define',
'continue',
['func',
[],
['do',
['assign', '__stdlib_for_index', ['inc', '__stdlib_for_index']],
['go']]]],
['define',
'go',
['func',
[],
['if',
['less', '__stdlib_for_index', ['len', ['range', 2, 'n']]],
[['func',
[],
['do',
['assign', 'i', ['getat', ['range', 2, 'n'], '__stdlib_for_index']],
['if',
['getat', 'sieve', 'i'],
[['func',
[],
['do',
['assign', 'j', ['mul', 'i', 'i']],
[['func',
[],
['do',
['define', 'break', None],
['define', 'val', None],
['define',
'continue',
['func',
[],
['if',
['less', 'j', 'n'],
['do',
['assign',
'val',
['do',
['setat', 'sieve', 'j', False],
['assign', 'j', ['add', 'j', 'i']]]],
['continue']],
'val']]],
['letcc',
'cc',
['do', ['assign', 'break', 'cc'], ['continue']]]]]]]]],
None],
['continue']]]],
None]]],
['letcc', 'cc', ['do', ['assign', 'break', 'cc'], ['go']]]]]]
だいぶ節約できるだろうと思ったのにな
ほかの処理にかかる時間がほとんどってことかな
マクロ展開するとけっこうすごいことになってるし
というわけで展開結果を取っておくのはやめました
kb84tkhr
nonlocal expr; expr[:] = expanded
スライスへの代入忘れとったわ！
def eval_assign(left, expr, env, cont):
def _eval_assign(val):
match left:
...
case ["slice", arr, start, end, step]:
return eval_expr(arr, env,
lambda arr_val: eval_expr(start, env,
lambda start_val: eval_expr(end, env,
lambda end_val: eval_expr(step, env,
lambda step_val: cont(set_slice(
[arr_val, start_val, end_val, step_val, val]))))))
...
def set_slice(args):
arr, start, end, step, val = args
arr[start:end:step] = val
return val
builtins = {
...
"set_slice": set_slice,
...
段差がすごいことに
def test_array_set(self):
run("a := [5, 6, 7, 8, 9]")
self.assertEqual(run("a[0; 1] = True or False"), True)
self.assertEqual(run("a"), [5, True, 7, 8, 9])
self.assertEqual(run("a[3:] = [10, 11]"), [10, 11])
self.assertEqual(run("a"), [5, True, 7, 10, 11])
run("a[1:4] = [12, 13, 14]")
self.assertEqual(run("a"), [5, 12, 13, 14, 11])
run("a[:2] = [15, 16]")
self.assertEqual(run("a"), [15, 16, 13, 14, 11])
run("a[3:1:-1] = [17, 18]")
self.assertEqual(run("a"), [15, 16, 18, 17, 11])
よかろう
kb84tkhr構文を導入してはstdlibのevalをrunに書き換えてると構文とマクロ（関数も）の名前がぶつかる問題が発生する。
これ
def primary():
match current_token:
...
case "while":
advance(); return while_()
とこれ。
# eval(["define", "while", ["macro", ["cnd", "body"], ["qq",
# ["scope", ["do",
# ["define", "break", None],
# ["define", "val", None],
# ["define", "continue", ["func", [],
# ["if", ["!", "cnd"],
# ["do", ["assign", "val", ["!", "body"]], ["continue"]],
# "val"]]],
# ["letcc", "cc", ["do", ["assign", "break", "cc"], ["continue"]]]]]]]])
run("""
while := macro (cnd, body) qq(scope(
break := val := None;
continue := func()
if !(cnd) then val = !(body); continue() else val end
end;
letcc cc do break = cc; continue() end
))
""")
rubyやSmalltalkの気持ちがわかってきた気がするぞ
kb84tkhr上野マクロのwhileと構文のwhileに違う名前を割り当てればとりあえずは解決するしそれほど悪い解決策ではないと思うのだけれどもいったんリセットして考えたい。
追加した構文を外す。
def break_continue():
# if current_token == "break":
# advance()
# return ["break", define_assign()]
# if current_token == "continue":
# advance()
# return ["continue"]
return define_assign()
def primary():
match current_token:
case "(":
advance(); expr = expression(); consume(")")
return expr
case "[":
advance(); elems = comma_separated_exprs("]")
return ["arr"] + elems
case "if":
advance(); return if_()
# case "while":
# advance(); return while_()
case "letcc":
advance(); return letcc()
case "func":
advance(); return func_()
case "macro":
advance(); return macro()
return advance()
while、break、continueはどれも関数スタイルの書き方になる。
def test_break_continue(self):
self.assertEqual(run("""
i := sum := 0;
while(True,
if i == 5 then i = i + 1; continue() end;
if i >= 10 then break(sum) end;
sum = sum + i;
i = i + 1
)
"""), 40)
これもこれでありなんだけれども。
kb84tkhrといったところをいじってる間におかしい挙動を見つけた。
これが IndexError になってしまう。
run("""
a := [5, 6, 7, 8, 9];
i := sum := 0;
while(i < len(a),
if a[i] == 8 then
i = i + 1;
continue()
end;
sum = sum + a[i];
i = i + 1);
print(sum)
""")
調べる。
toigはデバッガがないのでややこしくなってきたらprintデバッグしかない。
試行錯誤してここまでprintを入れたところで事象を確認。
run("""
a := [5, 6, 7, 8, 9];
i := sum := 0;
while(i < len(a),
if a[i] == 8 then
print(0, i);
i = i + 1;
continue();
print(1, i)
end;
print(2, i);
sum = sum + a[i];
i = i + 1)
""")
continue()から戻ってきてしまっている → 1 5
2 0
2 1
2 2
0 3
2 4
1 5
2 5
continue()はただの関数として実装していたので当たり前だった。
そりゃ戻ってくるよね。
run("""
while := macro (cnd, body) qq(scope(
break := val := None;
continue := func()
if !(cnd) then val = !(body); continue() else val end
end;
letcc cc do break = cc; continue() end))
end
""")
だからこれならうまくいく。
run("""
a := [5, 6, 7, 8, 9];
i := sum := 0;
while(i < len(a),
if a[i] == 8 then
i = i + 1;
continue()
else
sum = sum + a[i];
i = i + 1
end
);
print(sum)
""")
今まで、このテストが通ってるからちゃんと実装できてると思ってた。
self.assertEqual(run("""
i := sum := 0;
while(True,
if i == 5 then i = i + 1; continue() end;
if i >= 10 then break(sum) end;
sum = sum + i;
i = i + 1
)
"""), 40)
この場合、continue()から戻ってきても次の行でbreakしてしまうので発覚しなかった。
教訓：ふたつの機能をひとつのテストでテストしようとしない
kb84tkhrというわけでcontinueもletccで実装する。
run("""
while := macro (cnd, body) qq(scope(
break := continue := val := None;
loop := func()
letcc cc do continue = cc end;
if !(cnd) then val = !(body); loop() else val end
end;
letcc cc do break = cc; loop() end))
end
""")
continue()には引数が必要ないので、継続を引数なしでも呼べるようにする。
def eval_expr(expr, env, cont):
match expr:
...
case ["letcc", name, body]:
def skip(args): raise Skip(lambda: cont(args[0] if len(args) > 0 else None))
return lambda: apply(["func", [name], body, env], [skip], cont)
...
awhileも同じ。
run("""
awhile := macro (cnd, body) qq(scope(
break := continue := val := None;
loop := func()
letcc cc do continue = cc end;
it := !(cnd);
if it then val = !(body); loop() else val end
end;
letcc cc do break = cc; loop() end
)) end
""")
forも作った。これは配列しかとらないやつ。
ジェネレータを使うgforがあればforはいらないんじゃないかと思いつつもジェネレータを作るために使っていたりするので作っておくことにした。
といっても配列しか取れないので汎用性は低い。
ジェネレータをwhileで書くようにするとかして消すほうがいいかもしれない。
run("""
for := macro (e, l, body) qq(scope(do(
__stdlib_for_index := -1;
if not is_name(!(e)) then error(q(must_be_a_name), q(_), !(e), q(at_for)) end;
__stdlib_for_l := !(l);
break := continue := __stdlib_for_val := !(e) := None;
loop := func ()
letcc __stdlib_for_cc do continue = __stdlib_for_cc end;
__stdlib_for_index = __stdlib_for_index + 1;
if __stdlib_for_index < len(__stdlib_for_l) then
!(e) = __stdlib_for_l[__stdlib_for_index];
__stdlib_for_val = !(body);
loop()
else __stdlib_for_val end
end;
letcc __stdlib_for_cc do break = __stdlib_for_cc; loop() end
))) end
""")
マクロの引数についてすこし慎重な書き方をしてみた。
__stdlib_for_indexは新たに導入する変数がbody内の変数とぶつからないように。
__stdlib_for_lはlを評価したい場所が2か所あるのでそのまま!(l)とすると副作用も2回起こってしまうのでそれを防ぐため。
eは名前であることを想定しているので複数回!(e)しても多分問題ない・・・はず。
式も許したら柔軟性が上がって便利になったりするだろうか。わからない。
bodyは1回しか出てこないので大丈夫。
kb84tkhrif not is_name(!(e)) then error(q(must_be_a_name), q(_), !(e), q(at_for)) end;
慎重ついでにeが名前であることをチェックしてみた。
is_name()はあらたに作成。
builtins = {
...
"is_name": lambda args: n_ary(1, is_name, args),
...
}
run("""
__stdlib_is_name_before := is_name;
is_name := macro (e) qq(__stdlib_is_name_before(q(!(e)))) end
""")
is_name(foo)となったときfooが評価されては意図と違うのでマクロで書いた。
is_name(q(foo))と書くのは面倒だし。
組み込み関数をマクロで上書きするという技を使っている。
自分だけは呼び出せるようもとの組み込み関数は別の変数に覚えておく。
error(q(must_be_a_name), q(_), !(e), q(at_for))は何やってんのと思われそうだけれども文字列型がないので無理やり文字列っぽい変数名を出力している。
evalなら["error", ["q", "Must be a name:"], ["!", e], ["q", "@ for"]]程度には書けるんだけれども、parser通すとq(Must be a name:)とは書けないので。qの中とは言えちゃんとした式でないといけない。
kb84tkhr__stdlib_is_name_beforeみたいな名前はまあこれくらい書いておけば変数名がぶつからないだろうと思ってなんとなくモジュール的に名前を付けた気になっている。
Common Lispではgensymという関数で絶対にぶつからない名前を作ってくれてそれを使うのが正しいらしい。
軽く作るならたいしたしくみはいらなさそうだしあとでやってみるかな
kb84tkhrstdlib()やテストの中身をひととおりevalからrunに書き換えた。
関数は機械的に書き換えれば済むけれどマクロは少々悩んだところもあり。
でもまあだいたい全部parseできるようになったと思っていいということだろう。
kb84tkhrfuncとmacroにdoをつける。
たいして意味はない。
_unfoldl := func (x, b)
if p(x) then b else _unfoldl(t(x), b + [h(x)]) end
end;
なんか右肩のあたりがスースーする。
_unfoldl := func (x, b) do
if p(x) then b else _unfoldl(t(x), b + [h(x)]) end
end;
落ち着く。
オレオレ言語ですから！好き放題！
func (x) returns ... end とか macro (x) expands ... endとかもいいかなと思ったけどちょっと長い。
上の例みたいに行が変わるときはいいけど1行でちょっと書きたいときは長たらしい。
func (x) do x + 1 endをたとえば$($1 + 1)みたいに書けるようにしたらいいかなあ。
まあでもやめとく。
kb84tkhrパーザの変更はconsume("do")を入れてやるだけなんですけどね
def func_():
consume("(")
params = comma_separated_exprs(")")
consume("do")
body = expression()
consume("end")
return ["func", params, body]
def macro():
consume("(")
params = comma_separated_exprs(")")
consume("do")
body = expression()
consume("end")
return ["macro", params, body]
stdlib()とテストは全面的に修正。
kb84tkhr話を戻して（どこへ
こういうのの見かけをもうちょっとよくしたい。
while(i < 10,
sum = sum + i;
i = i + 1;
sum)
こうなるとうれしい。
while i < 10 do
sum = sum + i;
i = i + 1;
sum
end
rubyやSmalltalkの気持ちがわかってきた気がするぞ
rubyからヒントをもらってdo ... endを特別扱いしてみよう
関数呼び出しの後にdo ... endが続いてたら引数に追加してやるくらいでうまくいくかな
def call_index():
target = primary()
while current_token in ("(", "["):
match current_token:
case "(":
advance()
target = [target] + comma_separated_exprs(")")
if current_token == "do":
advance()
target += [expression()]
consume("end")
case "[":
advance()
target = index_slice(target)
return target
あっさりうまくいった。
self.assertEqual(run("""
i := sum := 0;
while (i < 10) do
sum = sum + i;
i = i + 1;
sum
end
"""), 45)
ただし関数呼び出しなのでi < 10はカッコに入れてやらないといけない。
ifと見かけが統一できないのはちょっと気になる。
このdo ... endは関数呼び出しとマクロ呼び出しと共通なので関数でも同じことができる。
def test_func(self):
self.assertEqual(run("func (a, b) do a + b end (5, 6)"), 11)
self.assertEqual(run("func (a, b) do a + b end (5) do 6 end"), 11)
うれしいかどうかはわからない。
kb84tkhrいままでrest引数（関数定義でパラメータに*をつけるやつ）は最後にくるものとしてたんだけれどもdo ... endを作ったのでrest引数の後にも引数を書けるようにしたい。
下のテストはいままで失敗してたけれども rが[5, 6]、aが7になるようにしたいということ。
ここを直す。
self.assertTrue(fails("macro (*r, a) do 5 end (5, 6, 7)"))
ここを直す。
def extend(env, params, args):
...
match params[0]:
...
case ["*", rest]:
assert len(params) == 1, \
f"Rest param must be last: `{params}` @ extend"
define(env, rest, args)
...
rest引数が来たら、残りの仮引数・実引数の数からrest引数にどれだけの長さを割り当てるか計算して割り当てる。
def extend(env, params, args):
...
match params[0]:
...
case ["*", rest]:
rest_len = len(args) - len(params) + 1
assert rest_len >= 0, \
f"Argument count doesn't match: `{params}, {args}` @ extend"
define(env, rest, args[:rest_len])
extend(env, params[1:], args[rest_len:])
...
こういうテストが通る。
self.assertEqual(run("func (*args, a) do [args, a] end (5)"), [[], 5])
self.assertEqual(run("func (*args, a) do [args, a] end (5, 6)"), [[5], 6])
self.assertEqual(run("func (*args, a) do [args, a] end (5, 6, 7)"), [[5, 6], 7])
self.assertEqual(run("func (*args, a, b) do [args, a, b] end (5, 6, 7)"), [[5], 6, 7])
self.assertEqual(run("func (a, *args, b) do [a, args, b] end (5, 6, 7)"), [5, [6], 7])
self.assertEqual(run("func (a, b, *args) do [a, b, args] end (5, 6, 7)"), [5, 6, [7]])
rest引数が複数あったらどうなるのかというとエラーにはならずそれなりに通ってしまう。
ここは未定義動作ということで。
kb84tkhrだいぶendで終わる言語っぽくなった
self.assertEqual(run("""
n := 30;
sieve := [False] * 2 + [True] * (n - 2);
j := None;
for (i, range(2, n)) do
when (sieve[i]) do
j = i * i;
while (j < n) do
sieve[j] = False;
j = j + i
end
end
end;
primes := [];
for (i, range(0, n)) do
when (sieve[i]) do
primes = append(primes, i)
end
end
"""), [2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
そんな感じでなにも定義を変えないでdo ... endを使えるのはけっこう便利でそれで十分なことも多いんだけれども
forなんかはもうひと声ほしい感じ
letもそうかな
stdlibに入ってるものじゃないけど
self.assertEqual(run("""
let ([
[a, 5],
[b, 6]]
) do a + b end
"""), 11)
そしてaifやcondなんかはdo ... endとは相性が悪い
run("""
g3 := gfunc (n) do
yield(n); n = inc(n);
yield(n); n = inc(n);
yield(n)
end;
gsum := func (gen) do aif(gen(), it + gsum(gen), 0) end
""")
run("""
fib := func (n) do
cond(
[n == 0, 0],
[n == 1, 1],
[True, fib(n - 1) + fib(n - 2)])
end
""")
gfuncはいい感じになったんだけれども
このへんを解消することはできるだろうか
letもcondもaifも言語仕様からは外そうかと思ってるものでもあったりする
それとdo ... endとの相性の悪さの間に相関関係はあるだろうか
kb84tkhrちょっと待て
gfuncの定義がなんか変だ
run("""
gfunc := macro (params, body) do qq(
func (!(params)) do
yd := nx := None;
yield := func (x) do letcc cc do nx = cc; yd(x) end end;
next := func () do letcc cc do yd = cc; nx(None) end end;
nx := func (_) do !(body); yield(None) end;
next
end
) end
""")
paramsと言ってるわりに配列が入ってくることを想定していない
こうあるべき
run("""
gfunc := macro (params, body) do qq(
func (!!(params[1:])) do
...
[1:]は["arr", ...]の"arr"を無視するため。
そうするとgfuncの呼び出しがちょっとだけ見た目悪くなる。
run("""
g3 := gfunc ([n]) do
...
""")
なんとかしたい
なんとかなるかな
kb84tkhrもう少しそれっぽい形でかけるようにするにはどうしたらいいだろう。
次に目指すのはforをfor ... in ... do ... endと書けるようにするあたりだろうか。
そうなると文法自体をカスタマイズする必要がありそう。
書きたい形と関数スタイルにしたものを並べてみる。
書きたい形 ： for i in [5, 6, 7] do print(i) end
関数スタイル： for ( i , [5, 6, 7] , print(i) )
whileの場合。
関数スタイル： while ( i < 10 , print(i) )
書きたい形 ： while i < 10 do print(i) end
このレベルなら式と区切りが交互に出てきてそれを関数スタイルに変更するだけでできそう。
区切り語の並びだけ覚えておけば処理できるんじゃないか。
関数／マクロ名 式1 区切り語1 式2 区切り語2 ... end
についてはこんなデータを持っておいて。
{
関数／マクロ名: [区切り語1, 区切り語2, ..., end],
関数／マクロ名: [区切り語1, 区切り語2, ..., end],
...
}
なんでも書けるわけではないけどletも多少よくなる。
関数スタイル： let ( [[a, 5], [b, 6]] , a + b )
書きたい形 ： let [[a, 5], [b, 6]] do a + b end
これまで ： let ( [[a, 5], [b, 6]] ) do a + b end
letは実際には scope(a := 5; b := 6; a + b)と書けば済んでしまうのでそこだけ考えるとモチベーションにはならないのだけれども。
そういえばscopeも scope a := 5; b := 6; a + b end と書けるようにできるか。
今だとscope () do ... endと書かなければならない。
scopeはちょっと長いなあ。こっちをdoにする？ちょっと混乱しそう。
そんなに使いたくもならないしまあほっとくか。
qqとかでも同じことはできそう。
全部endで終わる形にしてしまうとendの階段で行数食われるのがあまりうれしくなかったりするところもある。
カッコでこういうのはもう目が慣れちゃってるんだけれども
(
(
( )))
endだとこう書きたくなる。
do
do
do
end
end
end
これは慣れるだろうか？
do
do
do end end end
gfuncは多少すっきりするけど理想形とは違う。
関数スタイル： gfunc ( [a, b] , yield(a); yield(b) )
書ける形 ： gfunc [a, b] do yield(a); yield(b) end
書きたい形 ： gfunc (a, b) do yield(a); yield(b) end
(a, b)はtoigのexpressionではないので。
aifをifと同じように書けるようにするにはこのしくみではダメそう。
elifの数が決まってないし、単に式を持ってきて関数の引数にすればいいわけでもない。
でもまずはこの作戦で進めてみよう。
kb84tkhrカスタム文法を導入するには、動的なルールに基づいて構文解析を行う仕組みと、そのルールをユーザが定義するしくみが必要。
まず構文解析の方から着手する。
do ... endを引数にするのはやめる。
def call_index():
target = primary()
while current_token in ("(", "["):
match current_token:
case "(":
advance()
target = [target] + comma_separated_exprs(")")
# if current_token == "do":
# advance()
# target += [expression()]
# consume("end")
case "[":
advance()
target = index_slice(target)
return target
カスタム文法は直接定義。
"__stdlib_when"などはいままでwhenだったマクロの名前を変更したもの。
カスタム文法の方を先に定義しているので、when := macro ...のwhenまで構文と思われてしまう。
マクロ定義の後にカスタム文法を導入できるようになったらこんな名前にしなくてもいいかもしれない。ただカスタム文法を定義した後は関数スタイルでは呼べない。そういう意味では別名にしておけば関数スタイルで呼ぶこともできる。うれしいかどうかというとたぶんうれしくはない。
custom_rule = {
"when": ["__stdlib_when", "do", "end"],
"while": ["__stdlib_while", "do", "end"],
"awhile": ["__stdlib_awhile", "do", "end"],
"for": ["__stdlib_for", "in", "do", "end"],
"gfunc": ["__stdlib_gfunc", "do", "end"],
"gfor": ["__stdlib_gfor", "in", "do", "end"],
"let": ["__problems_let", "do", "end"],
}
letの定義をこんなところに入れたくはないけれども今だけだから。
primary()内でカッコでも配列でもfuncでもmacroでもifでもなければカスタム文法を探して一致するものがあればcustom()を呼ぶ。
def primary():
match current_token:
...
case op if op in custom_rule:
advance(); return custom(custom_rule[op])
return advance()
カスタム文法にしたがって解析するところ。
簡単な文法しか作れないので簡単。
def custom(rule):
ast = [rule[0]]
for keyword in rule[1:]:
ast += [expression()]
consume(keyword)
return ast
テストもパラパラ書き換えていく。
このへんはマクロっぽさが消滅したといってよかろう。
run("""
n := 30;
sieve := [False] * 2 + [True] * (n - 2);
j := None;
for i in range(2, n) do
when sieve[i] do
j = i * i;
while j < n do
sieve[j] = False;
j = j + i
end
end
end;
primes := [];
for i in range(0, n) do
when sieve[i] do
primes = append(primes, i)
end
end
""")
gfunc()もそれほど見た目悪くないかなあ。統一感だけの問題。
run("""
walk := gfunc [tree] do
_walk := func (t) do
if is_arr(first(t)) then _walk(first(t)) else yield(first(t)) end;
if is_arr(last(t)) then _walk(last(t)) else yield(last(t)) end
end;
_walk(tree)
end;
gen := walk([[[5, 6], 7], [8, [9, 10]]])
""")
はっ
funcの方をfunc [foo, bar] do ... endにすればよいのでは？（天才
いや、ないでもないか clojure風にしました！とか言って
もっと言えば、関数はひとつだけしか引数を取らないことにして、複数渡したいときは配列として渡す、みたいなことをすればいっそう統一感が出るかもしれない。
呼び出しまで含めて考えると構文解析が難しくなるかもしれない。
evalによるテストはほとんど重複なのでやめた。
kb84tkhr勢いあまってscope()もカスタム文法化してみたけれども同じようにやるとこんな感じでパーザに__stdlib_scopeが埋め込まれてしまってあんまり美しくない。
__stdlib_scopeがscopeであってもあとから定義するものが埋め込まれるという意味では同じなので気分的な問題なんだけれども。
def letcc():
name = advance()
assert is_name(name), f"Invalid name: `{name}` @ letcc"
consume("do")
body = expression()
consume("end")
return ["letcc", name, ["__stdlib_scope", body]]
たぶんscope := macro ...てやってるところさえ過ぎてからカスタム文法を追加すればマクロ名をscopeのままにできるんじゃないか。
カスタム文法を定義できるようにしよう。
カスタム文法用の関数を用意しておく。
runのたびに忘れられては困るのでグローバルに覚えておく。
あんまりカッコよくはないけれども。
top_envだってグローバルにしてるし。
def init_rule():
global custom_rule
custom_rule = {}
def add_rule(name, rule):
global custom_rule
custom_rule[name] = rule
カスタム文法は構文解析中に定義できないといけないので関数やらマクロやらで定義するわけにはいかない（気がする
#から行末までをコメントにするようにして、#rule while do endみたいに定義することにしよう。これくらいなら構文解析中にやってもたいしたことはない。
def next_token():
while current_char().isspace(): advance()
nonlocal token
token = ""
match current_char():
...
case "#": return comment()
...
def comment():
advance()
line = []
while current_char() not in("\n", "$EOF"):
line += current_char()
advance()
line = "".join(line)
if line.startswith("rule"):
keywords = line.split()
add_rule(keywords[1], keywords[1:])
return next_token()
こんな感じでカスタム文法を定義できる。
__stdlib_whenみたいな名前にしなくてもよくなった。
ただし#ruleを先にしてしまうとダメ。
run("""
when := macro (cnd, thn) do qq
if !(cnd) then !(thn) end
end end
#rule when do end
""")
なので勢い余ったscopeもこれでいける。
run("""
scope := macro (body) do qq
func () do !(body) end ()
end end
#rule scope end"
""")
さらに勢い余ってqqも。
def stdlib():
run("None #rule qq end")
qqはマクロじゃないし中身もほかと比べて特殊なことしてるから若干心配だったんだけど問題なく動いている。
Noneをつけてるのは仕様上なにか評価するものがないとエラーになってしまうため。
なおq()はq ... endにはしていない。
たいてい項ひとつを囲んでるだけなので。
q(foo)をq foo endにしてもあまりうれしみがない。
たとえばtryの定義や利用はこうなった。
こんな単純なカスタム文法でもいろいろ改善できる。
endで終わるタイプの文法を試してみたかった動機は記号少なめの見た目にしたかったというところなんだけどけっこう果たせてる気がする。
run("""
raise := func (e) do error(q(raised_outside_of_try), e) end;
try := macro (try_expr, exc_var, exc_expr) do qq scope
prev_raise := raise;
letcc escape do
raise = func (!(exc_var)) do escape(!(exc_expr)) end;
!(try_expr)
end;
raise = prev_raise
end end end;
#rule try catch do end
riskyfunc := func (n) do
if n == 1 then raise(5) end; print(6)
end;
middlefunc := func (n) do
riskyfunc(n); print(7)
end;
parentfunc := func (n) do
try
middlefunc(n); print(8)
catch e do
print(e)
end;
print(9)
end
""")
endがヨコに並ぶのは目の方を慣らすことにした。
コーディング規約的には1行で始めた分を1行で終わるようにするのがわかりやすい気がしている。
tryを例にとると macro do、qq、scopeを1行で始めているのでend end endと1行で３つendを書いて終わらせる、という感じ。
toigのコーディング規約など誰が気にするのかとか言わない。
kb84tkhrさらに柔軟なカスタマイズはできるだろうか。
省略可能な要素とか要素の繰り返しとか。
if ... then ... endやif ... then ... elif ... then ... else ... endなんかは構文解析で["if", thn, els]に翻訳しなおしているけれども、標準の構文はif ... then ... else ... endだけにしてマクロとカスタム文法でif ... then ... endやif ... then ... elif ... then ... else ... endを実現できるようにできるくらいまでいければうれしい。
となると#rule when do endみたいな書き方しかできないと無理かなあ？
ifのルールならたとえば #rule if then *(elif then) ?else end みたいに書ければ処理できそう。
となると#ruleもまた構文解析ですか？
もうひとつパーザを作るのもなんだかかなあ
・・・
もしかしてカスタム文法もparse()してやればよくない？
parse()してる最中にparse()呼んでほんとに大丈夫か微妙に自信がないけれども動かない理由もない。
split()してたところをparse()にして、
def comment():
...
if line.startswith("rule "):
rule = parse(line[5:])
add_rule(rule[1], rule[1:])
...
#ruleはtoigの配列の形で書いてやる。
run("None #rule [qq, end]")
こいつ…動くぞ！
run("None #rule [foo, *bar, *[baz, quz], end]")
でcustom_ruleが
{'foo': ['foo', ['*', 'bar'], ['*', ['arr', 'baz', 'quz']], 'end']}
になるし！
おもしれー！
これはいけるのでは？
kb84tkhrささやかな拡張から始める。
今まで、キーワード、式、キーワード、式、・・・と交代で並んでいることを前提としていたけれども式が出てくる位置をしていできるようにする。こんな感じで。
#rule [for, EXPR, in, EXPR, do, EXPR, end]
実はこれだけならparse()する必要はなかったんだけれども。
先に思い付いたのがそっちだったから仕方ない。
custom()はmatchと再帰で書き換え。
def custom(rule):
def _custom(rule):
match rule[0]:
case "end":
advance()
return []
case "EXPR":
return [expression()] + _custom(rule[1:])
case keyword:
consume(keyword)
return _custom(rule[1:])
return [rule[0]] + _custom(rule[1:])
let [[a, 5], [b, 6]] do ... end ではなく let vars [[a, 5], [b, 6]] do ... end と書くようにするとかできる。
def test_let2(self):
run("""
let := macro(bindings, body) do
...
end
#rule [let, vars, EXPR, do, EXPR, end]
""")
self.assertEqual(run("""
let vars [[a, 5], [b, 6]] do a + b end
"""), 11)
何がうれしいのとか聞かない。
いい例が思いつかなかっただけ。
kb84tkhrここに式を書くと指定できるようになったということは、ここに式でないものの指定もできるはず。
ジェネレータ関数の引数にパラメータリストを渡すとか、
forの変数名のところには変数名を書く（式を書いてはいけない）ようにするとか。
こう。
def custom(rule):
def _custom(i):
match rule[i]:
case "end":
advance()
return []
case "EXPR":
return [expression()] + _custom(i + 1)
case "NAME":
name = expression()
assert is_name(name), f"Invalid name: `{name}` @ custom({rule[0]})"
return [name] + _custom(i + 1)
case "PARAMS":
consume("(")
return [["arr"] + comma_separated_exprs(")")] + _custom(i + 1)
case keyword:
consume(keyword)
return _custom(i + 1)
ast = [rule[0]] + _custom(1)
return ast
NAMEのエラーメッセージでちょっと情報量を増やすためrule[1:]と渡していたところをインデックスを渡すように変えてみた。こっちの方がちょっと速いはずだし（焼け石に水）。そのうち破綻するかもしれない。
#rule [gfunc, PARAMS, do, EXPR, end]
で
g3 := gfunc (n) do
...
end;
と書けたり
#rule [for, NAME, in, EXPR, do, EXPR, end]
で
for 8 in [5, 6, 7] do print(i) end
が
AssertionError: Invalid name: `8` @ custom(for)
になったりするように。
（forでは今までマクロ側で
for := macro (e, l, body) do qq scope
...
if not is_name(!(e)) then error(q(must_be_a_name), q(_), !(e), q(at_for)) end;
...
とチェックして（苦しいエラーメッセージを出して）いた）
kb84tkhrカスタム文法の最初にくる名前＝マクロ名ということでやってきたけれどもこれはなんか余計な制約になってる気がするので、それぞれ指定するようにする。
run("""
__stdlib_when := macro (cnd, thn) do qq
if !(cnd) then !(thn) end
end end
#rule [when, __stdlib_when, EXPR, do, EXPR, end]
""")
マクロはカスタム文法名（そう呼ぶことにする）とは違う名前にすることにした。
修正はほんの少し。
もちろんマクロ名やルールは全書き換えだが。
def comment():
...
if line.startswith("rule "):
rule = parse(line[5:])
add_rule(rule[1], rule[2:])
...
別で指定できるようになったのでふたつの文法でマクロを使いまわすこともできる。
カスタム文法名は変えないといけないが。
例によって何がうれしいかはわからない。
def test_let(self):
run("""
_let := macro(bindings, body) do
...
end
""")
self.assertEqual(run("""
#rule [let, _let, EXPR, do, EXPR, end]
let [
[a, 5],
[b, 6]
] do a + b end
"""), 11)
self.assertEqual(run("""
#rule [let2, _let, vars, EXPR, do, EXPR, end]
let2 vars [
[a, 5],
[b, 6]
] do a + b end
"""), 11)
ところで
パーザに__stdlib_scopeが埋め込まれてしまってあんまり美しくない。
の問題をどうやって解決したかというと、scopeをevalのレベルで実装した。
def eval_expr(expr, env, cont):
...
match expr:
...
case ["scope", expr]:
return lambda: eval_expr(expr, new_scope(env), cont)
...
やりたい放題かよって感じもしないでもないけれども、scopeをfuncで書く、ってなんか逆な気もしてなんか違和感だったんだよねえ
むしろscopeとdefineを組み合わせてfuncをマクロで実現できないのか、みたいな。
ラムダ計算的にはfuncが先にあるわけだけれども。
というわけで自分の中ではそれなりにスジは通っている。
ASTの方のqqやscopeを別の名前にするかどうかはまだ考えている。
kb84tkhrscopeを追加してるときに思い出した
def eval_expr(expr, env, cont):
match expr:
...
case ["do", *exprs]:
return lambda: foldl_cps(exprs,
lambda _, expr, c: eval_expr(expr, env, c),
None, cont)
...
doはdo ... endで盛大に使ってるけれどもこの"do"とは関係ない。
たまに自分でも混乱するので変えてしまおう。
```py
def eval_expr(expr, env, cont):
match expr:
...
case ["seq", *exprs]:
return lambda: foldl_cps(exprs,
lambda _, expr, c: eval_expr(expr, env, c),
None, cont)
...
ここも修正して一貫性が出た。
def sequence():
exprs = [define_assign()]
while current_token == ";":
advance()
exprs.append(define_assign())
return exprs[0] if len(exprs) == 1 else ["seq"] + exprs
test_eval.pyではそこら中に出てくるけれどももう更新していないので消す。
kb84tkhrifのルールならたとえば #rule if then *(elif then) ?else end みたいに書ければ処理できそう。
よしじゃあやるべ
構想とは違うけどこんな感じで動かしたい。
run("""
_my_if := macro(cnd, thn, *rest) do
if len(rest) == 0 then
qq if !(cnd) then !(thn) else None end end
elif len(rest) == 1 then
qq if !(cnd) then !(thn) else !(rest[0]) end end
else qq
if !(cnd) then !(thn) else _my_if(!!(rest)) end
end end
end
#rule [my_if, _my_if, EXPR, then, EXPR, *[elif, EXPR, then, EXPR], ?[else, EXPR], end]
""")
*[elif, EXPR, then, EXPR]はelif EXPR then EXPRの0回以上の繰り返し、?[else, EXPR]はelse EXPRがあってもなくてもいい、というつもり
_my_ifマクロが意外とすっきりした形で書けてちょっと驚いている。再帰さまさまである。条件・結果・条件・結果・・・と規則正しく並んでいるからできることでもある。
?はまだ字句解析を通らないので*[]のほうから実装してみる。
できあがりから言うとこう。
def custom(rule):
def _custom(r):
if r == []: return []
match r[0]:
case "EXPR":
return [expression()] + _custom(r[1:])
case "NAME":
name = expression()
assert is_name(name), f"Invalid name: `{name}` @ custom({rule[0]})"
return [name] + _custom(r[1:])
case "PARAMS":
consume("(")
return [["arr"] + comma_separated_exprs(")")] + _custom(r[1:])
case keyword if is_name(keyword):
consume(keyword); return _custom(r[1:])
case ["*", subrule]:
ast = []
while current_token == subrule[1]:
advance()
ast += _custom(subrule[2:])
return ast + _custom(r[1:])
case unexpected:
assert False, f"Illegal rule: `{unexpected}` @ custom({rule[0]})"
ast = [rule[0]] + _custom(rule[1:])
return ast
ちょこちょこ修正してるところから説明すると、iを引数にするやり方はやっぱり破綻したのでruleそのものを渡す形に戻したのと（もとのruleも参照したかったので引数の受け取り側はrにした）、endが来たら終了としていたのをruleの末尾に到達したら終了と変更している。
本題はcase ["*", subrule]:の節。
subrule[1]に今回で言えばelifが入っているので、今見ているトークンがelifに一致するうちはsubruleで_custom()を呼んでsubruleにしたがってトークンを読みASTを作る。再帰万歳。
?のルールは入れないで試す。
#rule [my_if, _my_if, EXPR, then, EXPR, *[elif, EXPR, then, EXPR], else, EXPR, end]
想定どおり展開されているか？
print(expand(my_if True then 5 + 6 else 7 + 8 end))
→ ['if', True, ['scope', ['add', 5, 6]], ['scope', ['add', 7, 8]]]
print(expand(my_if False then 5 + 6 elif True then 7 + 8 else 9 + 10 end))
→ ['if', False, ['scope', ['add', 5, 6]], ['scope', ['_my_if', True, ['add', 7, 8], ['add', 9, 10]]]]
大丈夫そう。
評価までやる。
self.assertEqual(run("_my_if(True, 5, 6)"), 5)
self.assertEqual(run("_my_if(False, 5, 6)"), 6)
self.assertEqual(run("my_if True then 5 else 6 end"), 5)
self.assertEqual(run("my_if False then 5 else 6 end"), 6)
self.assertEqual(run("_my_if(False, 5, True, 6, 7)"), 6)
self.assertEqual(run("_my_if(False, 5, False, 6, 7)"), 7)
self.assertEqual(run("my_if False then 5 elif True then 6 else 7 end"), 6)
self.assertEqual(run("my_if False then 5 elif False then 6 else 7 end"), 7)
self.assertEqual(run("_my_if(False, 5, False, 6, True, 7, 8)"), 7)
self.assertEqual(run("_my_if(False, 5, False, 6, False, 7, 8)"), 8)
self.assertEqual(run("my_if False then 5 elif False then 6 elif True then 7 else 8end"), 7)
self.assertEqual(run("my_if False then 5 elif False then 6 elif False then 7 else 8end"), 8)
よーし
マクロと構文を別に指定するようにしたおかげで両方テストできている。
kb84tkhr省略可能の?を実装する。
?を受け入れる。
def next_token():
...
match current_char():
case c if c in "+-*/%?()[],;":
append_char()
...
?を単項演算子として扱う。
ただし#ruleの中でしか意味を与えていないのでそこ以外で書くとエラー。
def unary_ops():
return unary({"-": "neg", "*": "*", "?": "?"}, call_index)
カスタム文法の扱いは*とそっくり。
def custom(rule):
def _custom(r):
if r == []: return []
match r[0]:
case ["*", subrule]:
ast = []
while current_token == subrule[1]:
advance()
ast += _custom(subrule[2:])
return ast + _custom(r[1:])
case ["?", subrule]:
ast = []
if current_token == subrule[1]:
advance()
ast += _custom(subrule[2:])
return ast + _custom(r[1:])
...
elseがない形も動くようになった。
self.assertEqual(run("my_if True then 5 end"), 5)
self.assertEqual(run("my_if False then 5 end"), None)
self.assertEqual(run("my_if False then 5 elif True then 6 end"), 6)
self.assertEqual(run("my_if False then 5 elif False then 6 end"), None)
aifにもelifが使えるようになった。
run("""
_aif := macro (cnd, thn, *rest) do
if len(rest) == 0 then qq scope
it := !(cnd); if it then !(thn) else None end
end end elif len(rest) == 1 then qq scope
it := !(cnd); if it then !(thn) else !(rest[0]) end
end end else qq scope
it := !(cnd); if it then !(thn) else _aif(!!(rest)) end
end end end
end
#rule [aif, _aif, EXPR, then, EXPR, *[elif, EXPR, then, EXPR], ?[else, EXPR], end]
""")
def test_aif(self):
self.assertEqual(run("aif 5 then it + 1 end"), 6)
self.assertEqual(run("aif 0 then it + 1 end"), None)
self.assertEqual(run("aif 5 then it + 1 else it + 1 end"), 6)
self.assertEqual(run("aif 0 then it + 1 else it + 1 end"), 1)
self.assertEqual(run("aif 0 then 5 elif 6 then it + 1 end"), 7)
self.assertEqual(run("aif 0 then 5 elif 0 then it + 1 end"), None)
self.assertEqual(run("aif 0 then 5 elif 6 then it + 1 else it + 1 end"), 7)
self.assertEqual(run("aif 0 then 5 elif 0 then it + 1 else it + 1 end"), 1)
self.assertEqual(run("aif 0 then 5 elif 0 then 6 elif 7 then it + 1 end"), 8)
self.assertEqual(run("aif 0 then 5 elif 0 then 6 elif 0 then it + 1 end"), None)
kb84tkhrなんかちょっとやりきった感がある
マクロと継続で機能を追加してカスタム文法であたかも組み込みの機能であるかのように見せかける、というのがまあまあいい感じで実装できたんじゃなかろうか
なんでも書けるというわけではないけれど
あとやってみたいのはfuncとかifとかを上書きすること
今はreturnつきのfuncをruncっていう名前で書けるようにとかやってみたけどfuncを再定義できれば意識しなくてもreturnが使えるし
生のifはelifなしのシンプルなif ... then ... else ... endという形にしておいてelifは後付けで実装するとかしたほうがキレイな気がする
今は関数やマクロよりも先にそのへんが処理されてしまうので上書きできない
さきに関数やマクロを探してなければ生のfuncやifで処理する、というのはあるかもしれないんだけれどもifマクロを定義中にifを使う、とかやるとややこしくなりそう
組み込み関数的にifやfuncを定義できれば一番シンプルな気がするんだけどいまのところうまくいくイメージがわいてない
生のifはbuiltin-ifとかいう名前にしてしまうというのもアリだが
それでいいのかもねー
kb84tkhrあと演算子のカスタマイズがあるか！
既存の演算子の多くは組み込み関数に翻訳されるので組み込み関数の方を上書きしてやればカスタマイズはできる。
add := sub; print(5 + 3)
→ 2
:=や=なんかは特殊形式なので上書きできない。
演算子の評価は完全に構文解析にハードコーディングされているのであたらしい演算子は追加できない。
Prattパーザだったら構文規則をデータで持ってるので演算子の方はなんとかなるのかな
読み飛ばしてたけどやってみてもいいかもしれない