比較プログラム言語論 平成１７年５月１８日 森田　彦.

Presentation on theme: "比較プログラム言語論 平成１７年５月１８日 森田　彦."— Presentation transcript:

1 比較プログラム言語論 平成１７年５月１８日 森田　彦

2 レポート（5/11）総括 ＜ テーマ ＞ ＜興味を持った点＞ ＜感想＞
　＜　テーマ　＞　 本日の講義で、あなたはどの様な点に最も興味を持ちましたか？そしてその理由は？それらをできる限り具体的に、200字～400字程度で記述して下さい。 　＜興味を持った点＞ コンパイルの過程（流れ） 最適化 コンパイラとインタプリタ 　＜感想＞ コンパイルの過程を理解してからプログラミングを行った方が良い？

3 興味Ⅰ－コンパイルの過程①－ 今回の講義で最も興味を持ったのはプログラムの実行のながれです。プログラム実行と言っても内部ではいくつもの工程を経て実行されていることがわかったからです。特にその工程の中にある翻訳（コンパイル）ですが、単に構文を解析するだけではなく、プログラムの無駄な部分を最適化することによって処理時間の短縮や容量の縮小などの向上を図っている重要な工程であることを知りました。今までJBuilderで何気なくプログラムの実行を行っていましたが、その中でも最適化が行われていたことは知りませんでした。

4 興味Ⅰ－コンパイルの過程②－ 私が今日の講義で興味を持ったことは、コンパイルの過程です。入力された原始プログラムから一句一句の字句に分解していることははじめて知りました。いっぺんに処理していると思っていたのでコンピュータというのは何を処理するにも分解してから、効率を上げるための最適化と同じように、簡略化してからひとつひとつ処理していくものなのだと思いました。 今日の講義で一番興味を持った事は、コンパイルの過程です。 字句・構文・意味の解析や、最適化などの面倒な作業を、人間に代わってコンピュータが自動でやってくれるし、こちらの方に間違いがない限りその結果に間違いが生じないというのも、一見当たり前のようですが実はすごい事だと思います。

5 興味Ⅱ－最適化①－ 今日の講義では『コンパイルの過程』に興味を持ちました。その中でも『最適化』です。プログラミングをするときに何気なく書いているもの、たたきこみ、共通式に置換等。コンパイラにそんな機能があるとは知りませんでした。あらかじめたたきこみ等を使用してプログラミングしなくても結局は同じ速さで処理をするプログラムが出来るのですね。小さなプログラムならたいして関係ないのでしょうが、大きなプログラムであらかじめ最適化されたもの、してないものだとどのぐらいコンパイルに時間がかかるのかふと気になりました。

6 興味Ⅱ－最適化②－ 今までどれがうまいプログラミングコードでどれが冗長なプログラミングコードかが、いまいちピンときませんでした。ただ文字列をそろえて見やすければいいのかな、といった程度のことでした。しかし、この最適化の「共通式の置換」「サブルーチンの組み込み」を見て、なるほどと思いました。（中略）・・・プログラミングの時間、領域の効率化を図る。それが出来ているコードがうまいプログラミングなんだと実感しました。 最適化によるメリットは理解できましたが、最適化された後のデメリットも詳しく知りたいと思いました。 ＜質問＞

7 最適化と分かりやすさについて 無駄な処理をなくすことは必要 しかし、一般に最適化を進めるとプログラムの処理内容が分かりにくくなる。
＜例＞半径ｒの円の面積Ｓと球の体積Ｖを求める場合 double pi=3.14; S=pi*r*r; V=4*pi*r*r*r/3; double pi=3.14; S=pi*r*r; V=4*S*r/3; 最適化 原則：プログラムは分かりやすく。後はコンパイラの最適化に任す。 しかし、処理時間のかかるプログラムでは、プログラマによる最適化の工夫（アルゴリズムの工夫も含む）が必要。

8 最適化とデフラグの関係は？ 最適化はプログラムの時間効率と領域効率を向上させるものということですが、コンパイルの最適化とディスクデフラグの最適化とは何か違う点があるのでしょうか ？ デフラグ：Defragmentationの略。　　 　　　　　　　　　　→　ディスク最適化とも言う。 記憶装置（ハードディスク）内のファイル（の記憶場所）を並べ替え、空き領域の断片化を最小にすること。 基本的には、コンパイルの最適化とは別物

9 ディスク・デフラグ

