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

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

このページは、Lazy K公式サイトの翻訳です。

基本的に超訳です。

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

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



訳者による前書き / 訳語について


Lazy K

要約

Lazy Kは、ガベージコレクションと、ストリームベースのI/Oシステムが付いた、参照透過性を持つ関数型プログラミング言語です。

Lazy Kが、類似の他のプログラミング言語(訳注: どうも、HaskellやML系の言語を指しているように思える)と違っている点は、それらのプログラミング言語が持っているほとんど全ての機能が、Lazy Kには欠けている事です。 例えば、統合されたHindley-Milner多相型システムの提供等です。 また、(他の言語では実現されているような)プラットフォームに依存しないGUIプログラミングや、他言語との結合サポート(訳注: おそらく、SWIGのようなものの事だと思われる)等の、(他言語ではほぼ標準装備になっているような)拡張可能な標準ライブラリは、Lazy Kでは標準装備にはなっていません。 更に、このようなライブラリを書く事はおろか、何よりも、定義や参照を行うようなどんな手段も、また、組み込み関数以外のどんな関数も、Lazy Kは提供しません。 そして、このLazy Kの持つ無能性は、数値や文字列やその他のあらゆるデータ型のサポートが欠如している事によって、更に増幅されています。 ですが、それにも関わらず、Lazy Kはチューリング完全なのです。

サンプルコード

以下は、素数を出力する、Lazy Kのプログラムソースです。 簡潔な「エラトステネスのふるい」のアルゴリズムをlazy listを使って実装してあり、意外と高速です。 私のコンピュータでは、実行開始してから最初の一秒で大体素数80個ぐらいを出力できています(勿論、数が大きくなるにつれ、出力される頻度は落ちていきます)。

K
(SII(S(K(S(S(K(SII(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(SS(S(S(KS)K))(KK)))))
(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(SII)))
(K(SI(KK)))))))(K(S(K(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)(S(S(KS)K)I)
(S(SII)I(S(S(KS)K)I)(S(S(KS)K)))))(SI(K(KI)))))))))(S(KK)K)))))))(K(S(KK)
(S(SI(K(S(S(S(S(SSK(SI(K(KI))))(K(S(S(KS)K)I(S(S(KS)K)(S(S(KS)K)I))
(S(K(S(SI(K(KI)))))K)(KK))))(KK))(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)))
(SI(KK))))))(K(K(KI)))))(S(S(KS)(S(K(SI))(SS(SI)(KK))))(S(KK)
(S(K(S(S(KS)K)))(SI(K(KI)))))))))(K(K(KI))))))))))(K(KI)))))(SI(KK)))))
(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))(S(SII)I(S(S(KS)K)I)))))))K))))
(S(S(KS)(S(KK)(SII)))(K(SI(K(KI)))))))(SII(S(K(S(S(KS)(S(K(S(S(SI(KK))
(KI))))(SS(S(S(KS)(S(KK)(S(KS)(S(K(SI))K)))))(KK))))))(S(S(KS)
(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))(K(S(S(KS)K)))))))(K(S(S(KS)
(S(K(S(S(SI(KK))(KI))))(S(KK)(S(K(SII(S(K(S(S(KS)(S(K(S(K(S(S(KS)(S(KK)
(S(KS)(S(K(SI))K))))(KK)))))(S(S(KS)(S(KK)(S(K(SI(KK)))(SI(KK)))))
(K(SI(KK))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))
(K(SI(K(KI))))))))(K(K(SI(K(KI)))))))))(S(K(SII))(S(K(S(K(SI(K(KI))))))
(S(S(KS)(S(KK)(SI(K(S(K(S(SI(K(KI)))))K)))))(K(S(K(S(SI(KK))))
(S(KK)(SII)))))))))))(K(SI(K(KI))))))))(S(S(KS)K)I)
(SII(S(K(S(K(S(SI(K(KI)))))K))(SII)))))

以下は、入力された文字列を単純に反転させる、Lazy Kのプログラムソースです。 例えば、「stressed」と入力を与えると、「desserts」が出力されます。 このソースはLazy KのJot記法によって記述されています。 先の素数出力コードはLazy KのCL記法によって記述していたのですが、このJot記法では、先のCL記法よりもソースコードの量がかなり多くなります。

