いものやま。

雑多な知識の寄せ集め

「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という機能として実現したわけだけど、この時代にデータフローというものを見出しているというのは非常に興味深い。

今日はここまで!