10 興味Ⅲ－コンパイラとインタプリタ①－ 今回の講義で、私が一番興味を持ったのが、コンパイラの場合とインタプリタの場合の実行結果までの流れの違いである。コンパイラもインタプリタも高水準プログラムを翻訳し、実行して結果を出すという作業であるが、コンパイラはデバックに時間はかかるが、実行速度が速いという特徴があり、インタプリタは逆にデバックには便利だが実行速度は遅いという特徴があるということであった。 　　　それを踏まえて、一見コンパイラの方が実行速度が速い分便利でいいじゃないかと思ったが、インタプリタはその分結果が出るまでの細かい作業を確認しながらできるという利点があることを聞いて、それぞれにちゃんとその時々の用途に分けて必要とされる要素があるのだととても感心した。

11 興味Ⅲ－コンパイラとインタプリタ②－ 今回の講義で興味を持ったのは、コンパイラとインタプリタの違いです。まず、コンパイラとインタプリタの違いとは、ただ機械語に変換する際に、動作がひとつひとつ区切って行うか、一度にすべて行ってしまうかの違いだけと思っており、動作内容自体は、まったく同じことを行っていると思っていた。そして、どちらかというと、インタプリタのほうが、実行速度が速いと思っていた。 コンパイラは、全訳した文を読み上げる事に対応。 インタプリタは同時通訳に対応。

12 興味Ⅲ－コンパイラとインタプリタ③－ 今回の講義で興味を持ったことは、コンパイラとインタプリタです。コンパイラではデバックに手間がかかるが、実行速度が速いという点が、インタプリタではデバックには便利だが、実行速度が遅いという点がある。この場合、どちらのほうがいいのだろうか。たいていは、使用目的で変えるのだろうが、コンパイラとインタプリタはどういう風に使い分けられているのだろうか。 コンパイラとインタプリタではどちらが主流なのか気になった。 インタプリタ→　BASICで導入（デバッグの有利さを優先）。その他、 Prologや JavaScript、Perl（パール）などで採用。 コンパイラ→　その他のほとんど全ての言語で採用

13 感想 普段JBuilderなどで打っている字句がこのような意味をもっているとは知らなかったので、この字句（の意味）を踏まえてプログラムを打つと理解するのが速くなるのではないでしょうか？最適化のたたきこみをみると非常にプログラムがわかりやすく感じました。プログラムを打つ場合こういう風に単純に考えれば結構できそうな気がしました。 理解するにはこういう処理などの過程を知ったほうがいいと思いました。 私は簡単なプログラミングの作業でもアルファベット一つ間違えただけで認識してくれないコンピュータに多々腹が立ちましたが、一文字一文字がきちんと意味を持ってるんだなという気がしました。 コンパイルの過程はプログラミングの理解に有益？

14 ＜本日のテーマ＞ 翻訳システム（コンパイラ）の数学理論 ＜内容＞ チューリング機械 オートマトン 形式文法とオートマトンの関係

15 計算可能とは？ チューリングの考え １９３７年 アラン・チューリング(Turing) 計算理論のモデルとしてチューリング機械を提唱
計算可能とは？　チューリングの考え １９３７年　アラン・チューリング(Turing)　計算理論のモデルとしてチューリング機械を提唱 計算とは（チューリングの考え） 　　紙に書かれた記号を読み、それに基本的な思考操作を加えて新しい記号を書く。→この操作の繰り返し チューリング機械 　　上の“計算”を機械的に実行するモデル→計算過程をある理想的な機械で表現→計算可能とはどういうことかを研究した。

16 チューリング機械 テープ、ヘッド、有限状態制御部 コンピュータの原型モデル チューリング機械の動作 ①ヘッドが見ている記号を書き換える
→　記憶装置 →　入出力装置 コンピュータの原型モデル →　CPU チューリング機械の動作 　　①ヘッドが見ている記号を書き換える 　　②ヘッドを左に動かす 　　③ヘッドを右に動かす 　　④計算を終了する

17 チューリング機械の例 アルゴリズムに対応！ 状態遷移関数で表現→計算可能 記号”0”を記号”1”に置き換える
有限状態制御部の規則（状態遷移関数） 　　(Q1,1)=(Q2,1,R)　 　　(Q2,B)=(Q2,B,L)　 　　(Q2,1)=(S,0,R) 　　Q1,Q2,S：状態 　　1,0,B：テープの記号 　　R,L：ヘッドの移動 アルゴリズムに対応！ １ B ･･･ Q1 １ B ･･･ Q2 １ B ･･･ Q2 ０ B ･･･ S 状態遷移関数で表現→計算可能

