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

段階的計算における最適なステージ化プログラム生成
の自動化
清水 春樹

亀山 幸義

段階的計算 (ステージ化計算) は，特定のパラメータに特化したプログラム (コード) を生成し，実行するという複数の段階を持つ計算である．特化を全自動で行う部分計算に対して，段階的計算では，対象領域ごとの最適化をプログラマが記述するため，手間はかかるが効率的なコードを生成できる可能性が高い. 段階的計算をサポートする機構を持つプログラム言語を MSP 言語と呼び，その言語におけるプログラミングを MSP と呼ぶ．本研究の目的は，通常のプログラムをステージ化プログラムに自動的に変換する手法を得ることである．段階的計算のケーススタディとして高性能計算のプログラムを扱った経験から，ステージ化プログラム全体を手動で開発するのは手間が膨大であるという問題があることがわかった．この問題に対する解決策として，本研究では，与えられたプログラムをステージ化
プログラムに変換する部分を自動化し，そのあと手動で最適化を行なう，という組み合わせで，効率良いコードを生成することとした．Linger らは，束縛時解析に基づいたプログラムのステージ化手法を提案したが，彼らの方法はMSP 言語で型付け可能なプログラムの侯補を全て返す．我々は，コードの「望ましさ」の基準を定め，その基準で最適なコードを得る手法を提案する. この手法に，メモ化による let 挿入やドメイン最適化を組み合わせて，手動でのステージ化に近い効率を持つステージ化プログラムを自動生成する．

Staged Computation is a compuation which has multiple stages such as code generation and code execution. While Partial Evaluation oﬀers fully automatic program specialization, Staged Computation lets a
programmer to write domain specific optimization, thus allowing chances to generate more eﬃcient codes.
An MSP language is a programming language with some support for Staged Computation. The purposeof this research is to acquire an automatic method to convert unstaged programs into staged programs.
From our experience on developing staged programs for high-performance computation, it turns out that
hand-conversion needs much energy and cost, which will not be justified in many applications. To address
this problem, we propose a combined method to obtain a staged program, by first converting an unstaged
program into a staged one automatically, and then hand-optimizing it. Linger and Shears proposed an automatic conversion method based on binding-time analysis, but their method returns all possible well-typed
programs. In this research, we set up a criteria for desirability of codes, and then propose an algorithm toobtain the most desirable code based on this criteria. Combining this method with staged memoization anddomain-specific optimization, we expect to obtain an automatic staging method, whose output is close tohand-written staged programs.

した効率の良いプログラムを生成して出力する手法

1 はじめにである．他のメタプログラミング手法と違い，MSP

本研究は，メタプログラミングの一つである段階

では生成されたプログラムコードの型安全性が静的的計算 (マルチステージプログラミング，MSP) に関に保証される，という特徴がある．MSP をサポートする研究である．MSP は，特定のパラメータに特化する機構を持つプログラム言語を MSP 言語と呼び，

Atuomatic Generation of Optimal Staged Programs.
Haruki Shimizu,Yukiyoshi Kameyama, 筑波大学大学
院システム情報工学研究科コンピュータサイエンス
専攻, Dept. of Computer Science, Grad. School of
Systems and Information Engineering, University ofTsukuba.

MetaOCaml がその代表例である．MetaOCaml は，Lisp の擬似引用 (quasi-quoation) に対応するコンス
トラクトを OCaml に追加し，MSP を行なえるようにした拡張である．
本研究の目的は MSP を，高性能計算などにおける，手動のコード生成が行われている分野に適用し，は，プログラムと，ステージ化後のプログラムの型

系統的で信頼性が高いコード生成を行うことである．

付けの情報から，その型を持つステージ化プログラ

我々の研究の全体像を図 1 に示す．

ムを生成することができる．しかし，この手法では，ステージ化後のプログラムとして型付け可能なものが複数あるときは，そのすべてのを出力する．本研究では得られるコードの望ましさに基準を定め，その基準で最適なコードを得るアルゴリズムを提案する．
また，この手法に，Monadic Staging やドメイン最適化を組み合わせた手法についても言及する．

2 ステージ化について
図1

