比較プログラム言語論

比較プログラム言語論
平成１６年５月１９日
森田彦
レポート（5/12）総括
＜テーマ＞

本日の講義で、あなたが最も興味を持った点はどのような点
ですか？講義の全体的な感想と共に、できる限り具体的に、
200字～400字程度で記述して下さい。
＜興味を持った点＞



翻訳（コンパイル）の過程
最適化処理
Ｄ言語
＜感想＞

エスペラント語について
＜質問＞

多数あり
＜レポートへのコメント＞
「プログラミング言語は簡単になって
いない」という意見に同意が集まっ
ています。→HPを参照して下さい。
興味１－コンパイルの過程－
最も興味を持った点は、プログラムの実行まで
には色々なことをやっているところです。
その中でも、コンパイルの過程で字句解析、構
文解析、意味解析では原始プログラムを字句
に分解しその字句が文法的に正しいかをチェッ
クしているとか、最適化ではプログラムの時間
効率と領域効率を向上させるためにいろんな
方法がとられていることを初めて知った。
普段は何気なくつかっているけど、プログラム
の実行までにこういうことが行われているのは
すごいと思った。
興味２－最適化－
今日の講義の中で最も興味を持った点は、最適化についてで
す。ただひとこと「最適化」と言っても、演算回数を減らすのに
は実に様々な種類があり、一つ一つは時間・領域ともにほんの
少しの節約にしかならなくとも、プログラムの内容が複雑になり
ソースが長くなれば長くなるほど効率を上げているのだなと思
いました。（中略）人間が多少効率を悪く書いてしまったプログ
ラムを、人間が考えたシステムによって直されるというのは面
白いと思いました。
今まで最適化と言ってもただ簡単にその処理を簡単にすると
言う1つの処理を行っているだけだと思っていたが、最適化の
方法が色々あるのに、少々関心が持てた。たたみこみや共通
式の置き換え、繰り返し文の再編、レジスタの割り付けの再編、
式評価の変更、そしてサブルーチンの組み込みという処理全
てをあわせて最適化なのだということがわかった。
興味３－Ｄ言語－
今回の講義で一番興味を引いたのはC言語の続きの
D言語なるものがあるという話でした、前回の講義で
はまだ開発されていないと言っていたけど探すと意外
に見つかるものなのだと思いました、しかし開発元が
違うみたいなので一般に普及することは無いかなと思
いました。
言語を作ってもこのように世間に知れ渡らないまま多
くの言語が消えたのかと考えると言語開発の会社も
大変だと思いました。そして多くの言語が作られてい
ることからプログラム言語で出来ることはこれからど
んどん増えていくんだと考えさせられるところでもあり
ました。
感想－エスペラント語－


講義の内容と、ちょっと外れたところまでサポートし
ていただいて、ありがとうございました。エスペラント
については少し調べたことがあるものの、「エスペラ
ント博士が開発した」というのと言語本体を少々だけ
だったので、今日のお話が聞けてとても面白かった
です。
質問の中にエスペラント語という世界共通の言語を
目指した言語があると初めて知り驚きました。そして、
その言語を作る動機として「諸民族の平和と共存」と
いう大義を知り、考えさせられました。現状では世界
の共通語として英語が使われていますが、やはりネ
イティブに分があるのは否めないと思ったからです。
質問１－コンパイラとインタプリタの融合－


コンパイラは翻訳と実行が分かれていて、デバッグに手間が
かかるけど、実行速度が速いというメリットがあり、インタプリ
タは翻訳と実行が同時にでき、コンパイラとは逆にデバッグ
には便利だけど、実行速度が遅いというデメリットがあります。
が、でもどうしてこの二つのメリットの部分だけを組み合わせ
た、もっと効率のいい翻訳と実行のプログラミングはないの
でしょうか？
コンパイラはテバックに手間がかかるが、実行速度が速い。
インプリンタはテバックには便利だが,実行速度は遅い。とい
うように、それぞれにメリットとデメリットがあります。テバック
に便利で、実行速度が速いというのは不可能なのですか？
デバッガ機能を備えたコンパイラシステムが発達
→ JBuilderもその一例
Javaのコンパイラ戦略
質問２－最適化－


複雑なプログラムの中で最適化が行われていな
かった場合の処理の速度と行われている場合の処
理の速度ではどのくらいの差が出てくるのだろうと
思いました。
人間が回りくどくプログラムしたとき(ソースを打ち込
んだとき)に、その最適化したプログラムを目に見え
る形にして表示することはできないのでしょうか？そ
うしたら、「あ、ここで最適化が行われたんだ。」とい
うのがよくわかり、次からはある程度人間自身が最
適化して書き込むようになって、機械が最適化する
時間が短縮されると思うのですが。
最適化と分かりやすさについて

無駄な処理をなくすことは必要

しかし、一般に最適化を進めるとプログラムの処理
内容が分かりにくくなる。
＜例＞半径ｒの円の面積Ｓと球の体積Ｖを求める場合
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;
原則：プログラムは分かりやすく。後はコンパイラの最適化に任す。
しかし、処理時間のかかるプログラムでは、プログラマによる最適化の
工夫（アルゴリズムの工夫も含む）が必要。
質問３－コンパイラのエラーメッセージ－


私自身はコンパイルの時点でエラーになることが多
いですが、コンパイラはどこまでエラーをだすので
しょうか？ひょっとしたら、コンパイルできるエラーも
存在するのではないかと思っています。たぶん、言
語によっては厳しいものも安易なものもあると思い
ますが、そこはどうなのでしょうか？？
去年の講義でも思いましたがプログラムを打って実
行する際にエラーが発生して間違っている場所はわ
かりましたがこれをどのように修正したらよいかわ
かればな、とずっと思っていました。今後このような
機能のついたソフトは登場するのでしょうか？
Delphi VS Java
言語によって文法エラーのレベルが異なる。
＜Delphi＞
＜Java＞
var
a,b,c: Integer;
begin
a:=4;
b:=2;
c:=a/b; ← エラー
end;
文法的に厳しい
int a,b,c;
a=2;
b=3;
c=a/b; エラーなし！
皆は、どちらを好みますか？
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：受理状態

有限オートマトンの例
Q={q1,q2,q3}、Σ={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年代はプログラミング方法の研究へ
第５回目レポート
＜テーマ＞
 本日の講義で、あなたが最も興味を持った点はどの
ような点ですか？講義の全体的な感想と共に、でき
る限り具体的に、200字～400字程度で記述して下さ
い。
 なお、上の記述を行った上で,質問や以前のレポート
に対するコメント等を付加しても結構です。
 提出先：[email protected]
 件名：「学籍番号（半角）+半角空白＋氏名」を記
入して下さい。
例） s02xxx 学院太郎
Javaのコンパイラ戦略

Java言語の翻訳は２段階
Java言語プログラム
Javaコンパイラ
機械語ではない！
コンパイラとインタプリ
タの併用
高い互換性（移植
性）を実現
Javaバイトコード（CPUやOSによらず共通）
Javaインタプリタ
（Windows）
Javaインタプリタ
（UNIX）
プログラムの実行
Javaインタプリタ
（MacOS）

Download Report