いものやま。

雑多な知識の寄せ集め

『RubyでつくるRuby ゼロから学びなおすプログラミング言語入門』を読んでみた。

前から気になってた『RubyでつくるRuby』をこの前の技術書展5で購入して読んだので、その感想とか。

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門

結論から言うと、「残念な本だったなぁ」というのが正直な感想。

自分が読む前に期待していたのは、わざわざRubyを対象の言語として選んできているくらいなのだから、「Rubyっぽさ」にちゃんと触れ、その「Rubyっぽさ」を活かして構文解析や抽象構文木の評価を実装していく、という内容。

ただ、読んでみたら、

となっていて、拍子抜け。

抽象構文木の評価も、クラスを使ってダックタイピング的に「うひょ〜、同じメソッド呼び出しでも、ポリモーフィズムでちゃんとあるべき処理が実行されるぜ! これぞオブジェクト指向! case文? そんなのいらん!」ってなってればカッコよかったんだけど、配列を使ったプリミティブな構造になってて、case文で条件分岐して、といった具合で、「えぇぇ・・・」と。
そんなのはHaskellにでもやらせとけと。

まぁ、そうなっているのは理由があって、この本で実現するRubyインタプリタは極々小さなサブセットになっていて、四則演算、変数、分岐、関数、配列、ハッシュくらいしかサポートしていないから。
ここでいう配列やハッシュも、メソッド呼び出しとかは一切サポートされてないので、ホントにプリミティブな機能しか用意されてない。
なので、RubyRubyっぽいところがゴッソリ落とされている感じ。
でも、それってRubyでやる必要あるの・・・?

そんな内容なので、この本はRubyの入門書としては使い物にならないので注意。
当然、構文解析も筆者の用意したgemの関数をポンと叩くだけなので、インタプリタ作成の入門書とかにも当然ならない。
RubyRubyをつくる、というネタ自体は非常に面白いと思うのだけど、ホントそういう趣味本として読むならともかく、実用性はまったくなし。
まぁ、そう言う本、自分は嫌いではないけど(^^;

にしても、せめて構文解析の部分はちゃんと書いて欲しかったなぁ・・・
もちろん、そこが一番難しいところで、書くのも大変なのは分かるんだけど、上記の通り、正直入門書にはまったくならない本なんだから、せめて趣味本としてちゃんと知的好奇心を満たしてくれている内容にして欲しかった。

ぶっちゃけた話、「Rubyプログラムを実行できるRubyプログラム」を書くだけなら、以下でいいわけだから:

eval File.read $*.shift

多分これが一番短いと思います。(23文字)

ちなみに、ちゃんとブートストラップもするし、(当たり前だけど)Rubyの機能もフルサポートしてるw

「いやいや、そんなん構文解析も評価も全部親のRubyインタプリタに丸投げしてるだけやん」って言われそうだけど、本書だって組み込み関数や配列やハッシュの実装は親のRubyインタプリタに丸投げだし(これ自体はまぁ仕方ない)、構文解析も筆者の作ったgemに丸投げでブラックボックスなわけだから、丸投げの度合いが違うだけとも言える。
例えば、それこそ筆者の作ったgemで本書の最後のプログラムを一つの関数として提供すれば、関数呼び出し1つポンとやってオシマイ、となるわけだし。

で、上記のワンライナーRubyインタプリタはおかしい、インタプリタの説明に全然なってない、と思うのなら、やっぱり構文解析の部分をマルッと省略してしまっている本書も、同様の批判がされるべきなんじゃないかな、と思う。
どうせこんな趣味本を買う初心者なんかいないんだから(偏見)、マニアックな方向に寄せて、ちゃんと書いて欲しかったなぁ。

今日はここまで!

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門

「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の試みは失敗だったと言えるかもしれない。

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

今日はここまで!

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

前回の続き。

1.6 Honest, Folks, We Was Just Funnin’

この数ページで、プログラミング言語に取り組んでいるほぼすべてのコンピュータ科学者を致命的に怒らせただろう。
今や、怒れるカウボーイ達、ウィザード達、伝道師達、技術者達、よろず屋達(Handymen、修正主義者達のこと)のリンチ暴動が集まっている。
彼らは瞬間的に紛争を忘れ、私たちを通りの向こうにある古い狩猟用の木に引きずり出すという決意に結束している。

読者はおそらく私たちほとんど同情していないだろう。
結局のところ、ソフトウェア危機を解決しようとするほとんどすべての試みを無駄に却下しただけではないか?
真面目な研究者を半狂乱なマンガのキャラクターとして描写して、傷害に侮辱を加えていなかったか?

実際には、私たちの風刺は、ターゲットに見えるかもしれない少数の人々にしか向けられてない。
例えば、プログラムの検証や意味論を扱うほとんどの人は、かなり賢明である。
彼らは、自分の研究が重要だと考えているが、既存の言語の新しい意味論による記述がソフトウェア危機を解決しようとしているという幻想のもとにはいない。
彼らは実際にウィザードと呼ばれるに値するほどではない。

同じように、ほとんどが単なる死人であるような人々によってプログラムが構築されることを、ほとんどのプログラマ・ソフトウェアエンジニアはよく知っている。
彼らは、専門的な機械に近いプログラミングが、ソフトウェア開発の問題に対する普遍的な救済策ではないことを知っている。
賢い人でさえ、あまりにも多くの巧みさが殺すことができることを知っている。
これらの人々は真のカウボーイではない。

同様に、ほとんどの技術者達は、良い環境が悪い言語に対する救済策ではないことを知っている。
多くの伝道師達は、良い方法論では本当に悪いシステムを克服できないことを知っている。

私たちの批判は、彼らが取り組んでいる特定の問題がソフトウェア危機の根底にあると確信している、小規模少数派に対してのものである。
たとえば真のウィザードは、正式なツールがないことが命令型言語の問題のすべての原因になっていると確信している。
同じように、実際の技術者は、現実の問題は適切なプログラミング環境がないことであると確信している。

彼らは解決策を持っていると確信しているが、みな間違っている。
彼らは、使用されているマシンの基本設計に問題があるとしていないため、間違っている。
代わりに、彼らは問題がマシンの使用方法にあると考えている。
彼らは問題を技術的なものとして見ていない。
多くのアプローチは非常に異なり、あまり共通性がないが、1つ共通な点がある。
すなわち、彼らはソフトによる解決(ソフトウェア、数学、方法論など)をハードの問題に提案している。

ある研究者グループは、私たちのブラックリストからはっきりと抜け落ちている。
私たちは、新しい種類のマシンを設計する人々については、何も悪いことを言っていない。
もちろん、私たちは彼らを、はんだこてでソフトウェアの危機を解決することができると思っている狂信者、修理士と風刺することも出来た。
結局のところ、彼らは、カウボーイや伝道師と同じように、彼らの仕事が将来の鍵であると確信している。

違いは、彼らは正しいということだ。
ソフトウェア危機全体の根底にある問題は、実際にはマシンアーキテクチャの問題である。
私たちは提案された個々の新しいアーキテクチャがその仕事に縛られなければならないと言っているわけではない。
しかし、全体としては、ハードウェアの研究者が解決策につながる唯一の道に従っている。
主題の半分である「ソフト」のコンピュータ科学者(意味論者、方法論者、言語設計者)には、選択肢がある。

一つは、彼らは自分のスキルとエネルギーを、古い逐次型・命令型アプローチを少しでも長くしてみようと努力することに専心することが出来る。
この選択をするのは、カウボーイ、ウィザード、伝道師、技術者、よろず屋である。

もう1つの選択肢は、新しいマシンや計算形式の模索を試みることである。
この選択は、新しい世代のコンピュータに適した新しい種類の意味論、方法論、言語などを発見するのに、技術とエネルギーを捧げることを意味している。
この道を歩む人たちは未来を選んでおり、彼らの努力が無益でもばかげてもいないことが示されるだろう。

もちろん、第3の可能性もある。
それは、問題は無視して、特定の計算形式からは独立した意味論、方法論、検証システムなどを開発しようとすることである。
これは可能であり、命令型言語の検証は、非手続き型言語にも容易に適用できる。
しかしながら、研究者は問題を永遠に避けることは出来ない。
そのような、立場を明らかにしていないと自身では思っている人々は、(計算が本質的に逐次的であるという確信など)無意識の偏見の犠牲者であることが多い。
生涯の仕事としている主題のリスクについての、根本的な論争を避けようとする研究者は、無関係であることを最後に証明する。

1.7 非手続き型言語

命令型のプログラマや言語設計者が、マシンとの愛憎関係を持つことは明らかである。
一方では、彼らはマシンから離れたがり、抽象的で高レベルで構造化されていて数学的で問題指向でありたいと思っている。
同時に、彼らはマシンに近づき、計算の詳細を制御し、プログラムをできるだけ効率的にするという圧倒的な衝動を持っている。
もちろん、プログラマがマシンに近づくことを可能にする機能と修繕は、すべてのトラブルを引き起こすものである。
これらは、未熟者が悲しみ、ウィザードが分析に困り、伝道師は悪と告発し、よろず屋は永遠に修復している機能である。

命令型言語の問題は、多くの人々にマシンとの関係の「愛」の側面を再考させている。
彼らは、プログラミング言語の最も基本的な原則、すなわち計算や動的な活動を指定することが意図されているため、本質的に動的であるということを拒否しようとしている。

PASCALのような言語の本質的に動的な2つの機能は、代入と制御フローである。
当然のことながら、多くの人がそれらを排除しないべきかのか、疑問に思った。
この急進的な解決策は、最も重い制御フロー、すなわち、goto文が不名誉に引退することを余儀なくされた後、信頼性を得た。

代入も制御フローも、本当には必須ではないことは古くから知られており、純粋に静的で数学的な言語でプログラムを書くことは可能である。
約50年前、チャーチは計算可能な数値関数を(関数を定義するための非常に簡単な形式である)ラムダ計算で表現できることを示した。
後でクリーネ(Kleene)は、同じことが、再帰的な関数定義である「構造」だけの単純な言語でも言えることを示した。
発明された最初の高レベル言語の1つはLISPであり、その「純粋なコア」には代入も制御フローもなく、確かにLISPはチャーチとクリーネの仕事の一部に基づいていた。

手続き型言語(すなわち、代入や制御フローのない言語)は、多くの点で命令型言語よりはるかに優れているという一般的な合意がある。
手続き型言語は、参照透過(referentially transparent)であり、プログラムに現れる式の値は、部分式の値だけに依存し、これらの部分式が評価される順序には依存しない。
特に、関数(または「関数手続き」)は、実際には単語の通常の意味での関数を表している。
関数によって返される値は引数の値によって決定され、関数が「呼び出される」「時間」から独立している。
つまり、数学記号(+など)は、従来の数学とまったく同じように使用される。
非手続き型プログラマによって使用される表記法は、プログラマによって使用のために修正された、従来の数学の表記法である。

ウィザード達はもちろん、非手続き型言語を喜んで受け入れている。
なぜなら、従来の数学の手法を使用してプログラムを推論することができるからである。
非数学的な表記の数学的な意味を作るために全く新しい形式を開発する必要がない。
たとえば、等式の置換の法則が成り立つ。
すなわち、関数 f(x, y) x - 2 * yという式で定義されている場合、 f(A, B)という式は A - 2 * Bに置き換えることが出来る。
(少なくとも本書で考慮されている)非手続き型言語の意味論は、非常に簡単に仕様化することが出来る。
式の意味は、指定された関数または演算を部分式の意味に適用した結果であり、再帰的定義の意味はその最小不動点(least fixed point)である。

伝道師達もまた、恍惚としている。
ISWIMのような言語ではgoto文はなく、forループすらない。
副作用もなく、例えば式 f(x) - f(x)の値は、整数を含むとして、計算が終わるのならば、常に0である。
参照透過性は明らかにトップダウンアプローチをより簡単にし、関数定義とwhere節は優れた構造化ツールとなっている。

それにもかかわらず、非手続き型言語は、常に(特にカウボーイ達によって)、致命的な欠陥があるとみなされてきたーーすなわち、それらは(おそらく)本来的に非効率的である、と。
この(非難された)非効率性の根本的な原因は、反復の欠如である。
手続き型言語は純粋に定義的なものなので、変数の値は、少なくとも定義が有効なプログラムの範囲内では変更できない。
ダイクストラDijkstra、1965、p.215)は、以下のように言っている:

その優雅さにもかかわらず、深刻な反論がそのようなプログラミング言語(代入や制御フローがないもの)にはされるだろう。
スタック内の情報は、入れ子にされた存続時間を持つオブジェクトとして表示され、そして、その存続期間全体にわたって一定の値であるだろう。
そして、既存の名前付きオブジェクトの値は、別の値で置き換えられる。
結果として、新しく形成された結果を格納する唯一の方法は、スタック上に置くことであるが、スタック上に置かれた値を知るすべはなく、興味がないにも関わらず、スタック上の値の寿命は長くなる。
まとめると、それはエレガントだが不十分である。

※(訳注)おそらく、ループを再帰で実現することについて言及していて、その場合、スタックが深く掘られていくことになるが、その古い値は(ループでは)もう不要になっていて、しかも現在の関数から参照することも出来ないにも関わらず、ずっと生き続けてしまうということを指摘している。
なお、末尾再帰であれば(処理系の実装が賢ければ)そのようにスタックが掘られることはないが、その場合、メモリ上の値の置き換えは発生している。
(末尾再帰は、本質的にはループで必要なスタックを引数として表現し、gotoによるラベルジャンプでループを実現しているのと同じ)

ダイクストラの判断は、より古い従来の非手続き型言語(主にLISP)の経験によって確かに確認された。
多くのアプリケーションでは、LISPはきわめて適していますが、他の人にとっては、特に懐古的であるため、LISPによる解決は許容できないほど遅い。
実際、LISPの開発者は、性能を向上させるが参照透明性を破壊するいくつかの「不純な」機能(実際の反復のためのプログラムを含む)をすぐに追加した。

しかし、最近、研究者は非効率性の問題に対する可能な解決策を発見した。
ダイクストラによって強調された弱点は本質的な弱点ではなく、特定の種類の非手続き型言語を実装する特定の方法の弱点である。
ダイクストラの批判には、暗黙のうちに2つの仮定がある。
最初の前提は、プログラムが従来のALGOLランタイムスタックアプローチを使用してフォン・ノイマン・マシンで実行されることである。
2番目の前提は、基本データオブジェクト(関数の引数)が有限集合であり、スタックに積み上げられる「マシン・ワード」の集合であるということである。
関数の引数が無限のオブジェクト(例えば、すべての素数のリスト)であることを可能にする新しい非手続き言語が登場している。
これらの新しい言語は依然として立派であり、数学的であるーー数学者は何百年もの間、無限オブジェクトを扱ってきている。
それにもかかわらず、新しい言語は新しいプログラミングスタイル、(リダクションマシン、遅延評価、データフローといった)新しい実装方法を許可し、ダイクストラによって言及された、反復を再帰とする問題を避け、一つのプログラムで多くのプロセッサが評価の協力を行える。
手続き型言語は、ある日、効率性と優雅さにおいてFORTRANと競合するかもしれない。

反復の代わりに再帰的定義のみを使用して、効率的にプログラムすることは可能かもしれない。
しかし、この奨励的な開発により、一部は完全に反復を放棄するようになった。
彼らは非手続き型言語が反復を持つことができないということを無神論的に受け入れている。
実際、非手続き型プログラミングは本質的に操作や動的な考慮事項から独立していると、彼らは原則をより一般的に拡張している。
彼らは、この「ダイナミズム」の欠如がプラスの美徳であると考えている。
彼らは、動的・操作の考えがプログラミング言語のすべての問題の源泉であると思っている。
プログラミングに対するこの神秘的で先見的なアプローチは、私たちが「丘の上のばか」と呼んでいるものを表している。
すなわち、プログラマは、単なる計算のやり方の詳細について言語と心に負担をかけてはならず、代わりに、静的で永遠な数学的対象について考えて、ただ計算の喧騒から離れて、丘の上に座っていなければならない、と。
もちろん、プログラムは実装されて、さらに効率的である必要があるが、(「神秘主義者達」によれば)それはエンジニアの、言い換えれば単なる商人の、関心事である。
プログラマは、この見解によれば、プログラムがどのように実行されるべきかについて何も知る必要はなく、数学的な観点からだけ理解するべきである、と。

神秘主義者達は、現在の「関数型プログラミング(functional programming)」コミュニティで特に強く象徴されている。
1つの特に極端な宗派は、関数はクリーンで高レベルであり、プログラマーの注目に値するが、その引数(卑しいデータオブジェクト)は汚れていて、低レベルであり、避けられるべきだと信じている。
ただのデータオブジェクトは、この宗派の支持者にとって、言い表せないほどありふれたものであり、彼らはそれを話すことさえ失望させると考えている。
したがって、その言語にはこれらのオブジェクトに名前がなく、変数と式は関数のみを表すことが出来る。
いくつかのデータフロー言語もこのカテゴリにいる。
これらの言語では、データフローは純粋に実装手法であり、非手続き型プログラマの洗練された感性を害するだけの操作概念である。

この理念に対する支持者は、実際の(「純粋な」)数学は本質的に静的オブジェクトを扱い、変化と動的活動は数学的精神とは異なるということを自明として、自身らを正当化している。
クリストファー・ストレイチー(Christopher Strachey)(1971、p.77)は、かつて次のように言っている:

...プログラミングにおける命令(またはコマンド)の使用は、変数を導入し、数学は一般に、この意味での変数の存在ーーすなわち、ある期間にわたって変化する値ーーを認識しない。
従来、数学は静的な状況だけを扱っている。
 オブジェクトの極限へのアプローチに関係する計算でさえ、一連の固定値の観点から対象を扱う。
 ...一方、プログラミングでは、プロセスの性質上、時間によって変化する変数を扱う。
プログラムは本質的に変更のスケジュールである。

(ストレイチーは、偶然にも、神秘的な視点を擁護していなく、むしろ、彼は代入文の理解に必要な新しい動的な数学を開発するウィザードを奨励していた)

しかし、数学が本質的に静的だというのは本当に正しいのだろうか?
数学者が時間とともに変化する値を決して扱っていなかったというのは本当に正しいのだろうか?
真実と違うことがあってはならない!
微積分が最初に開発されたとき、それはまさに操作の基礎にあった。
ニュートンは、時間と共に変化する流入量を導入した。
のちに、当然のことながら、微積分は、極限(または、より最近では、無限小という概念)の概念を用いて形式化された。
それにもかかわらず、微積分は本質的に量の変化、実際は滑らかに変化する量の研究である。
数学の基本原則は常に、量の概念を継続的に一般化することによって、静的な方法で動的を研究することだった。
例えば、昔「持ち去り」という動的だった概念は、負の数で公式化され、同じように「区分け」は有理数を使って形式化された。
数学は、常に様々な形の変化を研究してきている。

物理学者とエンジニアが、「極限への物体のアプローチ」に関連して、ストレイチーの計算の定義を受け入れるのは、非常に困難である。
実際に微分方程式を使用する人は、通常、速度、加速度、密度などのまさに操作上の概念を使用する。
動的な思考が「低レベル」であるとか、または混乱を生み出すということは、彼らには決して起こらない。
動的視点と静的視点との間に真の矛盾は見られない。
代わりに、彼らは反対であるが補完的で調和のとれた2つのアプローチを見ている。
数学が動的な状況をモデリングしている(または指し示している)とき、動的に考えないことがあるだろうか?
そうしないのは、なんとも愚かである!

神秘主義者達は基本的な問題(フォン・ノイマンアーキテクチャの不適当性)を認めているが、それを無視して問題を解決したいと思っている。
神秘主義者達は、彼らのプログラムがどのように実行されているか知りたくないし、少なくとも、プログラマが知るべきではないと思っている。
彼らの言語の意味論は、操作の考えを参照することなく与えることが出来るので、問題全体を自身の手で洗うことが出来ると考えている。
彼らはエンジニアに「ここに言語の意味論があり、それを実装し、望む関数を使用することが出来るので、フォン・ノイマンアーキテクチャに縛られてはならない」と言う。
神秘主義者達は、言語の設計はマシンに完全に依存しないと考えている!


ということで、本質的にはマシン・アーキテクチャの問題だ、というのが、筆者たちの主張。
フォン・ノイマンアーキテクチャに代わってデータフロー・アーキテクチャを考え、その上で動くプログラムを表現するためのプログラミング言語を考え、その数学的な意味論を、履歴を持った変数・関数で構成しようとしている、といった感じか。

