クソアプリ 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 という名前のプログラミング言語です。「プログラミング言語」を名乗るからには、もちろんチューリング完全ではあるのですが、仕様が極端に小さいため実用性は皆無です ¹。

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

TL;DR

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

関数で自然数を表す

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

                       # 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 を適用する回数で数値を表しています。

足し算

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

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 ⁴ 関数が必要になります。PRED を使うと、引き算の関数は次のように書けます。

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

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

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

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

さて、PRED 関数ですが、少し複雑な定義になります ³。

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

記事の長さの都合上説明は割愛します。(Wikipedia 英語版に詳しい解説があります。)

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

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 として扱われます ⁵。

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 英語版) これを説明するだけで一つの記事になりそうです。

論理値

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

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

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

AND/OR/NOT は以下のように定義されます ³。

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 ...)))
= ...

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

SKI コンビネータ

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

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

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

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

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

例: 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.. と表されます。括弧の代わりに後ろに . を置いている、というだけです ⁸。(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 で表されます ⁹。

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

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 プログラム ¹⁰

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 になって慌てて記事を書き上げました。実装も雑で (特にエラー処理)、テストもまだ書いていません ¹¹。本当は関数をどう表現しているか、といった実装の詳細についても書きたかったのですが、間に合いませんでした。

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

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