いものやま。

雑多な知識の寄せ集め

「Lucid, the Dataflow Programming Language」を翻訳してみた。(その13)

ちょっと間が空いてしまったけど、前回の続き。

2.8 無限プログラミング

Iswimファミリについてのこれまでの議論は、従来のオブジェクトが有限な代数に限定したものだった。
この形式のIswimは、ALGOLのような従来の命令型言語の再帰的サブセットに多かれ少なかれ一致している。
この制限により、Iswimプログラミングは本質的に、従来のプログラミングの、とても厳密に制限され構造化された形式となっている。

しかし、言語の代数をこのような「従来の」ものに限定する特別な理由はない。
オブジェクトが有限でない代数によるIswimファミリには、興味深く有用なものがたくさんある。
これらの言語は、従来の言語の単なるサブセットよりもはるかに豊かで、まったく新しいプログラミング手法を可能にする。

Iswimファミリで興味深いメンバの一例は、POP-2代数 Pのような代数 Hに基づいたもので、その宇宙(universe)には有限リストに加えて無限リストが含まれている。
リストは無限であってもよく、そのリストの要素は Hの世界の任意の要素であっていい(リストでもいい)。
このアイディアは、以下の「ドメイン方程式」によっていくらか正確にすることが出来て、POP-2の非リストなデータオブジェクトのドメイン Dとして、 Hの宇宙 H_0を定義する:

 L = 1 + H_0 \times L \quad \mathrm{and} \quad H_0 = D + L

最初の式は、「ハイパーリスト」(ドメイン Lの要素)が、空であるか(空リストはただ1つだけある)、 H_0の1つの要素(ヘッド(head))と1つのハイパーリスト(テイル(tail))で構成されていることを示している。
次の式は、 H_0の要素が Dの要素(文字列、数値、単語など)またはハイパーリストのいずれかであることを示している。
これらの式は、 Hでの演算は指定していなく、 Hの宇宙 H_0のみを指定しているので、 H自体は指定されていない。
しかし、これらの式の解が得られれば、通常のリスト演算(hdtl::などの記号で表される)は簡単に定義できる。

実際、これらのドメイン方程式は、無限の長さのリストがあるという解を持つ。
1つ注意しなければならない点は、ドメイン H_0にも豊富な種類の部分的(partial)オブジェクトが含まれていることである。
ドメイン Dでは、部分的(非標準)オブジェクトは \perpだけであり、他のすべてのオブジェクトは、正常で、健全な文字列、単語、整数などであった。
しかし、 H_0では、「混合」リストーーつまり、要素の一部(必ずしもすべてではない)が \perpであるようなリストーーを許可する必要がある。
また、ある時点で「テイルオフ(tail off、尻尾切り?)」する必要があるーーこれは、tlが何度も適用される場合に、ある時点で \perpと評価することである。
最後に、リストの構成要素は他のリストでもよいので、構成要素として部分的リストを持つようなリストを許可する必要がある。
このリストの要素は部分的リストであってもいいし、そうでなくてもいい。
要するに、ドメイン H_0は、すべてのオブジェクトの「純白さ」と \perpの「漆黒さ」との間に無限の多様な濃淡を許している。

(※正直、何を言っているのか分からないのだけど、操作的に考えたときに「無限の操作」を意味する \perpに対して、無限の長さを持つリストも操作が(場合によって)無限になる、ということを言いたいのだと思われる)

Iswim( H)でプログラミングすることと、「有限」オブジェクトの代数 AによるIswim( A)でプログラミングすることの大きな違いの1つは、(前者の場合)変数を再帰的(循環的)に定義するのに意味があるということである。
もう1つの違いは、終了条件なしで再帰関数定義を与えることも意味があるということである。
その場合、「結果」が無限であるので、評価は「永遠に」実行されることになる。

例えば、以下の定義を考えてみる:

 X = 1 \mathrm{::} X;

Iswim( P)では、この定義は \perp Xと関連づける。
というのも、 Pは有限リストのみを持ち、この定義を満たすような有限リストは存在しないからである。
しかし、Iswim( H)には無限を使った解が存在する。
すなわち、

[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...]

という無限に1が続くリストである。
さらに、これはこの方程式の最小解であり、したがって変数 Xに関連付けられた値となる。
次の「非終端」の定義

 \mathit{bump}(X) = \left( \mathit{hd}(X) + 1 \right) \mathrm{::} \mathit{bump}(\mathit{tl}(X));

は、完全に理に適った関数を定義している。
無限の数のリストを引数として期待し、引数の各要素を1ずつ増やすことによって形成される無限のリストを結果として返す。

演算子の結合の優先度が分かりづらい(+ > ::)ので、括弧を追加している。

これを使って、

 \mathit{nats} = 0 \mathrm{::} \mathit{bump}(\mathit{nats});

と定義すれば、 \mathit{nat}はすべての自然数(※ここでは0も自然数に入れている)の無限リスト

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ...]

を定義する。
このリストは、この方程式の最小の(そして、実際のところ、唯一の)解となっている。

無限オブジェクトを持つ代数は、非常に異なったスタイルのIswimプログラミングを可能にし、とてもエレガントな(ただし従来とはかなり異なるかもしれない)プログラムを作れるようにする。
すべての素数の無限リスト

