密な演算子呼び出しで実現した 内部DSLの前処理による 実行速度改善の試み

Presentation on theme: "密な演算子呼び出しで実現した 内部DSLの前処理による 実行速度改善の試み"— Presentation transcript:

1 密な演算子呼び出しで実現した 内部DSLの前処理による 実行速度改善の試み
東京大学 情報理工学系研究科 長田朋久 千葉滋 ----- 会議メモ (16/02/29 11:05) ----- 東京大学 千葉滋 Osada Tomohisa

2 内部DSL (Domain Specific Languages)
特定の領域に特化したプログラミング言語のライブラリ 自然な表記が可能 例: ScalaのList val lst = 1 :: 2 :: 3 :: Nil はじめに, 研究背景として 内部DSL を説明します. 内部DSLとは, 特定の領域に特化したプログラミング言語のライブラリであり, なおかつその領域について自然な記法を可能とするものです. 例として Scala のリスト表現を挙げると, このように Scalaでは 1::2::3::Nil という書き方でリスト「1,2,3」を表すことができます. ----- 会議メモ (15/12/01 16:16) ----- EDSLの説明になっているように説明する 自然な構文になる みたいな説明 ----- 会議メモ (15/12/09 16:07) ----- enable ----- 会議メモ (16/02/29 11:05) ----- Domain Specific Languages ーーー 普通はメソッドではない Osada Tomohisa

3 内部DSL (Domain Specific Languages)
特定の領域に特化したプログラミング言語のライブラリ 自然な表記が可能 例: ScalaのList ホスト言語の文法的制約を受ける val lst = ((Nil.::(3)).::(2)).::(1) これは実際には :: が Listクラスのメソッドであり, List型であるNilから :: メソッドが連鎖的に呼び出されることで実現されています. Scalaにはメソッド呼び出しの際に . と実引数のための()を省略するシンタックスシュガーの機能があるため, それにより自然なリスト表現となっているわけです. そして, このような内部DSLでは, ライブラリとして実現されるため, 表現力は必ず元の言語以下になる, という特徴があります. ----- 会議メモ (16/02/29 11:05) ----- :: は組み込み演算子ではない 必要に応じて好きな演算子を定義できる ーーー → メソッドだからユーザが自由に定義できる "::" はListクラスのメソッド 組み込み演算子ではない Osada Tomohisa

