神戸大学理学部数学科のペ−ジへ.
児玉のホ−ムペ−ジへ.

数学プログラミング入門

神戸大でこんなような集中講義を行った. (神戸大集中講義 計算数学B 2000/07/24-28) かなり偏った内容だけど, これだけで完結っていうよりは, 興味を持ったら自分で勉強してもらうつもりで概論的にやってみた. 時間が足りなくて, 始めに思っていたのとはちょっと内容が変わっちゃった. 後半は代数の知識とかも必要なので読むのはたいへんかも. 最後の方は濃くなりすぎて説明不足. あんまり入門編にはならなかったなぁ.

中で使っている主なプログラミング言語は C, ruby, Modula2. あと, 何の言語ともつかないような抽象的な (っていうか 嘘 ruby もどきの)アルゴリズム記述もある.

講義のメモと 横山氏提供のノ−トから再現したけど, 口調の不一致, 抜け落ち等が見られる. まだ HTML になり切っていない部分がある. 許してね.

参考用のコ−ド類は 講義基本例題. Xサンプル. ruby数式処理. sather数式処理. 結び目.

講義の目的

主目的

一般的な C 言語の入門講座はすでに履修していることを仮定する. 数学者むけプログラミング入門っていうことだが, Mathematica などの使い方講座じゃなくて, こういうソフトを作成出来るようになるのが目的. そういうわけで, 数学用ツ−ルの使い方ではなく, 汎用プログラミング言語や汎用ツ−ルで数学用のツ−ルを 実装するうえでのプログラミングの要所を見て行く. 数学的構造をアルゴリズム化してプログラムで実現する手順を追ってみる.

入門編の後は、高山先生のところへどうぞ.

概要

1. 公開用のライセンス.
2. 開発ツ−ルに何を用いるか.
3. グラフィックスの扱い.
4. X のプログラミングモデルと舞台裏.
5. デ−タ−表現の観点から見たオブジェクト指向プログラミング
6. 繰り返し構造.
7. ル−プの再構成.
8. 探索コ−ド.
9. 結び目理論の例から, 結び目の扱い.
10. 組み込み用 小言語の例, コンパイラ/インタプリタ系.

公開用のライセンスの問題.

みんなに使ってもらうことを考えよう. まずできた成果をどうやって他の人に使ってもらうか, それから, プログラミングのノウハウも自分だけで抱えるんじゃなくて 他の人の参考になるとか再利用できるとかを考慮しよう.

開発ツールになにを用いるか

前に設計された言語の欠点を補う意味で新しい言語は開発されている. C 言語には素のままでは, 数学プログラミングに向かないさまざまな欠点がある. システムプログラミングにはよいけど, 実験的な数学プログラムを安全に作るには向かない. C や C++ 以外の言語も考慮してみよう.

新しい言語を勉強するのは, C 言語でプログラムの原則を理解していれば, それほど難しいことじゃない. 逆に, C言語が気になっても, 他のもっと学びやすい言語で基本を押えておけば, C言語に移行するのもそんなにたいへんではない. 扱いやすいスクリプト言語と呼ばれる簡易言語(インタプリタ)を理解しているとよい. 例えば Ruby とかは適当と思う.

グラフィックの扱い

X の画面でなにか表示を行う, 例えば, 拡散項付の微分方程式の解を時間をずらして見たい場合, 画面にどのように見せるかを考えてみる. X のプログラミングやツールキットが必要になる. gtk とか OpenGL(mesa) を使うと楽だけど, 基本的な事はどのツ−ルキットを使っても大差はない. どのような気分で作れば, 画面の出力が成功するか見てみる.

X のプログラミングモデルと舞台裏

どういう設計が行われ, どのように実現されているかちょっとだけ覗いてみる. 内部の構造まで知っていると, 表面の部分を扱うだけの場合でも有益.

デ−タ−表現の観点から見たオブジェクト指向プログラミング

繰り返し構造. ル−プの再構成.

探索コ−ド

結び目理論の例から. 結び目の扱い.

組み込み用 小言語の例. コンパイラ/インタプリタ系

ライセンス

作成したソフトウエァの公開の問題点. 誰のものか？

ソフトウェアを公開する側から云うと, 自分がプログラムを書いて, 皆に使っていいよって言ったとする。 もらった人が勝手にソースを改造して、自分版として公開したり、論文書いたり、 売ったりしてよいか。

好意で "どうにでも使ってくれ" という意味で ライセンスを書かないで出す人もいるけど, 使う側からすると,これはかえって使いにくい. この点もちゃんと考えておいて, 公開ライセンスに明示しておく必要がある.

つまり, 作ったプログラムを人に使ってもらう場合、ライセンスをきちんと宣言したほうが 使うほうもはっきりして幸せ, ということ.

逆に, 自作のプログラムでも, どこまで自分の権利が及ぶか気を使わねばならない事もある.

私立の大学でよい計算プログラムができたとする, これを公開して良いか？ 大学のプロジェクトでできたものは大学の財産という考え方がある. 公立の学校の場合は、アメリカの場合は、公共に還元すべきだという考え方で 無料で公開される場合が多い. 日本だと、国有財産だと解釈すると, 公開の条件が厄介になる可能性がある. 例えば, 講義ノ−トを無料で公開すると, 受講料を支払って受講する人と無料でアクセスする人との不公平ができる. この点は考慮しておく必要があるかも.

一般企業に就職した後で、勝手にフリーソフトを作るとまずい. 作る前に、雇用者との関係で、権利の放棄をしてもらうとよい. 当然就業時間に作業をしてはいけない. GPL (GNU Public License) の文面内にこの点を論じた部分がある. 最近だとオ−プンソ−ス関係への理解も得られるかもしれない.

ソフトウェアによって作成した研究用デ−タ−は？

数学的なデ−タ−を自然物とみなした場合, デ−タ自体ではなくその独自の編集に著作権が生じると思われる. 人が作ったプログラムで計算をしてデータを得てそれを論文で使いたい場合, この意味では,通常,デ−タ−の作成者に権利があると解釈できる. 面白いアルゴリズムを自分が考え出して、誰かがそれを使ってデータを 生成したとしても、そのデータに対する権利は自分にはないという事になるのかも.

電話帳のデータは、おそらく NTT が著作権を持っているはず。 それを NTT がやっているより便利に使いやすいように編集を行った場合、 その独自の編集に権利が与えられると考えられる。

オ−プンソ−ス/フリ−ライセンスの概念.

商用でなくてもすむものは、お互い気分良く使えるように配付しよう。

数学プログラムで、内部でどのような処理をしているのか見せたくない場合、 他の人がそれを使って計算結果に疑問がわいた場合、その他の人が調べるすべが ないのは問題。

またせっかくよいアルゴリズムを使っているのに、他の人が勉強できない. 配付の仕方は、 ソースがあれば、ちょっと改造して似たような処理につかえるはず。 そのような勉強の機会を奪わないようにする。 知識やノウハウを利用しやすいようにしたほうがよい。

1. 再配布の自由.

作者からの配付、だけでなく, 配布,販売,譲渡を制限しない. 販売を制限しないとは？ 回り回って、自分のプログラムが雑誌などに収録されてしまうとか。 回り回って商品化されてもよいことにしようよ, ってこと. どこまで流通するかは、作者にはコントロールできない。 使ってみて便利だったから他の人にも渡したいのに制限があると渡せない。

ロイヤリティ, 報酬を要求しない. 販売は制限しないのに... どういうこと？ 使うときにビールおごってね、などはかまわない。 回り回って、誰かが販売した場合、販売の利益に応じて作者にいくらか ロイヤリティを要求するのはダメ. 実費,手数料,寄付を求めることは良くある. FTP 公開でもサーバ使用料や維持費など. 神戸大学数学ソフト集 CD-ROM を作ってもよい。 寄せ集めをする場合、とっても手間がかかる. 何故かって云うと, ライセンスを明示しないで出している人が居た場合, ちゃんと連絡をとって許可をもらわないといけないので. 1-2人ならまあ良いけど, CD-ROM を埋めるくらいとなると, かなり厄介な問題になる. こういう CD-ROM 集とかを作る人が出るかも知れないので, 権利関係をはっきりさせておいてあげると助かる。

2. ソ−スコ−ドを含むこと.

3. 派生ソフトウェアを許可すること.

改造版を出すな、というと、元になったソフトを参考にした部分を 公開時にけずらなければならなくなる。 この場合には, 厳密にはクリーンルーム手法, スクラッチから書きましたっていうことが証明できないとだめ。 商用ソフトや、BSD の初期の頃ではこのことが問題になった。 AT&T が研究用に UNIX を作った その頃ソフトウェアを作ってそれを売ることは禁止されていた Bercley がそれを真似た BSD の中に含まれている AT&T のコードはまずいってことになった

後で制限がつけられそうな文言で公開すると不愉快な事になるかも. ソフトウェアの変更/再配布を許す. 派生したソフトウェアは元のソフトウェアと同じ条件で配布すること. GPL の自己感染的な条項を参照 お互い邪魔をせずに、親切な配付をしよう 改造して出す場合でも親切に出してね

4. 原ソ−スコ−ドと派生コ−ドの統合.

5. 個人,団体,国に対する差別をしない.

6.使用分野に対する差別をしない.

7. ライセンスの継承性.

8. 特定の製品に固有なライセンス,他のソフトウェアに対する干渉の禁止.

9. 皆さんに使ってもらいたい場合には GPL が適当

RMS の構想がすばらしかった。 Eric Steven Raymond が分析したソフトウェアの改良過程が正常に働く要件は？ どうしてフリーソフトは成功したの？ 山形さんの日本語訳(他に経済関係の翻訳もある) http://www.post1.com/home/hiyori13/jindex.html

OS,開発言語,ツ−ル

