昨日の続き。
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
節と一緒になることで、この式は出力が何であるかーーつまり、式の値ーーを正確に指定している。
しかし同時に、その式はその出力がどのように得られるかーーつまり、入力に関してsquare
、arg
、sqroot
という変換をこの順に適用していことーーをある程度指定している。
したがって、ボックスやラインについて直接話さなければならない絶対的な必要性はなく、上記のネットワークは、与えられた式の単純なグラフ表現と考えることが出来る。
また、それ自体でシンプルに元の式の2次元的な表現ともいえるグラフを特定することが出来るので、(上で仮に与えた「プログラム」のような)2番目のテキストを書く必要はない。
したがって、Lucidのプログラムは、式で参照された変換と(入力以外の)データによる、単なる式である。
プログラムの出力は、単純に、プログラムで式として示されたデータ、すなわち、プログラムの値である。
Lucidは、BASICやCOBOLよりも、学校の代数によく似ている。
この時点で、数学に詳しい読者は懐疑的になることだろう。
Lucidは確かに従来の数学のように見えるが、その見た目は欺瞞であるかもしれない。
結局のところ、多くのプログラミング言語は数学的な記法を使うが、(私たちが見てきたように)従来のものとは違う何かだったりする。
再びsqroot(avg(square(a)))
という式を考えてみよう。
sqroot
とsquare
というフィルタは、数値を演算する従来の数学的な関数として確かに理解できるが、avg
はどうだろう?
ある数値にavg
を適用した結果は何だろうか?
8の「平均」とは、何だろうか?
数学において、関数が返す値は、与えられた値、すなわち、その引数によって決定される。
しかしながら、前述の説明によれば、avg
フィルタは直前の値までの平均値を記憶しており、新しい引数が与えられる度にこの記憶された平均値を更新していると考えられる。
記憶を持った数学的な関数だなんて、聞いたことがあるだろうか?
確かに、これがコンピュータサイエンス特有の動的なコンセプトである。
しかし、avg
のようなフィルタによって変換された「データ」が単なる単一の数値でないことを思い出せば、この見かけ上の矛盾は解消される。
avg
フィルタは、作業全体を通して、といった一連の数値をすべて受け取る。
これはフィルタへの入力のすべてである。
同じように、フィルタはただ1つの数値を生成するだけではなく、別の一連の数値を生成する。
これはフィルタの出力のすべてである。
したがって、フィルタを従来の数学的な関数を計算するものと考える場合、関数はその一連の数値を引数として与えられ、その結果として一連の数値を返すものでなければならない。
それは、入力のシーケンスの集合から出力のシーケンスの集合への関数でなければならない。
実際、avg
フィルタによって実行される入出力変換を特定するようなシーケンスの関数f
が存在することは、理解に難しくない。
与えられた一連のs
に対して、f(x)
は単に
という一連の平均となる。
(無限のシーケンスのみを扱えば、すべてはよりシンプルになる)
これが、従来の数学の静的性質とプログラミングの動的性質との間にある明らかな矛盾を解決するLucidの方法である。
Lucidの式は実際に数学的な意味での式であり、式で参照される関数は実際に厳密な意味での関数である。
式は、個々のデータ項目ではなく、シーケンスとして値を持っている。
そして、関数はシーケンスをシーケンスにマップする。
一貫性のために、「従来の」式および変換でさえ、シーケンスおよびシーケンスの関数として示される。
すなわち、式2 * 3
はシーケンス
という値のシーケンスを持ち、square
という変換は
とマップする関数に対応する。
Lucidでの式は、プログラムで言及されている変換を含むフィルタのネットワークの出力を示すものだと考えることが出来ることは、すでに見てきた。
そのような式の値は無限のシーケンスであり、それはネットワークによって生成され、その順に並べられた、すべての個々の値の完全な記録あるいは履歴として考えることが出来る。
問題の式がプログラムの場合、その無限のシーケンスは、プログラムの出力の様子の完全なる記録または履歴となる。
例えば、プログラムPの値がすべての素数の無限シーケンス()であれば、Pは素数を列挙するプログラムであると考えることが出来る。
そのような素数生成プログラムが実行されると、最初は数2が生成され、次に3, 5, 7, 11などが生成される。
もっとも、必ずしも一定の速度ではないが。
Lucidプログラムに現れる文、例えば
mean = first y fby mean + d;
は、実際に等式であり、その定義が有効であるプログラムの領域内での変数の値を指定する。
変数の値もデータ項目の無限のシーケンスでもあり、定義の右側の式に対応するネットワークによって生成された値の完全な記録と考えることが出来る。
(この考え方では、これらの値が一定の割合で生成されると仮定したり、これらの値の生成が他の変数または出力の生成と同期することを仮定したりしてはいけない)
プログラムは、プログラム内に定義を持たない(そして、関数定義での仮引数でもない)変数を使用することがある。
そういった変数は入力変数と呼ばれ、プログラムの値は一般にそれらの変数の値に依存する。
入力変数に与えられた値は、Lucidプログラムへの入力を構成する。
これらの値も無限のシーケンスであり、入力された順にプログラムに入力されるすべてのデータ項目の完全な記録と考えることが出来る。
ここでも、データ項目がプログラムによって入力として読み込まれる速度は常に一定であると仮定したり、データ項目が出力として書き出される速度と必ず同じであると仮定したりしてはいけない。
上のRMS(二乗平均平方根)プログラムには、入力変数が1つ、すなわち、変数a
しかない。
例えば、プログラムへの入力(すなわち、a
の値)がといったシーケンスであった場合、出力(すなわち、式としてのプログラムの値)は、といったシーケンスになる。
したがって、例えば3番目の数値出力は3.54であり、これはとなっている。
これはちょうど、上記のネットワークから期待されるものとなっている。
ある意味では、Lucidの「動的」な側面は、ある種の錯覚である。
Lucidは実際のところ、静的な履歴のただの微積分でしかない。
示唆的な名前(next
など)や通常の記号(+
など)を使用し、シーケンスでの各点における演算を指定することで、シーケンスのインデックス(位置を指し示す添字)を明示的に参照することをとりわけ避けて、この錯覚を保っている。
この「錯覚」はプログラミングをしやすくする上で絶対不可欠である。
厳密に静的な視点を使用しながら、すなわち、Lucidのシーケンスの履歴を文字列やリストといった別のデータ型として解釈しながらプログラムを書くことは、ほとんど不可能である。
その点、動的な視点はそれほど非現実的でもない。
Lucidプログラムが最終的には実行され、実装にはデータフローもしくはそのシミュレーションがおそらく必要となるだろう。
私たちは、静的で無限の履歴は「非現実的」であり、実際の演算の様子は「現実的」であると容易に主張することが出来る。
Lucidのデータフローによる解釈は、動的に変化するシステムでの一連の差分方程式による解釈よりも非現実的ではない。
主な違いは、微積分における「時間変数」は連続的に変化するが、Lucidの「反復時間」は離散的に変化することである。
いやはや、なんともぶっ飛んだ発想だとしか・・・
数学の式って静的だけど、コンピュータって動的に動くよね。
->
変数や関数は、時間変数を伴った無限のシーケンスと考えればいいいじゃん!
そうすれば、式は静的であるにも関わらず、様子は動的になる!
変数や関数を時間変数を伴った無限のシーケンスだと考えると、そのすべてを記述しきるのは難しいよね。
->
シーケンスの各点で保たれてる性質を微分方程式みたいに記述すればいいじゃん!
微分方程式を満たす関数が(微分方程式を解くことによって)得られるかは分からないけど、その関数の様子は(微分方程式があれば数値シミュレーションが可能になるように)動的に得られる!
微分方程式みたいに書かれていても、理解しづらいし、実行できるかも分からないよね。
->
シーケンスをデータの流れと考えて、各関数はそれを処理するフィルタであると考えればいいじゃん!
ついでにいえば、それで反復も処理できるじゃん!
・・・といった感じ。
この発想自体は非常に面白いと思うのだけど、じゃあ実際それでプログラミングしてみろと言われたら、かなり困りそう。
それこそ、平均一つとっても、普通は「「実数の有限部分集合」の集合」から「実数の集合」への写像と考えるわけで(例えばみたいな)、無限シーケンスの集合から無限シーケンスの集合への写像と考えるのは、ちょっと無理があるように思える。
例えば、ここでは平均を1回求めればそれで終わりだったけど、平均を何度も・・・それも有限回ではなく、無限回求めなければならない、となった場合(つまり、「無限シーケンス」の無限シーケンスを考える場合)、その構想はたちまち破綻しそうな・・・
まぁ、このあたりはあとのお楽しみということで。
(自分もまだ先をちゃんと読めてないので、これが解決されているのかどうか知らない)
ちなみに、1章はまだまだ続く・・・
先は長い・・・
今日はここまで!