日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

限定継続演算子の拡張およびそれを用いた並列向け領域特化言語群の実現
山口 洋

千葉 滋

本稿では，埋め込み領域特化言語の表現力を向上させるための言語拡張を提案する．この言語拡張は並列化向け領域特化言語群の実装に有効である．例えば，フォーク・ジョイン型の並列化プリミティブに対しては逐次と同様の構文を提供できるようになる．この構文は，メソッドやクロージャのような広く使われている言語機構のみを用いた場合には困難であったものである．さらに限定継続演算子と組み合わせたことにより，ノンブロッキング型の並列化プリミティブに対しても同様の領域特化言語を実現可能である．この領域特化言語群により，リファクタリングコストの削減と並列化の誤りの防止が期待される．また，提案する演算子の実装も試みた．

その中でも代表的な並列化プリミティブ群として，

1 はじめにフォーク・ジョイン型を取り上げる．これは，計算の本稿では，埋め込み領域特化言語 (DSL, Domain

分岐を行うフォークと，フォークされた計算の結果をSpecific Language) の表現力を向上させるための汎用合流させるジョインの組からなるようなプリミティの言語機構を提案する．ある領域に特化した言語プブである．このフォーク・ジョイン型プリミティブ

リミティブを構築することに使われる既存の言語機は，既存の言語機構で構築可能な範囲では構文的な制構としては，メソッド・クロージャや Scala の名前呼約が大きく，並列化前の逐次のプログラムの構造を壊

び引数，Ruby のブロック引数のように暗黙的にサンさないように書き加えるという制限の下では，そのプクを生成する機構などが挙げられる．しかしながら，ログラムを並列化することができない．そのため，リしばしばこれら既存の言語機構だけでは十分なプリファクタリングコストの増大や，並列化の誤りといっミティブを得られず，埋め込み DSL を諦めて，専用た問題が生じる．

コンパイラや強力なマクロ機構による専用 DSL を頼らざるをえないことが多い．

本稿では，新しい言語機構として，限定継続演算子に必要呼びのアイディアを加えた新しい演算子を提既存の言語機構だけでは十分なプリミティブを得案し，この演算子によってその問題を解決する．まられない例は並列化プリミティブである．各並列化た，フォーク・ジョイン型プリミティブには，一般的プリミティブは本質的に独自の構文を必要としておなブロッキング型だけでなく，ノンブロッキング型のり，既存の言語機構で構築可能な範囲では強い構文的プリミティブもあるが，それらのプリミティブに対しな制約を受け，自由に便利な構文を提供することが難ても本演算子は有効である．また，本稿では提案するしい．実際，Cilk [5] [6] を始めとして数多くの並列向演算子を Scala に対する言語拡張として実装したプロ

け DSL が提案されているが，その多くが専用のコントタイプについても述べる．

パイラを必要とする．

2 領域特化言語における構文的な制約
Hiroshi Yamaguchi, Shigeru Chiba, 東京大学情報理工学系研究科, Graduate School of Information Science and Technology, The University of Tokyo.

既存の言語機構で実現できる範囲でフォーク・ジョイン型の並列化プリミティブを用いた領域特化言語

能な，フォーク・ジョイン型を用いた領域特化言語
return (f() + g()) * v;

は，必ず，フォーク点とジョイン点の両方を示すプリ
return (par (() -> f()) + g()) * v;

ミティブが揃っている必要がある．
我々は，ジョインする点が暗黙的に補完されるよう

final Future <Integer > x =ForkJoinPool . commonPool (). submit (() -> f());
final int y = g();return (x.get () + y) * v;

な構文を，埋め込み領域特化言語でも実装可能にすべきと考えている．それによって，構文的な制約を軽減することができ，逐次のプログラムの構造を保った並列化が可能なプリミティブを実現できるからである．

図1

フォーク・ジョイン型における構文的な制約

例えば，そのようなプリミティブ par はジョイン点を明示しないため実現できなかったが，ジョイン点のを設計する場合，構文的に制約を受けることがある．

補完により実現可能なプリミティブとなる．

例えば図 1 の 1 番目のような，簡単な Java 8 のプロ

現実には暗黙的な補完を実現できる言語機構はな