移植性, Bignum/Bigfloat, GC(garbage collection), allocate, deallocate の対応(メモリ−リ−ク) deallocate 後の使用 実行速度, 他のツ−ルとの協力

人間にとって作業しやすく,誤りを未然に防ぐのが良いプログラミング言語だ. 誤った答えを高速に求めたり, 誤ったプログラムを素早く作成しても無意味ってことだ. あまりにも遅いのも嫌なので, その辺はバランスの問題って事だが, 目的によってバランスが変わって来るはずだ.

不適切な言語で開発を進めて、苦しむ事例もある. C ができるなら問答無用で C ではじめてもよいのだが.... C の勉強に相当の時間を投資してきた、というのだとちょっともったいないけど, そうでないなら, 数学プログラミングにもっと適した言語もある.

移植性. ぼくはあんまり気にしていないので、苦情を受ける. つまり, "Linux版があるけど Windows では使えないの？" とか.

Bignum/Bigfloat. 計算の数値が何時の間にか誤っていると, いやーんって感じかもしれない。 C で無造作にプログラムを組むと 2進で 31 桁. 10^9 とか float だと 10^300 ぐらいまではいけるけど... 自分でためしてみよ。 float の場合でも, 大きな行列の計算で誤差が出て誤った結果となることがある. また,誤差の影響を避けるために特別な配慮がひつようだったりする. C でプログラムを書いていていやなのはここ！ error がでないんだけど、こっそり違う結果を出したりする。 テスト用の小さなデータでは OK なんだけど、実際の計算だと 整数で扱える範囲を越えちゃって、しかしエラーを出さないというのは最悪。 C 言語ではなにが起こるかプログラマが知っているという前提なんで エラーを出さない.

それを解消するのが Bignum/Bigfloat で 100! などが Mathematica で計算できるのは, この機能がくみこまれているから. Cの多倍長のパッケージもあるけど、 始めから組み込まれていたほうが、いらない苦労を しなくてすむ.

GC(garbage collection). 長時間の動作が必要なプログラムで メモリ− リ−クが起こると動作に失敗する. C 言語でポインタやってる？ ポインタ使うときの一番の問題は、使う前に allocate しなくちゃならない 使い終ったときに deallocate/dispose しなくちゃならない。 allocate と deallocate の問題 C でコンパイルしただけだと、メモリは使われないで allocate した段階で メモリを OS からもらって消費する. システム全体で消費するメモリが足りなくなってメモリリークが起こる。 リーク(水道管の水洩れ状態) deallocate 後の使用の問題もある. ポインタが指しているものは、すでに自分のものじゃなくなっている. GC とは、allocate したものを使い捨てにしてよい deallocate しなくても、使い終ったものを自動的に返す allocate した後で、いつ返せばよいかを C 言語の方で勝手に判断してくれる。 非常に便利。 C 言語に GC 機能を追加するライブラリを使用しても良い。 C や C++ のようなダサイ言語にはついてないけど、Java のような今風の言語には ついてる。

配列の添字範囲の異常. 動作時の添字範囲チエックを嫌がる人が多いけどなんでかな？ セキュリティ関連の問題の原因となることが多いので, 問題があることはみんな分かっていると思うけど, チエック機構を入れると遅くなるので嫌われる. "性能こそ(ほとんど)全て" って事だ. 速度競争は止めろ.

実行速度. 実行速度はどうか、走らせて一週間かかるっていうと勇気がいる 僕の経験だと、Basic ==> Modula-2 で速度が 50 倍になった :-) . 上の GC のタイミングをプログラム作者がしっかり書くと、速度は上がる。 Java や古い Lisp など、突然遅くなったりする。 意図しないときに GC が動くからね. でも, 昔よりはGC の手法もだいぶ洗練されているそうだ.

他のツ−ルとの協力 Visual hogehoge のような、マウスでカチカチやっているとプログラムが できてしまうのがあるが、単体としてはよいが、editor でプログラムを書くこと を考えるとあまり得でない。 UNIX の Emacs 上でプログラムを書くという環境は、Visual hogehoge と ほとんど同じようなことができるし、使い勝手もよい。 Emacs の使い方は覚えましょう。

演習問題 実行時間/コ−ディング時間/簡便性/メンテナンス性の トレ−ドオフについて考察せよ. 電卓的/プロトタイプ向き/実行速度重視 の各々について プログラミング環境の選択基準は？ 具体的にはどのようなプログラミング環境/言語を選択するか？

演習問題 文法的な柔軟性と記述の安定性のトレ−ドオフについて考察せよ. バグ取りの安定性(宣言,文法の硬さ) 実際の言語選択にどのように生かしたか？

