なぜ関数プログラミングは重要か


John Hughes,
Institutionen för Datavetenskap,
Chalmers Tekniska Högskola,
41296 Göteborg, SWEDEN.
rjmh@cs.chalmers.se

この日本語訳は原著者の承諾を得て山下がここに公開するものです。
この訳文についての、御指摘などは山下伸夫(nobsun .at. sampou.org)までおねがい いたします。
翻訳最終更新日 : 2011-09-17


原文 "Why Functional Programming Matters"
日本語訳PostScript

この論文は1984年以来何年ものあいだChalmers大学のメモとして回覧された。 1989年と1990年に幾分か改訂をしたのが[Hug89]と [Hug90]である。この版はもとのChalmer大学のメモ のnroff原稿をもとにしてLaTeX用にいくぶん編集を加え、出版用のものに近づけ たものである。さらに、一つ二つの誤りを訂正している。いくぶん古臭い整形で あること、例が Haskell ではないことをお許しいただきたい。

概要

ソフトウェアがどんどん複雑になるにつれ、それを上手く構造化することがま すます重要になっている。上手く構造化したソフトウェアは書きやすく、デバッ グしやすく、かつ、将来のプログラミングコストを引き下げるために再利用可 能な部品群を提供するものである。従来の言語では問題を部分化する方法につ いて概念的な限界がいくつかある。関数型言語はこれらの限界を押し広げるも のである。この論文では、とくに関数型言語の二つの特徴、モジュール化に大 きく貢献する高階関数と遅延評価を披露する。例のように、リストとツリーを 操作し、いくつかの数値計算アルゴリズムをプログラムし、また、α-β発見 法(ゲームをするプログラム中で用いられる人工知能由来のアルゴリズムのひと つ)の実装をおこなう。モジュール性はプログラミング成功の鍵であるから、関 数型言語は実世界にとって極めて重要である。

1. イントロダクション

本論文は「実世界」にとって関数プログラミングが極めて重要であることを例 示し、関数プログラマが、関数プログラミングの利点が何であるかを明確にす ることでその利点をフルに活用できるよう支援するひとつの試みである。

関数プログラミングは、関数だけで全体が構成されているプログラムの故にそ う呼ばれている。メインプログラムそれ自身は、プログラムへの入力を引数と して受けとり、その結果としてプログラムの出力を供給する関数として書く。 典型的にはこのメイン関数は別の関数を使って定義する。それらもまた、さら に多くの関数を使って定義し、最終的なレベルでは関数は言語のプリミティブ となる。これらの関数は通常の数学的な関数に似ており、この論文では普通の 等式で定義する。記法はTurnerの言語、Miranda(TM) [Tur85]に準じたものであるが、関数型言語の知識 なしでも読めるものになっているはずである。(MirandaはResearch Software Ltd. の商標である。)

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

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

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

関数プログラマでさえ、いわゆる利点には満足してはいないはずである。それ は、関数型言語を活用するのに役にたたないからである。代入がないだけ、あ るいは参照透明であるだけではプログラムを書くことはできない。そこには、 プログラムの品質をはかる尺度がない故に、めざすべき理想がないのである。

あきらかに、このように関数プログラミングを特徴付けることは不適当である。 代わりのなにかを見つけなければならない。関数プログラミングの力を説明す るだけではなく、関数プログラマが懸命にめざすところを明示するなにかを。

2. 構造化プログラミングとの類似

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

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

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

今やモジュール化設計がプログラミングを成功させる鍵であることは一般に受 け入れられている。そして Modula-II [Wir82]、 Ada [oD80]、 Standard ML [MTH90]のような言語はとくにモジュー ル性を向上させるように設計された機能を含んでいる。しかしながら、多くの 場合、見過ごされる非常に重要なポイントがある。問題を解くための部品プロ グラムを書くとき、その問題を部分問題に分割し、部分問題を解き、その解を 合成する。元の問題を分割する方法は、部分解を貼り合せる方法に直接依存す る。それゆえに、概念的には問題をモジュール化する能力を高めるためにはそ のプログラミング言語のなかで新たな糊の類を用意しなければならない。複雑 なスコープ規則や分割コンパイルの規約は事務的な詳細でしかなく、問題を分 解する新しい概念的道具をあたえるものではない。

糊の重要性は、大工仕事との類比によって、正しく評価できる。椅子は、部分 (座部、脚、背もたれなど)を作り、それらを正しくくっつけ合せることで容易 に作ることができる。しかし、これはジョイントと木を張り合せるという能力 に依存する。その能力がなければ、椅子を作る方法はひとつ木の塊からそれを 彫り出す以外なく、非常に難しい作業になる。この例は、モジュール化の強大 な力と正しい糊を持つことの重要性の両方を例示するものである。

さて、関数プログラミングに戻ろう。この論文の残りの部分では関数型言語が 二つの新しい、非常に重要な糊を提供するのだという議論をしよう。あたらし い方法でモジュール化可能でそれによって非常に簡潔になるプログラムの例を いくつもあげていこう。これこそが関数プログラミングの力の鍵であり、モジュー ル化を大幅に向上することが可能になる。また、関数プログラマが目指して邁 進すべき目標は、これから述べる新しい糊で、より小く、より簡潔に、より汎 用的なモジュールを貼り合せるということである。

3. 関数の貼り合せ

二種類の糊のうち最初のものは単純な関数を貼り合せてより複雑な関数にする ものである。これは簡単なリスト処理問題(リストの要素の足しあげ)で説明す ることができる。リストを

	listof X  ::= nil |  cons X (listof X)
 
と定義する。これはXのリスト(Xは何でもよい)はnil(要素のないリストを表現 する)であるか、または、あるXと別のXのリストをconsしたものである、という 意味である。consはその最初の要素がXで二番目の要素およびそれに続く要素が 別のXのリストの要素であるようなリストである。Xはここでは任意の型を表し ている。たとえば、Xが整数ならこの定義は、整数のリストは空か、整数と整数 のリストとのconsであるということである。通常のやりかたに従ってリストを 明示的にnilやconsを書くのではなく、単にその要素を角括弧でくくって書くこ とにする。これは単に記法の便のための省略記法にすぎない。たとえば、
    []           の意味は     nil
    [1]          の意味は     cons 1 nil
    [1,2,3]      の意味は     cons 1 (cons 2  (cons 3  nil))
 
