kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

Scheme手習い(19) Yコンビネータ(4)

Yコンビネータでいろいろな関数を動かしてみます

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

再帰しない関数を渡しても動くかな

((Y (lambda (add2) (lambda (n) (add1 (add1 n))))) 1)
⇛ 3

動いた!

じゃあ、2引数の関数は?

((Y
  (lambda (member?) 
    (lambda (a lat)
      (cond ((null? lat) #f)
            ((eq? (car lat) a) #t)
            (else (member? a (cdr lat)))))))
 'c '(a b c))
⇛ エラー

(f f)は引数をひとつしか取らないもんなあ
頭使わずに解決してみます

(define Y2
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x y) ((f f) x y)))))))

((Y2
  (lambda (member?) 
    (lambda (a lat)
      (cond ((null? lat) #f)
            ((eq? (car lat) a) #t)
            (else (member? a (cdr lat)))))))
 'c '(a b c))
⇛ #t     

動きました
でも引数の数ごとにY作んなきゃいけないとか頭使わなさすぎです

じゃあ、カリー化したら?

(((Y
   (lambda (member?) 
     (lambda (a)
       (lambda (lat)
         (cond ((null? lat) #f)
               ((eq? (car lat) a) #t)
               (else ((member? a) (cdr lat))))))))
  'c) '(a b c))
⇛ #t

動きました
リストの中にcを含むかどうかを判定する関数を作り、その関数を(a b c)に適用しています
細かく考えだすと頭がパンク気味です

カリー化って、引数の順番どうなんですかね
並んだ引数のなかで特別扱いがひとつだけ

(((Y
   (lambda (member?) 
     (lambda (lat)
       (lambda (a)
         (cond ((null? lat) #f)
               ((eq? (car lat) a) #t)
               (else ((member? (cdr lat)) a)))))))
  '(a b c)) 'c)
⇛ #t

当然ながらこれでも動きます
引数の順番は考えて決めましょう

3引数は?
2回カリー化するのかな?
いや1回だけでよさそうです

(((Y
   (lambda (insertR)
     (lambda (lat)
       (lambda (old new)
         (cond ((null? lat) (quote ()))
               ((eq? (car lat) old) (cons old (cons new (cdr lat))))
               (else (cons (car lat) ((insertR (cdr lat)) old new))))))))
  '(a b c)) 'b 'd)
⇛ (a b d c)

oldnewlatの組に分けるのはブサイクな気がしたのでlatを外に出しました

*関数も動きました

(((Y
   (lambda (rember*)
     (lambda (a)
       (lambda (l)
         (cond ((null? l) (quote ()))
               ((atom? (car l))
                (cond ((eq? (car l) a) ((rember* a) (cdr l)))
                      (else (cons (car l) ((rember* a) (cdr l))))))
               (else (cons ((rember* a) (car l)) ((rember* a) (cdr l)))))))))
  'b) '((a b c) a b c))
⇛ ((a c) a c)

入れ子になった再帰はどうでしょうか?

(((Y
   (lambda (o*)
     (lambda (n)
       (lambda (m)
         (cond ((zero? m) 0)
               (else (((Y
                        (lambda (o+)
                          (lambda (m)
                            (lambda (n)
                              (cond ((zero? n) m)
                                    (else ((o+ (add1 m)) (sub1 n)))))))) 
                       n) ((o* n) (sub1 m)))))))))
  2) 3)
⇛ 6

動きました

o+に名前をつけてやれば見やすいかな?

((((lambda (o+)
     (Y
      (lambda (o*)
        (lambda (n)
          (lambda (m)
            (cond ((zero? m) 0)
                  (else ((o+ n) ((o* n) (sub1 m))))))))))
   (Y
    (lambda (o+)
      (lambda (n)
        (lambda (m)
          (cond ((zero? m) n)
                (else (add1 ((o+ n) (sub1 m))))))))))
  2) 3)

o*にも名前をつけてやってもいいですね

((lambda (o+)
   ((lambda (o*)
      ((o* 2) 3))
    (Y
     (lambda (o*)
       (lambda (n)
         (lambda (m)
           (cond ((zero? m) 0)
                 (else ((o+ n) ((o* n) (sub1 m)))))))))))
 (Y
  (lambda (o+)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) n)
              (else (add1 ((o+ n) (sub1 m))))))))))

じー

じー

名前をつけて呼び出す・・・だと・・・?

(define ...)は何ですか。

もしかして、これがdefineってこと?

(define ... )は正しく動作するといえますか。

defineは実はlambdaだから正しく動作する?

確かに。いまや再帰とは何かを知っています。

再帰だけちょっと心配だったけど、Yがあれば書けるし?

そういうことなんでしょうか?

defineにしちゃちょっとスコープ的にうるさい感じがしますが
というのは、こういう書き方ではうまくいかなかったので

((lambda (o* o+)
   ((o* 2) 3))
 (Y
  (lambda (o*)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) 0)
              (else ((o+ n) ((o* n) (sub1 m)))))))))
 (Y
  (lambda (o+)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) n)
              (else (add1 ((o+ n) (sub1 m))))))))))

o*からo+が見えてないんです
見た目はきれいなだけに残念
入れ子にして書けばいいんですが
ちょっと書き方変えるぐらいでうまくいかないかなあ

入れ子にして書かなきゃいけないとすると相互に呼び合う関数は大丈夫かと気になります
こういうのとか

