Document

POPL 2005 報告
報告者: 前田俊行
はじめに
• 法律上の請求の原因の種類を問わず、報告者
は、本報告の使用若しくは使用不能またはサ
ポートサービスの提供若しくは提供不能から生じ
る一切の損害 (逸失利益、機密情報若しくはそ
の他の情報の喪失、事業の中断、人身障害、プ
ライバシーの喪失、誠実または合理的な注意義
務を含めた義務の不履行、過失、またはその他
の金銭的損失を含みますがこれらに限定されま
せん) に関して一切責任を負いません。
Invited Talk:
Interpreting the Data
Rob Pike
(Google)
一言でいうと、このお話は
• Map & Reduce は素晴らしいという宣伝
– Map & Reduce : Google の開発者等が
Google のデータベースにアクセスするために
日常的に使っているらしい言語
一目でわかる Map & Reduce
proto "document.proto"
max_pagerank_url:
table maximum(1) [domain: string] of url: string
weight pagerank: int;
doc: Document = input;
url: string = doc.url;
emit max_pagerank_url[domain(url)] <- url
weight doc.pagerank;
一目でわかる Map & Reduce
proto "querylog.proto"
static RESOLUTION: int = 60;
# in minutes
log_record: QueryLogProto = input;
query: string = log_record.query;
datum: table sum[t: time][lat: int][lon: int] of int;
loc: location = locationinfo(log_record.ip);
if (def(loc)) {
t: time = log_record.time_usec;
m: int = minutesof(t);
m = m - m % RESOLUTION;
t = trunctohour(t) + time(m * int(MINUTE));
emit datum[t][int(loc.lat)][int(loc.lon)] <- 1;
}
Rob Pike 氏よりのお言葉
• Good
– make it easier to express yourself
• Better
– hide stuff you don’t care about
• Best
– hide stuff you do care about
• Give the language a purpose
A Simple Typed
Intermediate Language
for Object-Oriented Languages
J. Chen and D. Tardi
(Microsoft Research)
一言でいうと、この論文は
• オブジェクト指向言語のための
中間言語 (LILc) を提案する
– LILc = Low-level Intermediate Language
with Classes
何がうれしいのか?
• オブジェクト指向言語を
型情報を保存したまま
コンパイルできるようになる
– 型情報を保存することの利点
–
–
–
–
コンパイラのデバッグに使える
最適化に使える
プログラムの安全性証明に使える
etc.
» (TAL のように)
既存研究は?
• ある、が
– 型システムが非常に複雑である
• 再帰型や継承の扱いが複雑になる
– 安易にやると、型チェックが決定不能になる
– 汎用的でない
• 様々な言語機能をカバーできない
• 様々なコンパイル手法をカバーできない
等の理由により、流行していない
LILc の特徴
• 型システムが
– シンプル
• コンパイラ書きにも理解できる(?)
– 汎用的
• 様々な言語機能を表現できる
• 様々なコンパイル手法が利用できる(?)
• 型チェックが決定可能
LILcのアプローチ
• 「クラス」を「名前」と「レコード」に分ける
• 「名前」
: クラスの名前
• 「レコード」 : クラスの具体的なデータ表現
• 「名前」の親子関係と
「レコード」の親子関係を分ける
• 「名前」の親子関係: subclassing
• 「レコード」の親子関係: subtyping
• クラス間の継承関係を
subclassing だけで表現する
名前
A
subclass
= 継承
subtype
レコード
B
LILc で表現できること(の一部)
• クラス間の継承関係
• ダウンキャスト
(例) Object obj = “Test”;
String str = (String)obj;
• Covariant array
(例) Integer[] ints = new Integer[10];
Object[] objs = ints;
objs[0] = “Hello, World!”;
A Bisimulation for
Type Abstraction and Recursion
E. Sumii and B. C. Pierce
(University of Pennsylvania)
一言でいうと、この論文は
• 2つのプログラム(この論文ではλ-calculus) が
等価であることを証明するための
手法を提案する
– 等価であること =
あらゆる実行コンテキストで同じ振舞をすること
– この論文の提案する手法
• Bisimulation による方法
何がうれしいのか?
• コンパイラの最適化が正しいかどうか
検証できる
• 同じインターフェイスを持った
2つのモジュールが本当に等しいか、
つまり、どちらのモジュールを使っても
結果が変わらないかを検証できる
• etc…
既存研究は?
• ある、が上手く使えない
– Logical Relation による方法
• 問題: 再帰関数や再帰型を扱うと複雑になる
– (従来の) Bisimulation による方法
• 問題:
– 抽象型 (existential型) に応用できない
– 完全でない
» 本当は等価なプログラムを異なると判断する場合がある
この論文の手法の特徴
• Bisimulation を
等価なプログラムの関係ではなく、
等価なプログラムの関係の集合と考える
この論文の方式
従来の方式
抽象型の
ための何か1
P2
P1
P5
P3
P4
何か2
P1
P6
P2
P6
P4
P3
P5
従来の手法でなぜ
抽象型が扱えないのか
• 抽象型の値に関する情報を忘れてしまうから
(例)
M = pack int, <1,λx:int.x=0> as τ
M’= pack bool, <true,λx:bool.￢x> as τ
( τ= ∃α.α×(α→bool) )
λx:bool.￢x:
α→bool
M
M’
1:α
true:α
λx:int.x=0:
α→bool
この関数が取れる引数が
true:αだけということがわからない
この関数が取れる引数が
1:αだけということがわからない
この論文の手法
• 抽象型の値に関する情報も追跡する
(例)
α: int, bool
λx:bool.￢x:
α→bool
M
M’
1:α
true:α
λx:int.x=0:
α→bool
この関数が取れる引数が
true:αだけということがわかる
この関数が取れる引数が
1:αだけということがわかる
この論文の手法の性質
• 抽象型も扱える
• 健全かつ完全である
• シンプルである
– 従来の手法と比べて
Mutatis Mutandis:
Safe and Predictable
Dynamic Software Updating
G. Stoyle (University of Cambridge),
M. Hicks (University of Maryland),
G. Bierman (Microsoft Research),
P. Sewell (University of Cambridge) and
I. Neamtiu (University of Maryland)
一言でいうと、この論文は
• 実行時に動的にプログラムを更新できる言語
(Proteus) を提案する
– Proteus の特徴
• 安全
• 柔軟
• 予測可能
何がうれしいのか?
• プログラムを停止させることなく
そのプログラムを更新することができる
– (例) Windows を停止させることなく
Windows Update する
この論文で扱う更新の種類
• 名前付き型の更新・追加
• トップレベル関数・変数の更新・追加
名前付き型の例
type A {
int a;
};
C の構造体や
Caml の type n = …
この論文の手法で実現できる
実行時更新の例
type A {
int(int) a;
int b;
};
type A {
int a;
};
更新
A M(A a1)
{
A a2;
a2.a = a1.a + 1;
return a2;
}
(注) 本当は古い型Aの値から新しい型Aの値
への変換関数が必要だがここでは省略
A M(A a1)
{
A a2;
a2.a = a1.a;
a2.b = a1.a(a1.b);
return a2;
}
実行時更新の難しいところ
• 更新するタイミング
– 更新しようとしている型の値を
プログラムが正に操作しようとしていたら困る
更新してはいけないタイミングの例
type A {
type A {
int a; 更新したい
int(int) a;
};
int b;
};
A M(A a1)
{
A a2;
a2.a = a1.a + 1;
return a2;
}
このタイミングで
更新されると
あぶない!
この論文の手法
• 名前付き型の値を利用する式全てに
注釈を付ける
– 注釈の種類は2つ
• abs : 型の名前だけ分かればよい式に付ける
• con : 型の中身が分からなければならない式に付ける
• 安全に更新できる箇所に印(‘update’)を付ける
– 安全に更新できる箇所 = それ以降 con が存在しない箇所
• これらの注釈や印は全て
型推論によって自動的に付けられる
注釈や印の例
A M(A a1)
注釈を付ける A M(A a1)
{
{
A a2;
A a2;
(conAa2).a =
a2.a = a1.a + 1;
(conAa1).a + 1;
return a2;
update;
}
return (absAa2);
ここなら型 A を更新しても安全!
}
(型 A の中身を使わないから)
From Sequential Programs to
Multi-Tier Applications by
Program Transformations
M. Newbauer and P. Thiemann
..
(Universitat Freiburg)
一言でいうと、この論文は
• 自然な形で書かれたプログラムを
Multi-Tier な形に自動的に変換する
手法を提案する
– Multi-Tier なアプリケーションの例
• Web アプリケーション
– 主に3つのtier
» クライアントのブラウザ
» アプリケーションサーバ
» データベースサーバ
何がうれしいのか?
• Multi-Tier なアプリケーションを
簡単に書けるようになる
– Multi-Tier なアプリケーションの作成は
複雑で難しい
• 複数のマシンの連携
• 非同期性
(例) 以下のプログラムを
Multi-Tier な形に変換する
void show_messages() {
string query = GUI_get_query();
string[] messages = DB_query(query);
GUI_show_messages(messages);
}
手順1: 関数や値に注釈をつける
void show_messages() {
C
string query = GUI_get_query();
string[] messages = DB_query(query);
GUI_show_messages(messages);S
C
}
C
クライアント
S
サーバー
手順2: 注釈が衝突する場所に
‘trans’ を入れる
void show_messages() {
C
string query = GUI_get_query();
query = trans[C->S] query; S
string[] messages = DB_query(query);
messages = trans[S->C] messages;
GUI_show_messages(messages);
C
}
trans[A->B] : 場所Aから場所Bへデータを移す
手順3: プログラムを分割する
S
void show_messages() {
string query = recv();
string[] messages = DB_query(query);
send(messages);
}
C
void show_messages() {
string query = GUI_get_query();
send(query);
connectや listen
string[] messages = recv();
などは後述
GUI_show_messages(messages);
}
ここまでのやり方の問題
• 効率が良くない場合がある
– ‘trans’ ごとにコネクションを張る必要がある
S
open
close
open
close
void show_messages(Messages i) {
bool b = i.hasNext();
b = trans[S->C] b;
if (b) {
string message = i.next();
message = trans[S->C] message;
GUI_show_message(message);
C
show_messages(i);
}
}
この論文の提案する解決方法
• コネクションのスコープをできるだけ大きくする
open
S
void show_messages(Messages i) {
bool b = i.hasNext();
b = trans[S->C] b;
if (b) {
string message = i.next();
message = trans[S->C] message;
GUI_show_message(message);
C
show_messages(i);
}
close }
最適化の結果
C
void show_messages(Channel chan) {
bool b = recv(chan);
if (b) {
string message = recv(chan);
GUI_show_message(message);
show_messages(chan);
}
}
S
void show_messages(Messages i, Channel chan) {
bool b = i.hasNext();
send(chan, b);
if (b) {
string message = i.next();
send(chan, message);
show_messages(i, chan);
}
}
最適化の結果、
connectや listen
などはこの関数内で
する必要はないことが
分かった
Invited Talk:
How should we program
graphics hardware?
P. Hanrahan
(Stanford University)
一言でいうと、このお話は
• Graphics ハードウェアを計算に使いましょう
という呼びかけ
– 理由: CPU よりも GPU の方が性能がいいから
CPU と GPU の性能比較
出典:
Stream Programming Environments,
P. Hanrahan, GP^2 Workshop, 2004
Graphics ハードウェアの特徴
• 並列度が高い
出典:
Stream Programming Environments,
P. Hanrahan, GP^2 Workshop, 2004
GPU の並列処理方式
• ストリーム・アーキテクチャ
Input
カーネル
Output
カーネル
カーネル
Input
カーネル
カーネル
Output
カーネル: 小さなプログラム
ストリーム: データの流れ
では、その並列性を
上手く利用するためには?
• プログラミング言語のレベルで
ストリーム・アーキテクチャを
サポートすればよい
– この人達の提案する言語: Brook
一目で分かる Brook
kernel void foo(float a<>, float b<>,
output float result<>)
{
result = a + b;
}
void reduce sum(float a<>,
reduce float result<>)
{
result = result + a;
}

Download Report