More than 5 years have passed since last update.

Unlambda言語について

Last updated at 2019-11-05Posted at 2018-04-01

Unlambda（アンラムダ）は、非常に小さな言語仕様をもつ関数型プログラミング言語です。関数型の難解プログラミング言語 (Esoteric programming language, esolang) の中では最も古く、David Madoreによって1999年に設計されました。

組み込みの数値や文字列といったものはなく、すべてのオブジェクトは関数です。またコンビネータ論理に基づいており、変数を一切使わずにプログラムを書きます。

現在の最新バージョンはUnlambda version 2で、ほとんどの処理系がこのバージョンに対応しています。公式サイトにはUnlambda 3を準備中との記載がありますが、結局発表されなかったようです。

例

下記はUnlambdaの公式サイトからの例で、フィボナッチ数を計算してアスタリスクの数として表示する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インタプリタにペーストして、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をとり、現在の継続を引数として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の解説ページにあるチュートリアルを読んでみるといいでしょう。

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

書籍「Rubyで作る奇妙なプログラミング言語」の付録でも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と命令融合を備えた、現在最速の処理系です。（解説記事）

haskell-unlambda

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

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

$ 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
解説
国際難読化Cコードコンテストの入賞作品。4kBのC言語で記述されたインタプリタです。

アプリケーション

The Comprehensive Unlambda Archive Network

ftp://ftp.madore.org/pub/madore/unlambda/CUAN/
Unlambdaプログラムのコレクションで、Unlambdaの公式配布物にも一部が収められています。Unlambdaで書かれたUnlambdaのインタプリタや、たくさんのQuineプログラムがあります。

Adventure in Unlambda

https://github.com/irori/advent-unlambda
世界最初のアドベンチャーゲームColossal Cave AdventureのUnlambda移植です。(解説記事)

ELVM

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

プログラミングコンテスト

Anarchy Golf

http://golf.shinh.org/
Unlambdaを含む数多くの言語でコードゴルフを楽しむことができます。コンテスト期間が終わった問題はコードが公開されるので、Unlambdaで短いコードを書く参考になるかもしれません（もし読めれば…）。

インタプリタはunl.cが使われています。

AtCoder

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

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

そのほかの関数型難解プログラミング言語

Lazy K

Unlambdaは.や?といった副作用を伴う関数を持つため（参照透過性を持つという意味の）純粋関数型言語ではありません。Lazy KはUnlambdaから副作用のあるオペレータを取り除き、s, k, i（あるいはその代替となるコンビネータ）のみでプログラムを書けるようにした純粋関数型言語です。入出力は文字のチャーチ数（関数で自然数を表したもの）表記のリストとして表現されます。またUnlambdaの評価戦略が正格評価であるのに対し、Lazy Kは遅延評価を行います。UnlambdaがScheme的であるとすれば、Lazy KはHaskell的であると言えるでしょう。

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

Grass

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