比較プログラム言語論
平成17年5月18日
森田 彦
レポート(5/11)総括
< テーマ >

本日の講義で、あなたはどの様な点に最も興味を持ちました
か?そしてその理由は?それらをできる限り具体的に、200
字~400字程度で記述して下さい。
<興味を持った点>



コンパイルの過程(流れ)
最適化
コンパイラとインタプリタ
<感想>

コンパイルの過程を理解してからプログラミングを行った方が
良い?
興味Ⅰ-コンパイルの過程①-
今回の講義で最も興味を持ったのはプログラムの実
行のながれです。プログラム実行と言っても内部では
いくつもの工程を経て実行されていることがわかった
からです。特にその工程の中にある翻訳(コンパイ
ル)ですが、単に構文を解析するだけではなく、プログ
ラムの無駄な部分を最適化することによって処理時
間の短縮や容量の縮小などの向上を図っている重要
な工程であることを知りました。今までJBuilderで何気
なくプログラムの実行を行っていましたが、その中でも
最適化が行われていたことは知りませんでした。
興味Ⅰ-コンパイルの過程②-


私が今日の講義で興味を持ったことは、コンパイルの過程で
す。入力された原始プログラムから一句一句の字句に分解
していることははじめて知りました。いっぺんに処理している
と思っていたのでコンピュータというのは何を処理するにも分
解してから、効率を上げるための最適化と同じように、簡略
化してからひとつひとつ処理していくものなのだと思いました。
今日の講義で一番興味を持った事は、コンパイルの過程で
す。 字句・構文・意味の解析や、最適化などの面倒な作業を、
人間に代わってコンピュータが自動でやってくれるし、こちら
の方に間違いがない限りその結果に間違いが生じないとい
うのも、一見当たり前のようですが実はすごい事だと思いま
す。
興味Ⅱ-最適化①-

今日の講義では『コンパイルの過程』に興味を持ち
ました。その中でも『最適化』です。プログラミングを
するときに何気なく書いているもの、たたきこみ、共
通式に置換等。コンパイラにそんな機能があるとは
知りませんでした。あらかじめたたきこみ等を使用し
てプログラミングしなくても結局は同じ速さで処理を
するプログラムが出来るのですね。小さなプログラ
ムならたいして関係ないのでしょうが、大きなプログ
ラムであらかじめ最適化されたもの、してないもの
だとどのぐらいコンパイルに時間がかかるのかふと
気になりました。
興味Ⅱ-最適化②-

今までどれがうまいプログラミングコードでどれが冗
長なプログラミングコードかが、いまいちピンときま
せんでした。ただ文字列をそろえて見やすければい
いのかな、といった程度のことでした。しかし、この
最適化の「共通式の置換」「サブルーチンの組み込
み」を見て、なるほどと思いました。(中略)・・・プロ
グラミングの時間、領域の効率化を図る。それが出
来ているコードがうまいプログラミングなんだと実感
しました。
<質問>
最適化によるメリットは理解できましたが、最適化された後の
デメリットも詳しく知りたいと思いました。
最適化と分かりやすさについて

無駄な処理をなくすことは必要

しかし、一般に最適化を進めるとプログラムの処理
内容が分かりにくくなる。
<例>半径rの円の面積Sと球の体積Vを求める場合
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などで打っている字句がこのような意味
をもっているとは知らなかったので、この字句(の意
味)を踏まえてプログラムを打つと理解するのが速く
なるのではないでしょうか?最適化のたたきこみを
みると非常にプログラムがわかりやすく感じました。
プログラムを打つ場合こういう風に単純に考えれば
結構できそうな気がしました。 理解するにはこういう
処理などの過程を知ったほうがいいと思いました。
私は簡単なプログラミングの作業でもアルファベット
一つ間違えただけで認識してくれないコンピュータ
に多々腹が立ちましたが、一文字一文字がきちんと
意味を持ってるんだなという気がしました。
コンパイルの過程はプログラミングの理解に有益?
<本日のテーマ>
翻訳システム(コンパイラ)の数学理論
<内容>