それにしても、長い(^^;
興味深い議論ではあるんだけどね。
次でやっと1章が終わる予定。

今日はここまで!

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

前回の続き。

1.4 命令型アプローチの問題

近年、プログラミング言語に対する命令型のアプローチは、ますますひどい兆候を示している。
従来の「主流」のプログラミング言語は、これまで以上に複雑な作業に、そして、これまで以上に多くの人々に使用されている。
最初のフォン・ノイマン・マシン(1950年代初めに作られた)は、1秒当たりわずか数百回の演算(加算など)しか実行できなかった。
プログラムは通常1人のプログラマーの仕事であり、数十行以上の長さであれば大きなものと見なされた。

最新のマシンは、1秒間に数十万回の命令を実行できるようになった。
現在のソフトウェアシステムの中には、数百万のプログラマシステムアナリストの長年の労力がかけられ、数百万行のコードを含んでいるものもある。
フォン・ノイマンの言語とマシンの基本原則は1952年以来ーー少なくとも1960年にALGOLが導入されて以来ーー変わっていない。
1985年にFORTRANとEDSACの子孫が彼らの年齢を示していることは驚くことではない。

フォン・ノイマンのアプローチに何か問題があるという最も明白な兆候は、これらのマシンや言語、特に言語の複雑さの、爆発的・指数的な増加である。
今やアクティブで使われている命令型言語は文字通り何百もある。
もちろん、異なるアプリケーションで異なる言語が必要になるというのは予期されうることである。
しかし、これらの言語は、同じドメインのアプリケーションを意図していても、本質的に異なるアイデアを採用していたりする。
ALGOL、PL/I、ALGOL 68、PASCAL、BASICのような、多かれ少なかれ「汎用的」言語もある。
特に、これらの言語は、ほぼ同じアプリケーションを想定していて、同じ概念(変数と代入文)に基づいており、「マシンに依存しない」と主張している。
それにもかかわらず、それぞれは何かと独自の方法をとっていて、それぞれと互換性がない。
これらの言語の1つから別の言語へのプログラムの変換方法はない。

フォン・ノイマンのアプローチの気が狂うような複雑さは、個々の言語そのものの状態に反映されている。
より野心的な汎用型言語(特にPL/I)は、想定されうる巨大な性質を持っている。
PL/Iのような言語は、何千もの制限や制約を対象として、何千もの機能、オプション、デフォルトを提供している。
いずれの人もPL/Iのすべてを知るなんて想像も出来ず、その「マニュアル」は、電話帳が何冊も集まったようなものになっている。

多くの言語設計者が、言語的な「過度の」アプローチを拒否し、PASCALなどの控えめな言語を作り出した。
これらの言語はおおまか成功しているが、結局のところ、いくつかの重要な点で欠けていることが常に示されている。
簡素化のプロセスは遥か遠く、最初の一歩がいまだ進めていないように見える。
有用で、完全に自然で、明らかに無害な記述やプログラムというのを書こうと思っても、書けなかったりすることが常だ。
たとえば、PASCALでは、100個の数値の配列をソートするプログラムを作成し、200個の数値の配列をソートするプログラムを作成できるが、任意の長さの配列をソートする単一のプログラムを書くことは出来ない。

もちろん、これらの制限は容易に解消できる。
型システムのちょっとした緩和、配列の概念のシンプルな拡張、マルチプログラミングのための追加機能・・・そして非常に迅速な言語となると、もはや単純ではなくなってしまう。
一般的な傾向として、シンプルで、しかし制限がありすぎて便利ではない言語は、拡張が繰り返され、やがては使い物にならないような膨大な怪物になってしまうようだ。
ALGOLはALGOL 68になり、FORTRANPL/I(あるいはFORTRAN 77)に拡張され、今はPASCALからADAが生み出されている。
制限と一般性との黄金比を得るのは不可能に思われる。
言語設計者は自分たちが成功していると思っているのかもしれないが、四半世紀経った今もFORTRANCOBOLが依然として最も広く使われている言語である。

フォン・ノイマン言語に関する第2の問題は、正確な仕様が欠如していることである。
マニュアルは通常、構文(どんなプログラムが許可されているのか)は明確かつ詳細に示しているが、意味(プログラムが何をするのか)はおおよその非公式の扱いしか示していない。
徹底的に網羅された電話帳(のように分厚い)マニュアルは、何が起こるのかについて、最も一般的な場合について、しかも非公式な言葉でしか記述していない。
本当に複雑な問題(特に、異なる機能の相互作用を含む問題)は、コンパイラ依存であり、コンパイラをよく知っているその実装の「教祖(guru)」に訊くしかない。
プログラマーは、言語の振る舞いを確認するために、短い「実験的な」プログラムを書くことがよくある。
この状況はダイクストラ(1976、p.202)によって、うまく記述されている。

以来、いびつで、不明確で、それゆえ不安定なソフトウェアシステムが増殖していくのを私たちは目撃している。
多くのプログラマは、彼らの仕事で必要となるキッチリしたツールで作業するのではなく、何が起こるのかも分からないような曖昧で掴み所のない環境、辺獄で暮らしている。
このような残念な状況の下では、正しいプログラムというのは、それが正しいと証明されたものであってさえ、意味がなくなる。
このようなシステムの増殖がコンピューティングコミュニティの士気に対して何をもたらしているのかは、記述しきれたものではない。

フォン・ノイマン病の3番目の症状は、最初の2つの必然的な結果であるーーつまり、まったく信頼できない。
プログラムは動作しない!
何のエラーも含まない12行程度以上の命令型プログラムを書くことは、ほとんど不可能である。
これらの「バグ」は、見つけるのが非常に困難であることが判明していて、プログラマは、プログラムの設計やコーディングに費やすよりもはるかに多くの時間をプログラムの「デバッグ」に費やすことになる。
結果として、エラーのないソフトウェアは、非常に高コストになる。
大きなシステムでは、すべてのバグを取り除くことは事実上不可能である。
微妙なエラーのいくつかは、(例えば、プログラムのあまり使用されていない部分に)何年も潜伏していて、突然「生き生きと現れ」壊滅的な結果をもたらしたりする。
もちろん、どの言語を使っていようと、人間は常に間違いを犯すだろう。
しかし、誤りをよく引き起こしていると経験的に判っている機能(goto文、副作用、エイリアシング)は、命令型アプローチにとって自然に示されるものであり、それなしでは困難と言える。

最後に、私たちはフォン・ノイマン・システムの第4の弱点について言及する。
これは最近明らかになった問題なのだが、最も重大であると示されるかもしれない。
それは、フォン・ノイマン・システムは非効率的であるということである。

経験豊富なプログラマーは、この声明が信じがたいと思うだろう。
彼らは、言語が複雑で、仕様が甘く、エラーが起こりやすいとは認めるかもしれない。
しかし、非効率的だなんてことがあるのだろうか?

ハードウェアを最大限に活用できるようにするとしたら、プログラマーがマシンに近づくようにする他ない。
実際、マシンに接近する必要があるということが、フォン・ノイマン言語で問題が起こるすべての原因になっている。
シンプルさ、信頼性、使いやすさなどは、すべて効率性のために犠牲になっている。
しかし、それでフォン・ノイマン・システムが効率的でないのだとしたら、それらは一体なんだというのか?

しかし、非効率性の批判は、言語よりもマシンに向けられている。
フォン・ノイマン・マシンは、一度に1つの命令しか実行できないーー 与えられた問題のロジックを何千も並行して計算することができる場合、フォン・ノイマン・マシンは、原理的に可能な速度より数千倍遅い速度で計算を実行することになる。
命令型言語は、フォン・ノイマン・マシンを最大限に活用するのに適しているかもしれないが、それらは必然的にマシンの逐次性を反映してしまう。

Christopher Stracheyは、単純ではあるが目を引く、この効率性の例を指摘したーーそれは、行列の乗算である。
Landin(1966、p.166)の後で、彼は議論で以下を指摘した:

純粋な命令型言語に関して、1つ不都合なことは、あまりにも多くのシーケンスを指定しなければならないということである。
行列の乗算をしたい場合は、行列の次元が n \times nであるなら、 n個の立方乗算(cubed multiplication)を行う必要がある。
これを行うための通常の(すなわち、命令型)プログラムを書くならば、それらがすべて実行される正確なシーケンスを指定する必要がある。
実際には、適切なグループにそれらをまとめ上げる限り、乗算をどのような順序で行うかは重要ではない。

この欠点は、プロセッサが高価なハードウェアであり、マシンのコストの大部分を占める時代には、あまり重要ではないように見えた。
しかし今や、LSIにより、プロセッサは比較的安価になった。
何千もの処理ユニットを持つマシンを構築できないという技術的あるいは経済的な理由は存在しない。
問題は、これらのプロセッサの活動をどのように組織し、同じタスクを協調して行えるようにするかである。

公平であるためにいうと、フォン・ノイマン・マシンに対する私たちの批判は、実際には、コンピュータシステムが単一の醜いフォン・ノイマン・マシンを中心としているという、システムアーキテクチャへの特定の見方に対する批判である。
実際、フォン・ノイマン・マシンは、長い間、システムの有用な構成要素であることが分かるかもしれない。
例えば、ネットワーク内に多数の適度なサイズのフォン・ノイマン・マシンを接続して、同じプログラム上で協調することが出来る。
これは確かにフォン・ノイマンボトルネックを回避する方法の一つである。
もちろん、多くの研究者は、まったく異なる方法でデータを処理する、まったく新しいマシンアーキテクチャ(データフローやリダクションマシンなど)に取り組んでいる。
とにかく、「フォン・ノイマン言語」を批判するとき、私たちが批判しているのは、単一のフォン・ノイマン・マシンで行われる計算の視点に基づいている従来の逐次・命令型言語である。

もちろん、原理的には、FORTRANのような命令型言語を何らかの並行(parallel)または分散(distributed)アーキテクチャで実装できない理由はない。
しかし、実装が単一の従来の逐次マシンのステップをシミュレートしただけであれば、そうすることには意味がない。
「パラレル」マシンの計算能力の大部分はアイドル状態になる。
FORTRANの本当に価値ある(言い換えれば)データフローの実装には、隠された並列性を検出するための洗練されたプログラム分析の段階が必要となる。
しかし、私たちは、プログラマと(コンパイラの)実装が交差する目的で働くばかばかしい状況にいることに気付くだろう。
この言語は、プログラマアルゴリズムを厳密に連続した形でコード化するように強制する。
一方、(コンパイラの)実装はこのコードを「クラック」して、元の並列アルゴリズムを復元する必要がある。
当然のことながら、命令型言語に「並列性」のための機能を追加することによって、この最後の問題を解決しようとすることになる。
しかし、結果として得られるプログラムはさらに複雑になり、新しい機能と言語の他の側面との相互作用は、前述の問題を悪化させるだけである。

レイノルズ(1970年)はかつて、言語設計者が直面している課題は、シンプルで汎用的かつ効率的である(すなわち、効率的なプログラムを書くのがかなり簡単である)ことを同時に満たす言語を生み出すことであると言った。
従来の命令型の研究の設計者は、これまでのところ、この挑戦に応えられていなかった。
たとえば、PL/Iは汎用的で効率的だが、シンプルではない。
PASCALはシンプルで効率的だが、特定の重要な側面では十分汎用的であるとは言えない。
APLはシンプルで汎用的だが、効率的ではない。
最後に、ADAはシンプルではなく、それが汎用的、効率的であるかはこれからといったところだ。

1.5 いくつかの示唆された解決策

命令型言語の最も熱心な支持者でさえ、何かが非常に間違っていると認めるだろう。
しかし、「ソフトウェアの危機」と「並列性の問題」については、いくつかの異なった態度がある。
ここではいくつかの(いくらか滑稽された)よくある視点を紹介する。

まず、私たちがクリント・イーストウッドの見解と呼ぶものがある。
この「険しいウェスタン」の観点では、プログラミングは厳しくて困難な作業であり、常にそうだが、しかし、「プログラマプログラマーがやらなきゃいけないことをやらないといけない」としている。
こういった「カウボーイ」達によると、実際の問題は、仕事を終わらせるのに十分なほど賢明でタフな本物のプログラマの不足していることである、という。
カウボーイ達は、長い時間「鞍(すなわちターミナル)で」プログラムを学び、他のすべての人が同じことをするのを期待している。
誰かがミスをするなら、それは「ミスした人自身の問題」である。
カウボーイ達は、一般的に「本での学習」(理論)と「新鮮な」言語を信じていない。
彼らはPL/Iが大きすぎる、あるいは、Cが低レベルすぎると不平を言う「未熟者」達を軽蔑する。
彼らにとって、PL/Iは機能が多すぎるなんてことはないし、Cは汚れきってなんかいない。
彼らが望むのは、コンピュータにもっと近づき、それを「ダンス」させるための、もっと強力なツールである。

カウボーイ達は確かに賞賛に値する。
彼らの中でも最も優れたもの(真のストレートシューター)は、普通のプログラマーをしても「臆病者」であるという印象を与えるようなソフトウェアを作り出すことが出来る。
しかしながら、そんな本当にタフなカウボーイ達が身のまわりにいるのかということを自問しなければならない。
実際にはそんなことはほとんどなく、ほとんどのソフトウェアは、ターミナルのワイアット・アープではなく、普通の、謙虚なトレイル・ハンド達によって書かれるという事実に従うしかない。

次は、私たちが「ミスター・ウィザード」学園の教えと呼ぶものである。
ウィザード達は多くの点でカウボーイ達の対極にいるが、プログラミングとプログラミング言語は本質的に非常に複雑であるということだけに関しては、彼らは意見を同じにしている。
ウィザード達の見解では、問題は、これらの言語の理論的・数学的な理解が不十分なことである。
ウィザード達は、古の伝承にある埃にまみれた多くの研究を調べている。
彼らはラムダ(Lambda)の"the Arts Magical, the Logyck Symbolyck and the Calculus"(訳せない・・・)を学んでいる。
彼らはタルスキ(Tarski)、チャーチ(Church)、カリー(Curry)の偉大な名前を思い起こさせる。

ウィザード達の究極の夢は正式なプログラム検証のためのシステムである。
これにより、言語やプログラムがどれほど悪くあろうとも、プログラマは(ウィザードに助けを得て)与えられたプログラムが正しいという気密な証明を生成することが出来るようになるだろう。
したがって、プログラム検証は、元のプログラムを金に変える賢者の石の一種である。
ジョン・マッカーシー(John McCarthy、1965、p.219)は、以下のように言っている:

合理的・数学的な計算理論が開発されれば、デバッグの排除という賞金を獲得することが出来る。
これまでとは違って、プログラマは、プログラムが希望した性質を持っていることをコンピュータで確認するための証拠を提示することになるだろう。

問題は、ウィザード達が手腕を振るったとしても、フォン・ノイマン言語の基本的な性質はもちろん変わらないということにある。
ウィザード達は正式な仕様書の作成に成功したかもしれないが、これらの仕様書で、理解不能なラムダ計算の電話帳(マニュアル)の分厚さも増す。
同様に、「実際の」プログラムの正しさの証明も、実用的ではないことが判明している。
ウィザード達は、「汚れた」機能(副作用、goto文、エイリアシング)でトラブルに遭遇した。
もちろん、これらはまさにカウボーイ達が最も愛している機能である。

しかし、カウボーイ達やウィザード達の有様を独善的な侮蔑で見ている、第三のグループがある。
このグループのメンバーは野性的な狂信者であり、構造化プログラミングの福音の伝道師達である。

伝道師達は、コンピュータサイエンス版の原罪の教義を認めている。
彼らは、人間が、注意散漫でミスをおかし(怠惰の罪(the sin of Sloth))、死んだ心の貧弱な力を超えた任務を遂行する(傲慢の罪(the sin of Pride))という固有の傾向を持って生まれてくると信じている。
罪の贖いとは、もちろんバグである。
バグ(および一般的なソフトウェアの問題)を回避するには、プログラマは悪の行いを放棄し、善なる行いを採用しなければならない。
プログラマは、儀式によってソフトウェアが悪霊に憑かれるのを防ぐために、プログラミングの厳格な規律(方法論)を採択するよう奨励される。

構造化プログラミングの弟子たちは、実際、悪いソフトウェアとの戦いで重要な成功を収めている。
それにもかかわらず、男と女の心の中に潜む邪悪は、予想以上に征服するのが難しいと分かっている。
節制ーーつまり、プログラマを邪悪に誘惑する禁断のリンゴである、goto文やポインタ変数といった機能を控えることは、伝道師達の教えにおいて重要な役割を果たしている。
しかし、既に気付いているように、プログラマはこれらの禁断の果物を避けがたい。
伝道師達は、すべての邪悪な特徴が追放された純粋で聖なる言語を夢見ている。
しかし、実際には、これらの「構造化プログラミング」言語の設計者は常に、効率の観点からその原則を妥協することを余儀なくされている。
したがって、忠実な人たちはひどく避けがたいジレンマに直面するーーすなわち、道徳に従って、正しいが効率的ではないプログラムを書くか、不道徳になり、効率的だがバグに苛まれたプログラムを作るか。
伝道師達は、自問しなければならないだろう。
「なぜ、悪魔は速いプログラムを持っているのだろうか?」と。

しかし、人間の能力は低いとする伝道師達と同じ意見を持つが、より現実的な解決法を強調する、第4の、より楽観的な視点がある。
私たちは彼らを、「技術者」学園の考えと呼んでいる。

技術者(Boffin)達は、人間の弱さがソフトウェア危機の根本的な原因であることに同意していて、なので、人間は裸で非武装のままではソフトウェアを生産することが出来ないとしている。
しかし、技術者達が提供する武装は、物理的、機械的なものであり、道徳や精神的なものだったりはしない。
彼らの目標は、構造化されたエディタ、診断的なコンパイラ、賢い型検査、洗練されたデバッグシステムといった、強力なプログラミングツールをプログラマに提供することである。
彼らの目的は、バグと同等の条件で戦える、技術的に強化されたスーパーヒーロー、超人的なプログラマを生み出すことである。

もちろん、「プログラマのワークベンチ」にある巧妙なデバイスが非常に有用であることは否定できない。
問題は、それらはプログラマの強みはもちろん、弱点も増幅することにある。
百万ドルのプログラマの役立つベルトにあるガジェットは、バグが多発する膨大なプログラムを簡単に作成できるようにして、膨大な量のリソースをデバッグに当てさせることが出来るようになる。
新世代のスーパープログラマによって作られたスーパープログラムは、恐ろしいスーパーバグとの新しい競争を生み出すのだろうか?
結果として、プログラマはさらに強力なツールを必要とするのではないか?
これらのツールはさらに恐ろしいバグを生み出すのではないだろうか?
そのプロセスは、終わることを知らない!

対照的に、私たちが「自前主義」または「修正主義」学園と呼んでいる野心は、かなり控えめである。
この観点では、ソフトウェアの危機は、命令型言語の重大な欠陥の結果であるとしている。
しかし、これらの欠陥は、フォン・ノイマンのアプローチ全体に内在する弱点の結果ではなく、むしろ設計ミスの産物である、と。
必要なのは、ちょっとした工夫、ちょっとした新しい部品、そして厄介な機能のいくつかの削除で、それですべてがうまくいくだろう、と。

今や、命令型言語が改善され、かなり単純な変更が大きな利益をもたらすことが多いことは間違いない。
問題は、ある変化が別の変化につながることであり、ある領域の改善が別の領域に悲惨な結果をもたらす可能性があるということである。
我たちは、ALGOLとFORTRANの修正がいつも成功しているわけではないということを見てきている。
これは特に、「並行性」や「データフロー」の機能を使用しようとした場合に当てはまる。


ということで、命令型言語の問題に関する話と、それに対する様々な態度の話。

正直、1番目と2番目(およびそれによる3番目)の話は、今となっては割とどうでもいい話だけど(ダメな言語は駆逐されてきたし、意味論もそんなに話題になることはない)、重要なのが4番目の指摘。
つまり、逐次的な記述なので、並列プログラミングが非常に難しいということ。

関数型が最近もてはやされるようになってきたのは、一つのプロセッサでの処理速度に限界がきて、マルチコア化が進んできた結果、この問題が浮上してきたからなのだけど、それを70年代後半〜80年代前半のこの時期に指摘しているというのは、非常に興味深い。

そして、それに対する様々な態度というのも、面白い。

カウボーイというのは、スーパーハカーになりゃいいじゃん、という態度だし、ウィザードの態度は、最近の関数型の信奉者の姿に非常に近い。
伝道師の、人は間違えるものだから、バグが起こりにくいように決まりを作って順守させようというのは、各種コーディング規約や、組込みでのMISRA-Cを思い起こさせるし、技術者の主張は、今やIDEなしではプログラミングが大変というのを予言しているようにも見えたり。

この本、書かれてから30年以上も経ってるのにね。
なんという先見の明か・・・

今日はここまで!

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

前回の続き。

なお、かなり意訳。

1.2 命令型プログラミング

RMS(二乗平均平方根)プログラムは、PASCALのような命令型言語で書かれたときには、ほぼ同じアプローチが使用されていても、とても異なったものになる。

次のPASCALプログラムは、前節でのLucidプログラムに多少なりとも対応している。
これはは同じタスクを実行するーー すなわち、有理数を繰り返し読んで、それまでのすべての入力の二乗平均平方根を繰り返し書き出す。
Lucidプログラムと同様に、終わりなく実行することを意図している。

program rms(input, output);
    var mean, a: real;
        n: integer;

    function square(x: real): real;
    begin
        square := x * x
    end;

    function newavg(y: real): real;
        var d: real;
    begin
        n := n + 1;
        d := (y - mean)/n;
        mean := mean + d;
        newavg := mean
    end;

    function sqroot(Z: real): real;
        var approx: real;
            err: real;
    begin
        approx := Z/2;
        err := abs(Z - approx * approx);
        while err > 0.0001 do
        begin
            approx := (approx + Z/approx)/2;
            err := abs(Z - approx * approx)
        end;
        sqroot := approx
    end;

begin
    n := 1;
    read(a);
    mean := square(a);
    writeln(abs(a));
    while true do
    begin
        read(a);
        writeln(sqroot(newavg(square(a))))
    end
end.

Lucidでのプログラムと、このPASCALでのプログラムの間には、明らかな類似点がいくつかある。
どちらの言語も、変数(approxのような識別子)を使用し、従来の数学と同様に算術演算などで(x - mean) / nといった式を構築している。
そして、どちらの言語も、変数は通常の代数のような単一のデータ項目だけではなく、一連のデータ項目をその値として取ると考えられる。
また、どちらの言語も、通常の数学と同じように「仮引数」を使って、通常の数学で使用されている関数と同じようなものをプログラマは定義している。

要するに、どちらの言語も記法では普通の数学に似ているが、そこには追加で「動的」な側面が存在している。
この動的な側面は、プログラムが計算を行うことを意図しており、計算は本質的に動的な活動であるという事実を反映している。
どちらもその動的プロセスの指定に少なくとも数学の表記法を使っている。

しかしながら、2つの言語は非常に異なっている。
PASCALとLucidは同様の数学的記号を使用しているため、実際よりもずっと似ているように見えるが、これらの記号は非常に異なった方法で使われている。

PASCALのような命令型言語の文はコマンドであり、定義ではない。
最も基本的なコマンドは代入文で、すべての命令型言語は何らかの代入形式に基づいている。
FORTRANx = b + cPASCALx := b + cのような代入文は、数学に見られるような(等式による)定義に外見上は似ているが、実際は非常に異なっている。

PASCALでは、識別子は(データの)格納場所を示している。
これらの格納場所は、一度に1つのデータ項目を保持できる「入れ物」と考えることが出来る。
一般に、格納場所は、計算中、異なる時間であれば異なる項目を持っている可能性がある。
ただし、プログラムの制御下にあるコンピュータが古い値を削除して新しい値に置き換えるまでは、指定された項目はその場所に残り続けている。

代入文は、代入文の左側にある名前の格納場所に対して、ちょうどその「更新」を実行するための命令である。
マシンは、右側の式を評価し、その結果を指定された格納場所に配置するような代入コマンドを実行する。
更新される格納場所の名前は、PASCALmean := mean + dと書かれるように、右側に出てくることもある。
この形式の文は、確かにコマンドとしては意味がある。
この文は、meanに格納された値をdに格納された量だけ増やすようにマシンに指示する。
しかし、これを定義文として解釈すると、文はナンセンスである(つまり、dの値が0である場合を除き、無意味である)。

命令型言語は、他の種類の基本的なコマンド(入出力文など)を持っているが、単純なコマンドではそれほど多くを達成することは出来ない。
それゆえ、命令型言語は、より単純なものから複雑なコマンドを構築するための多数の「制御構造」を持っている。
これらの「制御構造」によって、命令型プログラマはいくつかのより単純なコマンドを特定の順序で「実行」するよう指定することが可能になる。
例えば、ある条件が真であるまで1つのコマンドを繰り返し実行したり、あるいは、結果に対応する数に応じて、多数のコマンドのうちの1つを選択して実行したり、といった感じだ。
さらに、命令型プログラマは、特定のコマンドに名前をつけ、その名前を使ってそのコマンドを「呼び出す」ことが出来る。
これらの「プロシージャ(procedure、手続き)」はパラメータつきで呼び出すことができ、結果を返すことも出来る(この場合、「関数手続き」または単に「関数」と呼ばれる)。

要するに、PASCALプログラムは、これらの値がどんなものであるべきかだけでなく、所望の値がどのように計算されるかを詳細に指定する。
命令型プログラマは、プログラムの制御構造によってプログラムのテキストを飛び回り、指定された順序でプログラムの代入文を実行、再実行することで、コンピュータはプログラムを実行するのだと考える。
命令言語では、プログラマは、マシンが生成する必要がある値(データ)ではなく、マシンが実行する必要がある動作を指定することに、主に関心がある。

Lucidプログラムには、代入文と多少似ている文がある。
x = a + bといった「割り当て(assignment)」の一部は、十分に従来のように見えるが、

i = 1 fby i + 1;

であったり、あるいは

d = x - next x;

といったものは、従来の言語では見つけられない、不思議な「時間的」演算子を使用している。
一方で、k = 2 * k + 1のような、なんの問題もなさそうな割り当てでさえ、Lucidでは全く予期しない結果となる。

与えられたブロック内では、特定の変数への「割り当て」は1度しか許されず、与えられたブロック内で文の順序は無関係であるーーすなわち、プログラムの意味には影響しない。
Lucidでは、定義文は唯一の種類の文であり、read文やwrite文、goto文、do-while文やfor文、if文といったものは存在しないーー要するに、どんな種類の制御文もない。
Lucidでプログラマは独自の関数を定義することが出来るが、呼び出し規約といったものはない。
関数は副作用(side effect)を持つことは出来ない。
それらは本当に数学的な意味での関数である。
さらに、コマンドも副作用もないため、プロシージャはありません。

Lucidは、PASCALプログラマが使う動的なコンセプト(繰り返し)を保持していたり、他の動的なコンセプト(フィルタリング)を追加していたりするが、「制御フロー」の考えを完全に削除する。
上のPASCALプログラムでは、変数approxの一連の値は、2つの代入文の実行によって生成されている(2つ目の代入文は繰り返し実行される)。
しかし、Lucidプログラムでは、対応する変数approxの一連の値全体が、問題の変数のただ1つの定義文によって指定されている。
Lucidプログラムの実行において、マシンがテキストの特定の位置に達したと言うのは、意味がないーー実際、「実行」という言葉自体、本当に適切ではない。
Lucidプログラムは式であり、その出力は(式としての)その値である。
それゆえ、Lucidプログラムを実行しているマシンは、式を評価しているのであって、実行しているわけではない。

1.3 制御フロー v.s. データフロー

LucidによるプログラムとPASCALによるプログラムの違いは、2つの言語の違いだけではない。
2つの言語のデザインは、言語の実装に使用されるマシンの構造、すなわち「アーキテクチャ」を反映している。
LucidおよびPASCALの異なるアプローチは、基本的に異なる2つの計算モード、すなわち、所望の結果を計算する2つの非常に異なる方法を反映している。

PASCALのような命令型言語のプログラムは、「フォン・ノイマン・マシン」(数学者ジョン・フォン・ノイマンの名前にちなんで名付けられた)で動作するように意図されている。
フォン・ノイマン・マシンは、大きなメモリに接続された小さなプロセッサで構成されていて、このメモリが膨大な格納場所の集合体になっている。

          storage
         +--------+--------+
         | mean   | 23.078 |
         +--------+--------+
         | a      |  8.600 |
         +--------+--------+
         | n      |  7.000 |
         +--------+--------+
         | approx | 13.500 |
         +--------+--------+
         | d      |  0.036 |
         +--------+--------+
         |        |        |
                 ...
         |        |        |
+-----+  +--------+--------+
| CPU |==|        |        |
+-----+  +--------+--------+

データ項目は、メモリから1つずつ取り出され、実際の計算が実行される中央処理装置(CPU)に送られ、その結果が1つずつ「セル」に返される。
フォン・ノイマン・マシンの基本的な哲学では、データは通常は静止している。
しばしば、銀行のセキュリティボックスや刑務所が比喩として持ち出される。
データ項目は個々のセルに安全にロックされ、一度に1つずつ処理される。
CPUは、通常メモリに保存されているプログラムによって制御される。
プログラムとは、CPUが実行する少数の基本的な操作(特定の場所の内容を取得する、乗算を行う、特定の場所に結果を格納する、など)を指定する一連の「機械命令」である。
CPUは通常、メモリに格納されている順序で命令を実行するが、プログラムの一部が繰り返し実行されるように、この命令を変更する特殊命令もある。
フォン・ノイマンアーキテクチャの2つの基本的なコンセプトは、「コマンド」と「格納場所」の2つであり、それは命令型言語の設計コンセプトと同じコンセプトに基づいている。

「データフロー」と呼ばれる、計算の1つの代替形式は、データフローネットワークを介して「流れる」動作中のデータを処理する原則に基づいている。
データフローネットワークとは、多数の通信チャネルによって接続されたノードおよび処理ノード(processing station)のシステムである。
RMSプログラムで与えられたネットワークは非常に単純だったが、一般に、処理ノードは複数の入力および出力ポートを有してもよく、また、それらは直線的に接続されている必要もなく、ネットワークはループを有していてもよい。
データフローマシンとアーキテクチャを扱う世界中の多くの研究グループがある。
Dennis, Misunas, and Leung(1977)、Davis(1978)、Keller, Lindstrom, and Patil(1979)、Arvind and Kathail(1981)、Watson and Gurd(1982)などの論文を参照せよ。

データフローは、今まさに定義したばかりであるが、非常に曖昧な用語であり、動作中のデータの処理の一般的な原則には無数のバリエーションがある。
特に単純で重要なクラスの1つは、パイプラインデータフローと呼ばれるものである。
パイプラインネットでは、データは生成された順番通りにラインを流れ、「追い越し」もなく、データのインデックス情報もない。
パイプラインのデータフローネット内のノードは、データが消費されるのと同じ速度で出力を生成する必要はない。
私たちは特に、「関数型(functional)」または「純粋な(pure)」パイプラインデータフローと呼ばれる、制限された形式のパイプラインデータフローに興味がある。
この種のデータフローでは、ネット内のフィルタは関数型である必要があるーーフィルタが関数型であるとは、その出力の全履歴は、その入力の全履歴によって決定されるということである。
関数型であることは、(大まかに言って)フィルタにランダム性がなく、フィルタへ入力がやってくる速度が出力を生成する速度にだけ影響するを意味する。

「パイプラインデータフロー」という言葉が最初にハッキリと使用されたのは、20年以上前、Conway(1963)によってだった。
McIlroy(1968)、Kahn and MacQueen(1977)、Yourdon and Constantine(1979)など、多くの人々の働きによって、プログラミングや、プログラムを構造化する技術としてデータフローを使うことが発展してきている。
1974年、Gilles Kahnは、純粋なパイプライン関数型ネットワークの振る舞いは、対応する等式の集まりの固定点によって正確に記述されるという、非常に重要な発見をした(Kahn(1974)参照)。
(Faustini(1972)は、非常に一般的な演算モデルのための「Kahn原則」の妥当性を確立した)
Kahnの研究は、データフローの理論的側面ーー主に、非関数型のノードを持つネットワークの扱いへの彼のアプローチの拡張ーーにさらなる関心を呼び起こした。

プログラムの構築に対するデータフローアプローチ(McIlroyはそれを「配管(plumbing)」と呼んでいる)は、非常に効果的であることが判明している。
データフローアプローチの大きな利点は、「モジュール」がそれらを接続するパイプラインを通じて非常に簡単な方法で相互作用することである。
モジュールは、内部動作が別の内部動作に影響を及ぼさないという意味で、互いに十分に隔離されている。
これは、PASCALのような通常のプログラミング言語では当てはまらない。
プロシージャの本体にはパラメータへの代入、さらにはグローバル変数(プロシージャの外部変数であり、パラメータにはない変数)への代入を含めることが出来る。
その結果、明らかに単純な(RMSの例のような)PASCALプログラムのモジュール(プロシージャ)は、非常に複雑なやり方で互いに情報を渡すことが出来る。

プログラミングへのデータフローのアプローチは、すでに実際にテストされている。
一般的なUNIXオペレーティングシステムの「シェル」言語は、「パイプライン」と「フィルタ」(McIlroyの影響の結果)のコンセプトに基づいている。
UNIXパイプラインは、本質的に、直線的なデータフローネットワーク(つまり、ループも分岐もないもの)である。
したがって、UNIXで提供されるデータフローの形式は非常に限定的なものとなっているが、それにも関わらず、非常に強力である。
フィルター間のインターフェースは非常に制限されていて(文字のストリーム)、干渉や副作用の危険なしに容易に組み合わせられる。
非常に多くの場合、C言語のような「高水準」の言語に「下降」する必要なしに、シェル言語だけで問題を完全に解決することが出来る。
YourdonとConstantineは正式なデータフロー方法論(彼らはそれを「変換解析(transform analysis)」と呼んでいる)を作り上げ、それを多数の重要なアプリケーションに適用した。
彼らの方法は、2つの分離された段階から出来ている。
まず、「プログラム分析(program analysis)」と呼ばれる最初の段階では、必要な計算を実行するための(パイプライン)データフローネットワークを作成する。
そして、「プログラム設計(program design)」と呼ばれる2番目の段階で、そのネットワークを手頃な言語(通常はCOBOL)に翻訳する。

Lucidは、CやCOBOL(またはコマンドを使うことも出来るUNIXシェル言語)のような命令型言語への依存から解放することによって、データフロー方法論の成功を拡大しようとしている。
すでに多くのデータフロー言語があるが、それらの大半(特に「単一割り当て」言語)は、フォン・ノイマンの計算の観点から依然として大きな影響を受けている。
多くの純粋な非手続き型言語(基本的にはLISPのバリエーション)もあるが、それらはデータフローではなく、再帰的なプログラミングスタイルを指向している。
Lucidは、プログラミングにデータフローアプローチを組み合わせて使用することを意図しているにも関わらず、クリーンで非手続き型の言語であることを意図している。
私たちの目標は、できるだけ「システム設計」の段階を簡素化することにある。
これまで見てきた通り、Lucidプログラムは、基本的にはデータフローグラフのテキスト形式でしかない。

他の「メインストリーム」プログラミング言語と比べて、Lucidが奇妙で「不自然」でさえあると、ほとんどのプログラマが思うであろうと、私たちは認めざるを得ない。
読者は、「従来の」アプローチに投資された人的および物的資源を考えれば、このような非日常的な言語には未来があるのかどうか疑問に思うかもしれない。
読者は、最近まで単純な例以外で実行可能な実装を持っていなかった奇妙な言語に本全体を捧げる判断に疑問を呈するかもしれない。
言語についてもっと知りたいと思っている熱心なLucidユーザーのコミュニティはほとんどない。

しかし、私たちが現在のどのような状況であっても、Lucidや定義的なアプローチは本質的に人間とマシンとのコミュニケーションには奇妙であったり、ピッタリくるものではないということを認めている。
私たちの意見では、プログラマーは、このアプローチを使用する経験がほとんどないため、そのアプローチが奇妙であると判断している。
長く、直線的に順序付けられたシーケンスが、1度に1つずつ、一連の変数の集合に関連付けられた値を変えていくのが計算である、と考えるのは、本当にとても自然と言えるのだろうか?
FORTRANのような言語を学ぶ学生は、FORTRAN文がコマンドであるという事実を理解することが非常に難しいことがよくある。
数学的背景を持つ人々は、=という記号についての知識に矛盾しするx = x + 1というような「文」に、完全に混乱することがよくある。

尋ねられるべき質問は、どちらのアプローチがより奇妙なのかではなく、どちらのアプローチがより優れているかである。
10進数のシステムは、最初はローマ数字と比較して非常に奇妙に見えたが、計算が非常に簡単になったために最終的に採用された。
記述の代数システムは、それが受け入れられるまでに何世紀もかかった。
カルダノは、1545年に立方体 x^3 + px + qを解くためのアルゴリズム(ルール)を次のように記述した(Smith(1929)、p.206より):

(以下、引用部分が訳しづらかったので、原文ママ

Cube the third part of the number of “things”, to which you add the square of half the number of the equation, and take the root of the whole, that is, the square root, which you will use, in the one case adding half the number which you just multiplied by itself, in the other case subtracting the same half, and you will have a “binomial” and “apotame” respectively; then subtract the cube root of the apotame from the cube root of the binomial, and the remainder from this is the value of the “thing”.

カルダノは彼の手続き型(命令型)な方法が非常に「自然」かつ「従来通り」であると疑いもしなかった。
しかし、現代の数学者は、カルダノの解答を

 {
\begin{align}
u^{1/3} - v^{1/3} \quad where \quad & u = d^{1/2} + q/2, \\
& v = d^{1/2} - q/2, \\
& d = (p/3)^3 + (q/2)^2
\end{align}
}

とはるかに簡潔に表現することが出来、読者は式の値を計算する特定の一連の手順の詳細から解放されることが出来る。

上記の方程式の根のように、代数は常に計算と密接に関連していたが、代数への命令型、手続き型アプローチは数百年前に放棄された。
しかし現代のコンピュータプログラミングでは、(第二次世界大戦中の)現代の電子デジタルコンピュータの発明以来、命令的な視点が支配的である。
重要なプログラミング言語はすべて、命令的な視点に基づいている。
もちろん、多かれ少なかれ定義的なアプローチを使用するいくつかの言語(LISPなど)はあるが、利用できるのは限られた領域で、常に「少数派」言語のままである。
働いているプログラマーの大多数は、実質的に使用する機会がなく、あらゆる形式の定義型プログラミングを経験していない。

成功の尺度として人気を考えるならば、命令型アプローチは確かに成功していると示されている。
現在書かれているほとんどすべてのプログラムは命令型である。
同様の尺度であれば、もちろん、ローマ数字や手続き型アプローチも数学で同様に成功していると言える。
ルネサンス期には、これまで以上にこれらのシステムは使用されていた。
科学の急速な進歩は、はるかに複雑な問題に古い手続き代数表記法を適用することを数学者に要求した。
同時に、貿易と産業の大幅な拡大は、「従来の」数のシステムを、複雑さに慣れていない多数の普通の人々に計算させることを要求した。
1000年以上にわたり適切であると判明されていた古い表記システムは、基本的な欠陥を明らかにし始めた。
最終的には、位置表記法(position notation)や参照透過性(referential transparency)といった、根本的に異なる原則に基づく、まったく新しいシステムに置き換えられた。


時代が時代なので、出てくるプログラミング言語の名前がPASCALとかFORTRANCOBOLだったりするのがちょっと面白い。

そして、この開き直りであるw
Lucidが奇妙に見えることを認めた上で、命令型言語だって数学的に見れば奇妙だろうと開き直り、かつてのローマ数字や、変数を使わずに手続き的に解法を記述するスタイルの話を引き合いに出してきている。
位取り記法や変数を使う記法だって、出てきた当時は奇妙だったろうけど、それまでの方法には問題があったから、最終的には置き換えられた。
それと同じように、命令型言語にも問題があるから、今はLucidは奇妙に見えるだろうけど、最終的にはLucidのような言語に変わっていくだろう、と。

じゃあ、命令型言語の問題って何なのさ?という話については、次回で。

今日はここまで!

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

昨日の続き。

1. イントロダクション

Lucidはプログラミング言語だが、読者がすでに慣れ親しんでいるプログラミング言語(BASICやPASCAL、あるいはLISPでさえ)とは、まったく異なる。

以下は、有理数を含む計算を記述した簡単なLucidプログラムである。
このプログラムは、「実行しながら」入力の二乗平均平方根(※二乗平均平方根 - Wikipedia)を計算する。
もっと分かりやすく言えば、n番目の出力は、入力された最初のn個の数字の二乗平均平方根(二乗して平均をとった値の平方根)となっている。

sqroot(avg(square(a)))
where
    square(x) = x * x;
    avg(y) = mean
    where
        n = 1 fby n + 1;
        mean = first y fby mean + d;
        d = (next y - mean)/(n + 1);
    end
    sqroot(z) = approx asa err < 0.0001
    where
        Z is current z;
        approx = Z/2 fby (approx + Z/approx )/2;
        err = abs(square(approx) - Z);
    end
end

数学(あるいは単なる代数でもいい)の知識を持つ読者ならば、これが初めて見たLucidのプログラムであったとしても、プログラムがどのように動作するかをおそらく推測できるだろう。
プログラムは、入力された数値の二乗を作る関数square、それらの数値の実行中の平均を生成する関数avg、そして、その平均の平方根を生成する関数sqrootを使用している。

上記のプログラムによって記述された計算は、3つのコンポーネントが直列に接続された単純なネットワークであるとして理解することが出来る:

 input  +--------+ squares  +-----+ averages  +--------+ output
------->| square |--------->| avg |---------->| sqroot |-------->
        +--------+          +-----+           +--------+

このネットワークはLucidの式sqroot(avg(square(a)))に対応ていて、3つのコンポーネントはそれぞれプログラムで定義された3つの関数に対応している。
Lucidプログラマは、入力値(実際には変数aの値)の無限の流れが、'input'と書かれた矢印に沿って左からやってくるのを想像している。
これらの値は、3つの「コンポーネント」(もしくは「ブラックボックス」)を通過して変換され、'output'と書かれたラインで「外部」に送り出される。
プログラムの出力は、最後の値のストリームであり、この値のストリームは、プログラムの使用方法に応じて、プリンタに送られたり、あるいは、ファイルに保存されたりする。
このシステムを通過するデータの「粒」は「データン(datons)」と呼ばれ、それらが通過する(そして変換を行う)コンポーネントは、電子工学のアナロジーで「フィルタ」と呼ばれる。

入力値は、squareと書かれた最初の「コンポーネント」(もしくは「ブラックボックス」)を1つずつ通過していく。
squareコンポーネントは、受け取った値の二乗を1つずつ計算し、値を受け取った順に、二乗された値をsquaresと書かれたラインへ送り出す。

二乗された数は、avgと書かれた2番目のブラックボックスに至るまで、squaresと書かれたラインを移動していく。
このコンポーネントは、これらの数値を1つずつ受け取り、それまでに受け取ったすべての入力の平均を計算する。
その新しく得られた平均値は、計算されるたびに、averagesと書かれたラインへ1つずつ送り出される。

これらの平均値は、sqrootと書かれた3番目のブラックボックスに供給される。
このコンポーネントは、それらを受け取ると、受け取った数値の平方根を計算し、それら平方根を生成した順にoutputと書かれたラインへ1つずつ渡していく。

数学に詳しい(またはプログラミングの知識がある)読者は、おそらく個々のコンポーネントがどのように計算を実行しているかを推測することも出来るだろう。
squareの定義は、各入力の2つのコピーを掛け合わせるという明白な考えに基づいている。
avg関数の定義は、より洗練されたアルゴリズムを使用している。
それは実行中の引数の合計値を保持せず、代わりに、計算された直前の平均値を適切な増分だけ増加させる。
最後に、プログラム内で定義されたsqroot関数は、ニュートン法を使って引数の平方根を計算する。
それは、希望された精度が達成されるまで、徐々によりよい近似値を生成していく。

当然のことながら、このネットワーク内の3つのコンポーネントは、それらの計算を並行して(in parallel)実行することが出来、すなわち、それらはすべて同時に動作することが出来る。
avgフィルタが平均値を生成し始める前に、squareフィルタがすべての入力を受け取ってすべての二乗を計算する必要はない。
つまり、その上流では次の入力を準備し、下流では出力された最後の値を処理しつつ、avgフィルタは1つのアイテムを処理することが出来る。
ネットワーク内のフィルタは、それぞれ異なる割合で動作する場合もあり、それらの活動が同期していると仮定する必要はない。
すなわち、それらはすべて同時に入力を読み取り、同時に出力を生成する。
フィルタの中に他より速くデータを処理できるものがあれば、入力待ちの状態でアイドル状態になったり、処理待ちのラインにデータンをキューイングし始めるだろう。
これらの現象はいずれも、プログラムによって出力される最終的な一連の値には影響しない。
これらの値が生成される割合と、出力を生成するのに必要なリソース(キューにデータンを保存するためのスペースなど)にのみ影響する。

1.1 何がLucidを動作させているのか?

この時点で、読者は、私たちが実際のプログラムがやっていること以上のことを書いていると疑うかもしれない。
その疑惑は基本的には正しく、記述された計算の様子は、実際にはプログラムの1つの解釈でしかない。

ほとんどの従来のプログラミング言語では、プログラムが生成するであろう動的な様子(ネットワークを通るデータの流れなど)に関する明示的な情報を、プログラマが提供する必要がある。
そのような言語での経験を持つ読者は、どのラインがどのフィルタに接続されているか、どのラインが入力あるいは出力であるのか、ラインの初期内容は何なのか、といったことを、面倒で厄介な特殊用語(jargon)で指定し、データフローネットワークを記述しなければならないのだろうと予想するだろう 。
例えば、次のような感じだ:

NETWORK DIVISION.
      CONNECT PROGRAM-INPUT TO SQUARE-INPUT
      CONNECT SQUARE-OUTPUT TO AVG-INPUT
      CONNECT AVG-OUTPUT TO SQROOT-INPUT
      CONNECT SQROOT-OUTPUT TO PROGRAM-OUTPUT

しかし、Lucidプログラマはラインやフィルタを直接は操作しない。
代わりに、Lucidユーザーは処理されるデータと適用される変換を指定する。

例えば、sqroot(avg(square(a)))という式を考えてみよう。
式それ自体から、変換squareがデータaに適用され、その結果に変換avgが適用され、そしてさらにその結果に変換sqrootが適用されることは、明らかである。
さらに、式それ自体は、(全体として)3つの変換すべてを指定された順序で適用した最終的な結果を示している(あるいは表現している)。
この最終結果はプログラムの出力となるため、「出力」用の独立した文や宣言は必要ない。
同様に、(フィルタへの最初の入力を表している)変数aは、プログラムで定義されていない。
変数aが表すデータは任意であり、何でも構わないので、それゆえ、プログラムへの入力として扱うことが出来る。

sqroot(avg(square(a)))は、プログラマが提供する必要があるすべての情報を(whereに続く補助定義と一緒にすることで)含んでる。
where節と一緒になることで、この式は出力が何であるかーーつまり、式の値ーーを正確に指定している。
しかし同時に、その式はその出力がどのように得られるかーーつまり、入力に関してsquareargsqrootという変換をこの順に適用していことーーをある程度指定している。
したがって、ボックスやラインについて直接話さなければならない絶対的な必要性はなく、上記のネットワークは、与えられた式の単純なグラフ表現と考えることが出来る。
また、それ自体でシンプルに元の式の2次元的な表現ともいえるグラフを特定することが出来るので、(上で仮に与えた「プログラム」のような)2番目のテキストを書く必要はない。

したがって、Lucidのプログラムは、式で参照された変換と(入力以外の)データによる、単なる式である。
プログラムの出力は、単純に、プログラムで式として示されたデータ、すなわち、プログラムの値である。
Lucidは、BASICやCOBOLよりも、学校の代数によく似ている。

この時点で、数学に詳しい読者は懐疑的になることだろう。
Lucidは確かに従来の数学のように見えるが、その見た目は欺瞞であるかもしれない。
結局のところ、多くのプログラミング言語は数学的な記法を使うが、(私たちが見てきたように)従来のものとは違う何かだったりする。

再びsqroot(avg(square(a)))という式を考えてみよう。
sqrootsquareというフィルタは、数値を演算する従来の数学的な関数として確かに理解できるが、avgはどうだろう?
ある数値にavgを適用した結果は何だろうか?
8の「平均」とは、何だろうか?

数学において、関数が返す値は、与えられた値、すなわち、その引数によって決定される。
しかしながら、前述の説明によれば、avgフィルタは直前の値までの平均値を記憶しており、新しい引数が与えられる度にこの記憶された平均値を更新していると考えられる。
記憶を持った数学的な関数だなんて、聞いたことがあるだろうか?
確かに、これがコンピュータサイエンス特有の動的なコンセプトである。

しかし、avgのようなフィルタによって変換された「データ」が単なる単一の数値でないことを思い出せば、この見かけ上の矛盾は解消される。
avgフィルタは、作業全体を通して、 s_0, s_1, s_2, \cdots といった一連の数値をすべて受け取る。
これはフィルタへの入力のすべてである。
同じように、フィルタはただ1つの数値を生成するだけではなく、別の一連の数値 a_0, a_1, a_2, \cdotsを生成する。
これはフィルタの出力のすべてである。
したがって、フィルタを従来の数学的な関数を計算するものと考える場合、関数はその一連の数値 s_0, s_1, s_2, \cdotsを引数として与えられ、その結果として一連の数値 a_0, a_1, a_2, \cdotsを返すものでなければならない。
それは、入力のシーケンスの集合から出力のシーケンスの集合への関数でなければならない。

実際、avgフィルタによって実行される入出力変換を特定するようなシーケンスの関数fが存在することは、理解に難しくない。 与えられた一連のsに対して、f(x)は単に

 \langle s_0, (s_0 + s_1)/2, (s_0 + s_1 +s_2)/3, \cdots \rangle

という一連の平均となる。
(無限のシーケンスのみを扱えば、すべてはよりシンプルになる)

これが、従来の数学の静的性質とプログラミングの動的性質との間にある明らかな矛盾を解決するLucidの方法である。
Lucidの式は実際に数学的な意味での式であり、式で参照される関数は実際に厳密な意味での関数である。
式は、個々のデータ項目ではなく、シーケンスとして値を持っている。
そして、関数はシーケンスをシーケンスにマップする。

一貫性のために、「従来の」式および変換でさえ、シーケンスおよびシーケンスの関数として示される。
すなわち、式2 * 3はシーケンス

 \langle 6, 6, 6, 6, 6, \cdots \rangle

という値のシーケンスを持ち、squareという変換は

 \langle s_0, s_1, s_2, \cdots \rangle \mapsto \langle s_0^2, s_1^2, s_2^2, \cdots \rangle

とマップする関数に対応する。

Lucidでの式は、プログラムで言及されている変換を含むフィルタのネットワークの出力を示すものだと考えることが出来ることは、すでに見てきた。
そのような式の値は無限のシーケンスであり、それはネットワークによって生成され、その順に並べられた、すべての個々の値の完全な記録あるいは履歴として考えることが出来る。
問題の式がプログラムの場合、その無限のシーケンスは、プログラムの出力の様子の完全なる記録または履歴となる。

例えば、プログラムPの値がすべての素数の無限シーケンス( \langle 0, 3, 5, 7, 11, 13, \cdots \rangle)であれば、Pは素数を列挙するプログラムであると考えることが出来る。
そのような素数生成プログラムが実行されると、最初は数2が生成され、次に3, 5, 7, 11などが生成される。
もっとも、必ずしも一定の速度ではないが。

Lucidプログラムに現れる文、例えば

mean = first y fby mean + d;

は、実際に等式であり、その定義が有効であるプログラムの領域内での変数の値を指定する。
変数の値もデータ項目の無限のシーケンスでもあり、定義の右側の式に対応するネットワークによって生成された値の完全な記録と考えることが出来る。
(この考え方では、これらの値が一定の割合で生成されると仮定したり、これらの値の生成が他の変数または出力の生成と同期することを仮定したりしてはいけない)

プログラムは、プログラム内に定義を持たない(そして、関数定義での仮引数でもない)変数を使用することがある。
そういった変数は入力変数と呼ばれ、プログラムの値は一般にそれらの変数の値に依存する。
入力変数に与えられた値は、Lucidプログラムへの入力を構成する。
これらの値も無限のシーケンスであり、入力された順にプログラムに入力されるすべてのデータ項目の完全な記録と考えることが出来る。
ここでも、データ項目がプログラムによって入力として読み込まれる速度は常に一定であると仮定したり、データ項目が出力として書き出される速度と必ず同じであると仮定したりしてはいけない。

上のRMS(二乗平均平方根)プログラムには、入力変数が1つ、すなわち、変数aしかない。
例えば、プログラムへの入力(すなわち、aの値)が \langle 3.5, 3.2, 3.9, 4.1, 3.8, \cdots \rangleといったシーケンスであった場合、出力(すなわち、式としてのプログラムの値)は、 \langle 3.5, 3.335, 3.54, 3.69, \cdots \rangleといったシーケンスになる。
したがって、例えば3番目の数値出力は3.54であり、これは \sqrt{(3.5^2 + 3.2^2 + 3.9^2) / 3}となっている。
これはちょうど、上記のネットワークから期待されるものとなっている。

ある意味では、Lucidの「動的」な側面は、ある種の錯覚である。
Lucidは実際のところ、静的な履歴のただの微積分でしかない。
示唆的な名前(nextなど)や通常の記号(+など)を使用し、シーケンスでの各点における演算を指定することで、シーケンスのインデックス(位置を指し示す添字)を明示的に参照することをとりわけ避けて、この錯覚を保っている。

この「錯覚」はプログラミングをしやすくする上で絶対不可欠である。
厳密に静的な視点を使用しながら、すなわち、Lucidのシーケンスの履歴を文字列やリストといった別のデータ型として解釈しながらプログラムを書くことは、ほとんど不可能である。

その点、動的な視点はそれほど非現実的でもない。
Lucidプログラムが最終的には実行され、実装にはデータフローもしくはそのシミュレーションがおそらく必要となるだろう。
私たちは、静的で無限の履歴は「非現実的」であり、実際の演算の様子は「現実的」であると容易に主張することが出来る。 Lucidのデータフローによる解釈は、動的に変化するシステムでの一連の差分方程式による解釈よりも非現実的ではない。
主な違いは、微積分における「時間変数」は連続的に変化するが、Lucidの「反復時間」は離散的に変化することである。


いやはや、なんともぶっ飛んだ発想だとしか・・・

数学の式って静的だけど、コンピュータって動的に動くよね。
->
変数や関数は、時間変数を伴った無限のシーケンスと考えればいいいじゃん!
そうすれば、式は静的であるにも関わらず、様子は動的になる!

変数や関数を時間変数を伴った無限のシーケンスだと考えると、そのすべてを記述しきるのは難しいよね。
->
シーケンスの各点で保たれてる性質を微分方程式みたいに記述すればいいじゃん!
微分方程式を満たす関数が(微分方程式を解くことによって)得られるかは分からないけど、その関数の様子は(微分方程式があれば数値シミュレーションが可能になるように)動的に得られる!

微分方程式みたいに書かれていても、理解しづらいし、実行できるかも分からないよね。
->
シーケンスをデータの流れと考えて、各関数はそれを処理するフィルタであると考えればいいじゃん!
ついでにいえば、それで反復も処理できるじゃん!

・・・といった感じ。

この発想自体は非常に面白いと思うのだけど、じゃあ実際それでプログラミングしてみろと言われたら、かなり困りそう。
それこそ、平均一つとっても、普通は「「実数の有限部分集合」の集合」から「実数の集合」への写像と考えるわけで(例えば avg(\{1, 2, 3\}) = 2みたいな)、無限シーケンスの集合から無限シーケンスの集合への写像と考えるのは、ちょっと無理があるように思える。
例えば、ここでは平均を1回求めればそれで終わりだったけど、平均を何度も・・・それも有限回ではなく、無限回求めなければならない、となった場合(つまり、「無限シーケンス」の無限シーケンスを考える場合)、その構想はたちまち破綻しそうな・・・

まぁ、このあたりはあとのお楽しみということで。
(自分もまだ先をちゃんと読めてないので、これが解決されているのかどうか知らない)


ちなみに、1章はまだまだ続く・・・
先は長い・・・

今日はここまで!

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

だいぶ間が空いてしまったけど、以前書いた通り、データフロー言語であるpLucidをいじっていたりする。

この実装をいじりながらコードを読んでいたのだけど、どうにも分からない部分が。
というのも、実装が丸々ifdefで落とされていて、しかも、落とされたコードも実質何もしていないから。

まぁ、やりたかったであろうことは何となく分かるので、それなら自分で実装してしまおうかな、と。
けど、実装から仕様を理解しようとしているのに、その実装がないわけだから、どうあるべきかという仕様がまず分からない・・・
なので、仕様をちゃんと調べるしかないかな、と。

幸い、「Lucid, the Dataflow Programming Language」という論文?がネットに落ちてて、仕様はそこから理解できそうだった。

Lucid, the Dataflow Programming Language

ただ、自分の英語力が低いのと、やたら難解な単語が使われてて、読みにくい・・・

ということで、Google先生の力を借りながら、翻訳してみた。

なお、直訳じゃなくて、文脈からの自分の推測も入っているので、注意。

序文

Academic PressがLucidに関する本を書かないかと最初に打診してきたとき、私たちは容易に同意した。
本の制作は比較的簡単だと私たちは考えていたからだ。
つまり、既存の論文やレポートをいくつか集めて、編集上のコメントを追加するだけでよかったはずだった。
それが終わったら、私たちはもっと野心的なプロジェクトに移ることが出来るはずだった。

しかし、私たちが論文やレポートを読み返してみると、当初の計画ではダメなことに気がついた。
Lucidは(今もそうだが)非常に新しい開発だった。
にもかかわらず、私たちが提案した様々な論文が互換性を失うほどに大きく進化してしまっていたからだ。
いくつかの変更は細かい部分だったり技術的なものだったりしたが、それらは全体的に根底にある動機の根本的な変化を反映したものだった。

Lucidは1974年にカナダのワーテルロー大学で生まれた。
当時、この本の著者らは、数学科で教鞭をとっていた。

Lucidを開発する当初の目標は、非常に控えめだった。
私たちは、従来の「主流」のプログラミングが、代入やgotoのない、純粋に宣言的な言語で出来ることを示したかった。
私たちは当時(そして今も)、本当の「構造化プログラミング」では、まずこれらの機能(※代入やgoto)を排除する必要があり、プログラム検証にこそ実用的な可能性があると感じていた。

もちろん、私たちは、LISPのような「関数型(functional)」あるいは「適用型(applicative)」言語で、再帰を使用するだけで、どんなプログラミングの問題も原理的には解決できることを知っていた。
しかしながら、このアプローチはまったく信頼できなかった。
純粋な再帰による解法は(明らかに)反復を使用できず、それゆえ、実際に毎日のプログラミングで使用されるアルゴリズムのほとんどを除外することになる。
再帰的プログラミングの擁護者は、「末尾再帰」を反復と同等だと見做すが、そのような不自然なパラメータリストを持つプログラムは、毎日のプログラミングでは実際には使えたものではない)

実際のところ、LISPのような言語はループを書くことを許容している。
しかしそれは、(LISPがそれをprogという機能で実現しているように)代入を言語へ許容しなおしているだけでしかない。
そこで、私たちの目標は、progのように「汚れた」機能を導入することなく、反復アルゴリズムを宣言型(あるいは「非手続き型」)言語で表現できると示すことだった。

私たちの出発点は、以下の代入文

I := 1;
...
I := I + 1;

は、以下の宣言文

first I = 1;
next I = I + 1;

で言い換えることができるということだった。

これらの宣言文は、firstnextを演算として使用することができ、これらの演算は、単なる識別子や式にも適用できることを示唆している。
そして、next(x + y) = next(x) + next(y)のような直観的に真となる等式を、プログラムの動的な側面について使うことが出来る、と代数的に判断できる可能性を開いた。(※ここ、かなり意訳)

しかし、当初、それがどのような値が示しているのかということは、ハッキリしなかった。
最終的には、変数や式は、個々のデータの無限シーケンス(または履歴)を示していることに気づいたが、それまでLucidの作業は数ヶ月停止した。

ひとたびこの原則が確立されてしまえば、少なくとも単純な反復アルゴリズムは、等式の集合によって自然な形で表現できるということを実際に示すことが出来た。
また、プログラムの論証が本当にずっとシンプルであることを確認できた。
1つの利点は、表明(assertion)が策定された(formulated)言語がプログラミング言語の拡張であることだった。(※よく分からない・・・)
プログラム内の文(statement)はそのままプログラム内の変数の値についての真となる表明であり、より深い性質を導出するための公理を構成していた。

この初期の仕事は、原理的には反復がちゃんとできることを示した。
しかし、オリジナルのLucidは非常に単純な言語であり、非常に単純なアルゴリズムしか表現できなかった。
主流の命令型言語を置き換えることを本当に望むのなら、より現実的なアプリケーションを等式のスタイルでプログラミングできることを示す必要があった。
そこで、私たちは、より野心的な問題に取り組める言語の拡張を検討し始めた。

最初に追加された機能は(ループの)入れ子で、比較的簡単であることが示された。
それは単に変数の値が複数の時間パラメータに依存できるようにしたものだった。
(単純な無限のシーケンスは、1つのパラメータに依存する値と考えることができ、そのパラメータはシーケンスの位置であり、それを私たちは「時間」と呼んだ)
入れ子にした後、最も明白な次の一歩は、配列を追加することだったが、ここで何かが捻れてしまった。
私たちは、(APLのラインを参考に)配列を扱うためのシンプルな代数を見つけようと大量の努力を費やしたが、ほとんど成功しなかった。
主な問題は、配列が有限で、そして有限次元であると考えていたことだったと、今の私たちは気づいている。
私たちは、無限の配列ははるかにいい性質を持っていることは分かってたが、まだ従来の計算モデルに適合させることができていなかった。

そこで、私たちは配列に関する作業を中断し、他の最も明白な拡張、すなわちユーザ定義関数について検討した。
この拡張は、最も単純なものであることが分かったが、私たちが予想していたよりも強力だった。
特別なLucid演算を使用して定義された関数は、フィルタ(データストリームを変換する、連続的に動作するプロセス)と考えることが出来ることを発見した。
私たちの言語はそうしてコルーチンのような機能が得た。
コルーチンは強力なプログラミングツールとして知られていたが、非常に複雑であるとも考えられていた。
しかし、Lucidでは、コルーチンはほとんどタダで実現された!

ユーザー定義関数の成功は、Lucidでのアプローチへの信頼を強化した。
最終的に、従来の命令的ループで表現された繰り返しではなく、他の形式で表現された繰り返しがあることを理解した。
プログラミングへの新しいアプローチの根底にあるのは、計算そのものへの新しいアプローチであることに気がつき始めた。
それはつまり、データフローアプローチである。
それ以来、Lucidは古いアルゴリズムを表現するための新しい方法というだけではなくなった。
新しい(データフロー)アルゴリズムを表現するための新しい方法となった。
ある意味では、当初の目的は逆転してしまった。
もともとは、計算の従来のアプローチを数学的にちゃんとしたものに出来ることを示したかった。
今や、私たちは古い方法を排除し、まったく新しい世界観に置き換えることができることを示そうとしている。

もちろん、私たちはデータフローや計算へのデータフローアプローチを発見したと主張はしていない。
これに関して、M. McIlroy、J.Dennis、G. Kahnなど多くの人々が信用を共有している。
データフローが強力なプログラミング手法であるという実証的な証拠を提供したUNIXの開発者に、私たちは借りがある。

今の本は、私たちが当初書こうとしていた(あるいはむしろ、組み立てようとしていた)本とは、ほとんど関係がないものになっている。
ここで強調されているのは、お堅い研究の対象としてではなく、実用的なツールとしてのLucidである。
プログラムの検証は依然重要であり、関数型言語でははるかに簡単だと考えているが、それに関しては非常に簡単かつ形式張らない方法で取り扱う(変換には十分な注意が必要)。
実用的でない計算モデルに基づき、現実的な問題にフィットしていない言語で書かれたプログラムの正しさを実証することには、ほとんど意味がないと思われる。
したがって、本書の第一の目的は、データフローが本当に逐次的・命令的計算の代替であること、そして、データフローアルゴリズムをLucidで自然かつ簡潔に表現できることを示すことである。
私たちは成功したと期待しているが、判断は読者に任せたい。

しかしながら、あなたが判断を下す前に、A. Faustiniの優れたpLucidインタプリタ(これはC. Ostrumの最初の草稿に基づいている)を入手することをお勧めする。
言語は興味深いアプリケーションをプログラムするのに十分なほどリッチであり、エラー処理は優れている。
インタプリタは(ほとんどのインタプリタがそうであるように)大きく、ときに遅いが、いくつかのアプリケーションで使用するには十分である。
この本に書かれているサンプルプログラムは、Lucid拡張のものを除いてすべてがテストされているので、同様にうまく動くはずである。
唯一の問題は、現在のバージョンのインタプリタC言語で書かれていて、UNIXを必要とする。
不幸にも、より古く、より原始的なOSの使用を余儀なくされている人は、Lucidによるデータフロープログラミングを直に経験するのは、しばらく待つ必要があるだろう。

(以下、謝辞なので原文ママ

We would like to thank the funding agencies that supported the development of Lucid, and the production of this book. Initially this was done completely by the Canadian Science Research Council (subsequently the Natural Sciences and Engineering Research Council), even after one of the two of us (Bill Wadge) moved to the University of Warwick, in England. Eventually he obtained funding from the Science and Engineering Research Council of the United Kingdom. We are grateful for the help of both these bodies.

Collaboration across the Atlantic is not the easiest thing, and the development of the language was probably slower than necessary. (It did, however, enable us to preface lectures about Lucid with the observation that it was being developed by an Englishman working in Canada and a Canadian working in England.) At present, Ed Ashcroft is at SRI International, in California, and Bill Wadge at the University of Victoria, in British Columbia, Canada, and so now the authors are at least on the same side of the same continent.

We also would like to take this opportunity to thank the many people who have contributed to the development of Lucid and to the production of this book. These include (in alphabetical order) Thomas Cargill, Mansour Farah, Tony Faustini, Patrick Gardin, Christoph Hoffman, Steven Matthews, David May, Calvin Ostrum, Paul Pilgram and Ali Yaghi. Our special thanks go to Tony Faustini, Ali Yaghi and Steve Matthews, who wrote the pLucid manual and consented to having it included in the appendix. Extra special thanks go to Calvin Ostrum and Tony Faustini. Calvin became interested in Lucid as a second-year undergraduate student at Waterloo and singlehandedly produced an interpreter, written in C, in his third year. This interpreter forms the basis of the pLucid interpreter, which Tony Faustini developed while a research assistant at Warwick. Tony also contributed greatly to the design of pLucid itself.

Finally, we would like to thank the many students at the Universities of Warwick, Waterloo and Victoria who registered in courses in which Lucid was taught. Some of them were cruelly treated by early versions of pLucid and its interpreter, but they showed that mere mortals are capable of writing dataflow programs.

December 1984
Victoria, Canada

W. W. Wadge
E. A. Ashcroft

ということで、まずは序文だけ。

Java8でラムダ式が導入され、Haskellモナドによる関数の組み上げを、データの流れの組み上げと解釈してStreamという機能として実現したわけだけど、この時代にデータフローというものを見出しているというのは非常に興味深い。

今日はここまで!