[2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 51 53 ...]

を出力(値)とするようなIswim( H)プログラムは、以下のようになる:

P
where
    nats = 1 :: bump(nats)
    where
        bump(X) = hd(X) + 1 :: bump(tl(X));
    end
    P = 2 :: primesin(tl(tl(nats)))
    where
        primesin(L) = if isprime(hd(L))
                      then hd(L)::primesin(tl(L))
                      else primesin(tl(L)) fi;
        isprime(n) = nodivsin(P)
        where
            nodivsin(Q) = (q * q > n) or ((n mod q ne 0) and nodivsin(tl(Q)))
            where
                q = hd(Q);
            end
        end
    end
end

このプログラムは、自然数の無限リストからすべての非素数を取り除くように動作する。
素数性の確認では、構築中のすべての素数の無限リスト Pを使用している。

Iswimファミリの「無限を扱える」メンバのインタプリタがすでに数多く存在している。
最もよく知られている(そして最初に現れた)のは、Turner(1979)のSASLとHenderson(1980)のLispkitである。
これらの言語は、元の高階言語に基づいていて、IswimではなくISWIMのバリエーションとなっている。
著者の1人(William W. Wadge)は、Warwick大学の同僚と一緒に、先に説明した代数 Hに基づいて、このような「ラムダ微積分」言語を実装した。
(本質的にIswim( H)である)この言語は、PIFL(POP-2 Influenced Functional Language)と呼ばれ、学部の関数型プログラミングの授業で使用されている。

PIFLはpLucidの「仲間の」言語で、同じ代数に基づいていて、同じ構文規則を使用している。
その結果、この2つの言語には大きな重なりがある(PIFLでもwhere再帰的となっている)。
多くのPIFLプログラムは(構文的に)pLucidプログラムでもあり、同じ出力を生成する。
pLucidとPIFLとの交わりが、(大雑把に言えば)一階のPIFL、すなわちIswim( P)となっている。
(PIFLではリストの再帰的定義が必ず \perpを返すわけではないので、ぴったりIswim( P)というわけではない)
Iswim( P)ーー言い換えれば一階で有限なPIFLーーのことを、「pIswim」と呼ぶことにする。
Iswim( H)(一階で無限なPIFL)のことは、「HyperpIswim」と呼ぶことにする。
したがって、pIswimはpLucidの部分言語であり、HyperpIswimはPIFLの部分言語である。
この節の例は、すべてのHyperpIswimのプログラムであり、(したがって)PIFLのプログラムでもある。

無限オブジェクトでの計算を可能にするIswimファミリのメンバは、より洗練された実装を必要とすることは明らかである。
Iswim( H)のような言語に直面したとき、Iswim( P)のような言語を(かろうじて)カバーしていた従来の逐次的な解釈は、完全に破綻することになる。
特に、変数の再帰的な定義は、完全に理に適っていて有用であるものの、代入文と見做しては意味をなさなくなる。

しかし、他の2つの実装方法(すなわち、簡約(reduction)と要求駆動(demand driven))は、拡張できる。
簡約による方法は最も簡単に拡張できる。
以下のような、無限のデータに対する演算を含む式をどうやって書き換えるかという式を使うだけである。

 \mathit{hd}(X \mathrm{::} Y ) = X;

PIFLインタプリタは、SASLやLispkitの実装と同様に、この方法で動作する。

要求駆動も拡張できるが、ここではさらに注意を要する。
ある式の値が無限の場合、その式の値を要求することは出来ない。
なので、代わりにその値の一部、すなわち、他の部分的な要求を満たすのに必要な分だけを要求しなければならない。
計算の過程で、同じ値のより多くの部分が要求されるかもしれないが、一度にすべての値を必要とすることはない(これはpLucidインタープリタの仕組みとなっている)。
しかし、オブジェクトの「一部」を構成する概念は問題のオブジェクトの性質に依存するため、一般的な要求駆動インタープリタではない。


ということで、無限リストに関する話。

Haskellで(遅延評価によって)無限リストを扱えるのと同様に、Iswimでも無限リストを含むような代数を考えることで、無限リストを使ったプログラミングが可能になる、と。
これを実際に実装した言語がPIFLという言語で、pLucidとは兄弟のような関係になっているっぽい。

というのも、pLucidだとリスト自体は有限のものしか扱えないはずなので、PIFLはpLucidの部分言語というわけではないから。
けど、じゃあpLucidは無限を扱えないのかというと、そんなことはなくて、pLucidではPIFLと違って変数自体が時間方向に関して無限リストのように伸びていっている。

対比で書くと、時間という概念は持ち込まずに無限リストというオブジェクトを作り上げたPIFLと、時間という概念を持ち込んで時間方向に無限リストにしたpLucidという感じ。
どちらも無限を扱えるように拡張されているのだけど、その伸びていく方向が違う。
なので、兄弟のような関係と言える。


何はともあれ、2章はこれで終わりで、長かったIswimの話もここまで。
3章は、このIswimに時間方向の値のリストを持つ代数を入れたLuswimという言語を見ていくことになるっぽい。

今日はここまで!