いものやま。

雑多な知識の寄せ集め

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

技術 Lucid

前回の続き。

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になり、FORTRANはPL/I（あるいはFORTRAN 77）に拡張され、今はPASCALからADAが生み出されている。
制限と一般性との黄金比を得るのは不可能に思われる。
言語設計者は自分たちが成功していると思っているのかもしれないが、四半世紀経った今もFORTRANとCOBOLが依然として最も広く使われている言語である。

フォン・ノイマン言語に関する第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）

技術 Lucid

前回の続き。

なお、かなり意訳。

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のような命令型言語の文はコマンドであり、定義ではない。
最も基本的なコマンドは代入文で、すべての命令型言語は何らかの代入形式に基づいている。
FORTRANのx = b + cやPASCALのx := b + cのような代入文は、数学に見られるような（等式による）定義に外見上は似ているが、実際は非常に異なっている。

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

代入文は、代入文の左側にある名前の格納場所に対して、ちょうどその「更新」を実行するための命令である。
マシンは、右側の式を評価し、その結果を指定された格納場所に配置するような代入コマンドを実行する。
更新される格納場所の名前は、PASCALでmean := 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とかFORTRAN、COBOLだったりするのがちょっと面白い。

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

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

今日はここまで！

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

技術 Lucid

昨日の続き。

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フィルタは、作業全体を通して、 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）

技術 Lucid

だいぶ間が空いてしまったけど、以前書いた通り、データフロー言語である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;

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

これらの宣言文は、firstやnextを演算として使用することができ、これらの演算は、単なる識別子や式にも適用できることを示唆している。
そして、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という機能として実現したわけだけど、この時代にデータフローというものを見出しているというのは非常に興味深い。

今日はここまで！

トリックテイキングゲームのイロハを語ってみた。（その2）

ゲーム

昨日はトリテのイメージと専門用語について語ってみた。

今日はトリテのプレイングについて語ってみたい。

f:id:yamaimo0625:20160313142903j:plain

プレイの方針

さっそく、プレイの方針について。

といっても、自分もそんなにトリテが上手いわけではないので、基本的なところを。

まず、トリテをやったことがある人なら経験があると思うのが、選択の余地もなくほぼ自動的に出すカードが決まってしまって、ぐぬぬとなったこと。
自分から能動的な選択が出来ずに、何これクソゲー、と思ったことがある人も多いはず・・・

これを生んでいるのが、「マストフォロー」というルール。
そして、上記のような経験をすると、「マストフォロー」とかいう、プレイヤーから選択肢を奪うクソルールは、なくした方がいいんじゃないか？と思い、そんなクソルールを採用しているトリテなんか嫌いだ、となる人がいても、おかしくはないと思う。

けど、そこが逆に、ポイントとなる。

考えてみて欲しい。

なんで出せるカードが限られてしまうのか？

答えは簡単。

リードされたのと同じスートのカードを持っているから。

もしくは、

リードできていないから。

逆に言えば、それらを避けるように出来れば、自由にカードを出すことが出来る、と。

例えば、リードされたのと同じスートのカードを持っていなければ、自由にカードを出せるので、切り札をプレイしたり、あるいは、いらないカードを捨てたりすることが出来る。
また、そもそも自分がリードであれば、好きなカードを出し、他のプレイヤーの出すカードに縛りをかけることが出来る。

ここから導き出される方針は、以下の2つ。

まず、何かしらのスートを手札からなくすことで、自由にカードを出せる機会を増やすということ。
ちなみに、あるスートが手札にないことを、そのスートが「ボイド」である、と言ったりする。
（プログラムに馴染みのある人であれば分かると思うけど、"void"、つまり、「空っぽ」ということ）

そして、タイミングよくリードを得ることで、自分の好きなカードを出す機会を得るということ。
タイミングよくリードを取れれば、そこからいろんな行動をとることが出来る。