グラムをフォーク・ジョイン型のプリミティブを用く，逐次のプログラムとの構文的な違いを十分に埋めいて並列化することを考える．このプログラム中のることはできない．そのため，リファクタリングのコf() をフォークしたいとする．元のプログラムの構ストが増大したり，誤りが起きやすいといった問題が造を保とうとするならば，図 1 の 2 番目のように式生じる．の一部を切り取って渡すことで並列化できるようなリファクタリングのコストが増大する例は，図 2 のプリミティブが構築できると良い．ここで par は，ようなフォークする範囲を変更する場合である．いサンクとしてラムダ式 †1 を渡すと何らかの適切な方

ずれも ( f () + g()) × h() を計算するプログラムである法でフォークして並列化する仮想のプリミティブとが，フォークする範囲が異なり，上は f () をフォークする．しかしながら，この par は実現が困難である．

し，下は f () + g() をフォークする．このように言葉Java 8 において，典型的なフォーク・ジョイン型の並による説明の上では軽微な変更であるが，図に示した

列化プリミティブとしては，java.util.concurrent

通り，実際のプログラムの上では大きな変更となり，パッケージの Future がある．このプリミティブをプログラムのすべての行を修正する必要がある．特に用いたプログラムは，図 1 の 3 番目のように書か注目すべき点は，3 行目の y = g() から z = h() へれ，1 番目とは構文的に大きく異なってくる．まの変更である．これは，フォークする範囲を変更する

ず，1 個の式で書かれていたプログラムは f () ，g() ，ときには，同時に，フォークする計算と並列に行う計( f () + g()) × v の 3 段階に分割される．その上で，2算も変更しなければならないからである．このよう行目の ForkJoinPool.commonPool().submit で f ()に，フォーク・ジョイン型では並列化によってプログをフォークし，フォーク点とは離れた位置にある 4ラムの構造が大きく変化するだけでなく，その構造は行目の get でその計算結果をジョインさせる必要がフォークする範囲によって大きく異なる．そのため，ある．

フォークする範囲の変更もまた，プログラムの構造をつまり，フォーク・ジョイン型において受ける構文的な制約とは，フォーク点とジョイン点を明示的に大きく変更することが必要となり，リファクタリングのコストが増大する，書く必要があるということである．前述の par では間違いを起こす例としては，図 3 のようにジョイフォーク点しか明示されず，ジョイン点を示すプリミン点を誤って指定する場合が挙げられる．このプロティブがないため，一般的なフォーク・ジョイン型でグラムは，逐次のプログラムの構造を壊さないようには実現できないプリミティブである．一般に，実現可並列化しようとして失敗した例である．このプログ
ラムは，Java 8 のプログラムとして正しいものである†1 Java 8 で新たに導入された言語機構が，フォークした点の直後にジョインする点があるたの組からなる．このうち reset は shift/reset におけるfinal Future <Integer > x =ForkJoinPool . commonPool (). submit (() -> f());
final int y = g();return (x.get () + y) * h();それと同一である．また，tearOﬀ はこれまでの継続演算子とは異なり，2 段階に分けて継続を切り取ることで 2 種類の継続，すなわち従来の演算子における現在の継続に加えて “未来の継続” を同時に扱えるよfinal Future <Integer > xy =ForkJoinPool . commonPool (). submit (() -> f() + g());
final int z = h();うになっている．

TearOﬀ は 2 つの引数をとり，それぞれ現在の継続，return xy.get () * z;

未来の継続に相当するクロージャを受け取り何らかの
図2

リファクタリングコストが高い例

処理をするクロージャである．本稿ではこれらのクロージャをコントローラと呼ぶことにする．図 4 においては，それぞれ，k -> k.apply(...) が現在のreturn( ForkJoinPool . commonPool (). submit (() -> f()).get ()継続，(x, k) -> k.apply(x.get()) が未来の継続に対するコントローラであり，継続は引数 k として+ g()) * v;渡される．
図3

典型的な誤りの例

