いものやま。

雑多な知識の寄せ集め

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

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

1.8 Lucidーーバランスのとれた言語

Lucidでは、応用数学の他の分野で見られるような、静的と動的の間の調和のプログラミングを復元しようとしている。

Lucidは実際には非手続き型言語だが、決して純粋に静的な計算の視点に基づくものではない。
Lucid文はただの等式だが、これらの文と代入文の間の類似点は、単なる表面的なものであったり、構文的なものであったりしない。
節(クロージャ)の変数は、時間とともに変化する値を持つと考えることが出来る。
ユーザによって定義された関数は、実際、無限の一連のデータ間の対応を示していて、さらに実際フィルターと考えることが出来る。
sqroot(avg(square(a)))というLucidの式と、対応するUNIXのパイプ

square < a | avg | sqroot

の類似点は、構文が示すよりもずっと深い。
Lucidの時間的な演算は、プログラマに反復やデータフローの計算(フィルタや「配管」)を直接的かつ自然な方法で実現できるようにする。

Lucidプログラマは、プログラムの出力(意味)は正確に指定するが、どう計算が実行されるべきかは指し示したりしない。
プログラマには、演算について考えることができ、演算を実行する特定の順序、データフローの速度、バッファの容量、プロトコルなどの詳細について心配する必要がない。
この「暗黙的な」アプローチは、実装にもより自由度を与える。
Lucidによってプログラマは不要なシーケンスの指定を避けることができ、これは計算を並行して行うのにずっとよいスコープを与える。

特にLucidは、他の「データフロー言語」に比べて1つ大きな利点がある。
それは、プログラマはデータフロー(さらに言えば単一のデータフローパラダイム)に全体としては制限されず、他の演算コンセプトで考えることも出来ることである。
特に、プログラマは、ある文を反復アルゴリズムの指定として理解することが出来る。
これにより、プログラマは、変数を、計算の過程で繰り返し修正された値が保存された(記憶された)ものとして考えることが出来る。
例えば、以下の等式

i = 1 fby i + 1;
f = 1 fby f * i;

は、データフローネットワークを指定するものとして理解することは確かに出来る。
しかし、このケースでは、データフローとしてみるのは、やや不自然である。
上記のような等式は、ifの両方を1に初期化し、これらの値を繰り返し更新する反復としてみると、はるかに簡単に理解できる。
反復の各ステップで、iの新しい値はiの古い値に1を加算したものであり、fの新しい値はfの古い値とiの古い値を掛けたものである。

もちろん、反復はデータフローではなく、データフロー言語には存在しないだろう、という反論がされるだろう。
私たちは、前提には同意するが、結論には同意しない。
データフロープログラマは、他の「モード」の計算は利用できないべきなのだろうか?
「純粋な」データフローで、すべてが削減されるべきなのだろうか?
データフローは、反復などの他の形式の計算で補完されたときに、最も効果的である。
これは概念レベルだけでなく物理的にも正しい。
私たちは、データフローネットワークが本来的に間違っているものではないと分かっていて、それは、何らかの反復アルゴリズムに従って入力を処理する、メモリを持ったフィルタを持っている(例のプログラムのsqrootフィルタは、この視点でのケースである)
一方、実際には、マシンが「純粋な」データフローを通じてすべてを行うことがより簡単になるかもしれない。
重要な点は、Lucidはプログラマにも実装にもデータフローか反復かの選択を強制しないことである。
実際、プログラマからの視点からの計算(私たちはそれを「仮想実装」と呼ぶことがある)は、実際の実装と大きく異なる可能性がある。
実際の実装では、データフローをまったく使用しない場合すらある。
(実際、反復とパイプラインのデータフローしか使用しないのでは実装できない多くの有用なLucidプログラムが存在する)

