本文へジャンプ

学科概要
  • HOME
  • 学科概要
  • 学生による学科紹介

学生による学科紹介

3年生夏学期

言語処理系論 | 細谷 晴夫
開講時間:木曜2限 | 必修科目
シラバス
コンパイラを含む言語処理系の構築のための理論と技術を学ぶ。古典的技法である構文解析、コード生成、最適化などを網羅し、より現代的な関数型言語やオブジェクト指向言語の実装技術、ガべージコレクションなどにも触れる。
概要
この講義では、コンパイラを作成するためのノウハウについて学びます。実際的なコンパイラで用いられている構文解析や最適化の方法およびそのための知識を習得することが目標です。ここで学んだ知識は、主に6学期のCPU実験で生かされることになります。CPU実験では、CPUのアーキテクチャを構成するだけでなく、そのアーキテクチャのためのコンパイラを作成することも課題の一つとなっているからです。
授業の内容について
コンパイラとは、人間が書いたプログラミング言語をコンピュータが直接理解できる機械語に翻訳するプログラムのことです。すなわち、プログラムのソースコードを読んでそれを解釈し、機械語の命令列に変換するのがコンパイラの仕事です。授業では、ソースコードを読み込んで機械を出力するまでに一般的なコンパイラが行う作業のほとんどを、実際にコンパイラが処理を行うのとほぼ同じ順番で扱ってゆきます。

コンパイラが最初に行う作業は、プログラミング言語で書かれたコードを読み込んでそれを文法的に解釈することです。ここで、4学期に形式言語理論で学んだ正規文法や文脈自由文法というものが登場します。

まずコンパイラはコードを字句に分解します。これは「本日は晴天なり」という日本語を「本日」「は」「晴天」「なり」という四つの単語に分けるようなものです。多くのコンパイラはこの作業を正規文法に基づいて行います。予め定義された正規文法に合致する部分をそれぞれ字句として取出すのです。これは形式言語理論で学んだオートマトンの理論を用いれば難しいことではないので、授業でもあまり深くは触れられません。

次にコンパイラが行うのは、構文解析です。上の日本語の例でたとえるなら、「本日」「晴天」が名詞であることとか、「本日は」が主語で「晴天なり」が述語であることなどを見分けることだといえます。この作業は、字句の列を文脈自由文法に当てはめてゆく作業になりますが、字句解析よりもはるかに難しいものです。これは、字句解析で用いられている正規文法よりも、構文解析で用いる文脈自由文法の方がより複雑な文法を定義できるというところによります。

形式言語理論では、文脈自由文法を解釈するアルゴリズムとしてCYKアルゴリズムというものを習いますが、実際のコンパイラは構文解析にこのアルゴリズムを使いません。というのも、このアルゴリズムは時間が掛かりすぎるのです。そのため、より速く解析できるように制限を加えた文脈自由文法を使います。授業では、文法にどのような制限を加えるか、そしてそれをどのようなアルゴリズムで解析するかについて、詳しく述べられます。すなわち、構文解析はこの授業のメインテーマの一つとなります。

さて、構文解析が済んだら、コンパイラは型チェックなどを含む意味解析を行った後、プログラムを中間コードというものに変換します。中間コードとは、その名のとおり元のプログラミング言語と機械語との中間に位置する言語です。そして、コンパイラはこの中間コードに対して最適化という作業を行います。

最適化とは、コンピュータができるだけ効率的に処理を行うように、コードを書き換えることです。例えば、「ここは同じ計算を何度も繰り返しているけど最初に一回だけ計算すれば済むよね」とか「この値は結局後で使われないからそもそも計算しなくていいよね」というようなことをコンパイラが判断して、コードを書き換えるのです。授業では、実際に使われている代表的な最適化技法をいくつか紹介し、それの元になっている理論について説明されます。これがこの授業のもう一つのメインテーマです。

上に「後で使われない値は計算しない」という例を挙げましたが、ある値が結局使われないことをコンパイラはどのようにして知ることが出来るのでしょうか。それを知るためには、どの値がどこで使われているのかを解析しなくてはなりません。これは、値の使われ方を示すデータフロー方程式を立てて解くことで求めます。すなわち、この最適化技法はデータフロー方程式の理論に基づいているわけです。

