Rubyで関数プログラミングの頁に戻る

ループコマンドの排除(Part 2)

　　関数型言語というと、まず思い出されるのが、LISPでしょう。FORTRANの次に古いのに、未だに古臭い言語とは思われていないというある意味驚異的な言語です。しかし、LISPは実際には関数プログラミング言語としての使われ方をされていないことも多いらしく、LISPだから関数プログラミングだと思うと、間違う場合もあろうかとおもいます。それで、その使われ方をされていないとされる理由の１つには、ループを使用できるということがあるのではないかと思います（一番の理由は違うと思いますが）。
　　関数プログラミングでは、ループを使用しません。これが関数プログラミングにとって本質的なことかどうかは異論があるかもしれませんが、多分本質的なことではないかと思っています。それは、ループは、順次的なコマンドの並びを前提にした制御コマンドだと思うからです。
　　これだけでは何の事かわからないと思うので、例を示しましょう。
　　まず、正の整数a、bの乗算を行う関数を考えます。乗算自体は*で行えるのですが、ここでは加減算しかできないものと仮定して話をします。すると、通常は以下のように書くことになると思います。

    
def iter_mul(a,b)
  result=a
  while b > 1          # (1)
    result += a        # (2)
    b -= 1             # (3)
  end
  result
end
　　これ自体は至って簡単なのですが、これはwhileというループコマンドを使用しています。従って、これを排除します。すると、以下のようになると思います。


def rec_mul(a,b)
  if b == 1 then a                     # (1)
  elsif b > 1 then a + rec_mul(a,b-1)  # (2)
  end
end
　　つまりは、再帰的に表現することになります。
　　通常アルゴリズム等の本には、再帰は、ソースコードの上では簡潔に見やすく表現できるが、効率が良くないので、非再帰的なものに置換えるべきだとして、むしろ上のiter_mulの方を奨励することが多いです。しかし、関数プログラミングでは、ループコマンドを使うべきではないので、rec_mulの方を推奨します。
　　まず言っておくべきなのは、再帰であれ何であれ、関数呼出は通常スタックフレームの積み上げがあり、非効率です。そうでないことも多く存在しますが、基本的にはループ(又はgoto)よりも効率良く実装できることはありません。しかし、それにもかかわらず再帰的な表現を使うべきであることには理由があります。
　　それは、iter_mulを見てもらえれば分かりますが、アルゴリズムの中間結果が変数に記憶され、そのことを通じて関数全体が繋がりあるものとして機能するからです。つまり、resultや制御変数bの絶えざる破壊的更新を通じて、その時々の値に依存しつつ、while、+演算子、-演算子等の言語構成物が一個の関数を形成することになっています。ここで、while ... endではなく、begin ... end while b > 1とした場合（つまり、(1)と(3)の順番を変えた場合）はどうでしょう。意図しない結果が出ると思います。whileは、そういうようにiter_mulの(1)、(2)、(3)が意図した順番で実行されなければならないと言うことを前提にした言語構成の中で機能しているわけです。それは勿論、破壊的に更新される変数の時々の状態を媒介として、プログラムを実現しているからです。
　　ところが、rec_mulでは、resultはありませんし、bが定数でも何ら問題ありません。つまり、それらの変数の破壊的更新を行わずに、アルゴリズムを実現しているのです。換言すると、命令型的意味における変数が存在しないといっていいと思います。更に、whileのように、順次的に並んだコマンドをまとめてもいません。何をしているのかといえば、以下の式をそのままコード上に写して来ただけです。つまり、関数プログラミングでは、プログラムそれ自体が一種の仕様であり、宣言的なのです（どのように(How)計算されるかではなく、何が(What)計算されるかを記述すれば良いということ）。

a * b = a              if b = 1
a * b = a + a * (b-1)  if b > 1
　　従って、例えば、rec_mulの(1)と(2)を交換しても、何ら問題ありません（勿論ifとelsifは変えなければなりませんが、多くの関数型言語では、これらの役割を果たすものは全て同じ記号です）。或は、a + rec_mul(a,b-1)をrec_mul(a,b-1) + aとしても同じです。これに対して、iter_mulでは、この式を一つ一つの場合において展開し、そうすると、同じこと(つまり、加算)を繰り返していることが分かるので、whileでまとめているのです。具体的には以下のものをコード化していると言えますが、iter_mulとは似ておらず、iter_mulは、計算機に合わせてかなり変形されていることが分かると思います（つまり、仕様－コードの間に溝がある）。

a * b (result) = a1 + a2 + ... + ab
　　今回示した例は至って簡単なものなので、効率がいいほうが良いのでは？と素朴に思うかもしれませんが、しかし、もっと大きなアルゴリズムの構築の際には、この展開という作業や変数の状態を意識しながら書かなければならないことが、如何にアルゴリズムそれ自体とは無関係のものであり、負担のかかる作業であるかを理解すると思います。最後あたりの頁では、その例を何かしらの形で示してみようと予定しています。


　　注意１　： 破壊的更新(destructive update)というのは、変数値の状態を破壊して、別の状態にすることです。これを行う最も典型的な操作は、代入です。更に詳しく知りたい方は、基礎概念の項を参照して下さい。

　　注意２　： 再帰関数の作り方は至って単純です。基本的に再帰関数は、２つ以上の性質の異なる代替部からなります。そうでないと、無限再帰になってしまいます。それで、その２つの部分というのが、①基本条件、②再帰ステップ、です。基本条件では、分岐条件を満たした場合（或は満たさなかった場合）の非再帰的な値を返すようにします。そして、再帰ステップでは、そのまま再帰関数（及び必要な演算）を記述します。また、再帰ステップは、必ず基本条件に到達しなければなりません。そうでないと、これもまた無限再帰になります。上のrec_mulでは、基本条件は(1)で、再帰ステップは(2)です。それで、(2)は呼出毎に、b == 0の条件に近づくように作られています。


　　次の頁では、再帰にもパターンが数種類あることを示します。関数プログラミングにとっては、再帰は重要な方法ですので、その種類を色々知っておくことは大切だと思います。

Previous pageNext page