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

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

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

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

LispKit Lispの紹介　（本記事）
パーサとAST
インタプリタ前編後編
SECD抽象機械の実装　1 2 3
SECD機械語へのコンパイラ
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やHaskellのwhereのような感じで、一番上の方に本体の式が来るのは悪くないかもしれない。

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に変換するパーサの話。

Arantium Maestum

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

LispKit Lisp処理系の実装　序