目次


再帰的プログラミングをマスターする

再帰を取り込むことで、コードが保守しやすくなり、一貫性のある実証可能な正しいコードになるのはなぜなのかを学ぶ

Comments

コンピューター・サイエンスを学び始める学生にとって、再帰的プログラミングの概念が理解しがたいことは珍しくありません。再帰の考え方が難しいのはなぜかというと、再帰は、ほぼ、循環論法のようなものだからです。また、再帰的プログラミングは直感的なプロセスでもありません。

コンピューター・プログラミングの入門者のために再帰をわかりやすく定義すると、再帰とは、関数が直接または間接的に自身を呼び出すことです。

典型的な再帰の例

再帰的プログラミングの典型的な例には、階乗の計算が伴います。数値の階乗を計算するには、数値がその下にあるすべての数値と 1 を乗算します。例えば、factorial(5)5*4*3*2*1 と同等で、factorial(3)3*2*1 と同等です。

階乗の興味深い特性として、数値の階乗は、開始値をそのすぐ下にある数値の階乗で乗算した値と等しくなります。例えば、factorial(5)5 * factorial(4) と同等です。階乗関数は、次のような単純な形で作成することもできます。

リスト 1. 初めて階乗関数を作成する試み
int factorial(int n)
{
   return n * factorial(n - 1);
}

ただし、上記の関数には停止ポイントがないため、永遠に実行されるという問題があります。この関数は factorial を絶えず呼び出し続け、ゼロに到達しても関数を停止するきっかけがないことから、関数はゼロに対しても、負の数値に対しても factorial を呼び出し続けることになります。したがって、この関数に必要なのは、停止するタイミングを決定する条件です。

1 未満の数値の階乗を計算しても意味はないため、数値 1 で関数を停止して、1 の階乗 (1) を返します。したがって、実際の階乗関数は次のようになります。

リスト 2. 実際の階乗関数
int factorial(int n)
{
   if(n == 1)
   {
      return 1;
   }
   else
   {
      return n * factorial(n - 1);
   }
}

ご覧のように、初期値がゼロより大きい限り、この関数は終了します。この停止点は「ベース・ケース」と呼ばれます。ベース・ケースは再帰的プログラムの最終ポイントであり、ここで行われる処理は、回答を直接返せるだけの単純なものです。すべての再帰的プログラムでは、例外なく、少なくとも 1 つのベース・ケースが必要となり、最終的には 1 つのベース・ケースに確実に到達しなければなりません。そうでないと、プログラムが永遠に実行されるか、メモリーあるいはスタック空間がなくなるまで実行されることになります。

再帰的プログラムの基本ステップ

あらゆる再帰的プログラムが共通して従う一連の基本ステップは以下のとおりです。

  1. アルゴリズムを初期化します。再帰的プログラムには通常、処理を開始するためのシード値が必要になります。この要件を満たすには、2 つの方法があります。1 つは、関数に渡すパラメーターをシード値として渡すという方法です。もう 1 つの方法としては、再帰的ではないゲートウェイ関数を追加して、その関数で再帰的計算のシード値を設定します。
  2. 現在処理対象としている値がベース・ケースと一致するかどうかをチェックします。一致する場合は、その値を処理して結果を返します。
  3. より小さい、またはより単純な 1 つ以上の部分問題に関する回答を再定義します。
  4. 部分問題に対してアルゴリズムを実行します。
  5. それらの結果を結合して 1 つの回答にします。
  6. 結果を返します。

帰納的定義を使用する

再帰的プログラムを作成する際に、より単純な部分問題を見つけるのが難しい場合があります。けれども「帰納的に定義されたデータ・セット」を扱うと、部分問題を見つけるのがはるかに簡単になります。帰納的に定義されたデータ・セットとは、データ自身に関して定義されたデータ構造のことを指します。これは「帰納的定義」と呼ばれます。

例えば、リンク・リストはそれ自身に関して定義されます。リンク・リストを構成するノード構造には、2 つのメンバーが含まれます。1 つはノード構造が保持するデータ、もう 1 つは別のノード構造へのポインターです (または NULL へのポインター。この場合は、リストが終了されます)。ノード構造には自身に含まれるノード構造へのポインターが含まれることから、帰納的に定義されると言われます。

帰納的データを使用すると、再帰的手順をごく簡単に作成できます。再帰的プログラムと同じように、リンク・リストの定義にもベース・ケースが含まれることに注意してください。この場合、ベース・ケースは NULL ポインターです。NULL ポインターによってリストが終了するので、リンク・リストに対する再帰関数の多くでは、NULL ポインター条件をベース・ケースとして使用することもできます。

リンク・リストの例

リンク・リストに対する再帰関数の例をいくつか見ていきましょう。例えば、数値のリストがあり、このリストに含まれる数値を集計するとします。この場合、再帰的シーケンスの各ステップは、次のように集計関数に適用されます。

  1. アルゴリズムを初期化します。このアルゴリズムのシード値は、最初に処理するノードです。このノードがパラメーターとして関数に渡されます。
  2. ベース・ケースをチェックします。プログラムでは現在のノードが NULL リストであるかどうかをチェックして判別する必要があります。NULL リストである場合は、ゼロを返します。空のリストでは、すべてのメンバーを合計した値はゼロになるからです。
  3. より小さい、またはより単純な部分問題に関する回答を再定義します。この例では、リストの残りの部分を合計したうえで、現在のノードの内容を加算した値として回答を定義できます。リストの残りの部分を合計した値を算出するには、次に続くノードを引数としてこの関数を再度呼び出します。
  4. 結果を結合します。再帰呼び出しが完了したら、現在のノードの値を再帰呼び出しの結果に加算します。