これまでの内容を見て分かる通り、「マストフォロー」というルールが働くことによって、トリテではリードを持っているプレイヤーが、他のプレイヤーより圧倒的に有利になっている。
テニスでいうサーブ権のようなものだ。
その、リードプレイヤーの攻撃をいかにかいくぐり、自分が攻撃するターンに持ち込めるのか。
その駆け引き、読み合い、そして、自分と相手の手札のコントロールというところに、トリテの面白さは詰まっている。

逆にいうと、「メイフォロー」のゲームだと、このあたりがかなりふわっとなる。
リードをとって攻撃しても相手はいくらでも躱しようがあるし、フォローされなかったからといってそのスートのカードが手札にないと読むことは出来ない。
「マストフォロー」によって、相手の手札のコントロールや読みが可能になり、そして、攻防の妙が生まれてくる。

じゃあ、リードを持ったときの攻撃として、どんなことが可能なのか。

まず分かりやすいのは「トランプ狩り」。
トランプ、つまり、切り札というのは、言葉通り、「フォローする側の」切り札となる。
なぜって、リードという攻撃をかいくぐり、かつ、自分がリードする権利を引っ張ってこれるわけだから。
逆にいうと、せっかくリードという権利を得ても、その権利を奪われかねないのが、トランプという存在になる。
そこで、ならばと「切り札でリード」を行うことで、無理やり他のプレイヤーから切り札を引き出すことが出来る。
そして、場に切り札がなくなれば、安心して切り札でないスートのランクの高いカードを出すことが出来るようになる。

また、ほぼ確実に勝てるカードでリードを行うというのも出来る。
例えば、まだスペードが一度もリードされていなくて、スペードの一番強いカードを持っていれば、それでリードすることで、ほぼ確実にそのトリックをとることが出来る。
というのは、まだ一度もリードされていない場合、そのスートがボイドになっている可能性は低いので、ほぼ間違いなくフォローされるから。

あとは、ボイドを作るために自分の手札にほぼないスートのカードをリードするというのもある。
ボイドが作れれば、かなりコントロールが楽になる。

それと、終盤になってくると、カードが残っているスートの種類もトランプも少なくなってくる。
そうなると、フォロー出来るかどうかで勝負が決まってくることが多い。
それこそ、そのスートで一番最弱のカードであっても、他にフォロー出来るプレイヤーがいなければ、それだけで勝ちになる。
なので、他のプレイヤーがフォローできないスートでリードを行うというのが、有効になる。

それに関連して覚えておきたいのが、「ロングスート」という概念。
これは、自分の手札で枚数がやたら多いスートのこと。
トランプが枯れている場合、リードを奪ってこのロングスートでリードを行えば、他のプレイヤーはフォローが困難で、しかもトランプで主導権を奪い返すことも出来ないので、「ずっと俺のターン！」をすることが出来る。
ただし、このロングスートは諸刃の剣でもあって、自分の手札にやたらと多いということは、他のプレイヤーの手札には少ないということ。
すると、どうなるのかというと、他のプレイヤーからリードされることが少なくなる。
結果、フォローが出来ず、全部捨て札になってしまうということも・・・
なので、リードを得るタイミングというのが非常に重要になってくる。

終盤の話に関してもう一つ、「ボイド」や「ロングスート」は手札のスートの偏りを大きくする動きなわけだけど、逆に、どのスートも出来るだけ保持しようとするのがいい場合もある。
特に、手札に強いカードがほとんどない場合。
なぜかというと、上記のようにフォローできないことを期待してリードしてくる場合があるから。
この場合、出来るだけフォロー出来るように広く持っておくことで、思わぬ勝ちを得たりすることが出来る。

カウンティング？

さて、トリテでよく話題になるのが、カウンティングの話。

上記で見ての通り、場にどんなカードが残っているのかというのは、すごく重要な情報だったりする。
なので、カウンティングは大切といえば大切。

ただ、そうなると、「カウンティングは難しいから、自分にはトリテは無理」となってしまう人もいると思う。

