このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

フローチャートからマゾ・テストまで

http://twitter.com/ckuwata/status/4939817655 :

檜山さんとのミーティングは半分〜 1/4ぐらいは計算機科学の講義なのだが、今日は圏論とデータフローダイアグラムと「真のフローチャート」と「真の goto」についてだった。関連する論文を見つけたので読んでるが、 160p 近い英語論文で早くも泣きが入りつつある。

Kuwataさんが謎のような言葉をつぶやいているのだけど …… フローチャートとgotoについては、「イヂメられて石投げられるから人に話しちゃダメだよ」と言っておいたんだけどなぁ。まーいいや、この機会に述べておこう。おおっと、石投げるのはちょっと待ってよね。

内容:

「高次元のパイピング」に、このエントリーより短く、過去のフローチャート研究のおよその経緯が書いてあります。

口にしただけで忌み嫌われる

学習や教育の早い段階で刷り込まれた常識というのはホントに強烈で、一切の思考なしで肯定(受容)や否定(拒絶)の態度を取らせます。「フローチャートとgoto文」という言葉だけで、多くのプログラマに刷り込まれた判断機構=思考停止装置が発動して「それはダメなもの」「それは悪いもの」と反応するでしょう。

もちろん、「フローチャートとgoto文」スタイルのプログラムに弊害があるのは事実です。僕が取り上げたいのは、弊害を引き起こす要因を注意深く取り除いた、整合的かつ構造的で高度にモジュラーな「フローチャートとgoto文」なんですよね。なのに、言葉だけで拒絶的反応されるのは愉快じゃないので、まー、あんまり積極的に語ることはしなかったのです -- 「イヂメられて石投げられるから人に話しちゃダメだよ」

フローチャート研究の歴史(断片)

フローチャートが完全に日陰の存在だったかというと、そうでもなくて、アービブ&マナ、ロビン・ミルナー、ダナ・スコットのような計算科学の大家達もフローチャート研究に手を出しています*1

  • M.A. Arbib and E.G.Manes. Partially additive categories and flow diagram semantics. Journal of Algebra 62:203-227, 1980.
  • R. Milner. Flowgraphs and flow algebra. Journal of the Association for Computing Machinery, 26:794-818, 1979
  • D. Scott. The lattice of flow diagrams. In Proceedings of the Symposium on Semantics of Algorithmic Languages, pages 311-366, LNMath. 188., Springer-Verlag, 1971

フローチャートの研究を精力的・徹底的に行った人が、ルーマニアのステファネスク*2Gheorghe Stefanescu)です。「プログラムの算術的計算法 (続き&完結)」の最後「計算法と図解法」に、ステファネスクの名前が出ていたりもします。ちなみに、ステファネスクさんは、九州大学客員教授でいたことがあるそうです。

  • Gh. Stefanescu. On Flowchart theories I: The determinisitc case. Journal of Computer and System Sciences, 35:163-191, 1987.
  • Gh. Stefanescu. On Flowchart theories II: The nondeterministic case. Theoretical Computer Science, 52:307-340, 1987.
  • Gh. Stefanescu. An algebraic theory of Flowchart schemes. In Proceedings CAAP'86, pages 60-73, LNCS 214, Springer-Verlag, 1986.
  • Gh. Stefanescu. Feedback theories (a calculus for isomorphism classes of flowchart schemes). Revue Roumaine de Mathematiques Pures et Applique, 35:73-79, 1990.
    Early distributed as: Preprint Series in Mathematics, The National Institute for Scientific and Technical Creation, Bucharest, No. 24/April 1986.

カザネスク(Virgil Emil Cazanescu)との共著では:

  • V.B. Cazanescu and Gh. Stefanescu. A formal representation of Flowchart schemes I. Analele Universitatii Bucuresti, Matematica - Informatica, 37:33-51, 1988.
  • V.B. Cazanescu and Gh. Stefanescu. A formal representation of Flowchart schemes II. Studii si Cercetari Metematice, 41:151-167, 1989.
  • V.E. Cazanescu and Gh. Stefanescu. Feedback, iteration and repetition. Preprint 42, The National Institute for Scientic and Technical Creation, Bucharest, 1988.
  • V.E. Cazanescu and Gh. Stefanescu. Bi-Flow-Calculus. Unpublished manuscript, 1988.

