Scheme修行(5) 第14章 名前をつけましょう（続き）
rember1*をいじっていきます
再掲
(define rember1*
(lambda (a l)
(letrec
((R (lambda (l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) a) (cdr l))
(else (cons (car l) (R (cdr l))))))
(else
(let ((av (R (car l))))
(cond
((eqlist? av (car l))
(cons (car l) (R (cdr l))))
(else
(cons av (cdr l))))))))))
(R l))))今回の範囲はなんか順を追って丁寧に説明しているようで逆にわざと落とし穴を作っているような説明
ゆっくり見ていきます
letccを使うと
(R (car l))を求めてから(car l)と比較するってあたり、なんとなくもどかしさを感じます
(R (car l))を求めた時点で、その途中にaと等しいアトムがあったかどうかはわかっているはず
aと等しいアトムがなかったことを確かめるために(R (car l))と(car l)を比較するのは無駄
リストが等しいことを確認しようとすると要素を全部たどらないといけないので
空リストを見つけたときに方位磁針を用いると、
rember1*の役に立ちませんか。
null?だったとき、ということですね
空リストが見つかったということは、削除すべきアトムがなかったということなので
削除前のリストがそのまま答えになるはず
役に立たせることはできそうな気がします
ただ、carを見ている間に空リストになってしまった場合はまだcdrを見なきゃいけないとか
単純に終わってしまえばいいわけではないところがleftmostと異なるところです
補助関数から作り始めます
といってもこっちが本体のようなものです
リストlの最初に出てくるアトムaを取り除きます
上の定義のRでは外側の関数からlとaを引き継いでいましたが
ここでは独立した関数として書いているので引数になっています
(define rm
(lambda (a l oh)
(cond
((null? l) (oh (quote no)))
((atom? (car l))
(if (eq? (car l) a)
(cdr l)
(cons (car l) (rm a (cdr l) oh))))
(else
(if (atom?
(let/cc oh
(rm a (car l) oh)))
(cons (car l) (rm a (cdr l) oh))
(cons (rm a (car l) 0) (cdr l)))))))lが空リストの時
空リストを見つけると、継続ohを使って(quote no)を返します
空リストを見つけたということは、lをたどる途中でaに出会わなかったということですね
なぜ(quote no)なのかというと
失敗した時にリストを返してしまうと成功なのか失敗なのか判定できないからです
成功した時はリストを返し、失敗した時はアトムを返します
アトムであればnoだろうがyesだろうが問題ありません
leftmostでは失敗したとき(quote ())を返していました
失敗の値を何にするのか都度考えないといけないんでしょうか
リストもアトムも返すし失敗もする、っていう関数は作れないんでしょうか
ちょっと嫌ですね
ohで戻ったときにどうなるかはまだわかりません
気にしないで先へ進みます
lがアトムの時
(car l)がアトムの時の処理は普通です
ohはそのまま渡しているということは押さえておきます
lがリストの時
(car l)がアトムでなかった、つまりリストだった場合は(car l)にrmを適用します
このとき、あらたに現時点の継続をohにセットしてからrmを評価しています
(car l)の中にaが含まれているかどうかをテストするのが目的なので
もらってきたそのままohを渡してどこかにすっとばされては困りますから
で、アトム（つまりno）が返ってきた場合
(car l)にaが含まれなかったということなので
(rm a (car l) oh))で本来求めたかった値は(car l)ということになります
(car l)と、(cdr l)からaを取り除いたもの、
つまり(rm a (cdr l) oh))をconsします
cdr側にもaがなかったらどうなるんでしょうか
そうすると、値をnoとして（呼び出し元からもらった方の）ohに戻ります
たぶんそこでaが含まれてなかったぞ、と判定されてなんやらかんやら
そうでなければ、(car l)にaが含まれているということなので
(rm a (car l) 0))の値に(cdr l)をconsします
って、(rm a (car l) 0))ってなんでしょうか？
0って？
rmがうまくアトムを取り除いてくれることがわかっていますから、方位磁針は必要ありません。つまり
(rm a (car l) 0)を使うことができるという意味ですか。はい。どんな値でも大丈夫です。0は簡単な引数です。
なんでもいいなら()でもnoでもohでも渡していいってことですね
oh渡せば(rm a (car l) oh))になってletでまとめられそう
今回の継続は
空リストを見つけたとき、今までは素直に空リストを返してたところで
空リストではなく（ショートカットして）アトムを返すために使われている
ということになりますね
rmの動作
動作を追うとこんな感じ
(let/cc Say (rm 'a '((b) c (b)) Say))
= (let/cc Say (if (atom? (let/cc oh (rm 'a '(b) oh))) ...))
= (let/cc Say (if (atom? (let/cc oh (cons 'b (rm 'a '() oh)))) ...))
= (let/cc Say (if (atom? (let/cc oh (cons 'a (oh 'no)))) ...))
= (let/cc Say (if (atom? 'no) ...))
= (let/cc Say (cons '(b) (rm 'a '(c (b)) Say)))
= (let/cc Say (cons '(b) (cons 'c (rm 'a '((b)) Say))))
= (let/cc Say (cons '(b) (cons 'c (if (atom? (let/cc oh (rm 'a '() oh))) ...))))
= (let/cc Say (cons '(b) (cons 'c (if (atom? 'no) ...))))
= (let/cc Say (cons '(b) (cons 'c (cons '(b) (rm 'a '() Say)))))
= (let/cc Say (cons '(b) (cons 'c (cons '(b) (Say 'no)))))
= 'no本の例をもとにしたんですが、ふたつめのifのelse部分を通ってないので
カバー率が100%になってません
let/ccが入って、カバーすべきケースを思い浮かべるのが大変になってきた気がします
まじめにテスト項目あげようと思ったら頭痛くなるかも
バージョン1
呼び出し側を作ればいったんできあがりです
(define rember1*4
(lambda (a l)
(if (atom? (let/cc oh (rm a l oh)))
l
(rm a l (quote ())))))こんどは使わない継続に(quote ())ですかやめれ
わざとなの？
バージョン2
letを使うとあら不思議・・・
(define rember1*5
(lambda (a l)
(let ((new-l (let/cc oh (rm5 a l oh))))
(if (atom? new-l)
l
new-l))))
(define rm5
(lambda (a l oh)
(cond
((null? l) (oh (quote no)))
((atom? (car l))
(if (eq? (car l) a)
(cdr l)
(cons (car l) (rm5 a (cdr l) oh))))
(else
(let ((new-car (let/cc oh (rm5 a (car l) oh))))
(if (atom? new-car)
(cons (car l) (rm5 a (cdr l) oh))
(cons new-car (cdr l))))))))(rm a (car l) 0)や(rm a l (quote ()))が消えてしまいます
って、やっぱ2回評価される式にletで名前をつける、って言うんなら
同じ式じゃないとよくないんじゃないですかねえ
使われない引数だから何を渡しても結果は同じ
だからletでまとめてもやっぱり結果は同じなんでしょうけど
使われないことに意味がある？
失敗の時の値と同様、使われない値を何にするか考えるのはどうも気分がよろしくないです
失敗した時の値を()にしたりnoにしたり
使われない値を渡すときの値を0にしたり()にしたり
ここまで一貫して一貫性がないのはなにか言いたいことが隠されているに違いない
返されない値や使われない値として適切なものを都度探す必要があるのは面倒
なにかひとつ他には絶対に使われない値を用意しておいたほうがすっきりするでしょうか？
最終版
そしてこんな書き方が紹介されます。
(define rember1*6
(lambda (a l)
(try oh (rm5 a l oh) l)))
(define rm6
(lambda (a l oh)
(cond
((null? l) (oh (quote no)))
((atom? (car l))
(if (eq? (car l) a)
(cdr l)
(cons (car l) (rm6 a (cdr l) oh))))
(else
(try oh2
(cons (rm6 a (car l) oh2) (cdr l))
(cons (car l) (rm6 a (cdr l) oh)))))))使われない引数に0や()を渡している部分は消えてしまいました
(quote no)についても
この版の
rember1*は、noがアトムでないと動きませんか。いいえ。
と言い切っているのでアトムですらなくて良いということに
うーむ
tryって
注には以下のように書いてあります
`(and ...)、(try ...)などは省略形です。
(try x α β) = (letcc success (letcc x (success α)) β)名前
successはαやβの中に現れてはいけません。
αを評価して、普通に評価できたら次にβを評価するはずのところを忘れて
αを評価した値をそのまま返し、
αを評価中に継続xが呼び出されたらαの評価は中断してβの値を返す
他の言語ではraiseとかthrowと書くところをxと書けばだいたい似た感じ
ということが落ち着いて読めばわかるんですが、
letccが入れ子で書いてあるとなんだかややこしく見えてしまいます
if ... then ... else ... をgotoで書いているような感じに近いかなあ
慣れですかねえ
andがschemeに含まれているようにtryも含まれているのかと思いましたが
どうも含まれてない模様
例外の種類も渡せないし単純すぎて実用できないのかも
Racketには例外処理が最初からついてきますが、書き方が違うっぽいです
そこでマクロ定義方法をちょっと調べて作りました
上の定義をほとんどそのまま引き写し
(define-syntax-rule (try x a b)
(let/cc success
(let/cc x (success a))
b))これで上のコードも動いています
意外と簡単
何を教えてくれようとしたの？
結局のところ、失敗の時はtryを使え、それで万事うまくいく、っていう教えだったんでしょうか
それとも、tryみたいなやつはletccで作れるよ！って話？
どうも()を返したりnoを返したりしてるあたりがひっかかってて
読み取るべきことが読み取れたのか不安です
＃成功した場合にあらゆる値を返せて、しかも失敗だったという情報もくっつけられて、
＃でもいちいち失敗だったという情報をチェックしなくていい一貫性のある方法が・・・
＃なんて言いはじめると違う言語の話になってしまうかな