かくいう自分も、カウンティングは苦手w
正直、ちゃんと覚えてられない（＾＾；
なので、かなりフィーリングでしかカウンティングは行ってないけど、そんな自分でもトリテは楽しめているので、あまり肩肘張らずに楽しんだらいいと思う。

簡単に出来るカウンティングとして、「どのスートが何回リードされたか」というのがあると思う。
これをやるだけでも、だいぶ違う。
というのも、「マストフォロー」のルールがあるので、何回リードされたかを覚えておけば、そのスートが何枚くらい残っているかは、簡単に分かるから。

例えば、1つのスートが13枚で、4人でプレイする場合、平均で3枚くらい持っていることになる。
となると、1回目のリードはほぼフォローされるし、2回目のリードもけっこうフォローされる可能性が高い。
もちろん、ボイドを作られていなければ、だけど。
仮に2回とも全員がフォローすれば、13枚中8枚が使われたことになり、残りは5枚とすぐに分かる。
あるいは、一度もリードされていなければ、そのスートはほぼ13枚残っているということも分かる。

こんなふうに、どのスートが何回リードされたかという情報は、比較的覚えやすくて、結構重要なことが分かるので、オススメ。

アプリのススメ

あとは、実際に遊んでみるのが一番いいと思う。
その中で気づくことも多いだろうし。

ただ、あまり慣れてない状態でいきなり人と遊ぶのは、もしかしたらストレスがあるかも。

そんな場合、アプリで遊んでみるのも一つの方法。

オススメはウィザード。

Wizard

Wizard

  • Sean O'Connor
  • ゲーム
  • ¥480

手札をコントロールするというのがよく分かるし、何より面白い！

ということで、ぜひいろんなトリテを遊んでみて欲しいなw

今日はここまで！

トランプゲーム大全

トランプゲーム大全

夢中になる!トランプの本―ゲーム・マジック・占い (主婦の友ベストBOOKS)

夢中になる!トランプの本―ゲーム・マジック・占い (主婦の友ベストBOOKS)

Wizard Card Game

Wizard Card Game

Wizard

Wizard

  • Sean O'Connor
  • ゲーム
  • ¥480

トリックテイキングゲームのイロハを語ってみた。（その1）

ゲーム

ツイッターでエゴサしてたら、揚子江さんの次のツイートが目に入った：

この記事を書いたのも、もう3年近く前になるのだけど、けっこう読まれているみたいで嬉しい。

で、この「嫌いなゲームや苦手なゲームは攻略法を調べると面白いかもしれない」というツイートを見て、ハッとした。
そう、嫌いなゲームや苦手なゲームって、なんでそれが嫌いだったり苦手だったりするのかというと、どうプレイしたらいいのか分からない、どこが面白い要素なのか分からない、どうやれば勝てるのか分からないということが多いんじゃないかな、と。
（まぁ、最初に遊んだときにボコられたり、自分の好きなようにプレイしたら怒られたりして嫌いになる、という「人」が原因のケースもけっこうありそうだけど・・・

そして、「苦手だ」と明言する人が多いように感じるゲームの一つが、トリックテイキングゲーム。
通称、「トリテ」。

f:id:yamaimo0625:20180107143606j:plain

好きな人は好きだけど、嫌いな人はとことん嫌いというか。

曰く、

  • そもそも、専門用語がよく分からない
  • 専門用語があって、初心者おことわりみたいな雰囲気が嫌
  • どのカードを出したらいいのか分からない
  • カウンティングしないとダメとか無理無理
  • 変なプレイをしてゲームを壊しそう・・・
  • なんでフォローしないとダメなの？
  • テーマもないし、地味
  • トランプ（笑）

いや、言いたいことはすっごいよく分かる。
自分もトリテ嫌いだったから。

けど、トリテ好きになった今となっては、もし上記のような理由でトリテを嫌っているのだとしたら、ちょっともったいないかな、と。
「分かってくれば」、すごく手軽に遊べるとても面白いゲームなのに。

もちろん、この「分かってくれば」の壁が大きいのだけど。

ということで、その最初のつまずきを取り除いていければと思う。

