Pythonのリスト内包表記はチューリング完全だから純LISPだって実装できる

まえがき

Pythonにはリストに対する操作をさっと書ける、リスト内包表記というものが存在します。こんなやつです:

>>> [2*n for n in range(5)]
[0, 2, 4, 6, 8]
# 等価なfor文
>>> lis = []
>>> for n in range(5):
...     lis.append(2*n)
...
>>> lis
[0, 2, 4, 6, 8]

ところでこのリスト内包表記、チューリング完全だって知ってましたか？　こちらの記事でそのことが示されています。

• リスト内包表記の活用と悪用 by @KTakahiro1729

あああっ！　開かれるPythonワンライナー&難読化の世界！！　ステキすぎる！！！　超カッコいい！！！！

……でも、われわれはbrainfxxkだけで満足していてよいのでしょうか。ぼくは、もっと抽象的で、カッコよくて、とっても使いやすい枠組みがあれば、もっといろんなことができて楽しいと思うんです。

たとえば、LISPとか。
ほかには、LISPとか。

そういうことをニヤニヤと妄想してたら、リスト内包表記によるLISP実装が生えてきました。なにこれ！

できたもの

このようなものができました！

各ソースファイルは以下のようなポジションになっています:

• lisc.py: 全部を一つのリスト内包表記で書いたもの
• lisc_parts.py: 上の実装過程（パーツごとに分かれている）
• lisc_ref.py: ベースとなるLISP実装（参照実装）

妥協点注意点

動かす上では、以下の点に注意してください:

• エラーまわりの挙動
  • リスト内包表記では式しか使えないので、raiseやtry ~ except ~で例外処理ができないため
• コンスまわりの挙動
  • さっさと実装するためにLISPのリストをPythonのリストに対応させたので、コンスセルがない
  • そのせいで厳密なconsがほしいときにちょっと困るかも

純LISPって？

純LISP (pure LISP)は、LISPの父John McCarthyが1960年に論文"Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"¹で提唱した言語です。チューリング機械と等価な計算のシステムである、帰納関数を機械で実行するためのものとしてつくられました。現在では、純LISPはこの4つの要素:

• コンスと呼ばれるデータ構造と、それによって表現されたプログラム
• nilという空値／偽値
• atom、cons、car、cdr、eqの5つの基本関数
• if(あるいはcond)、quote、lambda、defineの4つの特殊形式

を持つ言語のことを指します。

上述の要素があれば、任意のLISPコードを評価（＝実行）する超循環評価器evalを構成することができます。つまり、チューリング機械に計算できるものなら何でも計算できるようになるのです。

（ちなみに、上記の要素は最小の構成ではないので、要素を削ってストイックに攻めることもできます）

Pythonのリスト内包表記でできること

先の記事にあるように、Pythonのリスト内包表記はそれだけでリスト上のループはもちろん、以下のこと

• 条件によるループ
  • 無限ループも可能
• 条件分岐
  • and/orによる方法
  • if ~ else
  • リスト内包表記のifによる方法
• 名前つき関数の定義
  • 名前つきであることで、再帰が書けます
• クラスの定義
• モジュール・ライブラリのインポート

を実現できるだけの表現力を持っています。どうやって実現するかは先の記事が詳しいのでここではあまり立ち入りません。

実装と感想

それでは実装の過程を軽く説明します。

まずはLISPの仕様を決める

まずはどんな実装にするかを考えます。まず、手間は掛けたくありません。さくっと三日くらいでつくってさくっと公開して、ツイッターなんかで場をどっかんどっかんいわせたいです。なので速度を重視しました。

LISPをつくるときの設計指針決めには、この記事が参考になります。

• LISPの処理系を作るときのコツ | Asciian

