「関数型言語」に関するFAQ形式の一般的説明

  • 729
    いいね
  • 75
    コメント

前置き:

  • 特定の言語ではなく、関数型言語一般に関する説明です。
  • ここに書くのが良いのかわかりませんが、それを考える時間ももったいないのでとりあえず書きます。必要が生じたら移転します。
  • 皆様のご要望や自分の気分(?)により随時加筆修正します。
  • 「それは違うんじゃない?」というご指摘はもちろん、初心者の方の素朴な疑問・質問や、「ここがよくわからない」「こういうことも書いてほしい」みたいなコメントも歓迎します。すぐに対応できない場合もあると思いますがすみません。Twitterのesumii宛でも構いませんが、コメントのほうが他の方も見つけやすくて良いと思います。当然ながら(他者に対しても)誹謗中傷等はご遠慮ください。
  • いただいたコメントはほぼ本文に反映していますので、本文を読むために、必ずしもコメントを読む必要はありません。もちろん、興味と余裕(?)があればコメントも読んでいただければ非常に有用だと思います(皆様ありがとうございます!)。
  • 英語&ちょっと古いですが、これより詳しいFAQとしては http://www.cs.nott.ac.uk/~gmh/faq.html があります。どなたか和訳&アップデートしませんか?←他力本願メソッド
  • (このFAQの)筆者については蛇足をご覧ください。

関数型言語って何?

関数型言語とは、厳密には関数型プログラミング言語(functional programming language)の略で、「関数型プログラミングを推奨・支援するプログラミング言語」のことです。

そういう定義なので、「どの言語が関数型で、どれが関数型ではない」という明確な線引きは存在しません。「JavaやC++は関数型言語である」という人々もいます。「OCamlはC++より関数型言語っぽい」「HaskellはOCamlより関数型言語っぽい」など、「より関数型言語っぽい」という「感じ」は存在します。

参考リンク:「関数型言語を使ってはいけない」

じゃあ関数型プログラミングって何?

副作用をできるだけ(あるいは全く)用いず、式や関数で計算を表すプログラミングスタイルのことです。副作用をまったく用いない関数型プログラムないし関数型言語を純粋(pure)、そうでないものを非純粋(impure)と言います。

じゃあ副作用って何!?

「式の値を計算して求める」(評価(evaluation)と言います)以外の動作のことです。例えば1+2という式には(普通は)副作用はありませんが、命令型言語のprint(1+2)とかprintf("%d", 1+2);とか(文法はテキトーです)には「画面に3を表示する」という副作用があります。

副作用がない式は、必然的に、評価する(=値を計算する)と常に同じ結果になります。これを参照透明性(referential transparency)と言います1

それだと入出力や状態(state)すら表せないのでは?

いいえ、純粋な関数型プログラミングでも、入力を引数、出力を戻り値とする関数を考えることにより、入出力も表現できます。非常に簡単に言うと、例えばhello(x) = "Hello, " + x + "!"みたいな関数で(これも文法は適当です)、文字列hogehogeを入力するとHello, hogehoge!と出力する、みたいなプログラムを書くことができます。

同様に、状態(の変化)についても、古い状態を引数として受け取り、新しい状態を戻り値として返す関数により表すことができます。

もっとも、命令型(手続き型)言語では状態を用いるのが普通の計算を、関数型言語では、そもそも状態を用いず再帰などで計算することも多いです。例えば「1から10までの整数を足す」だったら、命令型言語では

s=0; i=1;
while (i<=10) { s=s+i; i=i+1; }
print(s);

のように変数siの状態を変化させながら計算するところを、関数型言語では

output = sum(0,1)
sum(s,i) = if i<=10 then sum(s+i,i+1) else s

のような感じで書くことが少なくありません(上のプログラム例は適当です)。

副作用を「表現する」「表す」だけじゃ実行できないのでは?

helloなどのように(例えば入出力だったら文字列から文字列への)純粋な関数等で表された副作用も、最終的には言語処理系により実行されます(例えばHaskell処理系ではmainが入出力等を表す値とみなされて実行されます)。副作用を表す値は、単なる文字列や関数であって、それ自体は副作用を持たないことに注意してください。