それにもかかわらず、Lucidは依然として「データフロー言語」である。
なぜなら、

  1. Lucidプログラムの大部分は、パイプラインデータフローモデルで計算を書くことが出来、そして、そのモデルで読んで理解することが出来る。
  2. パイプラインまたは他の形式のデータフローを使用できるので、これらのプログラムを効果的に実装することが出来る。

からである。

Lucidのアプローチは、他のデータフロー言語とは異なり、

  1. Lucidは厳密に非手続き型言語(実際、関数型)であり、静的で記述的な意味論的を持つ。
  2. しかし同時に、プログラマはデータフローの意味で操作を考えることが出来る。
  3. しかし、プログラマは、少なくとも詳細については、実際の実装を理解する必要がない。
  4. 他の形式の操作(すなわち、パイプラインデータフロー以外の操作)も、プログラマおよび実装者は同様に利用可能である。

Lucidのアプローチは、最終的に効率と有効性(単純性と一般性)の両方を達成する可能性を提供する。
プログラマは、計算が実行される途中で、何らかの制御(「影響力」と言った方がいいかもしれない)を持っている。
プログラムは非効率である必要はない。
同時に、操作の面については指し示すのみで指定はしないので、プログラマはグロテスクな計算全体の詳細を計画するという手間を免れる。
したがって、プログラマは、命令型プログラマが自分のマシンを制御するために必要とするすべてのレバー、ハンドル、スイッチといった余分な「汚い」機能を必要としない。
それゆえ、言語は比較的単純なままでいられる。

もちろん、多くの人々は私たちのアプローチに疑念を抱いている。
彼らは、それはあまりに都合が良すぎて、真実ではないと感じている。

命令型言語の問題の根本的な原因は、マシンに対する矛盾した態度であることはすでに見てきた。
マシンから離れたいと思うと同時に、マシンに近づきたいと思う欲望がある。
これは、プログラマや言語設計者が直面する永遠のジレンマであり、すべての言語やシステムで発生する一般的な現象だと多くの人は考えている。
彼らのうちの何人か(主にカウボーイ達)は、Lucidはマシンに十分に接近せず、ポインタ変数やエラー終了、あるいはデータフローネットワークの実行時再配線を許さないので、あまりに単純で数学的であり、失敗するだろうと考えている。
他の人たち(神秘主義者達の何人か)は、逆の理由からLucidは失敗する運命にあると思っている。
彼らはLucidがデータフローに基づいているので汚れていると考えてて、(マシンがフォン・ノイマン・マシンであるかどうかにかかわらず)マシンに近すぎると思っている。
彼らは、私たちが原則を裏切り、操作的な考えを強調して「カウボーイ」になったんだと感じている。
Lucidの文は本物の等式で、Lucidの関数や変数は本物の関数である事実にもかかわらず、Lucidは「関数型」ではないと言っている。

言うまでもないが、私たちはこれらの意見には同意しない。
高レベルであることと効率的であることは同時には満たせないということを命令型言語が見出したというのは、確かに正しい。
しかし、私たちはこれに同意しない。
というのも、このジレンマは、きれいな理想主義と汚い実践との間に、恒久的で悲劇的だが避けられない格差があるという一つの例に過ぎないからである。
私たちは、より簡単な説明があると感じている。

プログラミングに関する多くの著作では、プログラマの仕事は、与えられたマシンに何かをさせることであると思われている。
そして、言語は、マシンが何を実行すべきなのかを人間が伝える手段であると思われている。
この描画がまさに誤解を招いている。
マシンはただ与えられるものではなく、プログラマを喜ばせるために存在しているわけでもない。
言語は、プログラマが任意の欲望をコンピュータに伝えるためのツールではない。
マシンは問題を解決するために存在しているのである。
例えば、飛行機の飛行をシミュレートしたり、製油所を制御したり、ガスの請求書を計算したり、といった具合だ。
この文脈におけるプログラマの役割は、マシンに問題を伝えることであり、プログラミング言語はそのためのツールとなる。
プログラマがマシンから離れたいという理由は、問題に近づくためである。
フォン・ノイマン・マシンの問題は、問題から離れすぎていることである。
それらは、やらなければならない仕事に適していない。