そもそも、トリックテイキングゲームって何？

おそらく、トリックテイキングゲームをまったく知らない人がこの記事を読むことはないと思うのだけど、一応、念のため。

トリックテイキングゲームは、カードゲームのジャンルの一つ。

基本的な流れは、以下の通り：

各自に何枚かの手札が配られ、順番に手札からカードを1枚ずつ表向きで出していく。
全員が1枚ずつ出し終えたら、出されたカードで強さ比べを行って、一番強いカードを出していた人が、その強さ比べでの勝者となる。
これを何度か繰り返し、ゲームごとに決められた方法で、最終的なゲームの勝者（あるいは敗者）を決定する。

これでなんで「トリックテイキングゲーム」という呼ばれ方になるかというと、上記の強さ比べのことを「トリック」と言い、それの勝者になることを「トリックを取る」と言うから。
トリックを取る（テイクする）ゲームなので、トリックテイキングゲーム。

トリックテイキングゲームの「イメージ」

さて、そんなトリックテイキングゲーム、テーマもヘッタクレもない感じだけど、それだと無味乾燥すぎて取っつきにくいので、ここではまず、トリックテイキングゲームの「イメージ」について話してみたい。

イメージして欲しいのは、争い合ういくつかの大国。
プレイヤーは、その大国の支配者。
支配者の元には当然何人もの家来がいて、それらがつまり手札。
その家来たちを使って他国と勝負を行い、自分の国を勝利へと導こう、というのが、ゲームの基本的な目的。

まぁ、手札を出し合って勝負を行い、相手を打ち負かすというゲームなので、シャドバやDXMと同じく、ある種のTCGと言うことが出来るかもしれない。

イメージしろ！
※イメージしろとは (イメージシロとは) [単語記事] - ニコニコ大百科

そして、争いといっても、そこにはいろいろな種類がある。
軍事による武力の争いだったり、宗教による影響力の争いだったり、商業による経済的な争いだったり、農業による生産力の争いだったり。
これらを表しているのが、各カードのマーク（スート）。
スペードは「軍事」、ハートは「宗教」、ダイヤは「商業」、クラブは「農業」を表していると考えるといい。
（※一説では、スペードは剣、ハートは聖杯、ダイヤは貨幣、クラブは棍棒を意味していると言われてる）

また、家来にも当然、優秀な家来からダメな家来までいるわけで、それを表しているのが、各カードの数字（ランク）。
当然、ランクの高い家来ほど強く、ランクの低い家来は弱い。

さて、ある国が何かしらの家来で争いを仕掛けてきた。
それに対して、他の国も同様に家来を出し、その優秀さで勝負を行うことになる。

ここで重要なのが、最初に出てきた家来と別ジャンルの家来を出しても、勝負にならないということ。
例えば、軍事の争いに宗教家が出てきても意味ないし、逆もまた同様。
これが「フォローできなければ（基本的には）負け」というルールを意味している。

さらに、出せる家来がいるのに出さないのは、たとえそれで勝てないとしても、「卑怯」ということになる。
これが「マストフォロー」というマーク縛りのルールになってくる。

そんな感じで、お互いの家来を正々堂々と戦い合わせ、そして自国を勝利へと導くゲームと考えると、いろいろなルールがとてもスッキリと腑に落ちると思う。

ところで、軍事、宗教、商業、農業と、4つの争点を示したわけだけど、このどれもが常に対等とは限らない。
例えば、軍事を使えば他の争いであってもそれを無視して勝利できるかもしれない。
叩き切ってしまえばいいわけだから。
そんなふうに、他の争いよりも強い争いというのが、「切り札」ということになる。
もちろん、「正々堂々と」戦わないといけないので、出せる家来がいるのならその家来を出すしかないのだけど。

さらには、このテーマだけ聞くと、強い家来（＝強い手札）を持ってるかどうかで勝負が決まってしまうように思えるかも。