1111100011111111100000111111111000001111111000111100111111000111111
1000111100111110001111111000111100111001111111000111100111111111000
1111111110000011111111100000111111110001111111110000011111111100000
1111111000111111100011110011111000111001111111110000011111110001111
0011111100011111111100000111001110011111110001111001111110001111001
1111100011111110001111111000111111111000001111001110011110011111110
0011110011111100011111111100000111001111111000111100111111000111100
1111110001111001110011111110001111111000111100111110001111111000111
1001111110001111001111100011111110001111111000111100111110001111111
0001111001110011111110001111001111100011111110001111001110011111110
0011111111100000111111111000001111001111111000111100111111000111111
1000111100111110001111111000111100111111000111111111000001111111100
0111110001111110001111111110000011110011100111111100011110011100111
0011110011110011111110001111111110000011110011110011111111100000111
1001111111100011111111100000111111111000001111111100011111111100000
1111111110000011111110001111111000111100111110001110011111111100000

以下は、Unlambdaインタープリタの完全な実装を、Lazy KのUnlambda記法で記述したものです。 Unlambda自身で書かれたUnlambdaインタープリタが何個かあるようですが、完全な機能を持つ物はこのLazy Kで記述されたソースの10倍以上の長さがあり、幾つかの機能の欠けた不完全なものでさえ、これの5倍以上の長さがありました。 それだけ、このLazy Kで書かれたソースが短い事に注目しておいて下さい。 (訳注: Unlambdaは、Lazy Kとは別のプログラミング言語。Lazy Kとは共通する部分が多い為、Lazy Kには「Unlambda記法」が前述のCL記法やJot記法と同様に用意されている。Unlambdaの詳細については翻訳:プログラミング言語Unlambdaを参照。)

