How To Become A Hacker: 継続でフィボナッチ

継続と言うか、call/ccに関してはいつかどこかで纏めて書こうと思ってるんですけどね。
色々継続に関して言うと文句があって(笑)、どっかでキッチリとトドメをさしておきたい(笑)。

それはともかく。
上記リンクに面白いコードが紹介されていました。


def fib
  a, b = callcc {|$c| [0,1] }
  puts b
  $c.call b, a + b  if b < 100
end

fib

上の例が解れば、やってることは同じなので難しくはないと思います。

難しいって(爆)。
Schemeでだいぶ継続慣れした、とか思ってたんですが、いやなかなか。解読するのに時間がかかりました。

一応、フィボナッチ数列の復習してみましょうか。定義はWikipediaに書いてありますがね。
Schemeで定義通りにバカ正直に実装すると次のようになります。


(define (fib n)
  (cond ((zero? n)
  0)
 ((= n 1)
  1)
 (else
  (+ (fib (- n 2)) (fib (- n 1))))))

Rubyだと次のようになるのかな?まあ、Rubyとして適切な書き方かどうかは分かりませんが(注1)。


def fib (n)
  if n == 0
    0
  elsif n == 1
    1
  else
    fib(n - 2) + fib(n - 1)
  end
end

構造的には上のようになりますよね。定義のまんま、って事で。
ただ、この構造は再帰ですけど、二つ再帰で呼び出される手続き(あるいはメソッド)が定義されていて、その計算結果を保持しながらなおかつ加算を行うんで無駄が多いと言えば多いです。
Lispをやってる人は、大抵のLisp処理系には末尾再帰最適化が実装されている筈だ、と信じて(注2)、次のように書く事を好みます。


(define (fib n)
  ;; ローカル手続きloopを定義
  (define (loop m a b)
    (if (zero? m)
 a
 (loop (- m 1) b (+ a b))))
  ;; loopに初期引数を与えて呼び出す
  (loop n 0 1))

Rubyは末尾再帰最適化は行わない筈ですが、末尾再帰自体は次のように書けるでしょう。


def fib (n)
  # ローカルメソッドloopを定義
  def loop (m, a, b)
    if m == 0
      a
    else
      loop(m - 1, b, a + b)
    end
  end
  # loopに初期引数を与えて呼び出す
  loop(n, 0, 1)
end

ご覧の通り、再帰部分で呼び出した手続き(あるいはメソッド)には、手続き(あるいはメソッド)の外で余計な事(例えば足したり引いたり)をしていません。こう言うスタイルの再帰を末尾再帰(tail recursive)と呼んで、特にSchemerは重宝しています。数学的にはgotoでのジャンプ構文と同じそうです。
まあ、実際末尾再帰に煩いのはSchemerくらいなんですけどね(笑)。Cのプログラマは再帰は知ってるけど、末尾再帰って言い方は知らないケースが多いようです。何せ教科書にはほぼ書いてない(注3)。

いずれにしても、この2種類の書き方がフィボナッチ数列の書き方の定番です。

が、「継続でフィボナッチ」と言うのはなかなか目にしないネタなんでビックリですね(笑)。

継続の説明自体は元リンクを見てもらうとして。
call/ccってのはRubyで存在する、ってのは聞いた事あるんですが(元々Schemeの機能)。それを使ったコード自体が初見です。大体、今調べてみたんですが、たのしいRuby 第2版 Rubyではじめる気軽なプログラミングには載ってない(爆)。多分ほとんどのRubyistに対しても謎の機能?
もう一回コード見てみますか。


def fib
  a, b = callcc {|$c| [0,1] }
  puts b
  $c.call b, a + b  if b < 100
end

fib

う～ん。ここままじゃちょっと(Schemeにある程度慣れてる僕には)分かり辛いですねえ。
一旦Schemeに直してみたいと思います。

とは思ったけど、これが結構大変だったんだ(爆)。

まず、Rubyの場合、$記号を付けて宣言された変数はグローバル変数、となる模様です。上のコード例で言うと$cってのがグローバル変数ですね。
つまり、Schemeにはそう言う便利な記法は存在しないんで、明示的にグローバル変数を宣言する必要があります。