チューリング機械
オートマトン
形式文法とオートマトンの関係
計算可能とは? チューリングの考え



1937年 アラン・チューリング(Turing) 計算理論の
モデルとしてチューリング機械を提唱
計算とは(チューリングの考え)
紙に書かれた記号を読み、それに基本的な思考操
作を加えて新しい記号を書く。→この操作の繰り返し
チューリング機械
上の“計算”を機械的に実行するモデル→計算過程
をある理想的な機械で表現→計算可能とはどういう
ことかを研究した。
チューリング機械

テープ、ヘッド、有限状態制御部
ヘッド
制御部

テープ → 記憶装置
→ 入出力装置
→ CPU
チューリング機械の動作
①ヘッドが見ている記号を書き換える
②ヘッドを左に動かす
③ヘッドを右に動かす
④計算を終了する
コンピュータの
原型モデル
チューリング機械の例


記号”0”を記号”1”に置き換える
有限状態制御部の規則(状態遷移関数)
(Q1,1)=(Q2,1,R)
1 B B ・・・
(Q2,B)=(Q2,B,L) アルゴリズム
に対応!
(Q2,1)=(S,0,R)
Q1
Q1,Q2,S:状態
1,0,B:テープの記号
1 B B ・・・
R,L:ヘッドの移動
0 B B ・・・
S
Q2
1 B B ・・・
Q2
状態遷移関数で表現→計算可能
オートマトン
オートマトン(automaton)
元々は、人や動物のまねをする装置を指す→
ロボット→自動計算機械のモデル→チューリ
ング機械がその代表例
情報科学では・・・
 状態遷移関数によって定義された操作を繰り
返す仮想機械を指す。
 状態遷移関数の種類によって色々なオートマ
トンを定義可能

有限オートマトン
テープ、ヘッド、有限状態装置から構成
ヘッドは一方向のみ動く
 有限オートマトンMの定義
M=(Q,Σ,δ,q0,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プロジェクトの背景

形式文法理論の誕生

チューリング機械に始まるオートマトン理論の
発展
オートマトン理論と形式文法理論の融合
プログラミング言語理論の基礎が確立


‘60年代はコンパイラ開発の時代
’70年代はプログラミング方法の研究へ
第5回目レポート
< テーマ >
①あなたはコンパイルの過程を理解してからプログラ
ミングを行った方が良いと思いますか?YesかNoを
答えた上で、その理由(あなたの考え)を記述して下
さい。
②本日の講義で、あなたはどの様な点に最も興味を
持ちましたか?そしてその理由は?それらをできる
限り具体的に、200字~400字程度で記述して下さい。
 なお、上の記述を行った上で,質問や以前のレポート
に対するコメント等を付加しても結構です。
 提出先:[email protected]
 件名:「学籍番号(半角)+半角空白+氏名」を記
入して下さい。
例) s03xxxx 学院太郎
計算可能とは?

例1)33を求める。→計算可能
X1=3
X2=3*X1=3*3=9
X3=3*X2=3*9=27


例2)3∞を求める。→計算不能
例3)フェルマーの定理
方程式 Xn+Yn=Zn (n は3以上の自然数)を満たす自然
数解(X,Y,Z)はない。→約350年間証明不能 →1995年に
解決 → 計算可能な問題に! <チューリングのねらい>
こういった個々の問題の証明ではなく、「一般に計算可能とはど
ういうことか?」と言う点を追求しようとした。
33の計算
2進数で表すと・・・
X1=3
X2=3*X1=3*3=9
X3=3*X2=3*9=27
1 0
1 0 0 1
1 1 0 1 1
適当な状態遷移関数を定義すればチューリング
機械で計算できる。
ダウンロード

講義スライド