````sii``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ks``s`k`s`k``si`kk``s`k`s``s``si`
kk`k``si`k`ki``s`kk``s``s`k``s``s`ks``s`kk``s`k``s``s`ksk``s`k``s``s`kski```s`
`siii``s``s`kski``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s`k``s``s`kski``s``s
`ks``s`kk``s`ks``s`k`sik`kk``s``s`ks``s`kk``s`ks``s`k`si``s`kk``s`k`s`k``sii``
s``s`ks``s`k`s`ks``s`k`s`kk``s`k`s`ks`s`k`s``s``s``s``si`kk`k``si`k`ki`k````s`
`s`kski```s``s`ksk```sii``s``s`kski``s`k`s``si`k`kik``s``si`kk`k```sii``s`k``s
`k`s``si`k`kik``sii`kk`k`k``s``s`ks``s`kk``sii`k``si`k`ki``s`k`s`kk``s`k`s``s`
k``s``s`kski``s`k``s``s`ksk```sii``s``s`kski``s``s`ks``s`kk``s`ks``s`k`sik`kk`
`s`k`s`k``s`k`s``si`k``s``s`ks``s``s`ksk`k``s`k`si``s`kk``s`k`s``s`ksk``s`kk``
s`ks``s`kk``s`ks```ss`s``s`ks``s`kk``s`ks``s`k`si```ss`si`kk`kk`k``si`k`kik``s
`k`s``s`k```s``siii``s``s`kski``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s`k``s`k`
s``si`k``s``s`ks``s``s`ksk`k``s`k`si``s`kk``s`k`s``s`ksk``s`kk``s``s`ks``s`k`s
`ks``s`k`s`k`s`ks``s``s`ks``s`kk``s`ks``s`k`s`ks``s`k`s``s`ksk``s`kk``s`k`s`k`
`s`k`sik``s`k`s`k``si`kk``s`k`s``s``si`kk`k``si`k`ki``s`kk``s``s``si`kk`k``s`k
`s``si`kik`k``s``si`k```sii``s`k`s``s`ksk``s`kk``s`k`s`kk``s`k`si``s`kk``sii`k
```sii``s`k``s`k`s``si`kik``sii`k``s`kkk`k`k`ki`k``si`k`kik``s`k`s`k``s`k`s``s
i`k``si`k``si`k``s``s`ksk`k``s``s`ks``s`k`s`ks``s`k`s``s`ks``s``s`ksk`k``s`k`s
i``s`kk``s`k``si`kk``s``s``s``si`k`ki`kk`k``si`k`ki`k`````sii```sii``s``s`kski
``s`k`s``si`kik`k```sii``s`k`s``s`ksk``s`kk``s`k`s`kk``s`k`si``s`kk``sii``s`kk
k`k`k``si`k`kik``s`k`s`k``si`k`ki``s`k`s``s`k``s``s`kski``s`k```s``siii``s``s`
kski``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ks``s`kk``s`ks``s`k`si``s`kk``s``s
`ksk``s``s`ks``s`kk``s`ksk`k``s``s`ks``s`kk``s`ksk`k``s``s`ks``s`kk``s`ksk`k``
s``s`ks``s`kk``s`ks``s`k`sik`kk`k``s`kk``s``s`k``s``s`kski``s``s`ks``s`kk``s`k
s``s`k`sik`kk``s`k`s``si`k``si`k``si`k``s``s`ksk`k``s``s`ks``s`k`si``s`kk``s`k
`si``s`kk``s`k`s`kk``s`k`sikk``s`kk``s`k`s``si`k``si`k``si`k``s`k`si``s`kk``s`
k`s``s`ksk``s`kk``s``s`ks``s`kk``s`ksk`k``s`k`s``s`ks``s`k`si``s`kk``s`k`sik``
s`kkk``s`kk``s`k`s``si`k``si`k``si`k``s`kk``si`k`k`k`k```sii```sii``s``s`kski`
`s`kk``s``s`k``s``s`ksk``s``s`kski``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``si
`k``si`k``si`ki``s`kk``s``s`ks``s`k`sik``s`kk``s`k`s``si`k``si`k``si`k``s``s`k
sk`k``s``s`ksk`k``s`k`s``s`ksk``s`kk``s`k`s`kk``s`k`sik``s`kk``s``s`k``s``s`ks
ki``s`k``s``s`ksk``s``s`kski``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``si`k``si
`k``si`k``s``s`ksk`k`s`k`s`k``s`k`s``si`k``s`k``s``s`kski``s``s`ksk```sii``s``
s`kskik``s`kk``s`k`s``si`k``si`k``si`k``s``s`ksk`k``s``s`ksk`k``s`k`s``s`ksk``
s`kk``s`k`s``s`ksk``s`kk``s`k`s`k`s``s`ksk``s`k`s`kk``s``s`ks``s`kk``s`ks``s`k
k``s`ks``s``s`ksk`k``s`k`sik`k``s``s`ks``s`kk``s`ks``s`k`s`ks``s`k`s`k`si``s`k
`s`kk``s``s`ksk`k``s`k`sik`k``s`kkk``s`kk``s``s`k``s``s`kski``s``s`ks``s`kk``s
`ks``s`k`sik`kk``s`k`s``si`k``si`k``si`k```sii``s`k`s``s`ksk``s`kk``s`k`s`kk``
s`k`si``s`kk``sii``s`kk``s``s`k``s``s`ksk```sii``s``s`kski``s``s`ks``s`kk``s`k
s``s`k`sik`kk``s`k`s``si`k``si`k``si`k``s``s`ksk`k``s``s`ks``s`k`s`ks``s`k`s``
s`ks``s``s`ksk`k``s`k`si``s`kk``s``s``s`k``si`kk``s``s``si`kk`k``si`k`ki`k````
`sii```sii``s``s`kski``s`k`s``si`kkk`k`ki``s`k`s``s`ksk``s`kk``s`ks``s`kk``s`k
s```ss`s``s`ks``s`kk``s`ks``s`k`si```ss`si`kk`kk`k```sii``s`k`s``s`ksk``s`kk``
s`k`s`kk``s`k`si``s`kk``sii``s`kkk`k`ki``s`kk```ss`s``s`ks```ss`s``s`ks``s`kk`
`s`ks``s`k`sik`kk`k``sii``sii`k`k``s`k`s``si`k``s``s`ksk``s`k``s``s`kski`````s
ii``s``s`kski`s``s`ksk```sii``s``s`ksk``s``s`kskik`kk`k`k``si`k`ki``s``s`ks``s
`kk``si`k`k`k`k```sii```sii``s``s`kski`k``s`k`s``si`k```sii```sii``s``s`kskik

ここらを見て、面白そうだと思ったら、どうぞ読み続けてみて下さい。

何故Lazy Kが必要とされるのか

或いは、Unlambdaのどこが間違っていたのかについて。

Brainfuckが(構造化された)命令的プログラミングの蒸留されたエッセンスを得ると同時に、ある言語は関数型プログラミングのエッセンスを得ているべきでした(訳注: 意味が怪しい)。 この「ある言語」の自然な候補は、Unlambdaが適切に思えます。 しかしながら、Unlambdaは非常にprettyな(訳注: 「厄介な」或いは「かわいい」?)言語で、関数的な度合いが私にとっては不十分でした。

Unlambdaのサイトには「関数型プログラミング言語とは、関数がファーストクラスな存在である事です」とあります。 ですが、私はそうではないと考えます。 何故なら、もしこの定義通りとするなら、大抵の高級言語は「関数型」の要件を満たしている事になります。 例えば、Perlですら(そして、多分Cですら(qsortの引数は関数なので))。 よく使われる「関数型プログラミング」という言葉は、「数学で言うところの関数」のような振る舞いの事ではないのですか? 要するに、副作用が無いという事ですよね? そして、純粋関数型言語、と言うのは、全ての関数は、必要とされるのがたった一回きりであるという事です。 その意味で言うのであれば、Unlambdaは「純粋関数型に近い」とすら言えません。 何故なら、UnlambdaのI/Oシステムは、副作用に強く依存しているからです(言い換えると、評価順に影響されるという事です)。 副作用のアイデア(つまり、評価順に依存しているという事)は、コンビネータ算法の設計とは全く相反しますし、Unlambdaプログラムを書く事とフラストレーションの溜まる経験との間に、奇妙な相互作用がある事を感じます。 勿論、よく考えれば、Unlambdaとしては「関数型言語の悪夢がやってくる」ように努力している訳ですし、Unlambdaの作者は「Intercalからインスピレーションを得た」と記しています。

私は、Lazy Kを設計するにあたって、エレガントさにのみ興味がありました。 Lazy Kは、SKIコンビネータ算法の純度において、少しも妥協はしていません。 I/Oの為に、特別なコンビネータを用意するような事はしていません。 抽象除去のルールにも例外はなく、常に正しくショートカットを行えます。 他のほとんどのプログラミング言語(関数型言語と呼ばれるものですら数多く含まれています)を汚染している、評価順によるいざこざはLazy Kにはありません。 もし、Lazy Kプログラムが、ある特定の評価順によって、より適切に動作できるのであれば、Lazy Kインタープリタはそれに気付くでしょう(訳注: 訳に自信無し)。 ここには(Unlambdaの)「d」オペレータはありませんし、あらゆる意味で、この「d」オペレータを定義する方法すらありません(但し、恒等式関数が同等の役割を果たす事を除いて)。 また、引数不要の関数にダミー引数を渡したりする必要もありません。 何故なら、(Lazy Kでは)関数とその返り値は完全に等価であり、交換可能なものだからです。

数学で使われる意味での関数のような、時間的制約が無いプラトニックな領域で、Lazy Kプログラムは動いています。 その事をUnlambdaのサイトでは「純粋な型無しラムダ計算の祝福された領域」と呼んでいます。 丁度、ガベージコレクションがメモリ管理のプロセスをプログラマから隠しているように、参照透過性は評価のプロセスを隠しています。 実際には、マンデルブロ集合の図を表示させたり、Lazy Kで書かれたスクリプトを実行するために必要な幾つかの演算が、漏れなく実装されています。

Lazy KのI/O

副作用無しに入出力を扱うにはどうすればいいのでしょう? ある意味では、入出力は副作用ではありません。 それは言わば、副作用と言うよりは「前作用」「後作用」とでもいったものです。 つまり、Lazy Kでは、プログラムは入出力を、単に、入力予定の場所から来て、出力予定の場所へと去っていく、(コンビネータで組み立てられた)関数として扱います。

入出力ストリームは、1バイト毎に0から255までの自然数に置き換えられたリストの形式になります。 (ファイル等の終了を示す)EOFは、リストの終端ではなく、数値の256で示されます(これは何故かというと、大抵の場合、EOFを特殊なケースで表現するよりは文字(的な何か)で表現した方が扱いやすいからです。もし、リストの終端の方が適するような場合があったら、ちょっと驚きです)。

前述のリストを作る目的の為に必要となるもののうち、ペア(訳注: Lispで使われる、リストを構成する単位)は、ペア「(X . Y)」を「(lambda (f) (f X Y)))」で表現する方式によって実現されます(訳注: これらはLispで記述した場合の表現)。 そして、自然数はチャーチ数(数値nを、n回のfold(畳み込み)操作を行う関数によって表現するという方法)で表現します。

(どのような入力を与えたにせよ)入力リストは無限の長さを持つものとして扱われ、リストの中に一度「256」が出現すると、その後は何個要素を取り出しても「256」しか出て来ません。 出力リストは、最初に出現した「256」を越えては決してチェックされません。 つまり、consセル(ペア)のcar部分が「256」の時、そのセルのcdr部分以降はチェックされずに捨てられます。 具体的には、それぞれのセルのcar部分の値を確認するには「(lambda (x y) x)」のような関数をセルに適用すればいい訳ですし、出力の終わりは単に「(k 256)」と表現する事ができます。 例えば、「(lambda (input) (k 256))」のような関数は、「入力を無視し、何も出力しない」動作を行います。 これは正しい挙動です。

(ちなみに、チャーチ数の256は非常にコンパクトな表現になります。 ラムダ表記(Lisp表記)では「((lambda (n) (n n)) ((lambda (n) (n n)) (lambda (f x) (f (f x)))))」となり、コンビネータ表記では「SII(SII(S(S(KS)K)I))」となります。)

Lazy Kインタープリタの現在の実装は今のところ、256以上のあらゆる値を出力の終端として解釈し、osへのリターンコードとして、その値から256を引いたものを渡します。

ついでに言うと、これらのルールによって、恒等関数は、入力データをそのまま出力データとしてコピーするプログラムになります。 そして、Lazy Kの構文では空のプログラムを恒等関数として扱うので、UNIXコマンドの「cat」(引数指定無し)の振る舞いを、他のどんなプログラミング言語よりもコンパクトに記述する事ができます。

Lazy Kの構文と動作

Lazy Kのモットーは「there's more than one way to do it」つまり「それには複数のやり方がある」(訳注: Perlのモットーとして有名)です。 更に言うならば、正確には「それには四通りの(記述)方法がある」と言えます。 それは、コンビネータ算法スタイル、Unlambdaスタイル、Iotaスタイル、そしてJotスタイルの四つです。

Lazy Kの文法は大体、四つの言語の文法を総合したようなものです(訳注: 訳が怪しい)。

          構文                              動作

  Program  ::= CCExpr                     CCExpr

  CCExpr   ::= CCExpr Expr                (CCExpr Expr)
             | epsilon                    (lambda (x) x)

  Expr     ::= "i"                        (lambda (x) x)
             | Expr'                      Expr'

  IotaExpr ::= "i"                        (lambda (x) (x S K)) ; SとKは下で定義
             | Expr'                      Expr'

  Expr'    ::= "I"                        (lambda (x) x)
             | "K" | "k"                  (lambda (x y) x)
             | "S" | "s"                  (lambda (x y z) ((x z) (y z)))
             | NonemptyJotExpr            NonemptyJotExpr
             | "`" Expr1 Expr2            (Expr1 Expr2)
             | "*" IotaExpr1 IotaExpr2    (IotaExpr1 IotaExpr2)
             | "(" CCExpr ")"             CCExpr

  NonemptyJotExpr
           ::= JotExpr "0"                (JotExpr S K)
             | JotExpr "1"                (lambda (x y) (JotExpr (x y)))

  JotExpr  ::= NonemptyJotExpr            NonemptyJotExpr
             | epsilon                    (lambda (x) x)