授業では、このような最適化技法のための理論として、他にループの帰納変数や上位関係について述べられます。

最適化が終わったら、コンパイラの最後の仕事は中間言語を機械語に変換することです。ここでも、効率の良い機械語を出力するための技法が存在します。例えば、複数の中間コード命令を一つの機械語命令に変換できる場合にどのように変換するのがもっとも効率的かとか、CPUのどのレジスタにどの値を入れるのがもっとも効率的かとかいったことがあります。

以上が大まかな授業内容です。理論的な話は多いですが、どれも実際にコンパイラを作るために応用されている理論なので、形式言語理論は抽象的な話ばかりでつまらないと感じていた人も、ここで言語理論が実際に使われている様を見ることができるでしょう。
授業の進行
授業では資料や教材などはほとんど配られないので、各々まじめにノートを取る必要があります。

10000円もする分厚い教科書がありますが、授業で直接教科書を参照することはありません。とはいえ授業で触れられないこともたくさん載っているので、CPU実験でコンパイラ係をやる人やコンパイラ作成に興味がある人にとっては必需品です。

月に一回程度、レポート課題が出ます。課題内容は過去の期末試験問題から指定された問題を解いて提出するというものです。習ったことがらを確認するための良い演習となります。(コンパイラに関する演習科目は5学期にはなく、CPU実験の一環として6学期に行われます)
試験について
試験問題は割りとシンプルで、主に用語の定義やアルゴリズムを書かせる問題や、実際に簡単なデータフロー方程式等を解かせる問題などが出ます。難しくはありませんが、授業でやったことをきちんと覚えていないと解けない問題です。
次のステップへ
CPU実験でコンパイラ係をやる人にとっては、この授業で学んだことは大いに役に立つでしょう。もっとも、授業で紹介される最適化技法の数は限られているので、高性能のコンパイラを作ることを目指す人にはこの授業で習うことだけでは物足りないかもしれません。

一方コンパイラ係をやらない人にとってはこの授業で学んだ知識はすぐには役立たないかもしれませんが、形式言語理論や離散数学で学んだ理論が実際にどのように応用されているのかを知るための良い実例となるでしょう。
離散数学 | 今井浩
開講時間:火曜2限 | 必修科目
シラバス
離散数学(グラフ理論、線形計画法、マトロイド理論)、ならびに、離散数学的手法によるアルゴリズムの設計と解析、離散最適化法(最小木問題、最大流問題、割当問題)。
概要
 離散数学は三年生の夏学期、つまりこの学科の最初の学期に行われる必修の授業です。
これは文字どおり離散的な、連続でない対象を扱う数学です。例えば離散的な問題の例として、順列や組み合わせをしらみつぶしに調べる問題などは、コンピュータを用いて解くとよいのですが、その効率的な解法の設計や研究は重要です。というのは、ある問題を解く(コンピュータに解かせる)のに要する時間は解法の設計に大きく依存するからです。設計が悪いために解けるはずの問題が現実的な時間内に解けなくなることさえあります。
 この講義では離散数学とその手法を用いたアルゴリズムの設計や解析の初歩を学びます。
離散数学の例え話
**離散数学的問題の例 「巡回セールスマン問題」

  ―商品を売ろう。ある営業マンの今日の予定。

 -鈴木さん、田中さん、高橋さん、澤さんの4件のお宅にお邪魔し、商品のプレゼンテーションをしたいと思います。
 -会社から出発して4件のお宅を全て訪問し、出来るだけ早く会社に帰って来たいと思います(*1)
 -早く移動できるルートもあれば、ひどく時間がかかってしまうルートもあります。

どういう風に巡回すれば最も効率的か。各ルート毎に所要時間が分かっていて、図にすると以下のようになっているとします。

(* 画像 pict.GIF*)



 元来、このような問題は数学としては低級な問題とみなされてきました。全ての場合を網羅すれは必ず解けることがただちにわかるからです。ところが、

  訪問するのが、たった4件のお宅でも、

  (会社) → 1 → 2 → 3 → 4 → (会社) 

