ラムダ計算１：ラムダ計算をざっくりと理解する

最近lispを勉強しているのですが、やっぱり数学的な背景についてもちょっと勉強しておきたいなぁ、、と思いました。
ということで、ラムダ計算についてまとめました。今回は入門編で、厳密な定義は置いておいてとりあえず具体例を用いて初歩的な用語・概念を一通り確認して、式をいじれるようになることが目的です。

目標

ラムダ計算ってなんぞ、という人がラムダ計算をざっくりと説明できるようになる
プログラムの中でラムダ式を使ってみる

ラムダ計算

背後にある計算モデル

コンピュータは計算を行うことで処理を行います。この計算機における計算の考え方については、３つのモデルがあります。命令型モデル、関数型モデル、論理型モデルです。lispなどの関数型言語（lispは純粋な関数型言語というわけではありませんが...）の基礎づけとなっているのはこのうちの関数型モデルです。関数型モデルにおける計算とは、一言で言えば、関数を呼び出すことによって値を次々と得ていくことです。
関数型モデルにおける実際の計算を行うのが、ラムダ計算（ラムダ算法）と呼ばれるものです。今回の主題ですね。

ラムダ式の導入

ラムダ計算における計算とは、関数を適用することによって値を得ることです。ラムダ計算のために使われる記法がラムダ式です。ラムダ式は、とりあえず関数の名前を取り去ったものと考えれば良いでしょう。
例えば、 $f(x) = 2x + 1$ という関数があったとします。これを表現するラムダ式は $\lambda x. 2 x + 1$ となり、関数の名前（ここではf）が取り除かれています。

わざわざラムダ式を使うのは次の理由からです。 $f(x)$ の表現では、これが関数の定義なのか、xという値に関数fを適用したのか判別できません。ラムダ計算では、関数の引数に何らかの値を与えることを適用または関数適用と言います。例えば、上の関数を３に適用する場合は、 $( \lambda x. 2 x + 1) \; 3$ のように表現します。ラムダ式を使うと、関数の定義なのか、適用なのかがその形からはっきりとみて取れます。

このように、 $\lambda x. 2 x + 1$ のような関数の表現は、関数の名前を除き本質のみを取り出した関数の定義そのものであるということで、ラムダ抽象や関数抽象と呼ばれます。関数において重要なのはその内部の処理であって、名前ではありません。

ラムダ項

ラムダ計算における式の構成要素がラムダ項です。ラムダ項には変数、適用、抽象、があります。適用、抽象は先ほど出てきましたね。
ラムダ項は３つの規則によって構成することができます。

1. 変数xはラムダ項。
2. ラムダ項M, Nに対して (M N) はラムダ項。この形のラムダ項を適用（ラムダ適用）という。
3. ラムダ項M、変数xに対して $\lambda x. M$ はラムダ項。この形のラムダ項を抽象（ラムダ抽象、関数抽象」）という。

変数はx, y, zなどというやつです。上の定義よりも表現力は劣りますが、とりあえず今の段階では、適用については $(\lambda x. M) \; y$ という形を覚えておけば良いかと思います。
ラムダ項を再帰的に組み合わせることでラムダ項が作られます。ラムダ式とラムダ項という言葉は同じ使われ方をしているようです。

ところで、具体的な数（整数とか）がラムダ項に含まれていないことに気が付いたかもしれません。実は、これらは上の３つのラムダ項によって構成することができます。ちょっと難しいのでこの記事では触れません。

関数の定義に使われる引数を仮引数、関数を使用するときに関数に与えられる引数を実引数と言います。先ほども触れましたが、ラムダ計算においては仮引数と実引数の区別がはっきりとつけられるようになります。
例えば、ラムダ抽象 $\lambda x. x + 1$ において、xは仮引数です。ラムダ適用 $(\lambda x. x + 1) \; 3$ において、3が実引数です。

先ほど、関数の名前は重要でないと述べましたが、変数の名前も同様です。 $\lambda x. x$ を見てください。xがyになろうがzになろうが、処理は同じです。次のように変数の名前を入れ替えることができます。