文法の曖昧さを除去する為に、「上の定義表内のNonemptyJotExprは、可能な限り最も長い0と1で構成された文字列に常にマッチする」という条件を追加します。

全ての空白は無視されます(これはJot記法の最中も含みます)。 行中の「#」以降はコメントとして扱われます。

この文法によって、CC、Unlambda、Iota、Jotで書かれた式が、(構文的に)不正でないかどうかをほぼ確実に判定する事ができます。 ここにツッコミを入れるとするならば、これらの記法の間には、一つ(だけ)衝突があります。 「i」は、UnlambdaでもIotaでも正しい表現なのですが、それぞれの記法によって「i」の意味が違ってきてしまいます。 とりあえずLazy Kでは、「i」の意味はUnlambdaのものを優先するようにしました。 (これは上の文法表でも厳密にそうなっています。)

この文法は、結果として混ぜこぜにする事を暗に許容し、Lazy Kはそれぞれの四つの言語の構成物を足したものよりも大きくなりました。 例えば、「SII``sii」と書いても「****i*i*i*ii*ii*ii11111110001111111110000011111111100000」と書いても、それは「SII(SII)」と同様に機能します。 私はこの可能性の追求はしません。何故なら、Lazy Kは既に充分に難読化してしまっていると思うからです。

尚、Lazy Kがラムダ算法構文をサポートできないどんな理由もありませんが、少なくとも今はサポートしていません。

