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