今年の連休の成果はスターウォーズを全編通して見たことだ（アニメ『クローン大戦』を含む）。それでちょっと思ったんだけど、Lisperにとって自分でLispを作ることは、ジェダイにとって自分でライトセイバーを作ることに似ている。おもちゃのLispなんて、少なくともSICPを読めば誰にでも書ける。とくにLispを使ってLispを書くなら、ベースにするLispのreadやシンボルのインターンが使える。今回、はじめてCでひととおりLispっぽいものを書いてみたわけだけど、やっぱり大変だったのはreadとシンボルのインターンだった。だからこんなのがきちんと実行できたのがうれしかった。

es0> (eq? (quote a) (quote a))
#tt
es1> (eq? (cons (quote a)) (cons (quote a)))
#ff

で、ジェダイならライトセイバーを自分で作るわけだ。奪ったライトセーバーを振り回すだけのグリーバス将軍とは、その点が決定的に違う。グリーバス将軍は強いけど、フォースの加護はない。フォースの加護もなしにライトセーバのような前時代の武器を使うのは、回顧趣味にほかならない。ようするにカッコつけてるわけだ。ラムダの加護もなしにLispを使うようなものだ。ポインタの加護もなしにCを使うようなものだ。ところでいまさらCのポインタの話だけど、みんな藤原博文著『Cプログラミング専門課程』を読めばいいと思う。僕がかろうじてCを全然使えないというわけでもないのはこの本があったからだ。けっこう版を重ねているのに柱（ページ番号とかある部分）に誤記が残ってるとか、編集については微妙なとこもあるけど、本当にいい本なので、曙橋界隈で藤原さんを見かけるとこっそりうれしい。

オレリスプでYコンビネータ

やっぱりリストの再帰ができないとリスプとはいえない。Yコンビネータが定義できるかやってみよう。Yコンビネータを使うと、関数に名前を付けずに再帰ができる。まあ、なんというか、「ラムダだけでここまでできる」みたいなのがうれしい。

これがYコンビネータ（"The Little Schemer"より）。

es20> (define Y 
        (lambda (le)
          ((lambda (f) (f f))
           (lambda (f) (le (lambda (x) ((f f) x)))))))

（この「Y」という名前は再帰に使うための名前じゃない。）

たとえばリストの長さを計算する関数なら、こんなふうに実現できる。ちっとも再帰関数には見えないかもだけど、Yコンビネータのなかで「再帰する」ことが抽象化されている感じ。

es24> ((Y (lambda (len)
            (lambda (l)
             (if (null? l)
                 0
                 (+ 1 (len (cdr l)))))))
       (quote (beans beans we need jelly beans)))
6.000000

なんかちゃんと動いてる！

にしても、もともと「アトムか、ドットペアか」というだけのルールでS式をパーズしようという企画だったので、いまから「'」記法を導入するのはやっかいだなあ。

あと、この例ではnull?を使っているけど、null?は組み込んではいない。null?とか自分のなかで定義するのがリスプなんだと思う。

es0> (define null? 
       (lambda (ls)
         (if (eq? (quote ()) ls)
             #t #f)))

Cによるはじめてのオレリスプ

できたよできた！とりあえず階乗の関数を定義して計算できるようになった。

k16@miffy:~/myproj/es$ ./es

es0> (define fact
        (lambda (n)
          (if (eq? n 1)
              1
              (* n (fact (- n 1))))))
fact
es1> fact    
#<closure ( n )>
es2> (fact 10)
3628800.000000
es3> 

ソースはこれ。メモリリークしまくっている状態だけど。あとで時間がとれたら感想とか書く。