自然数の足し算と引き算だけの関数型言語を作った

クソアプリ Advent Calender 2021 の 25 日目です。空いていたので飛び入り参加します。

---

タイトルを見ても よくわからないと思うので、まずは Hello World を……

```
-+.1.9+8..0..-+.1.-+.1.+22+5..0...1..-+.1.-+.1.26.+3..0..-+.1.-+.1.26.+3..0..-+
.1.-+.1.+26..1.+3..0..-+.1.-+.1.+26..8..-+.1.-+.1.52..-+.1.-+.1.-72..9..-+.1.-+
.1.+26..1.+3..0..-+.1.-+.1.+26..2.+3..0..-+.1.-+.1.26.+3..0..-+.1.-+.1.22+5..0.
..-+.1.-+.1.+52..1..-+.1.-+.1.5+2..0..-+.1.-+.1.44..0..........................
...
```

……余計にわからなくなりましたね。

この言語は、Worse という名前のプログラミング言語です。「プログラミング言語」を名乗るからには、もちろん**チューリング完全**ではあるのですが、仕様が極端に小さいため実用性は皆無です [^1]。

https://github.com/unsigned-wrong-wrong-int/worse-lang

同系統の言語として、Lazy K, Unlambda, Iota/Jot/Zot などの難解プログラミング言語 (esolang) があります。

# TL;DR

Worse では、**全てが関数**です。足し算も引き算も、自然数までもが関数で表されます。それらを上手く組み合わせることによって、プログラムを記述することができます。

# 関数で自然数を表す

自然数は以下のように表されます。このように定義された自然数を**チャーチ数**といいます [^2]。

```
                       # JavaScript 風に書くと……
0 = λf x.x             # f => x => x
1 = λf x.f x           # f => x => f(x)
2 = λf x.f (f x)       # f => x => f(f(x))
3 = λf x.f (f (f x))   # f => x => f(f(f(x)))
:
```

見てわかるとおり、関数 `f` を適用する回数で数値を表しています。

## 足し算

チャーチ数の足し算は次のように定義できます [^3]。

```
PLUS = λm n f x.m f (n f x)   # m => n => f => x => m(f)(n(f)(x))
```

実際に計算して確認してみましょう。

```
PLUS 2 3
= (λm n f x.m f (n f x)) (λf x.f (f x)) (λf x.f (f (f x)))
   ↓ m を (λf₀ x₀.f₀ (f₀ x₀)) に置き換え (添え字の ₀ は名前を区別するため)
= (λn f x.(λf₀ x₀.f₀ (f₀ x₀)) f (n f x)) (λf x.f (f (f x)))
   ↓ n を (λf₁ x₁.f₁ (f₁ (f₁ x₁))) に、以下同様に引数を置換
= λf x.(λf₀ x₀.f₀ (f₀ x₀)) f ((λf₁ x₁.f₁ (f₁ (f₁ x₁))) f x)
= λf x.(λx₀.f (f x₀)) ((λf₁ x₁.f₁ (f₁ (f₁ x₁))) f x)
= λf x.f (f ((λf₁ x₁.f₁ (f₁ (f₁ x₁))) f x))
= λf x.f (f ((λx₁.f (f (f x₁))) x))
= λf x.f (f (f (f (f x))))
= 5
```

ちゃんと 2 + 3 が 5 になりましたね。他の数でも同じように計算できて、0 を含む計算も正しい答えが出ます。興味のある方は試してみてください。

改めて見返してみると、`m f (n f x)` は「`f` を `n` 回適用したもの」に、さらに `f` を `m` 回適用している、と読めます。合計で `m + n` 回になるのも納得できます。

## 引き算

足し算の関数はシンプルでしたが、引き算は一筋縄ではいきません。まずは「一つ前の数」を返す `PRED` [^4] 関数が必要になります。`PRED` を使うと、引き算の関数は次のように書けます。

```
MINUS = λm n.n PRED m             # m => n => n(PRED)(m)
```

(`m` と `n` の順番に注意してください。)

これは、`m` に対して `PRED` を `n` 回適用する、つまり `m` の `n` 個前の数 `m - n` を求める関数です。

λ を使った記法にも慣れてきたと思うので、以下 JavaScript 風の注釈は省きます。

さて、`PRED` 関数ですが、少し複雑な定義になります [^3]。

```
PRED = λn f x.n (λg h.h (g f)) (λu.x) (λu.u)
```