1986, 87, 88年に集中して仕事してますね。これらの論文の一部は、http://www.comp.nus.edu.sg/~gheorghe/papers/ から、PDFまたはPS形式で公開されています。

1988年の"Feedback, iteration and repetition" は、1994か1995くらいに別な出版社(たぶん World Scientific)から出版され、一時はWebにもあったのですが、先ほど検索したら見つかりませんでした。この論文は、あまり注目されなかったようですが、色々なルーピング・オペレータの相互関係が書いてあって、後に長谷川真人さんの学位論文 "Models of Sharing Graphs: A Categorical Semantics of let and letrec (1997)"*3 で示された結果も示唆されています。

ステファネスク、カザネスク以外にも、エルゴット(Calvin C. Elgot)、ブルーム(Stephen L. Bloom)、エジック(Zoltan Esik)、ライト(J.B. Wright)あたりがフローチャートと繰り返し制御の研究をしています。なかでもエルゴットは先駆的で、70年代に次のようなトピックを扱っています。

  • C.C Elgot. Monadic computation and iterative algebraic theories. In Proceedings Logic Colloquium'73, pages 175-230, North-Holland, 1975. Studies in Logic and the Foundations of Mathematics Volume 80.
  • C.C. Elgot. Some geometrical categories associated with Flowchart schemes. In Proceedings FCT'77, pages 256-259, Springer-Verlag LNCS, 1977.

僕は、紙出版物にはどうにもアクセスしようがないのですが、"Some geometrical categories associated with Flowchart schemes" は、タイトルから妄想するに、1996年の A. Joyal, R. Street, D. Verity の "Traced monoidal categories" に似たアイディアが含まれていたのかもしれません(実際のところ分からんけど)。

フローノミアルとネットワーク

フローチャート(flowchart)以外に、フローダイアグラム(flow diagram)、フローグラフ(flowgraph)なんて言葉もあります。ステファネスクは、90年代になるとフローノミアル(flownomial)という変わった言葉を使い始めました。たぶん、フローチャートが代数的計算の対象となることを強調するために、多項式(polynomial)などと同じ語尾 -nomialを付けたのでしょう。強いて訳すなら「フロー式」「流れ式」とか。

PDF文書 ALGEBRA OF FLOWNOMIALS (1994) は、Webから手に入る一番まとまった資料です(Kuwataさんが見つけたのはコレですね)。

ステファネスクは2000年に、より包括的な解説本をSpringerから出版しました。そのタイトルは Network Algebra「フローノミアル」もやめて、バーグストラ(Jan A. Bergstra)の勧めで「ネットワーク」を使い出したのです。「フローチャート」という言葉に染み付いてしまった悪い印象を避けたかったのでしょうか? しかし、たいていの人は「ネットワーク」と聞いてLANやインターネットを連想するでしょうから、あんまり良い用語だとは思えません。
[追記 date="翌日"]定義(らしきもの)を確認すると、フローノミアルはフローチャートより形式的な概念を意味し、ネットワークはフローノミアルを含むより一般的な構造を指すようです。つまり、フローチャート → フローノミアル → ネットワーク の順で抽象度と一般性が増していくということらしいですね。[/追記]

残念ながら、Network Algebra は現在入手困難です。しかし、ALGEBRA OF FLOWNOMIALS や、関連する論文をたぐれば、ステファネスク達の成果や主張を読み取ることはできます。

gotoと圏論的なオペレータ

呼び名はともかくとして、プログラムはフローチャート(絵図)で表現でき、繰り返しはgoto文で表現できます。ただし、ここで話題にするgotoは、自由奔放で悪さをしでかすものではなく、とてもいい子です。どの辺がいい子かというと:

  1. 飛び先が制約されている。
  2. 制御と共にデータも持ち運ぶ。
  3. 型の整合性をきびしく検査される。

gotoの定式化となる圏論的オペレータは、トレース、フィードバック、コンウェイ(Conway)不動点、エルゴット(Elgot)繰り返し、クリーネ(Kleene)スターなどと呼ばれます。それぞれ少しずつ違うものですが、長谷川の定理*4により、(余)デカルト圏では、どれを使っても同等であることが保証されます。

Catyで使う状況では、余デカルト圏のトレース・オペレータか、またはエルゴット繰り返しオペレータ(コンウェイ不動点オペレータの双対)の形でしょう。

僕の動機と根拠

