第1章　関数プログラミングは難しくない！―初めて学ぶ人にも、挫折した人にもきちんとわかる

マルチコア環境が身近になった影響からか、勉強熱心なプログラマの間で関数型言語が話題になっているようです。関数型言語が奨励する関数プログラミングでは、これまで命令型言語で習得した、命令プログラミングの再代入を使う技法があまり通用しません。そのため、「⁠関数型言語は難しい」と言って途中で投げ出してしまう人も多いようです。

この特集では、関数プログラミングの習得を一度諦めてしまった人や、これから始める人のために、関数プログラミングのポイントをできるだけわかりやすく説明します。

筆者がわかるようになるまで

実は筆者も長い間、関数プログラミングを習得できませんでした。筆者は、長年Emacs Lispを使って、Mewというメールリーダーを開発してきました。人によってはLispを関数型言語に分類していて、そういう人は筆者のことを関数プログラマだと思っていたようです。しかし、実際のところEmacs Lispは命令型言語に分類するほうが適切であり、筆者がEmacs Lispでやっていたのは命令プログラミングでした。

そもそも関数プログラミングと命令プログラミングの違いもわかっていませんでしたし、「⁠関数プログラミングでは再代入（破壊的代入）を使わない」と聞いたことはありましたが、再代入なしでプログラミングができるとは想像もできませんでした。

関数プログラマと思われているのに関数プログラミングをまったく知らないというジレンマを打破するために、また再代入なしのプログラミングとは何かを理解するために、2007年に関数型言語Haskellを勉強しはじめました。そして、関数プログラミングが本当にわかったと思えるまでに、1年半かかりました。

こう言うと関数型言語や関数プログラミングは難しいと思われるかもしれませんが、習得に時間がかかったのは先入観を持っていたり、良い入門書に出会えなかったからです。わかりやすい説明があれば、関数プログラミングはそれほど難しくはありません。ただ、関数プログラマの数が少ないので、良い入門書が圧倒的に少ないのは確かです。この特集では、「⁠はじめからそう言ってもらえればわかったのに」という筆者の経験をもとに、重要なポイントを説明していきます。

関数型言語とは何か

あるようでない関数型言語の共通理解

そもそも関数型言語や関数プログラミングとは何でしょうか？驚かれるかもしれませんが、これらの言葉に共通理解はありません。それぞれの人が、それぞれの意味でこれらの言葉を使っています。

たとえば、「⁠関数に関数を渡せれば関数型言語だ」と言う人がいます。これは、あとで述べる筆者の定義とは異なります。

筆者の定義のほうが正しいと言うつもりはありません。理解していただきたいのは、このような共通理解の欠如が、関数型言語を難しいと思わせている一因だということです。関数型言語について議論するときは、まず「僕の関数型言語の定義はこう。君の定義は何？」と聞く必要があります。

筆者の関数型言語の定義

筆者の関数プログラミングの定義、すなわちこの特集での定義は、「⁠永続データプログラミング」です。永続データとは、破壊できないデータ、つまり再代入できないデータのことです。そして、永続データを駆使して問題を解くのが永続データプログラミングです。

また関数型言語とは、永続データプログラミングを奨励し支援している言語のことです。関数型言語では、再代入の機能がないか、再代入の使用は限定されています。筆者の定義はかなり厳しいほうだと言えます。

この対比で言えば、命令プログラミングとは「短命データプログラミング」ということになります。短命データとは再代入により破壊できるデータのことです。for文のカウンタ変数iが典型的な短命データです。

後述するように、永続データはマルチコアと相性が良く、短命データはマルチコアと相性が悪いことが知られています。筆者の関数プログラミングの定義から言えば、関数プログラミングがマルチコア時代に期待されている理由がよくわかると思います。

関数型言語の仲間たち

筆者の関数型言語の定義に合うメジャーな言語を次に示します。

静的型付き：Clean、F#、Haskell、OCaml、Scala、SML
動的型付き：Clojure、Erlang

