kb84tkhrのブログ

何を書こうか考え中です

Scheme修行(4) 第14章 名前をつけましょう

やっとletがでてきます
letをletrecよりletccより後でとりあげたのはどういうことなんでしょう?

leftmost

一番左のアトムを探すleftmostです

(define leftmost
  (lambda (l)
    (cond ((atom? (car l)) (car l))
          (else (leftmost (car l))))))

これは引数に空リストを含まないことが前提になっているので
空リストを含んでいてもよいようにしてやります

(define leftmost2
  (lambda (l)
    (cond ((null? l) (quote ()))
          ((atom? (car l)) (car l))
          (else (cond
                  ((atom? (leftmost2 (car l)))
                   (leftmost2 (car l)))
                  (else (leftmost2 (cdr l))))))))

ちょっと見慣れない形かと思いましたが
よくみると第4の戒律の、S式のリストを扱う形です
(car l)の一番左がアトムだったら(cdr l)を評価してやる必要は
ないのでcondが二重になってますがそこに惑わされました

(null? l)だったときに()を返しているのは
たとえば#fを返すようにすると一番左のアトムが#fだった場合と区別がつかないからです
ちょっと訳がわかりづらかった・・・

condの中の((atom? (leftmost2 (car l))) (leftmost2 (car l)))
(leftmost2 (car l))を2回評価しているのがもったいないですね

そのような望ましくない繰り返しを防ぐために、(letrec ...)を用いてみましょう。

はい。でも、(letrec ...)で好きなものに名前をつけるのですか?

代わりに(let ...)を使います。

こう

(define leftmost3
  (lambda (l)
    (cond
      ((null? l) (quote ()))
      ((atom? (car l)) (car l))
      (else
       (let ((a (leftmost3 (car l))))
         (cond
           ((atom? a) a)
           (else (leftmost3 (cdr l)))))))))

わからないのはこれ

(letrec ...)と見かけは同じですが、(let ...)は式の値に名前をつけるのです。

letrecだって式の値に名前をつけてるんじゃないかと思います先生!
違いは名前の見えてるスコープだけのような気がするんですが
どういうことでしょうか

次はS式から最初に見つかったアトムだけを削除するrember1*を作ります
これはまあ練習です
(eqlist? (R (car l)) (car l))という条件はなんだろうと思いましたが
言い換えると「carにaが含まれていなければ」という意味ですね

第15の戒律(仮)
繰り返される式の値に名づくるには(let ...)を用うべし。

depth*

リストの深さを求めるdepth*です

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

(depth* (cdr l))(add1 (depth* (car l)))が2回ずつ出てきます

letで書きます

(define depth*2
  (lambda (l)
    (cond
      ((null? l) 1)
      ((atom? (car l)) (depth*2 (cdr l)))
      (else
       (let ((a (add1 (depth*2 (car l))))
             (d (depth*2 (cdr l))))
         (cond ((> d a) d)
               (else a)))))))

よく見るとまだ(depth* (cdr l))が2回出てきてます
こうすべきでしょうか?

(define depth*3
  (lambda (l)
    (cond
      ((null? l) 1)
      (else
       (let ((d (depth*3 (cdr l))))
         (cond
           ((atom? (car l)) d)
           (else
            (let ((a (add1 (depth*3 (car l)))))
              (cond
                ((> d a) d)
                (else a))))))))))

こうすると確かに(depth* (cdr l))を繰り返し書かなくてすむようになりましたが
(depth* (cdr l))を評価する回数は実は変わっていません
そのわりに、コードの方はcondletの入れ子で読みづらくなっています
ちょっとこれはやり過ぎだったようです

第15の戒律(改訂版)
関数定義において繰り返される式は、当の関数を1回使用するときに2回評価される可能性があるなら、
それらの値を名付くるに(let ...)を用うべし。

コード上に何回出てくるかよりも、実際に評価される回数を重視しましょうってことみたいです
DRY原則とはバランスの問題になるのかな

あと今になってifを紹介したり

それは賢いですね。もっと前に知っておくべきでした。

何事にも、ふさわしい時と場所があるのです。

今がその時?
なんで?

さらに関数maxを導入すると

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

letが消えてしまいました
letでローカル変数を導入する代わりに関数の引数でも同じ働きができるわけですね
もともとlambdaですもんね