多くのアプリケーションでは、大規模な並列性(ほとんどの種類の数値解析)やネットワークを流れるデータ(ほとんどの形式の会計)を使用する計算がかなり自然に示唆されている。
フォン・ノイマン・マシン(あるいはむしろ、そのようなマシンからなるシステム)は、どちらの計算にも適していなくて、そのギャップを埋める必要があるのは、過負荷な言語を使用する貧弱なプログラマである。
プログラマが計算をどのように実行するかを単に指示するだけでは不十分であり、最適化を実現するための詳細を残しておかなければならない。
必要とされる計算の種類と提供される計算の種類との間の距離が、大きすぎる。
プログラマは、計算の詳細を自分自身で担当し、人間の知能をこのタスクに適用する必要がある。
そして、言語設計者は、問題指向の機能とマシン指向の機能の両方を提供する必要がある。
問題とマシンがあまりにもマッチしていないので、出来上がった言語が不幸な妥協となるのは驚くことではない。
命令型言語の設計者は、ハードウェアの問題をソフトウェアによって解決するという不可能をやろうとしていることになる。
ソフトウェアの危機は、本当はハードウェアの危機なのである!

新たな言語は新しいマシンを伴わない限り、危機を解決することは出来ない。
正式なデータフローマシンがあれば、マシンと多くのアプリケーションの間のギャップは大幅に狭くなる。
したがって、これらのアプリケーションの場合、データフローに基づく言語は、マシンが非効率的に使用されていても、マシンから遠く離れずに問題に近づくことが出来る。
プログラマは、計算を指定する負担から解放され、代わりに計算を指示するだけでいい。
これにより、言語は手続き的ではなくなり、余分な、汚れた機能を持たないことが可能になる。

したがって、私たちの見解は、新しい言語と新しい機械を一緒に開発しなければならないということになる。
これは、有名な日本の「第5世代」プロジェクトの見解である。
内田俊一(1982、p.1)の言葉では、

しかし今日のコンピュータシステムは、最初の世代以来、あらゆる種類の改良がなされているが、依然フォン・ノイマンの計算モデルに基づいている。
本質的に、起こったのは、ソフトウェアシステムが新しく洗練されたアプリケーションに対応するように拡張されたことである。
現在のコンピュータで使用されているソフトウェアシステムは、大きく複雑になりすぎていて、生産性、信頼性、および保守性を維持できなくなっている。
また、従来のアーキテクチャに基づくハードウェアシステムも、これらの複雑なソフトウェアシステムをサポートするための計算能力およびメモリ空間の改善の点で限界に近づいている。

日本のプロジェクトは、PROLOGという言語と論理的な演繹としての計算の考え方に大部分が基づいている。 PROLOGを使用するプログラマは、必要なデータを生成するための正確なレシピを供給する必要がない。
代わりに、必要なデータに関する論理的な主張の集まりを提示する。
PROLOGの実装は、要件を満たすデータを自動的に検索する。
検索は、プログラマによって与えられた主張の論理的な結果を実際に調査することになる。
例えば、PROLOGプログラマ

path(Coventry, Reading, X)

と入力すると(ここではXは変数)、PROLOGの実装は最終的に以下のように答えるだろう。

X = [Coventry, Birmingham, Oxford, Reading]

この答えから、プログラマ

path(Coventry, Reading, [Coventry, Birmingham, Oxford, Reading ])

がプログラム内の他の文の論理的な結果であると結論づけることが出来る。
これらの文(ここには示されていない)は、鉄道網におけるある町から別の町への経路の概念を公理化するかもしれない。
プログラマは、明示的な経路探索アルゴリズムを与える必要はない。
代わりに、プログラムが示しているパスを検索することによって、実装はパスを検出する。
PROLOGでは、計算は制御された演繹の一形式である。