演習問題 GC(garbage collection)とは何か？ どのような場面で効果的か？ (http://reality.sgi.com/boehm/gc.html)

演習問題 不正なポインタ, ガ−ベッジコレクション, 添字範囲 のオ−バ−とは何か. int a[11]; i=100; ..... a[-1]=a[10]+a[i]; また, ポインタの正当性チエック,自動ガ−ベッジコレクション, 配列の添字範囲のチエックについて 実行効率とプログラムの安全性とのトレ−ドオフについて考察せよ. ElectricFence, Checker や BoehmGC の主要機能についてまとめ C, C++ プログラミングへの有用性等について考察しろ.

演習問題 実行時チエックを プログラミング/デバッグ時だけに行うか 完成後も行うか？ 実行速度と安全性のトレ−ドオフに関して考察しろ.

開発環境

UNIX互換環境を推奨(Solaris,Linux,FreeBSD等) 僕は Linux (Plamo Linux) を使ってます。 近くに BSD を使っている頼れる人がいれば、FreeBSD もいいかも。

free ツ−ルの利用. どこで探すか

SAL Scientific Application on Linux http://sal.kachinatech.com/index.shtml

Linux Software Encyclopedia http://stommel.tamu.edu/~baum/linuxlist/linuxlist/linuxlist.html Linux で使えるソフトウェアの辞典を作ろうとしている 暇なときにどうぞ

Linux Applications and Utilities Page http://neal.nikkeibp.co.jp/linapps/ja/linapps.html 本来は英文のページ

プログラミングの前にそろえておく環境

shell環境(bash) シェルの使い方の勉強.

mule

make(gcc の -MM オプションも参照). make file の作り方、勉強した？ 複数のプログラムファイルを組み合わせて再度コンパイルするときに、 新しいものだけ選択してコンパイルしてくれる。 もし次のファイルが新しくなっていたら、次の操作をしてください。 空白の場合は C コンパイラでコンパイルしなおしてください。 このような予定表に従ってコンパイルしてくれる。 Makefile の書き方を勉強して書かなきゃいけないんだけど、それは面倒 gcc の -MM オプションで, ある程度は自動的に Makefile を作ってくれる。 man gcc の -MM を見る。 一つの長いプログラムを分割する場合、header file を作って #include file で読み込む。 Makefile はその依存関係を書くわけで、その例文を -MM オプションで 一応作れる。

gnuplot, ngraph. 数学的なプログラムをする場合に、データを可視化する、グラフを 書かせたりするのに便利.

コンパイラ達

C, C++, Fortran, Modula3, Ada, Forth, GNU Sather, Eiffel, Java. インタプリタで速度的に厳しいようならコンパイラを使うことになるかも.

C. C 言語のいやなところ、構造体の宣言が悲惨, 全ての構文を関数呼出しと同じ書式にしている. しかし、違ったものは違ったものに見えるべきだ. 1 万行から 2 万行を越えるとプロジェクト全体をまとめるのが 難しくなるのではないかと考えている。

C++. C の改良版言語として. GC が無い. 宣言が悲惨. 言語的な落し穴や、規格が変化するといういやな部分がある。 解説本が多いのもそのため。 C++ を使うならそれなりに覚悟しよう. C で指摘されていた欠陥の多くは Java, Eiffel 等の言語では解消されているが. C++ では Cとの互換性を保つためにそのままにされている. C, C++ の解説本が多いのは 知名度が高いって事もあるけど, 言語的な穽や暗い部分が多いからと思う. 松葉杖的ライブラリ(ElectricFence, Checker, BoehmGC)の使用を強く推奨する.

Fortran. いくつかの重要な計算ライブラリはある. 他の言語から fortran を使用する方法はいろいろある. ちょっとだけ知っていても損はない.

Modula2. MS-DOS 時代に僕が主に使った言語. 明確な言語仕様. わりと良い言語だと思うけどね？

Oberon. Pascal の作者 Wirth が Pascal, Modula, Modula2 の成果を踏まえて作ったオブジェクト指向言語. 開発言語だけでなく, OS, shell, 作業環境も含めて構想された. オブジェクト指向の型システムの拡張性の面を追求するような感じで定義されている. 文法はわりと明確.

Modula3 は Pascal をもう少し大規模開発向けに直したと考えておけばいい. DEC の人が作ったが, 良く分かった小人数で作られた, 居心地のよい環境やライブラリがある. Pascal や Modula2 を整理しなおしたみたいな明確な文法. 特に欠点は無いけど, 演算子のオーバーライドがないので, 数学的プログラミングには損かな?

Ada. 普通に使うなら適度な言語仕様のサイズ. 言語仕様が大きく見えるのは, 普通の言語では明示的に規定しないような マシン依存性の細部まで定義しようとした部分があるためだ. 硬くできているので安全かも、僕はつかわないけど. エイダって読む.

Eiffel. エッフェル. 宣言がわりと明解. 商用に開発するのに最良の選択かも。 言語としては成功している。 Eiffel を使ってオブジェクト指向を解説している本がある。

Sather. GNU に寄贈され GNU Sather となった(1999年). ソフトウェア工学的にはお薦めだが,まだ新しいので知名度は最低. Eiffel のよりスマ−トな改良版を目指して設計された. 文法が明解で暗い部分があまり無いので, 解説本はほとんど無いけど困らない. Iterator, closure がある。 Inheritance の 2 面 Subtyping と Code Inclusion を 個別にコントロールできる. GC,添字範囲チエック等が完備しているので, メモリリ−ク, バッファオ−バ−フロ−等の危険は無い. 配列サイズの動的な変更が可能. 実行効率もわりと良いみたい. 言語の仕様上は, 僕の理想にもっとも近い感じ.

Java. C や C++ を知っている人向けに C や C++ の弱点を解消したような言語 ポインタで失敗するのはやだな、と言う人にはいいかも。 Java の弱点もすでに指摘されている。 演算子の再定義はできない。

インタープリタ言語

Ruby, Python, perl, gawk, lisp(GNU Common Lisp), scheme(GNU Scheme), prolog 等.

Perl. でっちあげ的になんでも作るのに便利かつ強力. UNIXer の基礎知識でしょう. 僕は使わないけどね. 数学プログラミング的には目的が違う。論外。

GAWK. フィルタ−的なテキスト処理には便利. UNIXer なら知っておいて損は無いが, 数学プログラミングには論外. (でも, これで 時系列のフラクタル分析プログラムを書いた事があるんだよね.)

Ruby. (おすすめ.) 相談するのに日本語でできるので便利. この講義でも例文を ruby で書いたのが多い. 明解で簡潔な文法の Object指向インタプリタ. GC 組み込みでメモリ管理が不要(うれしい), メモリリークの心配がない. Bignum が組み込みなので, 数学プログラミングにはうれしい. C の int 相当で桁あふれがおきそうなときは自動的に Bigint にしてくれる. この辺の機構は perl や python みたいな後づけの処理系よりも良くできている. BigFloat クラスもある. perl,AWK なみに強力な文字列操作. perl の言語仕様をほとんどそのままひきうつせるように設計されている. Windows版もある. 文法が Eiffel にちょっと似ている.

Python. 構文的には while ループ、for ループの深さを indent の深さで表現する, インデントでブロックを作る文法が評価が分かれる所. すっきりしているけど嫌いっていう人は多い. オブジェクト指向の機能を後付けで拡張したので ちょっと気持の悪い部分もある. numerical Python っていうプロジェクトは進んでいるみたい. Rubyと同様の目的で使えるインタプリタ. Windows版もある.

GNU Common Lisp. Lisp を勉強するなら scheme がいい. common lisp は reduce で拡張されすぎた。

Scheme (GNU SCM). 簡潔さと柔軟性を兼ね備えている LISP. インタプリタとしては実行効率が良い. コンパイラもある. Lisp って柔軟。C と気分が違う。 アルゴリズムを勉強するための言語としてはいい。 全てがリストの世界なので, 動的プログラムも自然にできる. 静的スコ−プを持つので分かりやすい. (commonLISP は動的) 標準の SLIB や jacal で代数計算ができる.

prolog. 宣言文や、計算式が双方向に働く. つまり, c=a+b とか定義しておいて, c と b が確定すると aの値も求まる. 数値だけでなく論理的な関係でもこんな具合に 動作するのでうまく使うとものすごく柔軟なプログラムができる. わりといいところがあるが、はやらなくなってしまった。 もったいない.

smalltalk 古い言語なんだけど、今でもやる価値はある. ライブラリが充実しているし、 構文的に他の言語では実現できていないものもある。 強力かつ柔軟な object 指向言語。 かなり快適らしい。

Forth. スタックモデルを採用. この講義の一番最後のコンパイラ/インタプリタの設計で述べるけど、 スタックモデルだと 数式パーサはいらないとか、旨味は多い。 処理系はびっくりするくらいコンパクトだぞ. 僕は HP(ホ−ムペ−ジじゃないよ ヒュ−レット パッカ−ド)の スタックモデル電卓も愛用していて, スタックとか後置き式演算子にも違和感は無いけど, 普通はちょっと戸惑うかもね.

数学用に開発されたプログラム言語

Maple, Mathematica, Risa/Asir, Octave, SciLab等,

Reduce(CommonLisp), jacal(Scheme). 数学用に開発されたプログラム言語っていうか, 言語の拡張. jacal は Reduce もどきを Scheme で作成したもの. Reduce は, lisp に, rlisp っていう pascal 風にかけるような言語仕様の拡張を行って, (シンタックスシュガ−って云う.) rlisp で数式処理を記述する. だから, 見掛けは lisp とは思えないけど, reduce を使うときには, 内部では Lisp を使っている. もちろん, reduce 内で素のlisp を使うことも出来る. reduce の機能を拡張するときは Lisp と相互に言語が浸透しあっている。 Lisp の拡張ライブラリとかんがえてもいいかも。 Lisp っていうのは、対象言語レベルとメタ言語レベルをまぜこぜにしても やりやすいっていう特徴がある。

Mathematica を使うのに C が必要？ じゃ無いよね? Mathematica 自体は C(Objective-C とか)で書かれていると思うけど, Mathematica 内では独自の言語世界をつくり出している. reduce みたいに C 言語が浸透してきていることはない,

Risa/Asir. freeの数式処理系. 多項式の計算なら Mathematica よりもこれが良いでしょう. わりと高速.

GNU Octave -- a high-level language for numerical computations. http://www.che.wisc.edu/octave は MatLab のGNU版. 文法的にも互換性が高い. Windows版もある.

SciLab . MatLab 相当, ネットワ−クを通じての大規模な並列計算が可能. Free です。 たくさん使える計算機がある人はどうぞ。

演習問題. 抽象的アルゴリズムと 特定の環境での実現の違いについて考察せよ. アルゴリズムの記述に具体的な言語を使うとしたら何を選ぶか, 等.

演習問題. 自分の目的と使用環境について考察しろ. 結局どのようになったか？ その理由も明確にしろ. 数学プログラミングに必要な属性はなにか？

ツ−ルの協力,テキスト処理と結果のグラフ化

途中の経過等をテキストで出せるようにしておくと 計算結果の使い回しができる. グラフィックだけの出力はだめ.

テキストから gawk, perl, ruby, python による処理,計算結果の表示. gnuplot や ngraph で プログラム内からグラフィック表示. フラクタル分析の例(...は省略). UNIX の標準的なツ−ル, gawk,perl 等は使える方が良い. グラフィックは再利用性がない. 単純な text data で保存するほうがよい.

グラフィック

ボタン,マウスの状態をしらべる,点をうつ, マウスから点を打つ等の土台ができれば大丈夫. 点(座標)の入出力の辺りを見てみる.

X の階層. Xlib -- XToolKit/Widget set.

C言語等から使うライブラリの構成について. Xlib はXのプロトコルに近いレベルでのプログラミングを実現している. AthenaWidget, Motif 等の widget set は Xlib をもとにして ボタン, メニュ−のデザイン等の アプリケ−ションに近いレベルの機能を提供している. Athena widget は widget のサンプル実装としての意味合もあって, X に標準添付されている.

C部分は アテナウィジットの例で説明する。 X <==> Xlib (プログラム側、クライアント). X のプロトコル自体は ネットワーク上のクライアント/サ−バ− モデル になっている. Xlib は低レベルで書かれているので、関数が少なく、 使うのは難しい. X toolkit が定義されたたくさんの関数のかたまり. これにもう少し、ボタンの見掛けのデザインなどをウィジットセットという. Athena, Motif, GTk etc. これらの中で Athena ウィジットセットは試験実装という感じ。

最近は GIMP のために作られた GTk ができがよい。 要するに Athena ウィジットで改良されたものだと考えれば良い. Athena ウィジットはどこにでもあるので、安心.

まず ruby で例を書いてみるが, 基本的な考え方は他でも同じ. X に限らずグラフィック関係のソフトを使う場合になにを調べれば良いかっていうと, 次の基本 3 つができるかどうかだと思う. ボタン、マウスの状態を調べる、マウスで点を打つ. 大きなプログラムを作るのはそれができた後。

ruby のグラフィック関係は tk を使う。 Tcl/Tk の使い方を知る必要がある。 使い方の勉強には, Tcl/Tk はオンラインマニュアル, Ruby リファレンスマニュアル. Tk の部分はオンラインドキュメントが完成していない. どうするかって云うと, /usr/local/lib/ruby/1.4 に ruby 言語で書かれたライブラリがある。 complex.rb とか rational.rb とか例文として利用しても良い。 後は tkcanvas.rb とかのライブラリのソースを見て使うしかない。 tcl とか awk と同じように、#!/usr/local/ruby で始めたファイルを そのまま実行ファイルにすることができる。

gra-button.rb

ボタンの動作をしらべてみよう. たった3行のコ−ドだ. ボタン(Button)について調べようと思って、tk.rb の中身を見てみる class TKButton を発見. Tk.mainloop を # でコメントにすると？ なにもせずに終る。役割は、(雑に言うと) X の画面に窓を表示し、 ボタンが押されるのをじっと待っている、ボタンが押されたら、 押したようなへこんだ絵を書き直さなきゃならない、これらを 実現しているのが Tk.mainloop である。(ちょっと嘘.) Tk.mainloop は必ず必要. これでボタンを押すとなにかが起こるプログラムは書けるようになった.

#!/usr/local/bin/ruby 
# ボタンの動作の例  gra-button.rb
require 'tk'
b=TkButton.new(nil,'text'=>'hello', 'command'=>'exit').pack
Tk.mainloop

gra-mouse.rb

Phython でも sather でも Tk を使っている. C 言語とのインターフェースが必要で、i686-linux-libc1 というインストール しているシステムに合わせてシェアードライブラリが作られる この中に ruby.h とかがある. tcltklib.so や tkutil.so など。 自分で C 言語を使うときでも Tk を通して X を使うっていう手もあるのは 覚えておいても良い.

ソースを見てみよう. 今度はちょっと長い. C の include 相当が ruby の require. 絵を書くための画面を Canvas. 本質的ではないが, ruby のスコ−プ規則は独特なので, 変数のスコ−プに注意する必要がある. $ は ruby の global 変数. ローカル変数は、関数宣言 def の内部に入ることができない. 逆に関数宣言の中で使われたローカル変数は、ブロックの外で使えない. そこで, 関数の中で使う可能性のある canvas は global 変数にしてある.

         $canvas.bind '1', proc{|x,y|
                TkcOval.new($canvas,x-2,y-2,x+2,y+2,'fill'=>'black');
                }, '%x %y'

cbutton=TkButton.new(nil,
                'text'=>'clear',
                'command'=>proc{clearcanvas}
                ).pack('side'=>'left')

        def clearcanvas
          $canvas.find_all.each{|x| x.delete}
        end

#!/usr/local/bin/ruby
# canvas に 点を書く gra-mouse.rb

require "tk"

$canvas=TkCanvas.new(nil,
                'width'=>400,  'height'=>400,
                'borderwidth'=>1,'relief'=>'sunken'
        ).pack
# マウスボタン1 に動作を bind
$canvas.bind '1', proc{|x,y|
                TkcOval.new($canvas,x-2,y-2,x+2,y+2,'fill'=>'black');
                }, '%x %y'
cbutton=TkButton.new(nil,
                'text'=>'clear',
                'command'=>proc{clearcanvas}
                ).pack('side'=>'left')
qbutton=TkButton.new(nil,
                'text'=>'quit',
                'command'=>proc{exit}
                ).pack('side'=>'left')
def clearcanvas
        $canvas.find_all.each{|x| x.delete}
end

Tk.mainloop
# end of script

ドラゴン曲線 (dragon.rb).

n>=0 で a(4n+1)=1, a(4n+3)=0, n>=1 で a(2n)=a(n) この規則で生成した数列を表示してくれる. dragon っていうボタンをバババっと押すと、 ボタンを押すたびに 2^n 時間がかかる. Tk を通すと速度的には損. アテナウイジットとか GTk を使うべき.

#!/usr/local/bin/ruby 
# ドラゴン曲線
# n>=0 で a(4n+1)=1, a(4n+3)=0,
# n>=1 で a(2n)=a(n)
# (1) a(n) が周期的で無いことを示せ
# (2) a(n) を求めるプログラムを書く
# (3)
#    右に1 進み 
#    loop
#        a(n) の値に対して:
#        0 なら 右に90 曲がる
#        1 なら 左に90 曲がる
#        1進む; nを1進める
#    end

require "tk"

def a(n)
	case n%4
	when 1; return 1
	when 3; return 0
	else; return a(n/2)
	end
end

$canvas=TkCanvas.new(nil,
		'width'=>400,
		'height'=>400,
		'borderwidth'=>1,'relief'=>'sunken'
	).pack
dbutton=TkButton.new(nil,
		'text'=>'dragon',
		'command'=>proc{writeDragon}
		).pack('side'=>'left')
qbutton=TkButton.new(nil,
		'text'=>'quit',
		'command'=>proc{exit}
		).pack('side'=>'right')

def writeDragon
	$canvas.find_all.each{|x| x.delete}
	$n=$n+1; m=2**$n; l=100.0/(2**($n/2.0));
	px=200; py=200; x=l; y=0
	for i in (1..m)
		TkcLine.new($canvas,px,py,px+x,py+y)
		px,py=px+x,py+y
		ai=a(i);  print ai," "
		if ai==0; x,y=y,-x;  else x,y=-y,x;  end	
	end
	print "\n\n"
end

$n=0
Tk.mainloop
# end

演習問題. (1) a(n) が周期的で無いことを示せ. (2) a(n) を求めるプログラムを書く. (3) ドラゴン曲線を描く.

			
右に1 進み ,
loop (n = 2^k まで)
	0 なら 右に90 曲がる
	1 なら 左に90 曲がる
	1進む
end

自動配置の気持悪い例.

dancebox は C言語で X部分はアテナウイジットで作った. ボタンやラベル等は置き場所の明示しないなら 適当に配置される. ここで, label に表示する文字列の長さを変えたりすると, 配置の基準が変わって, ラベル類の場所変えが起こる. この例では, マウスが入ると label が長い文字列に変わる. サイズが変わると、label の配置が変わる. マウスカ−ソルの位置によっては, この長さの変化で 自動配置に矛盾が出て, 再配置,再再配置の循環がおこってしまう.

onlytop.c を見る. 窓を出して待っているだけ. ツールを include した上で、リソースを定義、 .Xdefaults とかシステムのリソースも読む. context を一個作っておいて、いろいろの属性を満たすように定義する. 実際にメインループの中で前もって作っておいた context を表示. 基本的に ruby の構成と同じなのがわかるかな?

onlytop2. マウスが窓の中に入ったときに反応を検出する. enter_proc っていう関数を窓の中に入ったときに実行. Tk と比べて面倒。 マウスの操作と名前の対応、などをバラバラに扱う必要がある.

ウインドウの上下、どういうメカニズムか

athena/twintop と pixmap. 隠れていたものが表に出たときになにをすればよいか. 隠れた窓が表に出たとき、pixmap でなにが起こっているか。 Expose を定義する必要がある. exporse, repaint は忘れてはいけない. 窓の形を変えると、repaint がおこる. C で書くときはちょっとだけ気を付ける.

演習問題. グラフィックツ−ルを作成しろ. マウスの操作で canvas に点を置く程度で良い. 色も変えられると良いかな？ file への出力はとりあえず xwd コマンドや xvのGrab でできる.

演習問題. 関数 f(x)=kx(1-x), (2

演習. Xcalc とか Xeye とかは Xlib や Athena ウィジットのサンプルコード的な 意味がある。 参考に読むとか改造して遊ぶと良い.

X 標準の oclock と、kdm 版. 透明時計 oclock -transparent は今一つ、目盛がない. 児玉さんの tips のページから引けたはず。 透明oclock に秒針とjewel を拡充 .

xcalc は改造への対応がよく考えられている. .Xdefaults をちょっと書き換えるだけで見栄えが全然変わる. 改造してみよ.

bc と連携し、bc に渡して結果だけ吸い上げるような X の電卓風インターフェースを作れ。 emacs から bc を呼び出して簡単に使える elisp もうあるけど、自分用に作る。

X のソースを取って来て、中をいろいろ眺めてみるっていうのが大事。

X の イベント駆動モデル と プロセス駆動モデル

ライフゲ−ム(lifeのソ−ス参照).

ecosystem

生物の生体、一匹一匹の増殖戦略を決めておく. ロトカ-ボルテラ補食モデル. 詳しくは 2生物生態系 を見る. dV/dt = a V - b V * P = b V ( a/b - P ) dP/dt = c V * P - d P = c P ( V - d/c )

適当なポテンシャル関数の断面になり、閉じた図形を描く. V と P が sin と cos みたいに循環し合うような関係になる. 時間に合わせて V-P 平面上を反時計回りに回る.

あとは隠れ場所効果(個体数が少なくなると隠れやすくなる)、 餓死しそうになるとがんばる効果をもうすこし入れると良い. 生物学の教科書の棚(数理生体学)ではちゃんと説明されている. ここで, k-->\infty, f(v)=aV としている f(V) が Vが小さいときにしたに凸のS字曲線とすると 隠れ場所効果を記述できる. 補食の効率を表す関数 f(V)

                dV/dt=rV(1-V/k)-f(V)P
                dP/dt=bf(V)P-cP

雑なシミュレーションなんだけど 窓で隠れていた部分再描画の部分を書いていないから, ちゃんとしようと思うなら, Expose と Configure に対応するプログラムを書いておく必要がある. まあ, 画面を更新しつづけているので, あまり気にはならないが...

印刷する場合は、 グラフィックデータを出すような関数を出すと良い. これは netpbm (画像変換ツールセット) のソースから拾ってくると 良いだろう. まあ, XV や xwd を使ってファイルに落してやれば大体は間に合うはずだ.

拡散方程式 (diffusion のソ−ス参照) ロトカ-ボルテラ捕食モデル(Lotka-Volterra prey-predator model)を 拡散方程式化.

                dV/dt=rV(1-V/k)-f(V)P   +d1 \delta V
                dP/dt=bf(V)P-cP         +d2 \delta P
                                        ^^^^^^^^^^^^拡散項

基本的に X のプログラミングはイベントに対して自動的に反応するような、 イベント駆動モデルになっている。 ecosystem, diffusion サンプルプログラムのように、勝手に動き 続けるようなプログラムは、イベントをどのように生成したらよいか. いくつか方法を考えてみよう.

キーボードから取得して出力を繰り返すプログラム.

          while(1){
              ... readln ...
              printf ...
          }

XtAppAddWorkProc で登録されると, 特にイベントが無い空き時間に その関数が実行されるので, XtAppAddWorkProc で foo2 を登録しておいて:

           void foo2(){
            A ... 目的のものを 1 回実行
	   }

自力でイベントを作る. 1 単位時間で画面を書き換えたあとで、自力でイベントを発生させる ruby の life の例を見よう.

1 秒ごとにイベントを作る例. 僕の透明な時計. 透明oclock に秒針とjewel を拡充 .

プログラムの中で勝手にル−プを作ると, X のイベントモデルとの整合性が合わなくなってしまい、 新たなイベントをとれない. 呼び出された関数の中で無限ループをつくっちゃだめってこと. じゃあどうするか。

          while(1){
            A ... 繰り返す
          }

        void foo(){
            A ... 目的のものを 1 回実行
            foo を呼び出すようなイベントキューに登録する
		}

イベントのdispatchを隠蔽するかどうかの問題で 全体としてみると同じだけど.... XtAppAddWorkProc で基底で実行する procedure を登録しても良いが 自力でdispatch する方が簡単.(かな？)

X のイベントがどの段階でプログラムに伝えられるかというと それは Mainloop ( XtAppMainLoop ) を見るとわかる. XtAppNextEvent と XtDispatchEvent が読み筋で, これが繰り返し実行される事でイベントに対応する関数がが呼び出される。 興味がある人は X のソースを読むべし.

	XtAppMainLoop の 実態:
	for(;;){
        XtAppNextEvent(app_con,&event);
        XtDispatchEvent(&event);
	}

この for ル−プを解いて, 他から繰り返し呼び出して イベントをチエックするように書き換える. m2/imp/LINX/Graph.LINX.c を見る .

          /*XtAppMainLoop(app_con);*/
          void XAppEvent(void){
            XEvent event;
  
            CharRead=0;
            while(XtAppPending(app_con)){
                  XtAppNextEvent(app_con,&event);
                  XtDispatchEvent(&event);
            }
            /* XSync or XFlush */
          }

m2/msm/eco.mod の LOOP を見る。(要するに pascal だし) ecosystem で使っている方法は、Graph.LINX.c と入り組んでるんだけど, 自前で mainloop の代替品を作っている. keyboard を押したりすると QuitProc で exit する.

こういう風に X のメカニズムを壊してしまうのは、本には書いてあったけど よいとはあまり思えない。X のイベントモデルに適合した形 で実現したほうがよいでしょう。

演習問題. 2生物生態系シミュレ−ション対して. (1)生物種を増やした場合の動向を調べ, 微分方程式でのモデルと比較しろ. (2) 緯度効果(気温,日照),隠れ場所効果等を組み込め. (2) ロトカ-ボルテラ捕食モデルとの関係を考察せよ.

演習問題. 流体の熱対流 "等" のシミュレ−ションを手続き型言語で書き下せ. (シミュレ−ション用言語/アプリケ−ションではなく.) シュミレ−ションをお手軽にやってみる事が目的ではなく, そのようなシュミレ−ションを成立させている 数学的/アルゴリズム的な背景に注目すること.

演習問題. diffusion プログラムのような "場" に注目したシミュレ−ションと ecosystem のような "粒子" に注目したシュミレ−ションが考えられる. この2つの観点の互換性について考察せよ. つまり, 一方の観点でかかれたプログラムの もう一方の観点への読替ができるか？

色と状態の対応 (diffusion のソ−ス参照)

色の付け方 P-V 平面上の閉曲線で、右が水色、上が黄色、したがって右上が緑

  RGB の 3 原色 ==> 人間の視覚細胞は明るい所で反応するものと
                    暗い所で反応するものの 2 種類があって、
                    明るい所で反応するものはさらに 3 種類

  3 つ揃うと白
  B と G の組合せ <== 1 種類の感覚を刺激しないで 2 種類の感覚を刺激する
  R と G の組合せ 
  G のみ

       Red           Green
             yellow
             [white]
       magenta    cyan
              Blue

演習問題. 数値の大小を色で表す色スケ−ルについて考察せよ. (R-->G-->B の順で大きくなって行くように使ってはどうか) 中間は色相環を考えると良い.

デ−タ−の表現

オブジェクト指向プログラミングを型の拡張の観点から考える. オブジェクト指向プログラミングでのクラスとインスタンスを 代数的な対象(有理数体,多項式環,有理多項式)等の実現のアナロジ−で考える. 有限体, 有理数体, 多項式環 等の実現. デ−タ−の表現, 演算の扱い. Ruby 言語で例示.

オブジェクト指向プログラミングって何？ それまでの古いプログラミングの概念を完全に打ち破った革新的な概念, って云うのは冗談. 構造化プログラミング, 情報の隠蔽, モジュ−ル構造, コ−ドの再利用 等の概念をまとめてうまいモデルにまとめて見せたのがオブジェクト指向. だから, C や Pascal それどころか アセンブラの頃でも 似たような構想でまとめられたプロジェクトはあったし, C や Pascal の概念の延長でとらえるのも全く的外れとは云えない. ライブラリの機能を使うだけという立場から云うなら, すっきりと統一感のあるライブラリの構成モデルとでも思っておいて良い.

普通のクラス構造の説明だと, 例えば動物のクラスがあって, その サブクラス(部分集合) として 哺乳動物クラスがあって....とか 集合の包含関係で説明するけど, 実際のコ−ディング例になると, コ−ドやインタ−フェ−スの再利用のための継承が出てくる. "なんか, 題目と現実がずれてるんじゃない?" とか思っちゃうよね?

クラス自体は何かの操作の実体とかがあってそれに対応するようにまとめている と思って良い. 一方で, 継承の方は, 集合の包含関係, インタ−フェ−スの連関(可能な操作の種類の包含関係), コ−ドの再利用 とかいくつかの面から考えられる.

演習問題. 現在使用している言語で, 実数, 整数, 有理数, 複素数, それらを係数とする多項式環, 有理多項式環 等の間でコ−ドの再利用,継承関係がどうなっているか? 数学的な意味合での包含関係と整合性がとれているか?

まあ, オブジェクト指向って色々な面があるわけで, 数学プログラミングの面から見ると, 上のような包含関係の 他に/代わりに 型システムの拡張の観点から見ると良いような気がする. Oberon言語とかの設計例を見ると明確になると思うけど.

実際の世界の犬や猫をオブジェクトと考えるんじゃなくて, 環や体(有理数体,多項式環等)をオブジェクト(クラス)と考える. 要素を取り出すこととインスタンスの対応, 要素に演算を考えることとメソッドの対応とかを見てみる.

現実世界にある物体にメッセージを送るっていう考え方はちょっとわかりにくい. C や Pascal でいう型システムの延長で考えるとよい。 以下では, 有理数や多項式のような代数的な対象を例に オブジェクト指向を見る. オブジェクトクラス = 代数的な実体. インスタンス = 代数的な実体から元をひとつとりだしてきたと考える。 メソッド = 計算規則の定義.

まず, 有理数の実装の例を少し見るけど, 有理数の (分母,分子) の整数の組みと対応付けと, 有理数の演算を取りまとめている様子を, Ruby のライブラリとかで, 自分で観察してもらいたい.

C だとやっかいなところ. rational を構造体として定義.

rational plus(rational r1,r2){
     ... 和の計算
      return r2;
}

/* d=a+b+c の計算 */
d=plus(plus(a,b),c);  こうやって書かなきゃならない
                      気分的にちょっとね。
                      実装法によってはここでメモリリ−クが起こるよ.

ruby が見やすい. ruby の標準添付ライブラリ rational.rb で有理数体を実現している.

      class Rational < Numeric

      def initialize(num, den)  分子分母 2 つの整数で定義

      @numerator = num
      @denominator = den

         @ はインスタンス変数(今取り出した要素が持っている値)

        require "rational"
        r1=Rational(3)   # r1 = \frac{3}{1}
        r2=Rational(2,3) # r2 = \frac{2}{3}

メソッド + とか - とかを定義したい

         def +(other)
         # self.plus(other) と同等の意味
           和の計算
         end       

         # d=a+b+c を計算したい
         d=a+b+c;

Sather の場合

 plus(other;RATIONAL):RATIONAL is
     # c=a+b は c = a.plus(b) を表すが四則演算記号等は . を省略してよい
     ...和の計算
 end;

 # c=a+b
 c:=a.plus(b);
 c:=a+b;
 # + は plus の syntax sugar

C++ でも同様に c=a+b; で複素数の和を定義できる modula-3, java は関数の再定義ないので, C のような感じで plus とかで書く！ C++ は + の再定義はできるが, GC がないので、ポインタを含む型でこのように使うと 色々と面倒な帳簿つけ的な作業が必要.(ダサダサだね.)

例： C , Modula2 での BigInt, Rational, Polynomial の実装と問題点. (メンテナンス性、 GC, 演算を表す構文) どれぐらい困難かをやってみます。

    knot のソースの msi/ (C でいう hoge.c に対応)以下で自前でやっている。
    knot のソースの msd/ (C でいう hoge.h に対応)
    PolyInt.msi  一変数整数多項式
    LongIntM.msd 多倍長整数計算
      基本的な構造は、
        sArray
        LongIntP ポインタ
        長い整数を 32bit 相当のかずに小分けしてポインタでつなげている
    LongIntM.msi  
        allocate, deallocate を自前でやる
        newS, disposeS
        メモリリークの検出を自分でやる
          GC のない言語で allocate や deallocate を繰り返す場合はこのようにする
        LongAddA が足し算
            pa は answer へのポインタ
            C では先にアドレスを作っておいて、ポインタを作る

  bigint として int のリンクリストを定義
    bigint plus(bigint a,b){
      res=a と b の和を作る
      return res; res はリンクリストであることに注意
    }

  /* d=a+b+c を求めたいので*/
  d=plus(plus(a,b),c);
             ~~~~~ a+b に対応する bigint が生成されている
                   これを deallocate していない

コピーの話

注意: shallow copy と deep copy. 大抵のインスタンスは内的には構造体へのポインタとして実現されている.

	a=FOO.new # a--->XXX
	b=a       # 代入すると, ポインタによる参照の代入がおこる.
	# a---->XXX
	# b-----^
	aのインスタンス変数を変更すると, b からも変更が見える.

	a=FOO.new # a--->XXX
	b=a.clone  # 代入すると, 新たな実体が作成される.
	# a---->XXX
	# b---->XXX'
	aのインスタンス変数を変更しても, b からも見ない.

	a=BAR.new # a--->XXX--->YYY
	a のインスタンス変数自体もポインタで実装されていた場合.
	b=a.clone 
	a が複製されるが...
	# a---->XXX --->YYY
	# b---->XXX'----^
	インスタンス変数の参照先までは複製されない.

  b=a   実体はコピーされず、a と同じものを参照する
        a を加工すると、b からも変化したものが見える
        (効率は非常によい)

  b=a.clone   b に a のクローンを与える (浅いコピー)
              a がさらに別の実体を参照していたとすると、その先の実体は
              コピーされない( shallow copy )

多項式 a = 3x^2 + 4 x + 5. a のインスタンス変数(内部での実現)が配列でなされているとする.

       _ _ _
  arr=|5|4|3|
       ~ ~ ~

         _____ _____ _____
  arr = | 3/4 | 2/3 | 1/2 |
         ~~~~~ ~~~~~ ~~~~~

多項式環を扱おう！

多項式の係数環の柔軟性. 総称(C++で云うテンプレ−ト)の例. Sather では Parametrized Classes にほぼ対応. Ruby では不要.

Sather では Parametrized Class にほぼ対応 型の混合への対応は？(整数係数多項式を有理数係数の場合と混合) polys.sa を見よ 一変数は配列で実現. polym.sa は多変数. 係数環が R 、これをクラスとして実装する 有理数係数の多項式環、複素係数の多項式環、すべて別々のクラスとして定義

      clas POLYS{R} is ...
                ~~~係数環をパラメータとする
      POLYS{RATIONAL} クラス
      POLYS{Zp} クラス

      POLYS($OB)
           ~~~~オブジェクトクラス

ruby では 和、差、積だけじゃなくて、多項式環の商体を作ったりもできるし、 係数環を別にきめてもそのまま使える。 正方行列環係数とか. 多項式クラスを与えたときに、係数になにがくるかは書かなくていい. オブジェクトクラスを与えたのとおなじ状況になっている. lib/ruby/polynomial.rb をみよ. 多項式の係数を配列に対応させることは、ある数列に母関数を対応させること に同じで自然な考え.

      def + (other)
             ~~~~~なにがくるかわからない、全てのオブジェクトを受け付ける
                  だから最初に受け付けてよいかどうかチェックする
                  if other.kind_of?(Polynomial)
                           ~~~~~~~~ smalltalk みたい。

Ruby: coerce による型の混合への対応 なんでも受け付ける coerce 開発者間の同意事項で、相手側のライブラリに変換を依頼する. polynomial.rb では def coerce(x) 以下に書いてある. 数値、式、配列のかたちそれぞれの場合に対応できる. 式の文字列に対しては、数式パーサを用いて評価する. 数式パーサは、数式処理ソフトの腕のみせどころ. eval (数式をそのまま実行しちゃうと、多項式がかえってくる) 157 行目 それぞれの変数を eval でかたづけちゃう 文字列で書いて変換する. 柔軟なライブラリが作れる.

Sather: 適当な型への変換を明示的に指定する. 適当な super class をパラメ−タとする. 後づけでも super class を定義できる 2 つの環で包含関係がある場合は、Sather の場合は自動変換はなく 意図的に行わなければならないので、自分で明示的にクラス間の変換を 用意しておくべき。 Sather の場合は rubyとは対照的に、人間が明示的に変換を行う ruby っていうのは実際に使うような計算プログラムのライブラリにあっている. 唯一の ruby の欠点は速度.

C++ では型システムの不備で $OB に対応する高位のクラスがない。 Java はこういう点考えられている。Sather とか Ruby もそうなっている。

Risa/Asir P_x で変数 "x" を表せる. Ruby polynomialm.rm P_.x で変数 "x" を表せる.

多変数多項式. Ruby の monomials

p=@power.clone
m.power.each_pair{|v,d| p[v]=p[v]+d}
                   ^ ^-- 次数
                   |--変数名
@power=Hash.new(0) # デフォルト 0
@power={"x"=>2, "y"=>3} # x^2 y^3
zdeg=@power["z"] # --> 0 つまり x^2 y^3 z^0 と見なされる

自分のプログラムの中で
class Monomial
   def myOrder(other)
     ...
   end;

   alias old_comp , <=> # 名をすり替える. 書式は間違いかも？

   def <=>(m)
      .....<=> を再定義
   end;
end;

one, zero の扱い.

/usr/local/lib/Sather/Library/Math/ rat.sa, cpx.sa Sather の complex (cpx.sa), real part と imaginary part, ここに int を使うと Gauss 整数. +, -, time, ,less ,で 1(one) や 0(zero) を返さないとうまくいかない. zero は自分自身を引けば作れるが one は？ rat.sa には one, zero がない. ライブラリ作者間の同意事項が必要. 言語の仕様以外の部分. polys.sa の例. 0次で定数項が0 の多項式を生成する部分で, 係数が complex の場合と rational の場合で、 参照先がある場合とない場合がある. ruby だと整数の 0 をほうりこんでおけば、coerce のメカニズムで 解決してくれるが、sather の場合は厳格なため問題がおこる.

Sather等 型に厳格な言語で.

element_zero:ET is
    if R.has_method(zero) then return R::zero;
    else ...どうするか？
        return #R(0); --適切なゼロ元ができるか？
    end;
end;

gbasem.rb 多変数関数のグレブナベースを計算する 係数環を有理数体にした場合と、Zp の場合を分けて書いちゃったけど、 体にはならない場合にグレブナベースをどうやって計算するかわからなかったので ちゃんと係数体を定義しておくと、一つの実装で問題なくいける。

ftp から Sather と ruby のプログラムをとれ！ ruby 勉強したら Sather もわかる。

ruby は
   def メソッド名 引数
      ...
   end

sather は 
   メソッド(引数:クラス名) クラス名 is
        ...
   end;

sather
  loop i::=0.upto!(d);....;end;
ruby
  0.upto(d){|i|....}

hyperreal.rb 超限実数 dx や dy などを含んだ体 四則演算のようにして極限の計算や微分ができる.

グラフ理論

t:=new(木構造);
t.each_with_preorder(|vertex|  ...  }
                             ~~~~~~~クロージャ
         (処理の固まりをeach...の引数として渡す)

     普通は b=func(a)
                   ~値

演習問題.

表現 抽象的グラフでは 辺行列,隣接行列,隣接リスト,接続行列. 空間グラフでは???

入力？ 文字入力には "辺リスト" が効率が良い. これから, 隣接行列等に変換する.

演習問題. グラフの実装例. (Sather添付ライブラリ Graphs 参照)

演習問題. グラフが与えられたときオイラ−グラフかどうかを判定せよ. オイラ−グラフに関しては, オイラ−回路を求めよ.

演習問題. グラフの入力 をデザインしろ.

演習問題. グラフの適当なデ−タ−表現で G/e , G-e の操作を実現しろ.

演習問題. n個の文字 J(n) の置換全体からなる置換群 S(n)の デ−タ−表現をデザインしろ. 積, 逆元 等の操作を実現しろ.

演習問題. S(n) の元に対して, 巡回置換の積の形でプリントせよ. 巡回置換どうしは,巡回置換の長さ,含まれる数字等で適当にsortすること.

演習問題. S(n) の元に対して, その元の Yang ダイアグラムを求めよ.

演習問題. S(n) の元の入力をデザインしろ. どのような方法が考えられるか？ 独立な巡回置換の積の形での入力を実現しろ.

演習問題. 1変数多項式のプログラム内の表現について考察せよ. 次の2つについて, 実行時間, メモリ効率, 実装の容易さ等の トレ−ドオフを考えろ. 1変数と多変数で状況はかわるか？ また, 他の表現法は考えられるか？ (1) 配列(Array) を有限数列と見て, これと母関数を関連づける方法. (2) 単項式に対して cx^n を nとc の組み [c,n] と表して(c != 0) 多項式をこれの列として表現する方法.

演習問題. 1変数多項式のデ−タ表現を設計し, +,-,*,/ に対応する関数を作成しろ. f3 = f1 + f2, f3 = plus(f1,f2), plus(f3,f1,f2) 等のような 記述(...のうちどれか)を可能にする.

演習問題. n変数の多項式環 k[x1,x2,...,xn] の元を

	(1) c*x1^{a1}*x2^{a2}*...*xn^{an}
	  の項のあつまりとして [c,a1,a2,a3,..an] の組みの列として表す場合
	(2) p[a1,a2,a3,...,an]=c と配列の拡張での実現
	(3) k[x1,x2,..xn]=k[x1,x2,..xn-1][xn] とみなして
		1変数多項式の係数の拡張とみなして実現.
	(4) c*x1^{a1}*x2^{a2}*...*xn^{an}
	  の項のあつまりとして [c,(xi=>aiのhash)] の組みの列として表す場合

演習問題 Bignum のデ−タ表現について考察せよ. (1) 必要サイズのメモリ−ブロックを確保する (2) 適当な(一定)サイズのブロックの link list (U-Basic の例?)

繰り返しと再帰的アルゴリズム

a(n)=2a(n-1)+3a(n-2), a(1)=3, a(2)=1 (suuretu.rb)

フィボナッチ数列 f(0)=0,f(1)=1, f(n)=f(n-1)+f(n-2) (fibonatti.rb, gosa.rb)

ペラン(R.Perrin)の数列 (perrin.rb) p(0)=3,p(1)=0,p(2)=3, p(n)=p(n-2)+p(n-3) q(n)=p(n)/p(n-1) の極限を求める

2分法 又は Newton法で 3次方程式の解の近似値を求める

演習問題. 数列の計算でのさまざまな手法のトレ−ドオフを考察せよ. Bignum が必要な程度に数値が大きくなると, 基本演算の計算時間を一定とみなせなくなる. +-*/ の基本演算の負荷を一定とすると 数列から a(n) を求める時間は:

		表引き  O(1)
		行列表現  O(\log n)
		線形再帰  O(n)
		樹状再帰  O(\frac{1+\sqrt{5}}{2}^n)

演習問題. a(n)=2a(n-1)+3a(n-2), a(1)=3, a(2)=1 は 等比数列の和として a(n)= 2*(-1)**(n-1) + 3**(n-1)) で直接計算できる. a(n)=2.0*(-1.0)**(n-1) + 3.0**(n-1)) として(又はこれを四捨五入) 浮動小数で求める場合何がおこるか考察せよ. 計算時間, 計算精度 等. 正しい値が出るのは何項目までか？ 正しい値が出なくとも, 概算値が必要な場合には有用だが 概算値が計算できるのは何項目までか？

