PythonでミニマルなLispを作る（評価編+α）

はじめに

この記事の続きです．
この記事で終わりです．
成果物だけ確認したい方はこちらをどうぞ．

2.評価

前回の記事で実装したreadを使って(hoge fuga)のような入力から["hoge", "fuga"]を作ることができました．あとはこの文字列のリストをS式として評価できれば完成です．まず文字列で表現されたシンボルと組み込みの関数や特殊形式との対応関係を辞書で実装します．

builtin.py(continue)

special_forms = {
    "quote": lambda symbol, *args: symbol,
    "lambda": lambda arglist, body, env, hook: lambda *args: hook(body, dict(zip(arglist, args), **env)),
    "define": lambda symbol, value, env, hook: [env.update({symbol: hook(value)}), "nil"][-1],
    "if": lambda test, trueform, falseform, env, hook: hook(trueform if hook(test) else falseform),
}

functions = {
    "atom": lambda symbol: type(symbol) is not list,
    "cons": lambda a, d: [a, d],
    "car": lambda cons: cons[0],
    "cdr": lambda cons: cons[1],
    "eq": lambda one, other: "t" if one is other else "nil",
}

constants = {
    "nil": (),
    "t": True,
}

特殊形式は場合によって現在のスコープを操作したり中でevalしたりする必要があるので関数とは呼び出し方を変える必要があります．その為別の辞書で管理することにします．特殊形式の引数にあるenvやhookについては後述します．

つぎにシンボルから値を取り出す関数を定義します．

builtin.py(end)

from enum import Enum

Kind = Enum("Kind", ["Special", "Function", "Constant", "Lambda", "Bounded", "Unbounded"])

def symbol_value(symbol, env):
    if callable(symbol):
        return symbol, Kind.Lambda
    elif symbol in special_forms.keys():
        return special_forms[symbol], Kind.Special
    elif symbol in functions.keys():
        return functions[symbol], Kind.Function
    elif symbol in constants.keys():
        return constants[symbol], Kind.Constant
    elif symbol in env.keys():
        return env[symbol], Kind.Bounded
    else:
        return None, Kind.Unbounded

現在のスコープを管理する辞書(env)を引数にとって各辞書から値を探します．どの辞書から見つかったかによってKind.種類も同時に返します．またlambdaは関数を返すので手抜きですがsymbolが関数だった場合そのままの値を返します．名前はCommon Lispのsymbol-valueからとりましたが（適当な名前が思いつかず）実態はsymbol-valueとsymbol-functionとfunctionを合わせたような感じです．

最後に本題のevalです．pythonではevalは予約語なのでeval_sexpとします．

eval.py

from builtin import symbol_value, Kind

env = {}

def eval_sexp(sexp, env=env):
    eval_in_env = lambda _: eval_sexp(_, env)
    if type(sexp) is list:
        car = sexp[0]
        func, kind = symbol_value(car if type(car) is str else eval_in_env(car), env)
        if kind is Kind.Special:
            return func(*sexp[1:], env, eval_sexp)
        elif kind is Kind.Unbounded:
            raise ValueError("The function {} is unbounded.".format(car))
        else:
            if not callable(func):
                func = eval_in_env(func)    
            return func(*list(map(eval_in_env, sexp[1:])))
    else:
        value, kind = symbol_value(sexp, env)
        if kind is Kind.Unbounded:
            raise ValueError("The symbol {} is unbounded.".format(sexp))
        return value

基本的にはリストの頭を関数，それ以降を引数として関数を呼び出すだけです．ただリストの頭が特殊形式だった場合と関数だった場合で以降の処理が異なります．関数だった場合には引数も評価しますが特殊形式だった場合には引数は評価せずに引数にenvとeval_sexpを追加します．また，リストの戦闘がリストだった場合にはその評価を先に済ませます．

試しに以下のようにテストしてみます．

test_eval.py

from eval import eval_sexp

sexp = ["lambda", ["a", "b"] ["cons", ["quote", "c"], ["quote", "d"]]]
print(eval_sexp(sexp)) 

なおこれは((lambda (a b) (cons a b)) 'c 'd)に相当します．

$ python test_eval.py
['c', 'd']

良いですね．readと組み合わせてみます．

test_readeval.py

from read import read
from eval import eval_sexp

print(eval_sexp(read()))

test.lisp

((lambda (a b) (cons a b)) 'c 'd)

$ python test_readeval.py < test.lisp
['c', 'd']

3.表示

以上までで純Lispの肝はすべて実装できました．ただしこのままだと結果の表示がPython準拠になってしいますのでプリティプリンタを実装します．

pprint.py(continue)

def pprint(value, end="\n"):
    if value is ():
        print("nil", end=end)
    elif value is True:
        print("t", end=end)
    elif type(value) is list:
        print("(", end="")
        for element in value[:-1]:
            pprint(element, end=" ")
        pprint(value[-1], end=")\n")
    else:
        print(value, end=end)
    return "nil"

見たまんまなので特に説明は必要ないとおもいます．

これはLispからも使えたほうが便利なのでimportフックでbuiltin.functionsに追加します．

pprint.py(end)

from builtin import functions

functions.update(print=lambda value: pprint(value))

確認しておきます．

test_pprint.py

from read import read
from eval import eval_sexp
from pprint import pprint

eval_sexp(read())

test.lisp

(print ((lambda (a b) (cons a b)) 'c 'd))

$ python test_pprint.py < test.lisp
(c d)

4.REPL

REPL（Read-Eval-Print-Loop）に必要なものをすべて実装できたので最後にREPLを実装します．

repl.lisp

from io import StringIO
from read import read
from pprint import pprint
from eval import eval_sexp

def readline(prompt):
    try:
        stdin = StringIO(input(prompt))
        stdin.name = "<stdin>"
        return stdin
    except EOFError:
        return

def repl(prompt="LISP> "):
    line = readline(prompt)
    while line:
        try:
            pprint(eval_sexp(read(line)))
        except Exception as e:
            print(e)
        line = readline(prompt)

ここまでの内容をただ組み合わせただけなので特にコメントはありません．

まとめ

Pythonで純Lispを実装しました．非常に仕様の小さい言語ですがBrainfuckよりも高級なものをいちから実装できたので楽しかったです．
今回実装したLispはGithubに上げてあるのでもし興味があるなら覗いてみてください．

また説明を端折った箇所も多いのでなにか質問がある場合はコメント下さい．ここおかしいよとかもっとこうした方がいいみたいのがある場合もコメントいただけるとうれしいです．

最後までお読みいただきありがとうございました．