である。リストの要素を再帰関数sumを使って足しあげることができる。sumは 二種類の引数、空リスト(nil)とconsに対して定義されていなければならない。 なにもない数の和はゼロであるから、
     sum nil =  0
 
と定義する。consの和は最初の要素を残りの要素の和に足すことで計算でき るので、
     sum (cons num list) = num +  sum list
 
と定義することができる。この定義を検証すると、下の箱のなかの部分のみが sumの計算に固有な部分であることがわかる。
               +---+
    sum nil =  | 0 |
               +---+
                              +---+
    sum (cons num list) = num | + |  sum list
                              +---+
 
このことは、sumの計算は一般的な再帰パターンと箱のなかの部分とを貼り合せ ることでモジュール化できることを意味している。この再帰パターンは慣例と しては reduce と呼ばれている。そして、sumは、
     sum = reduce add 0
 
のように表現できる。ここで簡単のためにreduceには演算子ではなく二引数関 数addが渡されるものとする。addは単に
    add x y  =  x +  y
 
のように定義される。reduceの定義はsumの定義をパラメータ化するだけで導く ことが可能で、
    (reduce f  x) nil =  x
    (reduce f  x) (cons a l)  = f a ((reduce f x)  l)
 
となる。ここで、(reduce f x) のように括弧でかこったのは、この部分がsum になることを明確にするためである。慣例としてはこの括弧は省略し、 ((reduce f x) l)は(reduce f x l)のように書く。reduceのように三引数の関 数はふたつの引数だけに適用された場合、残りの一つに引数を取る関数 となる。一般にn引数の関数がm(<n)の引数に適用された場合には残りのn-m引数 を取る関数となる。この慣例についてはあとで見ていくことにしよう。

このようにして、sumをモジュール化したのでこの部品を再利用する利益を得る ことができる。最も興味のあるのはreduceの部分である。これは、余分にプロ グラミングをすることなく、リストの要素を掛け合せる関数を書くのに使える。

    product =  reduce multiply 1
 
また、真理値のリストの要素がどれかが真であるかどうかを検査するのに利用 することもできる。
     anytrue =  reduce or false
 
あるいはすべての要素が真であることを検査するのにも利用できる。
     alltrue =  reduce and true
 
(reduce f a)を理解する一つの方法は、リストのなかで、consが出現するとこ ろをすべてfで置換え、nilが出現するところをすべてaで置換える関数だと看倣 すことである。例としてリスト[1,2,3]を取ることしよう。このリストは
     cons 1 (cons 2  (cons 3  nil))
 
ということなので、(reduce add 0)はこれを
     add 1 (add 2  (add 3  0))   =   6
 
に変換する。そして、(reduce multiply 1)はこれを
     multiply 1 (multiply 2  (multiply 3 1))   =    6
 
へ変換する。そうすると、(reduce cons nil)はリストを複写するものであるこ とは明白である。ひとつのリストの要素をもうひとつリストの前へconsしてい くことで、二つのリストを連結することができるので、
     append a  b =  reduce cons b a
 
というのを見いだすことができる。例をあげれば、
     append [1,2] [3,4] = reduce cons [3,4] [1,2]
                        = (reduce cons [3,4]) (cons 1 (cons 2  nil))
                        = cons 1  (cons 2 [3,4]))
                                  (replacing cons by  cons and nil by [3,4])
                        = [1,2,3,4]
 
リストのすべての要素を二倍する関数は次のように書くことができる。
        doubleall = reduce doubleandcons nil
 where  doubleandcons num list = cons (2*num) list
 
doubleandcons はさらにモジュール化することができる。まず、
        doubleandcons = fandcons double
        where  double n  = 2*n
               fandcons f el list = cons (f el) list
 
それから、
     fandcons f =  cons .  f
 
である。ここで、「.」(関数合成の標準演算子)は以下で定義される。
     (f .  g) h  = f  (g h)
 
fandconsの新しい定義が正しいことはいくつかの引数に適用してみれば理解で きる。
     fandcons f el  = (cons . f) el
                    = cons (f el)

したがって、
     fandcons f el list = cons (f el) list
 
最終版は、
     doubleall = reduce (cons . double) nil
 
となる。さらにもう一段モジュール化をすすめると、
    doubleall = map double
    map f =  reduce (cons .  f) nil
 
に到達する。ここでmapは任意の関数fをリストのすべての要素に適用する。map はもうひとつの汎用的に有用な関数である。リストのリストとして表現された 行列の要素の足しあげする関数も書くことができる。それは、
     summatrix = sum .  map sum
 
である。map sum はすべての行を足しあげるのにsumを使い、左はしのsumはそ の行の全体を足しあげて行列全体の和を得ている。

これだけの例があれば、ちょっとしたモジュール化が大いに役立つ可能性がある ことを納得するはずだ。単純な関数(sum)を「高階関数」といくつかの単純な関 数の合成としてモジュール化することにより、とくに余分にプログラミング努 力をすることなくリスト上の多くの関数を書きおろすのに使える、(reduce)と いう部品に到達した。リスト上の関数にとどまることはない。もうひとつの例 として、つぎに定義される、ラベル付順序ツリー

     treeof X  ::= node X  (listof (treeof X))
 
の型について考察しよう。この定義は、Xのツリーとは、あるXというラベルと、 やはりXのツリーであるようなサブツリーのリストをもつノードであるというこ とである。たとえば、
            1 o
            / \
          /     \
        /         \
     2 o             o 3
                     |
                     |
                     |
                     o  4
 
というツリーは
     node 1
         (cons (node 2  nil)
               (cons (node 3
                          (cons (node 4 nil) nil))
                     nil))
 