演習問題. 数列 a[n]=3a[n-1]-a[n-2], a[1]=1, a[2]=1 の計算を 等比数列の和として a*r1^(n-1)+b*r2^(n-1) の形式で直接求めた場合. どの程度の n まで計算結果が保証できるか？

演習問題. a(2^100) が必要になった場合どうするか？

演習問題. 以下の各々を Newton法で求めよ.

		x^2-4=0 の解 x=2,  初期値 0 以上
		x^{1/3}=0 の解 x=0, 初期値 任意
		sin x =0 の解 x=0,  初期値 |x| は π/4 未満

演習問題. Newton法の初期値はどのようにするのが良いか?

演習問題. Newton法の終了条件はどのようにするのが良いか?

演習問題. 1次元の 実数x については Newton 法が定義できるが, 複素数 x についてはどうか？ 具体的には x^3-1=0 の解がうまく求まるか？ また, 初期値と収束先の関係を調べろ.

演習問題. グラフに対して, 全域木の個数( t(G)=t(G-e)+t(G/e) (eが cut edge でないとき) t(G)=t(G/e) (eが cut edge) ), 連結成分数( b(G)=b(G/e) ), k-点彩色数/彩色多項式 ( p(G)=p(G-e)-p(G/e) ), 連結全域部分グラフ数, 等を求めるアルゴリズムを適当なプログラミング言語で実装/実現せよ.

