関数型プログラミング事始め (25) 再帰プログラミング(1)

関数型プログラミングがはじめての方へ贈る入門の書
次節：再帰プログラミング(2)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)

関数型プログラミングでは副作用が生じる繰り返し文を基本にするのではなく、副作用のない再帰プログラミングを基本とします。この再帰プログラミングは計算可能性としては万能で、どんなプログラムも作成可能です。再帰プログラミングに慣れれば、自然にプログラムを作ることができます。きっと、たぶん。

3章. 関数型プログラミング手習い

ここでは関数型プログラミングの基本を紹介していきます。１章で関数プログラミングの定義やその課題を紹介しましたが、この関数型プログラミングの実際を２章のISLispを使って紹介していきます。

3.1 再帰プログラミング

関数型プログラミングでは副作用のないプログラミングが基本ですが、再帰プログラミングは副作用のないプログラミングをするときの武器となります。

ここではOK! ISLispを使って関数型プログラミングの手習いをやっていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。

> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>

(1) 繰り返し文は副作用あり

再帰プログラミングの前に、繰り返し文を使うプログラミングを見ていきます。まずISLispで繰り返し文を使った階乗計算の関数 ifact を作ってみます。

ISLisp>(defun ifact (n)
(for ((x 1 (+ x 1)) (ret 1)) ((> x n) ret) (setf ret (* ret x))))
IFACT

(a) 繰り返し文の実行

上記の(x 1 (+ x 1))では制御変数 x を初期値1に設定して、繰り返しのステップ処理でxの値を1ずつ増加します。(ret 1)では返値を蓄える変数 ret の初期値を1に設定しています。

((> x n) ret)では繰り返し終了判断として、xの値が引数nの値より大きくなれば、forの値として、retの値を返します。

繰り返し本体の(setf ret (* ret x))ではretに(* ret n)の値を格納しています。

このifactでは、たとえば(ifact 2)を実行すると、最初はn=2, x=1, ret=1となり、終了判断では(> 1 2)となり、この結果は偽なので、繰り返し本体を実行し、その結果はretに(* 1 1)の結果の1を格納します。

次のステップではn=2,x=2,ret=1となり、繰り返し終了判断は(> 2 2)の偽になり、繰り返し本体ではretに(* 1 2)の結果の2を返します。

その次のステップではn=2,x=3,ret=2となり、繰り返し終了判断は(> 3 2)の真になり、繰り返しは終了し、結果として現状のretの値である2を返します。

(b) 繰り返し文の副作用

今回のifactの例では制御変数xと結果を返すための蓄積関数retを使っています。このxとretはfor文内のローカル変数として宣言されていますので、for文の外には影響を与えていません。しかしfor文の中では副作用が生じています。

今回の例では、xは明らかに制御変数として扱われていますので、繰り返し文の本体で値を強制的に変えるなどの副作用は行わず、ステップ処理のときのみ値を変更している副作用しか生じていません。これは誰が見ても自然な行為なので、たとえ副作用が生じても、暗黙的にこれを考慮してプログラミングすることになり、副作用によるバグはたぶん起こらないでしょう。

結果を返すための蓄積関数であるretは繰り返し本体で値を変える副作用を生じさせていますが、変数名も含めて、結果を蓄積するための変数であることが明らかにわかるので、この副作用によるバグはたぶん起こらないでしょう。たぶん。

このように今回の例では副作用が生じていますが、副作用に関する暗黙の了解がどんなプログラマにもありますので、それほど問題はありません。しかし、鬼畜なプログラミングとして、制御変数を繰り返し本体で変更したり、蓄積変数の値を外部変数に代入したりするとバグが生じるかもしれません。
注意してください。

(2) 再帰プログラミングは副作用なし

それでは階乗計算を再帰プログラミングしてみます。

ISLisp>(defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1)))))
FACT

(a) 再帰プログラムの実行

(if (<= n 1) 1 (* n (fact (- n 1))))では引数nが1以下であれば真となり 1 を返し、そうでなければ(* n (fact (- n 1)))を実行します。

このfactでは、たとえば(fact 2)を実行すると、最初は(<= 2 1)で偽となり、(* 2 (fact (- 2 1)))を実行します。この結果、(* 2 (fact 1))となります。

次の再帰の(fact 1)では、(<= 1 1)で真となり、1を返します。この結果を受けて、(* 2 (fact 1))は(* 2 1)となり、2を返します。

(b) 再帰プログラムの副作用

今回の再帰プログラムでは変数は引数のみしか使っていません。このため、変数による副作用は生じていません。

また引数の実装では値渡しする引数は副作用を生じません。そして関数型プログラミングでは基本的に値渡しをするので、引数では副作用は生じません。たぶん。

(c) 引数の実装

引数の実装ではスタックを使う実装が多くなります。実際にISLispでも引数はスタックで実装しています。

関数型プログラミングで値渡しの実装としては、即値型のデータではスタックにそのまま格納し、即値型でない構成型のデータ（例. 配列や文字列など）では暗黙的に（自動的に）コピーしたものをスタックに格納するという実装もあります。

ISLispではコピーしていませんので構成型の引数を使って副作用を生じさえないためには、どこかのタイミングで手動でコピーする必要があります。

(d) 再帰プログラミングの評価

繰り返しプログラムの(defun ifact (n) (for ((x 1 (+ x 1)) (ret 1)) ((> x n) ret) (setf ret (* ret x))))と、再帰プログラムの(defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1)))))と比較すると、一目瞭然ですが、再帰プログラムの方がシンプルでわかりやすいプログラムになっています。

この理由は再帰プログラムが「関数呼び出し」の暗黙的な高機能を使っていて、一方、繰り返しプログラムは関数呼び出しの機能を手動で作成しているからです。

つまり、再帰プログラムの方がシンプルですが、実行のときは関数呼び出しという高機能な仕掛けを使っているため、実行時間は却って遅くなる場合もあります。というか遅くなります。ここは注意してください。

ということでここでの結論「再帰はシンプルだが遅い」ではなく「再帰は遅いけどシンプル」です。

(予告) (3) 再帰プログラミングの仕方

次回は再帰プログラミングの仕方を紹介することになります。お楽しみに！