PROLOGはバランスのとれた言語の良い例である。
PROLOGのプログラム(少なくとも「純粋な」PROLOGのプログラム)は、一階論理の主張の集合として静的に理解することが出来る。
同時に、プログラマは、文を、深さ優先検索アルゴリズムを使った書き換え規則として理解することが出来る。
2つのビューは基本的に補完的である。
PROLOGプログラマは、プログラムを合理的に効率的なものにするために、検索戦略を理解する必要があるが、振る舞いのあらゆる面の詳細を知る必要はない。
自分のプログラムの正確さだけに関心を持っているのであれば、静的な文の主張の意味論で十分である。

日本の研究グループはPROLOGの研究について間違いなく賢明な決定を下した。
PROLOGは、日本のグループが念頭に置いている人工知能アプリケーションに適している。
しかし、私たちは、PROLOGが唯一の第5世代のプログラミング言語になることを強く疑っている。
確かに、インテリジェントな知識ベースシステム(IKBS)とAIアプリケーションの重要性は今後ますます高まるだろう。
確かに、PROLOGなどの言語はますます使用されるようになるだろう。
それにもかかわらず、(会計や数値分析のような)より直接的な「日常のよくある」計算も常に実行される。
PROLOGはこの種の問題にはまったく適していない。
たとえば、PROLOGプログラマは独自の関数を定義することはできず、算術演算でさえあまり立派なものではない。
AIおよびIKBSアプリケーション自体には、PROLOGスタイルの検索とバックトラッキングに加えて、十分に考慮された決まり切った(cut-and-dried)計算が多数含まれている。
PROLOGが他の言語や計算形式の助けを借りずにどれくらい自力で行うことができるかはまだ分からない。
日本のグループは確かに推論計算の限界を認識しており、データフローのアーキテクチャと言語(Lucidも含まれている)を調べている。
将来、「推論」プログラミング言語PROLOGなど)やデータフロー言語(Lucidなど)が協力して使用されることもあるだろう。
PROLOGは、エンドユーザーとのインターフェイス(これは非常に単純である)と、より「エキゾチックな」アプリケーションのプログラミングに使用できる。
一方、Lucidは、データフローマシンをプログラムして、より一般的な、舞台裏での計算を実行するために使用されるだろう。

もちろん、PROLOGとLucidはどちらもフォン・ノイマン・マシンで実装できる。
PROLOGはLucidよりも簡単に実装できる)
ちょっとした作業で、Lucidの合理的なサブセットを受け入れる、許容できる効率的な最適化コンパイラを作成することが出来る。
多くのアプリケーションでは、効率の程度は十分であり、あるいは少なくとも、非効率性はクリーンな非手続き型言語を使用する利点によって補われる。
しかし、システムプログラミングのような他のアプリケーションでは、非手続き型言語はCと競合することはできないと言うのは公平である。
というのは、非手続き型言語は単純に(フォン・ノイマン)マシンには十分に近づけないからである。
同様に、どんな命令型言語も(たとえデーフローマシンで実行されていたとしても)データフローマシン上で実行されるデータフロー言語と競合することは出来ない。

「丘の上のばか」は半分しか行けていない。
つまり、彼らは他のものを誠実に採用することなく、不適切な形の計算を拒否した。
彼らは、下にある谷に退廃的なフォン・ノイマンのアプローチの汚物と腐敗を見ているが、まだ山を越えてはいない。
彼らはまだ新しい時代のコンピューティングの預言者たちにコミットしていない。
彼らはまだ山の上で待ったままで、まだ反対側の豊かな地に降りる準備が出来ていない。

1.9 LucidーーThe Dataflow Programming Language?

この本のタイトルは意図的に曖昧にした。
「Lucid, the dataflow programming language」というフレーズは、「Lucid、(他の多くのものと同様の)データフロープログラミング言語」を意味する可能性がある。
しかし、「Lucidは、唯一のデータフロープログラミング言語」を意味することも出来る。
ある意味では、両方の読みが適切であると感じているので、私たちは曖昧な形でタイトルに残した。