可能なルートは
 4! = 24
通りあります。訪問する場所が増えれば当然、可能なルートは階乗で増えていきます。コンピュータがいくら人間より高速に計算できるからといえ、たとえば話を世界規模に持っていって「100都市を巡回する」ように考えると、1秒間に10億個の順列を作り出せるコンピュータを用いても100億世紀以上かかってしまうことが単純計算でわかります。つまり、「全ての場合を網羅すれば解けるはずであるが、それが現実的に不可能」であるということです。

 このような状況、問題に対処する方法を数学的に考える。これも離散数学の分野です。
実はこの「巡回セールスマン問題」は難しく、問題の規模がある程度大きいときに現実的な時間内で厳密に解けるような方法(アルゴリズム)は発見されていません。ここでは解法のいくつかを紹介したいと思います。

 <近似的な解法の例> 欲張り法(Greedy Algorithm)

方針:現在地から次の目的地へ最もコストの掛からないルートを毎回選択。

コストの最小値だけを調べればよいので、総当りよりは圧倒的に早い。単純な方法。

 会社 → 澤さん → 高橋さん → 鈴木さん → 田中さん → 会社 (4.7時間)

 この問題では実は最適解です。

が、この方針は精度に関してはいくらでも悪くなります。(田中→会社間が10000時間かかるようになっていても、このアルゴリズムではここを選ばざるを得ません)
まとめ
巡回セールスマン問題を例にお話させて頂きましたが、この問題は離散数学の体系のなかでは「グラフ理論」という分類になります。この「グラフ理論」は現実への応用分野も実に広く、たとえばデッドロックの検出、コンピュータネットワーク(インターネット)の構造モデル化、はたまた集積回路の設計にまで役に立っています。
 また、これに限らず離散的な値を考えなければならない問題というのはあちこちにあり、線形計画問題、マトロイド、組み合わせ論などがあります。
線形計画問題
せっかくなので、もうひとつ、離散数学の問題を見てみましょう。

* 線形計画問題とは


最適化問題のひとつで、目的関数と制約条件がすべて線形関数で表せる問題を線形計画問題といいます。

問1 製品A,Bを生産するためには原料a,b,cが必要です。売却利益はAが3、Bが2です。各製品の生産に必要な原料の量と在庫は図のとおりとします。このとき、売却利益を最大にするためにはA,Bをどのように生産すればよいでしょうか?

A B 在庫

a 3 1 10.5
b 2 2 9
c 1 2 8


解説 この問題を定式化すると、以下のようになります。Aの生産単位をx、Bの生産単位をyとします。

目的関数
z = 3x + 2y
を、制約条件
3x + y <= 10.5
2x + 2y <= 9

x + 2y <= 8

の下で最大にするx,yとそのときのzの値を求めなさい。

今回のように変数が2つだけであれば、図を描いて交点を求めれば解を得ることが出来ます。

#図を挿入

しかし、製品の数が3つ以上になると図を描くのはほぼ不可能になります。授業ではそのような線形計画問題を解くための方法(線形計画法)を学びます。具体的なアルゴリズムは書きませんが、それを用いることで多変数の場合でも効率よく解を求めることが出来ます。


問2 製品A,B,C,Dを生産するためには原料a,b,c,d,eが必要です。売却利益はAが3、Bが2、Cが1、Dが2です。各製品の生産に必要な原料の量と在庫は図のとおりとします。このとき、売却利益を最大にするためにはA,B,C,Dをどのように生産すればよいでしょうか?

A B C D 在庫

a 3 1 1 2 10.5
b 2 2 0 2 9
c 1 2 1 0 8
d 3 1 2 1 10
e 1 1 2 1 7.5