ここでいう関数(function)とは?

厳密な定義は数学的理論が必要ですが、簡単に言うと「引数を受け取り、戻り値を計算して返す手続き」です。関数の「戻り値の計算」を表す式の部分を本体(body)と言います。例えばf(x) = x+10という関数fだったらx+10が本体です。

式と同様、関数にも、本体に副作用が全くない純粋な関数と、副作用がある非純粋な関数があります。純粋な関数は、参照透明です。つまり、同じ引数を与えれば、常に同じ結果を返します。この点は数学の関数とよく似ていますが、関数型言語もプログラミング言語ですので、手続きとして書けない関数(計算不能関数)は書くことができません。

計算や入出力、状態の変化などを関数や関数適用(呼び出し)で表すので「関数型プログラミング」や「関数型言語」と呼ばれるのだと私は理解しています。

関数型プログラミング・関数型言語の何がうれしいの?

ザックリと簡単に言えば、

  • 副作用がない(純粋な場合)or 少ない(非純粋な場合)ので、
  • プログラム(式)とプログラム(式)の独立性が高く、
  • テスト・検証したり組み合わせたりするのが、
  • 副作用がある/多い場合に比べて簡単

ということだと思います。例えば、上のsum関数であれば、sum(s,i)の戻り値がs + i + (i+1) + (i+2) + ... + 10に等しいので、sum(0,1)0 + 1 + 2 + 3 + ... + 10に等しい、ということを数学的に検証(証明)することも比較的容易です! 後述の高階関数を用いれば、関数を部品に分けたり組み合わせたりすることが容易になるので、さらに独立性や検証可能性を高めることができます。

これらのメリットは非純粋でもそれなりに(大いに?)享受できます。

参考リンク:「なぜ関数プログラミングは重要か」 古典です。ただし、関数(型)プログラミングや高階関数だけでなく、遅延評価(後述)も強く推している点は、当然ながら間違ったことが書かれているわけではないのですが、今や必ずしも一般的ではないと個人的には思います(例:Haskellの主要設計者の一人による講演スライド17~18および39~40頁目、結論「The next Haskell will be strict」)(例2:過去の通説に反して、遅延評価の言語のほうが意味論がはるかに複雑という)。

参考リンク2:「函数プログラミングのエッセンスと考え方」 16~32頁目に、副作用を(あまり)用いず、高階関数を用いて関数を部品として組み合わせていく、関数型プログラミングの例があります。特に25頁目(Java)と26頁目(OCaml)のコードを見比べてください。それ以外の部分も非常に有用な情報の宝庫です。

他にも良い文献があったら or 私が忘れていたら是非とも教えてください(他力本願メソッド2)

関数型言語は実用的ですか?

関数型言語は様々な企業で商業利用されています。2004年から毎年開催されている関数型プログラミング商用ユーザワークショップの情報などを参考にしてください。

高階関数(higher-order function)って何?

関数を引数として受け取ったり、戻り値として返したりする関数のことです。C言語の関数ポインタと似ていますが、JavaScript風の文法で書くと

function make_adder(x) {
  function adder(y) {
    return x + y;
  }
  return adder;
}

みたく「新しい関数を作って」返すこともできる点が違います(GCCの独自拡張等ではC言語でもできますが)。

高階関数があると、

  • 上のほうで述べた「入出力を表す関数」を扱ったり、
  • 二つの関数fgを受け取ってh(x) = f(g(x))のように合成したhを作って返したり、
  • 関数fとリスト[x1,x2,...,xn]を受け取って、fを各要素に適用したリスト[f(x1),f(x2),...,f(xn)]を返したり(mapと言います)、
  • 二項演算子⊕とリスト[x1,x2,...,xn]を受け取って、x1x2⊕...⊕xnを返したり(foldと言います)、

等々、関数を部品として組み合わせることが容易になります。

