2011年5月30日月曜日

【ドラフト】物理シミュレーションを対象としたDSELについての試み

Abstract


物理シミュレーションを対象としたDSELについての試みを紹介する。このDSELを使うことで、数式に極めて近い形で宣言的に定義を記述するだけで物理シミュレーションのプログラムを書くことができる。

組み込みドメイン固有言語(DSEL)とは


ドメイン固有言語(Domain-Specific Language, DSL)は、特定の問題領域に特化したプログラム言語を提供することでソフトウェア開発の生産性を向上させるものである。DSLは問題領域に適した抽象レベルでの記述を可能にするため、コード量の低減やそれに伴うメンテナンス性の向上といったメリットがある一方、新しく言語を作ること自体が高コストであるという問題がある。

その問題に対する解として、組み込みドメイン固有言語(Domain-Specific Embedded Language, DSEL)は、既存の汎用言語に組み込む形でドメイン固有言語を実装するものである。このアプローチによって、ホスト言語のライブラリやコンパイラ、デバッガ、プロファイラを再利用できるというメリットが得られる。

DSELについては、以下の文献がある。
・Building domain-specific embedded languages
・Huddakの、Haskore music notation
・conal elliot, Functional Image
・金融契約
・Haskell School of Expression

ここでは、物理シミュレーションを対象としたDSELについての試みを紹介する。ホスト言語にはDSELを作るのに向いているという理由でHaskellを選んでいる。

物理シミュレーションを対象としたDSEL


まず具体的な例を挙げよう。簡単な例として、質点の自由落下のシミュレーションを考えてみる。

自由落下を数式で表現すると以下のようになる。

... 数式 ...

提案するDSELを使うことで、質点の位置の時間過程を出力するプログラムを以下のように記述できる。(これは、そのまま実行可能なコードである)

import Process                -- DSELを定義したモジュール

main = print $ take 10 $ process x
                              -- 10ステップ分の位置を表示

x = x0 +: integral' (v * dt)  -- 質点の位置
v = v0 +: integral (a * dt)   -- 質点の速度
a = g                         -- 質点の加速度

x0 = 10.0                     -- 質点の初期位置
v0 = 0                        -- 質点の初期速度
dt = constant 0.01            -- 時間刻み
g  = constant (-9.8)          -- 重力加速度

これだけである。このコードをコンパイルして実行すると、10タイムステップ分の質点の位置が出力される。質点の位置、速度、加速度について、数式そのままの定義を宣言的に記述するだけであることに注目されたい。計算順序について考慮する必要はない。つまり、定義さえ記述すれば「実装」はもはや不要なのである。

もしこれをDSELを使わずにそのまま書くと、「aからvを計算し、vからxを計算する。それをタイムステップごとに繰り返す」という実装を自分で書くことになるだろう。ごく普通の、シミュレーションのプログラムの流れである。

DSELの設計


...DSELの設計について

DSELの実装


...DSELの実装について

DSELの適用可能条件


DSELの課題


・計算効率
 ・持ち上げられているため、コンパイラの最適化が効かない
  →メタプログラミングによるコンパイル時最適化 or コードジェネレータ
・スペースリーク
 ・condAを使うとスペースリークする

DSEL、現状での利用可能範囲


・配列まるごとをProcessの対象とする。そのなかの要素1つ1つは特定のタイムステップについて明示的に記述
 →上記の2つの問題は生じない
 →ただし、フルにDSELで書くことができず、DSELとpure Haskellのハイブリッドでの記述となる
  ・配列まるごと→DSELの世界での記述
  ・配列内の要素1つ1つについて→あるタイムステップについて明示的にpure Haskellの世界に下ろして記述