ラムダ計算第1回: ラムダ計算を楽しもう！

# 今回のテーマ：ラムダ計算を楽しもう！

HapInSアドベントカレンダー2023、2日目の記事を担当するh_shimakawaです。

私の趣味はプログラミング言語自作です。 その趣味の一環で計算機理論の"ラムダ計算"について調べてみたので連載で紹介しようと思います。 最初のうちは紙とペンでできるので皆さんも取り組んでみてはどうでしょう？

第１回　真偽値と数値とたし算、かけ算

はじめに

皆さんはコンピュータやプログラミングの本質はなんだと思いますか？

よく言われるのは「コンピュータは 0 と 1 でできている」「プログラムは順序・分岐・繰り返ししかない」って考えている人が多いのではないでしょうか？

確かにそれはコンピュータやプログラミングの理解として多分あっています。

実際のコンピュータが電気の ON/OFF で表現されるため、0 と 1 で構成されるというのは間違いのない事実ですし、 プログラミングは「順序・分岐・繰り返し」で構成されているように見えます。

ですが、本当に「0 と 1」あるいは「順序・分岐・繰り返し」がないとプログラムが書けないのでしょうか？

そんなことはありません、他の要素でもプログラミングは可能です。 たとえば「ラムダ関数」だけでもプログラミングができます。 そしてラムダ関数で構築した計算理論を「ラムダ計算」といいます。

本記事ではラムダ計算の機能を一つ一つ作り上げながら、計算可能（チューリング等価）であることを証明します。

難易度

Level: 最初は簡単

置き去りにならないようしっかりついてきてください。

対象の読者

• 関数型言語の根底にあるラムダ計算に興味のある人
• 関数型言語の源流を見てみたい人
• もちろん上記に当てはまらない人にもおすすめです

目標

このテーマでの目標は、ラムダ関数の持つ能力だけで型なしラムダ計算を行います。

最終的にはチューリングマシンを実装して、ラムダ計算がチューリング等価であることを証明します。

現在の予定では以下のように進めます。

• ラムダ計算の基礎と真偽値、数値とたし算、かけ算
• ひき算とわり算
• リスト構造とリストの処理
• 無限に長いテープと評価器

用意するもの

• 推奨: 紙とペン
• なければ: パソコン

ラムダ計算とは

型無しラムダ計算とは

• この記事では型無しラムダ計算を扱います。
• 関数計算の基本的な理論体系で計算機科学などの基礎となっています。

ラムダ計算の記法

ラムダ計算は通常、その名の通り λ(ラムダ)を使った表記をします。

λaf.fa
// または
λa.λf.fa

この表記を見て、何が書いてあるか分からないと感じる人も多いでしょう。 これは Javascript だと以下のように表現されます。

a => f => f(a)
// または
a => {
  return f => {
    return f(a)
  }
}

本記事では、読者が簡単にプログラムを実行できるように、表記は JavaScript に統一しています。

ラムダ計算の構成要素

ラムダ計算の式は以下の３種類から構成されます。ついでに、ラムダ計算にはどのような要素が存在しないのかも明記しておきます。

ラムダ計算にある機能

項目	説明	Javascript でのコード例
変数	普通のプログラミングと同様に値を参照できます。再代入（上書き）はできません。	aやf
抽象	x => e の形を持ち、変数xとラムダ計算の式eから構成されます。これは、「引数 x を受け取り、式 e の結果を返す関数」を表します。	a => f => f(a)
適用	形式f(a)のように２つのラムダ計算の式fとeから構成されます。上記は「fと評価される関数にeと評価される値を引数として適用する（呼び出す）こと」を表現します。	f(a)

ラムダ計算に存在しない機能

項目	対策
真偽値、数値、文字列	全て自分で作る必要があります。
配列やリスト、構造体やクラス	全て自分で作る必要があります。
上記を操作するための命令(and,or+,-,new)	全て自分で作る必要があります。
if や for/while などの制御構文	全て自分で作る必要があります。

もうちょっと説明すると、ラムダ計算において、「値」は関数(抽象)しか取ることができません。 つまりf(a)はfもaも関数で、f(a)の計算結果も当然関数です。

カリー化

普通のプログラミング言語とは異なり、ラムダ計算にはもう一つ制約があります。 それは、すべての関数が一つの引数しか取らない、というものです。

最初は少し驚くかもしれませんが、これは大きな問題ではありません。 複数の引数を必要とする場合は、f(a)(b)(c)のように引数を一つずつ与えることで対応します。

以下で Javascript で記述したカリー化のサンプルコードです。 カリー化を使うことで、記述のシンプル化や引数の部分適用など、便利になる場面があります。

