2016/06/04

Scheme修行のtryについて

Scheme修行

Scheme修行

p89の欄外で補足されているtryについて.
これが出てきたのは rember1* の実装の中です.
rember1*atom aとリストlを引数に取ります.
lの中で最初に出てきたaと同じアトムを削除して新しいリストを返す手続きです.

tryを使う前の実装は以下になります.

(define rember1*
  (lambda (a l)
    (if (atom? (let/cc oh (rm a l oh)))
        l
        (rm a l (quote ())))))

(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
      (let ((new-car
             (let/cc oh
               (rm a (car l) oh))))
        (if (atom? new-car)
            (cons (car l)
                  (rm a (cdr l) oh))
            (cons new-car (cdr l))))))))

リストの中で最後まで探し終わってlがnullになれば継続に(quote no)を渡します.
atomであればcarにリストはないのでcdrを探します. 再帰的に探して,aと同じものがあれば,それを取り除いた残りのリストを返します.
取り除くのは最初に見つかったものだけです.
このコードをtryを使うとこうなります.

(define rember1*
  (lambda (a l)
    (try oh (rm a l oh) l)))

(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
      (try oh2
           (cons (rm a (car l) oh2)
                 (cdr l))
           (cons (car l)
                 (rm a (cdr l) oh)))))))

tryについてはここでページ欄外に

(try x α β)
=
(let/cc success
  (let/cc x
    (success a))
  b)

と書かれています.
ここがなかなかわかりませんでした.

まず中のlet/ccから考えます.

(let/cc x
  (success α))

α内で継続xが使われているはずです.
継続xに値γが渡されると,(let/cc x γ)となり,次の計算βに進みます.

継続xに値が渡されない場合はαの値が継続successに渡され,そこで計算が終了しこの式の値はαとなります.
つまり,tryはα内で継続xに値が渡されればβの値が返り,
渡されなければαの値が返るわけです.
元の式で継続に値が渡されたのを判別するために(quote no)を継続に渡してatom?で判別していたものを
継続が返ってくるかこないかで判別できるようになっています.

継続難しいです.
でもScheme修行で少しずつわかってきた気がします.


© 2022 wat-aro