Yコンビネータ復習

前にCommonLispで書いてみたんだけど、もう全然覚えてない。

書き方もひどいな。こりゃ。

というわけでもう一度やり直してみた。

今度はもう少し詳しく書く（つもり）

使ったのはallegro common lisp。

Yコンビネータができるまで

(if (zerop n)
0
(+ n (fun (1- n)))))

こんな再帰関数があったとする

呼び出すとこうなる。

cl-user> (fun 3)
6

まずこの関数から

(defun fun (n)
(if (zerop n)
0
(+ n (fun (1- n)))))

この中のfunを消したい。

引数としてここで呼び出す関数を受け取るように変えて、その引数をfuncallすればソースコード上からfunの呼び出しが消える。

(defun fun (rcf)
(lambda (n)
(if (zerop n)
0
(+ n (funcall rcf (1- n))))))

こうなりました。

再帰持に呼び出す関数をrcfとして引数で受け取る。

直接funを呼び出していた部分は(funcall rcf (1- n))とする。

funの引数には再帰呼び出しする関数を渡さないといけない。

(funcall (fun #'fun) 3)

funの呼び出しもこう変える。

で、実際に呼び出すとエラーになる。

cl-user> (funcall (fun #'fun) 3)
`#<Interpreted Closure (:internal fun) @ #x20822f1a>' is not of the
expected type `number'
[Condition of type type-error]

そう。funは呼び出す関数を受け取るようになっているのに

(+ n (funcall rcf (1- n))))))

の部分では(1- n)を渡すままになってるのが問題。

これでは動かない。ここも書き換えよう。

funは

?関数を受け取って

?数値を受け取って数値を返す関数を返す

関数。

自分自身を呼び出してほしいのだから引数には自分自身を渡す。

要は(funcall (fun #’fun) 3)と同じことをすればいい。

(+ n (funcall rcf (1- n))))))
　　　　　　　↓
(funcall rcf rcf)

これで?がかえってくるので、これに(1- n)を渡せばいい

(+ n (funcall rcf (1- n))))))
　　　　　　　↓
(+ n (funcall (funcall rcf rcf) (1- n))))))

結果、こんな感じになる。