(define ev?
  (lambda (n)
    (cond ((zero? n) #t)
          (else (od? (sub1 n))))))

(define od?
  (lambda (n)
    (cond ((zero? n) #f)
          (else (ev? (sub1 n))))))

どうやって書きましょう
od?を埋め込んじゃいましょうか

((Y
  (lambda (ev?)
    (lambda (n)
      (cond ((zero? n) #t)
            (else ((lambda (n)
                     (cond ((zero? n) #f)
                           (else (ev? (sub1 n)))))
                   (sub1 n)))))))
 3)

これはこれで動きますが、od?を作ろうと思ったらほとんど同じコードをもう一度書かないといけません
かなり癪に障ります

こんなふうに書いて動かないかなーと思いましたが無理でした
やっぱりev?からはod?が、od?からはev?が見えません

((lambda (ev? od?)
   (od? 3))
 (lambda (n)
   (cond ((zero? n) #t)
         (else (od? (sub1 n)))))
 (lambda (n)
   (cond ((zero? n) #f)
         (else (ev? (sub1 n))))))

さて。

ev?からod?が呼べる必要があり、od?からev?が呼べる必要がある、というのは
lengthからlengthを呼び出す必要がある、というのと似ています
Yコンビネータを作るときのやり方で1から作ってみます

まずは呼びたい関数を引数に取るようにします
ev?に当たる関数からはod?を呼び出しますのでev?ではなくod?を引数に取るというのが
今までと違います

;ev?に似た関数
(lambda (od?)
  (lambda (n)
    (cond ((zero? n) #t)
          (else (od? (sub1 n))))))
;od?に似た関数
(lambda (ev?)
  (lambda (n)
    (cond ((zero? n) #f)
          (else (ev? (sub1 n))))))

次に、今作った関数に名前をつけます。

((lambda (e? o?)
   'ここはあとで考える)
 ;ev?に似た関数
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 ;od?に似た関数
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

ev?に似た関数、od?に似た関数から、mk-ev?mk-ed?を作ります
mk-ev?mk-ev?mk-od?も使いますので、2引数を取る関数になります
ちょっとめんどくさい

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      'ここはあとで考える)
    ;mk-ev?
    (lambda (mk-od? mk-ev?)
      (e? (mk-od? mk-ev? mk-od?)))
    ;mk-od?
    (lambda (mk-ev? mk-od?)
      (o? (mk-ev? mk-od? mk-ev?)))))
 ;ev?に似た関数
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 ;od?に似た関数
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

このままだとやっぱり止まらないのでlambdaで囲みます

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      'ここはあとで考える)
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

関数を返してできあがり・・・なんですが関数を2つ返すことができません
(mk-ev? mk-od? mk-ev?)を返せばev?
(mk-od? mk-ev? mk-od?)を返せばod?になります

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      (mk-od? mk-ev? mk-od?))
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

ev?od?に名前を付けて両方使えるようにするにはどうするといいでしょう?
関数をふたつ返すことはできませんから中で使う?

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      ((lambda (ev? od?)
         (display (ev? 2)) (newline)
         (display (ev? 3)) (newline)
         (display (od? 2)) (newline)
         (display (od? 3)) (newline))
       (mk-ev? mk-od? mk-ev?)
       (mk-od? mk-ev? mk-od?)))
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))
⇛ #t
  #f
  #f
  #t

動きました
動いたんですけどここまでしないといけないかとちょっと疑問
ちょっと変えるだけとか、せめてYを2回使うくらいでできないもんですかね

Scheme手習い(18) Yコンビネータ(3)

関数を再帰させることができればYコンビネータも峠を越えたんじゃないでしょうか
あとは、形を整えてやるだけのはずですから

defineなしで再帰できるようになったlengthがこれ

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

先回りして目指す形はこれ

((lambda (le)
   ((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (le (lambda (x)
            ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (length (cdr l))))))))

↓の、「lengthに似た関数」(なんか名前ないのかな)を与えれば再帰する関数になる
便利な関数を取り出したいってことです

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

元の形と目指す形を見比べると、(lambda (l) ...)の部分が
lengthに似た関数」の中身に似てますね
元の形の(mk-length mk-length)lengthに相当してるので
(mk-length mk-length)lengthと名前をつけてやります

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

これで、「lengthに似た関数」の形が作れました
めでたしめでたし、ではなくて

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      ((lambda (length)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))
       (mk-length mk-length))))
   '(1 2 3))
(応答なし)

帰ってきません
しばらくすると「このプログラムはメモリを使いきりました」

何がおかしかったのか追ってみます
評価するには関数と引数を評価してやる必要がありますが
引数はこれ以上評価することはできませんので放置し関数部分に着目します

関数部分がまた(関数 引数)という形ですので上のlambdamk-length
下のlambdaを入れてやります

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

わかりづらくなってきましたが前回で初めて再帰したバージョンの形に似ています
全体を見るとやはり(関数 引数)という形ですので上のlambdamk-length
下のlambdaを入れてやります

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

引数のほうが、一つ前に出てきた関数とそっくりの形になりました
引数自体が(関数 引数)という形ですのでこれを評価しようとすると
また同じ形が出てきて再現がありません

mk-lengthを自分自身に何度も何度も適用し続けているからです

そのとおりですね
なにせ

再帰とはどんなものですか。
任意の関数へのmk-lengthの適用が無限に連鎖しているようなものです。

というくらいですから
まさしく文字通りにできあがりました

実際は無限に続けなくても、リストの長さを出すのに十分なだけ繰り返したら
やめてしまっていいんですが
完全に関数の形が確定するまで続き、途中でやめちゃうことはできないってことなんでしょうね

(mk-length mk-length)に名前をつける前はなぜうまくいっていたかというと
elseの中に入っていたので必要なときにしか評価されなかったからということでしょう

一見無限に評価が続いてしまいそうだけど必要な分だけ評価すればいい、っていうと
Haskellで書けば解決しそうな気もしますが軽く検索してみたところでは
別の問題があって簡単じゃないようです

lengthを作る関数から

(mk-length mk-length)

を抽出した以上、それはそれ以上関数を返してはいません。

意味がわかりません
それって何
誰かおしえてください

でどうするかっていうと、ここが山場2かと思いますけど、

(mk-length mk-length)が1引数の関数を返すとすると、
(lambda (x) ((mk-length mk-length) x))も1引数の関数を返しますか。

返しますね
それが何か?

それでは、以上のことをmk-lengthの自分自身への適用に対して行ってみましょう。

本ではなぜか(mk-length mk-length)をくくりだす前に戻ってコレやってから
あらためてくくり出し直してますが理由は読み取れてません
くくりだした形のほうで(mk-length mk-length)lambdaに入れてやっても
同じ形ができあがります

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

これでまた動くようになってます

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      ((lambda (length)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))
       (lambda (x) ((mk-length mk-length) x)))))
   '(1 2 3))
