Unlambda言語について

Unlambda（アンラムダ）は、非常に小さな言語仕様をもつ関数型プログラミング言語です。関数型の[難解プログラミング言語](https://ja.wikipedia.org/wiki/%E9%9B%A3%E8%A7%A3%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E8%A8%80%E8%AA%9E) (Esoteric programming language, esolang) の中では最も古く、David Madoreによって1999年に設計されました。

組み込みの数値や文字列といったものはなく、すべてのオブジェクトは関数です。また[コンビネータ論理](https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF%E8%AB%96%E7%90%86)に基づいており、変数を一切使わずにプログラムを書きます。

現在の最新バージョンはUnlambda version 2で、ほとんどの処理系がこのバージョンに対応しています。公式サイトには[Unlambda 3を準備中との記載](http://www.madore.org/~david/programs/unlambda/#whats_new)がありますが、結局発表されなかったようです。

## 例
下記はUnlambdaの[公式サイトからの例](http://www.madore.org/~david/programs/unlambda/#what_looks)で、フィボナッチ数を計算してアスタリスクの数として表示するUnlambdaプログラムです。`s`や`k`、`i`といった文字は関数で、`` ` ``は前置の関数適用演算子です。Unlambdaの関数はすべて１引数なので、カッコを使わなくても曖昧さなく関数適用を表せるのです。

````
```s``s``sii`ki
  `k.*``s``s`ks
 ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
  `k``s`ksk
````

このプログラムを[ブラウザで動くUnlambdaインタプリタ](https://inazz.jp/unlambda/)にペーストして、Run を押して走らせてみてください。放っておくと無限に走り続けるので適当なところで Stop か Pause で止めておきましょう。

## 言語仕様
以下にUnlambda version 2の言語仕様を示します。

プログラム中のすべての空白文字は（後述する`.`や`?`の直後を除き）すべて無視されます。また、`#`から文末まではコメントとして無視されます。

`F`と`G`がUnlambdaの式であるとき`` `FG``もまた式となり、「`G`を引数として`F`を呼び出す」という意味になります。評価時はまず`F`が評価され、その結果が`d`でなければさらに`G`が評価され、`G`の値を引数として`F`の値を呼び出したしたものが式全体の値となります。

プログラム全体はひとつのUnlambda式で、評価が終わるとプログラムを終了します。

以下の組み込み関数があります。

- `k` は引数`X`をとり、「引数`Y`をとり`X`を返す関数」を返します。つまり、``` ``KXY = X ```になります。
- `s` は引数`X`をとり、返された関数はさらに引数`Y`をとり、さらに引数`Z`をとる関数を返します。`Z`が与えられると``` ``XZ`YZ` ```を評価して返します。つまり、```` ```SXYZ = ``XZ`YZ ````です。
- `i` は引数をそのまま返します。
- `v` はどんな引数が与えられても、`v`自身を返します。
- `c` はScheme言語のcall/ccにあたります。引数`X`をとり、現在の[継続](https://ja.wikipedia.org/wiki/%E7%B6%99%E7%B6%9A)を引数として`X`を呼び出します。この継続が呼び出されると、その引数を返り値として`c`が呼び出された時点から実行を再開します。
- `d` は引数`X`を **評価せずに** 受け取り（なので厳密には`d`は関数というより特殊形式です）、 _プロミス_ を返します。この _プロミス_ に引数`Y`が与えられると、そのとき`X`が評価され、 `` `XY``の値が返ります。
- `e` は呼び出されるとプログラムを終了します。
- `.x` は、ピリオドに続く任意の１文字でひとつの関数です。呼び出されるとその文字を出力して、引数をそのまま返します。
- `r` は改行を出力して、引数をそのまま返します。
- `@` は引数`X`をとり、入力から１文字を読み込んでインタプリタの「現在の文字」として記憶します。入力に成功した場合`` `Xi ``を返し、失敗した場合（ファイル終端など）は`` `Xv ``を返します。
- `?x` は、クエスチョンマークに続く任意の１文字でひとつの関数です。引数`Y`が与えられると、文字`x`が「現在の文字」と等しければ`` `Yi ``を返し、そうでなければ`` `Yv ``を返します。`@`がまだ呼ばれていなかったり、最後の`@`が失敗していた場合は「現在の文字」は存在しないので、必ず`` `Yv ``が返ります。
- `|` は引数`X`をとり、「現在の文字を出力する関数」を引数として`X`を呼び出します。例えば「現在の文字」が改行文字だった場合、`` `Xr ``の値が返ります。まだ`@`が一度も呼ばれていなかったり入力が終端に達していて「現在の文字」が無い場合、`` `Xv``が返ります。

仕様ではプログラムの文字コードについては触れられていませんが、公式を含むほとんどのインタプリタは`.`や`?`の直後の１バイトをそのまま文字として扱います。

## 入門記事
前節の内容がUnlambda言語仕様のすべてですが、おそらくこれを読んだだけではプログラムを書けないと思います。

これからUnlambdaを始めようという人は、まずはこちらの[Unlambdaの解説ページ](http://wada314.jp/tcf/unlambda/)にあるチュートリアルを読んでみるといいでしょう。

[Unlambda公式サイト(英語)](http://www.madore.org/~david/programs/unlambda/#tut)では、変数をもつラムダ式からUnlambdaへ変換する方法が詳細に解説されています。副作用を持つ式を扱うときの落とし穴などについても述べられているので、すでにLazy Kなどでコンビネータ論理のプログラムを書いた経験がある人にも役立つでしょう。さらに、if分やループをどのように書くか、数値やリストを関数でどのように表現するかといったテクニックも紹介されています。

書籍「[Rubyで作る奇妙なプログラミング言語](https://book.mynavi.jp/ec/products/detail/id=24268)」の付録でもUnlambdaが紹介されており、関数だけでプログラムを書く考え方が解説されています。

## インタプリタ
### 公式
http://www.madore.org/~david/programs/unlambda/#distrib
Unlambdaの公式サイトで配布されているアーカイブに、いくつかの言語で書かれたインタプリタが含まれています。c-refcntフォルダにあるC言語版が最も手軽に試せますが、このインタプリタにはバグがあり、`e`関数 (exit) が`c` (call/cc) と同じ振る舞いになってしまっています。（プログラム全体の評価が終わればインタプリタは停止するので、プログラムを終了できないというわけではありません。）

### unl.c
http://users.math.cas.cz/~jerabek/ptakoviny/index.html#unl
Emil Jeřábek氏によるインタプリタ (unl.c) は公式のc-refcntインタプリタの50〜100倍高速です。

### irori/unlambda
https://github.com/irori/unlambda
筆者によるunlambdaインタプリタです。世代別GCと命令融合を備えた、現在最速の処理系です。（[解説記事](http://irori.hatenablog.com/entry/unlambda-interpreter)）

### haskell-unlambda
http://hackage.haskell.org/package/unlambda
Debian系のOSで`apt install unlambda`するとこれが入ります。[コードの先頭](https://github.com/abbradar/unlambda/blob/b94c952b962cc599bca08906159d55fa0b56677a/Main.hs#L5)に `-- A time- and output-limited unlambda` と書いてあるように、__CPUを5秒間使うか2048文字出力すると強制的に終了__してしまいます。

またプログラムは標準入力からしか読まれないので、入力を使うプログラムを実行する際は

```sh
$ cat foo.unl - |unlambda 
```

などとする必要があります。（foo.unlの末尾に改行があったりすると入力の最初の文字とみなされてしまうので注意。）

### JavaScriptインタプリタ (inazz.jp)
https://inazz.jp/unlambda/
Unlambdaプログラムをステップ実行しながら実行中の式を確認することができます。

### IOCCC 2019 Most functional interpreter
http://www.ioccc.org/2019/adamovsky/prog.c
[解説](http://www.ioccc.org/2019/adamovsky/hint.html)
国際難読化Cコードコンテストの入賞作品。4kBのC言語で記述されたインタプリタです。

## アプリケーション
### The Comprehensive Unlambda Archive Network
ftp://ftp.madore.org/pub/madore/unlambda/CUAN/
Unlambdaプログラムのコレクションで、Unlambdaの公式配布物にも一部が収められています。Unlambdaで書かれたUnlambdaのインタプリタや、たくさんの[Quine](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0))プログラムがあります。

### Adventure in Unlambda
https://github.com/irori/advent-unlambda
世界最初のアドベンチャーゲーム[Colossal Cave Adventure](https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%AD%E3%83%83%E3%82%B5%E3%83%AB%E3%83%BB%E3%82%B1%E3%83%BC%E3%83%96%E3%83%BB%E3%82%A2%E3%83%89%E3%83%99%E3%83%B3%E3%83%81%E3%83%A3%E3%83%BC)のUnlambda移植です。([解説記事](http://irori.hatenablog.com/entry/20111210/1323488113))

### ELVM
https://github.com/shinh/elvm
Esolang用コンパイラ基盤ELVMにはUnlambdaバックエンドが用意されており、C言語のプログラムをUnlambdaにコンパイルできます。（[解説記事](http://irori.hatenablog.com/entry/elvm-unlambda-part1)）

## プログラミングコンテスト
### Anarchy Golf
http://golf.shinh.org/
Unlambdaを含む数多くの言語で[コードゴルフ](https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%BC%E3%83%89%E3%82%B4%E3%83%AB%E3%83%95)を楽しむことができます。コンテスト期間が終わった問題はコードが公開されるので、Unlambdaで短いコードを書く参考になるかもしれません（もし読めれば…）。

インタプリタは[unl.c](#unlc)が使われています。

### AtCoder
https://atcoder.jp/
競技プログラミングのサイトAtCoderでは、Unlambdaでプログラムを提出することができます。[実際に何問か解かれた方の記事](http://satos.hatenablog.jp/entry/2018/04/23/235547)によると、時間制限がけっこう厳しいようです。

インタプリタはバージョン0.1.3との記載があるので、[haskell-unlambda](#haskell-unlambda)だと思われます。

## そのほかの関数型難解プログラミング言語
### Lazy K
Unlambdaは`.`や`?`といった副作用を伴う関数を持つため（[参照透過性](https://ja.wikipedia.org/wiki/%E5%8F%82%E7%85%A7%E9%80%8F%E9%81%8E%E6%80%A7)を持つという意味の）純粋関数型言語ではありません。[Lazy K](http://tromp.github.io/cl/lazy-k.html)はUnlambdaから副作用のあるオペレータを取り除き、`s`, `k`, `i`（あるいはその代替となるコンビネータ）のみでプログラムを書けるようにした純粋関数型言語です。入出力は文字のチャーチ数（関数で自然数を表したもの）表記のリストとして表現されます。またUnlambdaの評価戦略が[正格評価](https://ja.wikipedia.org/wiki/%E5%85%88%E8%A1%8C%E8%A9%95%E4%BE%A1)であるのに対し、Lazy Kは[遅延評価](https://ja.wikipedia.org/wiki/%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1)を行います。UnlambdaがScheme的であるとすれば、Lazy KはHaskell的であると言えるでしょう。

理論的にはLazy Kのほうがきれいですが、一方Unlambdaは `c` (call/cc) や`d` (delay) といった厄介なオペレータの使用をなかば強制される[^1]など、より難読性を指向していると言えるかもしれません。

[^1]: Unlambdaの設計者David Madoreによると、これらの要素は難読性を増すために加えられたとのことです。

### Grass
[ちょっと草植えときますね型言語 Grass](http://www.blue.sky.or.jp/grass/)は、W, w, v の３種類の文字だけを使ってプログラムを書く関数型難解プログラミング言語です。UnlambdaやLazy Kがコンビネータ論理を基にしているのに対し、Grassはラムダ計算とスタックマシンをベースとした計算モデルを持ち、プログラムの書き方もUnlambdaとだいぶ異なります。

## 関連リンク
- [The Unlambda Programming Language](http://www.madore.org/~david/programs/unlambda/)（公式サイト）
- [esolangs.orgのUnlambdaページ](http://esolangs.org/wiki/Unlambda)
- [Unlambda - Wikipedia](https://ja.wikipedia.org/wiki/Unlambda)