解説 これでは図を書くことが出来ませんね。どう解くのかは授業でのお楽しみに!
離散数学の学習効果
授業では、コンピュータを使って解く数学的問題とそれに対する今日までに考えられてきた解法が多数紹介され、まず離散的な問題の類型と有名な手法を学ぶことが出来ます。学んだ解法はいざ自分がアルゴリズムを設計する時に利用できることがあり、またアルゴリズムの効率を評価するための基礎知識が身につきます。
授業の進行について(今井先生の場合)
先生の説明を聞きながら板書を書き取っていく形です。先生曰く、板書はスライドよりほどよく遅いので、その場で考えて理解していくとよいとのことです。内容は今井先生が本質的なところから犀利な論理を用いて語って下さいます。受講生の自習のためとして「証明は略証明を与える。各自完成させよ。」のような指示がよく出ます。ですから少し厳しめな印象をもつこともあると思いますが、努力してついていけば必ず力はつきます。
試験について
大問4〜6題程度で大体が授業で扱う問題だと思います。後半の授業で、試験問題の出題範囲を先生が詳しく教えてくださいます。例年ほぼ試験のみで成績が決まるようです。
次のステップへ
次の学期(つまり3年冬学期)の全く同じ時間帯に今井先生による「計算量理論」の講義があります。困難さの尺度を導入することで離散数学的問題を分類し、計算の時間空間効率の解析に特化した議論をします。
注釈
1 巡回セールスマン問題(Traveling Salesman Problem, TSP)
  本来は一度訪れた場所に二度訪問してはいけないというルールがある。
情報科学演習 I | 各教官
開講時間:金曜午後 | 必修科目
演習内容
離散数学、情報論理の演習。
概要
情報論理
離散数学
コンピュータではなく、「紙と鉛筆」による演習。
情報論理
僕は、「論理式の構成に関する帰納法によって命題を証明する」というのが面白かった。
よく一般にやるような帰納法と同じ雰囲気で、論理式に関する問題が、論理式の構成に関する帰納法で解けるのが面白かった

あとは、「シーケンスと計算」がパズルみたいな感じで好きだった。
この計算は、ひたすら書く量が多くて、ともかく、手が疲れる。
最近はキーボードしか使っていないのに、演習中に紙が配られ、それに鉛筆で式を書く。
頭の中で書きたいことがあっても、鉛筆で書くのに手が追いつかず、問題が終わったら手がだるかった。

あと、論理学演習は「その場で解く」というのもあるけど、前もって「まとめプリント」が配られており、授業では、一番最初に、小テストがあり、is にきて、初めて予習をさせられたが、この予習が、結構辛かった。
大学に入ってから予習したのは語学と、この論理学演習くらいである。

この授業で最終的にたどりつきたかったテーマは「ゲーデルの不完全性定理」のおおざっぱな議論であり、自分としては、なんとなく証明できた気になれて、嬉しかった。

この授業に関係する総合科目が、駒場にあって、1年かけて、やはり「ゲーデルの不完全性定理」について授業が行われる。自分はこれに前半だけでていたのだが、演習も、前半だけ、楽だった。
おそらく、通年で聞いていたら、もっと、授業が楽だったのかもしれない。
離散数学
グラフ理論や、最適化、線形計画法など。
自分たちの目標は、「線形計画問題くらいはとけるようにしてテストを受けよう」だった。

友達が、3年の後期にやる実験II でコンパイラを作るときに、「最適化」として、ここでやった、最大流最小カットを、いつのまにか実装していた。
おお、本当に、実際に、実装して、使い道があるんだということに、とても驚きました。

授業でやってるあいだは、理論として勉強してるだけだったが、、、友達に感謝♪です。

思い出としては、森山さんが、問題の解説をしているときに、解いている問題が自分の研究そのものだったらしく、問題について、軽く解説をしたあとに、「こういうのは好きな人、是非今井研に行きましょう」という言葉でしめた授業が、二回あった。
情報科学実験 I | 各教官
開講時間:月曜・火曜・木曜 午後 | 必修科目
実験概要
プログラミング演習(ML,LiLFeS)
オペレーティングシステム実験(Linux カーネルプログラミング)
ハードウェア実験(論理回路、論理シミュレーション、VHDL)
プログラミング演習(ML)
前半では ML の基礎を学び、後半は穴埋め形式でML のインタプリタを作成する。
後半部分は、4学期(2年冬学期)でやった Scheme の時と似ており、あまり困らなかった。
最後はオセロの思考ルーチンを作成し、学生対抗で競技大会を行った。
この競技大会はけっこう燃えるイベントで、夏休みをかなり費やした人も少なくなかった。
特に、単なる高速化とはまた違う要素、「そこそこ高速で動作させながら、強い手をうつ」事がテーマなので、トレードオフを考えるようになった。
自分は、評価関数のパラメタを調節したり、効率よく先読みする方法を調べたのが、結構、楽しかった。
中には、定石の DB を用意したひともいて、その人が、大会でトップになった。