3

(mk-length mk-length)(lambda (x) ((mk-length mk-length) x))
書き換えたら何が起こって動くようになったんでしょうか

さっきと同じように評価していくと、同じようなステップをたどってこうなります

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

これも(関数 引数)の形ですが、引数の方がさっきは(関数 引数)の形だったものが
今度は(lambda (x) ((関数 引数) x))になってます
これは関数適用ではなくてひとつのラムダ式なのでそのままで関数を適用できます
ここがミソかな

適用するとこうです

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

こんどは全体がひとつのラムダ式になりました
((lambda (x) ((mk-length mk-length) x)) (cdr l))を評価することになるのは
(null? l)が偽のときだけ
つまり必要な時しか評価しない、が実現されています
ここもミソだな

なのでこれでいったん評価が終わったことになって
この関数を(1 2 3)に適用してやると想定どおり3が返されるというわけです

ふう

いよいよ「lengthに似た関数」に名前をつけて外に出してやります
lengthに似た関数」は一番外に出してやりたいので、全体をlambdaで囲みます
lengthに似た関数」にはleという名前をつけます

((lambda (le)
   ((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (le (lambda (x) ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

動きます

> (((lambda (le)
      ((lambda (mk-length)
         (mk-length mk-length))
       (lambda (mk-length)
         (le (lambda (x) ((mk-length mk-length) x))))))
    (lambda (length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l))))))))
   '(1 2 3))
3

コレが完成版で上半分が適用順Yコンビネータと呼ばれてるそうです

たぶん(mk-length mk-length)が裸のままの形が素のYコンビネータ

なんで「適用順」Yコンビネータっていう名前なんでしょうね?
適用順に何かする、というより適用順に評価する処理系でも動くよ、っていう感じですが

(define ... )は正しく動作するといえますか。

言えるんですか?

確かに。いまや再帰とは何かを知っています。

再帰が何かを知っているのとdefineの動作とどういう関係があるんでしょうか
Yコンビネータの話のとっかかりは

(define ...)は何ですか
興味深い質問です。(define ...)will-stop?に対しては
うまく働かないことを見たばかりです。

でしたが何か解決したんでしょうか
わかりません

(Y Y)は何ですか。

想像もつきません

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

(lambda (le)
  ((lambda (f) (f f))
   (lambda (f) (le (lambda (x) ((f f) x))))))

ってなんとなく形は似てますけどね

何ともいえませんが一生懸命に動きます。

とにかくメモリを使いきってくれることはわかりました

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を渡してやる、と
いったところでしょうか

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

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

ラスボス1来ました

Yコンビネータってのはこれ
正確には適用順Yコンビネータって言うらしいです

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

何がなんだかわかりません
こんなの読んでふむふむとかわかっちゃう人がいるんでしょうか
恐ろしいです

順番に見ていくしかありません

(define ...)は何ですか。

何でしょうか

では、再帰的定義とは何ですか。

何でしょう
哲学でしょうか

これはあのlength関数ですか。

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

そうですね

次の関数は何をするものでしょう。

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

なんでしょうか
lengthとそっくりですけど、eternityってあの無限ループするやつでしょうか

空リストの長さを決めますが、ほかには何も決めません。

確かにおっしゃるとおりです
「決める」より「求める」と書いたほうが馴染みがある感じ

> ((lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (eternity (cdr l))))))
   '())
0
> ((lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (eternity (cdr l))))))
   '(1))
(応答なし)

eternityの次くらいに部分的な関数ですね

この関数は便宜上length0と呼びます
eternityのところをlength0自身に置き換えてやると
判定できる要素数がひとつ増えて空リストまたは1要素のリストの長さを求める関数になります

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

これはlength1
この調子でlength2、length3とどんどん置き換えてやれば
任意の数までの要素を含むリストの数が数えられるようになります

でも無限の関数は書くことはできません。

そうですね

これらのプログラムにはすべてlengthに似た関数があります。おそらくこの関数を抽象化する必要があるのでしょう。

どんどん置き換えるかわりに関数呼び出しにするってことですね
DRY原則

lengthと似ているけれども(lambda (length) ...)で始まる関数が必要です。

なにがしたいんでしょうか

このことでしょうか。

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

ははーん
defineで名前を付けられないからlambdaの引数にして名前を付けるってわけですね
どうやらここがひとつのミソ

これはlength0を生成します。

たしかに、lengtheternityに置き換えてやればlength0そのものです
length1は以下のようになります
length0のeternityの部分をlength0に置き換えてやればできあがり

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

引数を置き換えてやればlength1になることはすぐ確認できます
length2から先も同様
でもなにかよくなったんでしょうか?
eternityのあたりでひとひねりしたらいいことありそうな予感はします

近いですが、まだ繰り返しがあります。

そうですね。コピペコーディングはよくないです

lengthを引数として取り、lengthに似た関数を返す関数に名前をつけましょう。

lengthを引数として取り、lengthに似た関数を返す関数」っていうのはこれですね

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

名前をつけるにはlambdaの引数にすればいいんでした

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

これで、...のところでは「lengthを引数として取り、lengthに似た関数を返す関数」を
mk-lengthと書けるようになりました
lengthを引数として取り、lengthに似た関数を返す関数」にeternityを渡したものが
length0でしたので、length0はこうなります

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

length0のeternityのところをlength0自身に置き換えるとlength1になるんでした

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

おお、重複が消えました
D・R・Y! D・R・Y!
これでたくさん書いても平気です

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

あとは無限に書けばできあがり!

再帰とはどんなものですか。

任意の関数へのmk-lengthの適用が無限に連鎖しているようなものです。

任意の関数?
ってeternityのこと?

実際に無限の連鎖が必要ですか。

もちろん、そんなことはありません。

長さを調べたいリストは有限ですもんね

何回必要かを推測することはできるでしょうか。

長くても100個まで、とか仕様書に書いてあればいいんですけどそうでなければ無理
たぶん100個くらいで充分なんで、とか言ったら品証の人が怒るんじゃないですかね

