あどけない話

インターネットに関する技術的な話など

関数型プログラミングと代入

関数型プログラミングでは、よく「代入は使ってはならない」と言われます。関数型言語の一種である Emacs Lisp を生業とする僕は、この言葉に長年悩まされてきました。代入を使わないで実用的なプログラムを書くことは無理だからです。

もちろん、問題の内容が数学の関数に類似したものなら、代入も副作用もないプログラムを書くことは簡単です。階乗(factorial)のコードは、以下のように奇麗に実装できます。

(defun factorial(n)
  (if (= n 1)
      1
    (* n (factorial (1- n)))))

しかし、こう書けることと、実際にこう書くかということとは別問題です。

Scheme のように末尾最適化を実装していて、末尾再帰をループに変換してくれるなら、上記を末尾再帰に変換したコードを書くでしょう。

しかし、Emacs Lisp には末尾最適化がありませんから、スタックが溢れてしまいます。また、つまらないことですが、速度も若干遅いでしょう。そこで僕は、躊躇なくループで以下のように書きます。

(defun factorial(n)
  (let ((ret 1) (i 1))
    (while (<= i n)
      (setq ret (* ret i))
      (setq i (1+ i)))
    ret))

関数型プログラミング言語の信者であれば、「setq は悪だ」と主張するかもしれません。しかし、そもそも代入(setq)は、そんなに悪いものなんでしょうか?

goto 文

なぜ関数プログラミングは重要か」には、「関数型プログラミングでの代入」を「手続型プログラミングでの goto 文」に例えて説明していました。

関数プログラミングと構造化プログラミングの類似を描くことは有用である。 過去、構造化プログラミングの特徴や利点は多かれ少かれ以下のように要約さ れてきた。構造化プログラムはgoto文を含まない。構造化プログラム ではブロックが複数の入口や複数の出口をもたない。構造化プログラムは非構 造化プログラムより数学的な扱いが容易である。構造化プログラミングのこれ らの「利点」は、気持の上では、先に議論した、関数プログラミングの「利点」 に似ている。これらは、本質的には否定形の謂であり、「本質的なgoto」 などに関する実りのない主張を導いた。

後になって改めて考えると、構造化プログラムのこうした特徴は、もちろん有 用であるが、事の核心に至っていないことは明かである。構造化プログラムと 非構造化プログラムのあいだの最も重要は相違は構造化プログラムはモジュー ル化という方法で設計されるということである。モジュール化設計は大きな生 産性向上をもたらす。まず第一に小さなモジュールは素速くかつ早期にコード 化できる。第二に汎用のモジュールは再利用可能で、これが後のプログラムを 速く開発することを可能にする。第三にプログラムのモジュールは独立に試験 することが可能で、これがデバッグ時間の節減に役立つ。

上のことと、gotoがないことなどは殆ど関係がない。これは小規模プ ログラミングに役立つが、一方で、モジュール化設計は大規模プログラミング に役立つ。それゆえ、多少やることが増えるが、FORTRANあるいはアセンブリ言 語において構造化プログラミングの利点を亨受することができる。

また、「On Lisp」にも、同じようなことが書かれています。

構造化プログラミングの推進者達がgotoを憎むのは,それがソース・コードに及ぼした影響のせいだ.彼らが有害だと見なすのはマシン語のジャンプ命令ではない ---ソース・コード内で抽象的構造に隠されている限りは問題にならないのだ. gotoがLispで非難の対象になっている理由は,楽に隠蔽できるからに他ならない:代わりにdoを使えるし,doが備わっていなくとも自分で書くことができる.もちろん新しい抽象的構造をgotoの上に構築するなら,どこかにgotoが存在せざるを得ない.だから新しいマクロの定義にgoを使うのは,既存のマクロが代わりに使えないときなら,必ずしも悪いことではない.

まったく、その通りだと思います。

ループの中で使われる break, next, redo などは、用途の制約されたジャンプ命令であり、本質的に goto と何らかわりがありません。見た目を変えて抽象化していることが重要なのです。

try/catch がない C 言語で本格的なプログラムを書こうとすると、どうしてもエラー処理に goto 文を使わなければならない状況に出会います。事実、BSDカーネルのコードは、goto 文だらけです。

代入が嫌われる理由

「計算機プログラムの構造と解釈」の3章には、「命令型プログラミングの落とし穴」という小節があります。そこに書いてある Scheme のコードを Emacs Lisp に変換すると、上記のコードになります。もう一度、出陣願いましょう。

(defun factorial(n)
  (let ((ret 1) (i 1))
    (while (<= i n)
      (setq ret (* ret i))
      (setq i (1+ i)))
    ret))

このコードに対する 説明はこうです。

これは、プログラムの生じる結果を変えない。しかし微妙な罠をしかける。代入の順序をどう決めるか。たまたま書いた通りで正しい。しかし代入を

      (setq i (1+ i))
      (setq ret (* ret i))

と逆にすると別の正しくない結果を生じる。一般に代入を使うプログラムでは、代入の相対的順序を注意深く考え、各文が変化した変数の正しい版を使うよう確認しなければならない。

たった、これだけの理由だとしたら、「だからどうした」と思います。

「On Lisp」には、もう少し味のあることが書かれています。

setqも,変数がどこで値を得たのかが判り辛くなるので白い目で見られる.

また、こうも書いています。

Lispオペレータのうち,副作用のために呼ばれるよう意図されているものはほんの僅かだ.... 関数的プログラミングを理想とするというのは,プログラムが決して副作用を使ってはいけないということではない.ただ必要以上に使うべきでないということだ.