研究の全体像MSP では，特殊な構成子 (MSP 構成子と呼ぶ) を用いて，プログラム内の評価順序を操作する．通常のこれまでに我々は，高性能計算のいくつかのプロ
グラム (隠れマルコフモデルのアルゴリズム，レイト

プログラムに MSP 構成子を加え，評価順序を操作することをステージ化する，という．

レーシング，行列計算など) に MSP を適用し，系統

本稿では，MSP 言語として，MetaOCaml を採用的なコード生成を行ってきた．これは，MSP を高性

し，この表記に従う．MetaOCaml における MSP 構

能計算分野のプログラムに適用しようという Shonan

成子は，Bracket (.< と >.)，Escape (.~)，Run (.!)

Challenge [1] の一貫として行ってきたものである．こである．この 3 つの構成子を既存のプログラムに付こで行ったのは，ステージ化されていないプログラム

加することで，プログラム内の評価順序を操作する．

が与えられ，効率良いコードを生成するステージ化プ

以下，それぞれの構成子について説明する．

ログラムに手動で変換する，という作業である．この・Bracket

経験を通じて，ステージ化プログラムの作成作業の多Bracket(.< >.) はコードを作る構成子であり，Lisp

くの部分は機械的であること，また，生成されるコーの quasiquote (backquote) に類似した働きをする．

ドの効率化のための技法である Monadic Staging [6]Bracket は任意の項を対象にでき，対象になった項はやドメイン最適化 [4] についても，ある程度自動的に評価されない．Bracket は項 e に対して，.<e>. のよ

組み込めるのではないか，という観察を得た．

うに e を.< >. で囲むことによって使用する．

本研究は，これらの観察に基づき，自動的に，人間・Escapeが作成したものに十分近いステージ化プログラムを

Escape(.~) は複数のコードを結合する構成子であ得ることを目的とする．対象領域ごとの個別の最適化

り，Lisp の comma (anti-quote) に対応する．Escapeのすべてを自動的に行なうことは不可能であるので ，は項 e に対して.~e のように項の前に.~を加えるこ

本研究の手法で自動的に作成するステージ化プログとによって使用する．Escape は Bracket で囲まれラムは，更に人間が手を加えることを想定する．つまた項を対象にし，対象の Bracket をはずす．ただし，り，機械的に生成されたコードであってはならず，ス

Escape は Bracket の中でしか使うことができない．

テージ化前のプログラムと (ある程度) 対応し，かつ，・Run

可読性にもすぐれたものであることが必要である．

Run(.!) は生成されたコードを (コンパイルして)ステージ化されていない通常のプログラムから，ス実行する構成子である．Run は項 e に対して，.!e

テージ化されたプログラムを自動的に得る手法としのように項の前に.!を加えることによって使用する．

て，Linger らは，部分計算における束縛時解析の考Run は Bracket で囲まれた項を対象にし，Bracket

え方をもとにした手法 [5] を提案した．彼らの手法での中の項をコンパイルして実行する．

例として，べき乗を求める関数 power を定義する．
let rec power n x =if n=0 then .<1>.
else .< .~x * .~(power (n-1) x)>.

彼らの手法は，入力として，ステージ化されていな
いプログラムと，ステージ化プログラムの型を受け取る．ステージ化プログラムの型により，どの引数がどのステージで評価されるべきかが指定される．これにlet power3 =.! .<fun x -> .~(power 3 .<x>.)>.

Bracket などの MSP 構成子を除いてみると，このプログラムは x の n 乗を計算する通常の関数である．

対して，型推論と束縛時解析をおこなって，MSP 構
成子をどの場所に何個いれればよいかをあらわす制約を生成して出力する．

関数 power3 は，x の 3 乗を計算するのに特化した関このアルゴリズムの特徴は以下の通りである．

数である．ただし，MSP 構成子がない状態で見ると，• 可読性の高いプログラムを生成 (後で人が手をpower3 は power を何度も再帰的に呼ぶというオーバ

加えることを想定しているため)ヘッドがかかる．MSP では，Bracket を使うことで• 生成されたプログラムは型付け可能なことを保証

