2008/05/13


今年の連休の成果はスターウォーズを全編通して見たことだ(アニメ『クローン大戦』を含む)。それでちょっと思ったんだけど、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を全然使えないというわけでもないのはこの本があったからだ。けっこう版を重ねているのに柱(ページ番号とかある部分)に誤記が残ってるとか、編集については微妙なとこもあるけど、本当にいい本なので、曙橋界隈で藤原さんを見かけるとこっそりうれしい。

2008/05/06

オレリスプで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)))


2008/05/05

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