kb84tkhrのブログ

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

Scheme修行(8) 第17章 我変わる、ゆえに我あり！

seasonedschemer

ふたたびdeepM
deepを内部に持つバージョンから始めます

(define deepM
  (let ((Rs (quote ()))
        (Ns (quote ())))
    (letrec ((D (lambda (m)
                  (if (zero? m)
                      (quote pizza)
                      (cons (D (sub1 m)) (quote ()))))))
      (lambda (n)
        (let ((exists (find n Ns Rs)))
          (if (atom? exists)
              (let ((result (D n)))
                (set! Rs (cons result Rs))
                (set! Ns (cons n Ns))
                result)
              exists))))))

これはメモ化が十分に働かない半バグバージョン
これを何度か修正して、以下のような形にします

(define deepM
  (let ((Rs (quote ()))
        (Ns (quote ())))
    (lambda (n)
      (let ((exists (find n Ns Rs)))
        (if (atom? exists)
            (let ((result
                   (if (zero? n)
                       (quote pizza)
                       (cons (deepM (sub1 n)) (quote ())))))
              (set! Rs (cons result Rs))
              (set! Ns (cons n Ns))
              result)
            exists)))))

この間にやったことは以下のとおり

  1. 正しくメモ化が動くようにする
    Dの呼び出しをdeepMに変えるだけ
  2. letrecをletに変更する
    自分自身を呼んでいないのでletでOK
  3. ふたつのletをひとつにまとめる
  4. 一度しか呼ばれていないDを、元のlambdaの形に置き換える
    せっかく関数の形に切り出したんですが元にも押します
  5. (lambda (m) (...) n)を(let ((m n)) ...)に書き換える ふたつの式は同等ですから
  6. (let ((m n)) ...)からletを消す
    このletはただnをmに置き換えているだけですから

ここでは何を教えてくれているのでしょう？

  • 式の変形の練習みたいなもの？
  • リファクタリング？
  • なにか計算機科学的な背景がある？
  • 次にやることの準備？

狙いがわかりませんでした

呼ばれた回数を数えるconsを作ります

(define counter #f)
(define set-counter #f)
(define consC
  (let ((N 0))
    (set! counter (lambda () N))
    (set! set-counter (lambda (x) (set! N x)))
    (lambda (x y)
      (set! N (add1 N))
      (cons x y))))

(set! counter (lambda () N))というのがちょっと不思議な書き方です
参照したいときは(counter)と関数を評価する形になります

こんなふうにNを直接見せてもやりたいことはやれるんですけれども

(define N 0)

(define consC
  (lambda (x y)
    (set! N (add1 N))
    (cons x y)))

直接見えるようにすると好き放題されてしまうので行儀がよろしくないということでしょうか
Javaで言うところのgetter、setterみたいな感じですね
外から勝手に使うことのできない状態をクロージャに持つことができました

なお(define counter #f)の#fには意味はありません
(define counter)でもいいしそれで通る処理系もあるようなのですが
Racketでは通らなかったのでとりあえず#fと書いてます

consCを呼ぶようにdeepを書き換えて

(define deep
  (lambda (m)
    (if (zero? m)
        (quote pizza)
        (consC (deep (sub1 m)) (quote ())))))

(deep 0)から(deep 1000)まで実行してやると

(define supercounter
  (lambda (f)
    (letrec
        ((S (lambda (n)
              (if (zero? n)
                  (f n)
                  (let ()
                    (f n)
                    (S (sub1 n)))))))
      (S 1000)
      (counter))))

(set-counter 0)
(supercounter deep)

500500回consを実行したことがわかります

ありがとう Carl F. Gauss (1777-1855)。

deepMのconsを数えてやると

(define deepM
  (let ((Rs (quote ()))
        (Ns (quote ())))
    (lambda (n)
      (let ((exists (find n Ns Rs)))
        (if (atom? exists)
            (let ((result
                   (if (zero? n)
                       (quote pizza)
                       (consC (deepM (sub1 n)) (quote ())))))
              (set! Rs (cons result Rs))
              (set! Ns (cons n Ns))
              result)
            exists)))))

(set-counter 0)
(supercounter deepM)

メモ化の効果で1000回で済んでいることがわかります
だから速くなったのかというとちょっとわかりませんが

14章のrember1*のconsを数えます
最初に作った版では、引数に取ったリストをそのまま返すだけでいい場合でも
１からリストを作っていたので余分なconsを行っていました
継続を使った版では、指定されたアトムがリスト内に存在しなければ
継続で即抜けて、指定されたリストをそのまま返しますので無駄なconsは実行されません

と言いたいだけなのか、もっと大事なことを言おうとしているのかわかりません
consの回数っていうのはけっこう気にされるようなのでそういう話なのかもしれません