call/ccの冒険～その2

call/ccの意味の分からないトコは、「無くてもいいじゃん?」って思えるケースがしばしば見受けられるトコです。
この原因の主たるところは、Schemeは明示的にreturnを使うようにはなっていない為じゃないのか、とかちょっと思うんです。
割に、C言語や、その派生モデルの言語の方がcall/ccの意図がつかみ易いのでは、と時々思います。
いずれにせよ、R5RSに以下のように記述されている通り、

call-with-current-continuation の平凡な用途は，ループまたは手続き本体からの構造化された非局所的脱出である。

call/ccの取りあえずの目的は脱出なんです。いわゆるcall/ccの「すげえ機能」と言う一種の誤解は、この「脱出をどう実現してるのか」から出てきた言わば副産物なんですよね。
従って、call/ccで脱出にこだわるのは、call/ccの機能を知る為の第一歩なんじゃないか、と思います。

ところで。ANSI Common LispとSchemeには次のような違いがあります。
ANSI Common Lispの場合、

CL-USER> (car '())
NIL
CL-USER> (cdr '())
NIL
CL-USER> 

となります。
これは、たまにプログラミングに於いてバグになるんですが、上手くすれば非常に便利なんですよね。コードを書く量が劇的に減ります。
実はこれはInterlispと言うLispから受け継いだらしいんですが、はじめは「何て手抜きな事を」と感じる事もなきにしもあらず。しかし、数学的には正しい結果でもあるんです。

空集合の部分集合は空集合自身のみである。

いいですね。魅力的です。
ただし、Schemeは数学的に見てヘンな結果になります。端的に言うとエラーを返す。

> (car '())
car: expects argument of type ; given ()

 === context ===
/usr/lib/plt/collects/scheme/private/misc.ss:74:7

> (cdr '())
cdr: expects argument of type ; given ()

 === context ===
/usr/lib/plt/collects/scheme/private/misc.ss:74:7

> 

ここで、Scheme上でANSI Common Lispのような働きをするextended-carとextended-cdrを書いてみましょう。それぞれxcar、xcdrとします。
恐らく、オーソドックスにSchemeでこれらを書くと、次のようなコードになるでしょう。

(define (xcar lst)
  (if (null? lst)
      lst
      (car lst)))

(define (xcdr lst)
  (if (null? lst)
      lst
      (cdr lst)))

何にも問題ありませんね。至極単純なコードです。実行結果は以下の通り。

> (xcar '())
()
> (xcar '(1 2 3 4 5))
1
> (xcdr '())
()
> (xcdr '(1 2 3 4 5))
(2 3 4 5)
> 

敢えてこれをcall/ccを用いて記述してみましょう。コードは次のようになります。

(define (xcar lst)
  (call/cc
   (lambda (return)
     (car (if (null? lst)
       (return lst)
       lst)))))

(define (xcdr lst)
  (call/cc
   (lambda (return)
     (cdr (if (null? lst)
       (return lst)
       lst)))))

これが脱出です。
考え方としては、要するに普通のcar/cdrなんですが、lstが空リストだった場合エラーになるんで、その条件の場合、car/cdrが作り出す筈の「計算結果を捨てて」空リストを持って脱出するわけです。
これは普通の手続き型言語で考えたらお馴染みでしょう。簡単です。
ただし、

1. call/ccを使わないでも書けるコードなのに、call/ccを使う必然性が見当たらない。


2. 単に構文的にはreturnがあれば済む話なんじゃないか。


3. そもそも、単に脱出する為だけに(call/cc (lambda (hoge) ...))って大掛かりさは何なんだ。

と言う不満があるでしょう。全くもってその通りです。
僕は1番目にずーっと引っかかってたんですよね。call/ccを使わなくても記述可能な場合が多い、んです。他でもっと簡易な代替手段があるのに、それでも敢えてcall/ccを使わなきゃならない理由は何なんだ、と。全くもって意味不明でした。
手続き型言語をやってる人は2番3番は思うでしょう。実際ANSI Common Lispにはreturnとかreturn-fromと言う構文があるんで、call/ccの煩雑さは際立ちます。単に脱出するだけだったらもっと簡易な脱出構文を用意しとけばいいのです。抽象化の失敗の薫りがしますね。
しかし、call/ccの練習、つまり、「慣れ」を考えるなら、敢えて上記のように「call/ccを使わなくても」書ける手続きをcall/ccを使って記述しなおすのは良いと思います。少なくと上の例のように「括弧の中と外が」ひっくり返るような形になるでしょう。文字通りひっくり返るんです。ここ、重要ですよ。

実は、この手の処理の場合、独立した手続きにするより、何かの組み込みとしてcall/ccを使った方が有用性が際立ちます。特に空リストのcarを取ったり、とかcdrを取ってエラーになる、と言うのは、ロジック自体は間違ってないトコでの「Scheme特有の性質」に足を掬われたりするんで、効果は絶大です。

ところで、ANSI Common Lispにはeveryと言う関数が定義されています。述語とシーケンスを引数に取り、シーケンスの全要素が述語を満たすかどうか判定します。
使用例は以下の通り。

CL-USER> (every #'characterp "abc")
T
CL-USER> (every #'oddp '(1 3 5))
T
CL-USER> (every #'> '(1 3 5) '(0 2 4))
T
CL-USER> 

これをSchemeで定義してみます。もちろんオーソドックスには再帰で繰り返し構造を記述して…と言うのが手の一つですが、メンド臭いんで、高階手続きを使って以下のようなコードをでっち上げます。

(define (every pred . arg)
  (not (member #f
        (apply map pred
        (map (lambda (x)
        (cond ((string? x) (string->list x))
       ((vector? x) (vector->list x))
       (else x))) arg)))))

ポイントがいくつかあります。

1. レストパラメータ以降の引数は全て一つのリストに纏められる。


2. Schemeでリストに変換可能なデータ型(シーケンス)はR5RS範疇では文字列とベクタである。


3. 写像手続きmapは結果をリストとして返す。


4. 高階手続きapplyは最後の引数がリストであれば、何を適用しても良い。


5. 手続きmemberは第一引数が第二引数のリストに含まれてるか調べる。


6. Schemeでは空リストも含み、論理的にはリストは#tである。

繰り返しを地道に書くのはメンド臭いです。メンド臭いからこそ写像手続き、あるいは高階手続きが存在します。
論理的には上のような流れで、極めて簡単にSchemeでeveryが実装出来ます。動作も完璧ですよね。

> (every char? "abc")
#t
> (every odd? '(1 3 5))
#t
> (every > '(1 3 5) '(0 2 4))
#t
> 

ってなワケで完成しました。ロジックも穴がありません。
「動けば良い」のならこれでよい。でも、この富豪の時代ではあまり気にならないんですが(正直気にならない)このコードは実は「効率性」から言うと問題があるんです。
上のコードでは手続きmemberを用いて与えられたリスト(apply以降の計算結果)に#fが含まれるかどうか見ています。問題は「1個でも#fが見つかれば、everyと言う定義に反する」って部分なんです。
つまり、計算途中に#fが見つかればそれで既に論理的には結果は明らかに#fなんです。そして、それ以降が#tだろうが#fだろうがどーでも良いのです。しかし、上のコードは律儀に最後までリストを走査します。
もうちょっと細かくapply以降の動作を見てみましょう。

(define (engine-of-every pred . arg)
  (apply map pred
  (map (lambda (x)
  (cond ((string? x) (string->list x))
        ((vector? x) (vector->list x))
        (else x))) arg)))

;; 実行例
> (engine-of-every odd? '(1 2 3 4 5))
(#t #f #t #f #t)
> (engine-of-every > '(1 2 5) '(0 3 4))
(#t #f #t)
> 

上の実行例を見ても分かると思いますが、1つ目の例で言うとリストの2個目の要素が#fだと分かった以上、それ以降の計算は無意味です。2つ目の例でもそうですね。その時点で計算を終わらせればそれでいいのです。
こう言う場合、強制的に計算を終了させるのがcall/ccの役目で、それこそが「脱出」です。call/ccを用いればもうちょっと計算効率が上がります。

(define (engine-of-every pred . arg)
  (call/cc
   (lambda (return)
     (apply map
     (lambda x   ;ここはR5RS参照
       (or (apply pred x)
    (return #f)))  ;脱出
     (map (lambda (y)
     (cond ((string? y) (string->list y))
    ((vector? y) (vector->list y))
    (else y))) arg)))))

;; 実行例
> (engine-of-every char? "abc")
(#t #t #t)
> (engine-of-every odd? '(1 2 3 4 5))
#f
> (engine-of-every > '(1 3 5) '(0 2 4))
(#t #t #t)
> (engine-of-every > '(1 2 5) '(0 3 4))
#f
> 

実はもう殆ど完成してますね。論理的には(#t #t #t)だろうと他のリストだろうと#tです。そして、一個でも#fが見つかった時には即座に計算を終了して#fを持って脱出してます。
このように、結構高階手続きとcall/ccは相性が良いです。高階手続きを設計する際は「call/ccを使う余地が無いか?」考えてみるのが一興でしょう。
なお、上のengine-of-everyで唯一注釈が必要なのは、R5RSに記述されている次のラムダ式の記法でしょう。

<変数>: 手続きは任意個数の引数をとる。手続きが呼び出される時には，実引数の列が，一つの新しく割り付けられたリストへと変換され，そしてそのリストが<変数> の束縛に格納される。

((lambda x x) 3 4 5 6) =⇒ (3 4 5 6)

一種、ラムダ式のレストパラメータと言っても良いのですが、ラムダ式の仮引数が括弧で囲まれてない場合、与えられた引数はリストとして纏められる、と言うルールがあります。あまり有名ではないのですが、覚えておいて損はないでしょう。

実は前回のコードの継続2と言うのは単にこの脱出を行っています。
もう一回コードを再録してみます。見比べてみてください。

(define (sum n)
  (let ((tag #f))   ;タグを設定
    (let ((count 1) (result 1))  ;初期条件
      (call/cc
       (lambda (body)
  ;; 継続1。bodyはここのcall/ccの「外側」をクロージャとして表現したもの。
  ;; 具体的には上部のletから末尾までが範囲となっている。
  ;; (正確にはλ式。つまり、letの束縛された数値は捕捉対象外である。)
  ;; tagはそのまた外側なので継続1には捕捉されない。
  (set! tag body)))   ;そのbodyをtagに代入している。
      (call/cc
       (lambda (return)
  ;; 継続2。ここの継続は継続1内に捕捉されている事に注意。
  ;; 継続1の「外側」に存在しているからである。
  ;; 条件を満たした場合、継続2はresultを持って計算を脱出する。
  (and (= count n) (return result)) 
  (set! count (+ 1 count)) ;手続的計算
  (set! result (+ count result))
  ;; tagへ飛ぶ。tagは事実上一引数関数になってるのでダミー引数'()を渡してる。
  (tag '()))))))