関数を(整数などと同様に)他の関数に渡したり変数に入れたりできることを、関数が第一級(first-class)の値である、と言うこともできます。第一級関数は、ほとんどの場合、クロージャ(closure)というデータ構造により実装されています(参考記事)。なので、本来は実装に用いるデータ構造の名前ですが、最近では第一級関数の機能のことをクロージャと呼ぶ言語もあります。

高階関数は非常に強力なので、いわゆる関数型言語以外のプログラミング言語でも「当たり前の機能」になりつつあります。高階関数がなければ(あるいは関数が第一級でなければ)関数型言語にあらずという人も少なからずいます。

遅延評価(lazy evaluation)って何?

簡単に言うと、「必要になるまで、式の値を計算しない」という計算方法(評価戦略(evaluation strategy))のことです。

例えばf(x,y) = if x>0 then x else yという関数に対し、f(式1,式2)みたいな関数適用(呼び出し)を考えます。「普通」は式1式2の値を計算してからfを呼び出しますが、遅延評価では「必要になるまで、式の値を計算しない」ので、とりあえずfを呼び出します。すると、if x>0のせいでxすなわち式1の値が「必要」になるので計算します。それがもし正だった場合、yすなわち式2の値は計算する必要がないので計算しません。

こうすることで、式2の値を計算する手間が省けるだけでなく、「無限に長いリスト」(ストリームとも言います)を容易に扱えるなどのメリットもある一方、いつどこで計算が起こるか(結果としてプログラムの実行時間や特にメモリ消費)が、人間にとって予想しにくくなることもあります。

遅延評価と純粋・非純粋は直交(独立)な概念であることに注意してください。Haskellはデフォルトで遅延評価の純粋な関数型言語、MLはデフォルトで遅延評価でない(先行評価(eager evaluation)もしくは正格(strict)であると言います)非純粋な関数型言語ですが、「先行評価の純粋な関数型言語」もいくつかありますし、「遅延評価の非純粋な関数型言語」も(プログラムの動作が人類に理解できるか疑問ですが)理論的には可能です。

第一級関数を利用して、先行評価の言語の中で遅延評価を実現する(遅延評価の言語を埋め込む)ことも可能です。先行評価でも関数の本体は、その関数が呼び出されるまで評価されないことを利用します。

OCamlなど、デフォルトは先行評価でも、注記(annotation)により遅延評価が可能な関数型言語もあります。Haskellなど、その逆もあります。

モナドって?

