比較プログラム言語論

比較プログラム言語論
平成１７年５月１８日
森田彦
レポート（5/11）総括
＜テーマ＞

本日の講義で、あなたはどの様な点に最も興味を持ちました
か？そしてその理由は？それらをできる限り具体的に、200
字～400字程度で記述して下さい。
＜興味を持った点＞



コンパイルの過程（流れ）
最適化
コンパイラとインタプリタ
＜感想＞

コンパイルの過程を理解してからプログラミングを行った方が
良い？
興味Ⅰ－コンパイルの過程①－
今回の講義で最も興味を持ったのはプログラムの実
行のながれです。プログラム実行と言っても内部では
いくつもの工程を経て実行されていることがわかった
からです。特にその工程の中にある翻訳（コンパイ
ル）ですが、単に構文を解析するだけではなく、プログ
ラムの無駄な部分を最適化することによって処理時
間の短縮や容量の縮小などの向上を図っている重要
な工程であることを知りました。今までJBuilderで何気
なくプログラムの実行を行っていましたが、その中でも
最適化が行われていたことは知りませんでした。
興味Ⅰ－コンパイルの過程②－


私が今日の講義で興味を持ったことは、コンパイルの過程で
す。入力された原始プログラムから一句一句の字句に分解
していることははじめて知りました。いっぺんに処理している
と思っていたのでコンピュータというのは何を処理するにも分
解してから、効率を上げるための最適化と同じように、簡略
化してからひとつひとつ処理していくものなのだと思いました。
今日の講義で一番興味を持った事は、コンパイルの過程で
す。字句・構文・意味の解析や、最適化などの面倒な作業を、
人間に代わってコンピュータが自動でやってくれるし、こちら
の方に間違いがない限りその結果に間違いが生じないとい
うのも、一見当たり前のようですが実はすごい事だと思いま
す。
興味Ⅱ－最適化①－

今日の講義では『コンパイルの過程』に興味を持ち
ました。その中でも『最適化』です。プログラミングを
するときに何気なく書いているもの、たたきこみ、共
通式に置換等。コンパイラにそんな機能があるとは
知りませんでした。あらかじめたたきこみ等を使用し
てプログラミングしなくても結局は同じ速さで処理を
するプログラムが出来るのですね。小さなプログラ
ムならたいして関係ないのでしょうが、大きなプログ
ラムであらかじめ最適化されたもの、してないもの
だとどのぐらいコンパイルに時間がかかるのかふと
気になりました。
興味Ⅱ－最適化②－

今までどれがうまいプログラミングコードでどれが冗
長なプログラミングコードかが、いまいちピンときま
せんでした。ただ文字列をそろえて見やすければい
いのかな、といった程度のことでした。しかし、この
最適化の「共通式の置換」「サブルーチンの組み込
み」を見て、なるほどと思いました。（中略）・・・プロ
グラミングの時間、領域の効率化を図る。それが出
来ているコードがうまいプログラミングなんだと実感
しました。
＜質問＞
最適化によるメリットは理解できましたが、最適化された後の
デメリットも詳しく知りたいと思いました。
最適化と分かりやすさについて

無駄な処理をなくすことは必要

しかし、一般に最適化を進めるとプログラムの処理
内容が分かりにくくなる。
＜例＞半径ｒの円の面積Ｓと球の体積Ｖを求める場合
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;
原則：プログラムは分かりやすく。後はコンパイラの最適化に任す。
しかし、処理時間のかかるプログラムでは、プログラマによる最適化の
工夫（アルゴリズムの工夫も含む）が必要。
最適化とデフラグの関係は？

最適化はプログラムの時間効率と領域効率
を向上させるものということですが、コンパイ
ルの最適化とディスクデフラグの最適化とは
何か違う点があるのでしょうか？
デフラグ：Defragmentationの略。
→ ディスク最適化とも言う。
記憶装置（ハードディスク）内のファイル（の記憶場所）を
並べ替え、空き領域の断片化を最小にすること。
基本的には、コンパイルの最適化とは別物
ディスク・デフラグ
興味Ⅲ－コンパイラとインタプリタ①－