Lazy Kの失脚

Lazy Kでインタラクティブなプログラムを書く事自体は難しくはありません。 ですが、Lazy Kでインタラクティブなプログラムを書こうとする者は注意しなくてはなりません。 何故ならば、それは(訳注: 純粋関数型言語に対する)冒涜だからです。

問題は、Lazy Kが、正確な入出力同期メカニズムを持たない事にあります。 参照透過性を持つ言語では、何がどのような順で評価されるかは、ランタイムシステムの判断による公平な(訳注: じゃんけんのような?)ゲームで決定され、厳密に同期が行われる事がありません。

ユーザの名前を尋ね、それから挨拶を表示するようなプログラムは通常、以下のように応答が行われると考えられます。 (尚、以下のテキストの強調部分はユーザからの入力を示します)

あなたの名前は何ですか?
Ben
こんにちわ、Ben!

しかし、原理的には、以下のような応答になるかも知れません。

あなたの名前は何ですか?
こんにちわ、Ben
Ben!

または、

Ben
あなたの名前は何ですか?
こんにちわ、Ben!

或いは、これらの微妙な中間物になるかも知れません。

とは言え、実際にインタラクティブなLazy Kプログラムを書いてみても、この問題が出てくる傾向はありません。 ユーザの入力の終わりを認識し、「こんにちわ」の「こ」を出力する幾つかの方法によっては、最初のケースは発生しません。 このプログラムの最も分かりやすい解決方法は、入力から改行を受け取った段階で、cons(Lispのリスト構築子)を使って「こんにちわ、[name]!」という文字列を式中に生成する事です。 可能なら、これを安全に行いたいと思うかも知れませんが、どのような評価器を使ったとしても、ユーザが改行を入力するという事を前もって証明する方法がありません。