(define *c* #f)

グローバル変数*c*の中身は、まあ何でも良いんで、取りあえず#fを束縛しておきます。
このグローバル変数に「継続」と言われるものを束縛するんですね。

次に、Rubyには多重代入と言う機能があります。左側が複数の変数で右辺が配列だった場合、位置的に対応しているもの同士が順番に束縛されていく模様です。


irb(main):001:0> a, b = [0, 1]
[0, 1]
irb(main):002:0> a
0
irb(main):003:0> b
1
irb(main):004:0>

ちょっとこう言う手続き型言語的に便利な機能は、S式のカタマリであるSchemeには存在してないんで(苦笑)。
元のRubyのコード見る限り・・・多値で実装するのが一番近いかなあ。
とは言っても。
Schemeなんかで「多値を返す」のは良く見かけるネタなんですが、一方、「多値を受け取る」のはどうすんだ、と(笑)。
元のコード見ると、最終行で


  $c.call b, a + b  if b < 100

と、また多重代入やってるっぽいんで、多値で「受け取る」事が必要そうなんですが・・・。
ふ～む、どうすっぺえ。ANSI Common Lispのmultiple-value-bindみたいな機能があれば良いんですけどねえ。
仕様書(R5RS)見てみると、次のような事が書いてあります。

(call-with-values producer consumer) 手続き
producer 引数を無引数で呼び出し，そしてある継続を呼び
出す。この継続は，(複数個の) 値が渡されると，それらの
値を引数としてconsumer 手続きを呼び出す。consumer へ
の呼出しに対する継続は，call-with-values への呼出し
の継続である。
> (call-with-values (lambda () (values 4 5))
    (lambda (a b) b))
5
> (call-with-values * -)
-1

うわ、何じゃこりゃ、分かり辛い(苦笑)。
ANSI Common Lispのmultiple-value-bindみたいな形式にしてくれりゃあエエのに。すっげえ見づらいぞ、それ。
まあ、それでも、Rubyのコードとの対比を考えると、保存する領域は最初の変数部分で、そこをcall-with-valuesのconsumer部分で呼び出せば良いのかな。
一応それを方針としてSchemeで書き直してみたのが以下のコードです。


(define *c* #f)    ;継続保存用のグローバル変数

(define (fib)
  (call-with-values
      ;; producer部
      (lambda ()
 (call/cc
  (lambda (k)
    (set! *c* k)   ;継続kをグローバル変数*c*に保存
    (values 0 1))))
    ;; consumer部
    (lambda (a b)
      (display b)
      (newline)
      (and (< b 100)
    (*c* b (+ a b))))))

これに関して言うと、Rubyの方がシンプルだなあ。メゲました(笑)。

ただ、オリジナルのRubyコードだと、ちょっとcall/ccの使い方が大仰しい気もしますけどね。大域変数への継続の保存より、脱出の方がより本質的なんじゃないか、と思います。
と言うのも、Schemeの仕様書にはハッキリこう記述されているんです。

手続きcall-with-current-continuation は，現在の継続を“脱出手続き” (escape procedure) としてパッケージ化し，それをproc に引数として渡す。脱出手続きとは，もし後でこれを呼び出すと，その時たとえどんな継続が有効であっても捨て去り，そのかわりに脱出手続きが造られた時に有効だった継続を使うことになるScheme手続
きである。

call/ccは本来、悩むようなものでもなく、単に「脱出の為に」設計されているんです。方向性の自由度は高いんですが、他の、例えば「継続の保存」ってのは使い方で言うと結構副作用的なんですよ。
脱出とはどう言うものか、と言うと、例えばわざと無限ループを作っておいて、何らかの条件を満たした場合、処理を中断してトップレベルに戻る、とか。割にC言語とかではお馴染みの概念でして、かつ、それ自体は大して難しいものではないんですよね。
例えば、お題のフィボナッチ数列を実装するとして、次のように実装しちゃえばこれは明らかに無限ループなのです。


(define (fib n)
  ;; 無限ループのローカル手続き
  (define (loop m a b)
    (display a)
    (newline)
    (loop (- m 1) b (+ a b)))
  ;; ローカル手続きloopの呼び出し
  (loop n 0 1))

この無限ループのフィボナッチ数列はベースケース(注4)が無いんで止まりません。0から始まって延々とフィボナッチ数を印字し続けます。
もちろん、最初に見た通り、これを「定型的な」フィボナッチ数列の実装として書き直した方が、普通は無難です。
が、敢えてcall/ccを使うとしては、最初のステップとしては、ローカル手続きとその実行部を(call/cc (lambda (c) ...))として包んでしまいます。


(define (fib n)
  (call/cc
   (lambda (c)
     ;; 無限ループのローカル手続き
     (define (loop m a b)
       (display a)
       (newline)
       (loop (- m 1) b (+ a b)))
     ;; ローカル手続きloopの呼び出し
     (loop n 0 1))))

そして、ローカル手続きの第一引数、mが0に到達した時「計算を捨てて脱出すれば良い」ので、評価対象はmになりますね。このロジックを繰り込めば、次のように記述できるでしょう。


(define (fib n)
  (call/cc
   (lambda (c)
     ;; 無限ループのローカル手続き
     (define (loop m a b)
       (display a)
       (newline)
       (loop (- (if (zero? m)  ;ここにベースケースを突っ込む
      (c #f)  ;cは(例えば)#fを持って脱出
      m) 1) b (+ a b)))
     ;; ローカル手続きloopの呼び出し
     (loop n 0 1))))

このように、コードの「無限ループ性」を生かしたまま、call/ccを使った脱出で計算を(ある意味無理矢理)終了させる事が可能なんです。
僕が思うには、こっちの「脱出版」の方が幾分考え方としてはスッキリしてると思います。
Rubyだとどーなるんだろうな(注5)。

注釈:

イテレータの豊富さがRubyの特徴なんで、明らかにこんな書き方はフツーはしないでしょう。

Schemeでは末尾再帰最適化が仕様で要求されています。反面、ANSI Common Lispはそうでもなくって、結果、CLerは、一般的にはそこまで再帰にこだわりません。

とは言っても、実装依存の話になりますが、Cの処理系によっては末尾再帰最適化してくれる処理系もチラホラある模様です。代表的なのがgcc。だから、C系のプログラマでも「末尾再帰」って単語は知っておいて損は無いと思います。
例えば、与題のコードを末尾再帰でCで書けば以下のようになるでしょう。多分。


#include <stdio.h>
#include <stdlib.h>

int fib(int m, int a, int b);

int main(int argc, char *argv[])
{
    int (*pM)(int m, int a, int b);

    pM = fib;
    
    if (argc != 2) {
 printf("パラメータの数が違います。\n");
 return 1;
    }

    (*pM)(atoi(argv[1]), 0, 1);

    return 0;
}

int fib(int m, int a, int b)
{
    printf("%d\n", a);
    if (m == 0) {
 return a;
    } else {
 return fib(m - 1, b, a + b);
    }
}

これをgccで最適化レベル2、-Sオプションを合わせてコンパイルすると次のアセンブリコードを吐き出します。


 .file "fib.c"
 .section .rodata.str1.1,"aMS",@progbits,1
.LC0:
 .string "%d\n"
 .text
 .p2align 4,,15
.globl fib
 .type fib, @function
fib:
 pushl %ebp
 movl %esp, %ebp
 pushl %edi
 pushl %esi
 pushl %ebx
 subl $28, %esp
 movl 8(%ebp), %esi
 movl 12(%ebp), %ebx
 movl 16(%ebp), %edi
 jmp .L3
 .p2align 4,,7
 .p2align 3
.L6:
 leal (%edi,%ebx), %eax
 subl $1, %esi
 movl %edi, %ebx
 movl %eax, %edi
.L3:
 movl %ebx, 8(%esp)
 movl $.LC0, 4(%esp)
 movl $1, (%esp)
 call __printf_chk
 testl %esi, %esi
 jne .L6
 addl $28, %esp
 movl %ebx, %eax
 popl %ebx
 popl %esi
 popl %edi
 popl %ebp
 ret
 .size fib, .-fib
 .section .rodata.str1.4,"aMS",@progbits,1
 .align 4
.LC1:
 .string "\343\203\221\343\203\251\343\203\241\343\203\274\343\202\277\343\201\256\346\225\260\343\201\214\351\201\225\343\201\204\343\201\276\343\201\231\343\200\202\n"
 .text
 .p2align 4,,15
.globl main
 .type main, @function
main:
 pushl %ebp
 movl %esp, %ebp
 andl $-16, %esp
 subl $16, %esp
 cmpl $2, 8(%ebp)
 je .L8
 movl $.LC1, 4(%esp)
 movl $1, (%esp)
 call __printf_chk
 movl $1, %eax
 leave
 ret
 .p2align 4,,7
 .p2align 3
.L8:
 movl $10, 8(%esp)
 movl $0, 4(%esp)
 movl 12(%ebp), %eax
 movl 4(%eax), %eax
 movl %eax, (%esp)
 call strtol
 movl $1, 8(%esp)
 movl $0, 4(%esp)
 movl %eax, (%esp)
 call fib
 xorl %eax, %eax
 leave
 ret
 .size main, .-main
 .ident "GCC: (Ubuntu 4.4.1-4ubuntu8) 4.4.1"
 .section .note.GNU-stack,"",@progbits

僕は残念ながらアセンブリは読めないんですが、アセンブリが読める人は、gccがCによる末尾再帰コードを単なるジャンプ構文に変換しているかどうか確かめてみてください。

終了条件の事。

Rubyでも書けるか、とトライしてみたが、callccが持つブロックの作用が良く分からず挫折致しました(爆)。

How To Become A Hacker

2009年12月28日月曜日

継続でフィボナッチ

0 件のコメント:

コメントを投稿

Twitter

Apprentice Hackers

リンクリスト

ブログアーカイブ

Tag Cloud

Recent Comments