const ADD = a => b => a+b // 2つ引数を取る関数を定義
const ADD_TWO = ADD(2) // 引数'a'に2を先に与えた関数を生成
console.log(ADD(2)(3)) // 5  カリー化せずに2 + 3を実行
console.log(ADD_TWO(3)) // 5 すでに2を引数に持つ関数に3を適用
console.log(ADD_TWO(10)) // 12 すでに2を引数に持つ関数に10を適用

真偽値と if

では、ラムダ計算をやってみよう。 TRUE,FALSE,IF は以下のように関数で表すことができます。 ソースコードは通常の Javascript を使用しています。 手書きで計算結果を確認したうえで、 javascript として実行して動作を確認することもできます。

// 定義
const TRUE = x => y => x;
const FALSE = x => y => y;
const IF = c => x => y => c(x)(y);
// 説明用コード
const TO_BOOLEAN = b => b(true)(false);
console.log(TO_BOOLEAN(TRUE)); // true
console.log(IF(TRUE)('yes')('no')); // "yes"
console.log(IF(FALSE)('yes')('no')); // "no"

簡単ですね。 TRUE と FALSE は、それぞれ必要とする引数を返すだけの関数です。

IF は真偽値 c を引数にとり、それに基づいて必要な処理を行います。

ここでソースコードの読み方について注意してほしいことがあります。

ここのコードでは真に当たるのがx=>y=>xであると書いてありますが、const TRUE =の部分はラムダ計算に必須ではありません。

これは Javascript で実行するために、便宜上変数に格納しているだけです。

同様に、説明用コードもラムダ計算の機能を人間にわかりやすい形に表現するために記述したもので、ラムダ計算自体には必須ではありません。 （なので、説明用コードには文字列や数値が登場しますがそこは切り分けて考えてください。）

数値

基点 n に対して、操作 p を m 回繰り返し適用することで数値 m を表現できます。

// 定義
const ZERO = p => n => n;
const ONE = p => n => p(n);
const TWO = p => n => p(p(n));
const THREE = p => n => p(p(p(n)));
const FOUR = p => n => p(p(p(p(n))));
const FIVE = p => n => p(p(p(p(p(n)))));
const SIX = p => n => p(p(p(p(p(p(n))))));
const SEVEN = p => n => p(p(p(p(p(p(p(n)))))));
// 説明用コード
const TO_INT = x => x((n) => n + 1)(0);
console.log(TO_INT(TWO)); // 2

え、こんなんでいいの？って気がしますね！ また、実は ZERO は FALSE と同じ関数であるのもポイントです。

0 との比較

数値が0と等しいかという判定は、プログラミングにおいて必要な処理ですよね！

// 定義
const IS_ZERO = n => n(x => FALSE)(TRUE);
// 説明用コード
console.log(TO_BOOLEAN(IS_ZERO(ZERO))); // TRUE
console.log(TO_BOOLEAN(IS_ZERO(ONE))); // FALSE
console.log(TO_BOOLEAN(IS_ZERO(TWO))); // FALSE

もう少し丁寧に説明します。

• ZERO のとき
  • IS_ZERO(ZERO)
  • (n=>n(x=>x(FALSE))(TRUE))(ZERO) // IS_ZERO を展開
  • ZERO(x=>x(FALSE))(TRUE) // n は ZERO
  • TRUE // ZERO は FALSE と同じで第２引数を返す
• TWO のとき
  • IS_ZERO(ZERO)
  • (n=>n(x=>x(FALSE))(TRUE))(TWO) // IS_ZERO を展開
  • TWO(x=>x(FALSE))(TRUE) // n は TWO
  • (p=>n=>p(p(n)))(x=>x(FALSE))(TRUE) // TWO を展開
  • (n=>(x=>x(FALSE))*1(n)))(TRUE) // p は x=>x(FALSE)
  • (x=>x(FALSE))*2(TRUE)) // n は TRUE
  • (x=>x(FALSE))(TRUE(FALSE)) // (x=>x(FALSE))(TRUE)において、x は TRUE
  • TRUE(FALSE)(FALSE) // x は TRUE
  • FALSE //TRUE は第 1 引数を返す

これを手書きで行うと、大きな達成感を感じることができます。 ぜひ手書きで計算してみてください。

数値演算

INC

基礎的な計算力を得るために INC(increment,+1)を実装する必要があります。

// 定義
const INC = n => p => x => p(n(p)(x));
// 確認用コード
console.log(TO_INT(INC(TWO))); // 3

