Scheme修行　第12章　避難しましょう（その１）

ローカルな関数を定義する手段としてletrecを習います。letrecを用いる目的は：

ローカルな関数を定義してそれに名前をつける事により、Yコンビネータを使わずにかつグローバルな名前を増やさずに再帰関数を定義する。（Yコンビネータを使うには再帰算数をそれ用に書き換える必要があり確かにちょっと妙な書き方になる。）
（小さな関数であれば）グローバルに定義されている他の関数に依存する事無く関数定義が出来る。（でもこれは殆ど同じ関数を重複して定義する事になりますが。）

です。

ノート：

multirember

元のmultiremberの定義は

(define multirember
  (lambda (a lat)
    (cond ((null? lat) '())
          ((eq? a (car lat)) (multirember a (cdr lat)))
          (else (cons (car lat) (multirember a (cdr lat)))))))

これをYコンビネータに対応させるには元の関数を以下の様に変換する。

multirember相当の関数を引数に受け取り、関数を返す関数をYコンビネータに渡す
1. defineの代わりに(lambda (mr)…で囲む。
2. multiremberを呼び出している部分はmrに変換する
そこでは普遍のaを引数として渡す必要は無い
1. lambda (a lat)の部分はlambda (lat)で良い
2. mrの引数は(cdr lat)だけで良い

実際に評価してみる。

> (let ((a 'tuna)
        (lat '(shrimp salad tuna salad and tuna)))
    (multirember a lat))
(shrimp salad salad and)
>

第９章の最後に出て来るlengthの定義は以下の通り。

((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))))))))

ここの、mk-lengthをfに変えて???と言う名前でdefineしようとしている。前半部分が適用順Yコンビネータ。
Yを使って定義し直すが、ここではmultiremberの書き直しとは違って、defineの次の行にlambda (引数)と言う形式になっていない。
また引数としてのlengthがdefineで付けられた名前のlengthを隠蔽している。
lengthは再定義してしまうとエラーになるので取り敢えずmyLengthと言う名前で定義して評価してみる。定義は以下の通り：

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

lengthはdefineで使うmyLengthではなく引数のlengthを使用している。
評価すると：

> (myLength '(a b c d e f g))
7
>

ちゃんと動く。
multiremberをletrecを使って再定義。この本ではletも出て来ていないのにいきなりletrec。
恐らくこの本で始めて問答の左右が逆転する。
微妙なやり取りが続くが、纏めると：

multiremberの引数aはmultiremberの定義内でしか参照出来ない。あるいは意味を持たない。
multiremberの引数aをmr側からも参照する必要がある。
引数として渡さないのであればmrはmultirember内で定義される必要がある。
defineはグローバルな名前を定義する機能で関数定義の内部でのローカルな名前の定義には使えない。

letrecは全体として式でそのスコープ内で局所的な名前の定義を持てる。letと同様に名前を定義する部分と本体としての式の部分に分かれる。multiremberの定義の四角で囲われた部分が定義部分で、最後のmrが本体の式の部分。ここではletrecは定義した関数を返してlatに適用している。
例を評価してみる。

> (let ((a 'pie) (lat '(apple custard pie linzer pie torte)))
    (multirember a lat))
(apple custard linzer torte)
>

ここではletrec内でmrを定義し、その関数をletrecの外に返してからlatに適用していたが、次ぎはletrec内でmrを定義しそのままletrec内でlatに適用している。新しい定義でも評価してみる。

> (let ((a 'tuna)
        (lat '(shrimp salad tuna salad and tuna)))
    (multirember a lat))
(shrimp salad salad and)
> (let ((a 'pie)
        (lat '(apple custard pie linzer pie torte)))
    (multirember a lat))
(apple custard linzer torte)
>

rember-fは述語関数を引数に取り、その述語関数を同値判定に使う関数を値とする。
DrRaketでは数値もeq?で比較出来るので数のリストから数を除く事は可能。

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

rember-fは

引数test?を取る関数（test?は述語関数）
関数の値は、引数としてアトムとリストを取る関数
その関数の値は
1. リストが空の場合は空リスト
2. リストの先頭要素にtest?を適用すると真となる場合は、残りのリスト
3. そうでない場合は、リストの先頭要素にリストの残り要素に同じrember-fを適用した結果を連結したリスト

multirember-fは

引数test?を取る関数（test?は述語関数）
関数の値は、引数としてアトムとリストを取る関数（m-fと名付けられている）
その関数の値は
1. リストが空の場合は空リスト
2. リストの先頭要素にtest?を適用すると真となる場合は、リストの残り要素に同じmultirember-fを適用した値
3. そうでない場合は、リストの先頭要素にリストの残り要素に同じmultirember-fを適用した結果を連結したリスト

基本は太字部のみが異なる。
一応ここのmultirember-fの定義を評価してみる。multirember-fはこの後も変形して色々出て来るのでここではmultirember-f1として定義。

> ((multirember-f1 eq?) 5 '(1 5 2 5 3 5 4 5))
(1 2 3 4)
>

この二つの関数でのポイントは再帰しようとする度に(rember-f test?)あるいは(multirember-f test?)で関数を求めてから適用する形式になっている事。上記の「同じrember-f」あるいは「同じmultirember-f」の部分で関数を求め直している点にある。
multirember-fをtest?に適用した結果、即ち(lambda (a lat)以降は一回のmultirember-fの適用では不変なのでletrecを使ってこれに名前m-fを付けてletrecの値として返す形に変形。multirember-f2と言う名前をつけて評価してみる。

> ((multirember-f2 eq?) 5 '(1 5 2 5 3 5 4 5))
(1 2 3 4)
>

再定義したmultiremberはletrec内でmrと付けた(lambda (a lat)…で始まる関数を最後にletrecの値として返しているので、defineの次の行にlambda (a lat)…と書くのと等価。
letrec内のローカルな名前としてmultiremberと書いても確かに等価。
『(letrec…)は再帰関数を定義しており、(define…)は名前と値を結びつけていますから、』と書いてありますが、あくまで(letrec…)の値として定義した関数を返しているので(letrec…)を取り除ける筈。

プログラミング再入門

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

Scheme修行　第12章　避難しましょう（その１）

ノート：

multirember