なんでも再帰

消えるループ

簡単だけど、よくありそうな例として、こんなのを考えてみよう。 入力テキストの行数を数える関数count_linesを書きたい。 Cで書くとすれば、こんな感じだ。

    /* 例1 */
    int count_lines(void)
    {
        int count = 0, c;
        for (c=getchar(); c!=EOF; c=getchar()) {
            if (c == '\n') count++;
        }
        return count;
    }

Schemeにも明示的なループを記述するdo構文がある。 敢えてC風に記述すれば、こんな感じになる。

    ;; 例2
    (define (count-lines)
      (let ((count 0))
        (do ((c (read-char) (read-char)))    ;c=getchar()
            ((eof-object? c) count)          ;EOFならreturn count;
          (if (char=? c #\newline)
              (set! count (+ count 1))))))

do構文ではループ終了テストが2番目の引数に来ることを除けば、ほぼ一対一に コードが対応しているのがわかると思う。 しかし、do構文はカッコがたくさんあってどうもわかりにくい (*1)。Scheme好きな私でさえそう思うくらいだ。

もちっと、「Schemeらしい」書き方(私の主観だが)をしてみよう。

    ;; 例3
    (define (count-lines)
       (define (loop count)
         (let ((c (read-char)))
          (cond ((eof-object? c) count)
                ((char=? c #\newline) (loop (+ count 1)))
                (else                 (loop count)))))
       (loop 0))

ループ構文が消えてしまった。代わりにローカル関数loopを定義して、 そいつを再帰的に呼び出している (*2)。 そう、Schemeプログラマは再帰が大好きで、 とにかくなんでもかんでも再帰で書きたがる。

手続き型言語では、再帰はイメージが悪い。 よく例に出されるQuick Sortみたいに 本質的に再帰的なアルゴリズムならともかく、ループで書けるものを わざわざスタックを消費して再帰にするなんて、というわけだ。 だが、Schemerが再帰を好むのは、単に「ループは再帰で書き直せる」という アルゴリズムのクラスの教科書の記述を確かめたいからじゃない。 ちゃんと実用上の利点があるんだ。

再帰は重いのか

まず、あなたが「再帰は重い」という概念を持っているとしたら、 それを捨ててもらわなくちゃならない。

ローカル関数loopの定義をよく見てみよう、EOFの場合以外は、 それぞれ分岐した枝の最後でloopそれ自身を呼んでいる。 カッコをとっぱらって疑似コードで書いてみると分かりやすいかも。

    ;; 例4
    define loop(count)
      c = read-char()
        c == EOFならcountを返す
        c == '\n' なら loop(count+1) を呼ぶ
        それ以外なら loop(count) を呼ぶ
    

関数ボディ内で、条件によって処理が3つに分岐している。こんなふうに、 処理がフォークのように分岐してゆくパターンは、普段のプログラミングで 良く出て来る。 関数の一番最後の処理(分岐がある場合は、それぞれの分岐した枝の先の最後の処理) が関数呼び出しである場合、それを末尾呼び出し(tail call)という。 この例のように、末尾呼び出しが再帰的に行われるのは末尾再帰という。

Schemeの大きな特徴は、tail callがgotoと等価になることだ(*3)。 すなわち、例4の疑似コードは、あたかも次の疑似コードのように評価される。

    ;; 例5 (*4)
    loop:
      c = read-char()
        c == EOFならcountを返す
        c == '\n' なら count = count+1; goto loop;
        それ以外なら count = count; goto loop;
    

Gotoと言ってもブロックの先頭に飛んでいるだけだから、Perlでのnext文や Cのcontinue文と同じことだ。これは、理論上そうなるってだけじゃなくて、 実際に計算機の上で実行されるコードが、next文やcontinue文と同じってことだ。 例3に示した再帰のプログラムは、実行時型検査などの点を除けば 例1のCプログラムと同じように実行される。実際、型情報も取り扱えるように 拡張されたSchemeコンパイラなら、例1のCプログラムをコンパイルしたのと ほとんど同じ機械語を生成するはずだ。

末尾再帰がループと同等に実行されるのは、コンパイラによるオプショナルな最適化ではない。 Schemeは、末尾呼び出しでスタックを消費しないことを言語規格上要求している。

Schemeプログラマは、例3のコードから例5の処理を一瞬で思い浮かべる。 いや、思い浮かべるというよりも、例3のコードと例5の処理は全く同一、 不可分なものとして認識されていると言ったほうがいいかな。 「処理」という漢字を見て「しょり」という読みを思い浮かべるみたいなもんだ。 もちろん、プログラムを書く時には、例5の様なアルゴリズムを考えて、 それを自然にコードに書き下すと、例3のコードになるというわけだ。

ループと末尾再帰のコードを同一視するには多少慣れが必要だけれど、 よく現われるパターンというのはある。 CやPerlのループ構文では、何もしなければループが継続し、 中断したいときはbreakやlastを使う。 再帰で繰り返しを書く時には、逆に何もしないとループから抜けて、 繰り返したい時に末尾呼び出しを使うんだ。 これは、Perlの名前つきブロックに良く似ている。

相互末尾再帰

再帰より明示的ループの方がわかりやすいのに、なんでわざわざ再帰にするの? という疑問がまだあるかもしれない。ちょっと問題を複雑にしてみようか。 今度は、行数のかわりに単語の数を数えてみよう。ここで、単語とはひとつ以上の空白文字 で区切られた文字列であるとする。Cで書くならこんな感じだ。コメント内の数字は、 後のSchemeコードとの対応をわかりやすく示すためのものだ。

    /* 例6 */
    int count_words() 
    {
        int count = 0;       /* カウンタ */
        int ws = TRUE;   /* 直前に読んだ文字が空白ならTRUE */
        int c;
        for (c=getchar(); c!=EOF; c=getchar()) {
            if (isspace(c)) {
                ws = TRUE;            /* [1] */
            } else {         
                if (ws) count++;      /* [2] */
                ws = FALSE;           /* [2],[3] */
            }
        }
        return count;
    }

再帰を使って書く場合、ループ内で変更される変数を引数にする。こんな感じだ。

    ;; 例7
    (define (count-words)
       (define (loop c ws count)
          (cond ((eof-object? c) count)
                ((char-whitespace? c) (loop (read-char) #t count)) ; [1]
                (ws    (loop (read-char) #f (+ count 1)))          ; [2]
                (else  (loop (read-char) #f count))))              ; [3]
       (loop (read-char) #t 0))

Cのコードにあった、代入やインクリメントが消えてしまった。それらは、再帰的に 呼び出す関数への引数渡しという形に変換されている。例えば、読んだ文字c が空白文字で無く、かつフラグwsが真の場合([2])、次の ループのwsには偽が渡され、 countには(+ count 1) が渡されている。 (なお、ここでは読み込んだ文字cも引数にしてしまっているが、 スタイルの問題。 例3のように、loopのボディでlet文を使ってもいい。 私はわりと何でも引数にしてしまう質だ)。

ところで、上の実装では、直前に空白文字を読んでいるかどうかという 状態を記憶しておくためにフラグwsを導入していた。 変数を使うかわりに、直前に空白文字を読んだ時に呼ばれる関数と そうでない場合に呼ばれる関数とを別々に定義しておいて、どちらの関数が 呼ばれているかで現在の状態を表す、という手法がある。 前者をin-space、後者をin-wordという 関数で表現してみたものが、次のコード例だ。

    ;; 例8
    (define (count-words)
       (define (in-word c count)
          (cond ((eof-object? c) count)
                ((char-whitespace? c) (in-space (read-char) count))
                (else                 (in-word (read-char) count))))
       (define (in-space c count)
          (cond ((eof-object? c) count)
                ((char-whitespace? c) (in-space (read-char) count))
                (else                 (in-word (read-char) (+ count 1)))))
       (in-space (read-char) 0))

in-spaceとin-wordがお互いを 再帰的に呼び合っているので、相互再帰と言ったりする。 この場合でも、お互いの呼び出しは必ず関数のいちばん最後にあるから、 末尾再帰と言える。末尾呼び出しをgotoに置き換えて処理の流れを 疑似コードを示してみよう。

    ;; 例9
    define count-words()
        c = read-char();
        count = 0;
        goto in-space;
      in-word:
        if c == EOF return count;
        if whitespace(c) { c = read-char(); goto in-space; }
        else             { c = read-char(); count += 1; goto in-word; }
      in-space:
        if c == EOF return count;
        if whitespace(c) { c = read-char(); goto in-space; }
        else             { c = read-char(); goto in-word; }

さらに、ダブルクオートで囲まれた部分については、そのダブルクオートが閉じられるまでを (例え空白文字が中にあっても)一単語と数える、という仕様にしてみようか。 クオートされた文字列注にダブルクオートを含める場合はバックスラッシュでエスケープ するものとする。

現在、ダブルクオートで囲まれた文字列を読んでいる、という状態を 関数in-quoteに対応させてみたものが次のコードだ。

    ;; 例10
    (define (count-words)
       (define (in-word c count)
          (cond ((eof-object? c) count)
                ((char-whitespace? c) (in-space (read-char) count))
                ((char=? c #\")       (in-quote (read-char) (+ count 1)))
                (else                 (in-word (read-char) count))))
       (define (in-space c count)
          (cond ((eof-object? c) count)
                ((char-whitespace? c) (in-space (read-char) count))
                ((char=? c #\")       (in-quote (read-char) (+ count 1))
                (else                 (in-word (read-char) (+ count 1)))))
       (define (in-quote c count)
          (cond ((eof-object? c) (error "EOF in quoted word"))
                ((char=? c #\")       (in-space (read-char) count))
                ((char=? c #\\) (read-char) (in-quote (read-char) count))
                (else                 (in-quote (read-char) count))))
       
       (in-space (read-char) 0))

各々の関数が現在の状態を表しており、次に呼び出す関数が次の状態への遷移であると 考えると、上記のコードは状態遷移図そのままであるとも言える。フラグによって 状態を管理する実装と、どちらが見やすいか、というのはケースバイケースだが、 条件が入り組んで来ると、相互再帰で書かれたコードの方が見やすいと私は思う。

これでもまだ再帰のメリットに納得しない? なら、こんな仕様はどうかな。 上記の仕様に加えて、開き括弧が出て来たら、閉じ括弧が出て来るまでを 一単語とみなす。但し、括弧はネスト可能、つまり、 `abc (def (ghi) jkl) mno' は、`abc', `(def (ghi) jkl)', `mno' の3単語とみなすんだ。 但しダブルクオートで囲まれた文字列の中では括弧は機能しないとする。さてどうだ (*5)。

    ;; 例11
    (define (count-words)
      (define (in-word c count)
        (cond ((eof-object? c) count)
              ((char-whitespace? c) (in-space (read-char) count))
              ((char=? c #\")       (in-quote (read-char) (+ count 1) #f))
              ((char=? c #\()       (in-paren (read-char) (+ count 1) #f))
              (else                 (in-word (read-char) count))))
      (define (in-space c count)
        (cond ((eof-object? c) count)
              ((char-whitespace? c) (in-space (read-char) count))
              ((char=? c #\")       (in-quote (read-char) (+ count 1) #f))
              ((char=? c #\()       (in-paren (read-char) (+ count 1) #f))
              (else                 (in-word (read-char) (+ count 1)))))
      (define (in-quote c count nested?)
        (cond ((eof-object? c)      (error "EOF in quoted word"))
              ((char=? c #\")       (if nested?
                                        count
                                        (in-space (read-char) count)))
              ((char=? c #\\) (read-char) (in-quote (read-char) count nested?))
              (else                 (in-quote (read-char) count nested?))))
      (define (in-paren c count nested?)
        (cond ((eof-object? c)      (error "EOF in parenthesis"))
              ((char=? c #\()       (in-paren (read-char) count #t)
                                    (in-paren (read-char) count nested?))
              ((char=? c #\))       (if nested?
                                        count
                                        (in-space (read-char) count)))
              ((char=? c #\")       (in-quote (read-char) count #t)
                                    (in-paren (read-char) count nested?))
              (else                 (in-paren (read-char) count nested?))))
      (in-space (read-char) 0))

ネストした括弧の処理は、本質的に再帰的な処理だ。 だから、括弧の中を処理するルーチンin-parenの中で、 括弧やダブルクオートが出て来た場合に、それぞれを処理するルーチンを再帰的に 呼んでいる。ネストした処理に関わるin-parenとin-quote はネスト中かどうかのフラグを取り、もしネスト中であればin-space に制御を渡さずにそのままリターンする (例11ではcountを返しているが、 実はその結果は無視されるので何を返しても良い。)

単語の数を数えるという処理に限っていえば、Cでも括弧のネスティングレベルを 数えることにより実現できるけれど、もしこれが入力を解析して何らかの構造を 組み立ててゆくようなプログラムだったらどうだろう。 Cだと、結局自分でスタック的な構造を書くか、再帰を使うしかなくなるだろう。 Schemeでは、全く同じパターンでコードが書ける。 本質的な処理の流れが同じなら、コードも同じように書けてしかるべきだ。 これが、プログラミング言語の抽象化の能力だ。

開かれたループ

ま、再帰を使おうがフラグ＋ループ構文を使おうが、コードの見やすさは慣れの問題だ。 しかし、再帰コードには、ループ構文ではちょっと出来ない芸当もできる。

次のコードは、例8のコードに加え、引数user-charで 与えられた文字に出会った際に、引数user-procで与えられた 関数に制御を移すものだ。つまり、この関数を使う人が振舞いをカスタマイズできる と思ってもらえば良い。

    (define (count-words user-char user-proc)
       (define (in-word c count)
          (cond ((eof-object? c) count)
                ((char-whitespace? c) (in-space (read-char) count))
                ((char=? c user-char) (user-proc (read-char) (+ count 1)))
                (else                 (in-word (read-char) count))))
       (define (in-space c count)
          (cond ((eof-object? c) count)
                ((char-whitespace? c) (in-space (read-char) count))
                ((char=? c user-char) (user-proc (read-char) (+ count 1)))
                (else                 (in-word (read-char) (+ count 1)))))
       (in-space (read-char) 0))

この関数を次のように呼び出せば、例10と同じ動作をする。

    (define (in-quote c count)
       (cond ((eof-object? c) (error "EOF in quoted word"))
             ((char=? c #\")  (in-quote (read-char) count))
             (else            (count-words (read-char) count))))

    (count-words #\" in-quote)

関数count-wordsが複雑な動作をするブラックボックスであったとしても、 ユーザーは自分の好きな動作をプログラムした関数を渡して、部分的に処理を 置き換えることが出来る。 末尾再帰を正しく処理するScheme実装ならば、 user-procの末尾呼び出しはスタックを消費しない。 また、ユーザが定義した関数in-quoteからcount-words を呼び出す時もスタックを消費しない。それぞれの関数ブロックへの先頭へジャンプすることで、 あたかもcount-wordsとin-quote全体が 一つのループになったかのように実行される*6。

また、ユーザ関数は、繰り返しを続けたい時のみcount-wordsを呼べば良い。 繰り返しを途中で止めたければ、普通に値を返すだけだ。 それが最初に呼ばれたcount-wordsの戻り値となる。

Cでループ構文を使った場合でも、関数ポインタを渡すようにすれば ユーザによる拡張は実現できる。しかし、ユーザ関数を呼ぶ時に スタックフレームが消費されるし、ユーザ関数がループを中断できるようにするには また別のメカニズムが必要になる。

in-quoteは任意のクロージャで良いから、in-quote自身が 他の関数の内部で定義された関数であってもよい。次の関数は、 ユーザから渡された文字quoterをクオート文字として、 count-wordsを呼び出す関数だ。 この例では、 二つの独立した関数(count-words, count-words-with-quote) の中でローカルに定義されたコードブロックをまたがって処理のループが構成されることになる。

    (define count-words-with-quote quoter)
       (define (in-quote c count)
         (cond ((eof-object? c)   (error "EOF in quoted word"))
               ((char=? c quoter) (in-quote (read-char) count))
               (else              (count-words (read-char) count))))
       (count-words quoter in-quote)

Schemeプログラマが再帰を好んで使う理由は、こんな柔軟性なんだ。

脚注

• *1: この例はCと対応が取りやすいように、 やや冗長に書いてある。 行数のカウンタnはわざわざlet で導入しなくても、ループ変数にしてしまえばいいし、そうすると 副作用のあるset!も消えてすっきりする。 こいつがScheme風味のdoループ：

      (define (count-line)
        (do ((c     (read-char) (read-char))
             (count 0           (if (char=? c #\newline) (+ count 1) count)))
            ((eof-object? c) count)
          ))

  こういう、ボディーが空のdoループはちょっとした繰り返しを書きたい時には良く使う。

• *2: ちなみにこの例も説明のために 冗長に書いている。ループが一重だけの処理なら、私はnamed-let構文の方が好みだ。

      (define (count-line)
         (let loop ((c     (read-char))
                    (count 0))
            (cond ((eof-object? c) count)
                  ((char=? c #\newline) (loop (read-char) (+ count 1)))
                  (else                 (loop (read-char) count)))))

  named-let構文は一種のsyntax sugarで、展開されると例に上げたコードと ほぼ同一になる。

• *3: gotoと言っても、例5に示すように ブロックの先頭に飛ぶだけだから、無制限なgotoのような弊害は無い。 処理系は、どの変数がどの期間にアクティブなのかを静的に解析できる。 もっとも、それが出来るのはSchemeの変数束縛のセマンティクスがあればこそ なのだが。

• *4: ここでは、ループ変数countが gotoの直前に新しい値に更新されるように書いたが、厳密にいうとこれは誤り。 ループ変数は代入されるのではなく、毎回新しい束縛として生成される。 例えば、5つの関数のリストを返す次のコードを考えてみる：

      (define (foo)
         (define (loop x r)
            (if (= x 5)
                (reverse r)
                (loop (+ x 1) (cons (lambda () x) r))))  ; [1]
         (loop 0 '()))

  ループの度に[1]で、ループ変数xをクローズするクロージャを生成している。 都合5つ、そのようなクロージャが作られるが、それぞれのクロージャは別々のx を見ている。

      (define l (foo))   ; 関数5つのリスト
      ((car l)) ==> 0    ; 最初のクロージャのxは0
      ((cadr l)) ==> 1   ; 次のクロージャのxは1

• *5: 3/29/2002までの版では、 ここの例は間違っていた。ネストしているかどうかのフラグを取らずに、 in-parenを再帰的に呼び出していたのだが、ネスト中かどうかで 閉じ括弧の後の処理を変える必要があるのでそれではうまく動かない。

• *6: トップレベルで定義された関数への 末尾呼び出しは、処理系によってはgotoにできない場合がある。各トップレベル関数を Cの関数としてコンパイルするような処理系だ。下位のコンパイラとして Cを使っている限り、Cの制限に縛られてしまうわけだ。そのような処理系は 厳密な意味ではR5RS準拠とは言えない。 確かScheme48は、モジュール全体をひとつのでっかいCの関数にコンパイルすることで、 トップレベルの関数への末尾呼び出しを本当にgotoで実現していた、と思う。