演習問題. n の Ynag ダイアグラムの数は？ 総ての Yang ダイアグラムを印刷する((逆)辞書式順序で) (yang-diagram.rb)

演習問題. ユ−クリッドの互除法をル−プで実現せよ.

ル−プの再構成

ル−プの形式で記述されたアルゴリズムを 呼出毎に部分的に実行する形式に変換する. 他のアルゴリズムに組み込む場合や, X の呼出モデルに適合させる場合に必要.

なぜこんなことを考えるのか順列生成の例で考えてみる. アルゴリズムの教科書とかで見ると順列生成とかその他のアルゴリズムは こんな感じで書かれているはず.

初期設定
loop
    何かいろいろ作る(...でなければloopから脱出)
    使う.
end;

初期設定 1
loop 1
    何かいろいろ作る 1(...でなければloop 1 から脱出)
    初期設定 2
    loop 2
        何かいろいろ作る 2 (...でなければloop 2 から脱出)
        使う.
    end;
end;

class PremutationStream
    def initialize
        ....初期設定
    end;

    deg generate
        ....順列生成
    end;
end;

# 2個の順列を調べる例.
stream1=PremutationStream.new # 初期設定1
while (perm1=stream1.generate) # 生成1
    stream2=PremutationStream.new   #初期設定2
    while (perm2=stream2.generate) # 生成2
        ....使う
    end;