十分に大きな数を推測しなかったことはいつわかりますか。

最も内側のmk-lengthに渡されたeternityを実行するときです。

eternityを呼んじゃったら負けですね

この時点でeternityに対してmk-lengthをもう一回実行するように書くとどうなりますか。

言ってる意味がわかりません

どんな関数がmk-lengthに渡されるのか誰も気にしないので、

どうせeternityは呼ばれちゃいけないので、何を渡しても同じ
だからさっき「任意の関数」って言ってたんですね

最初にmk-lengthを渡すこともできますね。

まあいいんじゃないですかね
なんで渡したいのか知りませんけど

そうすれば、eternityに対してmk-lengthを適用した結果をcdrに対して
適用することで、連鎖をもう一段先に進めることができます。

ええとどういうことですか
ええとええと

長過ぎるリストを引数にとったとき、これまで(eternity (cdr l))ってなってた呼び出しが
((mk-length eternity) (cdr l))になってくれるってことですかね

最初にeternityを渡すのをやめてmk-lengthを渡すってことは、

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

eternitymk-lengthに変えるってことですね

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

eternityがどっかいっちゃいました
さっき思ってたことと違いますね
わかりません!

脳内で動かしてみます
空リストを渡せば0が返ります

空でないリストを渡すとlength0は無限ループに入りましたがこれはどうなるでしょう
連鎖がもう一段先に進むでしょうか?
(1)を渡してみます
lnull?ではないので、(length (cdr l)) つまり(mk-length '())が呼ばれます
ここでmk-length(lambda (length) ...)lengthには'()が渡されます
なんかおかしいです

さらにlengthmk-lengthという名前に変更することさえできます。

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

どういうリファクタリングでしょうか
間違いじゃないのはわかるんですけど

なぜ、こんなことをしたいのでしょうか。

気になりますね

すべての名前は同等ですが、ある名前はほかのものよりさらに同等なのです。

何を言っているんでしょうか

そうです。名前は一貫性を持って使えば、それでよいのです。

いややっぱ目的が見えてないと

そしてmk-lengthlengthよりさらに同等な名前なのです。

そう言われてもわかりませんが、今や渡されてるのはmk-lengthですからね
そういうことでしょうか

mk-lengthmk-lengthに渡される今となっては、この引数をさらなる再帰
生成するのに使えますか。

はい。mk-lengthを1回適用すればlength1が得られます。

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

mk-length(mk-length eternity)になりました
(mk-length eternity)はまんまlength0ですので
さっきと違って再帰呼び出しがエラーになりません
全体としてはlength1になります

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

の値はなんですか。ここでl(apples)です。

ここは練習

  (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l))))))))
   '(apples))

スタート
全体を見ると1〜6行目が関数で、7行目が引数
引数はこのままでいいので関数の方を変形します
1〜6行目の中では、1〜2行目が関数で、3〜6行目が引数
(mk-length mk-length)mk-lengthを3〜6行目のコードで置き換えます

= (((lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l)))))))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l))))))))
   '(apples))

今度は、1〜4行目の関数に、5〜8行目の関数を引数として与えます