この記事によれば、レキシカルスコープよりもダイナミックスコープのほうが実装が簡単とありますので、ダイナミックスコープを選択します。ふむふむ、関数をホスト言語の関数オブジェクトにしておくとFFI実装が楽らしいです。いつか対応しよーっと。また、コンスセルを使ったリスト処理はめんどくさいのと、Pythonにはリストのスライスがあって便利なので、LISPのリストはPythonのリストに対応させます。また、シンボルはとりあえずPythonの文字列にすることにして、思考を放棄します。

というような感じで、LISPの設計方針が決まりました。ぼくはただひたすらに楽をしたいのです。

手はじめに普通に実装する

方針が立ったなら、手を動かしましょう。とはいえいきなりリスト内包表記で実装するのは自殺行為です。なんといってもリスト内包表記縛りは難読化に等しい道。デバッグが鬼のようにツラいのは目に見えるとかいうレベルではないでしょう。なのでまずはふつうに実装し、それをリスト内包表記に変換します。

ということで、ふつうに実装したものがこちらです。

「ふつうに実装するって言ったやんけ！！」とお怒りになりませぬよう。簡単な部分はリスト内包表記を視野に入れた実装になっています。あと、関数について考えるのがめんどくさかったので5つの基本関数群を特殊形式(evalが特別扱いするオペレータ)にしてしまいました。

めんどうなことはあとでなんとかすればいいのです²。

パーツに分けてリスト内包表記にする

実装の手順は以下のように行います:

1. 各パーツ (_read_list()とかl_eval())をリスト内包表記で実装
2. 各パーツをを名前つき関数定義の奥義でトップレベルのリスト内包表記内で保持
3. 各パーツを適切に呼び出してLISPのREPL(インタプリタ)を構成

まずはリスト内包表記で各パーツを実装したものがこちらです。

なんだかストリームなるものが突如増えています。

これは、パーサの各関数を文字列→(読み込んだオブジェクト, 読み込んだ文字数)の形で実現しようとして地獄を見てしまったため、ストリームを読む方式に変更したからです。

ここをちょろっとだけ説明します。

まず、ふつうに実装した版の_read_list()を見てみましょう:

def l_read_list(s):
    list = []
    i = 0
    while True:
        if i >= len(s):
            return (list, len(s))
        c = s[i]
        if c == ')':
            return (list, i+2)
        elif c == ' ':
            i += 1
        else:
            (l, n) = l_read(s[i:])
            i += n
            list.append(l)

無限ループは実装できるのですが、こういった、繰り返しの途中で後続の処理を抜ける種類のコードはリスト内包表記では書くのがつらいです。ほんとすごくつらかった。一週間くらいgithubに草も生えないほどでした。つらかった時期のコードは、こんな感じです:

# https://github.com/t-sin/lisc/commit/b4a2957a1b835bb17fc732027eeae7d58fe92505 より抽出
def read_list(s):
    print('read-list: ',s)
    return [[clis.clear() or (l,i) if c==')' else (l,i) if c==' ' else [[clis.pop(0) for j in range(n)] and l.append(ss) or (l,i+n) for ss,n in [l_read(s[i:])]][0] for l in [[]] for i,c in clis] for clis in [list(enumerate(s))]][0][0]