型の検査を（コンパイル時など）実行の前に実施するのが静的型付き、実行時に実施するのが動的型付きです。

Lisperの方には申しわけありませんが、筆者はCommon LispやEmacs Lispを関数型言語には分類していません。Schemeは微妙です。これらのLispは、「⁠Lisp」という独自のパラダイムだと考えるほうがよいと思います。ClojureはLispの一種ですが、永続データプログラミングを推進しているので関数型言語に分類できます。

それぞれの言語を簡単に説明します（順不同⁠）⁠。

SML: その名の通り標準化されたML（Meta-Language）です。ML系の言語では、関数の型を書かなくても、正しいコードであれば型が推論でき、推論できた場合は型レベルの誤りがないことが保証されます。参照型や配列に対しては破壊的代入ができます。いくつか実装がありますが、筆者としては東北大学で開発されているSML#に期待しています。
OCaml: フランスのINRIA[1]が開発したML系の言語です。コンパイラがあまり最適化を施さないにもかかわらず、出力されたコードが高速に動作します。参照型などへの破壊的代入が可能です。構造的サブタイピングによる型安全なオブジェクトや多彩なモジュール機能を持っています。
F#: MicrosoftがOCamlをもとにして開発した.NET上のML系言語です。Visual Studioで開発でき、多様な.NETのライブラリを利用可能です。
Scala: Martin Odersky氏が、オブジェクト指向プログラミングと関数プログラミングを融合するために作ったJVM用の言語です。環境の変化に追随できるように拡張性を重視して設計されており、一見組込みだと思われる機能がライブラリとして実装されています。
Clojure: Rich Hickey氏が開発したJVM用の革新的なLispです。古いLispの欠点（たとえば、わかりにくい関数名や括弧の多さ）を改善しています。永続データプログラミングを基本としており、破壊的な操作はSTM（Software Transactional Memory）を使うことでのみ許されます。
Haskell: 純粋関数型言語が乱立した状態を解決すべく標準化された純粋関数型言語です。Miranda[2]に似た文法を持ち、デフォルトで遅延評価です。実質的な標準実装であるGHCでは、軽量スレッドやSTMが利用できます。
Clean: オランダのナイメーヘン大学で開発された純粋関数型言語です。Haskellと同様Mirandaに似た文法を持ち、デフォルトで遅延評価です。破壊的代入や入出力にまつわる問題を一意型という機能を使って解決しています。
Erlang: 軽量プロセスを用いたネットワークプログラミングに特化した言語です。エリクソン社が開発しました。軽量プロセスは、ほかの軽量プロセスとメッセージをやりとりすることで処理を進めます。高い耐故障性を持ち、コードのホットスワップもできます。

これまでの知識が足枷（あしかせ）に

かつての筆者がそうだったように、命令プログラマであれば、再代入なしにプログラムが書けるなんて想像もできないのではないでしょうか？一体、再代入できる変数なしでどうやってfor文を実現するのでしょう？

関数プログラミングを習得するには、これまで命令プログラミングで培った技術はいったん忘れ、真っ白な気持ちで臨む必要があります。関数型の山を登るためには、命令型の山を降りなければなりません。関数プログラミングの習得が難しい理由の一つは、このようにプログラミングの初心者に戻ることを要求されるからだとも言えます。

この特集では、4つの問題を再代入なしに解いていきます[3]⁠。

数値計算─⁠─第2章
最長重複文字列探索─⁠─第3章
赤黒木（ハッシュテーブル⁠）⁠─⁠─第4章
CSVパーサの実装─⁠─第5章

関数プログラミングの雰囲気が伝われば幸いです。

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

命令プログラミングでも十分自分のやりたいことは実現できるのに、わざわざ関数プログラミングを学ぶ理由はなんでしょうか？その疑問に答えるべく、関数プログラミングの利点をまとめます。

豊かなデータ型を持つ

