読者です 読者をやめる 読者になる 読者になる

kb84tkhrのブログ

何を書こうか考え中です

Scheme手習い(17) Yコンビネータ(2)

defineなしで再帰を実現できたものの、わかった感が薄くて今ひとつ

  • eternityの唐突感
  • (mk-length mk-length)の手品感

このあたりを解決しないと眠れそうにありません
いえ寝ます
いえ自分なりに納得感のある道を探してみます
厳密さよりも感覚的に納得できるような方向で

まずはlengthからスタート
defineを使わずに同じことを書けたら勝ち

(define length
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (length (cdr l)))))))

defineが使えないので取ります

(lambda (l)
  (cond ((null? l) 0)
        (else (add1 (length (cdr l))))))

が残っていてはいけないので、仮にselfという名前を入れておきます

(lambda (l)
  (cond ((null? l) 0)
    (else (add1 (self (cdr l))))))

このままではselfが定義されてないよと怒られてしまうので、lambdaの仮引数にしてしまいましょう

(lambda (self)
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (self (cdr l)))))))

これで一応ちゃんとした関数になりました
あとはselfに元の関数を入れてやれば再帰するんじゃ?
正確には自分自身じゃないけど、同じコードならいいよね?
同一人物じゃないけど双子の弟みたいな

((lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (self (cdr l)))))))
 (lambda (l)
   (cond ((null? l) 0)
         (else (add1 (self (cdr l)))))))

ほらほらほら
もうできちゃったんじゃないの?

> (((lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 (self (cdr l)))))))
    (lambda (l)
      (cond ((null? l) 0)
            (else (add1 (self (cdr l)))))))
   '(1 2 3))
self: undefined;

あーそうですねー外側のselfは定義されてないですねー
馬鹿ですねー
外側のselfがエラーにならないようにするにはどうすればいいでしょう?

じー

そうか、外側の関数も引数でself自身を受け取るようにすればいいですね!
こう

((lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (self (cdr l)))))))
 (lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (self (cdr l))))))))

おっといけない
このselfは自分自身を引数に取って、つまり(self self)となって初めて
さっきまでのselfになるのでいじってやらないと

((lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 ((self self) (cdr l)))))))
 (lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 ((self self) (cdr l))))))))

これでもう動かない理由はないはず

> (((lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((self self) (cdr l)))))))
    (lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((self self) (cdr l))))))))
   '(1 2 3))
3

動きました

(lambda (self) ...)が2箇所あります
これはself自身なのでselfと名前をつけましょう

((lambda (self)
   (self self))
 (lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 ((self self) (cdr l))))))))

できましたね

> (((lambda (self)
      (self self))
    (lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((self self) (cdr l))))))))
   '(1 2 3))
3

(self self)(self self)を呼び続ける、ってことですね
selfself自身を呼び出せればいいんだけど
selfself自身のことを知らないからselfを渡してやる、と
いったところでしょうか

あれこれ考えてるうちにこの関数も普通に再帰に見えてきましたよ