先のhello関数のように入出力や状態を表す引数や戻り値をいちいち明示して書くのは面倒くさいので、見た目は普通に副作用があるように見えるプログラムを書くための仕組みです。例えばhello = { x = Read(); Write("Hello, " + x + "!"); }みたいな雰囲気で書けます(文法は適(ry。ただし、これも副作用がある「ように見える」だけで、実際にはhello(x) = "Hello, " + x + "!"みたいな関数等の書き方の一種に過ぎないので、それ自体には副作用はありません(詳しい方へ:例えばhelloのリストを作った場合を想像してください)。

学術的には圏論(category theory)が云々…ですが普通に関数型言語を使うだけならば必ずしも理解する必要はないと思います。モナドは当然ながらHaskellなど純粋な関数型言語でよく用いられますが、MLなど非純粋な関数型言語でも、副作用を扱いやすくする等の目的で使うことがあります。モナドの仕組みは強力なので、副作用を表す以外の目的にも利用されています。

参考リンク:http://doi.acm.org/10.1145/262009.262011 ないし http://homepages.inf.ed.ac.uk/wadler/topics/monads.html の中の "How to declare an imperative"(DVIとPostScriptしかないですがWebで検索すればPDFファイルも出てきます。どっかに日本語訳ないんでしょうか?>ご存じの方)

詳しく知りたい方は、「すごいHaskellたのしく学ぼう!」という本の説明も非常に丁寧で(その分だけ長いですが)わかりやすいみたいです。

他に良い文献があったら or 私が忘れていたら是非とも教えてください(他力本(ry>皆様

オブジェクト指向と関数型は対立していますか?

いいえ、メジャーなオブジェクト指向言語が命令型言語ベースのため、オブジェクト指向=命令型という誤解もよくありますが、データとそれに対する操作(メソッド)のまとまり(オブジェクト)を基本にシステムを構築するオブジェクト指向と、「副作用を用いない」関数型プログラミングとは、直交・独立な概念です。積極的に副作用を用いる命令型オブジェクト指向も、副作用を用いない純粋関数型オブジェクト指向もあります(Pierce著「型システム入門」第18章と第32章など)。要するに、オブジェクトの状態を破壊的に更新するか(命令型)、新しい状態を持つオブジェクトを作り直して返すか(関数型)というだけの違いです(後者はいわゆるイミュータブルなオブジェクトとして広まりつつあるようです)。

むしろ、オブジェクト指向も関数型言語も、基礎理論はほとんど同じ分野の人たちが研究しています(紹介記事)。オブジェクトと第一級関数やデータ抽象の考え方(第2章・第3章)など、強い類似も少なくありません。Schemeの第一人者による「オブジェクト指向プログラミングに関する欧州会議」(ECOOP)における基調講演スライド(特に22ページ目)や、Haskellの主要設計者の一人による「オブジェクト指向プログラミング・システム・言語・アプリケーションに関する国際会議」(OOPSLA)における基調講演スライド(およびGoogle TechTalksにおける同内容の講演動画)でも議論されているので参照してみてください。

もちろん、どんな言語(というかどんな技術や概念)でもあるように、関数型言語のファンでオブジェクト指向が嫌いという人も一定数はいますし:-)それは思想・信条の自由です。上の記述はあくまで理論の話です。紹介記事の冒頭に書いたとおり、「単純な関数型言語に、複雑なオブジェクト指向はいらない」という考え方もあります(私個人の好みもそれに近く、OCamlのOはほとんど使っていません。参考リンク:「オブジェクトは OCaml の鬼子」)。

関数型言語は哲学や宗教と関係がありますか?

ありません。いやひょっとしたらいつか何らかの関係が見出されるかもしれませんが、これまでのところ、まっとうな言説は寡聞にして知りません。

参考リンク:ソーカル事件

(詳しい方へ:ライプニッツのモナドが…とか、カリーハワード対応する数理論理学の起源は哲学だから…とかは、ここでは「関係がある」に含めません。哲学科出身の計算機科学研究者の先生方もいらっしゃいますが、一部で見られるような2トンデモ議論は伺ったことがありません。Cf. すべてのものには関係があるが、近いものは遠いものより関係がある

より詳しく関数型言語ないし関数型プログラミングを学ぶには、どのような本が良いですか?

いろいろとありますが、文献リストとしては http://d.hatena.ne.jp/akuraru/20150410/p1 が良いと思います。(他にもあったら(ry

蛇足:あなたは誰ですか?

東北大学 大学院 情報科学研究科の教授(ソフトウェア基礎科学分野)です3。情報処理国際連合(IFIP)関数型プログラミング ワーキンググループ(WG2.8)の正メンバーや、米計算機学会(ACM)関数型プログラミングに関する国際会議(ICFP)の委員・委員長などを務めさせていただいています。それ以前にも同国際会議主催のICFPプログラミングコンテストでは2000年ペンシルバニア大学チーム)と2002年東京大学チーム)の2回ほど優勝させていただきました!:-)

TODO: 主な関数型言語の良い紹介へのリンク集

TODO: 関数型言語は銀の弾丸ではない(書くまでもない?)


  1. 本来の分析哲学での意味とは異なるようですが(参考)、関数型言語の分野では歴史的事情により広まってしまった用語法のようです。 

  2. 誤解があるといけないので止むを得ず一つだけ具体的に挙げると、元MITの著名研究者が英語版Wikipediaでトンデモ議論を展開してbanされるまでに至ってしまった件など、古来(?)より複数の事例があります(「えらい先生」を引き合いに出してすみません)。 

  3. 他の方と混同されていると耳にしたので念のため…(内輪ネタ(?)ですみません)