二番目のケースが起こらない事もまた明らかです。 それは、プロンプト(「あなたの名前は何ですか?」)がconsによって生成されるかどうかには関係ありません。 これが正しく動作する理由は、Lazy Kインタープリタが遅延評価を行い、それによって、可能な限り早い段階で、或いは(入力も含めて)可能な限り遅い段階で、出力が生成されるかのどちらかだからです。

つまり、実際には、インタラクティブなソフトを書く際にも問題はありません。 ですが、二番目のケースの解決方法には何か、不快な存在が居座っています。 参照透過なプログラムは評価順に関して、遅延評価が適切に動作する事を頼りにしてはいけないのです。

どうすれば、このモラル的ジレンマから抜け出せるでしょうか? より洗練されたI/Oシステムへと変更するのは色々と難しく、そうするには多分、入出力の同期を正確に行える、HaskellのI/Oシステムをベースにする必要があるでしょう。 私はそれを実装するのは気が進みませんし、現在の方式のシンプルさの方を優先して選びたいです。 楽な方法は、インタラクティブな何かが起こると動作するようなバッチプログラムを書く事でしょう。 これはユーザにプロンプト等を出せない問題等があります。 Lazy K配布物には、この「インタラクティブ」なプログラムのモデルが付属しています。

Lazy Kインタープリタ

巧妙に「lazy」と名付けられたLazy Kインタープリタは、以下のようなコマンドライン命令で使用できます。

lazy [-b] { -e program-code | program-file.lazy } *

引数に「-e」が与えられた場合は引数のLazy Kコードを実行し(perlのように)、引数に「-e」が与えられなかった場合はその名前のファイルに含まれたLazy Kコードを実行します。 複数のコード片を指定する事もでき、その時には後方から関数的に結合されます。 これはLazy KのI/Oモデルの動作の仕方に基づくもので、それぞれのプログラムの出力を次のプログラムの入力へとパイプ連結するのと同じになります。 具体的には、「lazy prog1 prog2 prog3」とシェルから実行した場合は、「lazy prog1 | lazy prog2 | lazy prog3」と同じ事になりますが、より効率的に動作します(そしてバイトストリームの中間結果が作成されなくなります)。 最初のプログラムの入力は常にSTDINとなり、最後のプログラムの出力は常にSTDOUTになります。

