Open21

トイ言語実験日記６（toigでeval）

kb84tkhrkb84tkhr

ifを作る
型を判定する組み込み関数がほしい

ToigStrで文字列を表すことになったので、isinstance(..., str)では正しく判定できなくなっている

ici.py
_builtins = {
    ...
    "is_bool": lambda _, s: s.append(type(s.pop()) is bool),
    "is_int": lambda _, s: s.append(type(s.pop()) is int),
    "is_str": lambda _, s: s.append(type(s.pop()) is ToigStr),
    "is_name": lambda _, s: s.append(type(s.pop()) is str),
    ...
}
stm.py
_builtins = {
    ...
    "is_bool": lambda args: type(args[0]) is bool,
    "is_int": lambda args: type(args[0]) is int,
    "is_str": lambda args: type(args[0]) is ToigStr,
    "is_name": lambda args: type(args[0]) is str,
    ...
}

Parserでは、ToigStrを先に処理しておかないといけなかった
そうでないとToigStr("If")でもcase "if":にマッチしてしまう
普通にバグでしたすみません

parser.py
    def _primary(self):
        match self._current_token:
            case ToigStr(s):
                return self._advance()
            ...
            case "if":
                self._advance(); return self._if()
            ...
        return self._advance()

本体
matchも分割代入もないのでちょっと泥臭いが普通に書ける

test_eval.py
        self.go("""
            eval := func (expr) do
                if expr == None then
                    None
                elif is_bool(expr) or is_int(expr) or is_str(expr) then
                    expr
                elif expr[0] == 'if' then
                    if eval(expr[1]) then eval(expr[2]) else eval(expr[3]) end
                else
                    error('Unexpected expression: ', expr)
                end
            end
        """)

        ...

        assert self.go("eval(['if', True, 5, 6])") == 5
        assert self.go("eval(['if', False, 5, 6])") == 6

        with pytest.raises(AssertionError):
            self.go("eval(['unexpected case'])")

https://github.com/koba925/toig/commit/3d9bce1ba4b0c4ec61898633d974515520342a95

kb84tkhrkb84tkhr

defineとgetを作るよ
辞書がないので配列使って辞書もどきを作るよ
とりあえずスコープはなしで

test_eval.py
        self.go("""
            define := runc(env, name, val) do
                for p in env do
                    if p[0] == name then p[1] = val; return(val) end
                end;
                append(env, [name, val]);
                return(val)
            end
        """)

        self.go("""
            get := runc(env, name) do
                for p in env do
                    if p[0] == name then return(p[1]) end
                end;
                error('Not found:', name)
            end
        """)

配列に破壊的に要素を付け足す関数がほしいけどなかった
pushで破壊的に追加しようかなあと思ったけど
突然Pythonのやり方を尊重してappendを破壊的変更に使うことに変えた
pushとpopは非破壊的に

