前提知識

$y = f(x)$
なら、 $f(x)$ が $x+1$ のとき、 x に数 $3$ を入れれば、 $y=4$ になる。

本文

画像貼り付けるのめんどくさくてやる気が出ないが　テキストだけで書いてみる。

では、 x に数ではなく、 関数 を入れたらどうなるだろうか？　そう考えたのが　ラムダ計算　だ。

$f(x)$ はもう使っているので、アルファベット順で次は $g(x)$ という関数があるとしよう。

$y = f(x)$
なら、 $f(x)$ が $x+1$ のとき、 x に数 $g(x)$ を入れれば、 $y=g(x)+1$ になる。

ここで、コンピューター・プログラミングに慣れた方の中には、
$f(x)$ の戻り値（つまり、計算結果）に 数ではなく 関数が残ったまま返ってくる（仮にこれを 消化がゆっくり と呼ぶとしよう）、あるいは 数ではなく 演算子が残ったままの式が返ってくる　ことに違和感を覚えるかもしれない。
だったら便宜的に

$h(x) = g(x)+1$
と決めておけば　$h(x) = f(x)$ と書けるので、 関数が、別の関数（同じ関数でもいいが）を返している という物の見方ができるだろう。

何かい関数？

ここで、
$y = f(x)$ で x が 数 のとき 一階関数 と呼び、
$y = f(x)$ で x が 一階関数 のとき 二階関数 と呼ぶ。

つまり雑に説明すると、以下の説明に出てくる式は間違っているが、
$y = f(g(x))$ のうち $g(x)$ の 消化がゆっくりな気分 で引数に関数を渡すことを 二階関数 と呼んでいる。
$y = f(g(h(x)))$ のうち $g(h(x))$ の 消化がゆっくりな気分 かつ、そのまた $h(x)$ の 消化がゆっくりな気分 で 引数に入れ子の関数を渡すなら 三階関数 だ。

n階関数 のうち $2<=n$ のものを 高階関数 と呼ぶ。 ラムダ計算は 高階関数 を扱う。
また、読み方は こうかいかんすう だが、漢字変換できないので たかしなかんすう と入力すると一発で出てくる。
ここで、

これは 一階関数、高階関数、どっちなの？

$z = g(x)$
$y = f(z)$

と書いてあるとき、もし $g(x)$ は $x * 2$ であり、 $x$ が $3$ であるるなら、

$z = g(3)$
$6 = g(3)$

なのだから、

$y = f(6)$
$7 = f(6)$

だ、ということになってしまうと、これは 一階関数 になってしまう。
コンピューター用語で言うと、 評価してから引数に渡す ということを上記でしてしまった。
そこで、またコンピューター用語で言うと、高階関数とは、 まだ評価せず引数に渡す ということだ。

しつこく言うと、
$6 + 1$ から、演算子（計算の記号）が消えるまで計算する、つまり、式を数に変換することを、 評価 と呼ぶ。
プログラミングでは evaluation （エヴァリュエーション）と呼ぶ。 略して eval( ) みたいな名前の関数を見かけることもある。

で、
評価してから引数に渡すことを 先行評価 (eager evaluation) とか、 正格評価 (strict evaluation) と呼ぶ。
まだ評価せず引数に渡すことを 遅延評価 （lazy evaluation）と呼ぶ。

ラムダ計算でも、プログラミング言語でも、それが 先行評価なのか、遅延評価なのか、見分けが付くように書かなければ
読む人に分からない。
そこで、 遅延評価だと分かるような 回りくどい書き方、 ラムダ式 という書き方がある。

ラムダ式

漢字の「入り」みたいな字だが　λ（ラムダ）というギリシャ文字があって、この文字を使うから ラムダ式と呼ぶ。

プログラム言語の方が分かりやすいので、プログラム言語の ラムダ式の説明を先にする。

y = f( (x)=>{x+1} )

↑ 以上が、 C# を模した ラムダ式 の疑似コードだ。

(x)=>{x+1}

↑ という書き方が、 C# での ラムダ式 だ。
引数が $x$ で、その定義は $x+1$ だ、と定義文が書いてある。
定義文を見て先行評価しようというプログラマーは恐らく いないから、これで 遅延評価 だと見分けが付く。

他にも、 Rust言語では以下のように書く（疑似コード）。

y = |x| x+1

↑ であるから、 コンピューター・プログラム言語では ラムダ式の表し方 は様々で決まりはない。分かればいい。
次に オリジナルの数学でのラムダ式の書き方を見てみよう。

