翻訳:プログラミング言語Unlambda

[トップ][一覧][最近の更新]

このページでは、Unlambda公式サイトの翻訳を試みます。

基本的に超訳です。

訳の正しさは全く保証されません。 訳のおかしい部分は多数あります。

翻訳元サイトの許可を取ったりはしていません。 無認可です。

まだ翻訳途中です。

しかし、途中でへばりました。すみません。


プログラミング言語Unlambda

Unlambda: 関数型言語の悪夢がやってくる

(訳注: この訳は、 http://hw001.gate01.com/eggplant/tcf/unlambda/ から貰いました。)

目次

Unlambdaワールドの最新情報

(Unlambdaが何なのかを知らない人は、このセクションは飛ばして、イントロダクションの方からどうぞ。)

[2001/08] このページ(訳注: 原文の方)はUnlambdaバージョン3配布物の為に、今現在も改訂中です(訳注: 訳に自信無し)。

イントロダクション

“こいつはひどい……こいつはおぞましい……みんな大好きUnlambda。” CyberTabloid

“あらゆるコードがIOUCCに参加できる言語、それがUnlambdaである。” Encyclopaedia Internetica

(訳注: IOUCCとは、IOCCC(ja.wikipedia:IOCCC)のようなものだと思われる。国際Unlambdaコード難読化コンテスト?)

Intercal以来の歴史の中で、これ以上は無い、最悪のブツである。” Computer Languages Today

“LispのS式を装着したENIACによって脳味噌を強打される効果が、Unlambdaで書かれたプログラムを読む際に発生します。貴方はこれっぽっちもアルファケンタウリの西を探そうとしませんでした。” The Hitch-Hacker's Guide to Programming

(訳注: これらは全部、適当に捏造された煽り文句だと思われる。)

Unlambdaとは何か

Unlambdaはプログラミング言語です。 何も目新しい部分はありません。 Unlambdaの独特な部分は、二つのプログラミング言語の家系の親戚が思いがけず交わったりなんかした辺りにあります。

難読化プログラミング言語(詳細については下の方のリンク先を見て下さい)は、典型的には、言語内でのオペレーションに強い制約を課したり、プログラマに使い古された何かとは全く違う要素を持ち込んだりしています。 (勿論、そのような言語であっても、まだチューリング完全にはなっています。) Unlambdaもそうです(但し、どのようなオペレーションを許可するのかは適当に選んだ訳ではなく、理論的に重要なものを選択しています)。 既にある大抵の難読化プログラミング言語はチューリングマシンパラダイムに挑戦していますが、Unlambdaではテープも配列もスタックも使いません。 バイナリ指向ではないし、何を隠そう、整数を扱う事すら行いません。 他の目立つ(無)機能は、全く変数、データ構造、コード構造(ループや条件分岐等)を持たない事です。

予想以上に、Unlambdaはプログラミングに対して関数型アプローチを使います。 唯一の操作可能なオブジェクトは関数です。 それぞれの関数は、引数として(一つの)関数を取り、返り値として(一つの)関数を返します。 それはさておき、バイナリ(訳注: 二分木?)を“applyする”操作は、Unlambdaでは幾つかの組み込み関数として提供しています(最も重要なものは、K及びSコンビネータです)。 ユーザが新しい関数を作る事は可能ですが、それを保存したり名前を付けたりする事はできません。 Unlambdaは変数を扱わない為です。

ちょっと見では、どうやっても克服できそうにない制約にも関わらず、Unlambdaは完全にチューリング等価なのです。

数学的には、Unlambdaのコアは、完全にK及びSコンビネータに頼った、λ抜きのλ算法によって記述できます。 それ故に“Unlambda”という名なのです。 Unlambdaでは頭部(“eager”または“by value”または“strict”)評価が行われます。 私(訳注: Unlambdaの作者)はこれにオリジナリティを主張する事はできません。 ですが、私の知る限り、これ(KSコンビネータ)の論理的コンセプトを実際に実装した(そして故意に難読化を目論んだ)プログラミング言語を仕上げたのは私が最初です。 そして、(不明瞭化の為に選択した)一連の関数も追加しました。 出力(そしてバージョン2では入力も)を可能にし、更なる不明瞭化の為にdelayやcall/ccのようなものも追加しました。

用語についての注釈: “純粋関数型プログラミング言語”というフレーズが、HaskellやCleanのような言語に使われます。 これらの言語は遅延評価を行い、副作用が厳密に上手い事分離されます。 私はこの用語が嫌いです。 “関数型”プログラミング言語は関数がfirst class objectであるという事を意味している訳で、“純粋関数型”という称号は、関数のみがfirst class objectであるUnlambdaのような言語にこそ相応しいと考えます。 ついでに言うと一般的に“純粋関数型プログラミング言語”と呼ばれているものは、正確に言えば、厳密な副作用制御機能付き遅延評価プログラミング言語とでも言うべきものです。 これは、“関数型プログラミング言語”とは、全く直交する概念です。 非関数型言語や、eager(非遅延評価)な関数型言語でも厳密な副作用分離を実装する事が可能そうなのはすぐに分かりそうなものです。 多くのケースで時々、「Unlambdaは“純粋関数型”プログラミング言語である」と言われますが、これは、一般的に使われているこの用語の意味とは違うのです。

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

(空白は含んでも含まなくても構いません。このページの幾つかの作成バージョンは無駄に複雑で効率の悪いプログラム(訳注: 空白を含んでいるという事だと思われる)を書いています。)

「こいつは何て読みにくいんだ」と思いましたか。 Unlambdaプログラムを書く事は、実は、思ったよりも簡単なのですが、Unlambdaプログラムを読む事は事実上不可能です。 このUnlambdaプログラムの解説は後で行いますので、基礎演習が終わるまで、もう少しお付き合いをお願いします。

見ての通り、Unlambdaプログラムではバッククォート文字(ascii番号96=0x60)が多用されます(大体、Unlambdaプログラムの文字の半分ぐらいはバッククォート文字です)。 Unlambdaでのバッククォート文字は、(訳注: schemeでの)「apply」操作を意味します。 バッククォート文字の後ろには、SやKコンビネータが来ます(Iコンビネータも来れますが、その場合は完全に省略可能です)。 他の幾つかの文字も、Unlambdaプログラム中に使う事ができますが、それほど頻繁に使われる訳ではありません。 バッククォート及び「s」「k」「i」以外に、前述のサンプルプログラムには「r」や「.*」が含まれています。 これらはUnlambdaでの出力関数です(「r」は改行を出力し、「.*」はアスタリスク(「*」)を出力します)。 より洗練されたUnlambda関数(「v」「d」「c」「e」及び入力関数)は、このサンプルでは全く使っていません。

Unlambdaのルール

Unlambda言語の第一原則は、「全てのオブジェクトは関数である」という事です。 これはつまり、Unlambdaは、純粋な型無しラムダ算法によって描かれるという事です。 (正直に言いますと、Unlambdaの「d」は正しくは関数ではありません。ですが、まあ関数に似たようなものだと考えても問題は無いでしょう。)

Unlambdaはラムダ算法の形をしているにも関わらず、ラムダ(抽象)操作(訳注: schemeでのlambdaのような、関数を生成する機能)を持ちません。 それどころか、ラムダ操作はS, K, Iコンビネータに置き換えられなくてはいけません。 これは、抽象除去(abstraction elimination)によって機械的に行う事ができます。 ですが、抽象はありませんし、Unlambdaでは関数に名前を付ける事もできません(ビルトイン関数を除いて)。 Unlambdaには変数や、変数に類するものは無いのです。 ですが、この事は独自の関数を生成する事が出来ない、という事ではありません。 また、扱えるオブジェクトが関数のみであるという事は、データ構造及びそれに類するものを作り出す事が出来ない、という事もありません。 ですが、データ構造のようなものを作り出す為には、それをad hocな関数で表現するしかありません。 そして実際、独自のデータ構造体を上手く構築する事ができますし、Unlambdaは適正なガベージコレクションのようなものを持つ高級言語なのです。

そう、全ては関数なのです。 原初にはビルトイン関数(i、k、s等々)だけが存在し、それらに対して行える唯一の操作が「関数Fを関数Gに「適用」(apply)する」事であり、それは具体的には「`FG」として示されます。 これこそが、Unlambdaを構築する基礎的なアイデアなのです。

その他の難読化プログラミング言語へのリンク及びメタリンク

(訳注: 省略)

チュートリアル

Unlambdaのような難読化プログラミング言語の解説を行おうというのは実にばかばかしい事です。 が、とりあえず簡潔な紹介を行う事にします。

関数とその適用について

イントロダクションで述べたように、Unlambdaで扱える唯一のオブジェクトは関数です。 全ての関数は正確に一つの引数だけを取り、返り値として一つの値だけを返します。 当然、引数として渡す値は関数ですし、返り値も関数になります。

Unlambdaプログラムを構築する為の基本的な材料は、基礎関数と適用(apply)オペレーションです。 まず、Unlambdaのバージョン1によって、七つの基礎関数「k」「s」「i」「v」「d」「c」「.x」(xは任意の1バイト文字です。つまり実際には6+256の基礎関数とも言えますが、ここでは「.x」は一つの関数として扱います。ちなみに「r」関数は「.x」関数のxに改行コードを指定したものの同義語です)が用意されました。 そして、Unlambdaのバージョン2によって、追加の基礎関数「e」「@」「?x」(xは任意の1バイト文字)「|」がサポートされました。

関数の適用はバッククォート文字(ascii番号96=0x60)によって指定します。 これは前置句として表記します。 具体的には、「`FG」というのは、関数FをGに適用する、という意味になります。

さて、ここでちょっと、「適用する」という事の意味を詳細に説明します。 まず簡潔に説明しておくと、 (訳注: 「`FG」が評価されて)関数Fが引数Gを受け取った時、 適用を含むその他の関数を引数Gに対して適用したり、 逆に、引数Gを他の関数に対して適用したりを行います。 (何を隠そう、これぐらいしかできません。) この辺の具体的なところは、後で説明します。 勿論、関数FもGも、各種の関数から得られます。 (訳注: ここは訳が非常に怪しい。あとで検討し直す事)

全てのUnlambda関数は単項(引数を必ず一つだけ取る)ですから、バッククォートによる表記法で充分に明瞭であり、(訳注: CやLispの関数のように)括弧を必要としません(こう説明してもいいでしょう。バッククォートはLispの左括弧「(」の役割を果たし、右括弧「)」はUnlambdaには不要なのです)。 例えば、「``FGH」は「「FをGに適用したもの」をHに適用する」という意味になります。 もう一つ例を挙げると、「`F`GH」は「Fを「GをHに適用したもの」に適用する」という意味になります。 ところで、ある表記が正しいUnlambda文法になっているかどうかを判断するには、簡単な方法があります。 まずカウント初期値を1としておきます。そして、先頭から順に読んでいき、読んだものがバッククォートであるならカウント数を1増やし、読んだものがバッククォートではなく他の組み込み関数ならカウント数を1減らします(訳注: .xとかの二文字表記の関数も一つとして数える事)。表記が正しいUnlambda文法であるなら、カウント数は常に正の値を維持し、最後までカウントし終わった段階でゼロになる筈です。

有史以来、全てのUnlambda関数は一つの引数しか取れませんので、もし複数の引数を取る関数を扱いたいと思った時には、「カリー化」が必要になります。 これは、(Unlambda関数が)一つの引数を受け取った後に、更に別の引数を(矢張り一つずつ)受け取るというものです。 具体的には、もしFが三つの変数を必要とする関数だとすると、これはおそらく「```FG1G2G3」のようなコードによって、適用される事になるでしょう。 まず、Fは最初の引数(G1)を受け取り、何も行わずに、次のような関数F2(仮名)を返します。 F2(仮名)は、「引数を一つ(G2)受け取り、何も行わずに、次のような関数F3(仮名)を返す」挙動をする関数です。 F3(仮名)は、「引数を一つ(G3)受け取り、G1とG2とG3を使って、Fが本来行いたかった何らかの操作を行う」挙動をする関数です。 これが「カリー化」の考え方です。 つまり、「``FG1G2」と「`FG1」は文法的には正常なのですが、どちらにしても、この後に想定している数の引数が与えられるまでは、実際には何も行われません。

ここまでの話はあまり理論的ではありません。 勿論、独自の関数を新しく定義したいと思った時に、関数の引数を渡す為に利用可能に思える、どんなアルゴリズムでも採用する事は可能です(が、Unlambdaではペアやリスト等を定義するのが著しく困難な為、引数をリスト等にまとめる等の手法を採用するよりは、このカリー化を用いるのが明らかにベストでしょう)。 しかし、ビルトイン関数である「k」と「s」は、先程の説明通りに、二個か三個の引数をカリー化方式で取ります。 (備考: 引数を全く取らない関数を構築する事は、仮に不可能でないとしても、非常に不自由です。 なぜなら、カリー化は、言ってみれば、全ての引数を受け取るまでは評価を先伸ばしにするようなものだからです。 そうなると、引数が零個であるという事は、非常に喜ばしくない状況です。 純粋なラムダ算法では、(訳注: 参照透過性があるので)評価順は決定されておらず、重要でもありませんので、それでも別に問題はありません。 ですが、(訳注: 副作用を持つ関数がある)Unlambdaではこれは大きな問題になります。そのような状況では組み込み関数の「d」が助けになります。)

評価順に関する注釈: 例えば、Unlambdaが「`FG」を評価する場合、まず先にFが評価され、次にGが評価され(但し、Fが組み込み関数「d」である場合は除く)、その後に実際の適用動作が行われます。 この「評価」動作はidempotentに行われます。 つまり、既に「評価」されたコードをもう一度「評価」しても、何も行われません(この非「level-of-quotation」コンセプトは、m4マクロやSIMPLEマクロに類したものです)。 (訳注: おそらく、これは組み込み関数「d」に関係する話だと思われる。他の部分を訳し終わってから、もう一度ここの意味を見直す。)

(多分、特徴的な表現と関数で、前者を評価する事によって後者が得られる事を、より明らかに表現できると思います。 例えば、(Scheme版ではなく)Java版のUnlambdaインタプリタを使ってみてください。 これは単なる選択肢に過ぎません。 これにより、組み込み関数「d」が、その引数部分の評価を後回しにする事が分かりやすくなるでしょう。)

では、Unlambdaのビルトイン関数の説明に戻りましょう。

コンビネータ

Unlambdaの最重要要素は、組み込み関数「k」と「s」です。 Unlambdaがチューリング完全になる為には、この二つがあるだけで充分なのです(とは言え、何かを出力したい場合は「.x」も必要ですが)。 組み込み関数「k」を簡潔に説明すると、「kは(前述のカリー化方式で)二つの引数を取り、そして、第一引数をそのまま返します」。 つまり、「``kXY」を評価すると、(評価済の)「X」になります。 ここでの注意点は、「Y」の値自体は捨てられますが、kに渡される前に(引数として)評価だけは行われるという事です。 組み込み関数「s」は更に少々デリケートになります。 「s」は三つの引数を取り、それらをX, Y, Zとすると、「``XZ`YZ」を評価するのと同じ事を行います。

もう少し、はっきりさせておきましょう。 「k」は、二つの引数が適用されるまで何も行わず、二つの引数が適用された時は第二引数は捨て、返り値として第一引数を返します。 「s」は、三つの引数が適用されるまで何も行わず、三つの引数が適用された時は、まず第一引数を第三引数に適用したものが算出され、次に第二引数を第三引数に適用したものが算出され、最後に前者を後者に適用したものが算出され、その結果が返されます。

例えば、「```skss」という式を考えてみましょう。 まず最初の「s」が三つの引数「k」「s」「s」を受け取り、これは、(先ほどの「s」の説明より)「``ks`ss」を評価するのと同等に機能します。 ですが、よく見ると、この式は「k」に対して二つの引数(「s」と「`ss」)を与えているので、(先ほどの「k」の説明より)最初に渡された方の引数(つまり「s」)が返る事になり、最終的な結果は「s」となります。

関数「i」にも言及しておきます。 「i」は単純な恒等関数です。 分かりやすく言い換えるなら、「i」は一つの引数を取り、それをそのまま返り値として返します。 関数「i」は、厳密には必須ではないのですが、実際には必要です。 「i」は、「``skk」によって置き換える事が可能です。 (実際に「```skkX」を評価すると、まず「s」を変換して「``kX`kX」になり、そして「k」を変換して「X」が得られます。)

要約すると、組み込み関数「k」は「定数関数構築子」だと言えます。 これはつまり、あらゆるXについて、「`kX」は、値Xを返す定数関数を意味するという事です。 組み込み関数「s」は「置換適用」に対応します。 これはつまり、「``sXY」は、XをYに直接適用する代わりに、Z(「``sXY」に渡す引数)にXとYそれぞれを適用し、その後に、先ほど適用した`XZを`YZに適用します。 最後の「i」は恒等関数です。

抽象除去

「抽象除去」の大体の流れについて今から説明します。 Unlambdaがどのように動作するのかを理解する事は必ずしも必要ではありませんが、抽象除去を使って何かを行う事は理解しておく必要があります(訳注: 訳が微妙におかしい)。

続きはあとで。

まだまだ先は長い……。


訳者による要約

Unlambda概要

Unlambda書式

Unlambda組み込み関数

続きはあとで。

一般的な用語説明

λ算法

コンビネータ / combinatory logic

あとで。

適用 / apply

カリー化


コメントその他

コメント解説間違い修正その他等々、この辺によろしくお願いします。


最終更新 : 2007/02/17 00:41:17 JST