もしプログラムを全く指定しなかった場合、空合成が行われ、結果として恒等関数が作られ、「cat」コマンドのような挙動が得られます(但し、本物のcatコマンドよりもずっと遅いですが)。 もしlazyにSTDINからソースコードを読み込ませたい場合、「lazy -」のように指定します。

「-b」オプションを付けると、入出力をバイナリモードで扱うようになります、OSがそれを気にする場合には(Windows等)。 サンプルプログラムの幾つかで問題が発生した時は(Unlambdaインタープリタで問題が発生しやすいようです)、このオプションを試してみてください。

Lazy Kコンパイラ

配布物にLazy Kコンパイラが含まれていますが、これはLazy Kから機械語やCに変換するものではありません。 これは、もっと希望の持てるメタ言語で書かれたプログラムからLazy Kへと変換するものです。 Unlambdaのように、Lazy Kは自分自身をオーソドックスとは言い難いVM用のバイトコードにコンパイルします。 このコンパイラはSchemeで書かれ、「lazier.scm」というファイルに保存されています。

lazier.scmによるコンパイルには、Scheme記法で書かれたラムダ算法を使います。 (lazier.scmによって提供される)「laze」関数は、最適化された抽象除去として機能します。 (注意: Lazierによって提供される各種の束縛はスペシャルフォームではなく通常の関数なので、引数はquoteした状態で渡す必要があります。)