end;

順列の生成(Heap のアルゴリズム) (permutation.rb)

演習問題. permutationの生成をル−プで実現するのではなく, 呼び出し毎に1個ずつ生成するような, ストリ−ム風に実現しろ.

	def gen_loop
		local 変数...
		初期化
		loop
			生成
			print...
		end;
	end;

	class Sample
      # 代数的な対象を提供する class ではなく、アルゴリズムを提供するクラス

	attr 状態を表す変数;

	def initialize
	...初期化
	end;

	def gen_unloop
		生成
		return 結果
	end;
	end; # class

	def main
		a=Sample.new;
		b=Sample.new;
		loop
			g1=a.gen_unloop;
			....
			g2=b.gen_unluup; # 複数生成できる
			g1, g2を使う;
		end;
	end;

演習問題. (1) 有限表示群 G= から S(n) への表現の個数を数えろ. (2) conjugate なものを除いて数えるにはどうすると良いか.

演習問題. Yangダイアグラム生成をル−プで実現せよ.

演習問題. Yangダイアグラム生成を 1度呼び出す毎に1つづつ生成するような (ストリ−ムモデルの)手続きで実現せよ.

想定する利用法
loop
    y=YANG::genYang # yang図を1個生成
    loop
        g=genPerm(y) # yに対応するconjugate クラスを生成
    end;