未来のステージへ計算を先送りし，Escape によって• 候補が複数あるときはそのすべてを出力 (人が今計算できる箇所を先に計算してしまうことで，プログラムを生成することができる．

power3 で Run を行う前の評価結果は以下のようになる．

.<fun x -> (x * (x * (x * 1)))>.
これが Run により，fun x -> (x * (x * (x * 1)))

どの候補がいいかを選ぶ)

Linger らのアルゴリズムの概要を以下で説明する．
ステップ 1. 与えられたプログラムのすべてのプロ
グラム・ポイントに，Annotation 変数と呼ばれる整数値変数 (互いに相異なるもの) を付加する．
例: ステージ化前のプログラム.

という関数定義をコンパイルしたものと同等なもの(λx.((+ x) 1))が得られる．power3 は n=3 に特化した関数であり，Annotation 付きプログラム:

これは再帰呼び出しや条件分岐がないため，通常のpower 関数よりも高速である．

(λx.((+f xe )d 1c )b )a

(1)

(2)

Annotation 変数は MSP 構成子の個数を意味し，

上記のようなステージ化は，プログラマが手動でAnnotation つきの項 en に対して，n=0 のとき，項ステージ化構成子を書き込むことで実現する．また，

e 自身を表し，n>0 のときその項に Bracket が n 個付

プログラマが特定領域ごとの最適化を記述することいた項を表し，n<0 のときその項に Escape が-n 個付で効率的なコード生成を可能にしている．本研究の目いた項を表す．

的は，ステージ化構成子の書き込みを自動化し，でき

項につける Annotation は，一般には，整数値を表るだけプログラマが手動で記述したものに近づけるす式 (Annotation 変数，整数値定数，加算，減算かことである．

ら構成される) となる．例えば，以下の式 (3) は，(λx.((+0 x−1 )0 10 )1 )0

3 既存研究3. 1 Linger らの手法
Linger らによって提案された手法 [5] は, 部分計算における束縛時解析 (BTA) を利用し，自動ステージ(3)

次の式 (4) を意味する．

(λx..<((+ .~x) 1) >.)(4)

また，型にも Annotation を付ける．たとえば，(int1 ->int1 )0(5)化をおこなう．対象言語は，MetaML のコア言語でという型は，((int code) -> (int code)) というあり，MetaOCaml の基礎である λi と比べると，(1)型を表す．ここで’a code は，型’a をもつ項のコードを表す型である†1 ．

Run がない (コードを生成できるが，体系内で実行することはできない), (2) 多相型に対応していない，という違いがある．

†1 MetaOCaml では，コード型は Environment Classifier に対応する型変数を含むため，この型は，(’a,int)
code -> (’a,int) code と表現される．

ステップ 2. Annotation 付き項の型推論を行う．

が与えられた場合，s=1,t=1,u=0 が得られる．

上記の式 (3) の型推論を行うと，返ってくる型はステップ 4. 制約を解消して，可能な Annotation

int -> int であるが，式 (4) の型推論をするために変数の組合せ全てを「可能なステージ化」として出力は，Annotation 付き項の推論を行うルールが必要と

する．

なる．

Linger らのアルゴリズムで生成される制約は，An-

このための規則の主要なものを，以下に掲げる．
C; Γ ⊢n+j e : ti−jAnnC ∪ {n + j ≥ 0, i ≥ j}; Γ ⊢n ej : tinotation 変数に関する線形の不等式であるので，有Γ(x) = (t, m, λ)Var{n ≥ m}; Γ ⊢n x : t

以下は Linger らの手法で自動ステージ化を行った

限時間で解消することができる．
例

例である．(実行結果は，我々が作成した実装による．)
入力は以下の 2 つである．

C1 ; Γ ⊢n e2 : s C2 ; Γ ⊢n e1 : s → t
AppC1 ∪ C2 ∪ valid(s); Γ ⊢n e1 e2 : t• 式 (3) の プ ロ グ ラ ム の Annotation で あ る