stm.py
_builtins = {
    ...
    "append": lambda args: args[0].append(args[1]),
    ...
ici.py
def _append(_, s):
    arr = s.pop(); val = s.pop()
    arr.append(val)
    s.append(None)

_builtins = {
    ...
    "append": _append,
    ...
}
stdlib.py
        self._go("push := func (l, a) do l + [a] end")
        self._go("pop := func (l) do l[:-1] end")

あとzipを作ったりruncをstdlibに格上げしたりしている
unfoldを知ったので使ってみたいお年ごろ > zip

stdlib.py
        self._go("""
            zip := func (l1, l2) do
                unfoldl(
                    [l1, l2],
                    func (s) do first(s) == [] or last(s) == [] end,
                    func (s) do [first(first(s)), first(last(s))] end,
                    func (s) do [rest(first(s)), rest(last(s))] end
                )
            end
        """)

        self._go("""
            defmacro _runc (params, body) do quasiquote
                func (unquote_splicing(rest(params))) do
                    letcc return do unquote(body) end
                end
            end end

            #rule [runc, _runc, PARAMS, do, EXPR, end]
        """)

これだけお膳立てを整えてやっとeval

test_eval.py
        self.go("""
            _eval := func (expr, env) do
                print('eval', expr);
                if expr == None then
                    None
                elif is_bool(expr) or is_int(expr) then
                    expr
                elif is_str(expr) then
                    get(env, expr)
                elif expr[0] == 'define' then
                    define(env, expr[1], _eval(expr[2], env))
                elif expr[0] == 'if' then
                    if _eval(expr[1], env) then
                        _eval(expr[2], env)
                    else
                        _eval(expr[3], env)
                    end
                else
                    error('Unexpected expression: ', expr)
                end
            end
        """)

        self.go("""
            global_env := [];
            eval := func (expr) do _eval(expr, global_env) end
        """)

        assert self.go("eval(['define', 'a', 5])") == 5
        assert self.go("eval('a')") == 5
        assert self.go("eval(['define', 'b', 6])") == 6
        assert self.go("eval('b')") == 6
        assert self.go("eval(['define', 'b', 7])") == 7
        assert self.go("eval('b')") == 7

        with pytest.raises(AssertionError):
            self.go("eval('c')")

https://github.com/koba925/toig/commit/24e600304a4ebd6b7d570eeb4062880ed86e3471

kb84tkhrkb84tkhr

テストメソッドを分割した

test_eval.py
class TestEval(BaseTest):
    @pytest.fixture(autouse=True)
    def setup_env(self):
        self.go("""
            define := runc (env, name, val) do
                ...
            end
        """)

        self.go("""
            get := runc (env, name) do
                ...
            end
        """)

        self.go("""
            _eval := func (expr, env) do
                ...
            end
        """)

        self.go("""
            global_env := [];
            eval := func (expr) do _eval(expr, global_env) end
        """)

    def test_primary(self):
        assert self.go("eval(None)") == None
        ...

    def test_if(self):
        assert self.go("eval(['if', True, 5, 6])") == 5
        ...

    def test_define(self):
        assert self.go("eval(['define', 'a', 5])") == 5
        ...

setup_env()の大部分は１度だけ実行すればいいんだけれども
scope="class"にするとself.iにアクセスする方法が見つからなかったので
テストごとに実行するようにしている
なんとかならないか

https://github.com/koba925/toig/commit/dca84755fb34add1ebb272f4e4238d2b970dcc85

kb84tkhrkb84tkhr

scope="class"にするとself.iにアクセスする方法が見つからなかった

このへんが我ながらうさんくさいんだよなー
これでちゃんと動くのか少々心配だけど動いてるって状態

test_commons.py
class BaseTest:
    i: ICI | STM

    @pytest.fixture(autouse=True)
    def set_interpreter(self, request):
        request.cls.i = request.param()

    def parsed(self, src):
        return self.i.parse(src)

メソッドごとにInterpreterを生成するならこれでいいんだよな

class BaseTest:
    @pytest.fixture(autouse=True)
    def set_interpreter(self, request):
        self.i = request.param()

    def parsed(self, src):
        return self.i.parse(src)

なんでこうしなかったんだっけ？
Interpreterを毎回つくるのがもったいないと思ったのかな？
うさんくさいところもないしこっちでいくか
普通にテスト通るし

https://github.com/koba925/toig/commit/99322b27fadd3fdf79d58c54038a6c36f951c317

kb84tkhrkb84tkhr

組み込み関数
global_envで組み込み関数を入れておきelseは全部関数として扱う

    def setup_eval(self):

        self.go("""
            _eval := func (expr, env) do
                ...
                else
                    op_val := _eval(expr[0], env);
                    args_val := map(expr[1:], func (arg) do _eval(arg, env) end);
                    op_val(args_val)
                end
            end
        """)

        self.go("""
            global_env := [
                ['add', func (args) do args[0] + args[1] end],
                ['sub', func (args) do args[0] - args[1] end],
                ['equal', func (args) do args[0] == args[1] end]
            ];
            eval := func (expr) do _eval(expr, global_env) end
        """)

    def test_builtins(self):
        assert self.go("eval(['add', 5, 6])") == 11
        assert self.go("eval(['sub', 11, 6])") == 5
        assert self.go("eval(['equal', 5, 5])") == True
        assert self.go("eval(['equal', 5, 6])") == False

https://github.com/koba925/toig/commit/113f734103dc1001894b5a0ea18e860d5323c090

kb84tkhrkb84tkhr

じゃユーザ定義関数
環境にスコープを導入しないと
[親環境, [[名前, 値], [名前, 値], ...]]という形で表すことにする
global_envは親環境をNoneとしてこう

global_env := [None, [
    ['add', ['primitive', func (args) do args[0] + args[1] end]],
    ['sub', ['primitive', func (args) do args[0] - args[1] end]],
    ['equal', ['primitive', func (args) do args[0] == args[1] end]]
]];
eval := func (expr) do _eval(expr, global_env) end

そうそう
組み込み関数をis_callableで見分ける、というわけにいかないので
目印をつけて['primitive', 関数本体]と表すことにした

defineはenv[1]を見るように変えて、

define := runc (env, name, val) do
    for p in env[1] do
        if p[0] == name then p[1] = val; return(val) end
    end;
    append(env[1], [name, val]);
    return(val)
end

getはenv[1]に名前が見つからなかったらenv[0]で探すようにする
env[0]がNoneだったら見つからなかったということでエラー

get := runc (env, name) do
    for p in env[1] do
        if p[0] == name then return(p[1]) end
    end;
    if env[0] != None then
        get(env[0], name)
    else
        error('Not found:', name)
    end
end

funcを作るところとapplyを呼ぶところ

_eval := func (expr, env) do
    ...
    elif expr[0] == 'func' then
        ['closure', expr[1], expr[2], env]
    ...
    else
        op_val := _eval(expr[0], env);
        args_val := map(expr[1:], func (arg) do _eval(arg, env) end);
        apply(op_val, args_val)
    end
end
kb84tkhrkb84tkhr

なんか投稿しようとしたらWAFが文句言ってきたので二つに分けた

apply
やってることはいつもと同じ
[op_val[3], []]で新しいスコープを作っている

body := op_val[3]とかってやりながら書いた方が可読性が上がるけどまあいいやという気になっている
matchや分割代入があればそれでやるんだけど

apply := func (op_val, args_val) do
    if op_val[0] == 'primitive' then
        op_val[1](args_val)
    else
        env := [op_val[3], []];
        for name_val in zip(op_val[1], args_val) do
            define(env, name_val[0], name_val[1])
        end;
        _eval(op_val[2], env)
    end
end

テスト

    def test_function(self):
        assert self.go("eval([['func', ['n'], ['add', 'n', 5]], 6])") == 11

    def test_fib(self):
        self.go("""eval(
            ['define', 'fib', ['func', ['n'],
                ['if', ['equal', 'n', 0], 0,
                ['if', ['equal', 'n', 1], 1,
                ['add', ['fib', ['sub', 'n', 1]], ['fib', ['sub', 'n', 2]]]]]]]
        )""")
        assert self.go("eval(['fib', 0])") == 0
        assert self.go("eval(['fib', 1])") == 1
        assert self.go("eval(['fib', 2])") == 1
        assert self.go("eval(['fib', 3])") == 2
        assert self.go("eval(['fib', 10])") == 55

    def test_adder(self):
        self.go("""eval(
            ['define', 'make_adder', ['func', ['n'],
                ['func', ['m'], ['add', 'n', 'm']]
            ]]
        )""")
        assert self.go("eval([['make_adder', 5], 6])") == 11

おっそ！
fibのテストだけで4秒かかっている
iciのfibで1秒、stmのfibで4秒て感じ

['fib', 6]でがまんしとこ
これなら合わせて1秒

https://github.com/koba925/toig/commit/d2b385abf72afd3971326800094151f62dc8c5b7

kb84tkhrkb84tkhr

これくらいでもevalが実装できました、て言えそうな気もするけどカウンター作れるところまでやっとこ

assignとseqを作って

assign := runc (env, name, val) do
    for p in env[1] do
        if p[0] == name then p[1] = val; return(val) end
    end;
    if env[0] != None then
        assign(env[0], name, val)
    else
        error('Not found:', name)
    end
end

_eval := func (expr, env) do
    ...
    elif expr[0] == 'assign' then
        assign(env, expr[1], _eval(expr[2], env))
    elif expr[0] == 'seq' then
        val := None;
        for e in expr[1:] do
            val = _eval(e, env)
        end;
        val
    ...
end

カウンター

    def test_counter(self):
        self.go("""eval(['seq',
            ['define', 'make_counter', ['func', [], ['seq',
                ['define', 'c', 0],
                ['func', [], ['assign', 'c', ['add', 'c', 1]]]
            ]]],
            ['define', 'counter1', ['make_counter']],
            ['define', 'counter2', ['make_counter']]
        ])""")

        assert self.go("eval(['counter1'])") == 1
        assert self.go("eval(['counter1'])") == 2
        assert self.go("eval(['counter2'])") == 1
        assert self.go("eval(['counter2'])") == 2
        assert self.go("eval(['counter1'])") == 3
        assert self.go("eval(['counter2'])") == 3

ここらへんまで動けばstmもiciもだいたいちゃんと動くって言っちゃってよいのでは

https://github.com/koba925/toig/commit/52098cf63002bde2205a4b949b8994481cef714d

kb84tkhrkb84tkhr

文字列と配列をちょっと扱えるようにするとevalが作れるわけだから
最小evalにもうちょっと機能を付け加えるだけでevalでevalが書けそうだな
いや書けるに決まっているんだけど
現実味というか

kb84tkhrkb84tkhr

構文解析をつける直前の main くらいから始めるとちょうどいまじっそうしたくらいのところ

https://github.com/koba925/toig/commit/7b8a63df83074706aae41c34ca6f7f7c950c5e01

これに必要な機能だけ追加していこう
ここまでやってきたことをなぞりながら進めればいいだろう

    i.go(["define", "eval", ["func", ["expr"], "expr"]])

    assert i.go(["eval", None]) == None
    assert i.go(["eval", True]) == True
    assert i.go(["eval", False]) == False
    assert i.go(["eval", 5]) == 5

https://github.com/koba925/toig/compare/main...eval_on_eval

kb84tkhrkb84tkhr

次はifを作る
まず親evalで文字列と配列が扱えるようにしないと

文字列を評価するところ

class ToigStr(str):
    pass

class Evaluator:
    def eval(self, expr, env):
        match expr:
            ...
            case bool(val) | int(val) | ToigStr(val):
                return val
            ...

文字列・配列を扱うための組み込み関数を追加
たぶんこれくらいで足りるはず
忘れてたら都度追加する

class Evaluator:
    def _apply(self, f_val, args_val):
        if callable(f_val):
            return f_val(args_val)

# Builtin Functions

def _set_at(args):
    args[0][args[1]] = args[2]
    return args[2]

def _slice(args):
    arr, start, end, step = args
    return arr[slice(start, end, step)]

def _set_slice(args):
    arr, start, end, step, val = args
    arr[start:end:step] = val
    return val

def _error(args):
    assert False, f"{' '.join(map(str, args))}"

_builtins = {
    "__builtins__": None,
    "add": lambda args: args[0] + args[1],
    "sub": lambda args: args[0] - args[1],

    "equal": lambda args: args[0] == args[1],

    "array": lambda args: args,
    "get_at": lambda args: args[0][args[1]],
    "set_at": _set_at,
    "append": lambda args: args[0].append(args[1]),
    "slice": _slice,
    "set_slice": _set_slice,

    "is_bool": lambda args: type(args[0]) is bool,
    "is_int": lambda args: type(args[0]) is int,
    "is_str": lambda args: type(args[0]) is ToigStr,
    "is_array": lambda args: type(args[0]) is list,

    "print": lambda args: print(*args),
    "error": lambda args: _error(args)
}

class BuiltIns:
    @staticmethod
    def load(env):
        for name, func in _builtins.items():
            env.define(name, func)

class Interpreter:
    def __init__(self):
        self._env = Environment()
        BuiltIns.load(self._env)
        self._env = Environment(self._env)
kb84tkhrkb84tkhr

新しいeval()
exprの型を判断して処理する
ifだけでなくquoteも追加

    i.go(["define", "eval", ["func", ["expr"],
        ["if", ["equal", "expr", None], None,
        ["if", ["is_bool", "expr"], "expr",
        ["if", ["is_int", "expr"], "expr",
        ["if", ["is_str", "expr"], "expr",
        ["seq",
            ["define", "op", ["get_at", "expr", 0]],
            ["if", ["equal", "op", ToigStr("quote")],
                ["eval", ["get_at", "expr", 1]],
            ["if", ["equal", "op", ToigStr("if")],
                ["if", ["eval", ["get_at", "expr", 1]],
                    ["eval", ["get_at", "expr", 2]],
                    ["eval", ["get_at", "expr", 3]]],
            ["error", "expr"]]]
        ]]]]]
    ]])

型の判断ではorがないのでひとつずつifで確認している

quoteはなぜ必要になるかというと
["eval", ["if", True, 5, 6]]と書くと、["if", True, 5, 6]を親evalが評価して5にしてから"eval"に渡してしまうため
ここは評価しないでそのままにしておいて、という意味で["eval", ["quote", ["if", True, 5, 6]]]と書く
assert i.go(["eval", None]) == NoneとかではNoneを親evalが評価仕様がしなかろうがNoneはNoneだったから

そのへんも含めて書き直し＆ifのテスト

    def eval(expr):
        return i.go(["eval", ["quote", expr]])

    assert eval(None) == None
    assert eval(True) == True
    assert eval(False) == False
    assert eval(5) == 5
    assert eval(ToigStr("hello")) == "hello"

    assert eval(["if", True, 5, 6]) == 5
    assert eval(["if", False, 5, 6]) == 6
    assert eval(["if", ["if", True, True, True], 5, 6]) == 5
    assert eval(["if", True, ["if", True, 5, 6], 7]) == 5
    assert eval(["if", False, 5, ["if", False, 6, 7]]) == 7

https://github.com/koba925/toig/commit/a857ea84bf5f40768c8d75225b529dcbcf468389

kb84tkhrkb84tkhr

次は変数

ところで"define"をdefineできるのか？（お前が聞くな
えーと、
書いてから考えよう

forがないので自前で再帰する

    i.go(["define", "define_", ["func", ["env", "name", "val"], ["seq",
        ["define", "_define_", ["func", ["pairs"],
            ["if", ["equal", "pairs", ["array"]],
                ["seq",
                    ["append", ["get_at", "env", 1], ["array", "name", "val"]],
                    "val"],
                ["seq",
                    ["define", "name_val", ["get_at", "pairs", 0]],
                    ["if", ["equal", ["get_at", "name_val", 0], "name"],
                        ["set_at", "name_val", 1, "val"],
                        ["_define_", ["slice", "pairs", 1, None, None]]]]]]],
        ["_define_", ["get_at", "env", 1]]
    ]]])

    i.go(["define", "assign_", ["func", ["env", "name", "val"], ["seq",
        ["define", "_assign_", ["func", ["pairs"],
            ["if", ["equal", "pairs", ["array"]],
                ["assign_", ["get_at", "env", 0], "name", "val"],
                ["seq",
                    ["define", "name_val", ["get_at", "pairs", 0]],
                    ["if", ["equal", ["get_at", "name_val", 0], "name"],
                        ["set_at", "name_val", 1, "val"],
                        ["_assign_", ["slice", "pairs", 1, None, None]]]]]]],
        ["if", ["equal", "env", None],
            ["error", "name"],
            ["_assign_", ["get_at", "env", 1]]]]]])

    i.go(["define", "get_", ["func", ["env", "name"], ["seq",
        ["define", "_get_", ["func", ["pairs"],
            ["if", ["equal", "pairs", ["array"]],
                ["get_", ["get_at", "env", 0], "name"],
                ["seq",
                    ["define", "name_val", ["get_at", "pairs", 0]],
                    ["if", ["equal", ["get_at", "name_val", 0], "name"],
                        ["get_at", "name_val", 1],
                        ["_get_", ["slice", "pairs", 1, None, None]]]]]]],
        ["if", ["equal", "env", None],
            ["error", "name"],
            ["_get_", ["get_at", "env", 1]]]]]])

関数名変えときゃいけそう
配列の操作をいちいちget_at、set_at、sliceで書くのもけっこうだな

kb84tkhrkb84tkhr

文字列型作ったらこれでeval()が作れるんじゃねって気がしてきた

ただの錯覚でした
ほんとうにありがとうございました

本当に顧客が必要としていたもの：quote

というわけでclass ToigStrは抹殺

で、is_nameはマクロがないと定義できないので、「配列でなくてNoneでもboolでもintでもないもの」を名前と判断する
あとはdefineとassignの処理を入れて

    i.go(["define", "eval", ["func", ["expr", "env"],
        ["if", ["not", ["is_array", "expr"]],
            ["if", ["equal", "expr", None], None,
            ["if", ["is_bool", "expr"], "expr",
            ["if", ["is_int", "expr"], "expr",
            ["get_", "env", "expr"]]]],
            ["seq",
                ["define", "op", ["get_at", "expr", 0]],
                ["if", ["equal", "op", ["quote","quote"]],
                    ["get_at", "expr", 1],
                ["if", ["equal", "op", ["quote", "define"]],
                    ["define_", "env",
                        ["get_at", "expr", 1],
                        ["eval", ["get_at", "expr", 2], "env"]],
                ["if", ["equal", "op", ["quote", "assign"]],
                    ["assign_", "env",
                        ["get_at", "expr", 1],
                        ["eval", ["get_at", "expr", 2], "env"]],
                ["if", ["equal", "op", ["quote", "if"]],
                    ["if", ["eval", ["get_at", "expr", 1], "env"],
                        ["eval", ["get_at", "expr", 2], "env"],
                        ["eval", ["get_at", "expr", 3], "env"]],
                ["error", "expr"]]]]]
            ]
        ]
    ]])

テスト
スコープのテストもいまやっておく

    i.go(["define", "global_env", ["array", None, ["array"]]])

    def eval(expr):
        return i.go(["eval", ["quote", expr], "global_env"])

    def fails(expr):
        try: eval(expr)
        except AssertionError: return True
        else: return False

    assert eval(None) == None
    assert eval(True) == True
    assert eval(False) == False
    assert eval(5) == 5

    assert eval(["if", True, 5, 6]) == 5
    assert eval(["if", False, 5, 6]) == 6
    assert eval(["if", ["if", True, True, True], 5, 6]) == 5
    assert eval(["if", True, ["if", True, 5, 6], 7]) == 5
    assert eval(["if", False, 5, ["if", False, 6, 7]]) == 7

    assert eval(["define", "a", 5]) == 5
    assert eval(["define", "b", 6]) == 6
    assert eval("a") == 5
    assert eval("b") == 6

    assert eval(["define", "b", 7]) == 7
    assert eval("a") == 5
    assert eval("b") == 7

    i.go(["define", "global_env", ["array", "global_env", ["array"]]])

    assert eval(["define", "a", 8]) == 8
    assert eval("a") == 8
    assert eval("b") == 7

    assert eval(["assign", "a", 9]) == 9
    assert eval("a") == 9
    assert eval("b") == 7

    assert eval(["assign", "b", 10]) == 10
    assert eval("a") == 9
    assert eval("b") == 10

    assert fails(["assign", "c", 11])
    assert fails("c")

    i.go(["define", "global_env", ["get_at", "global_env", 0]])
    
    assert eval("a") == 5
    assert eval("b") == 10

https://github.com/koba925/toig/commit/ca0f317d050a1ce1d71a771eb4db90f005645319

kb84tkhrkb84tkhr

組み込み関数・ユーザ関数・seqを一気に実装

まるごと

    i.go(["define", "first", ["func", ["l"], ["get_at", "l", 0]]])
    i.go(["define", "last", ["func", ["l"], ["get_at", "l", -1]]])
    i.go(["define", "rest", ["func", ["l"], ["slice", "l", 1, None, None]]])

    i.go(["define", "map", ["func", ["l", "f"],
        ["if", ["equal", "l", ["array"]],
            ["array"],
            ["add",
                ["array", ["f", ["first", "l"]]],
                ["map", ["slice", "l", 1, None, None], "f"]]]]])

    i.go(["define", "define_", ["func", ["env", "name", "val"], ["seq",
        ["define", "_define_", ["func", ["pairs"],
            ["if", ["equal", "pairs", ["array"]],
                ["seq",
                    ["append", ["last", "env"], ["array", "name", "val"]],
                    "val"],
                ["seq",
                    ["define", "name_val", ["first", "pairs"]],
                    ["if", ["equal", ["first", "name_val"], "name"],
                        ["set_at", "name_val", 1, "val"],
                        ["_define_", ["slice", "pairs", 1, None, None]]]]]]],
        ["_define_", ["last", "env", 1]]]]])

    i.go(["define", "assign_", ["func", ["env", "name", "val"], ["seq",
        ["define", "_assign_", ["func", ["pairs"],
            ["if", ["equal", "pairs", ["array"]],
                ["assign_", ["first", "env"], "name", "val"],
                ["seq",
                    ["define", "name_val", ["first", "pairs"]],
                    ["if", ["equal", ["first", "name_val"], "name"],
                        ["set_at", "name_val", 1, "val"],
                        ["_assign_", ["rest", "pairs"]]]]]]],
        ["if", ["equal", "env", None],
            ["error", "name"],
            ["_assign_", ["last", "env"]]]]]])

    i.go(["define", "get_", ["func", ["env", "name"], ["seq",
        ["define", "_get_", ["func", ["pairs"],
            ["if", ["equal", "pairs", ["array"]],
                ["get_", ["first", "env"], "name"],
                ["seq",
                    ["define", "name_val", ["first", "pairs"]],
                    ["if", ["equal", ["first", "name_val"], "name"],
                        ["last", "name_val"],
                        ["_get_", ["rest", "pairs"]]]]]]],
        ["if", ["equal", "env", None],
            ["error", "name"],
            ["_get_", ["last", "env"]]]]]])

    i.go(["define", "eval", ["func", ["expr", "env"],
        ["if", ["not", ["is_array", "expr"]],
            ["if", ["equal", "expr", None], None,
            ["if", ["is_bool", "expr"], "expr",
            ["if", ["is_int", "expr"], "expr",
            ["get_", "env", "expr"]]]],
            ["seq",
                ["define", "op", ["first", "expr"]],
                ["if", ["equal", "op", ["quote","func"]],
                    ["array", ["quote", "closure"],
                        ["get_at", "expr", 1], ["get_at", "expr", 2], "env"],
                ["if", ["equal", "op", ["quote", "quote"]],
                    ["get_at", "expr", 1],
                ["if", ["equal", "op", ["quote", "define"]],
                    ["define_", "env",
                        ["get_at", "expr", 1],
                        ["eval", ["get_at", "expr", 2], "env"]],
                ["if", ["equal", "op", ["quote", "assign"]],
                    ["assign_", "env",
                        ["get_at", "expr", 1],
                        ["eval", ["get_at", "expr", 2], "env"]],
                ["if", ["equal", "op", ["quote", "seq"]],
                    ["eval_seq", ["rest", "expr"], "env", None],
                ["if", ["equal", "op", ["quote", "if"]],
                    ["if", ["eval", ["get_at", "expr", 1], "env"],
                        ["eval", ["get_at", "expr", 2], "env"],
                        ["eval", ["get_at", "expr", 3], "env"]],
                ["seq",
                    ["define", "op_val", ["eval", "op", "env"]],
                    ["define", "args_val", ["map",
                        ["rest", "expr"],
                        ["func", ["arg"], ["eval", "arg", "env"]]]],
                    ["apply", "op_val", "args_val"]]]]]]]]]]]])

    i.go(["define", "eval_seq", ["func", ["exprs", "env", "result"],
        ["if", ["equal", "exprs", ["array"]],
            "result",
            ["eval_seq", ["rest", "exprs"], "env",
                ["eval", ["first", "exprs"], "env"]]]]])

    i.go(["define", "apply", ["func", ["op_val", "args_val"],
        ["if", ["equal", ["first", "op_val"], ["quote", "primitive"]],
            [["last", "op_val"], "args_val"],
            ["seq",
                ["define", "env", ["array", ["get_at", "op_val", 3], ["array"]]],
                ["set_params", "env", ["get_at", "op_val", 1], "args_val"],
                ["eval", ["get_at", "op_val", 2], "env"]]]]])

    i.go(["define", "set_params", ["func", ["env", "params", "args"],
        ["if", ["equal", "params", ["array"]], None,
            ["seq",
                ["define_", "env", ["first", "params"], ["first", "args"]],
                ["set_params", "env", ["rest", "params"], ["rest", "args"]]]]]])

    i.go(["define", "global_env", ["array", None, ["array",
        ["array", ["quote", "add"], ["array", ["quote", "primitive"],
            ["func", ["args"], ["add",
                ["get_at", "args", 0], ["get_at", "args", 1]]]]],
        ["array", ["quote", "sub"], ["array", ["quote", "primitive"],
            ["func", ["args"], ["sub",
                ["get_at", "args", 0], ["get_at", "args", 1]]]]],
        ["array", ["quote", "equal"], ["array", ["quote", "primitive"],
            ["func", ["args"], ["equal",
                ["get_at", "args", 0], ["get_at", "args", 1]]]]],
    ]]])

いつものひとたちが動いた

    eval(["define", "fib", ["func", ["n"],
        ["if", ["equal", "n", 0], 0,
        ["if", ["equal", "n", 1], 1,
        ["add", ["fib", ["sub", "n", 1]], ["fib", ["sub", "n", 2]]]]]]])

    assert eval(["fib", 0]) == 0
    assert eval(["fib", 1]) == 1
    assert eval(["fib", 2]) == 1
    assert eval(["fib", 3]) == 2
    assert eval(["fib", 6]) == 8

    eval(["define", "make_adder",
        ["func", ["n"], ["func", ["m"], ["add", "n", "m"]]]])
    assert eval([["make_adder", 5], 6]) == 11

    eval(["seq",
        ["define", "make_counter", ["func", [], ["seq",
            ["define", "c", 0],
            ["func", [], ["assign", "c", ["add", "c", 1]]]
        ]]],
        ["define", "counter1", ["make_counter"]],
        ["define", "counter2", ["make_counter"]]
    ])

    assert eval(["counter1"]) == 1
    assert eval(["counter1"]) == 2
    assert eval(["counter2"]) == 1
    assert eval(["counter2"]) == 2
    assert eval(["counter1"]) == 3
    assert eval(["counter2"]) == 3

https://github.com/koba925/toig/commit/3e871b09319f98e4ba406d864ae45e195078c174

kb84tkhrkb84tkhr

便宜上いままでひとつずつ実行していたevalを定義する式をseqで全部ひとつにまとめる

    DEFINE_EVAL = ["seq",
        ["define", "first", ["func", ["l"], ["get_at", "l", 0]]],
        ["define", "last", ["func", ["l"], ["get_at", "l", -1]]],
        ...
        ["define", "eval", ["func", ["expr"], ["_eval", "expr", "global_env"]]]
    ]

それを使ってevalを定義する

    i.go(DEFINE_EVAL)

    def eval(expr):
        return i.go(["eval", ["quote", expr]])

    assert eval(None) == None
    assert eval(True) == True
    ...

そのevalとevalを定義する式を使ってevalを定義する
なにを言ってるかわからねーと思うが（以下略

    eval(DEFINE_EVAL)

evalで動かしたevalでfibを動かす

    eval(["eval", ["quote",
        ["define", "fib", ["func", ["n"],
            ["if", ["equal", "n", 0], 0,
            ["if", ["equal", "n", 1], 1,
            ["add", ["fib", ["sub", "n", 1]], ["fib", ["sub", "n", 2]]]]]]]]])

    assert eval(["eval", ["quote",["fib", 0]]]) == 0
    assert eval(["eval", ["quote",["fib", 1]]]) == 1
    assert eval(["eval", ["quote",["fib", 2]]]) == 1
    assert eval(["eval", ["quote",["fib", 3]]]) == 2

動いた！

といっても超遅くてこれだけで10秒くらいかかる
fib(6)とかまったくやる気しない
その気になればいくらでもevalを重ねていくこともできるはずけど同様

遅いけどevalでevalが書けたというのは自分の中では大きいマイルストーン
おめでとう俺

https://github.com/koba925/toig/commit/013f5d446d4414a3d4f46cdc7adfd95a42ea455e

kb84tkhrkb84tkhr

なんて書くとさらっと動いたように見えるかもしれないけれども艱難辛苦を乗り越えてここまでやってきました（大げさ
デバッグを支援してくれるような機能がほぼないし変数の値を見ようにも
デバッガでenvの中を見てenvを探しその中で目的の変数を探す、みたいなことをやらなきゃいけなくて大変
printだけがお友達
だけどprintもちゃんと動くか保証の限りではない
という状況で、引数ひとつ書き忘れてたとかくらいでも難航

なにを言ってるかわからねーと思うが（以下略

あらためてまとめ

pythonでevalを書く
pythonで書いたevalでevalを書く
pythonで書いたevalで書いたevalでevalを実行

Evaluator().eval(["eval", ["quote", ["eval", ["quote",["fib", 3]]]]])が動くようになりました、って書いたらわかりやすいかな（そうでもない

Evaluator().eval(["eval", ["quote", ["eval", ["quote",["fib", 3]]]]])
----------------   -----             ------
Pythonで書いたeval  ↑                 ↑             
                   Pythonで書いたevalで書いたeval
                                     Pythonで書いたevalで書いたevalで書いたeval

ふたつめとみっつめは全く同じevalってところがミソ
いろんなテストにもなっているという安心感

kb84tkhrkb84tkhr

toigでevalを書き、evalでevalを書いたら次は

toigでtoigを書く、かなあ
最後までやるとマクロやらカスタムルールやら継続やら入ってくるし道のりは長そうだが
救いはtoigで書いたしくみを流用できるかもというところ

やってみるか

文字列関連でもう少し組み込み関数がほしくなるかな？どうかな？

kb84tkhrkb84tkhr

test_eval.pyの名前をtest_toig_on_toig.pyに変えてと

classで表現してるところはどうしようか
いつぞややってみたようにクロージャで書くかな

class BaseToigOnToigTest(BaseTest):
    @pytest.fixture(autouse=True)
    def setup_eval(self):

        # Utilities

        self.go("""
            EOL := '
';
            is_space := func (c) do c == ' ' or c == EOL end;
            is_digit := func (c) do '0' <= c and c <= '9' end;
            is_alphabet := func (c) do
                ('A' <= c and c <= 'Z') or  ('a' <= c and c <= 'z')
            end
        """)

        self.go("""
            is_name_first := func (c) do is_alphabet(c) or c == '_' end;
            is_name_rest := func (c) do
                is_name_first(c) or is_digit(c)
            end
        """)

        self.go("""
            contains := runc (a, l) do
                for e in l do
                    if a == e then return(True) end
                end;
                False
            end
        """)

        # Scanner

        self.go("""
            scan := func (src) do
                pos := 0;
                token := '';

                advance := func () do pos = pos + 1 end;

                current_char := func () do
                    if pos < len(src) then src[pos] else '$EOF' end
                end;

                append_char := func () do
                    token = token + current_char();
                    advance()
                end;

                word := func (is_rest) do
                    append_char();
                    while is_rest(current_char()) do append_char() end
                end;

                name := func () do
                    word(is_name_rest);
                    if token == 'None' then None
                    elif token == 'True' then True
                    elif token == 'False' then False
                    else token end
                end;

                get_token := func () do
                    token = '';

                    while is_space(current_char()) do advance() end;

                    if current_char() == '$EOF' then '$EOF'
                    elif is_name_first(current_char()) then
                        name()
                    elif is_digit(current_char()) then
                        word(is_digit);
                        to_int(token)
                    else error(c) end
                end;

                tokens := [];
                while True do
                    token :=get_token();
                    append(tokens, token);
                    if token == '$EOF' then break() end
                end;
                tokens
            end
        """)

        # Parser

        self.go("""
            parse := func (tokens) do
                pos := 0;

                current_token := func () do tokens[pos] end;
                advance := func() do
                    pos = pos + 1;
                    tokens[pos - 1]
                end;

                primary := func () do
                    advance()
                end;

                expression := func () do
                    primary()
                end;

                expr := expression();
                if current_token() != '$EOF' then
                    error(current_token())
                end;
                expr
            end
        """)

        # Interpreter

        self.go("""
            go := func (src) do eval(parse(scan(src))) end
        """)

文字列関連でもう少し組み込み関数がほしくなるかな？どうかな？

to_int()が必要になったのでstm、iciとも追加した

これだけのために意外とたくさん書かないといけなかった
ヘルパー関数とかも多いからまあそんなもんか

class TestInterpreter(BaseToigOnToigTest):
    def test_primary(self):
        assert self.go("go('None')") == None
        assert self.go("go('True')") == True
        assert self.go("go('False')") == False
        assert self.go("go('5')") == 5

https://github.com/koba925/toig/commit/7338bc3a3edae0b83655dbabcd479eec8197db95