end;

探索コ−ド

集合 S の条件から x が S に入るかどうか調べる. ( in-set.rb )

n-queen の実現方法(nqueens.rb). N-Queens (nqueens.rb) N*Nの桝にN個のQueenを互いに当たらないように置く置き方は何通りあるか？ while や for ループの入れ子構造. ループを繰り返す. ループを関数にしておいて再帰的に呼び出す.

演習問題. N-Queens の実現で ル−プの入れ子, 再帰版, 再帰+当たり判定テ−ブル の 3手法で メンテナンス性,実行効率等は？

演習問題. チェスボ−ドの分割 (split.rb). (2n)*(2n) のチェスボ−ドを桝目に沿って切り 対称な2つの部分に分ける. 分け方は何通りあるか？ ただし,回転,反転でおなじものは同一とみなす.

演習問題. (2n+1)*(2n+1)のチェスボ−ドから中央の1桝を除いたものを 対称に切り分ける わけ方を数えろ.

演習問題. 多項式の分解 polynomial.rb . (1) Zp 上で分解の候補を探す (2) Z 上への戻し方を探す

演習問題. n*n の魔方陣を生成せよ. 1..n^2 の数値の配置の探索と解釈できる. n=奇数の魔方陣に関しては効率の良い方法が知られている.

演習問題. Yang ダイアグラムに対して, そのような Yang ダイアグラムを持つ S(n) の元を生成するコ−ドを書け. (ある元に対して conjugate な元全てを求める問題と同等)

	Jn={1,2,3,...n} n個の文字
	S(Jn): Jn の置換群
	s \in S(Jn)
	s=(1,2,3)(5,6)(4) sは独立な巡回置換の積で表現できる.
	この長さを大きい方から図示したものを Yang 図形という
    Young diagram は orbit の長さを求める
    巡回置換の長さを図示したものと考えるとよい

	(こだわる人への注: 巡回置換を s の作用による orbit とみなす.)
	Yang 図形と 和がn の非増加数列(>0) を対応させる事ができる

	■■■ <--長さ3の軌道/巡回置換に対応
	■■   <--長さ2
	■     <--長さ1
	yang図の数列表現 3,2,1

	s=(1,2,3,4)(5)(6)
	■■■■
	■
	■
	yang図の数列表現 4,1,1

	s=(1,2)(3,4)(5,6)
	■■
	■■
	■■
	yang図の数列表現 2,2,2

	[Fact] Yang図と S(Jn) のconjugate class は 1:1 に対応する.
	                        ^^^^^^^^^^^^^^^同値関係

x^{-1}sx = t となる xがあるとき sとtは同値 s〜t で同値関係を考える. x は文字の名前付けを変える効果がある. 文字の入れ換えだけなので s と t の巡回置換表示での長さは変わらない. 和がnの非増加数列 は conjugate class(置換群のあるクラス) を 1 つ決める.

このときtはsに対してJnの名前づけをxに沿って付替えたものと解釈できる. 文字の入換えだけなので s と t の巡回置換表示での長さは変わらない. つまり同じ yang図を持つ.

loop
    y=YANG::genYang  # yang図を1個生成
    loop
        g=genPerm(y) # y に対応する conjugate クラスを生成
    end;
end;

こんな感じで S_n を yang図から conjugate class の意味で整理されたものを構成できる

演習問題. 上の逆, つまり "同じ yang図を持つなら同値" であることを示せ.

結び目理論

画像の解釈 デ−タ表現 アルゴリズム(群表示を求める) アルゴリズム(Alexander 多項式,Bignum,多項式の扱い) 演習問題 結び目の入力をデザインしろ. 時間が無いので省略.

コンパイラ/インタプリタ系の組み込み

ruby については、文字列を eval 命令でプログラムとして 与えることができる. lisp の場合だと、プログラムを list として生成しておいて実行なので できて当然。 一般にインタープリタ言語は eval 相当があれば OK. 問題はコンパイラ言語のなかで生成したコードを、プログラムを実行したい場合。

nqueens.rb の例で考えてみる. 8-queens を 8 段階のループで実現. q[1] が 1 番目の queen の置場所. 行の位置は queen の番号で打ちぎめ. 列の位置を 1 から 8 まで for loop を組み合わせる. ル−プの深さが固定となってしまうので 6-queen や 7-queen に適合しない. loop を再帰呼び出しに展開する. ループの入れ子を関数の呼び出し関係に分解、1 つの for loop を関数にした. n-queen の n に対して、入れ子の for loop の関数を文字列として 書き出して、eval で ruby に実行させる.

	例:
	8-queen
	def queen8 # n-queen のサンプルコ−ドより.
		for..
			for..
				....8段階の for ル−プ
			end;
		end;
	end;

	n に対して対応する関数を生成して eval すると良い.
	qString = "
		def nqueen
			for...
				...n段階のfor
			end;
		end; "
	eval qString;

KNOT プログラムの 群表現の探索コ−ドの例. 1次元ホモトピ−群 G=π1(S^3-k) の群表示(ペリフェラル構造つき) と 結び目の幾何的な構造を 1:1 に解釈できる. f: G-->S(Jn) 準同型 の表現と covering 空間に 1:1 に対応がある. 群表現 f を探したい. (有限表示群から S(n) への表現, covering空間)