4 密な演算子呼び出しによる内部DSL Scala ProteaJ [Ichikawa et al, Modluarity'14]
二項演算子に見えるメソッドを定義可能 ドットと括弧を省略できるが空白が必要 可能な演算子名に制限がある メソッド名であるため ProteaJ [Ichikawa et al, Modluarity'14] n項演算子を定義可能, 空白不要, メソッド名に 制限がない 擬似的なリテラルを演算子で定義可能 密な演算子呼び出しになりやすい 1.+(2) = 1 + 2 そこで, 内部DSLの表現力を向上させるための研究として, 密な演算子呼び出しによる内部DSLの構築をサポートする言語があります. ----- 会議メモ (15/12/09 16:07) ----- Exsiting approaches ----- 会議メモ (16/02/29 11:05) ----- 前のスライドから情報が増えてる? 次のスライドがよく分かるようになる話を 密な演算子呼び出しとは Scala → 単純な演算子呼び出し 演算子名は決まっている 前後に空白がいる ProteaJ → 密な演算子呼び出し 演算子名は何でも いらない → 擬似的なリテラルが表現可能になる Osada Tomohisa

5 擬似的なリテラルを密な演算子呼び出しで 表現する
0b101 // 5 "0b" _ : Binary -> Int "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0" : Binary "1" : Binary ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex ----- 会議メモ (16/02/29 11:05) ----- アンダースコア _ はオペランド 上3つは単項演算子 下2つは無項演算子 タイトル: 擬似的なリテラルを密な演算子呼び出しで表現する Osada Tomohisa

6 擬似的なリテラルを密な演算子呼び出しで 表現する
オペレータ オペランド 0b101 // 5 "0b" _ : Binary -> Int "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0" : Binary "1" : Binary 単項演算子 ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex ----- 会議メモ (16/02/29 11:05) ----- アンダースコア _ はオペランド 上3つは単項演算子 下2つは無項演算子 タイトル: 擬似的なリテラルを密な演算子呼び出しで表現する 無項演算子 (関数)型 Osada Tomohisa

7 擬似的なリテラルを密な演算子呼び出しで 表現する
"0b" _ : Binary -> Int "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0" : Binary "1" : Binary Expect Binary value Return Int value 0b101 // 5 ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex Osada Tomohisa

8 擬似的なリテラルを密な演算子呼び出しで 表現する
"0b" _ : Binary -> Int "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0" : Binary "1" : Binary Expect Binary value Return Int value 0b101 // 5 0b ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex ----- 会議メモ (15/12/09 16:07) ----- zerob(one(zero(one()))) --- 101がオペランド式 Osada Tomohisa

9 擬似的なリテラルを密な演算子呼び出しで 表現する
"0b" _ : Binary -> Int "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0" : Binary "1" : Binary Expect Binary value Return Int value 0b101 // 5 0b 1 ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex ----- 会議メモ (15/12/09 16:07) ----- zerob(one(zero(one()))) Osada Tomohisa

10 擬似的なリテラルを密な演算子呼び出しで 表現する
Expect Binary value "0b" _ : Binary -> Int "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0" : Binary "1" : Binary Return Int value 0b101 // 5 0b 1 ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex ----- 会議メモ (15/12/09 16:07) ----- zerob(one(zero(one()))) Osada Tomohisa

11 擬似的なリテラルを密な演算子呼び出しで 表現する
"0b" _ : Binary -> Int "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0" : Binary "1" : Binary Expect Binary value Return Int value 0b101 // 5 0b 1 ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex ----- 会議メモ (15/12/09 16:07) ----- zerob(one(zero(one()))) 4回の演算子呼び出しが密に発生 Osada Tomohisa

12 How to construct EDSL by dense operator calls
Syntax are more expressive by operators Binary numbers for example This expression needs some operators to parse 0b101 // 5 "0" : Binary "1" : Binary "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0b" _ : Binary -> Int ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex 0b 1 Underscore is a hole part, which expect a value of a specific type Osada Tomohisa

13 How to construct EDSL by dense operator calls
Syntax are more expressive by operators Binary numbers for example This expression needs some operators to parse 0b101 // 5 "0" : Binary "1" : Binary "0" _ : Binary -> Binary "1" _ : Binary -> Binary "0b" _ : Binary -> Int call operators 4 times ----- 会議メモ (15/12/01 16:16) ----- 前の分野を進めていくと...こういうことも可能です _ _ : Regex -> Regex -> Regex 0b 1 Underscore is a hole part, which expect a value of a specific type Osada Tomohisa

14 密な演算子呼び出しによる実行時間の低速化
独自に作成した言語にて実験 2進数リテラルの評価時間を 計測 "0b10101" を4万回評価 通常のリテラル コンパイル時に意味解析 密な演算子呼び出し 遅い. 実行時に意味解析(=演算子実行) しているようなもの 直にパース の方もなんか説明 ----- 会議メモ (15/12/09 16:07) ----- zerob(one(zero(zero(... - I have imlemented this idea on my language - Dense operator calls make evaluation time slow ----- 会議メモ (16/02/29 11:05) ----- 実行時に構文解析しているようなものだから 遅い Osada Tomohisa

15 密な演算子呼び出し部分の構文木変換 目標 方法 密な演算子呼び出しによる内部DSLの実行時間を削減する
----- 会議メモ (15/12/01 16:16) ----- デンスオペレータと コンパイラが直にパーすする場合とを 比較してやっぱ遅いですね という simplify -> transform ----- 会議メモ (16/02/29 11:05) ----- 構文木を変換することで ← いらない 方法: コンパイル時に内部DSL部分の構文木を変換する Osada Tomohisa

16 実験に用いた独自言語 密な演算子呼び出しによる内部DSLを 構成可能な言語を作成
operators TupleInt { "0" () = 0 -> 1; "1" () = 1 -> 1; [r] "0" _ (TupleInt pair) = (first pair) -> ((second pair) + 1); [r] "1" _ (TupleInt pair) = ((first pair) + (1 << (second pair))) -> ((second pair) + 1); }; operators Int { [r] "0b" _ (TupleInt pair) = first pair; }; ----- 会議メモ (15/12/01 16:16) ----- Attempts ----- 会議メモ (16/02/29 11:05) ----- タイトル: 独自言語 2進数の例にする Osada Tomohisa

17 実装した構文木の変換 まず, 演算子のインライン展開を実装した 例: 0b10 のインライン展開 Call(Var("0b"),
構文木の文字列表現 Call Var Tuple Call(Var("0b"), Call(Var("1"), Call(Var("0"),Tuple(0,1)))) First(Tuple(Plus(First(Tuple(0,1)), LeftShift(1,Second(Tuple(0,1)))), Plus(Second(Tuple(0,1)),1))) ----- 会議メモ (15/12/01 16:16) ----- インライン展開に効果があったかを説明する ----- 会議メモ (16/02/29 11:05) ----- 構文木ってわかりにくいから 木の絵を書いたらどう Osada Tomohisa

18 インライン展開実装版の実行時間 独自に作成した言語にて実験 2進数リテラルの実行時間を 計測 "0b10101" を4万回評価
インライン展開により大幅に 速度が低下した 理由は調査中 直にパース の方もなんか説明 ----- 会議メモ (15/12/09 16:07) ----- zerob(one(zero(zero(... - I have imlemented this idea on my language - Dense operator calls make evaluation time slow ----- 会議メモ (16/02/29 11:05) ----- バグがありそうです 調査中 Osada Tomohisa

19 関連研究 書き換え規則 CodeBoost (C++): GHC/Haskell rewrite rules (Haskell):
GHC/Haskell rewrite rules (Haskell): {-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-} Osada Tomohisa

20 今後の予定 具体的な前処理の内容を考案する 実用的な言語で実装する 特定のDSLに特化した構文木の変換 Java(ProteaJ)上
----- 会議メモ (15/12/01 16:16) ----- ProteaJ -> Java にする 関連研究について調べますみたいな ----- 会議メモ (15/12/09 16:07) ----- preprocess -> ここまで出てきた言葉にする Concrete other approaches of AST transformation 2個目いらない search -> investigate ----- 会議メモ (16/02/29 11:05) ----- 今後の予定 より特定の演算子(DSL)に特化した木構造の変換 Osada Tomohisa

21 Summary EDSL constructed by dense operator calls are slow to evaluate expressions Propose transforming AST by using relations of operators in an EDSL Made an original language and implemented in-line expansion Apply the idea to practical languages to test performances for future tasks Osada Tomohisa