18 オートマトン オートマトン（automaton）
　元々は、人や動物のまねをする装置を指す→ロボット→自動計算機械のモデル→チューリング機械がその代表例 　情報科学では・・・ 状態遷移関数によって定義された操作を繰り返す仮想機械を指す。 状態遷移関数の種類によって色々なオートマトンを定義可能

19 有限オートマトン テープ、ヘッド、有限状態装置から構成 ヘッドは一方向のみ動く 有限オートマトンＭの定義 M=(Q,Σ,δ,q０,F)
　ヘッドは一方向のみ動く 有限オートマトンＭの定義 　M=(Q,Σ,δ,q０,F) 　Q:状態、Σ：入力記号、δ：状態遷移関数 　q0：初期状態、F：受理状態

20 有限オートマトンの例 Q={q0,q1,q2,}、 Σ={a,b}、 F={q2} δ(q0,a)=q1, δ(q0,b)=q0 ,
･･･ 入力記号 受理状態 状態 Q={q0,q1,q2,}、　Σ={a,b}、　F={q2} 　δ(q0,a)=q1,　 δ(q0,b)=q0 , 　δ(q1,a)=q1,　 δ(q1,b)=q2 , 　δ(q2,a)=q1,　 δ(q2,b)=q0 入力記号“ab”が受理されるか？ 　δ(q0,ab)= δ(δ(q0,a),b)=δ(q1,b)=q2 入力記号”ba”は受理されるか？ 形式文法と似ている･･･？ 受理！ 受理されない！ δ(q0,ba)= δ(δ(q0,b),a)=δ(q0,a)=q1

21 形式言語理論との関係 言語の種類 受理するオートマトン 句構造文法言語 チューリング機械 文脈依存文法言語 線形有界オートマトン
文脈自由文法言語 プッシュダウンオートマトン 正規文法言語 有限オートマトン コンパイラ（+コンピュータ）→オートマトンの一種

22 オートマトンの考え 人間の計算（思考）過程→状態の変化 状態を記号で表現すれば→記号の変化規則を状態遷移関数で表現できる
状態遷移関数で、“思考”を数学的に表現できる。→言語も“思考”の一例 プログラミング言語も（適当な状態遷移関数を定義できれば）コンピュータ（オートマトン）で理解（解読）可能 計算可能な問題はコンピュータで全て処理可能

23 ALGOL60プロジェクトの背景 形式文法理論の誕生 チューリング機械に始まるオートマトン理論の発展 オートマトン理論と形式文法理論の融合
プログラミング言語理論の基礎が確立 　‘６０年代はコンパイラ開発の時代 ’70年代はプログラミング方法の研究へ

24 第５回目レポート 　＜　テーマ　＞　 ①あなたはコンパイルの過程を理解してからプログラミングを行った方が良いと思いますか？YesかNoを答えた上で、その理由（あなたの考え）を記述して下さい。 ②本日の講義で、あなたはどの様な点に最も興味を持ちましたか？そしてその理由は？それらをできる限り具体的に、200字～400字程度で記述して下さい。 なお、上の記述を行った上で,質問や以前のレポートに対するコメント等を付加しても結構です。 件名：「学籍番号（半角）+半角空白＋氏名」を記入して下さい。 　　　例）　s03xxxx 学院太郎

25 計算可能とは？ 例１）３３を求める。→計算可能 例２）３∞を求める。→計算不能 例３）フェルマーの定理
　　Ｘ１＝３ 　　Ｘ２＝３＊Ｘ１＝３＊３＝９ 　　Ｘ３＝３＊Ｘ２＝３＊９＝２７ 例２）３∞を求める。→計算不能 例３）フェルマーの定理　 　　方程式　Ｘｎ＋Ｙｎ＝Ｚｎ　（ｎ は３以上の自然数）を満たす自然数解（Ｘ，Ｙ，Ｚ）はない。→約350年間証明不能　→1995年に解決　→　計算可能な問題に！　 こういった個々の問題の証明ではなく、「一般に計算可能とはどういうことか？」と言う点を追求しようとした。 ＜チューリングのねらい＞

26 ３３の計算 ２進数で表すと・・・ Ｘ１＝３ Ｘ２＝３＊Ｘ１＝３＊３＝９ Ｘ３＝３＊Ｘ２＝３＊９＝２７ １ ０ １ ０ １ ０
　　　　　　　　　　　　　　　　２進数で表すと・・・ 　Ｘ１＝３　　　　　　　　　　　　　　　　 　Ｘ２＝３＊Ｘ１＝３＊３＝９　　　 　Ｘ３＝３＊Ｘ２＝３＊９＝２７　 １ ０ １ ０ １ ０ 適当な状態遷移関数を定義すればチューリング機械で計算できる。