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

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

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

2 レポート（5/12）総括 ＜ テーマ ＞ ＜興味を持った点＞ ＜レポートへのコメント＞ ＜感想＞ ＜質問＞
　＜　テーマ　＞　 本日の講義で、あなたが最も興味を持った点はどのような点ですか？講義の全体的な感想と共に、できる限り具体的に、200字～400字程度で記述して下さい。 　＜興味を持った点＞ 翻訳（コンパイル）の過程 最適化処理 Ｄ言語 ＜レポートへのコメント＞ 「プログラミング言語は簡単になっていない」という意見に同意が集まっています。→HPを参照して下さい。 　＜感想＞ エスペラント語について 　＜質問＞ 多数あり

3 興味１－コンパイルの過程－ 最も興味を持った点は、プログラムの実行までには色々なことをやっているところです。
その中でも、コンパイルの過程で字句解析、構文解析、意味解析では原始プログラムを字句に分解しその字句が文法的に正しいかをチェックしているとか、最適化ではプログラムの時間効率と領域効率を向上させるためにいろんな方法がとられていることを初めて知った。 普段は何気なくつかっているけど、プログラムの実行までにこういうことが行われているのはすごいと思った。

4 興味２－最適化－ 今日の講義の中で最も興味を持った点は、最適化についてです。ただひとこと「最適化」と言っても、演算回数を減らすのには実に様々な種類があり、一つ一つは時間・領域ともにほんの少しの節約にしかならなくとも、プログラムの内容が複雑になりソースが長くなれば長くなるほど効率を上げているのだなと思いました。（中略）人間が多少効率を悪く書いてしまったプログラムを、人間が考えたシステムによって直されるというのは面白いと思いました。 今まで最適化と言ってもただ簡単にその処理を簡単にすると言う1つの処理を行っているだけだと思っていたが、最適化の方法が色々あるのに、少々関心が持てた。たたみこみや共通式の置き換え、繰り返し文の再編、レジスタの割り付けの再編、式評価の変更、そしてサブルーチンの組み込みという処理全てをあわせて最適化なのだということがわかった。

5 興味３－Ｄ言語－ 今回の講義で一番興味を引いたのはC言語の続きのD言語なるものがあるという話でした、前回の講義ではまだ開発されていないと言っていたけど探すと意外に見つかるものなのだと思いました、しかし開発元が違うみたいなので一般に普及することは無いかなと思いました。 言語を作ってもこのように世間に知れ渡らないまま多くの言語が消えたのかと考えると言語開発の会社も大変だと思いました。そして多くの言語が作られていることからプログラム言語で出来ることはこれからどんどん増えていくんだと考えさせられるところでもありました。

6 感想－エスペラント語－ 講義の内容と、ちょっと外れたところまでサポートしていただいて、ありがとうございました。エスペラントについては少し調べたことがあるものの、「エスペラント博士が開発した」というのと言語本体を少々だけだったので、今日のお話が聞けてとても面白かったです。 質問の中にエスペラント語という世界共通の言語を目指した言語があると初めて知り驚きました。そして、その言語を作る動機として「諸民族の平和と共存」という大義を知り、考えさせられました。現状では世界の共通語として英語が使われていますが、やはりネイティブに分があるのは否めないと思ったからです。

7 質問１－コンパイラとインタプリタの融合－ コンパイラは翻訳と実行が分かれていて、デバッグに手間がかかるけど、実行速度が速いというメリットがあり、インタプリタは翻訳と実行が同時にでき、コンパイラとは逆にデバッグには便利だけど、実行速度が遅いというデメリットがあります。が、でもどうしてこの二つのメリットの部分だけを組み合わせた、もっと効率のいい翻訳と実行のプログラミングはないのでしょうか？ コンパイラはテバックに手間がかかるが、実行速度が速い。インプリンタはテバックには便利だが,実行速度は遅い。というように、それぞれにメリットとデメリットがあります。テバックに便利で、実行速度が速いというのは不可能なのですか？　 デバッガ機能を備えたコンパイラシステムが発達 　→　JBuilderもその一例 Javaのコンパイラ戦略

8 質問２－最適化－ 複雑なプログラムの中で最適化が行われていなかった場合の処理の速度と行われている場合の処理の速度ではどのくらいの差が出てくるのだろうと思いました。 人間が回りくどくプログラムしたとき(ソースを打ち込んだとき)に、その最適化したプログラムを目に見える形にして表示することはできないのでしょうか？そうしたら、「あ、ここで最適化が行われたんだ。」というのがよくわかり、次からはある程度人間自身が最適化して書き込むようになって、機械が最適化する時間が短縮されると思うのですが。

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

10 質問３－コンパイラのエラーメッセージ－ 私自身はコンパイルの時点でエラーになることが多いですが、コンパイラはどこまでエラーをだすのでしょうか？ ひょっとしたら、コンパイルできるエラーも存在するのではないかと思っています。たぶん、言語によっては厳しいものも安易なものもあると思いますが、そこはどうなのでしょうか？？ 去年の講義でも思いましたがプログラムを打って実行する際にエラーが発生して間違っている場所はわかりましたがこれをどのように修正したらよいかわかればな、とずっと思っていました。今後このような機能のついたソフトは登場するのでしょうか？

11 Delphi VS Java 言語によって文法エラーのレベルが異なる。 var a,b,c: Integer; begin a:=4;
c:=a/b; end; ← エラー ＜Delphi＞ int a,b,c; a=2; b=3; c=a/b; ＜Java＞ エラーなし！ 文法的に厳しい 皆は、どちらを好みますか？

12 JBuilderのエラーメッセージ 内容によっては、修正候補を示してくれている。

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

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

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

16 チューリング機械の例 記号”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 状態遷移関数で表現→計算可能

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

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

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

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

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

22 第５回目レポート 　＜　テーマ　＞　 本日の講義で、あなたが最も興味を持った点はどのような点ですか？講義の全体的な感想と共に、できる限り具体的に、200字～400字程度で記述して下さい。 なお、上の記述を行った上で,質問や以前のレポートに対するコメント等を付加しても結構です。 件名：「学籍番号（半角）+半角空白＋氏名」を記入して下さい。 　　　例）　s02xxx 学院太郎

23 Javaのコンパイラ戦略 Java言語の翻訳は２段階 Java言語プログラム Javaコンパイラ
コンパイラとインタプリタの併用 Java言語プログラム Javaコンパイラ Javaバイトコード（CPUやOSによらず共通） Javaインタプリタ（Windows） Javaインタプリタ（UNIX） Javaインタプリタ（MacOS） プログラムの実行 高い互換性（移植性）を実現 機械語ではない！