今回の講義で、私が一番興味を持ったのが、コンパイラの場
合とインタプリタの場合の実行結果までの流れの違いである。
コンパイラもインタプリタも高水準プログラムを翻訳し、実行
して結果を出すという作業であるが、コンパイラはデバックに
時間はかかるが、実行速度が速いという特徴があり、インタ
プリタは逆にデバックには便利だが実行速度は遅いという特
徴があるということであった。
それを踏まえて、一見コンパイラの方が実行速度が速い
分便利でいいじゃないかと思ったが、インタプリタはその分結
果が出るまでの細かい作業を確認しながらできるという利点
があることを聞いて、それぞれにちゃんとその時々の用途に
分けて必要とされる要素があるのだととても感心した。
興味Ⅲ－コンパイラとインタプリタ②－

今回の講義で興味を持ったのは、コンパイラとイン
タプリタの違いです。まず、コンパイラとインタプリタ
の違いとは、ただ機械語に変換する際に、動作がひ
とつひとつ区切って行うか、一度にすべて行ってし
まうかの違いだけと思っており、動作内容自体は、
まったく同じことを行っていると思っていた。そして、
どちらかというと、インタプリタのほうが、実行速度が
速いと思っていた。
コンパイラは、全訳した文を読み上げる事に対応。
インタプリタは同時通訳に対応。
興味Ⅲ－コンパイラとインタプリタ③－


今回の講義で興味を持ったことは、コンパイラとインタプリタ
です。コンパイラではデバックに手間がかかるが、実行速度
が速いという点が、インタプリタではデバックには便利だが、
実行速度が遅いという点がある。この場合、どちらのほうが
いいのだろうか。たいていは、使用目的で変えるのだろうが、
コンパイラとインタプリタはどういう風に使い分けられている
のだろうか。
コンパイラとインタプリタではどちらが主流なのか気になった。
インタプリタ→ BASICで導入（デバッグの有利さを優先）。
その他、 Prologや JavaScript、Perl（パール）などで採用。
コンパイラ→ その他のほとんど全ての言語で採用
感想


普段JBuilderなどで打っている字句がこのような意味
をもっているとは知らなかったので、この字句（の意
味）を踏まえてプログラムを打つと理解するのが速く
なるのではないでしょうか？最適化のたたきこみを
みると非常にプログラムがわかりやすく感じました。
プログラムを打つ場合こういう風に単純に考えれば
結構できそうな気がしました。理解するにはこういう
処理などの過程を知ったほうがいいと思いました。
私は簡単なプログラミングの作業でもアルファベット
一つ間違えただけで認識してくれないコンピュータ
に多々腹が立ちましたが、一文字一文字がきちんと
意味を持ってるんだなという気がしました。
コンパイルの過程はプログラミングの理解に有益？
＜本日のテーマ＞
翻訳システム（コンパイラ）の数学理論
＜内容＞



チューリング機械
オートマトン
形式文法とオートマトンの関係
計算可能とは？チューリングの考え



１９３７年アラン・チューリング(Turing) 計算理論の
モデルとしてチューリング機械を提唱
計算とは（チューリングの考え）
紙に書かれた記号を読み、それに基本的な思考操
作を加えて新しい記号を書く。→この操作の繰り返し
チューリング機械
上の“計算”を機械的に実行するモデル→計算過程
をある理想的な機械で表現→計算可能とはどういう
ことかを研究した。
チューリング機械

テープ、ヘッド、有限状態制御部
ヘッド
制御部

テープ → 記憶装置
→ 入出力装置
→ CPU
チューリング機械の動作
①ヘッドが見ている記号を書き換える
②ヘッドを左に動かす
③ヘッドを右に動かす
④計算を終了する
コンピュータの
原型モデル
チューリング機械の例