記事の長さの都合上説明は割愛します。([Wikipedia 英語版](https://en.wikipedia.org/wiki/Church_encoding#Derivation_of_predecessor_function) に詳しい解説があります。)

これも試してみましょう。

```
PRED 3
= (λn f x.n (λg h.h (g f)) (λu.x) (λu.u)) (λf x.f (f (f x)))
= λf x.(λf₀ x₀.f₀ (f₀ (f₀ x₀))) (λg h.h (g f)) (λu.x) (λu.u)
= λf x.(λx₀.(λg h.h (g f)) ((λg h.h (g f)) ((λg h.h (g f)) x₀))) (λu.x) (λu.u)
= λf x.(λx₀.(λg h.h (g f)) ((λg h.h (g f)) (λh.h (x₀ f)))) (λu.x) (λu.u)
= λf x.(λx₀.(λg h.h (g f)) (λh.h ((λh₀.h₀ (x₀ f)) f))) (λu.x) (λu.u)
= λf x.(λx₀.(λg h.h (g f)) (λh.h (f (x₀ f)))) (λu.x) (λu.u)
= λf x.(λx₀.λh.h ((λh₁.h₁ (f (x₀ f))) f)) (λu.x) (λu.u)
= λf x.(λx₀.λh.h (f (f (x₀ f)))) (λu.x) (λu.u)
= λf x.(λh.h (f (f ((λu.x) f)))) (λu.u)
                    ^^^^^^^^ ここで f が一つ消えて x になる
= λf x.(λh.h (f (f x))) (λu.u)
= λf x.(λu.u) (f (f x))
= λf x.f (f x)
= 2
```

「0 の前の数」は便宜上 0 として扱われます [^5]。

```
PRED 0
= (λn f x.n (λg h.h (g f)) (λu.x) (λu.u)) (λf x.x)
= λf x.(λf₀ x₀.x₀) (λg h.h (g f)) (λu.x) (λu.u)
= λf x.(λx₀.x₀) (λu.x) (λu.u)
= λf x.(λu.x) (λu.u)
= λf x.x
= 0
```

したがって、`MINUS m n` は `m` が `n` 以下の場合常に 0 になります。

## 掛け算・べき乗

普通の自然数では引き算よりも掛け算の方が難易度が高いですが、チャーチ数の掛け算は比較的単純です。

```
MULT = λm n.m (PLUS n) 0
または
MULT = λm n f x.m (n f) x
```

上の定義では、0 に `m` 回 `PLUS n` を適用しています。一方、下の定義は、「`f` を `n` 回適用する関数」を さらに `m` 回適用します。どちらも合計で `m * n` になります。

べき乗に至っては、もっとシンプルです。

```
EXP = λm n.n m
```

これも、`EXP 2 3` (つまり `(λf x.f (f (f x))) (λf x.f (f x))`) などを計算してみればわかると思います。

さて、ここで少しだけ触れておきますが、割り算は引き算よりも かなり複雑です。([Wikipedia 英語版](https://en.wikipedia.org/wiki/Church_encoding#Division)) これを説明するだけで一つの記事になりそうです。

# 論理値

`TRUE`/`FALSE` も関数で表現することができます。

```
TRUE  = λa b.a
FALSE = λa b.b
```

1 つ目の引数を返すのが `TRUE`、2 つ目の引数を返すのが `FALSE` です。(`FALSE` の定義はチャーチ数の 0 と同じです。)

`AND`/`OR`/`NOT` は以下のように定義されます [^3]。

```
AND = λp q.p q p
OR  = λp q.p p q
NOT = λp a b.p b a
```

それぞれに `TRUE`/`FALSE` を当てはめてみると ちゃんと動作しているのが確認できると思います。

## 条件分岐

上の `TRUE`/`FALSE` は、実はそのまま条件分岐に使えます。

```
x (TRUE の場合) (FALSE の場合)   # if (x) { ... } else { ... }

例: TRUE なら PLUS 2 5、FALSE なら PRED 5
TRUE  (PLUS 2) PRED 5 = 7
FALSE (PLUS 2) PRED 5 = 4
```

引数の一方が返され、もう一方は破棄されるので、このような振る舞いになります。

## 述語

論理値を返す関数を述語 (predicate) といいます。

特によく使われるのはチャーチ数が 0 かどうかを判定する関数 `IS_ZERO` です。0 のときだけ `TRUE` が、他は `FALSE` が返されます。

```
IS_ZERO = λn.n (λx.FALSE) TRUE
```

`MINUS m n` の結果が `m` が `n` 以下の場合 0 になることを利用すれば、`IS_ZERO` と組み合わせて大小比較もできます。(これも述語です。)

```
LTEQ m n = IS_ZERO (MINUS m n)
```

# ペア

値のペアも、もちろん関数で表せます。これは LISP の cons に似ていて、リストを作るときにも便利です。

```
PAIR   = λx y f.f x y

例:
PAIR 2 TRUE = λf.f 2 TRUE
```

ペアの要素は、`TRUE`/`FALSE` を引数にすると取り出すことができます。

```
FIRST  = λp.p TRUE
SECOND = λp.p FALSE

例:
FIRST  (λf.f 2 TRUE) = 2
SECOND (λf.f 2 TRUE) = TRUE
```

# 再帰

繰り返し処理をしたい場合、反復の回数が固定ならチャーチ数を使うことができます。

```
例: 5 に 3 回 2 を足す
3 (PLUS 2) 5
```

そうでない場合は、**不動点コンビネータ**と呼ばれる関数を利用する必要があります。不動点コンビネータは、ざっくり言うと、再帰を可能にするための関数です。

`λx.x` のような名前を持たない関数は、自分自身を参照できないので、普通には再帰できません。`λf x.f x` のようにして、外から受け取った引数 `f` を再帰に使います。この `f` に適当な値を提供するのが不動点コンビネータです。

不動点コンビネータのうち、最もよく知られているのが Y コンビネータです。

```
Y = λf.(λx.f (x x)) (λx.f (x x))
```

これを使えば、再帰関数を書くことができます。

```
Y (λf x.PAIR x (f (PRED x))) 5
= (λf.(λx.f (x x)) (λx.f (x x))) (λf x.PAIR x (f (PRED x))) 5
= (λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) (λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) 5
= (λf x.PAIR x (f (PRED x))) ((λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) (λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀))) 5
= PAIR 5 ((λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) (λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) (PRED 5))
= PAIR 5 ((λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) (λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) 4)
= ...
= PAIR 5 (PAIR 4 ((λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) (λx₀.(λf x.PAIR x (f (PRED x))) (x₀ x₀)) 3))
= ...
= PAIR 5 (PAIR 4 (PAIR 3 (PAIR 2 ...)))
= ...
```

上の例では無限ループになりますが、条件分岐を利用して任意のタイミングでループを止めることができます [^6]。

# SKI コンビネータ

ここまでは関数**で**プログラムを表現するための基本事項を挙げてきました。ここからは一転して、関数**の**記述方法について話したいと思います。

これまでに出てきた `λ` を使った関数は、全て引数を使って関数の本体が記述されています。それが普通といえば普通なのですが、そうしない表現方法もあるのです。

具体的には、何個かの予め定義された関数だけを組み合わせて、`λ` を使わずに、あらゆる関数を記述します。その一例が、SKI コンビネータ計算です。名前の通り S と K と I という 3 つの関数 (コンビネータ) からなります。

```
S = λx y z.x z (y z)
K = λx y.x
I = λx.x
```

SKI コンビネータ計算はチューリング完全である、つまり、あらゆる関数 [^7] を構成できるということが知られています。

```
例: Y コンビネータ
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
```

実際には I は `S K K` に置き換え可能なので、S と K があればどんな関数でも書くことができます。

ちなみに、この後使おうと思っているので紹介しますが、関数の定義に次のような記法を使うことがあります。(`λ` を使ったものと意味は同じです。)

```
S x y z = x z (y z)
K x y   = x
I x     = x
```

# 足し算と引き算のチューリング完全性

さて、ここからが本題です。チャーチ数の足し算と引き算の関数を再掲します。

```
PLUS  = λm n f x.m f (n f x)
MINUS = λm n.n PRED m
PRED  = λn f x.n (λg h.h (g f)) (λu.x) (λu.u)
```

少し表記を変えて、以下のように定義します。(内容は同じであることが確認できると思います。)

```
+ m n f x = m f (n f x)
- m n     = n P m
P n f x   = n (Q f) (K x) I
Q f g h   = h (g f)
K x y     = x
I x       = x
```

`λ` を無くしておくことで、計算途中の式が すっきりするという利点があります。

## 下準備

まず、次の計算を考えてみましょう。

```
- - - x y
= - P - x y
= - P P x y
= P P P x y
= P (Q P) (K x) I y
= Q P (Q (K x)) (K I) I y
= K I (Q (K x) P) I y
= I I y
= I y
= y
```

`- - - x y` の結果が `y` になることから、`- - -` は `λx y.y` つまりチャーチ数の 0 に等しいということがわかります。この関数は、K コンビネータの 2 つの引数を入れ替えたもの、という見方もできます。これを K′ と呼ぶことにします。

```
K′ = - - -
K′ x y = y
```

K′ から、I コンビネータを作ることができます。初めの引数は捨てられるので、`x` の値によらず常に `λy.y` になります。

```
I = K′ +
```

次に、もう一つ計算しておきたい関数があります。

```
- + I x y z
= I P + x y z
= P + x y z
= + (Q x) (K y) I z
= Q x I (K y I z)
= K y I z (I x)
= y z (I x)
= y z x
```

これは、引数の順番を入れ替える関数です。この関数には C′ という名前をつけておきます。

```
C′ = - + I
C′ x y z = y z x
```

C′ は、ペアを作るときに便利です。

```
C′ a (C′ b)
= (λx y z.y z x) a ((λx y z.y z x) b)
= (λy z.y z a) ((λx y z.y z x) b)
= λz.(λx y₀ z₀.y₀ z₀ x) b z a
= λz.(λy₀ z₀.y₀ z₀ b) z a
= λz.(λz₀.z z₀ b) a
= λz.z a b
```

## S と K

ここまでくると、あとは S と K を作るだけです。先に答を見せます。

```
K = C′ K′ C′
S = + C′ (+ + (C′ (+ (+ K) I) K′))
```

実際に確認してみましょう。

```
C′ K′ C′ x y
= C′ x K′ y
= K′ y x
= x
```

```
+ C′ (+ + (C′ (+ (+ K) I) K′)) x y z
= C′ x (+ + (C′ (+ (+ K) I) K′) x y) z
= + + (C′ (+ (+ K) I) K′) x y z x
= + x (C′ (+ (+ K) I) K′ x y) z x
= x z (C′ (+ (+ K) I) K′ x y z x)
= x z (K′ x (+ (+ K) I) y z x)
= x z (+ (+ K) I y z x)
= x z (+ K y (I y z) x)
= x z (K (I y z) (y (I y z) x)))
= x z (I y z)
= x z (y z)
```

……というわけで、`+` と `-` の組があれば S と K を作れる (**チューリング完全である**) と、示すことができました。

ちなみに、全て `+` と `-` だけで表すと こうなります。長いですね。

```
K = - + (- - - +) (- - -) (- + (- - - +))
S = + (- + (- - - +)) (+ + (- + (- - - +) (+ (+ (- + (- - - +) (- - -) (- + (- - - +)))) (- - - +)) (- - -)))
```

# Worse の文法

ようやく言語自体の説明に入ることができます。文法は至ってシンプルです。

```
Expr ::= "+"
       | "-"
       | "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
       | Expr Expr "."
```

上で示したとおり、`+` と `-` だけで (理論上) プログラムは書けるのですが、シンタックスシュガーとして数値 (チャーチ数) も使えます。

ただし、利用可能なのは **1 桁**の数値だけです。10 以上の数は計算して作る必要があります。

`.` は関数の適用を表します。上で `f x y` のように書いていた式は、Worse では、`fx.y.` と書きます。また、`x z (y z)` は `xz.yz..` と表されます。括弧の代わりに後ろに `.` を置いている、というだけです [^8]。(`x y` のように並べただけでは関数適用の意味に**ならない**ので注意してください。)

コメントは、`#` から行末までです。

# プログラムの実行

Worse では、関数は常に遅延評価されます。

また、文法を見てもわかるように、Worse は入出力用の関数を持たない**純粋関数型言語**です。しかし、これは入出力を扱えないという意味ではありません。

プログラムは純粋な関数であり、インタープリターが、その関数が返す値を解釈して入出力を行います。

入出力は、ペアを用いて表現します。バイト単位での入出力になります。

```
PAIR x y f = f x y
FIRST p    = p K
SECOND p   = p K′
```

- (0 以上 255 以下, リストの続き) のペアは、1 バイト出力してから、リストの続きを評価することを表します。
- (256, 任意の関数) のペアは、プログラムの終了を意味します。2 つ目の関数は評価されないので何でも構いません。
- (257, コールバック) のペアは、1 バイト入力を受け取って、それを引数としてコールバック関数を実行することを表します。EOF は 256 で表されます [^9]。

実行のざっくりとした手順は以下のとおりです。

```
p を実行する手順:
FIRST p が
   0 以上 255 以下の場合、出力して SECOND p を実行
   256 の場合、終了
   257 の場合、入力 n を受け取って SECOND p n を実行
   それ以外の数、あるいはチャーチ数でない場合、エラー
```

# プログラムの基本事項

まず、10 以上の数の作り方です。これはチャーチ数の加算・減算・乗算・べき乗を利用します。

```
# 10 = MULT 5 2 = 5 (+ 2) 0
5+2..0.
# 32 = EXP 2 5 = 5 2
52.
# 257 = PLUS (EXP 4 4) 1 = + (4 4) 1
+44..1.
```

ペアの表現には C′ (`-+.1.`) を使います。

```
-+.1.[first].-+.1.[second]..
```

`PAIR` 関数自体は次のように表せます。

```
# + + C′ C′ K′
++.-+.1..-+.1..0.
```

また、出力の終端 (プログラムの終了) を表すペアは、 `FIRST` しか適用されないことを利用して、少し短く書けます。

```
# C′ (4 4) K′
-+.1.44..0.
```

最後に、Y コンビネータを載せておきます。`f` の部分を再帰したい関数で置き換えて使います。

```
# Y f = + 1 (C' 0 C') (C' 1 (+ (C' 1 C') (C' (+ (C' f 0)) C'))) +
+1.-+.1.0.-+.1...-+.1.1.+-+.1.1.-+.1...-+.1.+-+.1.[f].0...-+.1.....+.
```

# プログラムの例

もうそろそろ書き疲れてきたので、雑な説明とともに簡単なプログラムをお見せして、終わりにしたいと思います。

## Hello World (再掲)

単に 1 バイトずつ数値を作ってリストにしています。

```
-+.1.9+8..0..-+.1.-+.1.+22+5..0...1..-+.1.-+.1.26.+3..0..-+.1.-+.1.26.+3..0..-+
.1.-+.1.+26..1.+3..0..-+.1.-+.1.+26..8..-+.1.-+.1.52..-+.1.-+.1.-72..9..-+.1.-+
.1.+26..1.+3..0..-+.1.-+.1.+26..2.+3..0..-+.1.-+.1.26.+3..0..-+.1.-+.1.22+5..0.
..-+.1.-+.1.+52..1..-+.1.-+.1.5+2..0..-+.1.-+.1.44..0..........................
...
```

## cat プログラム [^10]

Y コンビネータを利用して再帰しています。

```
+1.-+.1.0.-+.1...-+.1.1.+-+.1.1.-+.1...-+.1.+-+.1.-+.1.++.-+.1..-+.1..0..+-+.1.
++.-+.1..-+.1..0.+44..1...0..-+.1....0...-+.1.....+.
```

# おわりに

今見返してみると、タイトルと中身のギャップがすごいですね。嘘は書いてないんですけど……

~~幸いなことに、クリスマスには何も予定がないので、~~12/25 になって慌てて記事を書き上げました。実装も雑で (特にエラー処理)、テストもまだ書いていません [^11]。本当は関数をどう表現しているか、といった実装の詳細についても書きたかったのですが、間に合いませんでした。

それではみなさん、メリークリスマス、そして良いお年を！

[^1]: こういうのをチューリング陥穽 (Turing tarpit) と呼ぶようです。
[^2]: 他にも自然数を関数にエンコードする方法はありますが、最も一般的なのがチャーチ数です。ちなみに、この文脈では 0 は自然数に含めます。
[^3]: これも あくまで一例です。
[^4]: predecessor (先行するもの) から。
[^5]: チャーチ数は自然数なので、-1 は定義されません。
[^6]: `f` を適用しなければ再帰は終了します。
[^7]: 厳密には「計算可能な」関数です。
[^8]: Unlambda の前置の `` ` `` と同様です。
[^9]: Lazy K の方式に倣いました。
[^10]: 入力をそのまま出力するプログラム。名前は cat コマンドに由来します。
[^11]: とりあえず Hello World が動いたので良しとしました。