TearOﬀ を実行すると次のように動作する．まず，現在の継続がクロージャとして切り取られ，対応するコントローラに渡される．次にコントローラ内で，そstatic R par <T, R>(final Supplier <T> thunk ) {return tearOff (の現在の継続に相当するクロージャが使われる．このとき，このクロージャは通常とは異なり，必要呼びのk -> k. apply (ForkJoinPool . commonPool (). submit ( thunk )),(x, k) -> k. apply(x.get ()));

ように動作する．まず，クロージャの引数が実際に必要になる直前まで実行される．すなわち，クロージャを x -> {...; y = f(x); ...} と模式的に表現す}

ると，y = f(x) の直前まで実行され，そこで一旦停
図4

par の実装止するということである．そして，そこで 2 段目の継続の切り取りが行われ，それが未来の継続として対め全く並列化できていない．フォーク・ジョイン型の応するコントローラに渡される．つまり，tearOﬀ はプリミティブの構文は逐次の構文と酷似しているが，通常の現在の継続の切り取りに加えて，必要呼びのよ実際には構文的に大きな違いが存在している．そのうな戦略で追加の継続を切り取ることができる．

ため，プリミティブに対する理解が不十分であると，このように間違いが起こる．

TearOﬀ 演算子には他にも特徴的な点があり，それは，現在の継続の引数の型を変更し，さらにその引数を未来の継続のコントローラに追加の引数として渡す

3 提案: ticket 演算子ことができる点である．これにより，図 4 の 4–5 行目

前節の問題を解決する言語拡張として ticket 演算子のように，tearOﬀ 演算子で切り取った現在の継続にを提案する．Ticket 演算子は，限定継続演算子 shift/re-

対して，サンクを実際に計算した値の代わりにフュー

set [2] [1] [9] に必要呼びの戦略を組み合わせて，暗黙チャーオブジェクトを渡すことができる．また，図 4的なジョイン点の補完を可能にした演算子である．この 6 行目のように未来の継続のコントローラには 2 個れにより，例えば Java 8 では，par を図 4 のように実の引数があるが，1 個目の引数 x はこの機能により追装できる．

加された引数である．未来の継続のコントローラは，Ticket 演算子は，拡張された継続演算子 tearOﬀ とこの引数を通して，4–5 行目で現在の継続に渡された継続の切り取り範囲を制限する reset の 2 つの演算子

フューチャーオブジェクトを受け取ることができる．

static R nonblocking_par <T, R>

def fib(n: Int): Future [Int] = async {if (n < 2)(final Supplier <T> thunk ) {return tearOff (1k -> k. apply (else {val xf: Future [Int] = fib(n - 1)

CompletableFuture . supplyAsync ( thunk )),val yf: Future [Int] = fib(n - 2)

(x, k) -> x. thenApplyAsync (k)await (xf) + await (yf));}}}

図5

ノンブロッキング型における par の実装

def fib(n: Int): Future [Int] = async {if (n < 2)

このように，2 つのコントローラ間で値の受け渡しに1else使用することができる．
また，フォーク・ジョイン型には，ここまでで取りawait (fib(n - 1)) + await (fib(n - 2))}上げた一般的なブロッキング型に加えてノンブロッキング型が知られている．ノンブロッキング型がよ

図6

2 つの領域特化言語によるフィボナッチ数の計算く見られる言語として node.js [7] があり，Java 8 においても CompletableFuture が存在する．ノンブロッ

したプリミティブによるプログラム，提案した ticketキング型のプリミティブでも図 5 のようにすること演算子を用いて実装したプリミティブによるプログ

で ticket 演算子により実現できる．一般には，ノンブラムの 4 種類を用いた．元の Scala Async はマクロにロッキング型のようなモナドに類するデザインパターよって実装されているため，shift/reset 版より高速でンに対しては継続演算子が有効であることが知られあると予想された．また，Scala Async によるプログており [4]，ticket 演算子はその理論を拡張する形で設ラム，shift/reset によるプログラムは同一であり，そ計されている．

れを図 6 上に，ticket 演算子によるプログラムを図 6下に示す．Ticket 演算子を使用すると逐次版のプログ

4 実装と実験ラムと同様の構造になる．

提案する ticket 演算子が実際に機能するかを確認す

実 験 環 境 は ，プ ロ セ ッ サ が Intel Core i7-4770Sるためにプロトタイプの実装を行った．プロトタイ

