【DT閑話】童貞プログラマが函数型言語(とラムダ計算)を理解してみる【初心者向け解説】

単なる函数オブジェクトをラムダと呼んだら怒られる気もするけど…*1 まあ小噺程度に僕も話してみたいです＞＜

函数型プログラミング言語に実用性はあるか? といふ問題についてはちゅーんさんが書いてくれてるので、プログラミング初心者なりにラムダ計算に焦点を当てて考察していけたらなー、と思ひます。

初心者が初心者向けに語ることは良いことと悪いことがそれぞれたくさんあって、初心者丸出しのこの blog でもいつも悩みながら書いてます。初心者が解説を書くことで自分の中にあるもやもやとした理解をまとめ上げることができる、そして熟練者が失ってしまひかねない初学者ならではも躓きを捉へられるといふのが良い点。そして悪い点としては、正確でない表現を別の初心者が間に受けてしまって、伝言ゲームで間違った認識を得ること。そんなわけで、僕はできる限り正確に把握したいと調べながら記事を書くことにしてます。

元記事さんを読んで気になるところとして、用語の不正確さがあります。「ラムダ式」と呼ばれてるものは、「ラムダ計算 (λ-calculus)」と、プログラミング言語の「ラムダ式」と呼ばれることもある機能について混同してます。プログラミングの文脈では「ラムダ式」は、後述するような函数を扱った機能のことを指すことが多いように感じられます。

函数とは何か

細かい定義は ja.Wp - 関数 (数学) を読んでください、ってことでいまは話を進めることにします。つまりは、 $f(x) = 2x + 3$ としたときに、 $f(5) = 2 \times 5 + 3 = 13$ になるものが函数です。俗に「数学的な函数」と呼ばれるもので、われわれが中学校の数学の時間に習ったシンプルな形がこれです。

この函数は、たとへば C言語でも十分に表現することができます。

int f (int x) {
    return 2 * x + 3;
}

JavaScript でも、ほぼ同様に書くことができるので、以下は JavaScript をベースに書くことにします。

var f = function (x) {
    return 2 * x + 3;
}

JavaScript を動かすには Google Chrome の JavaScript コンソールを利用するのがいちばん簡単です。

λとは何か

λ計算とは、アロンゾ・チャーチの考案した計算体系です。なぜ λ なのかは諸説あるのでこの場では拘りませんが、はじめ ^ と表現したのが誤植により Λ (λの大文字) になり、やがて小文字の λ になったのだ、との話が一般的なようです。つまり、 λ には「函数の記号」以上の意味はありません。

さて、さきほどの函数の定義を λ記法と呼ばれる流儀の書きかたで表すと、次のようになります。

$f = \lambda x.\, 2 \times x + 3$

また、 $g(x, y) = y / x$ であれば $g = \lambda x.\, \lambda y.\, y / x$ となります。

この記法では、 $f(5)$ を $f\, 5$ と、 $g(3, 2)$ を $g\,3\,2$ と書くことができます。難しい話はできるだけ抜きに行きたいのですが、「函数 f に引数 5 を渡して戻り値を得る」ことを「 f を 5 に適用する」と表します。

なぜこのように、一般的な数学の教科書などと別の記法をとるのかといふと、 $f(x)$ とだけ書いたときに函数 f の定義なのか、 f を x に適用(Cなどのプログラミング言語では函数呼び出し)した結果なのかの曖昧さを排除するため、とのことです*2。

実は純粋な λ計算の λ式では数字や計算式をこのように書くことができなくて、チャーチエンコーディングなどの方法で自然数を表現してやる必要があるのですが、ここではやはり気にせず次に進んでいくことにします。

JavaScript と λ

はい、ここからが「ラムダ式」の話になります。

プログラミング言語でいふところのラムダ式は C#, Python, Ruby, C++11 など、多くの言語に導入されてゐます*3。そして、我らが JavaScript の function 式も、ほかならぬこれらと同様のものです。