(defun fun (rcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall (funcall rcf rcf) (1- n))))))
cl-user> (funcall (fun #'fun) 3)
6

呼び出しが(funcall (fun #’fun) 3)なのは面倒なので

(defun fun (rcf)…

をmake-funに改名して裏方に回す。

んで別のfunを作る。

こんな感じにする。

(defun make-fun (rcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall (funcall rcf rcf) (1- n))))))
(defun fun ()
(make-fun #'make-fun))
cl-user> (funcall (fun) 3)
6

なんでfunを

(defun fun (n)
(funcall (make-fun #'make-fun) n))

にしないのかは内緒。

このあたり、funcallのいるcommonlispは辛いな・・・。

(defun make-fun (rcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall (funcall rcf rcf) (1- n))))))
(defun fun ()
(make-fun #'make-fun))

次に(funcall (funcall rcf rcf) (1- n)部分をローカル関数に切り出す。

こんな感じになった。

(defun make-fun (rcf)
(labels ((callrcf (m) (funcall (funcall rcf rcf) m)))
#'(lambda (n)
(if (zerop n)
0(+ n (callrcf (1- n)))))))
(defun fun ()
(make-fun #'make-fun))
cl-user> (funcall (fun) 3)
6

(defun make-fun (rcf)
(labels ((callrcf (m) (funcall (funcall rcf rcf) m)))
#'(lambda (n)
(if (zerop n)
0(+ n (callrcf (1- n)))))))
(defun fun ()
(make-fun #'make-fun))

今、こうなってるんだけど、もともとの処理をしている部分って枠の部分だけだよね？

「枠の部分に相当する処理を行う関数」を受け取って「make-funに相当する関数」を返す関数を作れば汎用的にならないか？

#'(lambda (n)
(if (zerop n)
0(+ n (callrcf (1- n)))))))

囲み部分に相当する関数を受け取とるということは。。。

(defun make-f (f) ...

こんな感じで引数として関数を受け取って。。。

make-funに相当する関数を返すんだから。。。。

(defun make-f(f)
#'(lambda (rcf) ...

こんな感じ。

あとはcallrcfの定義があって、実際の処理の代わりに引数のfをfuncallする。

全体はこんな感じ。

(defun make-f(f)
#'(lambda (rcf)
(labels ((callrcf (m) (funcall (funcall rcf rcf) m)))
(funcall f #'callrcf))))
(defun fun-impl(crcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall crcf (1- n))))))
(defun fun ()
(funcall (make-f #'fun-impl) (make-f #'fun-impl)))
cl-user> (funcall (fun) 3)
6

fun-implはmake-fに渡す関数。実際の再起処理を書いてある。こいつをmake-fに渡せば、make-fun相当のクロージャが返ってくる。

これで、make-funは(make-f #’fun-impl)で置き換えられることになる。

だからfunの定義は

(defun fun ()
(make-fun #'make-fun))

から

(defun fun ()
(funcall (make-f #'fun-impl) (make-f #'fun-impl)))

に変わってる。

さて次に

(defun fun ()
(funcall (make-f #'fun-impl) (make-f #'fun-impl)))

を考える。

これも汎用化しよう。

リテラルで#’fun-implをmake-fの引数に渡してしまっているが、これも外から受け取るようにしてしまう。

ちょっと気が早いけど名前もYに変えよう。

(defun Y (f)
(funcall (make-f f) (make-f f)))
(defun make-f(f)
#'(lambda (rcf)
(labels ((callrcf (m) (funcall (funcall rcf rcf) m)))
(funcall f #'callrcf))))
(defun fun-impl(crcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall crcf (1- n))))))
(defun fun(n)
(funcall (Y #'fun-impl) n))
cl-user> (fun 3)
6

だいたいできた。

あとは細かい調整。

まず、make-fのlabelsにある関数をリテラルで展開してしまおう。

(defun make-f(f)
#'(lambda (rcf)
(labels ((callrcf (m) (funcall (funcall rcf rcf) m)))
この関数をリテラルにして
(funcall f #'callrcf))))
直接この引数に入れてしまう。

こんな感じになりました。

(defun Y (f)
(funcall (make-f f) (make-f f)))
(defun make-f(f)
#'(lambda (rcf)
(funcall f #'(lambda (m) (funcall (funcall rcf rcf) m)))))
(defun fun-impl(crcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall crcf (1- n))))))
(defun fun(n)
(funcall (Y #'fun-impl) n))
cl-user> (fun 3)
6

もう少し調整。

(defun Y (f)
(funcall (make-f f) (make-f f)))

この部分のmake-fもリテラルを直接引数にしてしまう。

これでmake-f関数が消えた。

Yコンビネータできた！

(defun Y (f)
(funcall
(funcall
#'(lambda (f)
#'(lambda (rcf)
(funcall f #'(lambda (m) (funcall (funcall rcf rcf) m))))) f)
(funcall
#'(lambda (f)
#'(lambda (rcf)
(funcall f #'(lambda (m) (funcall (funcall rcf rcf) m))))) f)))
(defun fun-impl(crcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall crcf (1- n))))))
(defun fun(n)
(funcall (Y #'fun-impl) n))
cl-user> (fun 3)
6

λ式で書ききるとこんな感じ。

(funcall #'(lambda (n)
(funcall
(funcall
#'(lambda (f)
(funcall
(funcall
#'(lambda (f)
#'(lambda (rcf)
(funcall f #'(lambda (m) (funcall (funcall rcf rcf) m))))) f)
(funcall
#'(lambda (f)
#'(lambda (rcf)
(funcall f #'(lambda (m) (funcall (funcall rcf rcf) m))))) f)))
#'(lambda (crcf)
#'(lambda (n)
(if (zerop n)
0(+ n (funcall crcf (1- n)))))))
n))
3)