Arantium Maestum

プログラミング、囲碁、読書の話題

LispKit Lisp処理系の実装 3:インタプリタ〜条件分岐から関数適用まで

前回に続いてインタプリタの実装。今回はeval_の後半、IFによる条件分岐以降の項目を見ていく。

条件分岐のパターンマッチ

条件式を評価してその結果に対してパターンマッチ、分岐部分の式は片方しか評価されない。

        case Cons(Alpha("IF"), Cons(e1, Cons(e2, Cons(e3, Alpha("NIL"))))):
            match eval_(e1, n, v):
                case Alpha("T"):
                    return eval_(e2, n, v)
                case Alpha("F"):
                    return eval_(e3, n, v)
                case v:
                    raise ValueError(f"Non-boolean value {v} in if-condition")

条件式が真偽値じゃなければ実行時エラー。

無名関数

(LAMBDA ARG-LIST BODY-EXP)で無名関数が作れる。

        case Cons(Alpha("LAMBDA"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return Cons(Cons(e1, e2), Cons(n, v))

このインタプリタ内での関数の内部表現は((仮引数 . 本体の式) . (クロージャの名前部分 . クロージャの値部分))というネストしたドット付きリストになっている。関数オブジェクトとして特殊なデータタイプを用意するのではなく、あくまでシンボル、数値、Consセルの組み合わせで「評価済みの関数」を表現している。

ちなみにこの実装(Henderson本準拠)だとクロージャCons(n, v)つまり「現在の名前空間すべて」になるので非常にメモリ効率が悪い。少し煩雑になるが本体の式の中の自由変数を検出してそれだけをクロージャとして捕捉する方が効率は良くなる。

LispKit LispにはSchemedefineのように名前付き関数を定義する構文はないので、関数を名前で呼び出したかったらLAMBDAで作った無名関数にLETなどで名前を束縛する必要がある。

変数束縛

前回も書いた通り、LispKit LispのLETでは、第二要素が本体の式、それ以降が変数と値のペアのリスト。

        case Cons(Alpha("LET"), Cons(e1, e2)):
            n_ = Cons(vars_(e2), n)
            v_ = Cons(evlis(exprs(e2), n, v), v)
            return eval_(e1, n_, v_)

変数と値のペアのリストをヘルパ関数vars_exprsを使って名前リストと値リストに分け、値リストの方はevlis関数でに評価してから名前空間に追加した上で本体の式を評価する。

def vars_(es):
    match es:
        case Alpha("NIL"):
            return Alpha("NIL")
        case Cons(Cons(n,v), es_):
            return Cons(n, vars_(es_))
        case _:
            raise ValueError(f"Cannot get vars of {es}")

def exprs(es):
    match es:
        case Alpha("NIL"):
            return Alpha("NIL")
        case Cons(Cons(n,v), es_):
            return Cons(v, exprs(es_))
        case _:
            raise ValueError(f"Cannot get exprs of {es}")

def evlis(es, n, v):
    match es:
        case Alpha("NIL"):
            return Alpha("NIL")
        case Cons(e, es_):
            return Cons(eval_(e, n, v), evlis(es_, n, v))
        case _:
            raise ValueError(f"Cannot get evlis of {es}")

これらヘルパ関数はよくみると全部mapであることがわかる。Haskellっぽく書くとこんな感じ:

vars_ = map car
exprs = map cdr
evlis xs n v = map (\e -> eval_ e n v) xs

再帰的定義

LETRECはLETとあまり変わらない実装になっている:

        case Cons(Alpha("LETREC"), Cons(e1, e2)):
            n_ = Cons(vars_(e2), n)
            v_ = Cons(Alpha("PENDING"), v)
            v_.car = evlis(exprs(e2), n_, v_)
            return eval_(e1, n_, v_)

やはり名前空間を適切に取り出すためにvar_exprsを使って、evlisexprsで取り出したものを評価している。

ただしLETに比べて、evlisで使う名前空間が拡張されている。名前のほうはvars_(e2)、値のほうはAlpha("PENDING")というダミー値を追加した上でevlisに渡している。そしてそのevlisの結果をv_Alpha("Pending")部分を入れ替える形で破壊的代入している。

この「evlisに拡張した名前空間を渡す」「本体を評価する前に破壊的代入で名前空間を変更する」の二つが再帰を可能としているポイントとなる。

関数適用

LAMBDAの部分で書いた通り、関数部分であるe1を評価すると((仮引数 . 本体の式) . (クロージャの名前部分 . クロージャの値部分))という形になっているので、それをパターンマッチで解体して再帰的にeval_する。

        case Cons(e1, e2):
            match eval_(e1, n, v):
                case Cons(Cons(args, e3), Cons(n_, v_)):
                    return eval_(e3, Cons(args, n_), Cons(evlis(e2, n, v), v_))
                case e_:
                    raise ValueError(f"Non-function {e_} found at func position")

仮引数をクロージャの名前部分に追加、実引数のリストであるe2を評価した上でクロージャの値部分に追加、それらを名前空間として関数本体の式を評価して返す。

関数が再帰的かどうかは関係なく、まったく同じ処理で走る。再帰関数を作成するときに破壊的変更を使ってクロージャ再帰的にしてあることのメリットである。

ASTの文字列出力

llast.pyモジュールにto_string関数を追加しておく:

from dataclasses import dataclass

@dataclass
class Alpha:
    s : str

@dataclass
class Num:
    n : int

@dataclass
class Cons:
    car : any
    cdr : any

def to_string(e): # 追加
    match e:
        case Num(n):
            return str(n)
        case Alpha(s):
            return s
        case Cons(hd, tl):
            return f"({to_string(hd)}{to_string_tl(tl)})"

def to_string_tl(tl): # 追加
    match tl:
        case Alpha("NIL"):
            return ""
        case Cons(hd, tl1):
            return f" {to_string(hd)}{to_string_tl(tl1)}"
        case _:
            return f" . {to_string(tl)}"

やはりリストの取り扱いがちょっと特殊なのでその部分で相互再帰的になっている。

インタプリタを実行する

run関数で受け取る文字列をパース、空の名前空間で評価してから前述のto_string関数で文字列化している:

def run(s):
    return to_string(eval_(p.parse(s), Alpha("NIL"), Alpha("NIL")))

使ってみる

で紹介したユニットテストが全て通るのでヨシ。

雑感

Pythonのパターンマッチ構文は便利なのだが、なんらかのオーバーロードとかマジックメソッド定義でConsセルをリストと見做してcase [Alpha("LAMBDA"), args, body]:と書けるようになったりしないだろうか。今回のコードに関して言えば可読性が相当向上する。

前回と今回のコード

Interpreter for LispKit Lisp (based on Henderson's "Functional Programming Application & Implementation") · GitHub

次回

SECD抽象機械を実装する。

LispKit Lisp処理系の実装 2:インタプリタ〜変数から算術演算子まで

前回のパーサの出力するASTをそのまま実行するインタプリタを実装する。

インタプリタを実装する意義

「SECD抽象機械へのコンパイラ実装の前にインタプリタを作る」というのはHendersonのFunctional Programming Application & Implementationでの流れに従っている。

Python(やLispOCaml)のような高レベルプログラミング言語インタプリタを実装すると、言語の意味論を直感的に理解しやすい。ただしその直感は実装言語の意味論を直感的かつ正確に把握していることが前提となる。例えば関数適用時に実引数がどの順番で評価されるか、などが実装言語の仕様に依存しやすい(ちなみにPythonOCamlではその順番が逆だ)

これがSECD抽象機械などの低レベルな実行システムだと、挙動が厳密に定義・把握しやすいが直感的な理解は難しく、一長一短といったところ。というわけでやはり両方やるのが良さそう。

eval_関数

インタプリタの本体となるのはeval_という再帰関数で、未評価のASTノードを受け取り評価済みASTノードを返す。評価前と後で同じデータ型のままなのがLispらしい。

eval_関数はパターンマッチ(しつこいようだがPython3.10の新機能)で実装している:

def eval_(e, n, v):
    match e:
        case Alpha("NIL"): ... # マッチ後の処理は後述
        case Alpha(s): ...
        case Num(_): ...
        case Cons(Alpha("QUOTE"), Cons(e1, Alpha("NIL"))): ...
        case Cons(Alpha("ATOM"), Cons(e1, Alpha("NIL"))): ...
        case Cons(Alpha("CONS"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("CAR"), Cons(e1, Alpha("NIL"))): ...
        case Cons(Alpha("CDR"), Cons(e1, Alpha("NIL"))): ...
        case Cons(Alpha("EQ"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("LEQ"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("ADD"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("SUB"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("MUL"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("DIV"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("REM"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("IF"), Cons(e1, Cons(e2, Cons(e3, Alpha("NIL"))))): ...
        case Cons(Alpha("LAMBDA"), Cons(e1, Cons(e2, Alpha("NIL")))): ...
        case Cons(Alpha("LET"), Cons(e1, e2)): ...
        case Cons(Alpha("LETREC"), Cons(e1, e2)): ...
        case Cons(e1, e2): ...

eval_関数は評価するべき式e名前空間の名前部分であるn、そして名前空間の値部分のvを引数にとって評価結果を返す。名前空間(変数 . 値)のペアのリスト(association list)で表すのではなく、変数のリストのリストと値のリストのリストを別に保持している。(これはHenderson本に合わせた実装)

関数の中心は前述の通り式eに対するパターンマッチだ。

長くなるので今回の記事はREMまでの処理を解説する。IFによる条件分岐以降は次回に持ち越し。

シンボル

評価する式がシンボルだった場合、その内容がNILならそのままAlpha("NIL")というシンボルを返す(つまりNILは評価されてもNILのまま)。

        case Alpha("NIL"):
            return e

NIL以外のシンボルは変数として、対応する値を名前空間から探して返す。名前空間の探索はassocというヘルパ関数に任せている。

        case Alpha(s):
            return assoc(e, n, v)

シンボル解決のヘルパ関数

assoc関数で変数を表すシンボルに対応する値を名前空間からとってくる:

def assoc(x, n, v):
    match n:
        case Alpha("NIL"):
            raise ValueError(f"Variable {x} not found")
        case Cons(n1, ns):
            if member(x, n1):
                return locate(x, n1, v.car)
            else:
                return assoc(x, ns, v.cdr)
        case _:
            raise ValueError(f"Invalid name list {n} passed to assoc")

nvが名前や値の「リスト」ではなく「リストのリスト」であるのがポイント。LETや関数適用に入るたびにひとつ以上の変数束縛のある「環境」が名前空間に追加されていくので、assocもそれに対応する形でシンボル解決をする必要がある。

環境ひとつ分である「名前のリスト」にある変数が含まれているかを確認するmember関数と、変数に対応する値をとってくるlocate関数:

def member(x, n1):
    match n1:
        case Alpha("NIL"):
            return False
        case Cons(y, n2):
            return x == y or member(x, n2)

def locate(x, n1, v1):
    if x == n1.car:
        return v1.car
    else:
        return locate(x, n1.cdr, v1.cdr)

数値

数値の場合は本シリーズの序でも書いた通り、タネ本から少し乖離して「評価されての数値のまま」という結果になるようにしてある。

        case Num(_):
            return e

QUOTE、ATOM

QUOTEは次の要素をそれ以上評価せずに結果として返す。

ATOMは次の要素が評価された結果がシンボルや数値であれば真、そうでなければ(Consなので)偽となる。

        case Cons(Alpha("QUOTE"), Cons(e1, Alpha("NIL"))):
            return e1
        case Cons(Alpha("ATOM"), Cons(e1, Alpha("NIL"))):
            match eval_(e1, n, v):
                case Alpha(_):
                    return Alpha("T")
                case Num(_):
                    return Alpha("T")
                case _:
                    return Alpha("F")

ここでうっかりCons(Alpha("ATOM"), e1)としてしまうと(ATOM . e1)のようなドット付きリストに対するマッチになってしまうので注意。

ATOMの場合、引数であるe1をまず再帰的に評価(eval_(e1, n, v))してその結果に対しパターンマッチしている。

リスト関係

リストを作るCONS、リストの先頭とそれ以外を取り出すCARとCDR:

        case Cons(Alpha("CONS"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return Cons(eval_(e1, n, v), eval_(e2, n, v))
        case Cons(Alpha("CAR"), Cons(e1, Alpha("NIL"))):
            match eval_(e1, n, v):
                case Cons(e2, _):
                    return e2
                case e_:
                    raise ValueError(f"Cannot take CAR of non-cons {e_}")
        case Cons(Alpha("CDR"), Cons(e1, Alpha("NIL"))):
            match eval_(e1, n, v):
                case Cons(_, e2):
                    return e2
                case e_:
                    raise ValueError(f"Cannot take CDR of non-cons {e_}")

CONSは簡単だが、CARとCDRはそもそも対象がConsセルでなければエラーなので各ケースの中でさらにパターンマッチしている。

すべてのケースで、まずは引数を再帰的にeval_に渡しているのもポイント。

比較・算術演算子

比較用のEQ、LEQ、算術演算子のADD、SUB、MUL、DIV、REM:

        case Cons(Alpha("EQ"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return eq(eval_(e1, n, v), eval_(e2, n, v))
        case Cons(Alpha("LEQ"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Alpha("T") if x <= y else Alpha("F"))
        case Cons(Alpha("ADD"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x+y))
        case Cons(Alpha("SUB"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x-y))
        case Cons(Alpha("MUL"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x*y))
        case Cons(Alpha("DIV"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x//y))
        case Cons(Alpha("REM"), Cons(e1, Cons(e2, Alpha("NIL")))):
            return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x%y))

比較も算術演算子もヘルパ関数を使って実装。

比較・算術演算子のヘルパ関数

EQだけは数値以外の要素も比較できるので、独自のヘルパ関数内で直接パターンマッチしている:

def eq(x, y):
    match x, y:
        case Num(n), Num(m):
            res = n == m
        case Alpha(s), Alpha(t):
            res = s == t
        case _:
            res = False
    return Alpha("T" if res else "F")

めんどくさいのでEQで比較して同値だと分かるのは数値とシンボルだけにしてある。Consセルに拡張するのもそう難しくはないが・・・(再帰するだけ)

LEQやADDなどの算術演算子は引数が両方Numであることを確認する必要があるのでnumopというヘルパ関数を使っている:

def numop(x, y, f):
    match x, y:
        case Num(n), Num(m):
            return f(n, m)
        case _:
            raise ValueError(f"Numeric op on non-numeric values {x} and {y}")

Numに対するパターンマッチだけnumopで抽象化して、実際の演算や結果はPythonの無名関数を引数として受け取っている。

今回(と次回)のコード

Interpreter for LispKit Lisp (based on Henderson's "Functional Programming Application & Implementation") · GitHub

次回

次の記事ではIF、LET、LAMBDA、LETREC、関数適用の実装の紹介と、インタプリタが動いて「序」で紹介したユニットテストが通るところまで話す。

LispKit Lisp処理系の実装 1:パーサ

前回書いたとおりまずはパーサを実装する。

最近散々パーサ実装について書いてきてなんだが、Lispなのでかなりの手抜きパーサ。

字句解析

まずはトークンの定義:

from dataclasses import dataclass

@dataclass
class Lparen:
    pass

@dataclass
class Rparen:
    pass

@dataclass
class Dot:
    pass

@dataclass
class Alpha:
    s : str

@dataclass
class Num:
    n : int

Quoteトークンとして扱って、例えば(QUOTE (1 2 3))の代わりに'(1 2 3)と書けるようにしようかとも考えたのだが、タネ本の方ではそういう実装になっていなかったので今回は省略。

字句解析は本当に手抜き:

def lex(s):
    s = s.replace("(", " ( ").replace(")", " ) ").replace(".", " . ")
    for token in s.split():
        match token:
            case "(":
                yield t.Lparen()
            case ")":
                yield t.Rparen()
            case ".":
                yield t.Dot()
            case _ if all((c in string.ascii_letters) for c in token):
                yield t.Alpha(token)
            case _ if all((c in string.digits) for c in token):
                yield t.Num(int(token))
            case _:
                raise ValueError(f"Unable to lex {token}")

Pythonの文字列処理のs.replace(...)().の文字の周りに空白を入れてからs.split()を呼んで、それをパターンマッチで適当なトークンクラスに変換している。

構文解析

ASTのノードの定義:

from dataclasses import dataclass

@dataclass
class Alpha:
    s : str

@dataclass
class Num:
    n : int

@dataclass
class Cons:
    car : any
    cdr : any

トークンとASTでAlphaNumがかぶっているのが嫌だが、うまく差別化できる名前が思いつかない。見ての通り、三種類の要素しかないAST。

パーサは非常に簡単ながら再帰下降パーサになっている:

def parse(s):
    tokens = list(lex(s))[::-1]
    return parse_exp(tokens)

def parse_exp(tokens):
    match tokens.pop():
        case t.Lparen():
            return parse_list(tokens)
        case t.Num(n):
            return a.Num(n)
        case t.Alpha(s):
            return a.Alpha(s)
        case token:
            raise ValueError(f"Unexpected token {token} at start of expression")

def parse_list(tokens):
    items = []
    tail = a.Alpha("NIL")

    while tokens[-1] not in (t.Dot(), t.Rparen()):
        items.append(parse_exp(tokens))

    if tokens[-1] == t.Dot():
        tokens.pop()
        tail = parse_exp(tokens)
        if tokens[-1] != t.Rparen():
            raise ValueError(f"Unexpected token {tokens[-1]} found at end of dotted list")
    tokens.pop()

    for item in reversed(items):
        tail = a.Cons(item, tail)
    return tail

lexerの返すトークンを全部逆順にリストに入れて、相互再帰関数でpopして消費しながら回していく、というのは結構よく使う小技。

例えばこんな問題でもほぼ同じ手法が使えた:

トークンがメモリに乗るのが微妙だが、それ以外では無限に先読み可能なスタックとして便利に使える。

あとはparse_expで左カッコに遭遇したらparse_listを呼び出し、その中でリストの要素の数だけparse_expが呼び出される、という相互再帰構造。

使ってみる

前回同様、ユニットテストを掲載する。

まずはlexer:

def test_lexer():
    assert list(p.lex("()")) == [t.Lparen(), t.Rparen()]
    assert list(p.lex("(abc)")) == [t.Lparen(), t.Alpha("abc"), t.Rparen()]
    assert list(p.lex("( abc) ")) == [t.Lparen(), t.Alpha("abc"), t.Rparen()]
    assert list(p.lex("(abc 2)")) == [t.Lparen(), t.Alpha("abc"), t.Num(2),  t.Rparen()]
    assert list(p.lex("(abc 2 . ghi )")) == [t.Lparen(), t.Alpha("abc"), t.Num(2),  t.Dot(), t.Alpha("ghi"), t.Rparen()]
    assert list(p.lex("(()()(")) == [t.Lparen(), t.Lparen(), t.Rparen(), t.Lparen(), t.Rparen(), t.Lparen()]

parser:

def test_parser():
    assert p.parse("()") == a.Alpha("NIL")
    assert p.parse("(abc)") == a.Cons(a.Alpha("abc"), a.Alpha("NIL"))
    assert p.parse("(abc 2 . ghi )") == a.Cons(a.Alpha("abc"), a.Cons(a.Num(2), a.Alpha("ghi")))
    assert p.parse("(abc 2 . (ghi) )") == a.Cons(a.Alpha("abc"), a.Cons(a.Num(2), a.Cons(a.Alpha("ghi"), a.Alpha("NIL"))))

今回のコード

Lexer and Parser for LispKit Lisp (based on Henderson's "Functional Programming Application & Implementation") · GitHub

次回

次はパーサの返すASTをそのまま評価するインタプリタを作る。

LispKit Lisp処理系の実装 序

純粋関数型Lisp方言であるLispKit LispインタプリタとSECD抽象機械の機械語へのコンパイラを作成する。

タネ本はHendersonの「Functional Programming - Application & Interpretation」で、この本に載っているISWIMやPASCALのコードを大体なぞるようにPythonで書いていく。(最近出た「コンパイラー原理と構造ー」でもSECDマシンへのコンパイルの話題が出ているらしいがまだ届いていないので未確認・・・)

例によって長くなるので複数の記事に分ける。

流れとしては以下のようになる:

LispKit Lisp

LispKit LispはHendersonが考案したSECD抽象機械にコンパイルできる(=非常に簡単にいろんなアーキテクチャにポートできる)正格評価な純粋関数型のLispで、ある意味LandinのISWIMの中間表現のような言語である。構成要素はLispらしく最小限で、数値とシンボルとConsセルの三つ。

予約語・Special Form的なシンボルは以下の通り:

  • QUOTE
  • ATOM
  • CONS, CAR, CDR
  • EQ, LEQ
  • ADD, SUB, MUL, DIV, REM
  • IF
  • LET
  • LAMBDA
  • LETREC

これら一つ一つをユニットテストを通して紹介していく。

QUOTE

他のLispでも見られるクオート機能。シンボルやリストを変数や関数適用ではなく、シンボルやリストそのものとして評価させるために使う:

def test_quote():
    assert m.run("(QUOTE 1)") == "1"
    assert m.run("(QUOTE TEST)") == "TEST"
    assert m.run("(QUOTE (1 2))") == "(1 2)"
    assert m.run("(QUOTE (1 . 2))") == "(1 . 2)"

数値はそのまま数値として評価される。余談だがHenderson本のLispKit Lispでは数値リテラルもQUOTEなしだと変数のようなものとして名前空間に対する検索が行われてしまうようだったが(なので本の中の例では至るところで(QUOTE 1)などという表記が出てくる)、さすがに不便そうだったのでこの仕様は変えた。

シンボル、リスト、ドットつきリスト(リストの終端要素がNILでないもの)はすべて「そのもの」として評価されている。

ATOM

式の評価結果がアトミック(つまり数値かシンボル)であるかどうかを調べる:

def test_atom():
    assert m.run("(ATOM 1)") == "T"
    assert m.run("(ATOM (QUOTE X))") == "T"
    assert m.run("(ATOM (ADD 1 2))") == "T"

    assert m.run("(ATOM (QUOTE (1 2)))") == "F"
    assert m.run("(ATOM (QUOTE (1 . 2)))") == "F"

ちなみに真偽値は"T"と"F"というシンボルで表す。真偽値にそれらシンボルが束縛されているのではなく、シンボル自体が真偽値そのものであるのがポイント。

ATOMの引数が評価されて数値やシンボルなら真、リストなら偽。

CONS, CAR, CDR

ざ・LISPとも言うべきCONS、CAR、CDRの三組。

def test_list():
    assert m.run("(CONS 1 2)") == "(1 . 2)"
    assert m.run("(CONS 1 (QUOTE NIL))") == "(1)"
    assert m.run("(CONS 1 (QUOTE (2 3)))") == "(1 2 3)"

    assert m.run("(CAR (CONS 1 2))") == "1"

    assert m.run("(CDR (CONS 1 2))") == "2"
    assert m.run("(CDR (QUOTE (1 2)))") == "(2)"
    assert m.run("(CDR (CDR (QUOTE (1 2))))") == "NIL"

CONSでリスト作成・延長。CARで先頭要素を取り出し、CDRで先頭要素以外を取り出す。

LEQ、EQ

LEQとEQは比較演算子。LEQはless than or equal、EQはequal。

def test_comp():
    assert m.run("(LEQ 1 2)")  == "T"
    assert m.run("(LEQ 2 1)")  == "F"
    assert m.run("(EQ 1 1)")  == "T"
    assert m.run("(EQ 1 2)")  == "F"

ADD、SUB、MUL、DIV、REM

これらはお馴染みの算術演算子。REMは剰余。

def test_arithmetic():
    assert m.run("(ADD 1 2)")  == "3"
    assert m.run("(SUB 1 2)")  == "-1"
    assert m.run("(MUL 1 2)")  == "2"
    assert m.run("(DIV 1 2)")  == "0"
    assert m.run("(REM 1 2)")  == "1"

IF

条件分岐。

def test_if():
    assert m.run("(IF (QUOTE T) 1 2)") == "1"
    assert m.run("(IF (QUOTE F) 1 2)") == "2"
    assert m.run("(IF (EQ 1 1) (SUB 2 1) (ADD 2 0))") == "1"
    assert m.run("(IF (LEQ 3 1) (SUB 2 1) (ADD 2 0))") == "2"

    assert m.run("(ADD (IF (QUOTE T) 3 2) 1)") == "4"

LispKit LispではIFも式なので当然他の式の中にも書ける。

LET

変数導入・束縛に使う。

def test_let():
    assert m.run("(LET X (X . 1))") == "1"
    assert m.run("(LET Y (X . 1) (Y . 2))") == "2"
    assert m.run("(LET (ADD X Y) (X . 1) (Y . 2))") == "3"
    assert m.run("(LET (ADD X Y) (X . (SUB 2 1)) (Y . (MUL 2 1)))") == "3"

    assert m.run("(SUB (LET (ADD X Y) (X . 1) (Y . 2)) 2)") == "1"

面白いのは(LET BODY-EXP (VAR . EXP) ...)という構文だという点。他のLispでは(LET ((VAR . EXP) ...) BODY)という順番が普通だ。

LispKit Lispの構文の利点は実装の簡単さ。BODY-EXPの部分がcadrで取れて、((VAR . EXP) ...)の部分がそのままcddrでリストになっている。束縛する変数がひとつしかない場合、他のLispの構文だと(LET ((VAR . EXP)) ...)と書かせるのか別構文で(LET (VAR . EXP) ...)を用意するのか、と考える必要が出てくるが、LispKit Lispの構文だとそれはない。

最初は非直感的で読みにくいように感じていたのだが、慣れてみるとどうだろう。ISWIMやHaskellwhereのような感じで、一番上の方に本体の式が来るのは悪くないかもしれない。

LAMBDAと関数適用

LAMBDAで無名関数を作成し、(FUNC-NAME ARGS ...)で関数適用:

def test_lambda():
    assert m.run("((LAMBDA (X) (ADD X 1)) 1)") == "2"
    assert m.run("((LAMBDA (X Y) (ADD (MUL X X) (MUL Y Y))) 3 4)") == "25"

    assert m.run("(LET (INC 1) (INC . (LAMBDA (X) (ADD X 1))))") == "2"

    assert m.run("(LET ((REPEAT INC) 1) "
                     "(INC . (LAMBDA (X) (ADD X 1))) "
                     "(REPEAT . (LAMBDA (F) (LAMBDA (X) (F (F X))))))") == "3"

無名関数のまま適用したり、LETで変数束縛して呼び出したりできる。まだ最後の例ではREPEATが関数を受け取り関数を返す高階関数となっている。

LETREC

再帰的な定義を可能とするLETREC:

def test_letrec():
    assert m.run("(LETREC (FACTORIAL 5) "
                     "(FACTORIAL . "
                         "(LAMBDA (X) (IF (EQ X 0) 1 (MUL X (FACTORIAL (SUB X 1)))))))") == "120"
    assert m.run("(LETREC (FACTORIAL 5) "
                     "(FACTORIAL . (LAMBDA (X) (IF (EQ X 0) 1 (MUL X (FACTORIAL (DEC X)))))) "
                     "(DEC . (LAMBDA (X) (SUB X 1))))") == "120"

    assert m.run("(LETREC (ODD 17) "
                     "(ODD . (LAMBDA (X) (IF (EQ X 0) (QUOTE F) (EVEN (DEC X))))) "
                     "(EVEN . (LAMBDA (X) (IF (EQ X 0) (QUOTE T) (ODD (DEC X))))) "
                     "(DEC . (LAMBDA (X) (SUB X 1))))") == "T"
    assert m.run("(LETREC (EVEN 17) "
                     "(ODD . (LAMBDA (X) (IF (EQ X 0) (QUOTE F) (EVEN (DEC X))))) "
                     "(EVEN . (LAMBDA (X) (IF (EQ X 0) (QUOTE T) (ODD (DEC X))))) "
                     "(DEC . (LAMBDA (X) (SUB X 1))))") == "F"

    assert m.run("(LETREC (MAP DOUBLE (QUOTE (1 2 3 4 5))) "
                     "(MAP . (LAMBDA (F XS) (IF (EQ XS (QUOTE NIL)) XS (CONS (F (CAR XS)) (MAP F (CDR XS)))))) "
                     "(DOUBLE . (LAMBDA (X) (MUL X 2))))") == "(2 4 6 8 10)"

まずは簡単な再帰関数である階乗、そして相互再帰的なODDとEVEN、最後に高階関数のMAPを定義している。

以上でLispKit Lispの言語仕様的な部分は解説完了。

次回

次は入力文字列を構文解析して簡単なLisp的ASTに変換するパーサの話。

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサのメモリ効率化

前回まで見てきたBacktrackingパーサ、Packratパーサは「これまで見たすべてのトークン」をメモリ上のバッファに保持し続け、それらに対してのパース結果もすべてキャッシュに残し続ける実装になっていて、パース終了直前にはソースファイルのすべてのトークンがメモリに乗っている状態になってしまう。

実際にはバックトラックする予定がない場合、現在地以前にあるバッファのトークンを消してしまってもなんの問題もないし、それに対応するパース関数のキャッシュも削除できる。今回はその修正の話。

計測

まずparse関数をいじってパース終了時にtokens.bufferをプリントするようにする:

def parse(char_stream):
    _clear_caches()
    tokens = Backtrackable(xl.lex(char_stream), 2)
    _list(tokens)
    _match(tokens, t.Eof)
    print(tokens.buffer) # ここを追加

使ってみる:

>>> parse("[abc=xyz, [d, [e]=[x], f, g], x, [y=z]=[a,b]]")
[Lbrack(), Ident(s='abc'), Equal(), Ident(s='xyz'), Comma(), Lbrack(), Ident(s='d'), Comma(), Lbrack(), Ident(s='e'), Rbrack(), Equal(), Lbrack(), Ident(s='x'), Rbrack(), Comma(), Ident(s='f'), Comma(), Ident(s='g'), Rbrack(), Comma(), Ident(s='x'), Comma(), Lbrack(), Ident(s='y'), Equal(), Ident(s='z'), Rbrack(), Equal(), Lbrack(), Ident(s='a'), Comma(), Ident(s='b'), Rbrack(), Rbrack(), Eof()]

先頭の(からEofまですべてのトークンが保持されているのがわかる。

パーサ関数のキャッシュも確認:

>>> _caches
[{1: 4, 6: 7, 9: 10, 13: 14, 8: 15, 16: 17, 18: 19, 5: 20, 21: 22, 24: 27, 30: 31, 32: 33, 23: 34}, {8: 11, 12: 15, 5: 20, 23: 28, 29: 34, 0: 35}, {9: 10, 13: 14, 6: 19, 24: 27, 30: 33, 1: 34}, {1: 4, 5: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 6: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 8: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 9: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>"), 13: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>"), 16: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 18: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>"), 21: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 24: 27, 30: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 32: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>")}, {8: 15, 5: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 23: 34}, {5: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 6: 7, 8: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 9: 10, 13: 14, 16: 17, 18: 19, 21: 22, 23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 30: 31, 32: 33}]

やはり最初の方からすべて保持されている。

Backtrackableのbuffer

Backtrackableは今までバッファとしてただのPython listを使っていたが、その代替として「クリアできるバッファ」クラスを定義する:

class ClearableBuffer:
    def __init__(self):
        self._buffer = []
        self._start = 0

    def __getitem__(self, key):
        if 0 <= key < self._start:
            raise IndexError(f"Invalid access of index {key} for ClearableBuffer starting at {self._start}")
        return self._buffer[key - self._start]

    def __len__(self):
        return self._start + len(self._buffer)

    def __repr__(self):
        return repr(self._buffer)

    def append(self, item):
        self._buffer.append(item)

    def clear(self):
        if not self._buffer:
            return
        self._start += len(self._buffer) - 1
        self._buffer = self._buffer[-1:]

ほとんどListと同じAPIとなるが、x.clear()すると最後の要素だけ残して他の要素は消される。しかしアクセス用のインデックスはズレない。クリアされた要素のインデックスにアクセスしようとするとエラーになる。

使用例:

>>> xs = ClearableBuffer()
>>> for x in range(10):
...   xs.append(x)
...
>>> xs
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> xs[9]
9
>>> xs.clear()
>>> xs
[9]
>>> for x in range(10, 20):
...   xs.append(x)
...
>>> xs
[9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> xs[9]
9
>>> xs[8]
Traceback (most recent call last):
...
IndexError: Invalid access of index 8 for ClearableBuffer starting at 9

このClearableBufferBacktrackableクラスに持たせ、try_clearメソッドを追加する:

class Backtrackable:
    def __init__(self, input_, sentinel=None):
        self._stream = iter(input_)
        self.sentinel = sentinel
        self.i = 0
        self.buffer = ClearableBuffer() # ここを変更
        self.backtrack_points = []

 ...

    def try_clear(self):
        if self.backtrack_points or (self.i < len(self.buffer)-1) or (len(self.buffer) < 2):
            return False
        self.buffer.clear()
        return True

try_clearメソッドは「トークンストリームのバッファをクリアできる条件が整っているならする、そして成否を結果として返す」という関数。クリアできる条件というのは

  • バックトラック予定ではない = self.backtrack_pointsが空
  • 現在のトークンストリームの位置がバッファの最後の要素を指している
  • バッファに要素が2個以上含まれている

のすべてが満たされているというもの。

パーサ本体

この拡張を使って、パーサ関数側で折を見てバッファとキャッシュをクリアする処理を追加する。

例によってデコレータとして実装:

def _buffer_cache_clear(func):
    @functools.wraps(func)
    def f(tokens):
        if tokens.try_clear():
            _clear_caches()
        func(tokens)
    return f

バッファがクリアされた場合、キャッシュに残っているデータも必要なくなっているので同時にクリアする。前回の記事ではparse関数が呼び出されるごとに使っていた_clear_caches()をパース中にも使うようになる。

このデコレータで各パース関数を修飾する:

@_buffer_cache_clear
@_memo
def _list(tokens):
    _match(tokens, t.Lbrack)
    _elements(tokens)
    _match(tokens, t.Rbrack)

例によって他のパース関数も同じくデコレータを追加。

これでパース関数が相互再帰的に呼び出されるたびに「バッファとキャッシュがクリアできるか調べて、条件が合えばクリア」という処理が走るようになる。

使ってみる

>>> parse("[abc=xyz, [d, [e]=[x], f, g], x, [y=z]=[a,b]]")
[Comma(), Lbrack(), Ident(s='y'), Equal(), Ident(s='z'), Rbrack(), Equal(), Lbrack(), Ident(s='a'), Comma(), Ident(s='b'), Rbrack(), Rbrack(), Eof()]

>>> _caches
[{24: 27, 30: 31, 32: 33, 23: 34}, {23: 28, 29: 34, 0: 35}, {24: 27, 30: 33, 1: 34}, {23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 24: 27, 30: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 32: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>")}, {23: 34}, {23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 30: 31, 32: 33}]

パース終了時のバッファもキャッシュも元々に比べて減っているのがわかる。

今回のコード

Python Implementation of Memory-Efficient Packrat Recursive Descent Parser based loosely on Language Implementation Patterns · GitHub

次回

未定

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサのキャッシュクリア

前回のコードだとparse関数を複数回呼び出すと前回のキャッシュが残っていてパースがうまくいかない問題があった。parse呼び出しごとにキャッシュをクリアするようにしたい。

キャッシュ

xparser.pyモジュールのトップレベルにキャッシュのリストとそのリストをループしてすべてのキャッシュをクリアする関数を定義:

_caches = []

def _clear_caches():
    for cache in _caches:
        cache.clear()

_memoデコレータで作成されるキャッシュを_cachesに追加するようにする:

def _memo(func):
    d = {}
    _caches.append(d) # ここを追加

    @functools.wraps(func)
    def f(tokens):
        match d.get(tokens.i, None):
            case int(n):
                tokens.i = n
            case ValueError(_) as e:
                raise e
            case None:
                current_pos = tokens.i
                try:
                    func(tokens)
                    d[current_pos] = tokens.i
                except ValueError as e:
                    d[current_pos] = e
                    raise
    return f

あとはparse関数が呼び出されるたびに_clear_cachesするようにする:

def parse(char_stream):
    _clear_caches() # ここを追加
    tokens = Backtrackable(xl.lex(char_stream), 2)
    _list(tokens)
    _match(tokens, t.Eof)

使ってみる

>>> parse("[x=a]")
>>> parse("[[[[[")
Traceback (most recent call last):
...
ValueError: Invalid token Lbrack()
>>> parse("[abc=xyz, [d, [e]=[x], f, g]]")

前回見られた「二回目以降は第一回とトークン数が合えばパース成功、合わなければ失敗する」という挙動は修正されているようだ。

今回のコード

Python Implementation of Cache-Clearing Packrat Recursive Descent Parser based loosely on Language Implementation Patterns · GitHub

次回

Backtrackableクラスがこれまで見たすべてのトークンを不必要に保持していて、パース終了時にはソースファイルのすべてのトークンがメモリに乗っているのを修正する。

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサ

前回の記事は同じパースを何回も繰り返すので非効率だと書いたが、まずはどの程度非効率なのかを計測してからPackratパーサで効率化を図る。

計測

まずは問題の程度を計測したい。

こんなデコレータを定義する:

def _print_call(func):
    @functools.wraps(func)
    def f(tokens):
        print(f"{func} called in pos {tokens.i}")
        return func(tokens)
    return f

Pythonのデコレータは関数をとり関数を(修飾して)返す高階関数で、@decorator_nameと他の関数定義の前の行に書くことで定義される関数を修飾できる:

@_print_call
def _list(tokens):
    _match(tokens, t.Lbrack)
    _elements(tokens)
    _match(tokens, t.Rbrack)

これで_list関数は一旦定義され、その関数が_print_call関数に渡され、そして_print_call内で定義され返されるf関数が_listという名前に再束縛される(functools.wrapを使うことでf関数は外部からは_list関数そのもののように見える)。

_list以外にも_element_elements_assign_assign_list_nameといったパーサ関数にデコレータをつける。これらの関数が呼び出された場合その関数と現在のトークンストリームの位置が標準出力にプリントされる。

試してみる:

>>> parse("[abc=xyz, [d, [e]=[x], f, g]]")
<function _list at 0x10a8976d0> called in pos 0
<function _elements at 0x10a8977f0> called in pos 1
<function _element at 0x10a8975b0> called in pos 1
<function _assign at 0x10a897910> called in pos 1
<function _assign at 0x10a897910> called in pos 1
~中略~
<function _element at 0x10a8975b0> called in pos 18
<function _assign at 0x10a897910> called in pos 18
<function _name at 0x10a897b50> called in pos 18
<function _name at 0x10a897b50> called in pos 18

長いので中略したが、全部で139行出力される。重複が多く、例えば

<function _name at 0x10a897b50> called in pos 9

という行は12回出現する。

フィボナッチ数を再帰関数で算出するのが非常に非効率になるのと同じ理由で、ツリー状に分岐していく計算の至るところで同じ計算がくり返されているのが問題。そして解決法もまったく同じで、計算をメモ化してしまえばいい。

具体的にはトークンストリームの現在地に対しての成功・失敗をメモ化で記憶しておくことで、同じ地点で同じパーサ関数が適用された場合計算せずに結果を返すように変更したい。

メモ化デコレータ

今回はPackratパーサのキモであるメモ化もデコレータで実装する:

def _memo(func):
    d = {}

    @functools.wraps(func)
    def f(tokens):
        match d.get(tokens.i, None):
            case int(n):
                tokens.i = n
            case ValueError() as e:
                raise e
            case None:
                current_pos = tokens.i
                try:
                    func(tokens)
                    d[current_pos] = tokens.i
                except ValueError as e:
                    d[current_pos] = e
                    raise
    return f

デコレータの返す関数にディクショナリーをクロージャで持たせて、トークンストリームの位置であるtokens.iをキーとして「結果」をキャッシュしている。

結果として可能なのは「パースが成功した場合のトークンストリームのポジションを表す整数」と「パースが失敗した場合のValueError」の二つ。それに「キャッシュにキーが入っていない場合のデフォルト値のNone」を加えた三つのケースに対してパターンマッチしている。

パターンマッチの結果が整数だった場合は、トークンストリームのポジションをその数に変更して終了。ValueErrorだった場合はそのエラーをそのまま投げる。Noneだった場合はパース関数を呼び出してその結果をキャッシュする。

_print_callのようにパース関数を修飾する:

@_memo
def _list(tokens):
    _match(tokens, t.Lbrack)
    _elements(tokens)
    _match(tokens, t.Rbrack)

_element_elements_assign_assign_list_nameなどもすべてデコレータを付ける。

使ってみる

とりあえず計測・比較のために

@_memo
@_print_call
def _list(tokens):
    _match(tokens, t.Lbrack)
    _elements(tokens)
    _match(tokens, t.Rbrack)

のように「メモ化されていない結果を計算して返す場合のみ_print_callする」形でデコレータをつけてみる:

parsers$ python -i xparser_bt3.py
>>> parse("[abc=xyz, [d, [e]=[x], f, g]]")
<function _list at 0x104b6f7f0> called in pos 0
<function _elements at 0x104b6f9a0> called in pos 1
<function _element at 0x104b6f640> called in pos 1
<function _assign at 0x104b6fb50> called in pos 1
<function _element at 0x104b6f640> called in pos 5
<function _assign at 0x104b6fb50> called in pos 5
<function _name at 0x104b6feb0> called in pos 5
<function _assign_list at 0x104b6fd00> called in pos 5
<function _list at 0x104b6f7f0> called in pos 5
<function _elements at 0x104b6f9a0> called in pos 6
<function _element at 0x104b6f640> called in pos 6
<function _assign at 0x104b6fb50> called in pos 6
<function _name at 0x104b6feb0> called in pos 6
<function _element at 0x104b6f640> called in pos 8
<function _assign at 0x104b6fb50> called in pos 8
<function _name at 0x104b6feb0> called in pos 8
<function _assign_list at 0x104b6fd00> called in pos 8
<function _list at 0x104b6f7f0> called in pos 8
<function _elements at 0x104b6f9a0> called in pos 9
<function _element at 0x104b6f640> called in pos 9
<function _assign at 0x104b6fb50> called in pos 9
<function _name at 0x104b6feb0> called in pos 9
<function _list at 0x104b6f7f0> called in pos 12
<function _elements at 0x104b6f9a0> called in pos 13
<function _element at 0x104b6f640> called in pos 13
<function _assign at 0x104b6fb50> called in pos 13
<function _name at 0x104b6feb0> called in pos 13
<function _element at 0x104b6f640> called in pos 16
<function _assign at 0x104b6fb50> called in pos 16
<function _name at 0x104b6feb0> called in pos 16
<function _element at 0x104b6f640> called in pos 18
<function _assign at 0x104b6fb50> called in pos 18
<function _name at 0x104b6feb0> called in pos 18

今度は中略なし。全部で33行と、4分の1以下になった。

_print_callを外して使ってみる:

$ python -i xparser.py
>>> parse("[abc=xyz, [d, [e]=[x], f, g]]")

うまくいっているように見える。

しかし再起動なしに二回parseを使おうとすると問題が起きる:

$ python -i xparser.py
>>> parse("[x=a]")
>>> parse("[[[[[")
>>> parse("[abc=xyz, [d, [e]=[x], f, g]]")
Traceback (most recent call last):
...
ValueError: Failed to match Lbrack() to type <class 'xtokens.Eof'>

parseが使うパーサ関数のキャッシュが残ってしまっているので、関数を使えるのが一回限りになってしまっている。(二回目以降は第一回とトークン数が合えばパース成功、合わなければ失敗する)

今回のコード

Python Implementation of Packrat Recursive Descent Parser based loosely on Language Implementation Patterns · GitHub

次回

次回はパーサのキャッシュをparse呼び出しごとにクリアするような実装にして、何回でも利用できるように修正する話。