以下に、関数の疑似コードと実際のコードを記載します。

リスト 3. sum_list プログラムの疑似コード
 function sum_list(list l)
    is l null?
       yes - the sum of an empty list is 0 - return that
    data = head of list l
    rest_of_list = rest of list l
    the sum of the list is:
       data + sum_list(rest_of_list)

このプログラムの疑似コードは、Scheme でのプログラム実装とほぼ同じです。

リスト 4. sum_list プログラムの Scheme コード
 (define sum-list (lambda (l)
    (if (null? l)
       0
       (let (
             (data (car l))
             (rest-of-list (cdr l)))
          (+ data (sum-list rest-of-list))))))

この簡単な例では、C バージョンも同じく単純なものになります。

リスト 5. sum_list プログラムの C コード
int sum_list(struct list_node *l)
{
   if(l == NULL)
      return 0;
    return l.data + sum_list(l.next);
}

皆さんは、これよりも処理速度の速いプログラム、あるいは再帰を使わない、より効率的なプログラムを作成する方法はあると考えているかもしれません。再帰の速度とスペースの問題については後で取り組むとして、今のところは、帰納的データ・セットの再帰の話題を続けましょう。

例えば、文字列のリストがあり、そのリストに特定の文字列が含まれているかどうかを調べるとします。この問題をより単純な問題に分解する方法も、同じく個々のノードを調べることです。

つまり部分問題は、「検索文字列がこのノードに含まれている文字列と同じであるか?」ということになります。文字列が一致する場合、それが解になります。一致しない場合は、解に一歩近づいたということです。ベース・ケースは何になるかというと、次の 2 つがあります。

  • 現在のノードに該当する文字列がある場合、それがベース・ケースです (「true」を返します)。
  • リストが空の場合、それもベース・ケースです (「false」を返します)。

この問題が必ず最初のベース・ケースに到達するとは限りません。それは、ノードに含まれる文字列の中に検索文字列が常にあるとは限らないためです。ただし、問題が最初のベース・ケースに到達しなくても、リストを最後まで処理すれば 2 番目のベース・ケースに到達することは確実です。

リスト 6. 所定のリストに特定の文字列が含まれているかどうかを判別する Scheme コード
(define is-in-list
    (lambda   (the-list the-string)
       ;;Check for base case of "list empty"
       (if (null? the-list)
          #f
          ;;Check for base case of "found item"
          (if (equal? the-string (car the-list))
             #t
             ;;Run the algorithm on a smaller problem
             (is-in-list (cdr the-list) the-string)))))

この再帰関数は問題なく機能しますが、1 つの大きな欠点があります。それは、再帰を繰り返すたびに、同じ値を the-string として渡すことです。このパラメーターを追加で渡すことで、関数呼び出しのオーバーヘッドが増える可能性があります。

一方、関数の先頭にクロージャーを設定すれば、関数呼び出しのたびに文字列を渡す必要がなくなります。

リスト 7. クロージャーを使用して文字列を検索する Scheme プログラム
 (define is-in-list2
    (lambda (the-list the-string)
       (letrec
         (
              (recurse (lambda (internal-list)
                   (if (null? internal-list)
                      #f
                      (if (equal? the-string (car internal-list))
                         #t
                         (recurse (cdr internal-list)))))))
          (recurse the-list))))

プログラムのこのバージョンは、少々理解しにくくなります。このバージョンで定義している recurse という名前のクロージャーは、2 つのパラメーターではなく 1 つのパメーターだけを使用して呼び出すことができます (クロージャーについて詳しくは、この記事の右側で紹介しているリソースを参照してください)。the-stringrecurse に渡す必要がない理由は、このパラメーターはすでに親環境内にあり、呼び出しごとに値が変わることはないためです。recurseis-in-list2 関数内で定義されているため、このパラメーターには現在定義されているすべての変数が可視になります。したがって、これらの変数を再び渡す必要はありません。これにより、繰り返し処理のたびに渡す変数が 1 つずつ減っていきます。

この単純な例ではそれほど大きな違いをもたらしませんが、より複雑な関数になってくると、パラメーターを渡すのではなくクロージャーを使用することで、パラメーターを渡す際に伴う型指定、エラー、オーバーヘッドを大幅に減らすことができます。

この例で使用している再帰クロージャーは、少々面倒な方法で作成されています。再帰的プログラミングでは、この例と同じように letrec を使用して再帰クロージャーを作成してから初期のシード値を使ってクロージャーを呼び出すというパターンを何度も繰り返し目にします。

再帰パターンのプログラミングを容易にするために、Scheme では「名前付き let」というショートカットを使用できるようになっています。この構造体は let とかなり似ていますが、let とは異なる点として、ブロック全体に名前が指定されるため、再帰クロージャーとして呼び出すことができます。名前付き let を使用して作成する関数のパラメーターは、通常の let 内で使用する変数と同じように定義されます。つまり、通常の let 内で初期の変数の値が設定される場合と同じ方法で、初期のシード値が設定されます。そこからは、以降の再帰呼び出しで、パラメーターが同じ値として使用されます。