G の生成元の各々に対して S(Jn) の元を与えるような ル−プのコ−ドを Gの関係子を満たす事を確認するコ−ドを作って それを実行すると f を探す事ができる. コ−ドの生成部分と実行部分を コンパイラ/インタプリタ系と解釈できる.

インタープリタ( eval 機能 )の命令解釈部. program がコードをつくり出す == コンパイラ. コードを実行する == インタプリタ. コンパイラとインタプリタを両方兼ね備えた言語 pascal ( p-code という実行コードを生成 ). Java. コンパイルしたコ−ドを Java VM で実行. perl. プログラムを読んだとき、大体のところはパースしてしまって 中間コードに落してしまう, でもこれはインタプリタだな. ruby. perl と同様.

knot のソ−スより msi/REP.msi, msi/RepSack.msi, msd/RepStack.msd を参照 インタプリタとして, 群コ−ドの計算が出来る スタックモデルの仮想計算機を構成する.

インタプリタの基本的な構造.

	prog:計算コ−ド, 各行に1個の命令が書かれている.
	pp: プログラムポインタ, prog の注目する行番号

	loop
		command = prog から pp の行を1行読む. 
		if command="end-program" then loop から出る; end;
		case command
			.... command に対応した操作を行う.
		end;
		if 通常の場合 then pp を 1増やす;
		elsif 分岐/junp命令なら then pp を適当に細工する;
		end;
 	end;

変数管理, 数式の解釈 等が難しい.

basic インタープリタを作りたいっていう場合 面倒なのは変数管理と数式のパーシング サブルーチンなんか定義するなんていう話は後の話

2 項演算を中置きにしているから難しい 後置きの記号を使えば、数式の解釈は必要なくなる inorder から lisp 風の preorder でなく postorder で書き下したらどうか

      1+2       # ==> 3  inorder
      1 2 +     # ==> 3  postorder
      (+ 1 2)   # ==> 3  preorder  <== Lisp
      plus(1,2) # ==> 3  preorder  <== C 言語の関数

        1   2     3 4 # 計算順序
	1 2 + 3 + 1 1 + + # == 8 postorder
	    3   6     2 8 # 値

        1   2  4  3   # 計算順序
	((1 + 2)+3)+(1+1) # == 8 inorder
		3   6  8  2   # 値

インタプリタのデ−タ操作 次に数式の値を覚えておく部分だが、スタックモデルではどうか

デ−タ−には命令空間とは別に デ−タ−空間を用意する. デ−タはスタックモデルを用いると簡潔になる.

スタック モデル の特徴

	* 命令の設計で操作の対象を指定する必要が無い.
		stack の top に対して操作するように定義すると良い.
	* 数式のパ−サが不要
	* local変数の確保/管理もほぼ自動的に行える.
	* グロ−バルデ−タの扱いが難しい.
		対策1: 静的な記憶領域も作る.
		対策2: グロ−バルデ−タ−でstack に置いた時点で,
			この stack ポインタを記憶しておく.
	* スタックに置けるデ−タ構造を問題領域に合わせて適切に設定すると
		スタック上の演算の表現が簡潔になる.



		例:
置換 s=(1,2,3)(4) \in S(J_4)
	1->2->3->1 
	s=|1 2 3 4|  元
	  |2 3 1 4|  置換え先
	上の置換え先を取り出すと:
	s=[2 3 1 4] のように数列に対応させる事ができる.
	C 等では
	s=[0,2,3,1,4]; と 配列で表現する.
	s[1] # ==>2
	s[2] # ==>3
	s[3] # ==>1
	s[4] # ==>4
	つまり, 配列 s への参照がそのまま
	置換 s の作用を与えている.

    数値の演算でなく、置換群の元の演算を行うような置換群計算マシンを作りたい.
			案1. s を stack に
				2 3 1 4 の4個の数値を 置くと良い.
				通常の数値の計算とも相性が良い.
			案2. s を stack の 1個の成分として
				[2 3 1 4] の塊のまま置く.






KNOT プログラムの 群表現の探索コ−ドの例.
1次元ホモトピー群 G = \pi_1(S^3-k)
RepStack.msd  44 行目あたり

pointer up
pointer down    一番上を捨てる
Dup             先頭の上に copy を積み上げる
Swap
Drop
Over            引数 n で先頭 n 段目を一番上にコピーする(1段深くなる)
Rot             先頭 n 段をくるっと回す

Unit   単位元を置く
Inv    逆元を置く
Mul    かけ算
Eq()   同値判定





stack overflow を回避するには、stack の消費量をメモっていったらどうか.
  コメントでメモってある.
  演算の設計の方針としては、途中の計算は捨てる.




置換群の元そのものはどこで作るか.
57 行目あたり.
  Heap のアルゴリズム.
  ローカル変数をインスタンス変数において、ってことをせずに、
  スタック変数に置く.

InitGen を読み込んで Gen() を読み出す.




	conjugate の意味 1.
	f: G --> S(Jn) 準同型を構成したい.
	f1〜f2 : inner aut i.e. Exist s	s.t. f1=s f2 s~
	なら, f1, f2 は 番号付けの見掛けの違いだけなので,
	本質てきな差ではない.
	こういう無意味な差しか無いものは取り除きたい.


	conjugate の意味 2.
	結び目群(結び目の 補空間  S^3-K  の 1次元ホモトピ群 \pi_1(S^3-k) )
	の Wirtinger 表示では,(結び目群の良い性質を持つ有限表示)
	生成元は互いに conjugate になっている.		
	つまり, 1個の生成元に対して f(x) が決まれば,
	他の生成元の像は f(x) と同じ conjugate class 内にある.



  つまり 1 個の生成元に対して、f(x) が決まれば、
  他の生成元の像は f(x) と同じ conjugate class 内に
  あるG の生成元すべてについて、map をきめてやって、
  像が G の relation を満たすかどうかを調べれば良い.
  x の行き先をきめて、その conjugate class から他の元を取り出す.



	f の探し方 	群G=< x1,x2,...xk | r1,r2...rl >
	while(y=Yang図生成) # conjgate クラスが決まる.
		x1=yの代表元を固定
		while(x2= yが表すconjate class から生成)
			....
			xi=rj と 既に決めた x* を元に計算
			....k段のwhile ル−プで x1...xk が生成された
				r1..rl の関係をチエックする.
				失敗したらwhile の先頭で次を試す
		end;
	end;

	上の探索コ−ドに相当するコ−ドを G の群表示に応じた戦術で
	生成して,
	群コ−ドのインタ−プリタに与えると,
	準同型 f を全て生成できる.


	上の ル−プで書かれたコ−ドを, 実際には
	stream で(呼び出す毎に1個の f を生成するように)実現したい.


	ル−プは解いてしまうので, インタプリタでは
	while や for に対応する ル−プの構文は設計する必要がない.
  while ループを使わず、n-queen の例と同じようにループを解いてしまう.




	群コ−ドコンパイラが作成するコ−ドの概念.
  インタープリタ部分と、コンパイラ部分の組になったものは、
  REP.msi というソースにある

  # pp:プログラムポインタ.現在のプログラムの実行行を指す.
  yang図初期化
  label y=生成
  x1=yの代表元を固定 
  conjugacy クラス初期化
  label x2=生成
  生成に失敗したら直前のラベルに飛ぶ
  ...
  xi= (rj と既に既に決めた x* を元に計算)
  ... k段の while ループで x1 ... xk が生成された
  r1 .. rl の関係をチェックする
  チェックに失敗したら、直前のラベルに飛ぶ(プログラムポインタを適当に戻す)

  # コ−ド開始
  #  pp が上から流れて来たときにはそのまま流すけど、
  #下から上がって来たときにはexit して終了するコードを、
  #一番上に置いておけばよい。
  #
  label exit ; #全て生成しおわるとここに戻って来る.
  #  全ての f を生成しおわった時には、yang図形もすでにすべて生成しおわって
  #一番上に戻って来る。
  #初めのpp はここをさす事にする.
  # while(y=Yang図生成) # conjgate クラスが決まる.
  yang図初期化
  label y＝生成
  x1=yの代表元を固定
  #while(x2= yが表すconjate class から生成)
  conjugacy クラス初期化
  label x2=生成  # <----生成の行に label を置く
      # 生成に失敗したら直前のlabel に飛ぶ
  ....
  xi=rj と 既に決めた x* を元に計算
  ....k段のwhile ル−プで x1...xk が生成された
  r1..rl の関係をチエックする.
  #失敗したらwhile の先頭で次を試す	
  失敗したら直前の label に 飛ぶ(プログラムポインタを適当に戻す)
  #end;		
  #end;
  #もし最後までうまく抜けたら、関数 f の生成に成功している
  #label 次回の実行は pp(プログラムポインタ)を弄らないままでここに戻ってから
  #直前の label に飛ぶ.	
  # コ−ド終了






	演習問題.
		動的に構成されたコ−ドの実行方法を考える.
		インタ−プリタ言語では？
		ruby-poly の 多項式の入力の例.(eval)
		コンパイラ言語では？
		マシン語レベルで生成してそれを実行するという手もある.


    演習問題.
        スタックモデルの古い言語 Forth が有名。言語仕様を調べてみよう。
        knot のプログラムにも stack を使った部分があるので、参考にせよ.
        天文学をやっている人が、望遠鏡を制御するのに使った.


    演習問題.
        pascal-p, PL/0 等のコンパイラ/インタ−プリタ−系のソ−スを調べてみる.
        縮小言語の実装を見るような教科書をみるとよい。


    演習問題.
        生越のsmall 等の インタ−プリタ系のソ−スを調べてみる. 
        (http://www.nurs.or.jp/~ogochan/hack/)
        perl, python, ruby 等のインタ−プリタも,
        実行時に前もって構文解析を行っている.
	small でも構文木を構成している.




神戸大学理学部数学科のペ−ジへ.
児玉のホ−ムペ−ジへ.