で表現される。例を考えたり、そこから高階関数を抽象したりはせずに、 reduceに類似した関数redtreeへ直行しよう。reduceは二つの引数、consと置換 える何かと、nilと置換える何かを取ったことを思い出そう。ツリーはnodeと consとnilで組み立てられているので、redtreeはそれぞれを置換える何かとい う三つの引数をとらなければならない。ツリーとリストは別の型なので、それ ぞれの型の上の演算に一つずつ、二つの関数を定義する必要がある。故に、
  redtree f  g a  (node label subtrees) =
          f label (redtree' f g a subtrees)
  redtree' f g  a  (cons subtree rest) =
           g  (redtree f g  a subtree) (redtree' f g a rest)
  redtree' f g  a  nil = a
 
と定義する。redtreeと他の関数を貼り合せることで、興味深い関数がいくつも 定義できる。たとえば、ツリーのラベルの数値をすべて足すには、
     sumtree =  redtree add add 0
 
を使う。前述の例のツリーを引数として取ると、sumtreeは、
     add 1
        (add (add 2 0)
             (add (add 3
                  (add (add 4 0)  0))
                       0))
     = 10
 
を与える。ひとつのツリーのlabel全体のリストは
     labels =  redtree cons append nil
 
を用いる。同じ例では、
     cons 1
          (append (cons 2 nil)
                  (append (cons 3
                                (append (cons 4 nil) nil))
                          nil))
     = [1,2,3,4]
 
となる。最後にmapと類似した関数で、ある関数fをツリーのすべてのラベルに適用 する関数を定義できる。
      maptree f  = redtree (node . f) cons nil
 
これらはどれも、従来のプログラミング言語では分割できない関数を、部品(汎 用の高階関数といくつかの特定の特殊化関数)の合成として表現できる関数型言 語なればこそ可能になる。このような高階関数は、一度定義すると、非常に簡 単に数多くの演算をプログラムすることができる。新しいデータ型を定義した ときにその型を処理する高階関数を書くべきである。そうすれば、その データ型の取り扱いが簡単になり、その表現の詳細に関する知識を局所化でき る。従来のプログラミング言語での類推として一番いいのは、望みの時にはい つでも、新しい制御構造で拡張できるという拡張可能な言語である。

4. プログラムの貼り合せ

関数型言語が用意するもうひとつの新しい種類の糊はプログラム全体を貼り合 せることを可能にする。完成した関数プログラムは入力から出力への一つの関 数にすぎないことを思いおこせ。もし、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をできるだけ走らせないようにするので、「怠惰(遅延)評価」 と呼ばれている。これにより、ひとつのプログラムを多くの可能な答を構成 する生成器と適切なものを選ぶ選択器にモジュール化することが現実的なもの となる。いくつかのシステムではプログラムをこのような方法で同時に走らせ ることが可能であるが、関数型言語だけが、すべての関数について一律に遅延 評価を用い、プログラムの任意の部分がこの方法でモジュール化可能である。 遅延評価はおそらく関数プログラマのレパートリの中で最も強力なモジュール 化の道具である。

4.1. ニュートン-ラプソン法による平方根

いくつかの数値計算アルゴリズムのプログラミングをすることで遅延評価の力 を説明しよう。先ず最初に、平方根を求めるニュートン-ラプソンのアルゴリ ズムを考えよう。このアルゴリズムは数値Nの平方根を、初期近似値a0から始 めて、以下のルールを使って、どんどん改良していって、求める。

     a(n+1) =  (a(n) + N/a(n)) / 2
  
もし、この近似がある極限値aに収束するなら、
      a =  (a +  N/a) / 2
したがって、
      2a = a +  N/a
      a =  N/a
      a*a = N
      a =  squareroot(N)
  
である。実際この近似は急速にある極限値に収束する。平方根プログラムは一 つの許容誤差(eps)をとり、ふたつの隣接する近似値の差がepsよりも小くなった ときに停止する。このアルゴリズムは通常、だいたい以下のように プログラムされる。
     C   N IS  CALLED ZN HERE SO THAT IT HAS  THE RIGHT TYPE
           X = A0
           Y = A0 + 2.*EPS
     C   THE VALUE OF Y DOES NOT MATTER SO LONG AS ABS(X-Y).GT.EPS
     100   IF  (ABS(X-Y).LE.EPS) GOTO 200
           Y = X
           X = (X + ZN/X) / 2.
           GOTO 100
     200   CONTINUE
     C   THE SQUARE ROOT OF ZN IS NOW IN X
  
このプログラムは従来の言語では不可分なものである。これを遅延評価を使っ てよりモジュール化された形式で表現し、別のいくつかの場面でのその部品の 使い方を示す。

ニュートン-ラプソンのアルゴリズムは近似値の列を計算するので、プロ グラム中ではこれを、近似値のリストとして表現するのが自然である。各近似 値はその手前の近似値から次の関数によって導びく。

     next N x = (x + N/x) / 2
  
それで、(next N)は一つの近似値を次の近似値へ写像する関数である。この関 数をfと呼ぶと、近似値の列は、
      [a0, f a0, f(f  a0), f(f(f a0)), ..]
  
となる。これを計算する関数、
     repeat f  a =  cons a  (repeat f (f  a))
  
を定義すると、近似値のリストは
     repeat (next N) a0
  
で計算できる。repeatは「無限」の出力をともなう関数の一例である。しかし、 無限の出力を伴うことは問題ではない。なぜなら、実際にプログラムの他の部 分が要求しないかぎり、余分な近似値は計算されない。無限性は潜在能力にす ぎない。これらが意味するところは、必要とあらば、任意の数の近似値を計算 できるということであり、repeatは制限をもたないということである。

平方根発見器の残りの部分は、関数withinで、この関数は許容誤差と近似値 のリストを引数としてとり、そのリストを見て与えられた許容誤差よりも差の 小さい二つの連続する近似値を探す。これは次のように定義できる。

     within eps (cons a  (cons b rest))
            = b,                        if  abs(a-b) <= eps
            = within eps (cons b rest), otherwise
  
これらの部品を一緒にして、
     sqrt a0 eps N  = within eps (repeat (next N) a0)
  
とする。平方根発見器の部品を手にしたので、今度はこれらを別の方法で合成 してみることができる。ここで、行いたい変更のひとつは、二つの連続する近似値 の差がゼロに近づくのを待つのではなく、二つの近似値の比が1に近づくのを 待つようにすることである。これは非常に小さい数(二つの連続する近似値が 初めから小さい)に対してはより適切な方法である。また、非常に大きい数(丸 め誤差が許容誤差よりも大きい)場合にもより適切である。withinの代わりに 次のものを定義するだけでよい。
     relative eps (cons a (cons b  rest)) 
               = b,                          if abs(a-b) <= eps*abs b
               = relative eps (cons b rest), otherwise
  
さて、新しいバージョンのsqrtは以下のように定義できる。
     relativesqrt a0 eps  N =  relative eps (repeat (next N) a0)
  
近似値を生成する部分は書換える必要はない。

4.2. 数値微分

近似値の列を平方根に再利用したが、もちろん、withinやrelativeを近似値の 列を生成する任意の数値計算アルゴリズムに再利用することも可能である。数値 微分のアルゴリズムに再利用してみよう。 ある点においてある関数を微分した結果はその点におけるその関数のグラフの 傾きである。これは、その関数の与えられた点とその近くの点での値を計算し、 その二点間の直線の傾きを計算することで簡単に見積ることができる。この方 法は、もし二点が十分に近ければその関数のグラフはその間では大きく曲るこ とはないという仮定をしている。これにより、以下の定義をする。
     easydiff f x  h  = (f(x+h)-f x) /  h
  
よい近似値を得るためには、hの値は非常に小さくなくてはならない。残念な がら、もしhが非常に小さいと、二つの値f(x+h)とf(x)は非常に接近すること になる。そうすると、その差をとる演算での丸め誤差が結果をだいなしにして しまう可能性がある。どのようにして適正なhの値を選べばよいか? このジレ ンマに対する一つの解決策はhを合理的な大きさの値からはじめて小さくしな がらそれに対応する近似値の列を計算することである。このような列は微分値 に収束しなければならないが、結局のところ丸め誤差によって救いがたく不正 確な値になるだろう。もし、(within eps)が十分な精度の最初の近似値を選ぶ のに使われていれば結果に影響する丸め誤差の危険性はかなり低減され得る。 この列を計算するのに関数がひとつ必要である。
     differentiate h0 f x = map (easydiff f x) (repeat halve h0)
     halve x  =  x/2
  
ここでh0はhの初期値である。それ以降の値は繰り返し半分にすることで得ら れる。この関数があれば、任意の点での微分を
      within eps (differentiate h0 f x)
  
によって計算することができる。この解決法でも十分満足できない。それは近 似値の列の収束が相当遅いからである。ここで一寸した数学が役立つ。件の列 の要素は
     正しい値 + h に関連する誤差項
  
のように表現でき、理論的に誤差項はだいたいhの累乗に比例することを示せ るので、これをhが小さくなるよりもさらに小さくすることができる。正しい答 えをAとすると誤差項はB*h**nとなる。各近似は次に使うhの2倍の値で計算す るので、任意の連続する近似値は
     a(i)   =  A + B*(2**n)*(h**n)
および、
     a(i+1) =  A + B*(h**n)
  
と表現できる。ここで、誤差項は消去でき、
          a(i+1)*(2**n) - a(i)
     A =  --------------------
                2**n - 1
  
といえる。もちろん誤差項はおおまかにhの羃乗であるとしたので、この結論 も近似である。しかし、これはずっとよい近似である。この改良はすべての連 続する近似値の対に
     elimerror n (cons a  (cons b  rest)) =
             =  cons ((b*(2**n)-a)/(2**n-1)) (elimerror n  (cons b rest))
  
を用いて適用できる。誤差項を近似値列から除去することでずっと速く収束す るもうひとつの近似値列ができる。 elimerrorを使えるようにするにはもうひとつ問題がのこっている。nの正しい 値を知る必要がある。一般にはこの数値がなにになるかを予見することは難し いが計ることはやさしい。つぎの関数がそれを正しくそれを正しく評価すると いうことを示すのは難しくないが、証明はここではしない。
     order (cons a  (cons b (cons c rest))) =
             =  round(log2( (a-c)/(b-c) - 1  ))
     round x =  x rounded to the nearest integer
    log2 x   =  the logarithm of x to the base 2
  
さて、近似列を改良する汎用関数を定義する。
     improve s  = elimerror (order s) s
  
ある関数fの微分はimproveを使うと、以下のように、更に効率良く計算するこ とができる。
     within eps (improve (differentiate h0  f x))
  
improveはパラメータhを使って計算される近似値列にのみ作用し、hはおのお のの近似値間で半分になっていく。しかしながら、もしこれをその結果がさら に近似値列になっているような近似値列に適用すると! つまり、近似値列は1 回より多く改良され得るということである。別の誤差項が毎回除去され、結果 として近似列はずっとずっと速く収束する。そこで、以下をつかうと微分を非 常に効率良く計算できる。
     within eps (improve (improve (improve (differentiate h0 f  x))))
  
数値解析家の言葉では、これは4次の方法と同等なもので急速に精度の高い結 果をもたらす。
     super s  =  map second (repeat improve s)
     second (cons a  (cons b  rest)) =  b
  
と定義をすることも可能である。これはrepeat improveをつかって近似値列を 繰り返し改良した列を得て、改良された列のおのおのから二番目の近似値をと ることで新しい列を構成する。(二番目が採用するのに最適である。それは一 番目よりも精度が高く、余分な計算を必要としない。) このアルゴリズムは非 常に洗練されたものであり、近似値を生成すればするほど、どんどんと良い 計算メソッドになってゆくのである。このプログラムをつかって本当に効率よ く微分が計算できる。
     within eps (super (differentiate h0 f  x))
  
これは大槌をつかって、木の実を割るようなものであるが、要点はsuperのよ うな洗練されたアルゴリズムでも遅延評価を使ってモジュール化すれば簡単に 表現できるということである。

4.3. 数値積分

この節で議論する最後の例は、数値積分である。問題は次のように簡単に記述 できる。一実数引数の実数値関数fと二端点aとbが与えられたとき、二つの端 点間のfの曲線の下側の面積を求めよ。もっとも簡単な計算法はfが殆ど直線で あると仮定して面積をもとめるというものである。
     easyintegrate f a  b  = (f  a +  f b)*(b-a)/2
  
残念ながらこの計算ではaとbが非常に近くにないかぎり非常に不正確なものに しかならないように思える。よりよい計算法はaとbの間を二つにわけて、半分 ずつ計算してそれを足しあわせて面積を計算するというものである。最初の近 似値に前述の公式を用いてその積分値に近づく近似値列を定義することがで きる。そして、積分値にどんどん近づく近似値を半分ごとに足しあわせて残り の計算をする。この列は以下の関数で計算される。
     integrate f a b = cons (easyintegrate f a b)
                            (map addpair (zip (integrate f a mid)
                                              (integrate f mid b)))
                       where mid = (a+b)/2
  
zipはもうひとつの標準リスト処理関数である。二つのリストをとり、対のリ ストを返す。それぞれの対は二つのリストの対応する要素である。すなわち、 最初の対は、第一のリストの最初の要素と第二のリストの最初の要素からなる。 以下同様である。zipは以下のように定義できる。
     zip (cons a s) (cons b t) =  cons (pair a b) (zip s t)
  
integrateにおいて、zipは二つのサブ区間のそれぞれの積分値へ近づく値に対 応する対のリストを計算し、addpairを適用して対の要素の和をもとめ、元の積分へ近 づく近似値のリストを与える。 実はこのintegrateのこのバージョンは多少非効率である。それは、fの値を連 続して再計算しているからである。書いてあるとおり、easyintegrateはfをa とbとの点について評価し、integrate再帰呼び出しはこれらをそれぞれ再評価す る。また(f mid)はそれぞれの再帰呼出しのなかで評価される。それ故にfの値 を再計算しない以下のバージョンの方が望ましい。
     integrate f a b =  integ f a b (f  a) (f  b)
     integ f a  b fa fb = cons ((fa+fb)*(b-a)/2)
                               (map addpair (zip (integ f a m fa fm)
                                                 (integ f m b fm fb)))
                          where m = (a+b)/2
                                fm =  f m
  
integrateは積分値に漸近する無限リストを計算する。これは前節で differentiateが計算したのと同じである。それゆえ、任意の望む精度の積分 ルーチンは以下のように書きくだすことができる。
     within eps (integrate f  a b)
     relative eps (integrate f a b)
  
この積分アルゴリズムは前節で、最初の微分アルゴリズムがかかえていたのと 同じ欠点をかかえている。すなわち、収束が遅いことである。これはまた改良 することができる。この列の最初の近似値は(easyintegrateによって)二つの 点のみを使って計算され、b-aを区間とする。二番目の近似値は中点を使う。そ れにより、隣接点間の区間幅は(b-a)/2のみである。三番目の近似値はそれぞれ の半分の部分でこの方法を使う。それにより隣接点間の区間幅は(b-a)/4のみ である。あきらかに隣接点間の区間幅はそれぞれの近似値と次の近似値との半 分になる。この区間幅を「h」としてとり、列は前節で定義した、「improve」 関数を用いた改良に対応する候補となる。故に積分値に急速に収束する近似値 列を、たとえば、 以下のように書きおろすことができる。
    super (integrate sin 0 4)
    improve (integrate f 0 1)
    where f x = 1/(1+x*x)
  
(この後者の列はpi/4の計算に対する8次の方法である。二番目の近似値は、 fは5回の評価しか必要とせずに、小数点5桁まで正しい値である。) この節ではいくつもの数値計算アルゴリズムをとりあげ、部品を貼り合せる糊 として遅延評価を使って関数的にプログラムした。おかげで新しい方法で、 within、relative、improveのような汎用的に有用な関数にモジュール化する ことができた。これらの部品をいろいろな方法で組合せることでいくつかの良 い数値計算アルゴリズムを単純に簡単にプログラムした。

5. 人工知能からの例

関数型言語が本来、強力なもので、それは、高階関数と遅延評価というふたつ の新しい種類の糊をもつためであると主張した。この節ではより規模の大きい 例を人工知能からとり、この二つの糊をつかってどのように非常に単純 にプログラムすることが可能かを示す。

選択した例はα-β発見法というゲームプレイヤの状態がどのくらい良いものか を見積るアルゴリズムである。このアルゴリズムはゲームがどのように展開す るかを先読みすることで動作するが、役にたたない道筋を追及することは回避 する。

ゲーム状態がpositionという型のオブジェクトで表現されているものとしよう。 この型はゲーム毎に変化するものになる。これについては何も仮定しない。あ る状態からどのような動きが可能かを知る方法がなければならない。次のよう な関数があると仮定する。

     moves: position ->  listof position
 
この関数はゲーム状態を引数としてとり、ひとつの動きでとどき得るすべての 状態のリストを返す。例として三目並べを考えると、
           | |           X| |     |X|     | |
          -+-+-          -+-+-   -+-+-   -+-+-
    moves  | |     =   [  | | ,   | | ,   |X| ]
          -+-+-          -+-+-   -+-+-   -+-+-
           | |            | |     | |     | |

           | |           O| |     |O|
          -+-+-          -+-+-   -+-+-
    moves  |X|     =   [  |X| ,   |X| ]
          -+-+-          -+-+-   -+-+-
           | |            | |     | |
 
となる。これは、常にひとつの状態からどちらのプレイヤの番であるかを言う ことが可能であると仮定している。三目並べではどちらの番であるかは○と ×の数を数えることで判断する。チェスのようなゲームではこの情報は明示的 に「position」型に含めておかなければならない。

関数movesがあれば、最初のステップはゲームツリーを構築することである。こ のツリーはノードに状態のラベルが付いており、ノードの子はそのノードから 一手で到達可能な状態でラベル付けされたノードとなる。すなわち、もしノー ドが状態pのラベルがついたものであれば、その子は(moves p)の状態のどれか でラベル付けされている。ゲームツリーは無限に十分なり得る。もし、ゲーム が勝負がつかずに無限につづく場合である。ゲームツリーは第2節で議論したツ リーと同じものである。おのおののノードはラベル(状態を表現している)とサ ブノードのリストとを持つ。それゆえに、これらを表現するのに同じデータ型 を使うことができる。

ゲームツリーはmovesを繰り返し適用することによって、構築する。ルートの状 態からはじめて、movesはそのルートのサブツリーのラベルを生成するのに用い る。その後movesはサブツリーのサブツリーを生成するのに用いる。再帰のこの パターンは以下の高階関数を用いて表現できる。

     reptree f  a =  node a (map (reptree f)  (f a))
 
この関数を用いて、特定の状態からゲームツリーを構築するもうひとつの関数 を定義することができる。
     gametree p =  reptree moves p
 
例えば、図\ref{fig1}を見よ。ここで使われている高階関数(reptree)は前節で 無限リストを構築するのに使われた関数repeatに類似している。
   
            | |
           -+-+-
  gametree  | |
           -+-+-
            | |

                       | |
                      -+-+-
  =                    | |
                      -+-+-
                       | |
                    /  |  \
                  /    |    \
                /      |      \
              /        |        \
            /          |          \
          /            |            \
      X| |             |X|             | |
      -+-+-           -+-+-           -+-+-
       | |             | |             |X|
      -+-+-           -+-+-           -+-+-
       | |             | |             | |
      /|\           /|\           / \
       ...             ...          /     \
                                  /         \
                                /             \
                             O| |               |O|
                             -+-+-             -+-+-
                              |X|               |X|
                             -+-+-             -+-+-
                              | |               | |
                             /|\             /|\
                              ...               ...

  
α-βアルゴリズムは与えられた状態から先読みをしてゲームが良い方へ展開す るのか、悪い方へ展開するのかを知る。しかし、これを実行するには先読みな しで、ある状態の値をおおまかに評価することが可能でなければならない。こ の「静的評価」は先読の限界点で用い、このアルゴリズムを早く導くために用 いることになる。静的評価の結果は、コンピュータ側の視点(コンピュータが人 の対戦相手であることを仮定する)から見たある状態の見こみの尺度である。こ の結果が大きければ大きいほど、コンピュータ側の状態は良く、結果が小さけ れば小さいほど、状態が悪いということになる。このような性質の最も単純な 関数は、たとえば、コンピュータが既に勝っている状態では、+1を、負けてい る状態では-1をそれ以外は0を返すというものである。現実的にはこの静的評価 関数は「良い状態」となるさまざまなことを計る。たとえば、チェスでは、駒 の優位、中央部の支配などである。以下のような関数があると仮定しよう。
     static: position ->  number
 
ゲームツリーはひとつの(treeof position)であるから、関数(maptree static) を用いて、数値のツリーに変換することができる。(maptree static)は、この (無限の可能性もある)ツリーのすべての状態を静的に評価する。これは、第2節 で定義した関数maptreeを使う。

このような静的評価の木が与えられた場合、そのなかの状態の正確な値は何で あろうか。特にルートの状態に帰すべき値は何であろうか。その静的な値ではない、 なぜなら、その静的な値はおおまかな推測にすぎないからだ。あるノードに帰 すべき値はそのサブノードの正確な値から決定されるものでなければならない。 この決定は各プレイヤが可能な手のうち最良のものを選ぶという仮定を用いて 行う。高い値ほどコンピュータにとって良い状態であるということを思いおこ せば、任意の状態からのコンピュータの手は正確な値が最大のサブノードに誘 導する手を選択することになろう。同様にして、対戦者は正確な値が最小のサ ブノードに誘導する手を選択することになる。コンピュータと対戦者は交互に 手を打つことを仮定すれば、ノードの正確な値は、コンピュータの番ならば、 関数maximiseが計算した値であり、対戦者の番であれば、minimiseが計算した 値である。

     maximise (node n sub) =  max (map minimise sub)
     minimise (node n sub) =  min (map maximise sub)
 
ここでmaxとminは数値のリスト上の関数でそれぞれリストの最大値と最小値を 返す。これらの定義は完成品ではない。基本の場合の定義がないので、再帰が 永遠に続くからである。子がないノードの値を定義する必要があり、その値を そのノード(のラベル)の静的評価として採用する。故に静的評価はプレイヤが すでに勝利したとき、あるいは先読の限界に達したときに用いられる。 maximiseおよびminimiseの完全な定義は以下のようになる。
     maximise (node n nil) =  n
     maximise (node n sub) =  max (map minimise sub)
     minimise (node n nil) =  n
     minimise (node n sub) =  min (map maximise sub)
 
この段階で、一つの状態をとり、その正確な値を返す関数はほとんど書きおろ すことができる。これは以下のようになる。
     evaluate = maximise . maptree static .  gametree
 
ここには二つ問題がある。まず第一に、これは無限のツリーに対しては動かな い。maximiseはサブツリーのないノード(当該ツリーの終端のひとつ)に到達す るまで、再帰を続ける。もし終端がなければ、maximiseは何も結果を返さない。 第二の問題は同類の問題で、三目並べのツリーのようにたとえ有限のツリーで あっても、実際は非常に大きいツリーになり得るということである。ゲームツ リー全体を評価しようというのは非現実的である。探索は、次の数手に限らな ければならない。ツリーを固定の深さに刈り込むことでこれを実現する。
    prune 0  (node a x)  = node a  nil
    prune n  (node a x)  = node a  (map (prune (n-1)) x)
 
(prune n)はツリーを引数としてとり、ルートからnを超えるところにあるすべ てのノードを「切り捨てる」。もし、ゲームツリーが刈り込まれていれば、 maximiseは深さnのノードで次の再帰に入らず静的評価を使うようになる。ゆえ に、evaluateは以下のように定義することができる。
     evaluate = maximise . maptree static .  prune 5 .  gametree
 
これは(たとえば)五手の先読をおこなう。 この開発ではすでに高階関数および遅延評価を用いている。高階関数reptreeお よびmaptreeによりゲームツリーの構築と処理が簡単にできる。さらに重要なこ とは、遅延評価によりevaluateを上のようにモジュール化できるということで ある。gametreeは潜在的に無限の結果をもつので、このプログラムは遅延 評価でなければ停止しないことになる。遅延評価がなければ、
     prune 5  .  gametree
 
と書く代りに、この二つの関数を一つに畳み込んで当該ツリーの最初の五つの リーフだけを構築するようにする必要があるだろう。さらに最初の五つのリー フだけでも大きすぎて一度にメモリ内に保持できない可能性がある。このプロ グラムで書いた関数
     maptree static . prune 5  . gametree
 
はツリーの部分をmaximiseが要求しただけしか構築しない。おのおのの部分は maximiseが処理を終えたとたんに捨てられ(ガーベッジ・コレクタにより回収さ れ)るので、ツリー全体がメモリ内に常駐することはない。一時に格納されるの はツリーの小さい部分のみである。それゆえ、この遅延評価のプログラムは効 率がよい。この効率のよさは、maximise(合成の鎖の最後にある関数)と gametree(合成の鎖の最初にある関数)との相互作用に依存するものであるから、 遅延評価なしで実現するなら鎖のなかの関数全てを一つの大きな関数に畳み込 まなければならない。これは激烈なモジュール性の低下であるが、日常に起っ ていることである。各部分をいじりまわすことで、この評価アルゴリズムに改 良を加えることができる。これは比較的やさしい。従来のプログラマはプログ ラム全体を一つの単位として変更しなければならず、これはずっと難しい。

これまでは、単純なミニマックス法についてのみ言及してきた。α-βアルゴリ ズムの核心は、多くの場合、ツリー全体を見ることなくmaxmiseあるいは minimiseの値を計算することができるという観察にある。以下のツリーを考え よ。

              max
             / \
           /     \
         /         \
       /             \
     min               min
    / \             / \
  /     \         /     \
 1         2       0         ?
 
不思議なことに、このツリーを評価するために疑問符の値を知る必要はないの である。左側の最小値は1になるが、右側の最小値はあきらかに0に等しいかあ るいはそれより小さい。ゆえに二つの最小値の最大値は1にならなければならな い。この観察は一般化することができ、minimiseやmaximiseに組込むことがで きる。最初のステップはmaximiseを分離して数値のリストへのmaxの適用にする。 すなわち、maximiseを次のように分解する。
     maximise = max  . maximise'
 
(minimiseも同様に分解する。minimiseおよびmaximiseは完全に対称であるから、 maximiseについて議論し、minimiseも同様であるとする。) ひとたび、このよ うに分解するとmaximiseはminimiseそのものではなく、minimise'を使うことが でき、これを使って、minimiseがどの数字の最小値をとるかを見出す。次に、 これによっていくつかの数値はこれを見ることなく捨ることができる。遅延評 価のおかげで、もしmaximiseが数値のリストのすべてを見るわけではない場合 にはいくつかの数値は計算されず、これは潜在的に計算時間の節約になる。

maximiseの定義からmaxを因子抽出することはやさしい。以下のようになる。

     maximise' (node n  nil) =  cons n  nil
     maximise' (node n  l) =  map minimise l
           = map (min .  minimise') l
           = map min (map minimise' l)
           = mapmin (map minimise' l)
     where mapmin =  map min
 
minimise'は数値のリストを返し、そのリストの最小値がminimizeの結果 となる。したがってmap minimise' l)は数値のリストのリストを返す。 maximise'はそれらのリストの最小値のリストを返さなければならない。 しかしながら、このリストの最大のもののみ に関心がある。その最小値が(maximiseの結果に)影響を与えないようなリスト の最小値を除外するmapminの新しいバージョンを定義することになる。
     mapmin (cons nums rest)
      =  cons (min nums) (omit (min nums) rest)
 
この関数omitは「潜在的最大値(これまで見た最大の最小値)」を引数としてと り、これよりも小さい 最小値をすべて除外する。
     omit pot nil =  nil
     omit pot (cons nums rest)
      =  omit pot rest,                          if minleq nums pot
      =  cons (min nums) (omit (min nums) rest), otherwise
 
minleq は数値のリストと潜在的最大値を引数としてとり、もしこの数値のリス トの最小値が潜在的最大値よりも小さいか等しければ真を返す。これを実行するために リスト全体を見る必要はない。もし、このリストの要素のどれかが潜在的最大 値よりも小さいか等しければ、このリストの最小値も確実に小さいか等しい。 このようになる特定の要素の後のものには用はないのである。これは上記の例 の疑問符のものと同様である。それゆえに、minleqは以下のように定義できる。
    minleq nil pot  = false
    minleq (cons num rest) pot = true,            if  num<=pot
                               = minleq rest pot, otherwise
 
maximise'およびminimise'をこのような方法で定義しおえたので新しい評価器 は以下のように単純に書ける。
     evaluate = max  . maximise' .  maptree static . prune 8 . gametree
 
遅延評価のおかげで、maximise'が見るツリーの見る部分がより少くなるという ことはプログラム全体がより効率良く動作するということを意味する。このこ とはpruneが無限のツリーの一部を見るだけであるということがプログラムが停 止することを可能にするというのと同じことである。maximise'における最適 化は非常に単純ではあるが、評価のスピードに劇的な効果をもたらし得る。ま た、そのおかげで評価器は更に深く先読みすることが可能になる。

別の最適化をこの評価器にほどこすことができる。たとえば、今述べたα-βア ルゴリズムは、最良の手筋を最初に考えれば、最も良く働く。それは、もし、 非常に良い手を見付けたらそれより悪い手は、対戦者がそれに対して少くとも ひとつは良い応手をもつということを示す以外は必要のないものである。それ ゆえに、各ノードごとにサブツリーをソートし、コンピュータの手番のときは 大きい順に、そうでないときには小さい順にならべたいとおもう。これは以下 のような関数を書くことで実現できる。

     highfirst (node n sub) =  node n  (sort higher (map lowfirst sub))
     lowfirst (node n sub) =  node n (sort (not.higher) (map highfirst sub))
     higher (node n1 sub1) (node n2 sub2) =  n1>n2
 
ここでsortは汎用の整列関数である。これで評価器を以下のように定義する。
     evaluate = max . maximise' . highfirst . maptree static .
                      prune 8 . gametree
 
探索を制限するために、コンピュータあるいは対戦者の3手だけを考慮すれば十 分であると考えてよい。これをプログラムするのに必要なのはhighfirstを (taketree 3 . hightfirst)に置きかえることだけである。ここで、
     taketree n =  redtree (nodett n) cons nil
     nodett n  label sub = node label (take n sub)
 
である。taketreeはツリーのすべてのノードを、最大でn個のサブノードをもつノー ドに置換える。これはリストの最初のn個の要素(リスト長がn以下のときはそれ より小さい数の要素)を返す関数(take n)を用いる。

もうひとつの改良は枝刈りの洗練である。上のプログラムは状態が動的なもの であるにもかかわらず、固定の深さの先読をする。たとえばチェスでクィーン 取りがかかっている状態なのにそれ以上先を読まないという判断をするかもし れない。いくつかの「動的」な状態を定義し、これらの状態のところで先読み が止ってしまわないようにするのが普通である。関数「dynamic」がこのような状態を識別できるものと仮定すると関数 pruneの定義に一行の等式を加えるだけでよい。

     prune 0 (node pos sub) =  node pos (map (prune 0) sub),
                                              if dynamic pos
 
このような変更を加えることはこの例のようにモジュール化されたプログラムで は容易なことである。先に言及したように、このプログラムはその効率が 連鎖のなかの最後の関数maximiseと連鎖のなかの最初の関数gametreeとの間の 相互作用に決定的に依存しているので、遅延評価がなければ、一枚岩のプログ ラムとしてしか書けない。そのようなプログラムは書くのも、変更を加えるの も難しく、理解するのは非常に難しい。

6. 結論

この論文では、モジュール性がプログラミング成功の鍵であることを主張した。 生産性の向上を目的とした言語はモジュラプログラミングをよくよくサポート しなければならない。しかし、新しいスコープ規則や分割コンパイルの機能で は不十分である。モジュール性はモジュール以上の意味がある。問題を部分に 分解する能力は解を貼り合せる能力に直接に依存している。モジュラプログラ ミングを支援するには、言語は良い糊を用意しなければならない。関数型プロ グラミング言語は二つの新しいタイプの糊を供給する。すなわち、高階関数と 遅延評価である。これらの糊を用いて新しいわくわくするような方法でプログ ラムを簡単にモジュール化できる。その例をいくつも示した。より小さく、よ り汎用的なモジュールは、その後のプログラミングでより広く再利用すること ができる。このことは、なぜ関数プログラムが従来のものよりもずっと簡単に 小さく書けることの説明になる。そして、関数プログラマが狙うべき目標を用 意することになる。もしプログラムの部分のどこかがごちゃごちゃで複雑なも のであるなら、プログラマはそれをモジュール化し、その部品を汎用化しなけ ればならない。これを実現するためのツールとして高階関数と遅延評価が使え ることを期待するはずだ。

もちろん、高階関数や遅延評価の力や優雅を指摘したのはこれが最初ではない。 例えば、Turnerはこの二つが化学構造を生成するためのプログラムのなかで大 変有利に使えるのを示している[Tur81]。 AbelsonとSussmanはストリーム(遅延リスト)がプログラムの構造化に強力な道具 となることを強調した[AS86]。Hendersonはストリーム を関数型のオペレーティングシステムを構築するのに用いた[Hen82]。本論文の主に貢献するところはよりよいモ ジュール化がひとり関数型言語の力の鍵であると主張することである。

遅延評価をめぐる現在の論争にもかかわっている。関数型言語は遅延評価であ るべきだと信じるものもいれば、遅延評価であるべきではないと信じるものも いる。遅延リストを用意するだけで妥協するものもいる。この場合、(たとえば、 [AS86]のSCHEMEのように)特殊構文を用いてこれを構成 する。本論文では遅延評価が非常に重要で、第二級の市民権に格下げできない という更なる証拠を用意した。それは関数プログラマの持つおそらくもっとも 強力な糊であろう。このような極めて重要なツールへのアクセスを妨げてはな らない。

謝辞

この論文はOxfordのProgramming Research GroupでのPhil WadlerとRichard Birdとの多くの会話に負うところが大いにある。Charmers大学Göteborg校 のMagnus Bondessonは数値アルゴリズムのひとつの初めのころのバージョンに 深刻なバグがあることを指摘してくれた。そして、これに関して他の多くのも のの開発を促してくれた。この仕事はUK Science and Engineering Research Councilの支援により実現した。

[AS86] H. Abelson and G.J. Sussman. Structure and Interpretation of Computer Programs, MIT Press, Boston, 1986
[Hug89] J. Hughes. Why Functional Programming Matters, Computer Journal, 32(2), 1989
[Hug90] J. Hughes, Why Functional Programming Matters, In D. Turner, editor, Research Topics in Functional Programming, Addison Wesley, 1990
[MTH90] R. Milner and M. Tofte and R. Harper, The Definition of Standard ML, MIT Press, 1990
[oD80] United States Department of Defense, The Programming Language Ada Reference Manual, Springer-Verlag, 1980
[Hen82] P. Henderson, Purely Functional Operating Systems, 1982
[Tur81] D. A. Turner, The Semantic Elegance of Applicative Languages, Proceedings 1981 Conference on Functional Languages and Computer Architecture, Wentworth-by-the-Sea, Portsmouth, New Hampshire, 1981
[Tur85] D. A. Turner, Miranda: A non-strict language with polymorphic types, Proceedings 1985 Conference on Fucntional Programming Languages and Computer Architecture, pp.1-16, Nancy, France, 1985
[Wir82] N. Wirth, Programming in Modula-II, Springer-Verlag, 1982