名前付き let についての説明はかなり難解なので、次のコードをリスト 7 のコードと比較して、その違いを確認してください。

リスト 8. 名前付き let の例
(define is-in-list2
    (lambda (the-list the-string)
       ;;Named Let
       ;;This let block defines a function called "recurse" that is the
      ;;body of this let.  The function's parameters are the same as
       ;;the variables listed in the let.
       (let recurse
          ;;internal-list is the first and only parameter.  The
          ;;first time through the block it will be primed with
          ;;"the-list" and subsequent calls to "recurse" will
          ;;give it whatever value is passed to "recurse"
          ( (internal-list the-list) )

          ;;Body of function/named let block
          (if (null? internal-list)
             #f
             (if (equal? the-string (car internal-list))
                #t
                ;;Call recursive function with the
                ;;rest of the list
                (recurse (cdr internal-list)))))))

名前付き let を使用すると、再帰関数を作成する際の型指定とエラーが大幅に減ります。名前付き let の概念をまだ理解できないという場合は、上記の 2 つのプログラムを行ごとに比較することをお勧めします (また、この記事の右側で紹介しているリソースのうち、該当するドキュメントも参照してください)。

リストに基づく次の再帰関数の例は、さらに複雑なものです。この再帰関数は、リストが昇順になっているかどうかをチェックします。リストが昇順になっている場合は #t を返し、そうでなければ #f を返します。このプログラムは現在の値を調べるだけでなく、最後に処理した値を記録しなければならないという点で、これまでの例とは少々異なります。

リスト上の最初の項目は、他の項目とは異なる方法で処理する必要があります。最初の項目の前には項目がないためです。残りの各項目については、その項目の前に調べたデータ項目を関数呼び出しに含めて関数に渡す必要があります。この関数の内容は以下のとおりです。

