Elmでやってみるシリーズ13:あらためてシダを描く

間が少しあいちゃいましたが、実は続いていたこのシリーズ、「あらためてシダを描く」です。

f:id:uehaj:20140904230303p:plain

この図形は「バーンズリー(バーンズレイ)のシダ」と呼ばれる有名な図形で、以前各種の言語で実装するのが少し前に流行ったのが記憶に新しいところです。アルゴリズムなどについては詳しくはこちらをどうぞ。

実は、これについては、前にも「「プログラムでシダを描画する」をelmで描画する - uehaj's blog」で作ったのですが、当時はElmを良く知らずに試行錯誤で作ったものなので、現時点での知見をもとにして再度とりくんでみました。

このデモは計算量が大きく、さらにiframeでブログ内にインライン表示すると、なんらかの理由で非常に負荷が高くなる*1ので、今回はインラインデモは割愛します。全画面表示はこちら。

ソースはこちら。
ドラッグすると、パラメータが変更されて新たなシダ図形が描画さます。

ポイント

Main.elm(メイン), Leaf.elm(葉の表示)、Gauge.elm(ゲージの表示)の3モジュールに分割しました。Elmアプリケーションをモジュールに分割するにあたっては、Signalや状態更新の記述を独立性高く分割する方法について考えさせられました。
結論から言うと、
- モジュールに含まれるのが、純粋関数だけの場合には、思考すべきことはあんまりない。何を公開し何を隠蔽するかを吟味しておけば良い*2
- モジュールが状態を保持する場合(そのコードにfoldpを含む場合)、モジュールごとにぞれぞれ以下のようにパートを分けて、単独実行可能なアプリケーションにする(参考:GameSkeleton.elm)。
  - Define constants
  - User input
  - State
  - Update
  - Display
  - puts it all together and shows it on screen.
- その上で、メインプログラムからモジュールの状態更新(nextStateのような関数)、および現在状態を履歴から計算するfoldpの呼び出し等をどう扱うかについては以下から選択する
  - 定時間隔タイマ(fps,..)を使った状態更新が、機能上不要なモジュールであれば、モジュール側がliftしてSignal Elementを返しても良い。つまりイベントハンドラとステート管理をモジュール側で実装しても良い。
  - あるいは、定時間隔タイマを使うモジュールであっても、それを使うMain側が定時間隔タイマを使わないのであれば、ステート管理をモジュール側で実装してもよい。
  - しかし、モジュール側もMain側も定時間隔タイマを使う、もしくはMain側が定時間隔タイマを使うかどうか限定できない(一般ライブラリにする場合はそうなる)のであれば、両方でステート管理を実装すると、少なくとも現行Elmコンパイラが生成するJSコードにおいては性能劣化が激しい。なので、以下のようにする。
    - モジュール側では、
      - そのモジュールに関するStateレコードを定義し公開する
      - nextState, initStateに相当する処理を公開
      - 呼び出す側のMainでは、MainのStateレコードの1つのフィールドとしてモジュールのstateを含める。
    - 呼び出す側のMain側では、
      - nextStateの処理で、モジュール側のnextStateを呼び出し、MainのStateを更新する。
      - foldpを実行するのはMain側のみ。
  - その上で、モジュール側は、自分のfoldpを呼び出すmainを定義しても良い(Mainからは呼ばれない)。こうすることで、それぞれのモジュールを単独でも実行可能なElmアプリにできる。これはモジュールのデモや試験に有用。たとえば今回、赤のゲージはゲージ表示モジュール単独で実行できます(→Gauge.html)し、葉の表示モジュールでは、アニメーションや操作に反応しない葉っぱを表示させています(→Leaf.html)。
リアクティブっつーぐらいで、反応性重要
- このための工夫として、ドラッグ動作中は描画・計算する点の数を減らすようにしました。
- しかし、本来はこれは2モードにならなくても良いはずなのです。しかし残念ながら、現在のElmでは「計算中のマウスカーソル移動イベント」の検出の追随性が問題になります。(後述)
前回同様以下の問題がありました。
- 描画する点列の数nは実行を継続すればするほど増えていくのですが、Elmの標準ライブラリのGraphics.CollageおよびGraphics.Elementなどが提供するグラフィックスモデルは、ペイント系というよりドロー系で、描画されるデータが保持されるというものです。Canvasに書き残る、ということがないです(純粋だというわけですね)。
- この結果、nに比例して描画時間が増えていきます。計算結果の点列([(Int,Int)])は、foldpで累積的に追加していけるので、O(1)なのですが、累積的に伸びた結果であるpoints:[Form]の描画時間はO(1)ではなく、O(n)なのです*3。
- この結果、何も考えないと、放置しておくとだんだん重くなってマウスクリックに反応しなくなります。回避策として以下を実施しています。
  - 1フレームの描画に要した時間を計測し、しきい値(例1秒)を越えるようなら、点列の追加ペースを落す(半減させる)。最終的に追加ペースは0になるので、そうなったら表示内容は収束し変化しなくなる。
  - 他の方針としては、まにあわなくなってきたら解像度とか計算精度落して、とかの戦略もありそうだったが、今回はできなかった。
  - 本来なら、Elm開発者Evanczの論文「Elm: Concurrent FRP for Functional GUI」によれば、Elmには「async」というプリミティブがあり、長い計算処理は適当な粒度で非同期イベントとしてイベントキューに再キューイングを行うことで、「ジャイアントUIスレッドロック」のようなことが起きなくなり、レスポンスを損なわずに長い計算ができるはずでした。しかし現状のElm実装にはasyncプリミティブはまだ実装されていません(そのことや理由も上記論文に書いてある*4し、解決されるべき課題として議論されている。)。(追記)asyncの代用として、Time.delay 0が使用可能だそうですが試してない。
- 問題視してみましたが、例えば10000個とかの固定数で計算を打ち切れば良い話です。これをしなかった理由は、高速なCPUをもったマシンでは多数の点列を表示してゴージャスな表示、遅いマシンでは点数が少なくて、ちょっぴりみすぼらしいが表示はされる、というようなことを実現しようとしたかったからです。点数が多いと綺麗な表示になりますからね。
諸事情によりElm 0.13のスナップショット版を使用。これはリリース版ではないので、自前でコンパイルしたい方は、googlegroupsのelm-discussionを見て適当にダウンロードしてください。