トリックはこう言う事です。 RT: @valvallow 追記しました ＞vallog: "再帰も"ループも使わずに配列を逆順にする：継続呼び出し編 http://qurl.com/hs8ym

March 12, 2010

トリックはこう言う事です。 RT: @valvallow 追記しました＞vallog: “再帰も”ループも使わずに配列を逆順にする：継続呼び出し編 http://qurl.com/hs8ym

まずは黙って次のコードを見てください。

(defun my-reverse (ls)
  (let ((l ls) (acc '()))
    (loop
	 (if (null l) (return acc))
       (setf acc (cons (car l) acc))
       (setf l (cdr l)))))

これはANSI Common Lispによるコードなんですが、少なくとも、ANSI Common Lispが制定される前のCommon Lispではこう言う形で反復を記述するのが推奨、あるいは初心者向けだったんです。

ANSI Common Lispにはloopと言う構文があって、とにかく悪評高いんですが、実はそれは正確にはextended-loop(拡張されたloop)と呼ばれ、対して古典的なloopはsimple-loop(単純なloop)として区別されています。ANSI Common Lisp制定以降はloopファンはextended-loopに流れて、simple-loopはあまり使われなくなったんですが(実践Common Lispでも最初の方にわずか一例紹介されてるのみ、となりました)、それ以前ではこう言うloopの使い方をしてたんです。

@valvallow さんが看破なされているように、例のコードもこのコードも副作用使いまくり、です。でもCommon Lispは(それどころか古典的なLispの文脈では)実はこう言う感じで手続き的に書かれるのが好まれてたんですね。殆ど形式的にはBASICです。実はCommon Lispで「関数型プログラミング」が言われ出したのは結構新しいんです。90年代以降だと思いますね。SICPで「関数型」に慣れた人たちがその手法をCommon Lispに持ち込んできた、って見た方が正しいでしょう(SICPの初版出版は80年代)。

そして、もう一つ言っちゃうと、call/ccは実は「関数型言語の要素ではない」のです。引数付きgotoとか呼ばれてますが、gotoである以上「太古の怪物」です。つまり、手続き型のものなんです。

call/ccを関数型に組み込むと、Lisp的な関数型特徴に隠蔽されちゃって、ネストが深いところから「どう言う風に脱出するのか」把握が非常に難しくなります(初心者的には)。反面、例のコードも、そして、上のコードは当然call/ccじゃないんですが、いずれにせよ、手続的に書くと「インデントがフラットな印象で」比較的分かりやすいと思います。

上のloopを使ったコードの特徴として

returnと言う脱出構文が存在している
loopと言う特殊な構文が存在している

のが明らかです。両者ともSchemeには備わっていません。

まずは1番目をSchemeで実現するには、形式的にはcall/cc(あるいはlet/cc)を用いて大域脱出を試みれば良いです。つまり、

(define (my-reverse ls)
  (let/cc return
	  ...
	  ...
	  (and (null 何とか) (return 結果))
	  ...
	  ...))

とすれば上のCommon Lispのコードと整合性が取れます。

なお、どうしてandにしてるのか、ifじゃないのか、と言うのは、いつかSkypeで話した通り、Schemeのifでは第3引数が省略された時の返り値が「未定義」だからです。実装によってはエラーを返します。従ってこう言う場合、Schemeではandを使って逃げた方が得策です。一方、ANSI Common Lispのifは第3引数が省略された場合、デフォルトでnil(Schemeで言う空リスト+#f)を返す事が仕様で定められています。

この辺は、Gaucheなんかの「実用性目指して半分Common Lisp」みたいな実装では問題ないんですが、一方PLT Schemeなんかではトラブルの元になるんで気をつけましょう。

2つ目のloopマクロなんですが・・・これちょっとここで説明するのはメンド臭いな(笑)。Common Lispには古のprogと呼ばれる繰り返し用のマクロがあって、それをラップしたものがsimple-loopなんですが、そのprog自体がまた別のblockと言う特殊形式をラップしたもんだったりするんで・・・・・・。イカンな、Common Lispは。便利で高機能なんですが、レイヤーにレイヤー重ねて行ってるんでワケワカメです。一筋縄ではイカン。

いずれにせよ、ここで理解して欲しいのは、progと言うのは「S式のまとまりにタグを設定してそのタグを目指してジャンプする->結果反復となる」と言う事です。Schemeでprog的な動作をエミュレートするには、この知識だけで十分でしょう。

ここでは @valvallow さんの元のコードと整合性を合わせる為、タグをrとします。すなわち、progのエミュレート部分は、

(let ((r #f))
  ...)

とします。暫定的にrに#fと言う値を与えていますが、実はこれは何でも構いません。'()でも良いです。

さて、計算の実行を考えると、 @valvallow さんのコードを参考にする限り、

accに空リストを束縛した状態からスタート -> accには(car l)をconsして再束縛しないといけない
lにlsを束縛した状態からスタート -> lはcdrを取って、再束縛しないといけない
タグrへと飛ぶ(ジャンプする)

と言う三つの作業が必要となります。BASIC的に言うと「そのまんまやねん!」なんですが、一応明文化してみました。

これをSchemeで疑似コードっぽく書くと、

(let ((r #f))
  ...
  (set! acc (cons (car l) acc))
  (set! l (cdr l))
  (goto r))

ですよね。まあ、この辺は問題ない。問題は、

タグrにどうやって情報を記憶させるのか?
rへのジャンプ方法は?

の2点です。そしてここが「もう一個の」call/ccの出番なんです。

call/ccはSchemeが不完全ながらも関数型言語だとすると、殆ど唯一の例外である「手続き型言語の要素である」と言いました。例外なんです。もう一つのcall/ccの持つ例外が

call/ccではクロージャがひっくり返ってる

と言う部分です。

ラムダ式やS式では「括弧の内側」が情報の捕捉対象です。これがSchemeの原則です。一方、call/ccでは「括弧の外側」が情報の捕捉対象なんです。ここのルールがあまり明言されてないんで、call/ccは理解され辛い。Schemeは「設計が一貫した言語」と言うお題目で説明すると、やたら難解な説明になるんですよね。実は違ってて、Schemeはcall/ccの一点でこれが破綻してるんです。そこまで設計は実は一貫していない。だからSchemeの「ルール」に基づいて理解しようとするとやたら難解にならざるを得ない。「おかしな動作に見える」。いや、実際単に「おかしい」んですよ(笑)。

これには実は理由があるんです。R5RS読んでみれば分かるんですが、call/cc自体が「理論的に狙って設計された」ものじゃあ無いんです。

何人かのScheme 実装者が，catch コンストラクトの完全な強力さを，特殊な構文のコンストラクトによってではなく手続きによって用意できることに気付き，そしてその名前call-with-current-continuation が1982 年につくり出された。

これ分かりますかね?つや～に書いてますけど。事実上、何てこたあない、

何か手続きとして実装出来ちゃったから入れてみた。

って言ってるだけ、なんです(笑)。偶発的産物なんですよ(笑)。call/ccってのは。Schemeの登場が1975年。call/ccの登場が1982年。明らかに「狙って作った産物」じゃないんです。何だこの7年のタイムラグは(怒)。

前にTwitterで呟いたりしたんですけど、もう一度、抽象化してλ式、そしてcall/ccのキャプチャリングのルールを明記しておきます。λ式(()で表す)の場合、情報(/で表す)の捕捉対象は「括弧の内側」です。

(//////)

一方、call/cc(] [で表す)の場合、情報の捕捉対象は「括弧の外側」です。そしてその外側にあるλ式までを「ひっくり返ったクロージャ」として認識します。

(///]   [///)

つまり、Scheme慣れしてくると、どうしても「括弧の内側」に目を向けがちですが、call/ccはそうではない。ぶっちゃけた話、call/ccの内側に何があるか、なんてどーでもいい、ってばどうでもいいのです。そこは「対象外」です(文字通り、「クロージャの範囲外」です)。そうじゃなくって、call/ccの「外側」が重要なんです。

ここまで来ると、取りあえず先の「計算ロジック」を捕捉するためには、call/ccをどっか置いてみれば良い、って事になります。

(let ((r #f))
  (let/cc
   ...)
  (set! acc (cons (car l) acc))
  (set! l (cdr l))
  (goto r))

これで、let/ccの後ろのS式三つは全て「let/ccの外側」にあるんで捕捉対象になります。call/ccに認識されるのです。そしてrは認識されるけど#fは認識されません。これは何故か、と言うとletがλ式の構文糖衣である事から分かります。上のコードは下と等価です。

((lambda (r)
   (let/cc
    ...)
   (set! acc (cons (car l) acc))
   (set! l (cdr l))
   (goto r)) #f)

つまり、#fはλ式の「外側」にある。call/ccの外側はその外にあるλ式でせき止められています。従って、call/ccのキャプチャリングの範囲は明確になりました。

このキャプチャリングされた「情報」を抽象的に捉える枠組みが必要です。これが実はcall/ccが取る一引数関数の仮引数なんですよ。@valvallowさんのコードに合わせてcontinueとしますが、例えば

(///]continue   [///)

なんてなってた場合、λ式とcall/ccに挟まれた全情報はcontinueに受け渡されます。つまり、これが「メッセージパッシング」です。言い方変えると「継続受け渡し」ですね。つまり、

(let ((r #f))
  (let/cc continue
	  ...)
  (set! acc (cons (car l) acc))
  (set! l (cdr l))
  (goto r))

とした時点で、λ式とcall/ccに挟まれた全情報はcontinueで表されます。あとは煮るなり焼くなり好きにして状態です。目が潤みまくった女の子みたいですね(笑)。したがって、continueをrに束縛してしまえば、計算指示の情報はrに集約されるわけです。

(let ((r #f))
  (let/cc continue
	  (set! r continue))
  (set! acc (cons (car l) acc))
  (set! l (cdr l))
  (goto r))

あとは、継続は一引数手続きなんで、ダミー引数を何でもいいんでrに与えれば「タグジャンプ」が実現出来ます。

(let ((r #f))
  (let/cc continue
	  (set! r continue))
  (set! acc (cons (car l) acc))
  (set! l (cdr l))
  (r #f))

残りは最初にやった「大域脱出」returnと組み合わせれば完成です。

(define (my-reverse ls)
  (let/cc return
	  (let ((r #f))
	    (let ((l ls) (acc '()))
	      (let/cc continue
		      (set! r continue))
	      (and (null? l) (return acc))
	      (set! acc (cons (car l) acc))
	      (set! l (cdr l))
	      (r #f)))))

とまあ、背後にあるのはこう言う考えです。それとLispの古いコードを参考にしています。

Schemeで「再帰」とか「関数型言語の考え」に慣れちゃうと結構異端に見えるんですが、マジメな話、こう言うコードは古いLispの本だとちょくちょく見かけます。絶対「うげえ」とか思って吐きそうになったりするんですが(笑)、call/ccを理解するには、その手の「前時代的」コードを読むのが結構参考になるんですよ。もう一度繰り返しますが、call/ccが「引き数付きgoto」なら、間違いなく本質的には太古の遺物ですし、そんなにつや～な存在ではありません。明らかに「異質の」シーラカンス的な存在なんです。

参考までにLisp1.5 Programmer’s Manualを紹介しておきます。英語ですが、ザーっと眺めるだけで

「うそお、Lispってこんな書き方してたの???」

と驚く事請け合いです。マジでワンダーランドですよ。

12:36pm | URL: http://tmblr.co/ZHw6OyQO81g

RSS feed: http://cametan-001.tumblr.com/rss

Previous post Next post