functional programming in Lisp

2012-12-02 Sun

functional programming in Lisp

この記事は LL/ML Advent Calendar 2 トラック目 2 日目の記事です。 Twitter でふらふらしていたら巻き込まれました。コワイ！

L をふたつ入れるために大仰なタイトルをつけてしまったので、 Lisp はマルチパラダイム言語であるとか、 Common Lisp は素敵なオブジェクト指向言語でもあるとか、 Scheme は Algorithmic Language だと RⁿRS にも書いてあるとか*1、そういう前書きがあったのですが、そういうのはばっさりカットして、今回は（正格評価の）関数型プログラミング言語でよく話題になる末尾呼び出しについて書きます。

末尾呼び出し？

まずは「末尾呼び出し」や「末尾呼び出しの最適化」という言葉の意味を簡単におさらいしておきます。必要のない人は読み飛ばして構いません。

末尾文脈（tail context）における手続き（関数）呼び出しのことを末尾呼び出し（tail call）と呼びます。末尾文脈というのは、手続き本体の最後の式、及び、末尾文脈に現れる if の then 側や else 側の最後の式、 let の本体部分の最後の式などを言います。大雑把に言うと、その式の評価結果の値が、そのまま現在の関数の戻り値になるような場所のことです。詳しくは、 R6RS 11.20 Tail calls and tail contexts を参照してください（言語によっては言語仕様によって末尾文脈が明確に定義されていない場合もありますが、その場合は一旦 Scheme に落として考えてみるとよいでしょう）。

ある処理系で、末尾文脈における手続きの呼び出しの回数に制限がない（末尾呼び出しによりリソースを消費しない）とき、その処理系は真正末尾再帰的（properly tail recursive）である、と言います（R6RS 5.11 Proper tail recursion。言語によっては処理系が真正末尾再帰的であるかどうか仕様で定めていない場合もありますが、正格評価の関数型プログラミング言語を名乗る言語であれば、その処理系は真正末尾再帰的であると思ってよいようです）。

末尾文脈における手続き呼び出しを、リソースを消費しない形に最適化することを末尾呼び出しの最適化（tail call optimization）と呼びます。例えば、次のような手続き f、 g、 h があるとき、

(define (f x)
  (+ x (g x)))

(define (g x)
  (h (+ x x)))

(define (h x)
  (/ x 2))

f 中の +、 g 中の h、 h 中の / の呼び出しは末尾呼び出しです。 f の中の g の呼び出しは、 g から返ったあと、その戻り値を x と足すことを覚えていないといけません。それに対して g の中の h の呼び出しの場合、返ってきたあとにすることは、戻り値をそのまま g を呼び出した側に返すだけです。このとき h が g から呼ばれたことをわざわざリソースを使って覚えていなくても、 g を呼び出した手続きから直接 h を呼び出したように書き換えても意味は変わりません（エラー時のスタックトレースが変わりますがそれは置いておきます）。末尾呼び出しの最適化の裏側で起こっているのは概ねこのようなことです。

言語（または言語処理系）によっては、一般の末尾呼び出しではなく、自己末尾再帰（末尾位置における自分自身への再帰呼び出し）の最適化しかサポートしない場合があります。そのような場合は、特に、「末尾再帰の最適化」のように呼びわけます。

「末尾最適化」のような呼び方はよく見掛ける誤りです。

Scheme の末尾呼び出しの最適化は、アクター理論との関わりの中で生まれた（R5RS 3.5 Proper tail recursion）ものなのですが脇道なのでここでは措きます。

さて、長い前置きはこのくらいにして、実際に末尾呼び出しの使いどころを見てみましょう。

例 1: ループ

いちばん有名なのは手続き型言語のループの書き換えです。

while が下のようなマクロで書けるというアレです。

(define-syntax while
  (syntax-rules ()
    ((_ expr e1 es ...)
     (let loop ()
       (cond (expr
              e1 es ...
              (loop)))))))

この (let name (‌(v expr) ...) body ...) という構文は、 (define (name v ...) body) で name という手続きを定義し、(name expr ...) を呼び出すのとほぼ同じ意味です（ただし、 expr ... を評価するとき name はスコープに入りません）。

よくあるループ変数の値が n ずつ増加する for ループは下のように書けますし、

(define (for init step end f)
  (let loop ((i init))
    (when (< i end)
      (f i)
      (loop (+ i step)))))

