本を読む

読書やコンピュータなどに関するメモ

FizzBuzzとGaucheで学ぶ継続の基礎

 先日は酔った勢いで「FizzBuzzとGaucheで学ぶ遅延評価の基礎の基礎」ってエントリを書いてみました。今回は、再び酔った勢いで、同じネタから継続渡しスタイル(CPS:Continuation Passing Style)に挑戦してみます。

 言語は今回もSceme(Gauche)です。継続渡しスタイルの知識は、「プログラミングGauche」と「まるごとJavaScript&Ajax!」の受け売り(劣化コピー)ですので、勘違いがあったらご指摘ください。

遅延評価と継続渡しの比較

 遅延評価編では、無限ループを避けるために遅延評価を使いました。無限ループを避けるための方法としては、ほかに、継続渡しによる呼び出しトランポリンを使った方法があるみたいです。

 とてもおおざっぱにいうと、遅延評価は関数型プログラミングで、継続渡しは手続き型プログラミングなんだそうです。

まず手続き型っぽく書いてみる

 まず、継続は置いておいて、手続き型っぽくループ(単純な末尾再帰)で無限FizzBuzzを書いてみます。

(define (fizzbuzz-from n)
  (let ((item (cond ((zero? (modulo n 15)) "FizzBuzz")
		    ((zero? (modulo n 3)) "Fizz")
		    ((zero? (modulo n 5)) "Buzz")
		    (else n) )))
    (print item)
    (fizzbuzz-from (+ n 1)) ))

 実行してみます

gosh> (fizzbuzz-from 1)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
(略)

 もちろん無限ループですので、Ctrl+Cで止めてください。

リストを返すようにしてみる

 では次に、出力するのではなくリストを返すようにしてみます。遅延評価編とは逆に、ここでは「("Fizz" 2 1)」のように左に伸びていくものとします。

 上のコードを元に、単純に書くと、こんな感じになります。

(define (fizzbuzz-list-from n lst)
  (let ((item (cond ((zero? (modulo n 15)) "FizzBuzz")
		    ((zero? (modulo n 3)) "Fizz")
		    ((zero? (modulo n 5)) "Buzz")
		    (else n) )))
    (fizzbuzz-list-from (+ n 1) (cons item lst)) ))

 もちろん、無限ループですので、実行しても何も返りません。

gosh> (fizzbuzz-list-from 1 '())

再帰呼び出しを分離してみる

 ここまでの例では、ループ相当の末尾再帰を使っていました。では次に、その部分をtsugiという手続き(関数)に分離してみます。

(define (fizzbuzz-list-from n lst)
  (let ((item (cond ((zero? (modulo n 15)) "FizzBuzz")
		    ((zero? (modulo n 3)) "Fizz")
		    ((zero? (modulo n 5)) "Buzz")
		    (else n) )))
    (tsugi (+ n 1) (cons item lst)) ))

(define (tsugi n lst)
  (fizzbuzz-list-from n lst) )

 さらに、このtsugi手続きを引数で渡すようにしてみます。

(define (fizzbuzz-list-from n lst c)
  (let ((item (cond ((zero? (modulo n 15)) "FizzBuzz")
		    ((zero? (modulo n 3)) "Fizz")
		    ((zero? (modulo n 5)) "Buzz")
		    (else n) )))
    (c (+ n 1) (cons item lst) fizzbuzz-list-from) ))

(define (tsugi n lst c)
  (c n lst tsugi) )

 実行結果は、もちろんあいかわらず、無限ループのままです。

gosh> (fizzbuzz-list-from 1 '() tsugi)

 結果はさておき、このバージョンのfizzbuzz-list-fromでは、処理の最後を、引数で渡された「c」という手続き(実体は「tsugi」)に預けていることが重要です。このcを継続と呼ぶみたいです。で、関数の次の預け先を引数で渡すやりかたを継続渡しスタイル(CPS)と呼ぶみたいです。

中断してみる

 分離したことによって、別の手続きを渡せるようになりました。では、「tsugi」のかわりに、「tsuganai」手続きを渡してみます。

(define (fizzbuzz-list-from n lst c)
  (let ((item (cond ((zero? (modulo n 15)) "FizzBuzz")
		    ((zero? (modulo n 3)) "Fizz")
		    ((zero? (modulo n 5)) "Buzz")
		    (else n) )))
    (c (+ n 1) (cons item lst) fizzbuzz-list-from) ))

(define (nobi) '())

(define (tsuganai n lst c)
  (set! nobi (lambda () (c n lst tsuganai) lst))
  '() )

 実行してみます。

gosh> (fizzbuzz-list-from 1 '() tsuganai)
()

 なにやら無限ループにならずに終了しちゃいました。では、nobiを何度か呼び出します。

gosh> (nobi)
(1)
gosh> (nobi)
(2 1)
gosh> (nobi)
("Fizz" 2 1)
gosh> (nobi)
(4 "Fizz" 2 1)
gosh> (nobi)
("Buzz" 4 "Fizz" 2 1)

 めでたしめでたし。

修正2008-05-27:

 tsugi手続きのCPS版とtsuganai手続きが、いまいちCPSっぽくなかったので、以下のように変更。やってることは同じではあるけど。やっぱ酔ってた(←酒のせいにする)。

  • tsugi
    • fizzbuzz-list-from手続きの最後のc手続き呼び出しで、最後の引数をcからfizzbuzz-list-fromに
    • tsugi手続きで呼び出す手続きをfizzbuzz-list-fromからcに
    • そのc手続きの最後の引数をcからtsugiに
  • tsuganai
    • fizzbuzz-list-fromは改訂版と同じ
    • nobiにset!されるクロージャで、呼び出す手続きをfizzbuzz-list-fromからcに
    • そのc手続きの最後の引数をcからtsugiに
プログラミングGauche
プログラミングGauche
posted with amazlet at 08.05.15
Kahuaプロジェクト
オライリージャパン
売り上げランキング: 5302
まるごとJavaScript & Ajax ! Vol.1
天野 仁史 舘野 祐一 川崎 有亮 arton 田中 孝太郎 国分 裕 山本 有悟 海野 裕也 nanto_vi
インプレスジャパン
売り上げランキング: 37629

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://emasaka.blog65.fc2.com/tb.php/393-ea288264

[Gauche]継続と遅延評価

「プログラミングGauche」で理解できずに読み飛ばしてしまっていた「継続」を 大変わかりやすく解説してくれたエントリーをみつけ、思わず欲情欲情してしまった。 例も交えて丁重に解説してくれています。 本を読む FizzBuzzとGaucheで学ぶ遅延評価の基礎の基礎 本を読む Fi

 | HOME | 

Categories

Recent Entries

Recent Comments

Recent Trackbacks

Appendix

emasaka

emasaka

フリーター。
連絡先はこのへん

Monthly


FC2Ad