3.10GHz で 4 コア 8 スレッド，Java VM は OpenJDK

プは Java 8 ではなく，Scala 2.11 の言語拡張として実1.7.0_51 64 ビット版，Scala コンパイラは 2.11.1 で，最装した．具体的には，Scala 2.11 標準の型付き構文マ適化オプションとして “-optimise” のほか 5 種類 †2クロシステムを用いて，Scala に shift/reset を追加すを使用した．計測は，JIT の影響を抑えるため最初のる CPS プラグインの実装 [8] を参考に，型主導 CPS10 回を捨て，その後の 20 回の中央値をとった．

(Continuation Passing Style, 継続渡し形式) 変換のアイディアに基づいて実装した．
また，簡単なパフォーマンス測定を行った．実験対それぞれのプログラムについて fib(30) を計算した
結果は表 1 の通りである．Ticket 演算子を使用して実装したプリミティブが動作すること自体は確認でき

象として用いたのは，async/await というプリミティるものの，shift/reset を使用して実装したプリミティブである．このプリミティブは，ノンブロッキング

ブと比較すると並列化にかかったオーバーヘッドが 3な並列化を行うマクロライブラリ Scala Async [3] に倍，Scala Async そのものと比較すると 10 倍と非常によって提供される．これを用いてフィボナッチ数の大きい．これは継続をラッピングするための中間オブ計算を行った．比較対象として，逐次のままのプロジェクトのコストがかかること，またそれによって最グラムと，Scala Async をそのまま用いたプログラム，†2 “-Yclosure-elim”, “-Yconst-opt”, “-Ydead-code”,“-Yinline”, “-Yinline-handlers”

shift/reset を用いて Scala Async に似せて愚直に実装

表1fib(30)

領域特化言語時間 (s)

逐次0.004

Scala Async

0.165

shift/reset

0.598

Ticket1.734

適化が阻害されること，継続渡しのためにクロージャを大量に生成すること，さらに継続を 2 回切り取る
ため shift/reset と比較しても単純計算で 2 倍のクロージャが生成されることなどが原因として考えられる．
パフォーマンスの改善は並列化において重要であり，今後の課題である．

5 結論
本稿では，ticket 演算子を導入し，Java 8 のフューチャーオブジェクトのようなフォーク・ジョイン型の並列化プリミティブに対して，埋め込み領域特化言語の構文的な制約を軽減できることを示した．また，限定継続演算子の機能を取り込んだことにより，ノンブロッキング型の並列化プリミティブに対しても同様にできることを示した．
今後の課題としては，他の並列化プリミティブへの適用可能性の検証，並列計算における実用化に向けた実装の改善，Java を始めとする他の言語における実装を行う等が考えられる．

参考文献[1] Asai, K. and Kiselyov, O.: Introduction to Programmingwith Shift and Reset, ACM SIGPLAN Continuation Workshop 2011, 2011.
[2] Danvy, O. and Filinski, A.: Abstracting control, Proceedings of the 1990 ACM conference on LISP and functionalprogramming, ACM, 1990, pp. 151–160.
[3] EPFL and Typesafe, Inc.: Scala Async. https://github.com/scala/async, http://docs.scala-lang.
org/sips/pending/async.html.
[4] Filinski, A.: Representing Monads, Proceedings of the
21st ACM SIGPLAN-SIGACT Symposium on Principles ofProgramming Languages, POPL ’94, New York, NY, USA,ACM, 1994, pp. 446–457.
[5] Intel Corporation: CilkPlus. http://www.cilkplus.
org/.
[6] Joerg, C. F.: The cilk system for parallel multithreaded
computing, PhD Thesis, Massachusetts Institute of Technology, 1996.
[7] Joyent, Inc: node.js. http://nodejs.org/.
[8] Rompf, T., Maier, I., and Odersky, M.: Implementing
First-class Polymorphic Delimited Continuations by a Typedirected Selective CPS-transform, Proceedings of the 14th
ACM SIGPLAN International Conference on Functional
Programming, ICFP ’09, New York, NY, USA, ACM, 2009,
pp. 317–328.
[9] 浅井健一: shift/reset プログラミング入門, ACM SIGPLAN Continuation Workshop 2011, 2011.