実際、どれくらいトリックに勝てるかは手札による部分がけっこう大きいので、そのバラツキを減らすために、何回も行ってその結果で勝負を決めたりする。

あるいは、もっとシステマチックに「ビッド」を行うことでこの問題を解決しようとしているゲームもあったり。

例えば、各自が自分の手札を見て何回トリックをとれるかを宣言し、一番多い回数を宣言した人が「攻め」、それ以外の人は「受け」に回るという「攻防戦」の仕組みが入ったトリテがあったりする。
この場合、攻撃側は宣言した回数以上トリックをとれれば勝ちで、逆に、防御側は宣言された回数以上トリックをとられなければ勝ちになる。

他にも、自分の手札で何回トリックをとれるかを各自が宣言し、宣言通りにとれれば勝利ポイントをもらえ、そうでなければ勝利ポイントを失う、というトリテもあったりする。
この場合、大国の支配者であると同時に、実は裏社会のボスでもあり、裏で自分の国がどれだけ勝てるかをギャンブルしていて、そっちの方が重要である、というような 妄想 イメージをするといいと思う。

・・・厨二病じゃないよ？

専門用語・・・

次に、トリテの専門用語について。

これに関しては、以前にも書いたり。

ただ、結論から言えば、覚えてしまった方がいいと思う。
なぜかというと、まず、そもそもそんなに数があるわけでもないし、覚えてしまった方がいろいろ便利だから。

もちろん、何も知らない初心者に対して専門用語を使うのは間違ってると思うけど。

まず、カードに関して。
数字（A, 2, ... , 10, J, Q, K）は「ランク」、マークは「スート」と呼ぶことが多い。
これは単に英語でそう言うから。
それと、他より強いスートのことを「切り札」もしくは「トランプ」と言ったりする。
（※「トランプ」というのは本来「切り札」という意味）

あと、カードを出すことを「プレイ」すると言ったりする。
これは、将棋を「指す」、囲碁を「打つ」と同じで、そういうもんだと割り切った方がいい。

割り切った方がいいという意味では、「トリック」も同じ。
カードを出し合ってする強さ比べを「トリック」と言うわけだけど、なんで「トリック」なの？と言われると、答えられない。
それを不満に思う声も多いと思うんだけど、よくよく考えると、例えば将棋や囲碁で「対局」というのかと分からないし（「局」ってなに？）、麻雀の「場」（東場とか一本場とか）というのもよく分からない。
だから、「そう呼ぶもんなんだ」と割り切ってしまった方が、スッキリする。

「トリック」よりはスッキリすると思う同様の言葉としては「ディール」がある。
これは、各自に手札を配り、トリックを複数回行って手札を使い切るまでのこと。
普通は手札による偏りを均すために、複数ディール行って勝負を決めることになる。

あとは、「リード」と「フォロー」、それに伴って、「マストフォロー」「メイフォロー」「マストノットフォロー」といったところ。
これは英語で書けば簡単で、"lead"と"follow"、つまり、「導く」と「従う」ということ。
一番最初にプレイするから「リード」する（＝導く）となり、そのあとにプレイするから「フォロー」する（＝従う）となる。
先程のイメージで言えば、導くというのは、どの分野で競うかを決めるということになり、従うというのは、つまり、決められた分野での勝負にのるということになる。
そして、必ずフォローしないとダメなのが「マストフォロー」（"must follow"）、フォローしなくてもいいのが「メイフォロー」（"may follow"）、逆に、フォローしちゃいけないというゲームもあって、それは「マストノットフォロー」（"must not follow"）と呼ばれたりする。

あとは、リードするプレイヤーを「リードプレイヤー」や「リーダー」、フォローするプレイヤーを「フォロワー」と言ったりするくらい。

それと、自分のとるトリック数とかを宣言する「ビッド」とか。

上で挙げた用語を改めてリストアップしてみれば、

  • ランク
  • スート
  • 切り札（トランプ）
  • プレイ
  • トリック
  • ディール
  • リード
  • フォロー
  • ビッド

と、こんなもん。
そんなに多くないでしょ？