フローチャートとgoto文にも、しっかりとしたモデルや理論があるらしいと感じていただけたでしょうか。しかしそれにしても、マイナーな理屈であるのは確かです。なんでまたワザワザ? それは僕には必要性があるからです。Catyのテストスクリプトを書きたいのですよね -- それに対する適切なモデルは? と考えると、ネットワーク代数(フローノミアル代数)しかないでしょ、という感じ。

Catyのシステム自体やコマンド、そしてCaty上のWebサイトを徹底的にテストしたいのです。外部のテストツールを使う方法もありますが(そして、それも実際使いますが)、自分で自分をテストできるようにしたい。Caty/PythonPythonで書かれているので、テストコードもPythonで書くのは自然です。が、Catyは実装言語中立を標榜しているので、実装言語が変わっても同じテストデータ/テストシナリオを使い回したい要求があります。他にもいくつかの理由から、Catyスクリプトをテストスクリプト記述にも流用しよう、と考えました。

現状のCatyスクリプトは、意図的に機能を抑えているので、テストスクリプトを書くにはちょっと弱い。弱いとは言っても、ほんのチョットでも機能を足すとチューリング完全になってしまう境界線付近にいますから、ごくわずかな機能追加で万能になってしまいます。その「わずかな機能追加」をどんな形にしようか。そこでgotoが登場するのですよ。

他にも、goto(フィードバック・オペレータとか言うほうが誤解や反発が少ないですけどね)採用の動機と根拠はありますが、書くのが面倒なので今日は省略します。

マゾ・テスト

自分で自分をテストすることには、他にも面白い側面があります。外部ツール(手作業でもいいけど)では困難な「通常は触れないシステム内部の深い部分にも、手を出していじめ抜く」ことができます。

これはどういう事かと言うと: 自分自身のお腹に、渾身の正拳突きを決めるようなものです。他人が突いてきたら反射的に防御するので、正拳を決めることは不可能なのです。自分で自分を突き抜くことにより、尋常ならざるダメージを与えることができるでしょう。ドMな構造。

さて、正拳突きを決めるには、下を向いて腕を曲げたりしちゃダメです。あくまでも、正面の目標に向かって突くのです。つまり、自分の目の前に自分のお腹が見えている状況を作らなくちゃなりません。別な言い方をすると、システム内部(インタプリタ)から、当該システムを対象化できるということです。リフレクティブとかメタ巡回的とか呼ばれる構造ですね。スノーグローブ構造と言ってもいいかもしれません。

Catyの内部を流れるデータは、表層部から中核部まですべてJSONデータです*5JSONベースのデータ型は、帰納的定義を持つので、スカラーからはじめる帰納ステップにより列挙可能です。つまり、ブルートフォーステスト用データは容易に自動生成できます*6。こういうデータを三日三晩、自分自身に向けて打ち込み続ける、と。そんな苦行に耐え切れたなら、「俺って丈夫」って言ってもいいのじゃないかと思います*7。マゾっぽいけど。

構文の問題とかナニヤラ

リフレクティブで無防備な状態の核インタプリタ上でスクリプトを動かす、その状況のモデルは割とハッキリと想定できるのですが、具体的な構文となると、これはまた悩みの種。

素朴にラベルとgoto(フィードバックオペレータ)でもいいのですが、いくつかの問題があります。もう少し高級な構文コンストラクトの候補もいくつかありますが、一長一短。キーワード追加となると、その綴りでまた考え込みます。ウガ。

モデルももうちょい正確に記述しないと安心できないし、で、考え込む日々は続く。

*1:文献リストは、ALGEBRA OF FLOWNOMIALS の Bibliography からの引用です。

*2:いつものように、人名の正確な発音が分からないのですが、それでもカタカナ書き。

*3:1999年に書籍の形で出版されているようです。似た話題を扱っている論文として、Recursion from Cyclic Sharing: Traced Monoidal Categories and Models of Cyclic Lambda Calculi (1997)

*4:歴史的経緯を踏まえれば、カザネスク/ステファネスク/ハイランド/長谷川の定理とでも呼ぶべきでしょう。

*5:別途、外部から入るデータが、確実に妥当なJSONデータにトランスレートされることを保証する必要があります。

*6:テストデータとしての品質は保証できないけど。

*7:現状のCatyは全然丈夫じゃないです。まだまだ脆弱。