いものやま。

雑多な知識の寄せ集め

「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のような言語に変わっていくだろう、と。

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

今日はここまで!