C1 ; Γ ⊢n e1 : bool C2 ; Γ ⊢n e2 : t C3 ; Γ ⊢n e3 : t
If
C1 ∪ C2 ∪ C3 ; Γ ⊢n if e1 then e2 else e3 : t
型判定は C; Γ ⊢n e : s の形である．Γ は型環境，eは項，s は型，n はステージ (レベル) であり，C は，a,b,c... を そ れ ぞ れ j_1，j_2，j_3... に 変
更したもの• 型 (5)
これに対して，アルゴリズムを走らせて得られた制

この型推論で生成する制約をあらわし，n + j ≤ 0 な

約は以下のものである．

ど，Annotation 式に対する不等式からなる有限集合["1 = 0 + 0 + j_2"; "1 = 0 + 0 + 0 - j_5";

である．Γ(x) = (t, m, λ) は，変数 x の型が t で，ス"0 = 0 + j_1"; "1 = 0 + 0 + j_2";

テージ (レベル) が m で，かつ，この変数が通常のλ"1 = 0 + 0 + 0 - j_5"; "0 = 0 + j_1";

変数であることを意味している．(型推論のため，let"0 >= 0"; "j_3 >= 0"; "j_3 = 0";

rec で導入される再帰的な変数と通常のλ変数を区別"0 + j_1 + j_2 + j_3 >= 0"; "j_4 = 0";

している．) また，valid(s) は，型 s のあらゆるポイ"0 + j_1 + j_2 + j_4 + j_5 >= 0 + j_1";

ントにつく Annotation が非負である，という制約で"0 + j_1 + j_2 + j_4 + j_5 >= 0";

ある．

"j_6 = 0"; "0 + j_1 + j_2 + j_4 + j_6 >= 0";

上記の中で特に重要なのは Ann 規則で，これは，"0 + j_1 + j_2 + j_4 + j_6 >= 0";

通常の MSP 言語の型付け規則における Bracket と"0 + j_1 + j_2 + j_4 >= 0";

Escape のルールを 1 つにまとめたものである．すな"0 + j_1 + j_2 >= 0"; "0 + j_1 >= 0"]

わち，上記規則で j > 0 ならば Bracket を j 個つけ

この制約を解消することで j_n が決定する．

る規則となり，j < 0 ならば Escape を −j 個つける

j_1 = 0, j_2 = 1, j_3 = 0

規則となる．

j_4 = 0, j_5 = -1, j_6 = 0

上記の型付け規則を使って，式 (3) の型推論を行

これをプログラムに反映すると，以下の，ステージ
化プログラムが出力される．

うと，(ints ->intt )u(6)という型と，制約 (例は後述) が得られる．

(λx..<((+ .~x) 1).>)(7)

ステップ 3. 入力の型に関する制約を表現する．
入力となるプログラム全体の，ステージ化後の型は，ユーザが (入力の一部として) 与えているので，それを制約として表現する．たとえば，上記の型 (5)3. 2 Monadic Staging
Swadi ら [6] が提案した Monadic Staging は，既に計算した関数呼び出しの結果をメモ化する仕組みを，ステージ化計算において導入する手法である．この手

法は，関数の再帰呼び出しの部分 (Y コンビネータ)

式 (8) は if を含んでおり，このコードと (9) の型のを，メモ化の操作を組み込んだ Y コンビネータに置入力だけでは出力が一意に決まらない．以下が例 1 のきかえることによって，任意の関数に対するメモ化を

出力の候補である．

実現するものであり，関数が実現する計算とメモ化の

λx. .<if x = 1 then 0 else 1>.

操作を分離することで，元の再帰アルゴリズムを変え

λx. if x = 1 then .<0>. else .<1>.

ずにステージ化が実現できる．
例として，以下は Gibonacci 関数 (Fibonacci 関数

例 2.

の初期値を変数にした関数) に，ステージ化構成子を(λx.(λy.y) x) 10(10)

int code(11)

埋め込んだコードである．
let rec gib_s x y n =if n = 0 then x
else if n = 1 then yelse .< .~(gib_s x y (n-1))+ .~(gib_s x y (n-2))>.

例 2 は関数適用を含んだ例であり，以下がその出力候補となる．

.<(λx.(λy.y) x) 10>.