y = λx.x+1

↑ 表し方の違いだけで、ほとんど変わらない。これが遅延評価。

ここで、先行評価との違いを確認しておこう。

x=3
y = λx.x+1

↑ と、上式のように書かれていたら どうするだろうか？

y = λ3.3+1
y = 3+1
y = 4

↑ と、入れてみて、計算してしまうだろうか？ それでは先行評価になる。そこで遅延評価では……。

x=3
y = λx.x+1

↑ 意地でも x には まだ 3 を入れない。 λ の記号を見かけたら、 まだ入れるな ぐらいの注意書きだと思えばいい。
じゃあ、 いつ入れるか だが……。

いつ入れるか

これも後発の コンピューター・プログラム言語の方が読みやすいから、先にプログラム言語の方で説明する。

y = f( (x)=>{x+1} )
y(3)

↑ 以上のように、 $y$ は 高階関数なので、そこに $( )$ を付けてやれば 評価する、と考えればいい。
n階関数が、 n-1階関数になるわけだ。

もしもの話し

じゃあ もし、

y = f( (x)=>{x+1} )
y((x)=>{x+2})

↑ と 再定義 してやったらどうなるんだ！ という疑問だが、 C#言語では x は int型 を入れろ、のように 型が決まっている ので
このような書き方はできないはずだ。
もしできたら かなり エキサイティングでハッスルしてしまうだろう。

逆の言い方をすると、 ラムダ計算は 型が決まっていない 方をオリジナルとする。
コンピューター・プログラム言語の方では そういうのを 関数型プログラミング と呼ぶ。

歴史的には プログラミング言語は、関数型プログラミング言語 は 古くからあったが、
どちらかというと 高階関数を除外 して 型が決まっている プロシージャ型プログラミング言語 として
商業的に普及したという順序がある。
そしてそのあとで、 型が決まっていない（推論型）、 ラムダ計算が使える といった機能が盛り込まれ、先祖返りしている。
これは マシンのスペック（性能）や エディターの利便性 が上がったから、人類には早かったラムダ計算を徐々に扱えるようになったから、
かも知れない。

このようにラムダ計算には、

型がないもの
型があるもの（例えば上述の再定義ができないもの）

に大きく分けられる。

あと忘れていたが

数学（つまりオリジナル）のラムダ計算で 先行評価 を書くにはどうするかだが、
そもそも ラムダ計算 は 遅延評価 なので、全部 遅延評価。先行評価をしたいという文脈でラムダ計算は出てこない。一応、

λx.x+1

↑ を先行評価するには、

(λx.x+1) 3

↑ と 数の 3 をラムダ計算の右側に書いて、

= (λx.x+1) 3
= 3+1
= 4

↑ x は 数の 3 なんだ、と見せることはできる。 これは 3 が 数 なので、評価したように見える、というだけだ。
やってることは 遅延評価。

型が無いラムダ計算（つまり普通のラムダ計算）とは

プログラム言語の方に先に親しんでいると、型とは何か？ についての説明の 風呂敷が広がりすぎるので、
ここでは単に、

数か？
関数か？

↑ の２つを区別することを 型がある と呼んでいるとしよう。 上の２つを区別しなければ 型がない 。
だから、

式1: (λx.x+1) 3
式2: (λx.x+1) (λx.x * 2)

↑ ラムダ計算は、上の 式1、式2 のどちらの書き方でもイケる。
それぞれ 評価してみよう。

式1:
(λx.x+1) 3
= 3+1
= 4

式2:
(λx.x+1) (λx.x * 2)
= (λx.x * 2)+1

↑ となる。式1 の方が計算した気分になり、式2 の方は計算の途中の気分がするが、そこは慣れだ。

さまざまなケース

(λx.(x+2) * x) 3

例えば 引数 x が、定義文本体の中で２回以上出てくることは 普通にある。

(λx.(x+2) * x) 3
= (3+2) * 3
= 5 * 3
= 15

ただの 代入 と考えれば なんということはない。これはラムダ計算では 関数適用 (application) と呼ぶ。

で、ここで 見慣れないケースが出てくるかもしれない。

λx.x x

↑ x x （あいだにスペースがある）を見かけると 掛け算に見えてしまうが、ラムダ計算では 関数適用だ。例えば

(λx.x x) 3

↑ であれば、

3 3

↑ なのだから、声を上げて 9 と言いたくなるが、雑に説明するとこれは本来

