 This slide was a material for the “Reading PLDI Papers (PLDIr)”study group written by Kazuhiro Inaba ( www.kmonos.net ),under my own understanding of the papers
published at PLDI
 So, it may include many mistakes etc

 For your correct understanding, please

consult the original paper and/or the authors’presentation slide!

k.inaba (稲葉 一浩), reading:

PLDIr #13
Jun 30, 2010
paper written by J. Baker and W. C. Hsieh (PLDI 2002)

MAYA: MULTI-DISPATCH
SYNTAX EXTENSION IN JAVA

要するにJava用マクロシステム
 たとえばこんな拡張構文が作れますuse EForEach;h.keys().foreach( String s ) {System.err.println(s + “->” h.get(s));}

 こう展開される
for(Enumeration e$ = h.keys();e$.hasMoreElements(); ) {String s;s = (String) e$.nextElement();
System.err.println(s + “->” + h.get(s));}

どんな風に記述するか？
 例題：

h.keys().foreach( String s ) {System.err.println(s + “->” h.get(s));}

 まず宣言abstract Statement syntax(MethodName(Formal) lazy(BraceTree, BlockStmts));
 Statement ::=MethodName ‘(‘ Formal ‘)’ BlockStmts
 という構文を増やします！と宣言 （※ 下線部はMayaの予約語）

名前をつけて、useでlexical scopeに選択的導入可能

実装の本体

Statement syntax EForEach (「Enumeration型の式」
Expression:Enumeration enumExpなど、型に基づく条件\. foreach (Formal var)lazy(BraceTree, BlockStmts) body型検査とparseの){フェーズを混ぜる
final StrictTypeName castType =lazy-parse機能
StrictTypeName.make(var.getType());
コードテンプレート
return new Statement {(Lispの準クォート)
for(Enumeration e = $enumExp;
e.hasMoreElements(); ) {“衛生的な”変数名$(DeclStmt.make(var))$(Reference.makeExpr(var.getLocation()))= ($castType) e.nextElement();$bodyfor(Enumeration e$ = h.keys();}e$.hasMoreElements(); ) {};String s;}s = (String) e$.nextElement();
System.err.println(s + “->” + h.get(s));}

特徴・評価 Java用マクロシステム
 http://www.cs.utah.edu/~jbaker/maya/
 識別子や型情報を使った、適用条件の制御
 ASTオブジェクトに対する総称関数(マルチメソッド)として実現
 Lazy parsing/typechecking
 Lexical Scopeで拡張を入れたり出したり可能
 準クォートによる、書きやすいAST生成

 MultiJava (Java + マルチメソッド) を2500行程度で実装できた class D extends Cとのこと{ int m(Cc) { return 0; }int m(C@D c) { return 1; } }k.inaba (稲葉 一浩), reading:

PLDIr #13
Jun 30, 2010
paper written by O. Lhoták and L. Hendren (PLDI 2004)

JEDD: A BDD-BASEDRELATIONAL EXTENSION OF JAVABDD (二分決定図) とはこれがBDD Bool n から Bool への関数の効率的な表現(下図はWikipediaから引用)

 プログラム解析などで重要なデータ構造
 and, or を始め論理演算が効率的に実現される

Jedd とは BDD を組み込みの言語機能として持つJava を拡張した言語
 生のBDDをそのまま見せても使いにくいのでリレーショナルＤＢ風味の使い勝手を提供
イメージ図

RDB

BDD

1st author

title

year

Baker

Maya2002

LhotákJedd2004

f(0,0,0,0,0,0) = 1
f(0,1,0,0,1,1) = 1f( それ以外 ) = 0

Baker=00, Lhoták = 01
Maya=000, Jedd=001
2002=0,2004=1 とする（十分なサイズのビット列割り当てはJeddが上手いことやる）という関数

使用例：仮想関数呼出の実体解決<rectype, signature, tgttype, method> answer = 0B;
void resolve( <type,signature> receiverTypes,<subtype, supertype> extend){<rectype, signature, tgttype> toResolve =(type=>rectype tgttype) receiverTypes;
do {<rectype, signature, tgttype, method>resolved = toResolve{tgttype, signagure}>< declaresMethod{type, signature};
answer|= resolved;
toResolve -= (method=>) resolved;
toResolve = (supertype=>tgttype)(toResolve{tgttype} <> extend{subtype});} while( toResolve != 0B );}receiverTypes

extenddeclaresMethod<rectype, signature, tgttype, method> answer = 0B;

void resolve( <type,signature> receiverTypes,=> は、改名兼<subtype, supertype> extend){コピー兼射影<rectype, signature, tgttype> toResolve =(type=>rectype tgttype) receiverTypes;
do {<rectype, signature, tgttype, method>resolved = toResolve{tgttype, signagure}ジョイン>< declaresMethod{type, signature};answer|= resolved;
toResolve -= (method=>) resolved;
toResolve = (supertype=>tgttype)(toResolve{tgttype} <> extend{subtype});} while( toResolve != 0B );}射影 して 差演算合成して改名

特徴・評価 BDDを手軽に使うためのRDB風Java拡張
 http://www.sable.mcgill.ca/jedd/

 バックエンドのBDDは外部libを用いる
 便利な機能いろいろ 意味のあるデータ名から01列へのエンコード
 ”型”が合ってることの静的検査
 join や合成など、高度な演算のサポート
 変数ドメインの分割や並び順の最適化(SATソルバを使用)・プロファイラの提供

 手書きC++と比べてpoints-to-analysis で0.5～4%のオーバーヘッド