= ((lambda (l)
     (cond ((null? l) 0)
           (else (add1 (((lambda (mk-length)
                           (lambda (l)
                             (cond ((null? l) 0)
                                   (else (add1 ((mk-length eternity) (cdr l))))))) 
                         eternity) (cdr l))))))
   '(apples))

1〜7行目の関数に、(apples)を引数として与えます
内側のlは内側のlambdaの引数なので置き換えません

= (cond ((null? '(apples)) 0)
        (else (add1 (((lambda (mk-length)
                        (lambda (l)
                          (cond ((null? l) 0)
                                (else (add1 ((mk-length eternity) (cdr l))))))) 
                      eternity) (cdr '(apples))))))

(null? '(apples))ではないので、

= (add1 (((lambda (mk-length)
            (lambda (l)
              (cond ((null? l) 0)
                    (else (add1 ((mk-length eternity) (cdr l))))))) 
          eternity)
         '()))

1〜4行目の関数に、eternityを引数として与えます
あとはもういいかな

= (add1 ((lambda (l)
           (cond ((null? l) 0)
                 (else (add1 ((eternity eternity) (cdr l)))))) 
         '()))
= (add1 (cond ((null? '()) 0)
              (else (add1 ((eternity eternity) (cdr '()))))))
= (add1 0)
= 1

できました
複雑な形でどこから手をつければいいか悩みますが、感覚でなんとか

これは2回以上できますか。

はい。mk-lengthを自分自身に渡し続ければ、必要なだけ実行することができます。

次の関数はなんと呼ぶのがよいでしょう。

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

もちろん、lengthです。

ああそうですね
理屈上はね

ってこれ動くの!

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

てっきりYコンビネータが完成するまで動かないものだと思ってました
動くと思ってみればたしかに動かない理由はないですね
(mk-length mk-length)がつまりlengthそのものって感じ

Scheme手習い(15) 部分関数と全関数(2)

部分関数と全関数の話その2

コラッツの関数と呼ばれるやつ

  • 1なら終わり
  • 偶数なら2で割る
  • 奇数なら3を掛けて1を足す

たったこれだけの関数なのに、必ず終わるかどうか、つまり全関数かどうかは証明されていません
きっと全関数だろうとは思われてるみたい

(define C
  (lambda (n)
    (cond ((one? n) 1)
          (else (cond ((even? n) (C (o/ n 2)))
                      (else (C (add1 (o* 3 n)))))))))

終わるときはいつも1を返すんですけどさすがに面白くないので
何回再帰呼び出ししたかを返すようにしてみました

(define C2
  (lambda (n c)
    (cond ((one? n) c)
          (else (cond ((even? n) (C2 (/ n 2) (add1 c)))
                      (else (C2 (add1 (* 3 n)) (add1 c))))))))

(define C2list
  (lambda (n to)
    (display (format "~a " (C2 n 0)))
    (cond ((= (modulo n 10) 0) (newline)))
    (cond ((< n to) (C2list (add1 n) to)))))

1から100までの値を表示させてみました

0 1 7 2 5 8 16 3 19 6 
14 9 9 17 17 4 12 20 20 7 
7 15 15 10 23 10 111 18 18 18 
106 5 26 13 13 21 21 21 34 8 
109 8 29 16 16 16 104 11 24 24 
24 11 11 112 112 19 32 19 32 19 
19 107 107 6 27 27 27 14 14 14 
102 22 115 22 14 22 22 35 35 9 
22 110 110 9 9 30 30 17 30 17 
92 17 17 105 105 12 118 25 25 25 

わかりません

突然100を超えることがあるんでコンピュータが計算してくれるのでなければ確かめる気がしません
n = 31で106になりますがその後そんなに増えていってる感じはしません
100000までやってみたら350が最高でした
コンピュータさまさまです
100000までの値で最大値を更新したところだけプロットしてみました

f:id:kb84tkhr:20160515130512p:plain

なんか対数っぽいのでX軸を対数目盛に

f:id:kb84tkhr:20160515130628p:plain

これはよく乗ってると言っていいんでしょうか
ガウス素数定理みたいな?
まあでも素数と「3を掛けて1を足す」とかじゃ格が違う感じ

あと2回、3回と同じ数字が続くことが多いですね
これはかなり不思議
となりあった数のコラッツ数(って言うのかな)が同じになりやすい理由って特に思いつかないんですが


アッカーマン関数

(define A
  (lambda (n m)
    (cond
      ((zero? n) (add1 m))
      ((zero? m) (A (sub1 n) 1))
      (else (A (sub1 n) (A n (sub1 m)))))))

今度は

Aは常に答えを返しますか。

はい、全関数です。

だそうなので安心して(?)ちょっと計算させて、一般項を予想してみました

(A 0 n) = n + 1
(A 1 n) = n + 2
(A 2 n) = 2n + 1
(A 3 n) = 2^(n+3) - 3

増え方の増え方が激しいです

(A 4 0) = 13 = 2^2 - 3
(A 4 1) = 65533 = 2^2^2^2 - 3

(A 4 2)は計算が終わらないのであきらめました

手がかりが少なすぎてわかりませんけれども2乗を2(n+1)回繰り返す、であっても大変
ヘタして2乗を2^(n+1)回繰り返す、だったらとんでもない増え方です
足す1と引く1と再帰呼び出ししか使ってないのに

(A 5 n)なんて想像するだに恐ろしい

アッカーマン関数はものすごい増え方をする関数ですが
巨大数マニアにとってはまだまだ入り口にすぎないようです
面白いかも?と思われた方はこちらをどうぞ

(A 4 3)は何ですか。

現実的な問題として、答えは得られないでしょう。

どういう意味ですか。

(A 4 3)の値が求まるずっと前に、今読んでいるページは朽ち果ててしまうでしょう。

全関数だからといって油断してると大変なことになるよというお話

そこで
ある関数が停止するかを判定してくれるwill-stop?という関数があるといいなあ
と話が続きますが残念ながらそうは問屋がおろしてくれません
関数自身を処理するプログラムなんてLispっぽいですけどね

  • will-stop?があると仮定する
  • 関数を引数に取り、will-stop?で判定して、真ならば無限ループ、偽ならば真を返して停止する関数last-tryを作る
  • last-trylast-try自身を渡すとどうなるか
  • last-tryが停止するとすると、will-stop?は真なので無限ループする。おかしい
  • last-tryが停止しないとすると、will-stop?は偽なので停止する。おかしい
  • そもそもwill-stop?があると仮定したのがおかしい

残念

これは異常なことですか。

はい。そうです。will-stop?は正確に記述できるけれども我々の言語では定義できない最初の関数です。

この問題に関してほかの方法はありますか。

いいえ。ありがとう Alan M. Turing(1912〜1954) と Kurt Godel(1906〜1978)。

Godelは有名な「ゲーデルの不完全定理」というやつでぱっと見は違うけれども
実は同じことを言ってます
上記はTuringがいわゆるチューリング・マシンを使って示したときのあらすじ
に違いないと想像
あとアロンゾ・チャーチという人もラムダ計算で同じ結果を出しています
たぶんそのはず

チューリングゲーデルは一般向けの書籍もたくさん出てるんですが
チャーチに関する本は見かけたことがありません
業績としては負けてないような気がするんですが

チューリングゲーデルみたいな波瀾万丈の人生じゃないんですかね
ブルーバックスくらいのレベルで出してくれるといいんですけど

Scheme手習い(14) 部分関数と全関数

第9章「……もう一度、もう一度、もう一度、……」は、変な関数の話?

まずは部分関数と全関数から

(define looking
  (lambda (a lat)
    (keep-looking a (pick 1 lat) lat)))

(define keep-looking
  (lambda (a sorn lat)
    (cond ((number? sorn) (keep-looking a (pick sorn lat) lat))
          (else (eq? a sorn)))))

この関数、引数によっては無限ループに入ってしまい、実行が終わりません
つまり関数が値を返しません
引数によっては関数が値を返さない関数を部分関数と言います

これまで出てきた関数は、リストを扱うものであれば
リストのcdr(や場合によってはcar)について再帰を行っていました
そのため、再帰のたびにリストの長さが短くなるので
いつかは関数の実行が終わることが保証されていました
つまりどんな引数を与えても関数は値を返していました
そのような関数を全関数と言います
普通に関数と言ったらたいてい全関数だと思います

ただし、「どんな引数を」といっても「定義域の中では」という条件がつきます
この本では定義域、つまり「正しい」引数が何かについては書いてないことが多いです
読めばわかるだろ的な

正しくない引数だったら無限ループになるような関数はもしかするとあったかもしれませんが
たぶんエラーが出て終わるか知らんぷりして変な値を返すかどちらかだったと思われます
エラーが出て終わるのと、無限ループになって値を持たないというのとはたぶん扱いが異なるんでしょう

keep-lookingはリストを扱う関数ですが、再帰のときlatをそのまま再帰しています
そのためいつかは完了するという保証は(ぱっと見)ありませんし
実際無限ループになることがあるので部分関数です
そういう再帰を「不自然な再帰」と呼んでます

eternityはどんな引数を与えても無限ループになる、「最も」部分的な関数です

(define eternity (lambda (x) (eternity x)))

別にただ無限ループするだけの関数に引数なんていらないんじゃという気がしなくもないんですが
なにか背景があるんでしょう
引数がなかったら関数じゃなくて定数みたいなものですし

次はalignという関数

(define shift
  (lambda (pair)
    (build (first (first pair)) 
           (build (second (first pair)) (second pair)))))

(define align
  (lambda (para)
    (cond
      ((atom? para) para)
      ((a-pair? (first para)) (align (shift para)))
      (else (build (first para) (align (second para)))))))

でこの関数が何なのかというと、再帰時に引数が小さくなっているわけではないので
さてこれは全関数なのでしょうか、すぐにはわかりません、ということ

そもそも何をやっているかわかりにくいです
引数の第一要素がペアだったら、第一要素の第二要素をとっぱらって
第二要素のほうにくっつける、というのを繰り返しています
と言ってもやっぱりわかりにくいので具体例で調べてみます

(((1 (2 (3 4))) 5) (((6 7) 8) 9))
((1 (2 (3 4))) (5 (((6 7) 8) 9)))
(1 ((2 (3 4)) (5 (((6 7) 8) 9))))
(1 (2 ((3 4) (5 (((6 7) 8) 9)))))
(1 (2 (3 (4 (5 (((6 7) 8) 9))))))
(1 (2 (3 (4 (5 ((6 7) (8 9)))))))
(1 (2 (3 (4 (5 (6 (7 (8 9))))))))

正確にはうまく言えないけれど、だんだん右に寄っていく感じです
なんかいつかは終わりそうな雰囲気ですね

定義域は(例によって)書いてありませんがソースから逆算すると
アトムとかアトムのペアとかペアのペアとかそういうもののようです
引数のparaってなんの略?パラメータのこと?とかなり悩んだんですが
あとでporaというのが出てくるんで調べてみたらparaは誤植のようです
Pair OR Atomってことでしょう
というあたりもヒントになって
ちゃんと書けばこういうこと

  • アトムは pora である
  • pora と pora のペアは pora である

(例によって)特に説明もなく話は進んでいきます
微妙に暗示されてはいるんですが

alignの引数中のアトムの数を数える関数を書けますか。

書けますけどそれが何か?

(define length*
  (lambda (para)
    (cond ((atom? para) 1)
          (else (o+ (length* (first para)) 
                    (length* (second para)))))))

狙いはわからなくても先へ進みます

alignへの引数とその再帰的な使用で変化しているものがほかにありますか。

はい、あります。ペアの第1の要素はより簡単になっていますが、第2の要素はより複雑になっています。

引数の長さを決めるのにlength*は間違った関数ではないでしょうか。

文字通りに取れば間違ってはいないと思いますが
alignが全関数であることを説明しようとしているっぽいので
その目的にはそぐわないということらしいです

もっと良い関数を見つけられますか。

もっと良い関数では、第1要素にもっと注意を払わなければいけません。

注意を払うってなんですか

次のweight*のようなものでしょうか。

(define weight*
  (lambda (pora)
    (cond ((atom? pora) 1)
          (else (o+ (o* (weight* (first para)) 2) 
                    (weight* (second para)))))))

これは良さそうに見えます。

重みをつけるってことでした

alignが全関数、つまり必ず値を返すってことを証明しようという流れのようです
length*はshiftしても変わらないので役に立ちませんが、
weight*ならペアの第1の要素が簡単になれば小さくなっていきそうです
処理が進むにつれて小さくなるけれども、いくらでも小さくなれるわけではないので
どこかで止まるはず、ってことかな

n要素のporaの場合、
(weight* pora)の値がlength*より小さくはならないことは明らかですが
最小値はたぶん 2n-1 になるはず
ついでに最大値は 2^n-1

ちょっとweight*の減り方を見てみます
引数のweight*を表示するようにして・・・そういえば表示ってどうやるんだっけ
こうか

(define align
  (lambda (para)
    (display (format "~a~%" (weight* para)))
    (cond
      ((atom? para) para)
      ((a-pair? (first para)) (align (shift para)))
      (else (build (first para) (align (second para)))))))

実行

> (align '(((1 (2 (3 4))) 5) (((6 7) 8) 9)))
45
31
29
27
25
23
21
19
17
15
9
7
5
3
1
(1 (2 (3 (4 (5 (6 (7 (8 9))))))))

そうじゃない

そうか、全体のweight*を知りたいのに関数に渡されるのはcarとかcdrとかだけですからね
だめだな

イデアもないので真心で手間ひまかけて解決

> (weight* '(((1 (2 (3 4))) 5) (((6 7) 8) 9)))
45
> (weight* '((1 (2 (3 4))) (5 (((6 7) 8) 9))))
31
> (weight* '(1 ((2 (3 4)) (5 (((6 7) 8) 9)))))
29
> (weight* '(1 (2 ((3 4) (5 (((6 7) 8) 9))))))
27
> (weight* '(1 (2 (3 (4 (5 (((6 7) 8) 9)))))))
25
> (weight* '(1 (2 (3 (4 (5 ((6 7) (8 9))))))))
19
> (weight* '(1 (2 (3 (4 (5 (6 (7 (8 9)))))))))
17

2n - 1で止まりました
それっぽい感じです

いやでもほんとかな
単調減少といっても増えることはないというだけで、減らないこともあって
必ず止まるとは言い切れないのかも?
最小値があるのは間違いないけど、最小値に達したら必ず止まると言えるかな?

condの条件に沿って考えてみます

  • poraがアトムであれば終わる
  • weight*は1

これはいい

  • poraの第1要素がペアであれば、poraをshiftしてまたalignする

このときは小さくなるでしょうか
例を作って考えてみます

A、B、Cをpora型の値(Aはペア)として
まずは( (A B) C)をshiftして(A (B C))にします

(weight* X)はちょっと長いので n(X) と書くことにして
n( ( (A B) C)) = 4n(A)+2n(B)+n(C)で、n( (A (B C))) = 2n(A)+2n(B)+n(C)

n(A) > 1だから( (A B) C)をshiftすると必ずweight*は減少しますね

ここまではいいとして

それをalignしたときつまり(align (shift (A (B C))))のweight*はどうでしょう
(align (A (B C)))と同じか、より小さければいいんですが

alignの中ではshiftしかしてないから、増えることはないだろう、とか?
いや、それが確かかどうかわからないから細かく見ていこうとしているんでした
ここは置いておいて先に進んでみます

  • poraの第1要素がペアでなければ(つまりアトムならば)、第二要素をalignする

第一要素のアトムをaと書くことにすると
n( (a (B C)))=2*1+2n(B)+n(C)で、n( (a (align (B C)))) はええと・・・
n( (B C))とn(align(B C))の関係がわからないとやっぱり進みません

結局n(X) > n(align(X))がわからないとなんとも言えないですね
って元に戻ってるじゃないかよ

これはもっと細かく考えないとダメな気がします
数学的帰納法っぽく考えてみたらどうでしょうか
簡単なporaから順番に証明していく方針で

アトムから始めてbuildで作っていったものがporaですから

  • 集合S(1)をアトム全体の集合とし、その要素をs(1)と書く

ここがスタート

  • 集合S(2)は、S(1)の要素でできたペア全体の集合とし、その要素をs(2)と書く

1回buildしました

  • 集合S(3)は、S(1)またはS(2)の要素でできたペア全体の集合とし、その要素をs(3)と書く

2回buildしました

  • 集合S(n)は、S(1)〜S(n-1)の要素でできたペア全体の集合とし、その要素をs(n)と書く

(n - 1)回buildしました

でS(n)を全部の自然数について集めればpora全体の集合になります

そうすると、(first s(k)) ∈ S(k - 1)、(second s(k)) ∈ S(k - 1) のはず
S(1)については成り立つ、S(k-1)までが成り立てばS(k)も成り立つ、って感じで
それでできちゃうとweight*を作った意味がなくなるかな?
まあやってみます

  • n = 1 のとき、つまり pora ∈ S(1) のとき
    (align pora) = pora となり停止する
  • n = k - 1 のとき

といく前に n = 2 のとき、つまり pora ∈ S(2) のときで考えてみます
結城浩先生も例示は理解の試金石とおっしゃってますからね
難しくなる前にまず

  • (first pora)がアトムならば
    (align pora) = (build (first pora) (align (second pora)))
    (first pora)= poraであり、(second pora) ∈ S(1) だから停止する
  • (first pora)がペアならば
    (align pora) = (align (shift pora))

あーだめかー
(shift pora) ∈ S(2)だもんなー
不自然な再帰だからなー
ってわかってみるとあたりまえだなー
なんでやる前に気づかないかなー

そこでweight*の出番?
(weight* pora)で数学的帰納法
いいのかなあとびとびだったりしますが

  • (weight* pora) = 1 のとき、
    poraはひとつのアトムだから、(align pora)は停止する
  • (weight* pora) < k のとき(align pora)が停止すると仮定して
    (weight* pora) = k となる pora について考える
    • (first pora)がアトムならば
      (align pora) = (build (first pora) (align (second pora)))
      (weight* (second pora)) は明らかに (weight* pora) = k より小さいから
      (align (second pora))は停止する
      したがって(align pora)も停止する
    • (first pora)がペアならば
      (align pora) = (align (shift pora))
      上で(雑に)書いたとおり、shiftすると必ずweight*は減少するから
      (weight* (shift pora)) < (weight* pora) = k
      したがって(align pora)は停止する

お、できた?
一応理屈は通ってる気がします
weight*エライ?

ちょっと修正したshuffleという関数

(define shuffle
  (lambda (pora)
    (cond ((atom? pora) pora)
          ((a-pair? (first pora)) (shuffle (revpair pora)))
          (else (build (first pora)
                       (shuffle (second pora)))))))

これはさらにどういう結果を返すのかわかりにくいですが
簡単に無限ループに入るので部分関数です

Scheme手習い(13) 継続の続き

第8章「究極のlambda」の続きの続きの続き

数のリストから偶数だけを集めるevens-only*を作ります
タップではなく木から集めてくるところがさっきまでとは違います
これは普通の再帰だし問題ありません

次は収集子を使って、できあがりのリストと偶数の積と奇数の和を収集します
「同時に2つ以上の値を集める」にようにしたということなんでしょうけど
なんか取ってつけたような機能ですね
戒律とか読んだ記憶を頼りに書けるところまで書いてみますよと

(define evens-only*&co
  (lambda (l col)
    (cond ((null? l) (col '() 1 0))
          ((atom? (car l))
            (cond ((even? (car l))
                   (evens-only*&co
                     (cdr l)
                     (lambda (newl p s)
                       (col (cons (car l) newl) (* (car l) p) s))))
                  (else
                    (evens-only*&co
                      (cdr l)
                      (lambda (newl p s)
                        (col newl p (+ (car l) s)))))))
          (else
            (evens-only*&co

えーと
carとcdrの両方を再帰的に処理しなければならないので
(car l)と(cdr l)について呼び出す必要があることは間違いないんですけど

    (else
      (evens-only*&co (car l) ...)
      (evens-only*&co (cdr l) ...))

これではcarの結果が捨てられてしまってcdrの結果と別れ別れになってしまいます
関数型プログラミングの形になってません
どうやってくっつけてたんだったかな

いったん引き下がって、書けたところだけで動かしてみながら考えます
収集子はcollectorという関数があることにして

  (evens-only*&co '() collector)
= (collector '() 1 0)

  (evens-only*&co '(1) collector)
= ((lambda (newl p s) (collector newl p (+ 1 s)) '() 1 0)
= (collector '() 1 (+ 1 0))
= (collector '() 1 1)

  (evens-only*&co '(2) collector)
= ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s)) '() 1 0)
= (collector (cons 2 '()) (* 2 1) 0)
= (collector '(2) 2 0)

ここまでは*関数じゃなくても同じで問題ありません
ここから先はすでにちょっとあやしくなってきますが前回を思い出しながら

  (evens-only*&co '(2 4) collector)
= (evens-only*&co '(4) (lambda (newl p s) (collector (cons 2 newl) (* 2 p) s)))

ここでは(cdr l)つまり(4)を処理した結果をnewl、p、sに入れてもらえることを期待して
そこに(car l)つまり2を結合する関数を作っています
(evens-only*&co '(4) ...)が(4)を処理した値がnewl、p、sに入ってるイメージなんでした
自分の仕事は(car l)つまり2をなんとかすること
あとは「上から」言われたとおりにcolしますが、そのときnewl、p、sに自分の仕事の
結果を入れてます

= (evens-only*&co '()
    (lambda (newl p s)
      ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s))
       (cons 4 newl) (* 4 p) s)))
= ((lambda (newl p s)
     ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s))
      (cons 4 newl) (* 4 p) s))
   '() 1 0)
= ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s))
   (cons 4 '()) (* 4 1) 0)
= (collector (cons 2 (cons 4 '())) (* 2 (* 4 1)) 0)
= (collector '(2 4) 8 0)

lが()になったらリストを最後までたどったということなのでcolに初期値を与えて
継続を評価したら完了です

さて本番
木を対象にして考えてみます
これはどうなってくれるとうれしいかな

  (evens-only*&co '((2 3) 4) collector)

(car l)もリストであるところがさっきまでと違いますけれども
さっきのパターンを再利用してみます

(cdr l)の処理を次のevens-only*&coにまかせて結果をnewl、p、sに入れてもらい
自分は(car l)だけを処理して
もらったnewl、p、sに結合してやります

ただ今回は(car l)もリストなのでこっちもevens-only*&coを使って処理します

(car l)の処理が終わったら続いて(cdr l)の処理を行いますから
(car l)を処理するときのcolに(cdr l)を処理するためのevens-only*&coを指定してやれば
うまくいくんじゃないでしょうか

(define evens-only*&co
  (lambda (l col)
    (cond ((null? l) (col '() 1 0))
          ((atom? (car l))
           (cond ((even? (car l))
                  (evens-only*&co (cdr l)
                    (lambda (newl p s)
                      (col (cons (car l) newl) (* (car l) p) s))))
                 (else
                   (evens-only*&co (cdr l)
                     (lambda (newl p s)
                       (col newl p (+ (car l) s)))))))
          (else
            (evens-only*&co (car l)
              (lambda (newl p s)
                (evens-only*&co (cdr l)
                  (lambda (newl2 p2 s2)
                    (col (cons newl newl2) (* p p2) (+ s s2))))))))))

すごく大ざっぱに読めば
まず(car l)を処理して次に(cdr l)を処理してくっつけたら継続を呼ぶ、と読めますね

実行の様子を追ってみます

  (evens-only*&co '((2 3) 4) collector)
; (car l)がアトムでない場合の展開
= (evens-only*&co '(2 3)
    (lambda (newl p s)
      (evens-only*&co '(4)
        (lambda (newl2 p2 s2)
          (collector (cons newl newl2) (* p p2) (+ s s2))))))
; しばらくcdr側(内側)のevens-only*&coは放置
= (evens-only*&co '(3)
    (lambda (newl p s)
      ((lambda (newl p s)
        (evens-only*&co '(4)
          (lambda (newl2 p2 s2)
            (collector (cons newl newl2) (* p p2) (+ s s2)))))
      (cons 2 newl) (* 2 p) s)))
= (evens-only*&co '()
    (lambda (newl p s)
      ((lambda (newl p s)
        ((lambda (newl p s)
            (evens-only*&co '(4)
              (lambda (newl2 p2 s2)
                (collector (cons newl newl2) (* p p2) (+ s s2)))))
          (cons 2 newl) (* 2 p) s))
      newl p (+ 3 s))))
;car側が末端まで達しlambdaの呼び出しが始まる
= ((lambda (newl p s)
    ((lambda (newl p s)
        ((lambda (newl p s)
          (evens-only*&co '(4)
            (lambda (newl2 p2 s2)
              (collector (cons newl newl2) (* p p2) (+ s s2)))))
        (cons 2 newl) (* 2 p) s))
      newl p (+ 3 s)))
  '() 1 0)
;外側から順番に適用
= ((lambda (newl p s)
    ((lambda (newl p s)
        (evens-only*&co '(4)
          (lambda (newl2 p2 s2)
            (collector (cons newl newl2) (* p p2) (+ s s2)))))
      (cons 2 newl) (* 2 p) s))
  '() 1 3)
= ((lambda (newl p s)
    (evens-only*&co '(4)
      (lambda (newl2 p2 s2)
        (collector (cons newl newl2) (* p p2) (+ s s2)))))
  '(2) 2 3)
= (evens-only*&co '(4)
    (lambda (newl2 p2 s2)
      (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2))))
;car側の処理が完了。cdr側の処理を開始
= (evens-only*&co '()
    (lambda (newl p s)
      ((lambda (newl2 p2 s2)
        (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2)))
      (cons 4 newl) (* 4 p) s)))
;cdr側が末端まで達しlambdaの呼び出しを開始
= ((lambda (newl p s)
    ((lambda (newl2 p2 s2)
        (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2)))
      (cons 4 newl) (* 4 p) s))
  '() 1 0)
;car側の結果とcdr側の結果を結合する
= ((lambda (newl2 p2 s2)
    (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2)))
  '(4) 4 0)
= (collector '((2) 4) 8 3)

できたー
けどそろそろ限界

ソースを読んできっとこれで動きそう、というところまではわかる気がしてきましたが
ここまで来ると実行の様子を思い浮かべて確信を持つのは容易ではないですね

さてこれでこの章も終わりですがいったい「究極のlambda」ってなんだったんでしょう
高階関数のこと?
継続のこと?

原文だと「Lambda the Ultimate」となってますね
いろんなlambdaがあってその中で特にすごいlambdaがあるように読んでたんですが
これだとlambda様自体が究極であるって感じですね
「究極のlambda」というより「究極なるlambda」の方が雰囲気が出るかなあ