PythonでLispを実装した (evalつき)
1 like1,706 views
Pythonのリスト内包表記でLispを実装したことを、前後編に分けて話しました@lisp meetup #64
![リスト内包表記で順次処理
or や and の短絡評価を利用する
# printの返り値はNone
>>> [print("hello") or print("bye") for n in [None]]
hello
bye
[None]
値がある関数の場合は…
>>> [(str(42) and None) or print('hi') for n in [None]]
hi
[None]](https://image.slidesharecdn.com/2018-05-31implementing-lisp-with-python-180531150359/85/Python-Lisp-eval-8-320.jpg)
![リスト内包表記で代入
リストのリストを操作する場合、 n によって空リストを参照可能
>>> [lis.append(n) or lis for n in range(3)
... for lis in [[]]]
[[0], [1], [2]]
ちなみにこのforを逆にすると、こうなる
>>> [lis.append(n) or lis for lis in [[]]
... for n in range(3)]
[[0, 1, 2], [0, 1, 2], [0, 1, 2]]
内側の for が外側のループのローカル変数になるっぽい
lambda 式を代入（名前付け）することで、再帰できます](https://image.slidesharecdn.com/2018-05-31implementing-lisp-with-python-180531150359/85/Python-Lisp-eval-9-320.jpg)
![リスト内包表記で条件分岐
いくつか方法がある:
>>> [print(n) for n in range(3) if n % 2 == 0]
0
2
[None, None]
>>> [print(n) if n % 2 == 0 else 'w' for n in range(3)]
0
2
[None, 'w', None]
後者のほうが、複数の if を連ねて switch するのに便利](https://image.slidesharecdn.com/2018-05-31implementing-lisp-with-python-180531150359/85/Python-Lisp-eval-10-320.jpg)
![リスト内包表記で（無限）ループ
リスト内包表記のイテレーション対象は
実はループ内で更新できるのだ！！！！
>>> [e.append(None) for lis in [[None]] for e in lis]
for e in lis で lis の中のリストをイテレートしているのに、
e.append(None) でイテーレション対象が増えていく…！！](https://image.slidesharecdn.com/2018-05-31implementing-lisp-with-python-180531150359/85/Python-Lisp-eval-11-320.jpg)
![LISC (コード)
[[b.append(l_read(_make_stream(input('> ')))) or
(print(l_print(l_eval(b[-1], _env))) if b[-1] is not None else
b.append('')) for b in [[None]] for a in b] for _read_char in
[lambda stream: [(stream.pop() and None) or
stream.append(-1) or (None, stream) if pos >= len(stream[0])
else (None, stream) if pos == -1 else c.append(stream[0][pos])
or (stream.pop() and None) or stream.append(pos+1) or (c[0],
stream) for c in [[]] for pos in [stream[1]]][0]] for _peek_char in
[lambda stream: [(None, stream) if pos >= len(stream[0]) else
(None, stream) if pos == -1 else (stream[0][pos], stream) for
pos in [stream[1]]][0]] for _make_stream in [lambda s: [s, 0]]
for _read_list in [lambda stream: [[(_read_char(stream) and
None) or loop[1:] if _peek_char(stream)[0] == ')' else loop[1:] if
_peek_char(stream)[0] == None else loop.a ...
以下省略](https://image.slidesharecdn.com/2018-05-31implementing-lisp-with-python-180531150359/85/Python-Lisp-eval-15-320.jpg)
![つらかったこと
リーダの実装とリスト内包表記化を同時にやったらハマった
文字列 -> (結果, 読んだ文字数) の形にしようとした
ストリーム(パーサ状態を分離)にしたら簡単になった
デバッグがめっちゃつらい
そういえば難読化系の手法だった
エラー表示も役に立たない
>>> [[b.append(l_read(_make_stream(input('> ')))) or
(print(l_print(l_eval(b[-1], _env))) if b[-1] is not None
else b.append('')) for b in [[None]] for a in b] for _read＿cha
in [lambda stream: [(stream.pop() and None) or stream.append(
...
^ # これはどこを指しているんだ](https://image.slidesharecdn.com/2018-05-31implementing-lisp-with-python-180531150359/85/Python-Lisp-eval-20-320.jpg)
PythonでLispを実装した (evalつき)
- 2. 導入 Pythonのリスト内包表記は便利なものです 便利すぎて、チューリング完全らしいです 出典: リスト内包表記の活用と悪用 Pythonのリスト内包表記で実装されたBrainfxxkインタプリタ
- 5. ——実际にやってみた
- 6. リスト内包表記でできること リスト上のイテレーション＆収集 = mapcar リスト要素によるフィルタ = remove-if
- 7. リスト内包表記でできること リスト上のイテレーション＆収集 リスト要素によるフィルタ 順次処理 (new!) 代入 (new!) 処理の分岐 (new!) 無限ループ (new!)
- 8. リスト内包表記で順次処理 or や and の短絡評価を利用する # printの返り値はNone >>> [print("hello") or print("bye") for n in [None]] hello bye [None] 値がある関数の場合は… >>> [(str(42) and None) or print('hi') for n in [None]] hi [None]
- 9. リスト内包表記で代入 リストのリストを操作する場合、 n によって空リストを参照可能 >>> [lis.append(n) or lis for n in range(3) ... for lis in [[]]] [[0], [1], [2]] ちなみにこのforを逆にすると、こうなる >>> [lis.append(n) or lis for lis in [[]] ... for n in range(3)] [[0, 1, 2], [0, 1, 2], [0, 1, 2]] 内側の for が外側のループのローカル変数になるっぽい lambda 式を代入（名前付け）することで、再帰できます
- 10. リスト内包表記で条件分岐 いくつか方法がある: >>> [print(n) for n in range(3) if n % 2 == 0] 0 2 [None, None] >>> [print(n) if n % 2 == 0 else 'w' for n in range(3)] 0 2 [None, 'w', None] 後者のほうが、複数の if を連ねて switch するのに便利
- 11. リスト内包表記で（無限）ループ リスト内包表記のイテレーション対象は 実はループ内で更新できるのだ！！！！ >>> [e.append(None) for lis in [[None]] for e in lis] for e in lis で lis の中のリストをイテレートしているのに、 e.append(None) でイテーレション対象が増えていく…！！
- 12. これらを応用すると… 無限ループ → REPLをつくれる 代入(名前付け) → 再帰をつくれる 条件分岐 → 文字やシンボルによる処理の分岐できる つまり…
- 14. LISC LISP = LISt Proccessing LISC = LISt Comprehension https://github.com/t-sin/lisc/blob/master/lisc.py
- 15. LISC (コード) [[b.append(l_read(_make_stream(input('> ')))) or (print(l_print(l_eval(b[-1], _env))) if b[-1] is not None else b.append('')) for b in [[None]] for a in b] for _read_char in [lambda stream: [(stream.pop() and None) or stream.append(-1) or (None, stream) if pos >= len(stream[0]) else (None, stream) if pos == -1 else c.append(stream[0][pos]) or (stream.pop() and None) or stream.append(pos+1) or (c[0], stream) for c in [[]] for pos in [stream[1]]][0]] for _peek_char in [lambda stream: [(None, stream) if pos >= len(stream[0]) else (None, stream) if pos == -1 else (stream[0][pos], stream) for pos in [stream[1]]][0]] for _make_stream in [lambda s: [s, 0]] for _read_list in [lambda stream: [[(_read_char(stream) and None) or loop[1:] if _peek_char(stream)[0] == ')' else loop[1:] if _peek_char(stream)[0] == None else loop.a ... 以下省略
- 16. 構成のしかた 1. ふつうに笔测迟丑辞苍で尝颈蝉辫を実装する 2. Lispを构成する各関数をリスト内包表记に書き換える 3. おおきな一つのリスト内包表记を组み立てる
- 18. 构成する各関数をリスト内包表记に
- 20. つらかったこと リーダの実装とリスト内包表記化を同時にやったらハマった 文字列 -> (結果, 読んだ文字数) の形にしようとした ストリーム(パーサ状態を分離)にしたら簡単になった デバッグがめっちゃつらい そういえば難読化系の手法だった エラー表示も役に立たない >>> [[b.append(l_read(_make_stream(input('> ')))) or (print(l_print(l_eval(b[-1], _env))) if b[-1] is not None else b.append('')) for b in [[None]] for a in b] for _read＿cha in [lambda stream: [(stream.pop() and None) or stream.append( ... ^ # これはどこを指しているんだ
- 22. ところで、純Lispって… コンスっぽいもの atom , eq , car , cdr , cons の関数 if , quote , lambda , define の特殊形式 これらによって eval を構成できる …とされる（Wikipedia調べ）
- 23. あれLISC…、 eval は…？ eval は、ないの？？ ないの？？？？？？？
- 25. 導入 とりあえず純Lispを実装してみたものの、 eval がない あるもの: コンスっぽいもの atom , eq , car , cdr , cons の関数 if , quote , lambda , define の特殊形式 ほんとうにこれだけで eval 実装できるのか？
- 26. ——実际にやってみた
- 27. 手元にある道具 コンスっぽいもの atom , eq , car , cdr , cons の関数 if , quote , lambda , define の特殊形式 eval がほしいというつよいきもち (new!)
- 29. 環境 (親環境 値マップ) という形式にする コンスセルを使ってハッシュテーブル的な構造が必要 ここでは連想リスト(alist)を作る (_assoc name alist) : alist内の name の値を返す (_update alist name val) : 指定したキーの値を更新した alistを返す assoc のコード (define _assoc (lambda (item lis) (if (eq lis nil) nil (if (eq (car (car lis)) item) (car lis) (_assoc item (cdr lis))))))
- 30. 基本関数 関数オブジェクトは (:lambda: 引数リスト 本体コード) にした 環境の操作関数を用いて、組み立てる (_setv name val) : グローバル環境へ代入 (_loopup name env) : 環境内を再帰的に検索 たとえば… cons のコード (_setv (quote cons) (cons (quote :lambda:) (cons (quote (a b)) (cons (lambda (ne) (cons (_lookup (quote a) ne) (_lookup (quote b) ne))) nil))))
- 31. 評価器本体 eval 式 と 現在の環境 をとって、それを評価した値を返す 引数の 式 の種類で場合分け cond がないのでネストが深くなっても負けない、泣かない たとえば… アトムだったら: nil だったら nil を返す それ以外だったら: 環境から値を探して返す 環境に値がなかったら、 :unbound: を返す というふうにする。
- 32. これが eval だ！！！
- 33. (lambda (form env) (if (atom form) (if (eq form nil) nil (if (eq form t) form (_lookup form env))) (if (eq (cdr form) nil) nil (if (eq (car form) (quote if)) (if (_eval (car (cdr form)) env) (_eval (car (cdr (cdr form))) env) (_eval (car (cdr (cdr (cdr form)))) env)) (if (eq (car form) (quote quote)) (car (cdr form)) (if (eq (car form) (quote lambda)) (cons (quote :lambda:) (cons (car (cdr form)) (cons (lambda (ne) (_eval (if (eq (car form) (quote define)) (_setv (car (cdr form)) (_eval ((lambda (fn) (if (eq fn (quote :unbound (quote :undefined-op:) ((car (cdr (cdr fn))) ( (_lookup (car form) env))))))))))
- 34. 関数オブジェクトの部分 関数オブジェクトの構造は (:lambda: 引数 本体) 愚直に cons でつくってる 本体はホスト言語の関数 指定された環境（evalが与える)で本体コードを評価する ;;; さっきのevalより抜粋 (if (eq (car form) (quote lambda)) (cons (quote :lambda:) (cons (car (cdr form)) (cons (lambda (ne) (_eval (car (cdr (cdr form))) ne)) nil))) ...
- 35. 関数呼び出しの部分 _lookup で値を取ってくる（最後の行） :unbound: だったら、未定義なのでエラー値を返す そうでなかったら、 関数の引数より新しい環境を作り ( _bind のあたり)、 本体関数にそれを渡して呼び出す ;;; さっきのevalより抜粋 ((lambda (fn) (if (eq fn (quote :unbound:)) (quote :undefined-op:) ((car (cdr (cdr fn))) (cons env (cons (_bind (car (cdr fn)) (cdr form) env) nil))))) (_lookup (car form) env))))))))))
- 36. まとめ 純Lispから eval を導出できた Lispを実装するときのアドバイス progn を実装しておくとよい print を実装しておくとよい エラー機構をちゃんとしとくとカッコいい
- 37. (おまけ)妥協点 LISCおよびにその上のLISPは、簡略化のためめんどくさいため 以下の設計上の選択妥協をした リストはPythonのリストに対応させる つまり、コンスセルなし (hoge . fuga) はつくれない エラー処理は変な値を返すだけ 未束縛シンボル: __unbound_variable__ 上位コードには値として戻ってくる