この関数を n=5 に特化したステージ化を行うと以下のコードが生成される．
# .<fun x y -> .~(gib_s .<x>. .<y>. 5)>.;;- : (’a, int -> int -> int) code =.<fun x_1 ->fun y_2 ->((((y_2 + x_1) + y_2) +(y_2 + x_1)) + ((y_2 + x_1) + y_2))>.

このコードは (y_2 + x_1) を何度も計算していて実行効率が悪く，また，再帰関数では，コードのサイズも非常に大きくなるという問題が生じる．そこで，
関数呼び出しの際に引数の key によるメモ化を行う．

Monadic Staging は，コード生成時ではなく，生成されたコードの実行時にメモ化が起きるよう工夫し，そのメモ化を let 挿入の手法でコードに反映させるものである．これにより，以下のコードが生成される．
- : (’a, int * int -> int) code =.<fun (x_1, y_2) ->let z_3 = y_2 in
let z_4 = x_1 in
let z_5 = (z_3 + z_4) in
let z_6 = (z_5 + z_3) in
let z_7 = (z_6 + z_5) in (z_7 + z_6)>.

(λx..<(λy.y) x>.) 10(λx.(λy.y) x).<10>.
(λx.(λy.y) .<x>.) 10(λx.(λy..<y>.) x) 10
Linger らの手法は，ここから人間がもっともよい
プログラムを選ぶことを想定している．しかし，例えば例 1 の if 式では，if のネスト回数に依存する数の候補が出力されてしまう．さらに例 2 のような関数適用を組み込むと，かなり多くの候補が出力されることが予想される．
本研究では，自動生成したステージ化プログラム
を，手動で改善することを前提としているため，多数の侯補が出力されるより，もっとも良さそうな 1 つの侯補のみを示した方が都合がよいと考えられる．そこ
で，適切な基準を定めることで，出力されるプログラ
ムの候補数を減らすこととする．

4 望ましいステージ化プログラムの選択手法
4. 1 第一の方法
望ましいステージ化プログラムの基準として，もっとも自然かつシンプルな基準は，以下のものであろう．

3. 3 Linger らの手法の問題点計算できる箇所はなるべく早いステージでLinger らの手法は 1 つ問題点がある．それは出力されるプログラムが常に一意に決まるとは限らない(等式だけでなく不等式が残る) ということである．
例 1.

計算する．
これは，部分計算においても採用されている考え方である．しかし，ステージ化計算では，高階関数の型がステージ化と複雑にからむことがあるため，この

λx. if x = 1 then 0 else 1(8)

int -> int code(9)

考え方だけで，ステージ化の結果を，つねに一意的に決めることはできないが，ある程度の指針とはなる．

そこで，本章では，まず，この基準にしたがって構築

ルールで起こる最小化問題には必ず下限が存在し，最したアルゴリズムを紹介する．そのあと，別の基準に小化が可能である．App ルールも同様である．よっついても論じる．

て，Min(n+j) と Min(n+a) は，必ず解を持つ．

4. 1. 1 条件式についての解析

4. 1. 4 問題点

条件式 (if-then-else 式) を含むプログラムにおいて，条件式と関数適用式に対する最小化で，解が一意に上記の基準でステージ化プログラムを一意に決める
事を考える．

if e1 then e2 else e3

決まるとは限らない．例えば，(λx.(λy.y) x) 10 および int code
(12)に対して最小化問題を解くと，

式 (12) において「計算できる箇所はなるべく早いス.<(λx.(λy.y) x) 10>.

テージで計算する」とは，e1 を計算できるステージを(λx..<(λy.y) x>.) 10

最小化することと同値である．ここで以下は IF ルーという 2 つの解は，望ましい解から排除すること

ルと Ann ルールを組み合わせたものである．(制約 Cができる．なぜなら，この 2 つは，0 ステージで計算は省略した．)

できるラムダ式が計算されていないからである．し[Ann,IF]Γ ⊢n+j e1 : bool Γ ⊢n+j e2 : t−j Γ ⊢n+j e3 : t−jΓ ⊢n+j (if e1 then e2 else e3 ) : t−jΓ ⊢n (if e1 then e2 else e3 )j : t
e1 が計算できるステージは，e1 が bool 型になるステージであるので n + j である．つまり n + j の最小化を行うことで本研究が提案する基準で望ましい
コードを生成できる．