二本のリストを取り、それぞれのリストから要素をひとつずつ順に取り出して掛け、その和を求めるようなものは次のように書けます（単純に sum-prod を再帰呼び出しせず、結果を溜め込む引き数（accumulator） acc を取るようなローカル手続きを定義するのがミソです）。

(define (sum-prod xs ys)
  (let loop ((xs xs)
             (ys ys)
             (acc 0))
    (if (or (null? xs) (null? ys))
        acc
        (loop (cdr xs) (cdr ys) (+ (* (car xs) (car ys)) acc)))))

手続き型のループで変数に再代入していた部分が手続き適用による引き数の再束縛になっています。ひとつのリストから要素を取り出してループするための foreach 構文のある言語もありますが、その場合でもふたつのリストから並行して要素を取り出そうとすると、結局 for や while でベタ書きしないといけなくなります。

手続き型言語の for や while は、単純なループの場合は簡潔に書くことができるのですが、条件が複雑になったり、ループ変数が複数になった場合、

var x = ...;
var y = ...;
while (true) {
  ...
}

と外側でループ変数を宣言し無限ループをしておいて、内側の if で break したりというコードになりがちです。

手続きの末尾呼び出しで書いた場合は、ループ変数が増えたら単に手続きの引き数を増やせばよいだけですし、ループの中断も、自身を呼び出さない、という形で常に一貫しています。また、手続き型スタイルで変数の多いループを書くと、ループ内部で代入している見逃していないか不安になってきますが、末尾呼び出し版を関数型スタイルで書いているかぎりは、常に手続きの引き数にだけ注目していればよいので安心です。

例 2: 再実行

末尾呼び出しの最適化が嬉しいのは単純なループの場合だけではありません。

例えば次のような手続きがあるとしましょう。

(define (quux)
  (let ((x (foo))
        (y (bar))
        (z (baz)))
    (cond
     ((case-a?) ...)
     ;; 以下何十行か続く
     ...
     )))

この cond の分岐のどこかで問題があったとき、少し条件を調節して cond の部分から再実行したい場合にはどうしたらよいでしょう。

ここでも末尾呼び出しが役に立ちます。

cond を (let retry () ...) で包んでやって、

(define (quux)
  (let ((x (foo))
        (y (bar))
        (z (baz)))
    (let retry ()
      (cond
       ((case-a?) ...)
       ;; 以下何十行か続く
       ...
       ))))

cond 内の末尾文脈で (retry) してやるだけでいつでも再実行することができます。再実行に条件を付けたい場合（n 回再実行して駄目だったら諦める等）も retry に引き数を足してやるだけで簡単に実現できますし、末尾呼び出しの最適化のおかげで効率も goto と変わりません。言わば、引き数付きの goto です。 Lambda: the Ultimate GOTO!

ad-hoc に retry のようなものを入れるのではなく、プログラム全体を継続渡しにしたり、 call-with-current-continuation で継続を取り出したりすると、プログラムを任意の状態で中断したり再実行したりできるようになります。

例 3: 状態機械

ループの場合の変化形ですが、末尾呼び出しの最適化があると、状態機械が綺麗に書けます。

例えば、逆引き Scheme の状態機械の記事はそのような例です。

上記の例では、各状態の持つ変数の個数は同じですが、ある状態にだけ有効な変数が欲しい場合は単に手続きの引き数を増やしてやればよいだけです。

ML や Haskell のような静的型付きの関数型プログラミング言語の場合は、状態をバリアント（代数データ型、判別共用体）で表すようにした方が網羅性チェックができてうれしいかもしれません。

おまけ: 末尾呼び出しの落とし穴

このように便利な末尾呼び出しの最適化ですが、ひとつだけ落とし穴があります。末尾呼び出しのつもりが末尾呼び出しになっていなかった、というものです。

手続きの引き数部分で再帰呼び出しをしていてアイエエ！？スタックオーバーフロー！？スタックオーバーフローナンデ！？というのは stackoverflow.com でもよく見かけるスタックオーバーフロー事例ですが、そういったものは理解が進むうちに自然としなくなるでしょう。

その次にハマるのは例外処理との組み合わせです。 guard の body 部分（try ～ catch の try の内側）は末尾位置ではないからです。これは、例外処理の構文では body から抜けたあとに、設定した例外ハンドラを戻す、という処理が入るからです。このあたりは SRFI-34 の with-excepiton-handler の実装を見てみるとよくわかるでしょう（dynamic-wind の thunk の末尾は末尾文脈ではありません）。