記号”0”を記号”1”に置き換える
有限状態制御部の規則（状態遷移関数）
(Q1,1)=(Q2,1,R)
１ B B ･･･
(Q2,B)=(Q2,B,L) アルゴリズム
に対応！
(Q2,1)=(S,0,R)
Q1
Q1,Q2,S：状態
1,0,B：テープの記号
１ B B ･･･
R,L：ヘッドの移動
０ B B ･･･
S
Q2
１ B B ･･･
Q2
状態遷移関数で表現→計算可能
オートマトン
オートマトン（automaton）
元々は、人や動物のまねをする装置を指す→
ロボット→自動計算機械のモデル→チューリ
ング機械がその代表例
情報科学では・・・
 状態遷移関数によって定義された操作を繰り
返す仮想機械を指す。
 状態遷移関数の種類によって色々なオートマ
トンを定義可能

有限オートマトン
テープ、ヘッド、有限状態装置から構成
ヘッドは一方向のみ動く
 有限オートマトンＭの定義
M=(Q,Σ,δ,q０,F)
Q:状態、Σ：入力記号、δ：状態遷移関数
q0：初期状態、F：受理状態

有限オートマトンの例
状態
入力記号
受理状態
a b ･･･
Q
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
形式言語理論との関係
言語の種類
受理するオートマトン
句構造文法言語
チューリング機械
文脈依存文法言語
線形有界オートマトン
文脈自由文法言語
プッシュダウンオートマトン
正規文法言語
有限オートマトン
コンパイラ（+コンピュータ）→オートマトンの一種
オートマトンの考え


人間の計算（思考）過程→状態の変化
状態を記号で表現すれば→記号の変化規則
を状態遷移関数で表現できる

状態遷移関数で、“思考”を数学的に表現で
きる。→言語も“思考”の一例

プログラミング言語も（適当な状態遷移関数
を定義できれば）コンピュータ（オートマトン）
で理解（解読）可能

計算可能な問題はコンピュータで全て処理可
能
ALGOL60プロジェクトの背景

形式文法理論の誕生

チューリング機械に始まるオートマトン理論の
発展
オートマトン理論と形式文法理論の融合
プログラミング言語理論の基礎が確立


‘６０年代はコンパイラ開発の時代
’70年代はプログラミング方法の研究へ
第５回目レポート
＜テーマ＞
①あなたはコンパイルの過程を理解してからプログラ
ミングを行った方が良いと思いますか？YesかNoを
答えた上で、その理由（あなたの考え）を記述して下
さい。
②本日の講義で、あなたはどの様な点に最も興味を
持ちましたか？そしてその理由は？それらをできる
限り具体的に、200字～400字程度で記述して下さい。
 なお、上の記述を行った上で,質問や以前のレポート
に対するコメント等を付加しても結構です。
 提出先：[email protected]
 件名：「学籍番号（半角）+半角空白＋氏名」を記
入して下さい。
例） s03xxxx 学院太郎
計算可能とは？

例１）３３を求める。→計算可能
Ｘ１＝３
Ｘ２＝３＊Ｘ１＝３＊３＝９
Ｘ３＝３＊Ｘ２＝３＊９＝２７


例２）３∞を求める。→計算不能
例３）フェルマーの定理
方程式Ｘｎ＋Ｙｎ＝Ｚｎ（ｎは３以上の自然数）を満たす自然
数解（Ｘ，Ｙ，Ｚ）はない。→約350年間証明不能 →1995年に
解決 → 計算可能な問題に！＜チューリングのねらい＞
こういった個々の問題の証明ではなく、「一般に計算可能とはど
ういうことか？」と言う点を追求しようとした。
３３の計算
２進数で表すと・・・
Ｘ１＝３
Ｘ２＝３＊Ｘ１＝３＊３＝９
Ｘ３＝３＊Ｘ２＝３＊９＝２７
１０
１００１
１１０１１
適当な状態遷移関数を定義すればチューリング
機械で計算できる。

Download Report