4. 1. 2 関数適用式についての解析
条件式の場合と同様にルールから最小化問題の抽かし，(λx.(λy.y) x) .<10>.
(λx.(λy.y) .<x>.) 10(λx.(λy..<y>.) x) 10という 3 つは，いずれも，最小化問題の解である
ので，どれにするかが決まらない．
よって，本手法では，望ましいと思われるコードをすべて出力し，その最初の 1 つを出力する．その出力に不満がある場合は，2 つ目，3 つ目等を示し，どれを採用するかは人間が判断することとする．

出を行う．

[Ann,App]Γ ⊢n+a e2 : s Γ ⊢n+a e1 : (s → t−a )Γ ⊢n+a (e1 e2 ) : t−aΓ ⊢n (e1 e2 )a : t
このルールから (n+a) の最小化を行なえばよいことがわかる．

4. 1. 3 最小化問題の解の存在
整数を値として持つ式 p を最小化するという問題
を Min(p) と記述する．上記の解析により，望ましい解を求める問題は，条件式では Min(n+j), 関数適用
式では Min(n+a) を解くことに帰着された．
ここでは，最小化問題を解く前の連立不等式が解を持てば，これらの問題の解が存在することを示そう．

Annotation はすべての term に付くので，IF ルー
ル適用前に必ず Ann ルールが適用される．その際

n + j >= 0 という制約を追加している．そのため IF

4. 2 第二の方法
前節とは異なる形で，望ましいステージ化プログラ
ムを 1 つに絞ることを考える．これは，束縛時解析をおこなう型推論アルゴリズムに依存した基準である．
型推論木の下から上に導出を行なう型推論
において，先に導入された Annotation 変数の値を最小化する．

Linger らのアルゴリズムでは，すべてのプログラ
ム・ポイント (プログラムを抽象構文木で記述した
ときの，木のすべての節および葉) に対して相異なる Annotation 変数を付加するが，外側のプログラ
ム・ポイントに対する Annotation 変数を先に導入するものとする．なお，(抽象構文木の上で) 先祖ー
子孫関係にない 2 つのプログラム・ポイントに対する Annotation 変数は，どちらが先かを一意的に決められないが，ここでは，実装されたアルゴリズムがAnnotation 変数を作成する順番に従うものとする．
この方法では，すべての Anotation 変数について辞書式順序により最小化をおこなうので，最小化問題の解が (存在すれば) 一意的であることは自明である．
この方法に対して，以下の疑問が自然に発生する．
これらの疑問に対しての厳密な解答は，本稿執筆時点では得られておらず，将来課題である．

• 最小化問題の解がいつでも存在するか．
Annotation 変数は (型に対するものでない場合)
負の値を取ることができるので，最小化問題の解が存在することは証明を要する．

• 上記の基準は，前節における条件式や関数適用

fun s k -> k s a
let bind a f =fun s k -> a s (fun s’ x -> f x s’ k)

ret はコード型を受け取り，関数の形で返す．bind
は a の結果を新しく関数の引数として束縛する．
以下は，Gibonacci 関数に対して自動ステージ化を行って得られたステージ化プログラムである．
let rec gib_s x y n =if n = 0 then x
else if n = 1 then yelse .< .~(gib_s x y (n-1))+ .~(gib_s x y (n-2))>.

これを MS が適用可能な形にするため，以下の 3ステップの書き換えを行う．

式に対する解析結果と両立するか．

ステップ 1. 非カリー化 (引数の書き換え)

前節の議論において，条件式の j, 関数適用式のMS を適用するためには，非カリー化して引数をタa が，本節における最小化の対象となり，これら

プルにする必要がある．

を最小化するということは，前節と同様の最小化ステップ 2. Open Recursion への書き換えをおこなっていることに相当すると考えられる．

再 帰 関 数 let rec g x = ... (g a)... を ，

この節の方法で最小化問題を解くことは容易であ