$(\lambda x y z. x y z) \; x$
$\rightarrow (\lambda y z x. y z x) \; y$
$\rightarrow (\lambda z y x. z y x) \; z$

省略の記法

例えば、高階関数 $\lambda x. (\lambda y. x))$ は次と同じ意味です。
$\lambda x. \lambda y. x$
$\lambda xy. x$

上の例はラムダ抽象の省略でした。次はラムダ適用です。
例えば、 $((\lambda x y. x) \; a) \; b$ は、関数 $\lambda x y. \; x$ をaに適用したものをbに適用しています。これは次のように書くことができます。
$(\lambda x y. x) \; a \; b$

このようにかっこを省略します。

束縛変数と自由変数

ラムダ抽象 $\lambda x. x + y$ を考えてみます。変数xは引数に使われていますが、yは使われていません。この時、xを束縛変数、yを自由変数と言います。

簡約

ここまで、記法についてやってきました。では、実際に計算するにはどうするのでしょうか。例を見てみます。

$(\lambda x. x + 1) \; 1$
$\rightarrow 1 + 1$
$\rightarrow 2$

このように、関数の仮引数が実引数に置換されて計算が進みます。置換を繰り返して計算を進めることを簡約と言います。和の演算はラムダ項の規則には出てこないので、本来はちゃんと定義から構成してあげなければならないのですが、細かいことは気にしない方針なので、気にしないことにします。
もう少し複雑な例を見てみます。

$(\lambda x y. x) \; a$
$\rightarrow \lambda y. a$

これは少しわかりにくいかもしれませんが、 $(\lambda x y. x) \; a$ が $(\lambda x. (\lambda y. x)) \; a$ に等しいことを思い出せば、a を渡すと、まず仮引数 x が実引数 a に置換されて、{y を渡すと a を返す関数}が返されることがわかります。あるいは、仮引数x, y のうち、x が実引数 a に置換され、y が残ったと考える方がわかりやすいかもしれません。
これと同じように考えると、

$(\lambda x y. x) \; a \; b$
$\rightarrow (\lambda y. a) \; b$
$\rightarrow a$

と簡約できますね。

実際にプログラミング言語ではラムダ式をどう扱うか？

使い方は簡単です。たくさんの言語でラムダ式を使うことができますが、ここではpython、common lispでの使い方を紹介します。やっぱらラムダ式はlispで書いてみたいなってのと、あとはlispはわからんって人が多そうなので、pythonでもやってみようと思います。僕はpythonでラムダ式を使うのは初めてなのですが、まあpythonならシンプルに書けそう、という理由で選びました。

python の例

基本構文：

lambda (引数) : 処理(戻り値)

例：リストの各要素に２を加える関数

def plus2(lst):
    return list(map(lambda x: x + 2, lst))


print(plus2([1, 2, 3]))

実行結果：

[3, 4, 5]

map関数を使っています。第１引数に関数（ここではラムダ式）、第２引数にリストを渡して、リストの各要素に対して関数を適用します。返り値がmapオブジェクトなのでリストに変換してやります。

common lisp の例

lambdaコマンドを使います。
基本構文：

(lambda (引数)
  処理)

例：リストの各要素の２を加える関数

(defun plus2 (lst)
  (mapcar (lambda (x)
            (+ x 2))
          lst))

(princ (plus2 '(1 2 3)))

実行結果：

(3 4 5)

pythonの例と同じ処理をしています。

まとめ

今回はラムダ計算に触れることをしました。なんとなく感じは掴めたんじゃないかなと思います。
おいおいもっと踏み込んだ内容についてもまとめてみたいです。

参考

京都大学講義資料　http://www.kurims.kyoto-u.ac.jp/~cs/cs2015_katsumata150514.pdf
立川察理（2016）「関数型プログラミングの基礎ー JavaScriptを使って学ぶ」長瀬嘉秀監修株式会社莉テレコム
コンラッド・バルスキ（2013）「Land of Lisp」川合史郎訳オライリー・ジャパン
 柴田淳（2017）「みんなのPython」SBクリエイティブ株式会社

プログラミング原人の進化論

オレ　プログラミング　ベンキョウ　スル。マナンダ　コト　カク。