自粛真っ只中のGW中に本が２冊発掘された。
- LISP入門（培風館）1982
- マイコンピュータNo.15「応用特集リスト処理とLISPの研究」（CQ出版）1984
第五世代コンピュータで世間が人工知能に沸く中LISPに興味を持って購入したんだと思うけど、いまだにLISPは”完全に理解する”ってさえ言える感じではない。
というわけで、このGWに何度目かのLISP入門を始めてみた。
LISP入門の目標
大抵は本を流し読みして飽きてしまうのだけど、今回はせっかくなので目標を立てることにした。ズバリ「LISPインタプリタを作る」のが目標。良くある例題「階乗」「ハノイの塔」「n queen」が解けるインタプリタ作成を目指す！
インタプリタの仕様云々はLISPのことを知らない自分にはわからないので、最終的に出来上がったものが仕様ということにした。
インタプリタを作成する言語は Python。手元でサクっと何か書くときは大抵 Python なのでいつも通りに。環境としては PyCharm で Python 3.8.3 を使ってプロジェクトを作成した。
参考にしたのは上記の2冊の本、そして以下のサイト。
特に「((Pythonで) 書く (Lisp) インタプリタ)」はお世話になったと言うか、目指すものが出来あがっちゃってるので困った。リストをPythonのlistで実装している部分をセルに変えたりしてはいるけど、Envクラスなどほぼまんまコード使ってる部分もある。
出来上がったインタプリタは github に置いてある。名前は「Pythonで書いたLISP」で PISP。
以下、各ファイル毎のメモ。
Cell
Python の class で Cell を作る。プロパティに car, cdr を用意してデフォルトではどちらも None にしている。（空リスト）
class Cell:
def __init__(self, car_value=None, cdr_value=None):
self.car = car_value
self.cdr = cdr_value
def __str__(self):
if isinstance(self.car, self.__class__):
if self.cdr is None:
return '(%s)' % self.car
elif not isinstance(self.cdr, self.__class__):
return '(%s).%s' % (self.car, self.cdr)
else:
return '(%s) %s' % (self.car, self.cdr)
elif self.cdr is None:
return '%s' % self.car
elif not isinstance(self.cdr, self.__class__):
return '%s.%s' % (self.car, self.cdr)
else:
return '%s %s' % (self.car, self.cdr)
def cell_string(self):
return '(%s)' % self
引数は特に型の指定はしていないので atom でも Cell でも（何でも）car, cdr 共に接続できる。
上記リストにはないが、Cellの比較のために __eq__ も書いておく。それぞれの car, cdr が同じなら True。何と比較が行われるかわからないので、一応 other が Cell のインスタンスかどうかの確認も行っている。
print する際の __str__ は場合わけが汚いけど何とかプリントできている。
LISP は最初にセルをたくさん繋いで、必要な分をそこから取り出して使うのが本来のやり方らしいけど、今回は取り敢えずと言うことでセルが必要になったら都度新しいセルを作ることにする。なので GC ももちろん無し！
Parser
インタプリタの仕事と言うと「構文解析して実行」の事を言うのだと思うのだけど、その中の構文解析を Parser と Reader に分けてある。
Parser は入力されたS式をtokenに分解する部分。この後で Reader でセルを使った形式にする。
class Parser:
def __init__(self):
self.token_buffer = []
def tokenize(self, s):
(s0, string_dic) = self.parse_string(s)
s1 = s0.replace('(', ' ( ')
s2 = s1.replace(')', ' ) ')
s3 = s2.replace('\'', ' \' ')
tokens = s3.split()
self.do_quote(tokens, 0)
for key in string_dic.keys():
if key in tokens:
index = tokens.index(key)
tokens[index] = string_dic[key]
return tokens
tokenize は前出のコードを参考にしている。LISPのS式は ‘や”で括られた文字列を気にしなければ ‘(‘, ‘)’ の前後にスペース入れて .split すると綺麗に分解できる！感動。
で、そのあとで ‘ を (quote ) にする作業を加えてる。やっていることは’を見つけたら'(‘と’quote’に変更して、対応する括弧が閉じる場所に’)’を挿入してる。入れ子になってても再帰で対応。
また、”で括られた文字列をサポートするために、一番最初に “で括られた文字列を特別なシンボルに変換して、tokenize が終わったらそのシンボルを “の中の文字列に戻す作業も入れてる。
正直、”で括られた文字列は面倒だからサポートしてなかったのだけど、fprint のフォーマット文字列が必要になったので取り敢えずこんな感じで対応してみた。
これ、もっとスマートにできないものか？
ところで、入力された S式の括弧が閉じていない場合エラーになるのが嫌だったので、Parser は token_buffer に token を保持する。そして次に入力されて parse された token と繋がれて、括弧が閉じた分の tokens が返り値となる。
(car ‘(a が入力された場合は [‘(‘, ‘car’, ‘\”, ‘(‘, ‘a’] に分解されて、括弧が閉じていないので token_buffer に保持される。この時の返り値は []。次に入力が b)) の場合、[‘b’, ‘)’, ‘)’] に分解され先の token_buffer の末尾に加えられ、括弧が閉じているので返り値は[‘(‘, ‘car’, ‘\”, ‘(‘, ‘a’, ‘b’, ‘)’, ‘)’]になる。
Reader
Paser で token 単位に分割されたら後はセルで表現するだけ。
class Reader:
def read_next_cell(self, token, tokens):
s_list = None
if token != '(':
return Interpreter.atom(token)
while True:
try:
token = tokens.pop(0)
except IndexError:
print('Error ) is missing.')
return None
if token == ')':
return s_list
cell_car = self.read_next_cell(token, tokens)
s_list = Cell.append_cell_at_last(s_list, Cell(cell_car, None))
def read_cells(self, tokens):
token = tokens.pop(0)
return self.read_next_cell(token, tokens)
token をスキャンして、最初の token が ‘(‘ でなければそれは atom なので token を atom にして返す。そうでなければセル（s_list）を作る作業開始。
次に token を pop して ‘)’ なら括弧が閉じるのでセルの出来上がりなのでセル（s_list）を返す。
そうでなければセルの car の部分を再度 read_next_cell を呼んで作成した後、それを car にしたセルを作成して最初に作り始めたセル（s_list）の最後にくっ付ける。Cell.append_cell_at_last(a, b) はリストaの最後にリストbを加えるメソッド。
Interpreter
LISP の肝 Eval/Apply、そして名前空間の Env が詰まっているのが Interpreter。
class Interpreter:
class Env(dict):
def __init__(self, params=(), args=(), before=None):
super(dict, self).__init__()
self.update(zip(params, args))
self.before = before
def find(self, var):
return self if var in self else self.before.find(var)
def eval(self, s, env=None):
if env is None:
env = self.env
if not isinstance(s, Cell):
if isinstance(s, float) or isinstance(s, int):
return s
else:
return env.find(s)[s]
else:
if isinstance(s.car, Cell):
return self.apply(Cell(self.eval(s.car, env), s.cdr), env)
else:
return self.apply(s, env)
Eval は atom ならその値を返す。atom が数字でない場合は env から値を探して返す。セルなら car が関数名で cdr が引数として apply する。env はその時々での atom と値の辞書。
Envは先に出てきた ((Pythonで) 書く (Lisp) インタプリタ) のコードほぼそのまま。名前と値の辞書で、プロパティbeforeで世代（範囲？）を辿れる。lambda で新しい名前空間？が出来る度に新しい Env を作成してbeforeに繋げる。名前が最新の Env に見当たらなければ、その前の Env から探す。新しい Env から古い Env へと順繰りに探すので、同じ名前があっても最新の値を取得できる。
apply は S式と env から実際に関数を実行する。まず最初に以下の特殊形式？の関数の処理がベタに書かれている。
- quote
- if
- set!
- define
- lambda
- begin
- cond
今回の目標の「階乗」「ハノイの塔」「N Queen」を解くだけならこれで十分。（いらないものもあるけど）
そしてその後で S式の car 部が関数本体の場合（ Python の callable）の処理。
proc = s.car
exps = self.evaluated_args_list(s.cdr, env)
return proc(*exps)
最後に S式の car部が関数名の場合の処理がある。関数名の場合は env から関数名で関数本体を得て実行している。
proc = s.car
exps = self.evaluated_args_list(s.cdr, env)
return env.find(proc)[proc](*exps)
Functions
参考にした本でも web で見つけたコードでもそうなのだけど、組込関数（SUBR）は関数ポインタ？を使って呼び出されている。後から関数を加えるのに便利だから？と言うわけで Functions.py には SUBR な関数が入っている。
関数は {“関数名”: 処理へのポインタ} という辞書を使って呼び出すことにしている。これを準備するのが Interpreter.py の add_globals と load_functions。基本的な算術オペレータは Python の math と operator から拝借して、それ以外の組込関数（cons, car, cdr, append など）は Functions.py から読み込んでいる。
組込関数に可変長の引数を渡すのは *arg で問題ないのだけど、評価しない引数を渡さなければいけない場合は現状の eval だとできないので（全て評価されてから渡されてしまう）、eval(apply) の中に書くか quote で括ってから渡す仕様にするかしないといけない。と言うわけで fprint は quote で括ってから渡す仕様になってる。
def pl_fprint(format_string, *args):
print(format_string % tuple(args))
組込関数の名前についてはかなり適当。参考にした本やサイトによって違っていたりするので…。多分古いLISPとCommonLISPとschemeが混ざってるんだと思う。
Pisp
Pispインタプリタを動かす部分。-f オプションでファイルを指定して読み込ませることができる。例えば sample フォルダの hanoi.lsp を読ませる場合はこんな感じ。
$ python Pisp.py -f sample/hanoi.lsp
Read following functions:
dict_keys(['cons', 'car', 'cdr', 'length', 'plus', 'difference', 'numberp', 'atom', 'null', 'stringp', 'listp', 'fixp', 'floatp', 'append', 'reverse', 'last', 'member', 'list', 'fprint', 'print', 'or', 'and'])
read:
(define hanoi
(lambda (n i j k)
(begin
(if (> n 1)
(hanoi (- n 1) i k j)
)
(fprint '"move %dth from %d to %d" n i j)
(if (> n 1)
(hanoi (- n 1) k j i)
)
)
)
)
(hanoi 3 1 2 3)
hanoi
move 1th from 1 to 2
move 2th from 1 to 3
move 1th from 2 to 3
move 3th from 1 to 2
move 1th from 3 to 1
move 2th from 3 to 2
move 1th from 1 to 2
None
pisp > (quit)
__quit
$
ファイルを指定しなければそのままプロンプトに入る。
Pisp.py で行っているのは基本 repl。入力された S式を Parser に渡して返ってくる tokens のリストを Reader でセルにして Interpreter で eval している。括弧が閉じていなくてもエラーにならないようにする為に余計な処理が入っているけど、これは Parser に閉じ込めた方が後々面倒が少なそう。
「階乗」「ハノイの塔」「N Queen」
目標としたこれらの例題は無事に解ける（書ける）ようになった。それぞれ lisp_sample フォルダの中にコードが入っているので、読み込ませて起動すれば確認ができる。
「階乗」については簡単なので特に参考にしたものはない。
「ハノイの塔」は GW中に一緒に発掘された下記の本に書かれていたものを使った。begin で逐次処理するのは LISPっぽくないのかも。
- マイコンピュータNo.18「探求特集アルゴリズムとプログラミング」（CQ出版）1985
「N Queen」はネットで見つけた解法を参考にした。member の引数の順序が違うのがミソ。ネットを彷徨いながらコードを読んでみてなんとなくこのページが一番しっくり来た。斜めに利いているかどうかの確認がわかりやすいかどうかが肝な気がする。
その他
まだ色々と気になる点はたくさんあるのだけどその幾つか。
- nil の扱い
- ((lambda (x) (+ x 1)) 1) を動かす
- 組込関数
nil については globals で {‘nil’: None} になっている。S式 () を読み込んだ場合、Reader で None になる（Cell(None, None)にはならない）。null 関数は引数が None でも Cell(None, None) でも True を返す。と言うわけで、nil が False なわけではない。これは、最初になんとなく「nil は取り敢えず None にしておくか」としたのが原因。Python が if None A else B とすると B になるので動いている。ちなみに () の長さ（__len__)は0。
((lambda (x) (+ x 1)) 1) は当初の eval だと （関数名 引数）でないとダメだったので、car部が関数名でない S式を評価した時点でエラーになってた。ただ、この例の様に car 部が関数名でない場合もそれを eval して最終形態？が関数名もしくは lambda式ならそれを eval するようにした。
組込関数は参考にした本の例題で出てきた関数を幾つか入れてある。reverse とか append とかなのだけど、例題が再帰で解くものだったのでそれをそのまま Python に直してある。なので処理速度は遅いと思う。8 Queen すると数秒かかってから答えが出てくるので、アルゴリズムもあるだろうけど member が遅いのも原因なのかな？と思ってみたり。
最後に
取り敢えず目標には達したので満足。「LISP 完全に理解した！」と言えるところまでギリ行けたかな？
頭の中がかな〜り再帰脳になっているので、あれこれやってみたいことはあるのだけど時間切れ。7/17 発売の「Ghost of Tsushima」をやらないと…