let g’ f x = ... (f a) ... に変形し，この g’り，上記疑問が全て肯定的に解決されたら (証明できに Y コンビネータを適用する形で再帰呼び出しを行たら)，本研究の手法としてこちらを採用する予定でなうものを Open Recursion と呼ぶ．Monadic Stag-ある．

ing では，関数の再帰呼び出しをおこなう際にメモ化をするため，Open Recursion の形を採用している．

5 Monadic Staging の導入の自動化

そこで，対象となる関数における let rec の定義を

3. 2 節で Monadic Staging(MS) について説明した．

Open Recursion の形に変更する．

MS はステージ化コードを書き換える必要があり，まステップ 3. モナドを使う形への書き換え

た，メモ化のための key の設定を人手で行わなけれMS を適用した (Open Recursion の形になった) 関

ばならない．本研究では，ステージ化コードの生成の数をモナド上の関数に変形する．すなわち，関数の返段階で，自動的に MS を行なう仕組みを導入し，生り値を ret で置き換え，(Open Recursion 化前のプ

成コードの効率化を図った．

ログラムで) 再帰呼び出しを bind を用いた形に置き換える．

5. 1 コードの書き換え
MS は，モナドを用いて (コード実行時の) メモ化を行なう．ここで使うモナドは，状態と継続を組み合せた形で，’a monad =state ->
(state -> ’a -> answer) -> answerという型を持ち，これに対応した ret(return) と bind以上の手順を gib の例に適用すると，MS に対応した以下のステージ化コードを得る．
let gib_ms f (n, (x, y)) =if n = 0 then ret x
else if n = 1 then ret yelsebind (f ((n-2), (x, y))) (fun r1 ->bind (f ((n-1), (x, y))) (fun r2 ->ret .<.~r2 + .~r1>.))

メモ化を組みこんだ Y コンビネータをこの (再帰は，OCaml では以下のように定義される [6]．

を行わない) 関数に適用して不動点を得ることにより，

let ret a

メモ化をおこなうステージ化された gib 関数が得ら

=

れる．

M (k) =
m + 1 + k−1 C1 · m+1 C2 + k−1 C2 · m+1 C3

5. 2 key の設定
MS におけるメモ化は，関数の引数の一部を key と+... + k−1 Ck−2 · m+1 Ck−1m+1 Ck + M (k − 1)

し，その key に対応した値をメモ化するテーブルを蓄

n が増えていくごとに，爆発的に組み合わせが増ええる．その際，key の設定は人手で行う必要があったていくのがわかる．例えば，3 ステージの出力で，ifが，本研究では，前節での引数の書き換えにより，そ式が 4 つネストされているプログラムでは 35 通りのれぞれの引数が静的か動的かわかっているため，静的候補が出力されてしまう．しかし，本研究で提案する

引数 (すべて) を key として扱うことで自動的に key

基準により，if 式で複数の出力を候補とする問題は一設定をした．

意に定めることに成功したため，n,m がいくつであっても出力されるプログラムは 1 つである．

6 検証

本研究では，App 式に関する部分で，出力を一意

本研究によってどのくらい出力候補が減ったのかをに決めることができなかった．1 ステージの出力では，p を関数適用の数とすると，Linger らの手法の出力

検証する．
まず，Linger らの手法で，ネストした if 式を含む
プログラムに対する解侯補の個数を計算する．

m を if のネストの回数，n を出力ステージ (生成されるステージ化プログラムの出力となるコード型における code キーワードのネストの数) とする．ただし，ここでは，簡潔さのため，if 式がネストするのは候補が 2 · p + 1 個に対し，本研究では p + 1 個の出力になる．しかし，n が大きくなると if 式と同様に，出力が爆発的に増えてしまうため，増える量に対して減らすことのできる量はそこまで大きくない．
上記の考察を，gib などのプログラム例に適用した結果を表 1 に示す．

then-part のみとする．(else-part には if 式は含まれ

表1ないものとする．) このとき，最大で，a0 + a1 + ... + am ≤ n

ステージごとの出力候補数(13)を満たす非負整数の列 a0 , a1 , · · · , am の組み合わせの個数に相当するプログラム侯補ができる．