さきほど紹介した JavaScript のコードで function f (x) { ... } と書かずに var f = function (x) { ... } ; と書いたので、もしかすると違和感を覚えたかもしれません。

JavaScript には混乱しやすいことに、 function 式と function 文があります。式と文の区別は各自で気の向いたときに確認していただきたいのですが、ひとつ重要なことがあります。

function f (x) { ... } の函数定義では、この函数に必ず f と名前が付きます。ところが var f = function (x) { ... } ; では、 函数に名前がありません 。函数を作ったあとで、変数 f に代入してます。 var a = 1, b = "str"; とか書くのと同じ気軽さですね。そして、どちらの方法で函数を定義しても、まったく同じように f(5) と書けば使用することができます。(これは JavaScript の驚くべき特徴です！*4 )

このような「名前のない函数」のことを指して、無名函数と呼ぶことがあります。通常はこの無名函数のことを指してラムダ式と呼ばれます。また注目すべき点として、函数の中で函数を定義することができます。これは C言語しか知らない方には想像もしなかったことかもしれませんし、いままでラムダ式をご存じでなかった方にもやはり驚くべきことかもしれません。僕は驚いた。

ラムダ式と高階函数

「引数 x をとり、3倍した数を返す函数 f を定義せよ」「引数 h, x, y, z をとり、x, y, z, をそれぞれ h で適用した数を合計した数を返す函数 g を定義せよ」

こんな問題について考察してみます。数学の授業っぽい表記だと、こんな感じですね。

$f(x) = 3x$
$g(h,x,y,z) = h(x) + h(y) + h(z)$

λ表記で表すと、こうなります。

$f = \lambda x.\, 3 \times x$
$g = \lambda h.\, \lambda x.\, \lambda y.\, \lambda z.\, (h\,x) + (h\,y) + (h\,z)$

じゃあこれを C言語で書いてみようか… となると別の函数を定義しなければいけなかったり、函数ポインタの出番になったりちょっと面倒なのですが、 JavaScript ではいつでもどこでも、函数の中だろうと外だろうと、そのまま書けば大丈夫です*5。

var f = function(x){ return 3 * x; };
var g = function(h, x, y, z){ return h(x) + h(y) + h(z); };
console.log( g(f, 1, 2, 3) ); //=> 18

このように、変数として函数を受け取る函数のことを高階函数と呼びます。

ひとつ注目して欲しいところがあります。 h, x, y, z と平然と並んでますね。x, y, z は、当然「数」であることが期待されます*6。 h は函数オブジェクトです。 JavaScript の函数は、文字列や整数と同列に並ぶ、値の一種に過ぎません。これも C言語ではないことです*7。

一般化して考へる(mapとreduce)

さて、上記の JavaScript のコードですが、プログラムとして見ると柔軟性にかけるところがあります。

引数が 3つにしか対応してない
- 例: 2つのとき、5つのとき、 70のとき、 10000のとき…
「合計」にしか対応してない
- 「全ての数を掛けたい」場合

引数を 2つにするのに var g2 = function(h, x, y){ return h(x) + h(y); }; と修正するのはたやすいことです。 5つにするために var g5 = function(h, x, y, z, a, b){ return h(x) + h(y) + h(z) + h(a) + h(b); }; とするのもまた簡単なことです。

しかし、 70個の数に対応するためにこのような改造を施すことは、呆れるほどの手間がかかります。まして、 10000個の数に対応するために同じ調子でやってたのでは、正気で居ることの方が困難です。

といふことで、上記の需要を満たすために、もっと柔軟なコードに変更してみませう。

数をいくつでもとれるように配列で受けとる
Array#map メソッドを使用して、配列全体に函数を適用する
Array#reduce メソッドを使用して、配列を畳み込む

var f = function(x){ return 3 * x; };
var h = function(acc, n){ return acc * n; };
var gd = function(h,i,a){ return a.map(h).reduce(i); };
gd(f, h, [1, 2, 3, 4, 5]);

できましたー。

λ計算とJavaScript