一般的に関数型言語は、構造体（直積⁠）⁠、共用体（直和⁠）⁠、列挙型および再帰型を統合し、簡潔に表現できる豊かなデータ型を提供しています。この豊かなデータ型を使えば、たとえば木構造を簡潔に、しかも（危険なnullを使わないで）安全に定義できます。もちろんこの木構造は永続データです。

また、豊かなデータ型と表裏一体の機能であるパターンマッチングによって、データを直感的に操作できます。型が豊かであればあるほど、問題を容易に、しかも安全に解けるようになるので、プログラミングが楽しくなります。

今回は豊かなデータ型の例として木構造を第4章で扱います。

高いエラー検出率を誇る

命令型言語には式と文という構成要素があります。すべては式であるとする命令型言語もありますが、その場合は式を文の代わりに使っていることになります。一方、関数型言語の構成要素はすべてが式であり、小さな式を組み上げて大きな式を作ります。プログラム全体も一つの式です。

一般的に、文と文の間には型による制約がありませんが、式と式との型の関係は型システムによって検査されます。関数型では、全体がいくつもの式から組み立てられているので、あらゆる部分で型の関係が検査されます。豊かな型と協調しながら実施される型検査では、命令プログラマが想像するよりもはるかに多くの間違いを発見できます。

静的型付きの関数型言語では、この徹底的な型検査がコンパイル時に実行されます。テストケースを書かなくてもテストができ、コンパイルが通れば（たとえば整数と文字列を足すといった）型に関するバグが存在しないことが保証されます。静的型付きの関数型言語で開発すれば、自ずとテスト駆動となり、高品質のソフトウェアを作成できます[4]⁠。

高いエラー検出率については、第2章で扱います。

部品プログラミングが可能

関数プログラミングの極意は、バグが入り込みにくい小さな関数を使って大きな関数を組み立てることです。こういうと少しずつ異なる目的それぞれのために、似たような関数をたくさん書かないといけない場合が発生するのでは、と思われるかもしれません。しかし関数型言語には、関数に関数を渡すという機能があるので問題にはなりません。

引数に関数を取る関数は「高階関数」と呼ばれます。関数プログラミングでは、似たような仕事をする関数を一つの高階関数としてまとめ、引数として渡す関数で挙動を変化させます。言わば、汎用の部品に引数を渡して特定の目的専用の部品を作るのです。

命令型言語ではデータと関数（メソッド）の集合が部品となるのとは対照的に、関数型言語では関数自体が部品となります。これ以降の章はすべて、部品プログラミングの例になっています。

テストが容易

関数型言語では、関数が小さいのでテストが容易です。また、副作用のない関数とある関数を明確に分けるので、副作用のない関数に関してはテストが簡単です。

副作用の意味がわからないという人もいるかもしれませんので、この特集での定義を述べておきましょう。関数は、与えられた引数をもとに計算し結果を返します。計算結果を返す以外の仕事をする場合は「副作用がある」と言います。たとえば、入出力がそれにあたります。

また、関数は同じ引数に対して同じ結果を返すべきです。同じ引数を与えたのに、異なる結果を返す場合も副作用があると表現します。この種の副作用の原因は、再代入可能なグローバル変数などを利用していることです。関数プログラミングでは再代入は制限されていますので、この種の副作用については気にしなければならない範囲は狭いと言えます。

副作用のない関数とある関数の分離をどれくらい厳密に要求するかは言語によって異なります。絶対に分けなければならない言語、分けないとコンパイラが警告する言語、プログラマの良識に任されている言語とさまざまです。

今回掲載するコードには、すべて副作用がありません。基本動作を対話的にテストしていきます。関数プログラミングでも、入出力を扱うには副作用のあるコードを記述する必要がありますが、それは命令プログラミングとあまり変わらないので、今回は説明しません。

並列プログラミングの可能性が開ける

短命データを使ったプログラムをマルチコアに対応させるのは容易ではありません。再代入の際に一貫性を保証するために、変数をロックする必要があるからです。ロックが少ないと一貫性が保てませんし、たくさんあるとロックの順番を間違ってデッドロックを起こしやすくなります。ロックの粒度が小さければ利用方法を間違いやすくなりますし、ロックの粒度が大きければ性能が向上しにくくなります。