読者は今、Lucid自体がデータフロー(プログラミング)言語とみなされる根拠を理解する必要がある。
明確ではないのは、データフロー言語と考えられる理由である。

実際にはすでにかなりの数のデータフロー言語が存在している。
「データフロー言語」という用語は、プログラマがデータフロー計算を指定するプログラムを書くことができる言語を意味する場合、これらの言語を以下のように分類することが可能である。

1. FORTRANなどの従来の命令型言語

実際には、命令型のプログラムをコンパイルしてデータフローマシン上で実行することは可能である。
最も単純なコンパイルアルゴリズムは、データフローアーキテクチャによって提供される並列性を利用しない。
より洗練された技法では、プログラムを解析して隠れた並列性(隠された、というのは、つまり言語の逐次的性質によって)を検出することが必要となるが、この技法がどれほど成功するかはまだ分からない。
命令型のプログラムを書くのに費やされた膨大な努力を考えれば、試してみる価値は確かにある。
しかし、長期的な見通しは、FORTRANと会社が徐々に段階的に廃止され、適切なデータフロー言語に置き換えられることでなければならない。

2. ADAのような拡張命令型言語

同時に動作する2つ以上の計算をプログラマが設定できるように、従来の命令型言語に機能を加えることは可能である。
これらの新機能は、通信プロセス(CSP)、コルーチン(Kahn-McQueen)、フィルタとパイプライン(UNIX)などのさまざまな運用上のアイデアに基づいている。
確かに、これらの言語はデータフローアーキテクチャを利用することが出来る。
それらの多くは、Lucidに近く、プログラマはデータフローの観点から操作を考えることが意図され、奨励されている。
残念なことに、拡張された言語は、すでに十分に悪い通常の命令型言語よりもさらに複雑になる傾向がある。
また、この新機能は、データフローのアプローチとは全く相容れない、一般的な中央データストアの概念に基づいていることもある。
より直接的にデータフローに基づくものであっても、依然として奇妙で、複雑で、使用するのが難しい場合がある。
私たちは、これらの「リッチすぎる」言語が未来の波を表しているとは信じられない。
並列処理を強制する機能を追加するのではなく、不必要な逐次性をプログラマに指定させるような(または少なくとも推奨するような)機能(代入文など)を削除する必要がある。

3. 制限された命令型言語、例えば、IDのような単一代入言語

代入文の使用に関する特定の制限により、実装がプログラム内で並列性を見つけて利用することがずっと容易になることは、長い間知られていた。
制約があってもプログラムを書くのは難しくなく、単一代入プログラミングは非常に厳密な構造化プログラミングのようなものである。
もし、成功を(a)重要なプログラムを努力なしに正しく書くことが可能であり、(b)最大限に引き出された洗練された前処理とプログラムの分析なしにデータフローアーキテクチャーの優れたメリットを得られることとするならば、単一代入言語は最初に実際に成功したデータフロー言語である。
それにもかかわらず、単一代入言語が未来の波であるとは考えにくい。
代入文は、フォン・ノイマンの計算方法による二日酔いである。
なぜそれを制限するだけで済ますのだろうか?
完全に排除してみてはどうだろうか?

4. SASL、FGL、または、Lispkitなどの汎用関数型プログラミング言語