パッと見で理解するのは少し難しくなってきたかもしれませんが、問題ありません。 上記の INC(TWO)を考えてみましょう。

変数が他と重複しないように、TWO を a => b => a(a(b)) と書き換えて考えます。

INC(TWO)
= (n => p => x => p(n(p))(x))(TWO)  // INCを展開
= p => x => p(TWO(p)(x))  // nにTWOを代入
= p => x => p(a=>b=>a(a(b))(p)(x)) // TWOはa => b => a(a(b))
= p => x => p(b => p(p(b))(x)) // aにpを代入
= p => x => p(p(p(x))) // bにxを代入
= THREE // xにpを３回適用するのはまさしくTHREEですね。

インクリメント（+1）を行うだけでも、これだけの手間がかかるんですね！

たし算とかけ算

INC を使うと、たし算とかけ算ができるようになります。 ついでに累乗も定義できます。

// 定義
const ADD = m => n => n(INC)(m); // m+n
const MUL = m => n => n(ADD(m))(ZERO); // m*n
const POW = m => n => n(MUL(m))(ONE); // m^n
// 確認用コード
console.log(TO_INT(ADD(TWO)(THREE))); // 5
console.log(TO_INT(MUL(TWO)(THREE))); // 6
console.log(TO_INT(POW(TWO)(THREE))); // 8

ADD の説明をします。 残る二つは同じように展開できます。

ADD(TWO)(THREE)
= (m=>n=>n(INC)(m))(TWO)(THREE) // ADDを展開
= THREE(INC)(TWO)// mはTWO、nはTHREE
= (a=>b=>a(a(a(b))))(INC)(TWO) // THREEを展開
= INC(INC(INC(TWO))) // aはINC、bはTWO
= FIVE // ここでは定義していないですが、これは FIVE に相当します

ADD,MUL,POW は全て、回数(計算)(起点)の同じ形をしていることに気が付きましたか？

つまり、次のように考えることができますね。

ADDは、mに(+1)をn回繰り返す
MULは、0に(+m)をn回繰り返す
POWは、1に(*m)をn回繰り返す

展開してみよう！

先ほど話しましたが、ラムダ計算においてconst xxx =で変数に格納する必要はありません。 試しに今回定義した式の中で一番複雑な関数である POW を展開してみましょう。

let POW = m=>n=>n(MUL(m))(ONE)
// ONE を p=>x=>p(x)に展開
POW = m=>n=>n(MUL(m))(p=>x=>p(x))
// MUL を m=>n=>n(ADD(m))(ZERO)に展開
POW = m=>n=>n((m=>n=>n(ADD(m))(ZERO))(m))(p=>x=>p(x));
// ZERO を p=>x=>xに展開
POW = m=>n=>n((m=>n=>n(ADD(m))(p=>x=>x))(m))(p=>x=>p(x));
// ADD を m=>n=>n(INC)(m)に展開
POW = m=>n=>n((m=>n=>n((m=>n=>n(INC)(m))(m))(p=>x=>x))(m))(p=>x=>p(x));
// INC を n=>p=>x=>p(n(p)(x))に展開
POW = m=>n=>n((m=>n=>n((m=>n=>n(n=>p=>x=>p(n(p)(x)))(m))(m))(p=>x=>x))(m))(p=>x=>p(x));

// ついでに出力用関数TO_INTと引数TWO,THREEも付け加える
// TO_INT(POW(TWO)(THREE))を一気に展開して表示する
console.log((p=>p((n)=>n+1)(0))((m=>n=>n((m=>n=>n((m=>n=>n(n=>p=>x=>p(n(p)(x)))(m))(m))(p=>x=>x))(m))(p=>x=>p(x)))(p=>x=>p(p(x)))(p=>x=>p(p(p(x))))))

何かとてつもないものが生成されました。 流石にこの式は手書きで計算しなくてもいいです。

javascript として実行してみましょう。無事に 8 が出力されたかと思います。

ちょっと感動しますね！

今回はここまで

ラムダ計算の概要から、真偽値と if、数値とたし算かけ算までできるようになりました。

チューリング等価な性能を得るためには、まだまだ実装しないといけない機能がありますが、 何となく計算可能な気がしてきますよね。

次回は引き算と割り算を取り上げます。

ところでどうしてたし算やかけ算と一緒に登場しなかったのでしょうか？

それはたし算かけ算よりずっと難しいからです。

もし余裕があるなら、次回の掲載までに DEC(decrement, -1)を考えてみてください。 これを自力で解くことができたらすごいと思います。（少なくとも私には無理でした。）

*1:x=>x(FALSE

*2:x=>x(FALSE