PLisp:Pythonに統合されたLISP言語実装(1)

LISPの本を少し読んだが、LISPの原理は簡単だと思った.LISPにはSymbolic Expression、sexpというデータ構造が1つしかありません.プログラム自体もsexpであり、処理されたデータもsexpである.つまり、sexpで書かれたプログラムを説明できれば、LISP解釈器を作ります.
LISPではsexpは表と原子の2種類に分かれています.list(テーブル)は、0個以上のsexpを内部に秩序正しく含む.それ以外はsymbol(記号、「識別子」のような)、数字、文字列、ブール値など、atom(原子)です.例外はnilであり,表(空の表)であり原子である.
LISPの実行は,sexpの評価(evaluation)プロセスである.評価ルールは次のとおりです.
-シンボルではない原子であり、それ自体として解釈される.
-シンボルテーブルに対応する値として解釈されるシンボル.シンボルテーブルは、「シンボル->値」の対応するテーブルです.
-表、最初の要素を評価し、関数を取得し、この関数のパラメータとして他の要素を評価します.次に関数を呼び出し、このテーブルの値として値を返します.(関数が特殊な関数である場合、パラメータは評価されずに「名前で渡す」、一般的な関数では、パラメータは評価され、「値で渡す」の順です)
次に、Pythonを利用してLISP方言を実現します.
Python自体が十分なデータ構造を提供しているので、解析器(parser)を書きたくありません.Pythonにはlistデータ構造(配列)があり、LISPのテーブルに似ています.Python文字列はsymbolと見てもいいです.他のデータ型は、通常の原子として使用できます.
そこで、Python式を使うことができます.

["+", ["*", 3, 4], ['*', 5, 6]]

LISPを表す式:

(+ (* 3 4) (5 6))

また、Python式:

["let",
    [['x', 2],
     ['y', 3]],
    ['*', x, y]]

LISPを表す式:

(let
  ((x 2)
   (y 3))
  (* x y))

解釈の過程は、Python関数として書き、Python式を入力し、別のPython式を出力することができます.中間は副作用でIOを処理することができる.
どのように実現しますか?
まず、評価には、変数(またはLISPの記号)に対応する値を記録する記号テーブルが必要です.一方,LISPのシンボルテーブルは評価の過程(副作用)によって変化する.

class Context(UserDict):
    def __init__(self, parent=None):
        UserDict.__init__(self)
        self.parent = parent

Contextクラスは、シンボルテーブル、またはLISP評価の「コンテキスト」を表します.Contextはdictにすぎず、記号を入力し、値に対応します.このparentはcontextがネストできるので説明を待っています.
そして、各LISP関数はPython関数で表すことができます.コンテキストとパラメータのデカルト積からpython値へのマッピングとして定義します.簡単に言えば、LISP関数ごとに対応するPython関数は、「通常のパラメータ」のほか、Contextを追加のパラメータとして使用します.例:

def add(context, one, another):
    return one + another
# ['+', 1, 2] calls this function and evaluates to 3

この関数はシンボルテーブルに関係なく、シンボルテーブルを読み込まず、シンボルテーブルも変更しません.
次のようになります.

def _set(context, key, value):
    context[key] = value
    return value
# ['set', 'x', 40] calls this function and sets symbol 'x' to 40

これは「付与関数」で、シンボルテーブルを変更することで、シンボルkeyのvalueに対応する値を変更します.
そして

def _print(context, expr):
    print expr
    return expr
# ['print', ['quote', 'hello world!']] calls this function and prints "hello world!" to standard output

これは評価の副作用に完全に依存し,印刷出力を行う.
関数の基本形式はこうです.
基本的なLISP実行環境にはいくつかの基本的なLISP関数が必要です.最も基本的なのはもちろんeval関数です.LISPでは、evalの機能は1つの式を評価することです.Python関数を定義します.eval、組み込み関数evalとの名前の競合を回避するために.

def _eval(context, expr): #   expr， expr  
    if isinstance(expr, str): #     ，        
        cur_context = context
        #          ，      。
        while cur_context is not None:
            if expr in cur_context:
                return cur_context[expr]
            else:
                cur_context = cur_context.parent
        raise KeyError(expr)
    elif isinstance(expr, list): #    ，       。
        first, rest = expr[0], expr[1:]
        func = _eval(context, first) #           ，    。
        if getattr(func,"call_by_name",False)==False: #       。
            evrest = [_eval(context, e) for e in rest]
        else:
            evrest = rest
        return func(context, *evrest) #     ，     
    else:
        return expr #       ，     。

ちょうど3つの分岐に分かれており,LISP評価の3つのケースを扱う.
上記のコードでは、「特殊関数」について説明しています.一般的な関数は、呼び出す前にパラメータを評価してから入力します.次のようになります.

(+ (- 9 3) 4)

「+」関数を入力するには、(-9 3)の値:6を求める必要があります.
しかし、他の関数では、いくつかの条件に基づいて選択的に値を求める「名前で渡す」必要があります.次のようになります.

(if (eq (+ 1 1) 2) right wrong)

if関数は条件関数です.まず第1のパラメータの値を求めて、もし本当ならば、第2のパラメータの値を求めて、第3のパラメータは値を求めません;偽の場合、3番目のパラメータの値を求め、2番目のパラメータは動かない.
そのため、これらの特殊なLISP関数については、Python関数にいくつかのタグを付ける必要があります.私のやり方は、関数を定義した後、これらの関数にcall_を設定することです.by_nameの値はTrueです.あるいは@decoratorの方が簡単です.
典型的なif関数は、次のように定義されます.

@call_by_name
def _if(context, condition, iftrue, iffalse=None):
    if _eval(context, condition):
        return _eval(context, iftrue)
    else:
        return _eval(context, iffalse)

@call_by_name内部完了call_by_name=Trueの割り当て作業.関数体の内部では、_eval関数は最初のパラメータの値を求め,真偽の2つの場合にそれぞれ2つのブランチを呼び出す.
もう1つの典型的な「名前で渡す」関数はquoteであり、この関数は内部の記号が評価されることを避ける.LISP:

(quote abc)
'abc

両方の評価はシンボルabcを得る.quoteはこのようによく使われるため、LISPには特殊な引用符'構文があり、quote関数の応用に便利である.
Pythonでは、

@call_by_name
def quote(context, expr):
    return expr

def q(expr):
    return ['quote',expr]

quote関数はexprを評価せず、直接exprを返します.私はまたPython関数qを定義して、LISPの'に似ていて、書くのが便利です.
以上の基本関数があれば、実は簡単なプログラムを作ることができます.以下に説明します.

#   ，    ，      Context  ：
default_context = Context()

#   ，            
default_context["eval"] = _eval
default_context["print"] = _print
default_context["quote"] = quote
default_context["set"] = set
default_context["+"] = add

#   ， eval      。

#   Hello world
_eval(default_context, ["print", q("Hello world!")])
#      Hello world!

#     
_eval(default_context, ["set", q("x"), 5])
#      ，"x"    5。

#        
result = _eval(default_context, ["+", ["+", 1, "x"], 3])
print result
#   9

まとめ:
以上のプログラムから,この実現は入力が完全に合法的なPython式であり,出力もPython式であることがわかる.値を求めるのはPython言語でPython式の処理をしただけです.
現在定義されている関数によると、この「言語」機能は非常に簡単です.しかし,次編ではより多くの関数を導入し,この「言語」を機能完備のプログラム設計言語に近づけていく.