> (laze '(lambda (pair) (pair (lambda (a d) d))))
((s i) (k (k i)))

「lazy-def」関数は、(関数ではなく)マクロを定義できます(訳注: Lazy Kでは「定義」という機能自体が無い為、マクロで代用しているという事だと思われる)。 lazy-defで定義されたマクロは、その場でラムダ算法コードに展開されます。 このマクロはトップレベルとして扱われますが、Schemeとしての束縛からは隠す事ができます。 マクロは他のマクロを参照する事ができます(依存関係がループ状態にならない限りは)。 Schemeの「eqv?」で判定できる範囲であれば、マクロの名前はどのようなものでも使えます。 つまり、マクロの名前にはシンボルだけではなく、数値や文字や#tや#fや空リスト等を指定する事もできます。

> (lazy-def 'cdr '(lambda (pair) (pair (lambda (a d) d))))
> (laze 'cdr)
((s i) (k (k i)))
> (laze '(cdr x))
(x (k i))
> (lazy-def '(cdr pair) '(pair (lambda (a d) d)))
> (laze 'cdr)
((s i) (k (k i)))
> (laze '(cdr x))
(x (k i))

lazeが出力したラムダ算法コードをLazy Kのソースコードとして出力する、四つの関数があります。

> (lazy-def '(myprog input) '(cdr (cdr input)))
> (laze 'myprog)
((s ((s i) (k (k i)))) (k (k i)))
> (print-as-cc (laze 'myprog))
S(SI(K(KI)))(K(KI))
> (print-as-unlambda (laze 'myprog))
``s``si`k`ki`k`ki
> (print-as-iota (laze 'myprog))
***i*i*i*ii***i*i*i*ii*ii**i*i*ii**i*i*ii*ii**i*i*ii**i*i*ii*ii
> (print-as-jot (laze 'myprog))
11111110001111111000111111111000001111001111001111111110000011110011110011111111100000

もしプログラミングが地金のようなものに感じるなら、Lazierは、自由変数を保存する事で抽象除去のプロセスをスルーできるようにし、Lazy Kの「テンプレート」に手で他の式を差し込めるようにしているのです(訳注: 「地金の〜」の辺りが意味不明)。

> (lazy-def '(cons a b) '(lambda (f) (f a b)))
> (print-as-unlambda (laze 'cons))
``s``s`ks``s`kk``s`ks``s`k`sik`kk
> (print-as-unlambda (laze '(cons p)))
``s`k`s``si`k[p]k
> (print-as-unlambda (laze '(cons p q)))
``s``si`k[p]`k[q]

「prelude.scm」というファイルには、「cons」「if」「+」といった、便利な各種マクロが定義されています。 しかし、Yコンビネータ等を除いて、高階コンビネータが全然無い事が目立ちます(訳注: Yコンビネータもコメントアウトされてるように見える)。 私は毎回、手でこれらを書かなくてはなりませんでした。 ごめんなさい。 「prelude-numbers.scm」というファイルには、コードサイズに対して最適化された、128までのチャーチ数が定義されています。

Lazierプログラムを書く上で最も困難な部分には、デバッグの他に、マクロの多重インクルードによるコードの膨張を避ける事があります。 もし複雑な「関数」をマクロとして書き、それを何回も使うのであれば、その「関数」を変数(訳注: のようなもの?)に束縛し、コード内のあらゆる場所の周辺をバイパスさせ、必要な場所で呼び出すようにする必要があります。 それか、普通に多重インクルードのマクロでしのぐかです。 前者(変数を実装)の解決方法は多分、後者(マクロそのまま利用)よりも効果が小さいです。 というのも前者では、新しい変数束縛を追加する事自体が、コンビネータレベルでのコードの大膨張を起こすからです。

サンプルコード

以下は、Lazy Kの配布物に含まれるサンプルコードのリスト(簡単な説明付き)です。 更なる詳細はそれらのファイル自身に含まれています、大体は。

ab.scm
ab.lazy
「ABABABAB...」を延々と表示し続けます。
befunge.scm
befunge.lazy
Befunge-93のインタプリタです。「?」以外の全ての命令をサポートしています。
brainfuck.scm
bf2lazy.c
Brainfuckで書かれたプログラムをLazy Kで書かれたプログラムへと変換するコンパイラです。あらゆるBrainfuckの命令を固定長のLazy Kコードに変換できます。「[」命令と「]」命令で挟まれるコードブロックは、実行時にお互いを発見します(訳注: 訳が微妙)。
calc.scm
calc.lazy
任意精度の整数に対して足し算、掛け算、指数を計算できる、中置式(つまり普通の算数表記)の計算機です。
fib.scm
fib.lazy
「行ごとに、出力される*の数がフィボナッチ数になっている」Unlambda配布物に含まれるサンプルコードの、Lazy K版です。
iota-in-iota.scm
iota-in-iota.lazy
jot-in-jot.scm
jot-in-jot.lazy
Iota及びJot言語のサブセット(訳注: 一部の実装が抜けているが大部分は実装されているもの)のインタープリタです。Iotaインタープリタは1651個のシンボルを、Jotインタープリタは1541個のシンボルを使って書かれています(訳注: 訳が間違ってるかも)。
mergesort.scm
sort.lazy
bwt.lazy
lazy listを利用した、マージソートのナイスな実装です(lazy listは大抵のアルゴリズムに対して、良い方向に働くように思えます)。これには、UNIXの「sort」コマンドとして機能するものと、Burrows-Wheelerブロックソートのユーティリティの、二つのアプリケーションが含まれています。
powers2.scm
powers2.lazy
2の累乗を出力するという事以外は、fibと同じです。
primes.scm
primes.lazy
素数を10進数で表示します。
quine.lazy 2792個のシンボルを用いて書かれた、quine(自分自身のソースコードを出力する)プログラムです。これにはLazierコードは含まれていませんが、多分、Lazy Kのコードを見れば可能推測です(またはこれを実行した出力を……)。
reverse.scm
reverse.lazy
入力された文字の並び順を逆にします。
rot13.scm
rot13.lazy
ja.wikipedia:ROT13暗号の実装です。二重のrot13、最もよく議論されたフォーラムでの標準、コマンドラインから二回、rot13.lazyを指定します。(訳注: 訳が分からなかった。要は二回実行すれば元に戻る、という事だと思うが……)
unlambda.scm
unlambda.lazy
Unlambdaインタープリタです。入力関数及び「#」コメントを含む、Unlambda 2.0.0の機能を全てサポートしています。

他にも、幾つか明らかになっているプロジェクトがあります。

Falseインタープリタを書くのも楽しい事でしょう(最高に難しいという事はありません)。

バグと欠点


訳者による感想 / 要約 / その他


コメントその他

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

尚、明らかな訳の間違い等の場合は、直接本文を直してもらって構いません。


最終更新 : 2009/04/03 17:13:29 JST