関数型言語としては、2年の冬学期に Scheme をやっていたので MLの基本的な内容はすんなりとクリアできた。
ML をさわってやっぱり sheme はかっこは多いなぁ、あのかっこの多さは異常だなと思った。

後に、3年の冬学期に、米澤先生の授業を聞いて初めて、「ああ、演習のときに、ML ででてきた 型っていうのが考えていたよりも、もっと深い意味をもっていたんだなぁ」と思った。
プログラミング演習(LiLFeS)
前半は、○×ゲームの探索、αβ探索のプログラムを作成する。
後半のテーマは、形態素解析。英文の構文解析を行う。

LiLFeS は「こんな言語は IS にこないかぎり、さわらないであろう言語」だと思う。
「実用性がなく、無駄」という意見もあるが、一方で、「いい経験になった」という人もいる。
書いて遊ぶ分には、楽しい言語なので、ついでに、たぶん、今、さわらなければ、ほぼ、さわる機会がないであろうと思うので、僕個人としては、それなりに楽しめた。

英文を構文解析の最後の課題は、「オリジナルな機能を追加して英文を解析しましょう」という課題だったが、
そういう自由課題だと、いろんなことが考えられて、動いたときは楽しいけれど動くまでは、けっこうつらかった記憶がある。
これに関連して、単なる愚痴になってしまうけれど、この言語、デバッグのことをまったく考えてないで作られている気がする。
論理型なので、printf をはさんで一発でなおるみたいなことができないし、「もうちょっとデバッグしやすい言語ならいいのになぁ」と思います。


オペレーティングシステム実験(Linux カーネルプログラミング)
前半は Linux のお勉強というか、System Call のお勉強。
後半の課題には「すでにある RFC の規格に準拠した http サーバの実装」という課題がある。
この「規格にそったものを実際に実装しよう」というのが新しく、規格というものは、「面倒くさいけど大事なんだなぁ」と思いました。

自分が作った Web server に対して、普段使ってる IE からリクエストを出したら、本当にページが表示された。
最初にページが表示されたときは「本当にページが表示されるんだなぁ」という事にちょっと驚きつつ、最初は本当に嬉しかった。
でも、そこから後が面倒くさくて、いろんな規格があって、それにちゃんと対応しようとすると、ともかく面倒くさかった。

最後の課題は、「shell の実装」
shell を作っていくうちに signal と process group が 本当にわかったのが、嬉しかった。
Linux を普通にさわってるのに必要な知識以上のものがわかって「ああ、そうだったんだ」「なるほど、kろーいうことをやってたんだ」という感じがした。
ハードウェア実験(論理回路、論理シミュレーション、VHDL)
最初の 1/3 は ブレッドボード(穴のあいた基盤)に IC, 抵抗, ランプ, スイッチをつけ、スイッチを押す事によって、それに反応して LED ランプがちかちかする物を作った。
ここで、はじめて、こういう物に触った人は、たぶん、すごく楽しかっただろうなと思う。

次の 1/3 は ModelSim を使ったシミュレーションを行いながらVHDL の勉強をする。
今までは、ディスプレーに表示される文字をみながらデバッグしていたのが、波形をみながら、デバッグするのが、目新しかった。
また、ALU の仕組みを勉強し、単語として聞いてたものが、中身がどうなってるかがわかった感じで嬉しかった。

後半の 1/3 は 100万ゲートの FPGA 基板を使い、LED を点滅させたり、簡単な整数演算を実機で行う。