並列プログラミングの問題を解決する単一の方法はありません。用途別にいくつかの方法が提案されており、どの方法も永続データが基本となっています。これらは難しい話になりますので、この特集では取り上げません。ただ、わかりやすいScalaの例は紹介しておきましょう。Scala 2.9では、永続データである並列コレクションを利用すれば、これまでのメソッドチェインにparメソッドを挿入するだけで、処理が自動的にマルチコア化されます。

プログラミングがうまくなる

関数プログラミングを学ぶとプログラミングがうまくなります。なぜなら、プログラムを式のみで構成するという規律を学んだり、副作用がある関数とない関数を意識して分けるようになるからです。命令プログラミングしかする機会がない方も、関数プログラミングを学ぶ価値は十分にあります。筆者はHaskellを学んではじめて、プログラミングとは何かわかりました。

Haskellの環境整備

この特集では、関数型言語としてHaskellを用います。しかしながら、Haskell特有の機能は使いませんので、この特集の内容はほかの関数型言語でも通用するはずです。

Haskellを使う理由は、第一に筆者がHaskellをよくわかっているから、第二に文法が簡潔で本質を示しやすいからです。Haskellの文法は簡潔であるといっても、初心者には十分難しいでしょう。そこで、この特集では限られた構文しか用いません。たとえばローカル関数などの構文は用いないため、例示するプログラムがやや冗長になっています。

HaskellのGHCを利用

Haskellは標準化された言語であり、いくつか実装がありますが、一番よく使われているのはGHC（Glasgow Haskell Compiler）です。名前の通りコンパイラ（ghc）も提供されていますが、それ以外に対話環境（GHCi）やスクリプトとして実行させるコマンド（runghc）も付いてきます。

Haskell Platformのインストール

GHCとライブラリ管理コマンド（cabal⁠）⁠、および基本的なライブラリをまとめたパッケージが、Haskell Platformです。現在のバージョンは、2011.4.0.0であり、Linux、Mac、そしてWindows用が提供されています。この特集では、Haskell Platformを利用することを前提とします。最新のバージョンではなくとも、すべての例題は動きます。インストールしやすいバージョンを入れてください。

MacとWindowsのHaskell Platformは、ダウンロードのあと、クリックするだけでインストールできるので問題ないでしょう。Linuxですが、Debian系では次のようにしてインストールできます。

% apt-get install haskell-platform

ほかのLinuxでは、コンパイル済みのGHCを入れ、Haskell Platformに格納されるライブラリはGHCでコンパイルしてインストールする方法がよいでしょう。具体的には、1つ前のバージョンに対してインストール方法をまとめたWebページを参考にしてください。

対話環境の起動

Haskell Platformをインストールし終えたら、お好みのターミナルでGHCの対話環境コマンドであるGHCiを起動してください。次のようにPrelude>というプロンプトが表示されたら成功です。

% ghci
GHCi, version 7.0.4: http://www.haskell.org/ghc/ :?
for help
（略）
Prelude>

記念にHaskellのプログラムを実行してみましょう。お決まりのHello, World!の表示、そして簡単な計算をやってみます。

Prelude> putStrLn "Hello, World!"
Hello, World!
Prelude> 1 + 2
3

putStrLnは、引数の文字列を改行と共に標準出力へ出力する関数です。このようにHaskellでは、関数名にCamel形式[5]を使います。

GHCiを終了させるには、:quitコマンドを使います。

Prelude> :quit
Leaving GHCi.
%

次章からは、いよいよ関数プログラミングの世界に入っていきます。

本特集は、伊藤真之さん、大野健太さん、小宮山純平さん、竹井成和さん、日比野啓さん、桃井康成さん、山下伸夫さん（名前順）にレビューしてしていただきました。ここに名前を記して感謝いたします。