あとは、「ラフ」とか「ボイド」とか、慣例的に使われてる表現がいくつかあるけど、あまり気にしなくていいと思う。

（余談だけど、「ラフ」の綴りって、"Ruff"なのか・・・ Ruff (cards) - Wikipedia）

長くなったので、プレイングに関しては、また明日。

今日はここまで！

トランプゲーム大全

トランプゲーム大全

夢中になる!トランプの本―ゲーム・マジック・占い (主婦の友ベストBOOKS)

夢中になる!トランプの本―ゲーム・マジック・占い (主婦の友ベストBOOKS)

『現れる存在』を読んでみた。

読書 哲学

『現れる存在』を読んで、これが非常に面白い本だったので、紹介したい。

現れる存在―脳と身体と世界の再統合

現れる存在―脳と身体と世界の再統合

ちなみに、どんな本なのかをすごく簡単に言うと、知能とは脳の中に閉じているものではなくて、身体、さらには環境にもにじみ出て、それらの相互作用による創発によって生み出されているのではないか、ということを、様々な事例に基づいて主張している本。
哲学的であるのだけど、それ以上に非常に科学的。
そして、取り上げている事例を読むだけでもすごく面白い。

きっかけ

そもそも、なんでこの本を読もうと思ったのかというと、『人工知能のための哲学塾』の参加者で読書会を企画した方がいて、その準備会みたいな集まりにこそっと参加させてもらったのだけど（ちなみに、読書会自体には自分は参加できなかった・・・）、その場で『人工知能のための哲学塾』のアドバイザー的な立場だった大山さんがこの本を薦めていたから。

そのときはとりあえずメモっておいて、hontoでクーポンが出たら買おうと思っていたのだけど、いつまで経っても紙の本のクーポンが出ず、同じように待っていた飲茶さんの『飲茶の「最強！」のニーチェ』を買うときに、一緒に購入した。

届いてまず、その分厚さにびっくり。
こんなにしっかりした本だったのか・・・
（※脚注や参考文献、付録諸々を入れて400ページ強）
が、開いてパラパラとめくってみれば、これが読んでて非常に気持ちのいい文体。
翻訳がいいからなのか、分厚さのわりにだいぶスラスラと読めた。
（ただし、6章〜8章を除く。特に8章は読むに耐えない・・・）

どうして人工知能は「アホ」なのか

イントロダクションでまず語られるのがこれで、痛快すぎるw

われわれが作り出した最高の『知的』人工物は、なぜいまだに、言いようもなく手の施しようもないアホなのか。
一つの可能性は、われわれが知能そのものの本質をまったく誤解しているということだ。
われわれは心というものを、ある種の論理的推論装置が、明示的に蓄えられたデータと結びついたものも考えていた（略）。
（省略）
われわれが無視している事実とは、生物の心が何よりもまず、生物の身体をコントロールするための組織だということだ。
（省略）
心は決して身体を伴わない論理的推論装置ではないのだ。
（『現れる存在』より引用）

つまり、知能というとどうしてもパソコン的なものを思い浮かべてしまって、膨大なデータと、そのデータを処理する仕組みこそ知能なのだと思い込んでしまうけど、そんなんだから人工知能はどうしようもなくアホなんだよ、と。

確かに、知能のあり方をパソコン的なものとして捉えていれば、どうしたって出来上がるものはパソコン程度のものにしかならない。
そうじゃなくて、心が身体をコントロールするための組織として発達してきたという事実に目を向けなければ、生物の賢さというものは見えてこない、と。

そのあとは、CYCというとんでもないプロジェクト（二人世紀かけて知識データをコンピュータに入力する）を紹介し、それがゴキブリのもつある種の賢さにも劣ることを示している。
ゴキブリさん、ぱねぇ・・・

包摂アーキテクチャ、モデルをもたない心、環世界・・・