リスト 9. リストが昇順であるかどうかを判別する Scheme プログラム
(define is-ascending
    (lambda (the-list)
       ;;First, Initialize the algorithm.  To do this we
       ;;need to get the first value, if it exists, and
       ;;use it as a seed to the recursive function
       (if (null? the-list)
          #t
          (let is-ascending-recurse
             (
                 (previous-item (car the-list))
                (remaining-items (cdr the-list))
             )
             ;;Base case #1 - end of list
             (if (null? remaining-items)
                #t
                (if (< previous-item (car remaining-items))
                   ;;Recursive case, check the rest of the list
                   (is-ascending-recurse (car remaining-items) (cdr remaining-items))
                   ;;Base case #2 - not in ascending order
                   #f))))))

このプログラムはまず始めに、境界条件として、リストが空であるかどうかをチェックします。空のリストは昇順とみなされます。リストが空でなければ、リスト上の最初の項目とリストの残りの部分を再帰関数に渡します。

プログラムは次に、ベース・ケースをチェックします。リストの終わりに到達するのは、それまでのすべての処理が順番に行われてリストが空になった場合 (つまり、リストが昇順とみなされた場合) のみです。リストが空でなければ、現在の項目がチェックされます。

現在の項目が昇順になっている場合、リストの残りの部分が昇順であるかどうかという、未解決の部分問題だけが残されます。したがって、リストの残りの部分を再帰的に処理して判別を試みます。

注目する点として、この関数では、プログラムを前へ送ることによって、関数呼び出しから次の関数呼び出しまで状態を維持しています。これまでの例では毎回リストの残りの部分だけを渡していましたが、この関数では計算の状態に関する情報が必要です。現在の計算結果は、それまでの部分的結果に依存するため、再帰呼び出しのたびに、その部分的結果を渡します。これが、複雑な再帰プロシージャーで使用される共通パターンです。

実証可能な正しいプログラムを作成する

あらゆるプログラマーにとってバグは日常生活の一部です。ごく小規模なループや、ほんの小さな関数呼び出しでさえも、バグが含まれる可能性があるからです。ほとんどのプログラマーはコードを調べてバグの有無を確認することや、コードをテストしてバグを検出することはできても、プログラムが期待どおりに実行されることを実証する方法については把握していません。この点を踏まえ、ここからは一般的なバグの原因のいくつかを確認し、正しいことを実証できるプログラムを作成する方法を説明します。

バグの原因: 状態変化

バグの主な原因の 1 つとして、変数の状態が変化するときにバグが発生することがあります。プログラマーは変数の状態がいつ、どのように変化するかに抜け目な目を光らせているものだと思うかもしれません。単純なループではそうかもしれませんが、複雑なループになると、そうとは限りません。通常、ループ内では所定の変数の状態が変化する可能性のある過程がいくつかあります。

例えば、if ステートメントが複雑化してくると、複数の分岐ではある特定の変数が変化し、他の分岐では別の変数が変化する場合があります。その上、順序は一般に重要であっても、コーディングされている順序があらゆるケースで正しい順序であることを絶対確実にすることは困難です。この順序付けの問題により、あるケースのバグを修正することで、別のケースで別のバグが発生することも珍しくはありません。

このようなエラーを防ぐためには、開発者に次のスキルが必要になってきます。

  • 各変数がその現在の値をどのように受け取ったかを目で確認して把握する。
  • 2 つの役目を掛け持ちする変数がないことを確実にする(2 つの関連する、ただしわずかに異なる値を格納するために同じ変数を使用するプログラマーは少なくありません)。
  • ループが再開されるときに、すべての変数がそれぞれに想定される状態になっていることを確実にする (使用されることもテストされることもめったにない特別ケースで使用されているループ変数に新しい値を設定できないことは、よくあるプログラミング・エラーです)。

以上の目標を達成するためにプログラミングの際に設定しなければならないルールはたった 1 つしかありません。それは、「変数には一度だけ値を代入し、決して変更しないこと」です。

何ですって?(皆さんの懐疑心を代弁しました!) 命令型プログラミング、プロシージャー型プログラミング、オブジェクト指向プログラミングを通じて経験を積んできた多くのプログラマーにとって、このルールは冒とく的でしょう。これらのプログラミングでは、変数の代入と変更がプログラミング手法の中核となっていますが、命令型プログラマーがプログラミングで犯す誤りの根本的な原因の 1 つは、いつも状態変化にあります。

命令型プログラマーが変数を変更せずにプログラミングするにはどうすればよいでしょうか?通常は変数が変更される次のケースと、変数を変更せずにそれぞれのケースを切り抜けられるかどうか見ていきましょう。

  • 変数の再利用
  • 変数の条件付き変更
  • ループ変数

まずは最初のケース、変数の再利用です。通常は、まったく同じではないものの、似たような目的のために変数が再利用されます。例えば、ループの中で、ループ前半での現在の位置のインデックスと、ループ後半の直前または直後での位置のインデックスが必要だとします。この場合、多くのプログラマーが採る方法は、両方のインデックスに同じ変数を使用し、ループの中で単純に変数の値をインクリメントするというものです。この方法では、プログラムが変更されたときに、プログラマーが 2 つのインデックスを混同してしまうでしょう。この問題を防ぐのに最良のソリューションは、2 つの別個の変数を作成し、同じ変数に値を書き込んでいるかのように、一方の変数の値からもう一方の変数の値を派生させることです。

2 番目のケース、変数の条件付き変更は、変数の再利用問題のサブセットですが、既存の値を維持する必要がある場合も、新しい値が必要となる場合もあるという点が異なります。この場合も、最善の方法は新しい変数を作成することです。ほとんどの言語では、3 項演算子 ? : を使用して新しい変数の値を設定できます。たとえば、新しい変数に新しい値を代入する場合、その値が some_value 未満である限り新しい値を代入するには、int new_variable = old_variable > some_value ? old variable : new_value; というコードを作成できます。

(ループ変数については、この記事で追って説明します)。

あらゆる状態変化を取り除くと、最初に変数を定義する時点で、関数が存続する限り、変数の定義が維持されることがわかります。したがって、処理の順序付けがはるかに簡単になります。これは、既存のコードを変更する場合に特に言えることです。変数の順序がどのように変更されたのか、あるいは各分岐での変数の状態についての前提が何であったのかを懸念する必要がなくなります。

変数の状態が変わることがなければ、変数を宣言するときに変数を定義する場所で、その値を導出する方法が完全に定義されます。コード全体を調べて誤った状態変化や順序の違う状態変化を見つける必要は一切なくなります!

ループ変数について

次の問題は、変数代入を使わずにループを処理する方法です。その答えは、再帰関数にあります。表 1 に記載するループと再帰関数の特性を見比べてください。

表 1. ループと再帰関数の比較
特性ループ再帰関数
繰り返し同じコード・ブロックを繰り返し処理して結果を取得します。繰り返し処理の目的を示すために、コード・ブロックを終わらせるか、continue コマンドを発行します。同じコード・ブロックを繰り返し処理して結果を取得します。繰り返し処理の目的を示すために、自身を呼び出します。
終了条件ループが終了することを保証するためには、ループに 1 つ以上の終了条件を設定し、何からの時点でループがそれらの条件に適合することを保証する必要があります。再帰関数が終了することを保証するためには、再帰処理を終了させるベース・ケースが必要です。
状態現在の状態はループの進行に伴って更新されます。現在の状態はパラメーターとして渡されます。

以上のように、再帰関数とループにはかなり共通するところがあります。実際、ループと再帰関数は互いに置き換えられると見なせます。異なる点は、再帰関数では変数を変更する必要がめったにないことです。変数を変更するのではなく、新しい値を次の関数呼び出しに渡すだけで済みます。このことから、繰り返し処理によるステートフルな動作を維持しながら、更新可能な変数を使わないことによるすべてのメリットを確保することができます。

一般的なループを再帰関数に変換する

レポートを出力する一般的なループを例に、ループを再帰関数に変換する方法を見ていきましょう。

  • このループは、改ページごとにページの番号と見出しを出力します。
  • レポートの行は何らかの数値の基準によってグループ化されているという前提で、これらのグループについて、何らかの合計をトラッキングしているとします。
  • 各グループの最後に、そのグループに関する合計を出力します。

以下のコードはデモ用なので、この処理に必要な従属関数は存在し、期待どおりに機能するという前提で、従属関数はすべて省略しています。このレポート・プリンターとしてのコードは、次のとおりです。

リスト 10. 通常のループを使用したレポート出力プログラム
void print_report(struct report_line *report_lines, int num_lines)
{
   int num_lines_this_page = 0;
   int page_number = 1;
    int current_line; /* iterates through the lines */
    int current_group = 0; /* tells which grouping we are in */
    int previous_group = 0; /* tells which grouping was here on the last loop */
    int group_total = 0; /* saves totals for printout at the end of the grouping */

     print_headings(page_number);

     for(current_line = 0; current_line < num_lines; current_line++)
    {
       num_lines_this_page++;
        if(num_lines_this_page == LINES_PER_PAGE)
       {
          page_number++;
          page_break();
          print_headings(page_number);
       }

       current_group = get_group(report_lines[current_line]);
       if(current_group != previous_group)
       {
         print_totals_for_group(group_total);
          group_total = 0;
       }

        print_line(report_lines[current_line]);

       group_total += get_line_amount(report_lines[current_line]);
    }
}

このプログラムには意図的に、いくつかのバグを残してあります。バグを見抜けるか試してください。

ここでは変数の状態をひっきりなしに変更するため、特定の時点でその状態が正しいものであるかどうか判別するのは困難です。再帰的処理を使って同じプログラムを作成すると、次のようになります。

リスト 11. 再帰的処理を使用したレポート出力プログラム
void print_report(struct report_line *report_lines, int num_lines)
{
    int num_lines_this_page = 0;
    int page_number = 1;
    int current_line; /* iterates through the lines */
    int current_group = 0; /* tells which grouping we are in */
    int previous_group = 0; /* tells which grouping was here on the last loop */
    int group_total = 0; /* saves totals for printout at the end of the grouping */

      /* initialize */
   print_headings(page_number);

     /* Seed the values */
    print_report_i(report_lines, 0, 1, 1, 0, 0, num_lines);
}

void print_report_i(struct report_line *report_lines, /* our structure */
    int current_line, /* current index into structure */
    int num_lines_this_page, /* number of lines we've filled this page */
    int page_number,
     int previous_group, /* used to know when to print totals */
    int group_total, /* current aggregated total */
    int num_lines) /* the total number of lines in the structure */
{
    if(current_line == num_lines)
    {
       return;
    }
    else
    {
       if(num_lines_this_page == LINES_PER_PAGE)
       {
          page_break();
          print_headings(page_number + 1);
          print_report_i(
             report_lines,
              current_line,
              1,
              page_number + 1,
              previous_group,
              group_total,
              num_lines);
       }
       else
       {
          int current_group = get_group(report_lines[current_line]);
          if(current_group != previous_group && previous_group != 0)
          {
             print_totals_for_group(group_total);
             print_report_i(
                report_lines,
                 current_line,
                 num_lines_this_page + 1,
                 page_number,
                 current_group,
                 0,
                 num_lines);
          }
          else
          {
             print_line(report_lines[current_line]);
             print_report_i(
                report_lines,
                 current_line + 1,
                 num_lines_this_page + 1,
                 page_number,
                 current_group,
                 group_total + get_line_amount(report_lines[current_line]),
                 num_lines);
          }
       }
    }
}

どの時点でも、プログラムで使用している数値が自己矛盾した状態になることは決してありません。状態が複数回変化する場合はほぼ常に、状態が変わる間にプログラムで自己矛盾する数値を持たない複数の行を設けることになります。そのうえで、プログラムがそのような状態変化のまっただ中にあるときに行を追加する場合、変数の状態に関する理解が実際の状態変化と一致していなければ、大きな問題につながります。そのような変更を何度か行ったとしたら、順序と状態の問題により、非常にわかりづらいバグが発生するはずです。このプログラムでは、すべての状態変化は、完全に自己矛盾のないデータを指定して再帰関数を再実行することによって行われています。

再帰的レポート出力プログラムに関する証明

変数の状態を一切変更しないため、プログラムの正しさを実証するのは極めて簡単なことです。リスト 11 のレポート出力プログラムの特性についての証明をいくつか見ていきましょう。

大学を卒業して以来、プログラムの実証を行ったことはないという読者のために言っておくと、プログラムの証明を行うということは、基本的にプログラムの何らかの特性を探して (通常は指定された P)、その特性が事実であると実証することです。それには、次の概念を使用します。

  • 「公理」。これは、前提とする真実を指します。
  • 「定理」。公理から推定されたプログラムに関する表明です。

目標とするのは、真実 P を実証できる形で公理と定理を結び付けることです。プログラムに複数の特性がある場合、通常はそのそれぞれを独立して実証します。このプログラムには複数の特性があるため、そのうちのいくつかを簡単に証明します。

ここで行う証明は公式的な証明ではないため、使用する公理を指定することも、証明を裏づける中間定理を実証することもしません。証明が必要とならないほど公理と定理が明らかであることを願っています。

証明では、プログラムの 3 つの再帰ポイントをそれぞれ R1、R2、R3 と呼びます。すべてのプログラムには、report_lines は有効なポインターであり、report_lines が表す行数は num_lines に正確に反映されるという暗黙的な前提があります。

この例では、次のことを実証したいと思います。

  • プログラムはある特定の行のグループで終了する。
  • LINES_PER_PAGE で指定された行数が出力された後に改ページが行われる。
  • すべてのレポート項目の行が確実に 1 回出力される

プログラムが終了することを証明する

この証明では、ある特定の行のグループでプログラムが終了することを検証します。この証明で使用する手法は、再帰的プログラムでの証明で一般的に使われている「帰納的証明」という手法です。

帰納的証明は 2 つの段階で行われます。まず。特性 P が所定のパラメーター・セットに当てはまることを実証する必要があります。次に、P が X の値に当てはまる場合、X + 1 (または X - 1、あるいは何らかの類の段階的処理) の値についても当てはまるという帰納を実証します。このようにして、最初の数値から順番に、すべての数値について特性 P を実証していきます。

このプログラムの場合はまず、print_report_i が現在の current_line == num_lines で終了することを実証します。続いて current_line > 0 であることを前提に、print_report_i が所定の current_line で終了する場合は、current_line - 1 でも終了することを明らかにします。

証明 1. 特定の行のセットを与えてプログラムが終了することを検証する
前提
ベース・ケースの証明
検査結果により、current_line == num_lines の直後にプログラムが終了することがわかります。
帰納ステップの証明
プログラムが繰り返し処理を行うたびに、current_line が 1 増えるか、同じ状態になります (R1 および R2)。current_groupprevious_groupcurrent_line から導出されるため、R2 が発生するのは、current_line の現在の値が current_line の前の値と異なる場合のみです。

R1 は、num_lines_this_page の値が変更された場合にのみ発生します。num_lines_this_page の値は、R2 と R3 によってのみ変更されます。

R2 は R3 のみに基づいて発生し、R1 は R2 と R3 のみに基づいて発生するため、current_line の値は増加するはずであり、それは単調な増加でしかないと結論できます。

したがって、current_line の何らかの値によって処理が終了するとしたら、current_line より前のすべての値によっても同じく処理が終了することになります。

これで、前提に基づいて print_report_i が終了することが実証されました。

LINES_PER_PAGE で指定された行数が出力された後に改ページが行われることを証明する

このプログラムは、改ページを行う場所をトラッキングするため、この改ページ・メカニズムが帰納することを実証するだけの価値はあります。前述のとおり、証明では公理と定理に基づいて論証します。ここでは証明するために 2 つの定理を立てます。定理の条件が当てはまる場合、その定理に従って、プログラムに関する定理の結果が真実であることを確定します。

証明 2. LINES_PER_PAGE で指定された行数が出力された後に改ページが行われる
前提: 現在のページのページ見出しがすでに最初の行に出力されている
定理 1
num_lines_this_page が正しい開始値に設定されていて (条件 1)、行が出力されるごとに num_lines_per_page の値が 1 増えて (条件 2)、改ページの後に num_lines_per_page がリセットされる (条件 3) としたら、ページ上で出力された行数が num_lines_this_page の値に正確に反映される。
定理 2
出力された行数が num_lines_this_page の値に正確に反映され (条件 1)、num_lines_this_page == LINES_PER_PAGE となるたびに改行が行われる (条件 2) としたら、プログラムは LINES_PER_PAGE で指定された行数を出力した後に改ページを行うことが確実になる。
証明
定理 1 の条件 1 を前提とします。いずれにしても、検査結果で print_report_iprint_report から呼び出されたことを踏まえれば、この条件が明らかに当てはまることがわかります。

条件 2 は、num_lines_this_page の値の増加に応じて行を出力するプロシージャーのそれぞれを確認することによって判断できます。行は次のように出力されます。

検査結果では、行出力条件 1 と 2 が num_lines_this_page の値を 1 増やし、改ページと見出し出力を行った後、行出力条件 3 が num_lines_this_page を適切な値にリセットします (一般条件 3)。定理 1 の要件は満たされているため、プログラムは LINES_PER_PAGE で指定された行数を出力した後に改ページを行うことが実証されました。

すべてのレポート項目の行が確実に 1 回出力されることを証明する

プログラムが常にレポートのすべての行を出力し、1 行も省略しないことを検証する必要があります。それには帰納証明の手法に従って、print_report_icurrent_line == X に対して正確に 1 行を出力するとすれば、current_line == X + 1 に対しても正確に 1 行を出力するか、または終了するかのどちらかであることを明らかにできます。さらに、開始条件と終了条件の両方があることから、この両方が正しいことを実証する必要もあります。したがって、print_report_icurrent_line == 0 である場合に機能し、これが終了するのは when current_line == num_lines の場合のみであるというベース・ケースを実証する必要があります。

ただし、この例では簡略化して、最初の証明を根拠に直接証明するだけにします。最初の証明では、所定の数値で開始すると、適切なポイントで終了することを明らかにします。それには、アルゴリズムを調べて順次進行することを確認すれば、証明の半分は完了したことになります。

証明 3. すべてのレポート項目の行が確実に 1 回出力される
前提: 証明 1 を根拠とするため、この証明は、証明 1 の前提に基づきます。また、最初の呼び出しは , から行われることも前提とします。つまり、呼び出しは 0 から開始されます。
定理 1
current_line の値は print_line が呼び出された後にのみ増加し (条件 1)、print_linecurrent_line の値が増加した場合にのみ呼び出される (条件 2) としたら、current_line が 1 行で渡すすべての数値が出力される。
定理 2
定理 1 が真であり (条件 1)、current_line が 0 から num_lines – 1 までのすべての数値を渡し (条件 2)、current_line == num_lines になると終了する (条件 3) としたら、すべてのレポート項目の行が確実に 1 回出力される。証明
証明
定理 1 の条件 1 と 2 は、検査により真であることがわかります。R3 は、current_line の値が増加した場合に限り、print_line の呼び出し直後にのみ発生します。したがって、定理 1 は実証されるので、定理 2 の条件 1 も実証されたことになります。

条件 2 と 3 は、帰納証明によって実証できます。実際のところ、これは終了に関する最初の証明の焼き直しでしかありません。終了に関する証明を踏まえれば、最終的に条件 3 も実証できます。その証明と、current_line は 0 から開始するという前提に基づくと、条件 2 は真となります。したがって、レポートのすべての行が確実に 1 回出力されることが実証されたことになります。

証明と再帰的プログラミング

以上は、このプログラムについて行える証明の数例でしかありません。これよりもはるかに厳格な証明を行うこともできますが、私たちの多くは、面倒な計算やその表記に煩わされるよりも、プログラミングを選びます。

再帰的処理を使用すると、プログラムの検証がこの上なく単純化されます。命令型プログラムについてプログラムの証明を行うことはできないというわけではありませんが、命令型プログラムについて証明するには、状態変化が何度も発生するため手に負えません。状態を変更させるのではなく、再帰的に処理する再帰的プログラムでは、状態変化の発生回数が少なくなり、すべての再帰変数が一度に設定されるため、プログラムの変数の自己一貫性が維持されます。これによって論理的エラーが完全になくなるわけではありませんが、発生するエラーの種類の数は大幅に減ります。状態変更に対する再帰処理と繰り返し処理だけを使用するプログラミング手法は、一般に「関数型プログラミング」と呼ばれます。

末尾再帰関数

これまで、ループと再帰関数の関連性、ループを再帰関数に変換する方法、そして変数の状態を変化させない関数について説明してきました。変数の状態が変化しないプログラミングにすれば、元のプログラミングよりも保守しやすくなり、しかも正しいことを実証できます。

けれども、再帰関数を使用する場合に気になる問題の 1 つは、スタック・スペースの増加です。確かに、再帰関数の種類によっては、呼び出される回数と比例してスタック・スペースが増えていきます。ただし、どれだけ再帰のレベルが深くても、スタック・サイズが変わらない関数の種類が 1 つあります。

末尾再帰

ループを再帰関数に変換したとき、再帰関数が最後に行うのは再帰呼び出しになりました。print_report_i を評価すると、この呼び出しの後はこの関数内でこれ以上何も行われないことがわかります。

再帰関数は、ループのような動作を示します。ループはその終わりに達したとき、または continue を発行した後、そのコード・ブロック内では何の計算も行いません。それと同様に、print_report_irecurses が再帰ポイントに到達すると、計算するものは何も残っていません。

関数が最後に行う関数呼び出し (再帰呼び出しても、そうでなくても) は、「末尾呼び出し」と呼ばれます。末尾呼び出しを使用する再帰は、「末尾再帰」と呼ばれます。末尾呼び出しが実際に何を意味するのか理解するために、関数呼び出しの例をいくつか見ていきましょう。

リスト 12. 末尾呼び出しと末尾呼び出しではない呼び出し
int test1()
{
    int a = 3;
    test1(); /* recursive, but not a tail call.  We continue */
             /* processing in the function after it returns. */
    a = a + 4;
    return a;
}

int test2()
{
    int q = 4;
    q = q + 5;
    return q + test1(); /* test1() is not in tail position.
                         * There is still more work to be
                         * done after test1() returns (like
                         * adding q to the result
                         */
}

int test3()
{
    int b = 5;
     b = b + 2;
     return test1();  /* This is a tail-call.  The return value
                      * of test1() is used as the return value
                      * for this function.
                      */
}

int test4()
{
    test3(); /* not in tail position */
    test3(); /* not in tail position */
    return test3(); /* in tail position */
}

ご覧のように、呼び出しを実際の末尾呼び出しにするには、末尾で呼び出された関数の結果を返す前に、その結果に対して他の処理を行うことはできません。

関数内で行う計算は何も残っていないため、関数に実際に必要となるスタック・フレームもありません。唯一の問題は、多くのプログラミング言語とコンパイラーは未使用のスタック・フレームの処分方法を把握しないことです。未使用のスタック・フレームを削除する方法があれば、末尾再帰関数は一定のスタック・サイズ内で実行されることになります。

末尾呼び出し最適化

末尾呼び出しの後にスタック・フレームを削除するという考えは、「末尾呼び出し最適化」と呼ばれます。

最適化とはどういうことなのでしょう?その質問の答えは、別の複数の質問に対する答えによって出すことができます。

  • 末尾に位置する関数が呼び出された後、どのローカル変数が使用されますか?答え: 使用されるローカル変数はありません。
  • 値を返すために、どのような処理が行われますか?答え: 何の処理も行われません。
  • 関数に渡すパラメーターのうち、どのパラメーターが使用されますか?答え: どのパラメーターも使用されません。

末尾で呼び出された関数に制御が渡された時点で、スタックの中身はすべて無用になるようです。この時点でまだスペースを占拠している関数のスタック・フレームは、実際には無用であることから、末尾呼び出し最適化では、末尾に位置する関数呼び出しを行う際に元のリターン・アドレスを維持する一方で、現在のスタック・フレームを次のスタック・フレームで上書きします。

基本的に何を行っているかというと、スタックの手術です。アクティベーション・レコードは必要なくなるため、それを削除して、末尾で呼びだされた関数を呼び出し側関数にリダイレクトします。つまり、スタックを手作業で書き換えて、末尾で呼びだされた関数が親に直接戻るようにリターン・アドレスを偽造する必要があります。

下位レベルの詳細に深入りするのが実際に好きだというプログラマーのために、以下に、末尾呼び出しを最適化するアセンブリー言語のテンプレートを記載します。

リスト 13. 末尾呼び出しのアセンブリー言語のテンプレート
;;Unoptimized tail-call
my_function:
    ...
    ...
     ;PUSH ARGUMENTS FOR the_function HERE
     call the_function

     ;results are already in %eax so we can just return
    movl %ebp, %esp
    popl %ebp
    ret

;;Optimized tail-call optimized_function:
    ...
    ...
     ;save the old return address
    movl 4(%ebp), %eax

     ;save old %ebp
    movl (%ebp), %ecx

      ;Clear stack activation record (assuming no unknowns like
     ;variable-size argument lists)
    addl $(SIZE_OF_PARAMETERS + 8), %ebp ;(8 is old %ebp + return address))

     ;restore the stack to where it was before the function call
    movl %ebp, %esp

     ;Push arguments onto the stack here
     ;push return address
    pushl %eax

     ;set ebp to old ebp
    movl %ecx, %ebp

     ;Execute the function
     jmp the_function

このテンプレートを見るとわかるように、末尾呼び出しはいくつかの追加命令を取りますが、それでもかなりのメモリーを節約できます。こうした最適化を使用する際は、次の制約事項があります。

  • 関数が戻るときに、呼び出し側関数がスタック上に残っているパラメーター・リストに依存しないようにする必要があります。
  • 呼び出し側関数では、スタック・ポインターが現在どこを指しているのかに関心を持たないようにする必要があります (もちろん、呼び出し側関数がそのローカル関数を通過していると前提することはできます)。これはつまり、-fomit-frame-pointer を使用してコンパイルすることはできないということです。また、スタック上に保存するレジスターは、%esp ではなく %ebp を参照して保存しなければならないことも意味します。
  • 可変長引数リストは使用できません。

関数が末尾呼び出しで自身を呼び出すときの方法はさらに簡単になります。パラメーターの新しい値で古い値を上書きし、関数内でローカル変数がスタック上に保存される直後のポイントにジャンプすれば良いだけです。ジャンプ先は同じ関数なので、リターン・アドレスと古い %ebp はそのまま変わらず、スタックのサイズも変わりません。したがって、ジャンプの前に必要なのは、古いパラメーターを新しいパラメーターで置き換えることだけです。

命令を数個しか含まないコードについては、関数型プログラムの証明可能性と、命令型プログラムの速度とメモリーの特性をプログラムで利用できます。問題となるのは、現在のところ、末尾呼び出し最適化を実装するコンパイラーの数はごくわずかであることだけです。末尾呼び出し最適化を実装するには Scheme 実装が必要となります。このことは、他の多くの関数型言語についても同じです。ただし、関数型言語では命令型言語とは大幅に異なる方法でスタックを使用することがあるため (あるいは、スタックをまったく使用しないこともあります)、関数型言語での末尾呼び出し最適化方法はかなり異なってくる場合があります。

GCC の最近のバージョンでも、一定の限られた状況では、末尾再帰最適化が組み込まれます。例えば、前に説明した print_report_i は、GCC 3.4 上では -O2 を使用した末尾呼び出し最適化とともにコンパイルされているため、スタック・サイズが線形に増加することなく、一定のスタック・サイズで実行できます。

まとめ

再帰という素晴らしい技術を用いれば、パフォーマンスを犠牲にすることなく、その正しさを簡単に検証できるプログラムを作成することが可能になります。けれどもそれには、プログラマーが新しい観点からプログラミングに取り組む必要があります。通常、新しいプログラマーにとっては、命令型プログラミングのほうがより自然で直観的な出発点となるため、ほとんどのプログラミング入門では命令型の言語とメソッドに重点を置いています。ですが、プログラムが複雑化してくると、プログラマーが保守しやすく、しかも論理的に一貫性のある方法でコードを編成するには、再帰的プログラミングのほうが効果的な方法になります。


ダウンロード可能なリソース


関連トピック

  • How To Write Proofs: しばらくプログラムの証明を行っていないか、あるいはまったく行ったことがないプログラマーのために、証明の作成方法をわかりやすく説明しています。
  • Spec Patterns: 知らなかったかもしれませんが、証明にもパターンがあります。
  • 高階関数: 記事「高階関数」(developerWorks、2005年3月) で、クロージャーとその他の Scheme 関連の関数について取り上げています。
  • 魅力的な Python: Python での関数プログラミング: シリーズ「魅力的な Python: Python での関数プログラミング」(developerWorks、2001年3月) では、プログラマーが Python をプロシージャー型のオブジェクト指向言語だと見なしているとしても、Python には完全な関数型の手法でプログラミングを行うために必要なすべてのものが含まれていることを実証しています。
  • 書籍の閲覧: この記事で紹介した技術やその他の技術に関する書籍を閲覧してください。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=1064285
ArticleTitle=再帰的プログラミングをマスターする
publish-date=01172019