…あれ、プログラミングできなくね？と思ったあなたは正解。
ラムダ式の機能そのものには、プログラミングに必要な基本的な機能がほとんどありません。
真偽値もないし、比較級（if文）もないし、画面への出力もない（戻り値だけ）ので、ラムダ式だけでプログラミングはできません。
【SE閑話】文系プログラマが関数型言語（とラムダ式）を理解してみる【初心者向け解説】 | EHACO.net

この一節については、まったくもって擁護不能な、真っ赤な大嘘といふほかありません。このどちらも、 λ計算で表現可能 です。といふことは JavaScript の function 式でも書くことができます。

今回は、条件分岐と真偽値を函数で表現することを考察してみませう。

// これはふつうの JavaScript
var a = true;
var b = false;
(a) ? "foo" : "bar";
(b) ? "foo" : "bar";

// こっちは函数バージョン
// var IF = function(COND, THEN, ELSE) { return ...; };
// var TRUE = function(...) { return ... ; };
// var FALSE = function(...) { return ...; };
var A = TRUE;
var B = FALSE;
IF(A, "foo", "bar"); // => "foo"
IF(B, "foo", "bar"); // => "bar"

雛形はこんな感じになりますよね。

IF 函数は条件、真の場合の値、偽の場合の値、の三つの引数を受け取ります。そして条件が TRUE だったときに真の場合の値、FALSE だったときに偽の場合の値を返すようにしたいです。

単純に書いてみると IF 函数の定義は次のようになります。

var IF = function(COND, THEN, ELSE) { return COND(THEN, ELSE); };

これに適切な TRUE と FALSE を定義してやれば、函数だけで条件分岐が動きます。まだ λ で条件分岐と真偽値を表現できたことが信じられない……?

って向きの方のために、λ式で同じことを書いてみませう。

$true = \lambda x.\, \lambda y.\, x$
$false = \lambda x.\, \lambda y.\, y$
$if = \lambda x.\, \lambda y.\, \lambda z.\, x\,y\,z$

このλ項は上の JavaScript のコードと同じ構造ですので、 λ計算で条件分岐を実現できた ことになりますね。

簡潔な説明では済まなくなるので今回は避けますが、 λ式で再帰、つまりはループを表現することもできます*8。そのような性質と併せて、 λ計算は「チューリング完全」だといふことが證明されてゐます*9。

「チューリング完全」とは「チューリング機械と同じ計算能力を持つ」ことを意味します。チューリング機械とはアラン・チューリングの考案した想像上の計算機械で、入力から答を求めることができる問題であればどんな問題でもプログラミングして、有限時間で計算して答を出すことができます。

たいていのプログラミング言語はチューリング完全性をがありますし、 JavaScript も、 C言語も、 Ruby も Python も、もちろんチューリング完全です。そして、 λ計算もチューリングマシンと等価な計算能力を持つことは、1930-40年代には既に ja.Wp - チャーチ＝チューリングのテーゼとして知られてました。

ここで記事は唐突に結び

ほかにも触れたいことはたくさんあるのですが、ここまでで λ計算の基礎の基礎と、現実のプログラミング言語と λ計算の関連については触れられたかと思ひます。僕自身、ラムダといふ言葉を2011年の1月に知人宅で読んだ β簡約! λカ娘といふ同人誌(ペーパー)で知り、その後半年ほど忘れたままだったところを前職の同僚から F# といふものを知り、実際に手を動かして基礎について学ぶことができたのでした。それまでは「ML? メイリングリストのこと? あたい SGML のことならわかるよ！」と行った次第で、プログラミング言語については無知も甚しいものでした。

そんなこんなで勉強は怠っちゃいけないなー、と思ひつつ日常生活はたてこんでしまふもので、大した勉強ができてるわけでもありません。が、そんな中で何冊か読みかけの本はあるので、参考文献としてこれらを紹介して記事の結びとしたいと思ひます。

これは重要なことですが、僕ははてなダイアリープラスの会員ではないので、この記事経由で本をお求めになっても僕には一円も入りません……。