そこから本では、このブログでも何度か名前が出てきたブルックスと包摂アーキテクチャ（サブサンプション・アーキテクチャ）を紹介し、そのアーキテクチャを用いた様々なロボット、それに、モデルをもたない心（表象なき知性）、さらにはユクスキュルの環世界の紹介を行なっている。
このあたりは、『人工知能のための哲学塾』を読んでいれば、馴染み深いと思う。
そして、具体的なロボットの紹介もされているので、そこだけでも十分面白いと思う。

青写真なき発達

そのあと紹介されていて面白かったのが、乳幼児の歩行に関する話。

まず、新生児を持ち上げて床から離すと、よく調和のとれた足踏み運動が見られるらしい。
しかし、2ヶ月ほどすると、この足踏み運動は行われなくなる。
このあと、8ヶ月から10ヶ月になると再び足踏み運動が見られるようになり、およそ12ヶ月で自律的な歩行が見られるようになるらしい。

この2ヶ月から8ヶ月にかけて、足踏み運動が行われなくなる理由、普通だとちょっと分からない。
素直に考えると、2ヶ月頃には、なにか無意味な足踏みを抑止するような脳の成長があったりするのかな、と思ってしまう。

が、この理由は、もっと別のところにあったとのこと。
その答えは、「脚の重さ」w

どうやら、脚が成長していくことで、2ヶ月経った頃に、直立姿勢のときの脚の重さが、脚の筋肉が持ち上げられる重さを超えてしまうらしいw
なので、足踏み運動が行われなくなる。
そして、8ヶ月経った頃、今度は脚の筋肉が十分に発達してきて、結果、再び足踏み運動が見られるようになる、と。
実際、3ヶ月経って足踏み運動をしなくなった乳幼児を、実質的に脚が軽くなる水中に直立させると、再び足踏み運動を始めるらしいw

この事実の意味するところは、幼児の発達を理解するときに、複数の要因の相互作用を考えなければならない、ということ。
この例の場合、脳や遺伝子といった、中央集権的なものが原因だったのではなく、「脚の筋力」と「脚の重さ」という2つのパラメータの関係が、足踏み運動の振る舞いの原因になっていた。
つまり、脳や遺伝子になにか壮大な青写真があって、それにしたがって発達していたわけではないんだ、ということが分かる。

で、そのあともいろいろ面白い話が続くんだけど、まとめるの、諦めた（＾＾；
どれもこれもが興味深い話で、書き始めるとキリがない・・・
ということで、自分のTwitterでの呟きをピックアップ。
あとで余力があればまとめ直すかも。

007原理

「007原理」というのは、次のようなもの：

一般に、進化した生物は、環境の構造や環境に対する操作を、関連する情報処理操作の代用物としてうまく利用できる場合、あえて損失の大きなやりかたで情報を蓄積したり処理したりはしない。
すなわち、仕事を済ますのに必要なことだけを知るべきなのである。
（『現れる存在』より引用）

「オッカムの剃刀」の生物版というか、何かすでに使えるものがあるのなら、それを使うことでコストを下げるようにする、という原理。

外的な足場作り

環境との相互作用による創発を考えていくと、人間が賢くなってきたというよりかは、人間がまわりの環境を賢く作り変えてきたんじゃないか、という話。
この発想は非常に面白い。

言葉がもつ力

そして、言葉もそうやって人間に作られた「道具」の一つだ、という話。
コミュニケーションに使われるだけでなくて、言語自体が人間を賢くする力を持っている。

他、面白かった内容として、創発とはどういうことなのかの説明とかがあった。

それに関連して、今、制御理論に興味があったりする。

これまでの人工知能の理論は、基本的に2つの軸があって、統計学によるもの（ベイズ推論とか）と、最適化数学によるもの（ニューラルネットワークやSVM）とに分けられる。
ただ、創発といった相互作用を考えていくとすれば、そこで出てくるのは力学的な微分方程式で、それを解いていくための強力な武器になるのが、制御理論となってくる。

制御理論については、また別の機会に。

今日はここまで！

現れる存在―脳と身体と世界の再統合

現れる存在―脳と身体と世界の再統合