ついでにifも消えてぐっと見通しが良くなりました
ぱっと見でS式の再帰の形に見えますし
リファクタリング終了、って気分です
○○なら関数にする、みたいな戒律があってもよさそうな気分

leftmost(再)

leftmostではletを使うことにより同じ式を2回評価するという無駄を減らしましたが
まだ無駄があります

簡単なケースとして(leftmost '(((s))))を評価する場合
再帰を繰り返して'sにたどり着いた後、それにaという名前をつけ
aつまり'sはアトムなので'sを返す、ということを繰り返して値が求まります

1ステップずつ追うとこうです
関数名はlmと略記しました

(lm '(((s))))
(let ((a (lm '((s))))) (cond ...))
(let ((a (let ((a (lm '(s)))) (cond ...)))) (cond ...))
(let ((a (let ((a 's)) (cond ...)))) (cond ...))
(let ((a 's)) (cond ...))
's

答えは'sだとわかっているのにひとつずつ戻っていくのは無駄ですね
そこで、答えが求まったらすぐに値を返すようにします
letccを使います

こっちがこの章の本題なのかな?
いやでも「名前をつけましょう」だしなあ

こうかな・・・

(define leftmost5
  (lambda (l)
    (let/cc skip
      (letrec
          ((lm (lambda (l)
                 (cond
                   ((null? l) (quote ()))
                   ((atom? (car l)) (skip (car l)))
                   (else
                    (let ((a (lm (car l))))
                      (cond
                        ((atom? a) a)
                        (else (lm (cdr l))))))))))
        (lm l)))))

追うとこんな感じ

(leftmost5 '(((s))))
(let/cc skip (lm '(((s)))))
(let/cc skip (let ((a (lm '((s))))) (cond ...)))
(let/cc skip (let ((a (let ((a (lm '(s)))) (cond ...)))) (cond ...)))
(let/cc skip (let ((a (let ((a (skip 's))) (cond ...)))) (cond ...)))
's

終わりが速くなりました

・・・と思ったら、正解は違ってました!
そもそもaと名前を付ける必要もありませんでした
確かに

(define leftmost7
  (lambda (l)
    (let/cc skip
      (letrec
          ((lm (lambda (l)
                 (cond ((null? l) (quote ()))
                       ((atom? (car l)) (skip (car l)))
                       (else (let ()
                               (lm (car l))
                               (lm (cdr l))))))))
        (lm l)))))

動き方は同じようなものですがすっきりしました

(leftmost7 '(((s))))
(let/cc skip (lm '(((s)))))
(let/cc skip (let () (lm '((s))) (lm '())))
(let/cc skip (let () (let () (lm '(s)) (lm '())) (lm '())))
(let/cc skip (let () (let () (skip 's) (lm '())) (lm '())))
's

ループを途中で打ち切るような感じです
あ、letccをCで言うところのbreakみたいに使ったということですね

ところでletの中に複数の式が出てきました
Scheme手習いでは初

純粋に関数型のプログラムなら、複数の式を順番に実行する機能は必要ない
そんな風に考えていた時期が俺にもありました

じゃなくてそうですよね?
副作用がないということは関数の値しか使えるものがないのに
それを捨ててしまうということですから

ところがletccを使うと順番に実行する機能の使いでが発生する
letccを使ったプログラムは(いわゆる)関数型の範疇を飛び出してるってことになるんでしょうか
それまでにやろうとしてたことを忘れてしまうというのは副作用といえばこの上ない副作用ですしね
letccで得た継続の値を持ち出さない限り影響が外に及ぶことはなさそうですが

でも、手習いで出てた式の継続ならすっかり関数型の範疇内なはず
どういうことになるのかな

さてテキストの注にはlet ()の代わりにbeginとも書けるよ、と書いてありますが
実はそれも不要で、これで動きます

                       (else 
                        (lm (car l))
                        (lm (cdr l)))))))

condの後ろにはひとつしか式が書けないということにしておきたいんでしょうか
こだわりポイントが何なのかちょっとわかりません
動き方を同じように書こうとするとこんな風になると思いますが、正しさに少々不安が

(leftmost8 '(((s))))
(let/cc skip (lm '(((s)))) (lm '()))
(let/cc skip (lm '((s))) (lm '()) (lm '()))
(let/cc skip (lm '(s)) (lm '()) (lm '()) (lm '()))
(let/cc skip (skip 's) (lm '()) (lm '()) (lm '())))
's

そういう不安を起こさないように、ということかもしれません