代入が禁止されているこれらの言語は、LISPが近代化されれサニタイズされたバージョンである。
リストは通常、主なデータ構造である。
これらの言語は、特に無限リストが許可されている場合、データフロー言語として正常に使用できる。
これらの無限リストが(よく彼らがそうするように)履歴の表現に使われる場合、これらの言語でのプログラミングはLucidでのプログラミングと非常によく似ている。
これらの言語の問題は、私たちが見ているように、まだあまりにも一般的なことである。
リストは履歴として使用する必要はなく、はるかに複雑な構造を形成することが出来る。
リストの要素は任意のオブジェクトにすることが出来、関数は任意のオブジェクトに適用(および生成)することが出来る。
プログラマはこの一般性のために重い代償を払うことになるというのが私たちの考えである。
一般的なLISPライクな言語は実装するのがはるかに難しく、特定の技法(タグ付きの要求解釈など)は適用されない。
一般性はプログラマだけでなく実装者にも影響する。
Lucidのプログラマは、xとyを時間と共に変化する値と考えることができ、それらの(変化する)合計をx + yとして書くことが出来る。
しかし、LISPプログラマは、xとyが本当に無限のオブジェクトを表し、以下のようなものを書く必要があることを強制的に思い出させる。

componentsum(x, y)
where
    componentsum(x, y) = 
        cons(car(x) + car(y), componentsum(cdr(x), cdr(y)))
end

もちろん、(a)書かれたプログラムの種類に制限を課すことは出来るし(b)プログラムを前処理するか、+のようなシンボルの意味を拡張して、リストの要素ごとの合計を含めることも出来る。
これは私たちのリストの最後のカテゴリに私たちを連れて行くだろう。

5. 特別な目的のデータフロー関数型言語、すなわちLucid

したがって、Lucidは、単一代入およびLISPのような関数型言語を通じて、従来の言語からのデータフロー言語への進化を予測する試みとして見ることが出来る。
私たちは、この進化の面で最も進んでいるのが、データフロー言語であると主張している。
確かに、それが唯一のデータフロー言語であるとは主張していない。
また、他のデータフロー言語を必ずしも「失敗」とみなすことも望ましくない。
しかし、私たちは、Lucidが古いフォン・ノイマン形式の計算を最も拒否し、その代わりにデータフローを採用している、1つのデータフロー言語であると感じている。
Lucidは未来のデータフロー言語である。


ということで、これで1章はおしまい。

読んでて、唐突に日本の研究の話が出てきて驚いたw
それも、第五世代コンピュータの話とかw

第五世代コンピュータのプロジェクトはよく失敗だったと言われるし、自分もそう思ってたんだけど、自分の場合、シグマプロジェクトと混同してたというのがあった。

シグマプロジェクトはもうどうしようもない失敗プロジェクトだったわけだけど、第五世代コンピュータというのは、シグマプロジェクトとはまた別のプロジェクト。
第五世代コンピュータというのは、「述語論理による推論を高速実行する並列推論マシンとそのオペレーティングシステムを構築する」というものだったらしい。(引用元:wikipedia
これによって、高速なエキスパートシステムを作り上げ、人工知能を実現させよう、と。

結局、期待された人工知能は出来上がらず、また、ここで作られた技術もその後使われることがなかったので、失敗プロジェクトと見做されているんだけど、ただ、調べてみると、なんか違う感じ。

元より、人工知能を作ろうというところまでは言っていなくて、スコープとしてあったのは「マシンとOSの構築」という部分。
そして、実際にマシン(PIM)も作られているし、OS(PIMOS)も構築され、そのための言語(KL1)も作られている。
そういう意味で、当初のスコープはちゃんと達成されていたっぽい。

また、その研究成果は第五世代コンピュータの研究開発成果でPDFで見ることが出来るんだけど、意外と興味深い・・・

何かの拍子で再評価されたりすることもあるかもしれない。
実際、Lucidーーというか、データフロー言語に自分は興味を持ってるわけだしね。

それにしても、Lucidは自身を「未来のデータフロー言語だ」と言ってるわけだけど、現状は推して知るべし。。。
未来の言語どころか、忘れ去られて、誰も知らないような言語になってしまっている。
そういう意味で、Lucidの試みは失敗だったと言えるかもしれない。

けど、その問題意識は、非常に今の状態にマッチしていたり。
ある意味、「早すぎた」というか。
なので、温故知新、改めて評価される日が来たりするのかもしれない。

今日はここまで!