(λ_.3) 3

↑ で、 右側の 3 は、左側のラムダ式に入れる引数がないので、
文法エラー 、別の言い方をすると 計算停止 になるのではないだろうか？

また、このブログ記事より厳密な ラムダ計算入門 から例を借りてくると、

(λx.x x) (λx.x x)

↑ 上式の 関数適用 をやってみると、 無限ループ する。では、やってみよう。

(λx.x x) (λx.x x)
= (λx.x x) (λx.x x)

これは 計算停止しない と言えるだろう。

このように、なんだラムダ計算、エラーになるケースがあるじゃないか、と思えるが、
このような異常に思ってしまうケースも含めて ラムダ計算 だ。
型がない から 異常に思ってしまうケース が出てくるのだから、
コンピューター・プログラム言語では 型がある ようにして 異常に思ってしまうケースが出ない ようにするのは　なるほど納得だが、
それも ラムダ計算して分かったから避けれるという、物の見方の 裏返し なだけで、同じものを別の見方をしているだけともとれる。

今どきのプログラム言語の知識でラムダ式を説明すると？

多分、よく見かけるプログラム言語は 型があるラムダ式 なので、
そのままでは 型がないラムダ式 、つまり普通のラムダ式を説明できないが、
雑には説明できるので、雑に説明する。

ラムダ式は、次の３つのものの総称だ。

１つ目の構文ルール

x

↑ x はラムダ式だ。これは、 引数はラムダ式だ ぐらいの意味だが、これでは何のことだか分からないので　もう少し説明に手間をかける。

λx.x

↑ 上式の全体もラムダ式だが、１つ目の構文ルールは、左側の x も ラムダ式だ、と言っている。
例えば ビニール袋にゴミが入っていれば ビニール袋はゴミ袋と名前を変えるが、
x に ラムダ式を入れるんだから x はラムダ式だろ、と言っているのと同じだ。

１つ目の構文ルールは 変数（Variable） と呼ばれる。

２つ目の構文ルール

λx.x

↑ 先に言ったばかりだが、これもラムダ式だ。 見た目で いかにもラムダ式やってる気分 がするのは こいつ。
C#言語の疑似コードと比べてみよう。

λx.x
(x)=>{x}

λx.0
(x)=>{0}

λx.y
(x)=>{y}

↑ 中には違和感を覚えるものもあるかも知れないが、わたしが飽きてなくてヒマなら、のちのち説明する。

２つ目の構文ルールは ラムダ抽象（Abstraction） と呼ばれる。
プログラム言語ではフランクに 名無し関数 とか呼ばれることが多い。

３つ目の構文ルール

$e_1$ $e_2$

↑ $e_1$ と $e_2$ の間にスペースが開いてある。 e はラムダ計算だ。 つまり ラムダ計算を スペースを空けて並べたものも ラムダ計算だ。
そのとき、先頭から１つ目のラムダ計算に、先頭から２つ目のラムダ計算を入れる、という手順の決まりがある。
つまり、

$e_1$ $e_2$ $e_3$ $e_4$

↑ と書いてあれば、

((($e_1$ $e_2$) $e_3$) $e_4$)

の順に 評価する。 これは 左結合 と呼ぶ。
例えば、

λx.x λx.x+1 λx.x * 2 λx.x-3

↑ を評価すると、

λx.x λx.x+1 λx.x * 2 λx.x-3
= λx.x+1 λx.x * 2 λx.x-3
= λx.x * 2+1 λx.x-3
= λx.(x-3) * 2+1

↑ のように変形する。

３つ目の構文ルールは 関数適用（Application） と呼ばれる。
プログラム言語で似ているものと言うと、

y = f( (x)=>{x+1} )
y(3)

↑ という疑似コードでいう所の y(3) に当たる部分かと思う。

a = f( (x)=>{x} )
b = f( (x)=>{x+1} )
c = f( (x)=>{x*2} )
d = f( (x)=>{x-3} )

a(b(c(d(4))))

↑ よしできた。見事に左結合。 先行評価では暗算で 3 になると思う。
遅延評価では、 "a(b(c(d(4))))" の形のまま保っていると考えてほしい。つまり考え方は プログラムのソースコードに似ている。

だんだんプログラム言語に似てくる

ラムダ計算 の基本ルールを覚えていくと、だんだん これ プログラム言語の作り方なんじゃないか、と思えてくる。
わたしが サボりたくなったら 記事に続きを書く。

（書きかけ）