このコードで起こっていたエラーはたしかIndexError: list index out of rangeだったと記憶していますが、どこが悪いのか、読者のみなさんはわかりますか？　ぼくはまったくわかりませんでした。ループをむりやり抜けるため、ループの起点であるリスト(clis)をループ内で編集(clis.pop(0)とかclis.clear()とかしていて、闇がそこにあります。

読み込んだオブジェクト（パース結果）だけでなく読み込んだ文字数（パース状態）の正当性をも同時に保証することは、問題をうまく分離できていないことを意味していることに、一週間後に気付けてよかったです

ハンドアセンブル（リスト）

ともあれ、パーツは完成しました。LISPインタプリタの全体の形はだいたいこういう形

['無限ループでprint(eval(read(input()))するコード'
 for val1 in ['処理系のための変数1']
 ...
 for fn1 in [lambda x: '処理系のための関数1']
 ...]

になるので、ここまでで作ったパーツを埋め込んでいきます。アセンブラを書いたことないけど、ハンドアセンブルするときってこういう気持ちなんだろうな、と想像しながらやってみてください。typoに注意しましょう。この段階で構文エラーがでると、表示されるコードが大きすぎてどこが悪いのかわからないなんてことになります。

さて、実際にハンドアセンブルした結果が、こちらです:

[[b.append(None) or print(l_print(l_eval(l_read(_make_stream(input('> '))), env))) 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.append(l_read(stream)) for l in loop] for loop in [[None]]][0][-1]] for _read_symbol in [lambda stream: ''.join([[loop if _peek_char(stream)[0] == ')' else (_read_char(stream) and None) or loop if _peek_char(stream)[0] == ' ' else loop if _peek_char(stream)[0] == None else loop.append(_read_char(stream)[0]) for l in loop] for loop in [['']]][0][-1])] for l_read in [lambda stream: [[loop.append(None) or _read_char(stream) if _peek_char(stream)[0] == ' ' else None for l in loop] for loop in [[None]]] and ((_read_char(stream) and None) or _read_list(stream) if _peek_char(stream)[0] == '(' else _read_symbol(stream))] for env in [(None, {'nil': 'nil', 't': 't', 'atom': ('lambda', None, lambda o: 't' if type(o) is not list else 'nil'), 'cons': ('lambda', None, lambda a, b: [a, b]), 'car': ('lambda', None, lambda l: l[0]), 'cdr': ('lambda', None, lambda l: l[1:] if len(l) > 1 else 'nil'), 'eq': ('lambda', None, lambda a, b: 't' if a == b else 'nil')})] for l_eval in [lambda l, env: ('nil' if len(l) == 0 else (l_eval(l[2], env) if len(l) == 4 and l_eval(l[1], env) == 't' else l_eval(l[3], env)) if l[0] == 'if' else (l[1] if len(l) == 2 else '__quote_invalid_argument__') if l[0] == 'quote' else (('lambda', l[1], lambda new_env: l_eval(l[2], (env, new_env))) if len(l) == 3 else '__invalid_lambda_expression__') if l[0] == 'lambda' else (env[1].update({l[1]: l_eval(l[2], env)}) or (env[1][l[1]] if len(l) == 3 else '__define_invalid_argument__')) if l[0] == 'define' else [[fn[2](*eval_args) if fn[1] is None else fn[2](dict(zip(fn[1], eval_args))) if len(fn[1])+1 == len(l) else '__wrong_number_of_args__' for eval_args in [[l_eval(a, env) for a in l[1:]]]][0] if type(fn) is tuple and fn[0] == 'lambda' else '__undefined_operator__' for fn in [l_eval(l[0], env)]][0]) if type(l) is list else [search_val(env, l) for _ in [None] for search_val in [lambda e, s: [v if v else '__unbound_variable__' if e[0] is None else search_val(e[0], s) for v in [e[1].get(s, None)]][0]]][0] if type(l) is str else '__invalid_object__'] for l_print in [lambda l: '(' + ' '.join([l_print(e) for e in l]) + ')' if type(l) is list or type(l) is tuple else str(l)]]

アホか！！！！！

まとめ

こうして、人類はリスト内包表記でつくられた高等な言語を手に入れた。それは、無限に広がるリストの宇宙をconsとlambdaで縦横無尽に駆け巡る、大リスト内包表記時代の幕開けとなるのだった。

気がついたら生えてきてほしいものリスト今後の課題

• 数値とか文字列とか、ほしいなあ
• FFI(Foreign Function Interface)がわりと簡単に実行できそうなので、ほしいなあ
• Perlのppencodeみたいにリスト内包表記コンパイラが、ほしいなあ

1. McCarthy, 1960, https://aiplaybook.a16z.com/reference-material/mccarthy-1960.pdf ↩

2. いろいろとなんとかなした結果はmasterのlisc_ref.pyを見てみてください。 ↩