プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート

Scheme修行　第16章　位置について、セット、バン！（その２）

LISP Scheme

set!を使って、グローバルな関数名を参照せずに再帰を行うテクニックを習います。

ノート：

length

まずは元のlengthの定義から出発。
このlengthと言う名前はグローバルな名前で定義の中から参照している。lengthは組み込み関数として既に定義されているので、mylengthと言う名前で動作確認をする。

> (mylength1 '(1 2 3 4 5))
5
>

定義の中から自分自身へのグローバルな名前を介さずに参照する事を考える。関数内でローカルな名前hとして関数を定義し、それを再帰呼び出しする形に書き換える。letrecが使えない環境を想定しているのでletでの初期化で一旦適当な関数に割り当てておいて、後から本物の関数にset!を使って差し替え、差し替えられた関数を値とする形に書き換える。

この２段階のステップをグローバルな名前で一旦lengthに0を返す関数を割り当てて後から本物に差し替える定義を示している。set!はグローバルな名前に使うなと言う第16の戒律を持ち出しているが、最初からローカルな名前を使う事が目的なので既に冗長。

第17の戒律の『xの新しい値がxを参照する関数の時』と言うのはletrecが使えない環境でletrecで行う再帰を行う場合を指している。

> (mylength2 '(1 2 3 4 5))
5
>

このローカルな変数を使った定義は、lengthを２段階で定義した時と同様に架空のグローバル変数h1を２段階で定義している事に相当する。ここでの(let () …)は(set! …)と式としてh1を返す二つの式を纏める役割を果たしている。defineの名前の後は一つの式である必要がある為、このletが必要になる。

次に最初からh1に本物の定義を割り当て、lengthからは単にh1を参照する形に書き換える。lengthはh1であり、h1はh1で再帰しているので、lengthは再帰している事になる。

次にこの再帰している関数を一般化する。
length固有の部分を再帰の為に引数としてlengthが渡って来る形の関数Lを定義。元のlengthはローカル変数を使って再帰する部分のみにする。

Lを使ったlengthの定義を動作確認する。

> (mylength3 '(1 2 3 4 5))
5
>

lengthの定義のLを引数として与えて、length相当の関数を返す関数をY!として定義する。
Y!を使ったlengthの定義の動作確認をする。

> (mylength4 '(1 2 3 4 5))
5
>

コンビネータの名前にある!は再代入set!を使っている事を示唆する名前と思われる。

ここまではletrecが使えない環境を前提としていたが、letrecを使うとY!は更に単純に書ける。

depth!

元のdepth*の定義

(define depth*
  (lambda (l)
    (cond ((null? l) 1)
          ((atom? (car l)) (depth* (cdr l)))
          (else (max (add1 (depth* (car l)))
                     (depth* (cdr l)))))))

から、depth*を引数として与えられる関数に書き換えるとDとなる。これにY!を適用して動作確認をする。

> (let ((l '(margarine
             ((bitter butter)
              (makes)
              (batter (bitter)))
             butter)))
    (depth* l))
4
>
YとY!の違い

bizが適用された時、毎回最初の(let ( (x 0) ) …)から評価される訳ではなく、defineを評価される時にxが作られて初期化され、以降はbizが参照された時にlambdaが返した定義が評価される。つまりxはbizが定義された時に１回だけ初期化され、その後呼ばれる毎に1が足される。

bizにYを適用すると

  1. 引数(lambda (f) (biz (lambda (x) ( (f f) x))) )に関数(lambda (f) (f f))を適用した結果が返る。
  2. (biz (lambda (x) ( (f1 f1) x)))を評価した結果。ここでf1は(lambda (f) (biz (lambda (x) ( (f f) x))) )
  3. biz適用中：fに(lambda (x) ( (f1 f1) x))を割り当てる。このfをf2とする。
  4. biz適用中：xに1を足す。結果は1。
  5. biz適用中：新しい関数(lambda (a) (if (= a x) 0 (f2 a)))を作る。ここでf2は(lambda (x) ( (f1 f1) x) )。
  6. 結果として(lambda (a) (if (= a x) 0 (f2 a)))が決まる。

ここで( (lambda (a) (if (= a x) 0 (f2 a))) 5)を評価する。

  1. (if (= 5 1) 0 (f2 5))が評価される。
  2. (f2 5)が評価される。ここでf2は(lambda (x) ( (f1 f1) x) )。
  3. ((f1 f1) 5)が評価される。ここでf1は(lambda (f) (biz (lambda (x) ((f f) x))))
  4. 引数の5は置いといて、
    1. (biz (lambda (x) ((f3 f3) x)))が評価される。ここでf3はf1と同じ。
    2. biz適用中：fに(lambda (x) ( (f3 f3) x))を割り当てる。このfをf4とする。f4はf2と同じ。
    3. biz適用中：xに1を足す。結果は2。
    4. biz適用中：新しい関数(lambda (a) (if (= a x) 0 (f4 a)))を作る。ここでf4は(lambda (x) ( (f3 f3) x) )。
    5. 結果として(lambda (a) (if (= a x) 0 (f4 a)))が決まる。
  5. ((lambda (a) (if (= a x) 0 (f4 a))) 5)が評価される。ここでaは5、xは2。

以下同文だが、繰り返しの度xの値だけが変化するのでいずれxが5の状態で( (lambda (a) (if (= a x) 0 (f4 a))) 5)が評価される事となり、0が確定する。

一方、bizにY!を適用すると、

  1. Lにbizが割り当てられる
  2. ローカルな変数hが作られ（取り敢えず適当な関数が割り当てられる）
  3. hが(L (lambda (arg) (h arg)))の評価結果に差し替えられる。
  4. hは(biz (lambda (arg) (h arg)))の評価結果
  5. h代入中: biz適用中: fに(lambda (arg) (h arg))を割り当てる
  6. h代入中: biz適用中: xに1を足す。結果は1。
  7. h代入中: biz適用中: 新しい関数(lambda (a) (if (= a x) 0 (f a)))を作る。
  8. hに(lambda (a) (if (= a x) 0 (f a)))を割り当てる。
  9. hを返す。

ここで

  1. (h 5)を評価する。
  2. aに5が割り当てられ、xは1なので、(f 5)と評価される。fは(lambda (arg) (h arg))。
  3. (h 5)と評価される。振り出しに戻る…

ポイントはhに割り当てられている関数の定義にはbizを適用した結果返って来た関数が割り当てられているだけで、bizの適用が含まれていない為に二度とbizを呼ばない所にある。つまりbizは二度と評価されないので(set! x (add1 x))が二度と呼ばれず、xは1のまま変化しない。

参照透過でない状況でメモ化した場合の問題を示しているのか。