マクロの出番?

「On Lisp」の Graham さんなら、上記のコードはマクロで抽象化しなさいというでしょう。たとえば以下のように、1 から N まで数えるマクロ dotimes1 を書きます。

(defmacro dotimes1 (spec &rest body)
  `(let ((,(car spec) 1))
     (while (<= ,(car spec) ,(nth 1 spec))
       ,@body
       (setq ,(car spec) (1+ ,(car spec))))
     ,(nth 2 spec)))

このマクロの意味が分かる必要はありません。Graham さんも以下のように主張しています。

マクロ展開は多くの人が読むものではないので,普通はマクロ展開の中で創られた変数にsetqを使うことに害は少ない.幾つかの組み込みマクロの展開形を見てみれば,setqが山程あるだろう.

dotime1 を使えば、どちらの代入文を先に実行するかなんて気にしなくてよくなります。(まぁ、もともと自明ですし、dotimes1 で大幅に抽象化できたなんて主張する気はありません。)

(defun factorial(n)
  (let ((ret 1))
    (dotimes1 (i n ret)
      (setq ret (* ret i)))))

関数型プログラミングの利点

「なぜ関数プログラミングは重要か」の主張に戻ってみましょう。

関数プログラミングの特徴や利点は多かれ少かれ以下のようの要約されること がよくある。関数プログラムは代入文を含まない。それゆえ、変数は一度 値を与えられたら変更されない。もっと一般的ないいかたをすれば、関数プロ グラムには全く副作用がない。関数の呼出しは、結果を計算する以外の作用は もたない。このことは、バグの大きな源のひとつを断つ。また、実行順を気に しなくてよい。式の値を変更する副作用がないので、いつの時点で式の値を評 価してもよい。プログラマはフローの制御を指示するという負担から解放され る。式をいつの時点で評価してもよいので、変数とその値と自由に交換するこ とができる。すなわち、プログラムは「参照透明」である。この自由のおかげ で、関数プログラムはそうではない従来のプログラムより、数学的な扱いが容 易である。

このような「利点」のカタログは確かにそのとおりであるが、かやの外の者が 大したことではないと考えても驚いてはならない。つまり、関数プログラミン グは「〜ではない」ということ(代入はない、副作用はない、制御フローはない) を多く語っているが、「〜である」ということはそれほど語っていない。関数 プログラマはどちらかというと人生の楽しみを否定し、それにより高潔な者に なることを望む中世の修道僧のように思える。もっと物質的な利益に興味のあ る者にとってはこれらの「利点」はあまりピンとくるものではない。

関数プログラマは大きな物質的利益があると主張する。関数プログラマは従来 のプログラマより桁違いに生産的である。関数プログラムは桁違いに短かいか ら。しかし、なぜそうなるか。これらの「利点」にもとづいて示唆できる、微 かにもっともらしいの理由は、従来のプログラムの90%は代入文であり、関 数プログラムは代入文を削除できるというものである。これは全くもって滑稽 である。もし、代入文の削除がそれほど大きな利益をもたらすというなら、 FORTRANプログラマは20年ものあいだそうしたであろう。ひとつの言語をその言 語の特徴のひとつを削除することでより強力にするなどということは論理的に 不可能である。その特徴がたとえとても良くないものであってもである。

結論として、関数型プログラミングの利点は、高階関数と遅延評価だと主張しています。

関数型言語が用意するもうひとつの新しい種類の糊はプログラム全体を貼り合 せることを可能にする。完成した関数プログラムは入力から出力への一つの関 数にすぎないことを思いおこせ。もし、fとgがそうしたプログラムであるなら、 (g . f)は一つのプログラムであり、入力(input)に適用すると

g (f input)

を計算する。プログラムfはその出力を計算し、それはプログラムgの入力とし て使われる。従来はこれをfからの出力を一時ファイルに蓄えることにより実装 できていた。問題は、この方法でプログラムを貼り合せることが非現実的であ るほど、一時ファイルが非常に多くのメモリを占有する可能性があることであ る。関数型言語はこの問題の解決策を用意している。二つのプログラムfとgは 厳密な同期の上で走る。fはgがいくばくかの入力を読もうとして、 gが読もうとしている出力を供給するのに必要な間だけ走る。それから、fは実 行を中断し、gはさらなる入力を試みるまで実行される。ボーナスとしては、も し、gがfの出力をすべて読むことなく終了すれば、fは破棄される。fは無限に 出力を生成しつづける停止しないプログラムでも構わない。それはgが終了すれ ばすぐに強制的にfは停止させられるからである。これにより、停止条件はルー プの本体とは切離すことができ、強力なモジュール化が可能となる。

この評価方式はfをできるだけ走らせないようにするので、「怠惰(遅延)評価」 と呼ばれている。これにより、ひとつのプログラムを大多数の可能な答を構成 する生成器と適切なものを選ぶ選択器にモジュール化することが現実的なもの となる。いくつかのシステムではプログラムをこのような方法で同時に走らせ ることが可能であるが、関数型言語だけが、すべての関数について一律に遅延 評価を用い、プログラムの任意の部分がこの方法でモジュール化可能である。 遅延評価はおそらく関数プログラマのレパートリの中で最も強力なモジュール 化の道具である。

感想

Emacs Lisp には遅延評価はないので、ここでいう関数型プログラミングの恩恵には預かれないでしょう。遅延評価がなくても、高階関数を書くことも、関数に直行性を持たせることも、あたりまえのようにやっていることです。

結局、「代入は使ってはならない」という主張は気にしなくてもいいというのが結論です。