Unlambdaとは (アンラムダとは) [単語記事]

Unlambdaとは、David Madoreによって定義されたプログラミング言語で、関数型言語に分類される。

概要

1999年に純粋関数型言語の実証のために登場した言語。理論実証のためのシンプルな言語仕様だが、実用性も可読性もない。同年にバージョン2.0で入力用命令が追加されてからは仕様変更されていないしする必要もない。

変数の参照透過性という意味では変数定義がないので純粋だが、入出力の副作用を行う関数が存在するため厳密には純粋関数型言語として扱われないこともある。なお、Unlambdaの開発者は純粋関数型言語とは関数のみが第一級である言語のことを指すべきであるなどと供述しており、定義の問題に過ぎないのかもしれない。

サンプルコード

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
The Unlambda Programming Languageより

このプログラムを実行すると、一行ごとにフィボナッチ数列の数だけアスタリスクが出力される。第何項までか引用元にも記載がないので、強制終了しない限りメモリ不足かオーバーフローでインタプリタがクラッシュするまで無限ループするっぽい。

言語仕様

サンプルコードを見てのとおり、プログラムのほとんどは`(バッククォート)とsとkで占められており、そのほかに少数のi、r、.などの補助的な記号がある。これは実はコンビネータ論理(combinatory logic)という理論に基づいたものであり、その理論によれば、最低限`とsとkさえあればチューリング完全(つまり、C言語やBrainf*ckと同様のロジック)が達成できることが証明されている。

`は関数適用。kは2つ引数をとり、2つ目の引数を捨てて1つめの引数を返す関数。sが何かは考えたら負けは3つ引数をとり、「1つ目の引数を3つ目の引数に適用してできた関数を、2つ目の引数を3つ目の引数に適用してできた値に適用する」という関数である。

カリー化されていることにも触れなければコードが書けないが、やはり考えたら負けである。

i は``skk の短縮表記だが、引数をそのまま返す恒等関数と言ったほうがわかりやすいだろう。

ちなみに、k はconstantのドイツ語Konstantに、s はsubstitutionに、i はidentityの頭文字である。

Unlambdaにおいて、すべてのオブジェクトは1引数関数である。たとえばサンプルコード中の*も関数(ただし動作は定義されていないので関数適用されることはなく、画面表示を行う関数の引数としてのみ使用されている)である。

rと.はそれぞれ標準出力に改行や文字を出力するための関数である。本来純粋関数型言語としては不要なものであるが、デバッグ用途やプログラムを実用的にするための用途(どの口が言う!)で用意されている。

名前の由来

ラムダ計算をラムダの操作を用いずにKとSのコンビネータだけで実装したからUnlambdaだとのこと。

Mathematically, the core of the language can be described as an implementation of the lambda-calculus without the lambda operation, relying entirely on the K and S combinators. Hence the name “Unlambda”.

The Unlambda Programming Languageより

ラムダ計算のうちUnlambdaには値に名前をつける機能がないので少なくともα変換はないのはわかるが、β変換は関数適用なので`が該当するのではないかという気がするが、ここでいうラムダの操作とは、ラムダ抽象(関数をラムダ式で表現すること)を指す。変数名が使えないのでλx y.(x² + xy + y²)のようなラムダ式を書くことは出来ず、ラムダ式相当の機能を使いたければ、ラムダ式がある状態を、s, k, i を組み合わせてラムダ式のない状態に変換しなければならないから"Un" lambdaだということらしい。