if 数

ap 数

n=1

n=2

n=3

Opt

m を一定とし，出力ステージ n に関する関数とし

gib

2

14

3

6

10

1

て，プログラム侯補の個数 (最大値) を表現したもの

lcs

3

32

4

10

20

1

を M (n) とする．

ks

3

34

4

10

20

1

ss

5

26

6

21

56

1

M (1) =
m+1

上の表 1 は出力ステージごとの出力候補数である．
「n=1」等は Linger らの手法で出力ステージが k のM (2) =
m + 1 + m+1 C2 + M (1)ときの侯補数であり，Opt は本研究の出力数を表す．
本研究での出力数は出力ステージに無関係であるので表示していない．また，gib は gibonacci 関数，lsc は

M (3) =
m + 1 + 2 · m+1 C2 + m+1 C3 + M (2)longest common subsequence 関数，ks は knapsack関数，ss は subset sum 関数を表す．
この表からわかるように，本研究は if 式について

M (4) =
m + 1 + 3 · m+1 C2 + 3 · m+1 C3 + m+1 C4 + M (3)の絞り込みを行っただけにもかかわらず，現実のプログラム例では，常に 1 つに絞り込みができていることがわかる．

なども扱える必要がある．
本研究の最終目標は高性能計算などの分野で，コー

7 まとめと今後の課題

ド生成における様々な最適化をエキスパートが記述で本研究では，人手で作成したステージ化プログラ

きるようにすることで，人手で高性能コードを作成す

ムに近いものを得ることを目的に，ステージ化の自るための作業を大幅に軽減し，さらには，全自動で最動化を行った．具体的には，Linger らの手法を実装

適で信頼性の高いコードを生成することである．

し，本研究が提案するコードの望ましさの基準をもとに最小化問題を解くことで，望ましいステージ化プ

参 考 文 献

ログラムを生成した．また，その手法で生成したコー[ 1 ] Baris Aktemur, Yukiyoshi Kameyama, Oleg
Kiselyov, Chung-chieh Shan, Shonan Challenges for
Generative Programming, PEPM2013, pp.147-154,
2013.
[ 2 ] Gilles Dowek, Jean-Jacques Levy, Introduction
to the Theory of Programming Languages, Springer,2010.
[ 3 ] Jason L Eckhardt, Roumen Kaiabachev, Kedar
N Swadi, Walid Taha, and Oleg Kiselyov, Practical
Aspects of Multi-stage Programming, unpublishedmanuscript, 2004.
[ 4 ] Oleg Kiselyov, Modaular, Convenient, Assured
Domain-Specific Optimizations,
APLAS 2012,
poster presentation, 2013.
[ 5 ] Nathan Linger, Tim Sheard,
Binding-Time
Analysis for MetaML via Type Inference and Constraint Solving, Tools and Algorithms for the Construction and Analysis of Systems, 2004:266-279.
[ 6 ] Kedar Swadi, Walid Taha, Oleg Kiselyov, Staging Dynamic Programming Algorithms, unpublished manuscript, 2005.
[ 7 ] Walid Taha, A Gentle Introduction to MultiStage Programming,
Domain-specific Program
Generation 2003, 2003:30-50.

ドに Monadic Staging を組み込む部分も自動化した．
また，Linger らの手法と比べて，どの程度候補を減らすことができるのかを検証した．
今後の主な課題は，以下の 3 つである．(1) 領域に応じた最適化; 適当な領域特化言語 (DSL) を導入し，その DSL で記述された最適化を自動的に組み込むことが考えられる．(2) 生成コード量の制御; 自動ステージ化で生成されたコードは，計算できる箇所を計算しすぎる (再帰の全展開など) ことでコード量が爆発的に増える，という問題が発生することがある．
それを避けるために，領域ごとに最大展開量を設定できるようにすることで，全体的にもっとも効率のいいコードを生成したいと考えている．(3) 対象言語の拡張; Linger らのアルゴリズムは Run に対応せず，また，let 多相にも対応していない．また，高性能計算の具体例を対象とするためには，配列や浮動小数点型