AS3で遅延評価を実装してみました

最近読んでいるSICPの理解度を確かめるために、AS3で遅延評価を実装してみました。

遅延評価を理解する前に、AS3の関数呼び出しが値呼び出しであることを理解しておく必要があります。

値呼び出しというのは、例えば、

function square(x) {
	return x * x;
}
function ret2() {
	trace('called ret2');
	return 2;
}
square(ret2());

というコードがあった場合、最初にret2()が呼び出されてからsquare()の呼び出しが行われます。なので、実行結果は、

called ret2

となります。

仮にAS3が値呼び出しではなく、名前呼び出しであったとしたら、ret2()が評価される前にsquare()の評価がはじまり、途中で次のような状態になります。

return ret2() *ret2();

なので、実行結果は、

called ret2
called ret2

となります。

関数の呼び出し方法は、処理系によって決まっているため処理系のサポートがない限り変更することができません。
しかし、値呼び出しの処理系でも遅延評価のテクニックを使えば名前呼び出しと同じ順序で評価させることができます。

具体的な方法は、五十嵐先生の講義資料を参考にしました。

以下は、遅延評価の説明部分の引用です。

関数定義において，本体中でパラメータのいくつかを使用しないことがありえる．このとき，呼出し側で対応する実引数を評価するのは無駄である．実引数の評価が止まらない場合には，問題ですらある．

mini Schemeのように，関数が第一級の値である場合には，無駄な引数を評価しないために，パラメータ無しの関数として渡し，関数内部で使うときに初めて関数適用を行って引数の評価を行うというプログラミングで，この問題を避けることができる．このように，評価を遅らせるために用いられるパラメータ無しの関数を thunk と呼び，thunk を構成・評価することを，それぞれ freezing, thawing と呼ぶ．

ということで、schemeで遅延評価の実装方法が説明してあります。

(let ((p (lambda (x y) (* 2 x))))
   (p (+ 2 4) (fact 150)))

のようなプログラムを，機械的に実引数を freeze し，パラメータが使われているところで thaw するようにして，以下のように

(let ((p (lambda (x y) (* 2 (x)))))
   (p (lambda () (+ 2 4)) (lambda () (fact 150))))

のように書き換えることができる．(ここでは fact は階乗を計算するプリミティブと考えよ．)これにより，結果が使われないが時間のかかる階乗の計算をせずに，プログラムが実行される．

schemeに慣れていないと分かりづらいですが、要するに引数を匿名関数でくくって、関数内では必要になったときに引数の関数を呼び出し値を取得すれば遅延評価になるということです。

このコードをactionscriptで書くと次のようになります。

まずはfactの実装。

function fact(x) {
	if ( x == 0 ) {
		return 1;
	}
	else {
		return x * fact(x - 1);
	}
}

関数pの遅延評価なしバージョン

var p = function (x, y) {
	return 2 * x;
};
p(2 + 4, fact(150));

このバージョンだと、fact(150)の結果は使われないのに評価は行われます。

こちらが、遅延評価ありバージョン

var p_lazy = function(x, y) {
	return 2 * x(); // 引数を関数適用し、値を評価する(thawing)
};
p_lazy(function() { return 2+4;}, function() { return fact(150); }); // 引数を匿名関数で包む(freezing)

このバージョンでは、関数p_lazy()の第２引数は無視されてfact(150)は評価されません。

ここまで読むと、「で、これが何の役に立つの？」と疑問に思った人も多いと思います。
正直私も煩雑なだけでほんとに役立つのか？と思ってしまいました。

とは言いながらも色々考えてみた結果、
遅延評価が効果を発揮するのは、下記の２つの条件を満たしている場合のように思いました。

1. 引数の値が関数内部で使われるかどうかが状態によって変化する
2. 引数の値の取得処理に時間がかかる（計算量が多いなどの理由により）

具体的な例は、SICPを読み進めれば出てくるのだろうと思いますが今はわかりません。。。

おまけ

SICP問題1.5の復習

AS3は値呼び出しの処理系なので以下のコードを実行すると、関数testが呼び出される前に関数pが呼び出されてスタックオーバーフローになります。

function p() { p(); }

function test(x, y) {
	if ( x == 0 ) {
		return 0;
	}
	else {
		return y;
	}
}

test(0, p());

で、この問題を遅延評価に書き直すと以下のようになります。

function p() { p(); }

function test(x, y) {
	if ( x() == 0 ) {
		return 0;
	}
	else {
		return y();
	}
}

test(function() { return 0;}, function() { p(); });

これだとスタックオーバーフローが起こらないで終了します。

参考

• LazyForce(いげ太のブログ)
• id:amachangさんがjavascriptで遅延評価についての記事を書いてたんですね。参考になりました。

DisplacementMapFilterを使って波紋を表現する

DisplacementMapFilterを使って波紋を表現する

今回も前回に引き続きDisplacementMapFilterを使ったエフェクトに挑戦してみました。今回は、Macのウィジェットを追加した時のエフェクトみたいな波紋を作ってみたいと思います。

少し分かりづらいのですが、上の画像はMacのウィジェットマネージャを起動してウィジェットを追加したときに背景が波紋で揺れるエフェクトが出た瞬間をキャプチャしたものです。
このような波紋を作るには、下記のような周期的かつ滑らかに変化する置き換えマップが必要になります。

しかし、PerlineNoiseでこのような画像を生成する方法を思いつかなかったので別なアプローチを試すことにしました。

波紋用の置き換えマップ生成法（その１）

まずはじめに試したのは、単純にdrawCircle()関数で円を描きそれをBlurFilterでぼかすという方法です。時間の経過とともに、半径を大きくしアルファ値を0に近づけてみました。

一見良さそうに見えるのですが、よく観察してみると色が滑らかに変化していないため白と黒が切り替わっているエッジが目立ちます。
また、DisplacementMapFilterを適用させる画像によっては変化が目立ちません。
動きが早く大きさも小さければあまり気になりませんが、今回は緩やかに大きく動くエフェクトを作りたいので他の方法を考えました。

波紋用の置き換えマップ生成法（その２）

次に試したのは、Sine関数で描かれる曲面のz座標をすべての点において計算し、その値をピクセルの色とする方法です。この方法では置き換えマップ上のすべての点が計算によって求められます。
そのため置き換えマップのサイズが大きくなると計算量が増えるという問題が生じます。

まずは、計算量のことは考えずに方法１と比較して良いエフェクトが得られるかどうかを確認してみました。

これが生成された置き換えマップ用のBitmapDataになります。その１と比べて変化が滑らかになったためエッジが目立たなくなったのが確認できます。
コードは以下の通りとなります。

// 下記の式で与えられる曲面のz座標を青成分として描画する 
//
// z = 127 * sin(A(l - t) - π) + 128
// l = sqrt(x * x + y * y)
//
for (var i:int = - bmpHeight / 2; i < bmpHeight / 2; i++ )
{
	for ( var j:int = - bmpWidth / 2; j < bmpWidth / 2; j++ )
	{
		var l:Number = Math.sqrt(i * i + j * j); // (1)
		var angle:Number = Math.PI * (l - time) / bmpHeight * frequency; // (2)
		var h:int = (l - time) / bmpHeight / 2 * frequency; //(3)
		var attenuationFactor:Number = (bmpWidth / 2 - l) / (bmpWidth / 2); // (4)
		var density:uint = 0;
		if ( (-frequency <= h) && (h < 0) && l < bmpWidth / 2)  // (5)
		{
			density = attenuationFactor * (Math.floor(127 * Math.sin(angle - Math.PI / 2)) + 128);// (6)
		}
		bmpData.setPixel32(j + bmpWidth / 2, i + bmpHeight / 2, 0xFF000000 | density); // (7)
	}
}

1. これから色を求める点の中心からの距離
2. 時刻timeにおける地点(j, i)の角度（ラジアン値）
3. 時刻timeにおける地点(j, i)の何周期目かを計算
4. 地点(j,i)における減衰率
5. 0からfequencyで指定された周期のみを表示する
6. 色を計算
7. 求めた色を点に設定

以上で期待通りのエフェクトに仕上がっているのですが少しパフォーマンスが気になりました。

試しに400x400のサイズで実行時間を計測したところ、私の環境では1フレームあたり約140msかかることが分かりました。

計算量を減らすための工夫：Sineの周期性を使い1/4だけ計算し回転とコピーで補完する

Sineは変化が周期的なため中心から４つに分割して1/4を計算してしまえば、あとは回転とコピーをして求めたい画像を生成することができます。
どの部分から計算しても良いのですが、今回は右下部分の計算から開始することにしまいた。

// 実装方針：Sineの周期性を利用し1/4だけ計算し残りの3/4は回転とコピーで求める
//  1. 描画領域の中心点から４等分し、右下部分のみ計算する
//  2. 右下部分を残り部分にコピーする
var lastn:uint = bmpHeight / 2;
for (var i:int = 0; i < lastn; i++ )
{
	for ( var j:int = 0; j < bmpWidth / 2; j++ )
	{
		var l:Number = Math.sqrt(i * i + j * j);
		var angle:Number = Math.PI * (l - time) / lastn * 2 * frequency;
		var h:int = (l - time) / lastn * frequency;
		var attenuationFactor:Number = (bmpWidth / 2 - l) / (bmpWidth / 2);
		var density:uint = 0;
		if ( (-frequency <= h) && (h < 0) && l < bmpWidth / 2)
		{
			density = attenuationFactor * (Math.floor(127 * Math.sin(angle - Math.PI / 2)) + 128);
		}
		bmpData.setPixel32(j + bmpWidth / 2, i + bmpHeight / 2, 0xFF000000 | density);
	}
}
	
// 右下の1/4を左下にコピーする
var rm1:Matrix = new Matrix();
rm1.rotate(Math.PI / 2);
rm1.translate(bmpData.width, 0);
bmpData.draw(bmpData, rm1, null, null, new Rectangle(0, bmpHeight / 2, bmpWidth, bmpHeight / 2));

// 下の1/2を上にコピーする
var rm2:Matrix = new Matrix();
rm2.rotate(Math.PI);
rm2.translate(bmpWidth, bmpHeight);
bmpData.draw(bmpData, rm2);

この結果、１回BitmapDataを更新のに要する時間は平気で40ms程度となり、以前の約1/3になりました。

最終的にできあがったのがこれになります。

まとめ

• 置き換えマップをsetPixel32()を使って動的に生成することができました
• 動的生成に使う関数の周期性などを利用して計算量を少なくすることができ、パフォーマンス向上につながることが確認出来ました
  • 今回のケースでは関数がx軸対称かつy軸対称だったため、計算量を1/4に減らすことができました。しかし、データのコピーに時間がかかるため処理時間は1/3程度の短縮となりました。

ダウンロード

• パルスのソース一式（動かすにはTweenerが必要です）
• Sineカーブのソース一式

TODO

• 方法その２でにてその１と同じように任意の点から波紋が生成されるように修正する
• 波の干渉を再現する

参考

• DispalcementMapFilterとPerlineNoiseの使い方
• Tweener

TextFieldの行間をマイナスに設定した場合の注意

TextFieldの行間は、TextFormatオブジェクトのleadingプロパティで指定出来ます。フォントサイズを大きくした場合、文章の見栄えを整えるために行間をマイナスに指定することがたまにあります（フォントサイズを大きくすると境界枠とグリフの間の余白が目立つので）。
その際、TextFieldのautoSizeプロパティが"none"以外に設定されている場合は注意が必要です。

TextFieldの行間をマイナスに指定し、autoSizeプロパティをデフォルトの"none"以外に設定するとテキストの下端が切れてしまいます。

以下、確認用のコードです。

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.text.TextFormat;
    import flash.text.TextFieldAutoSize;

    public class Test1 extends Sprite
    {
        private var text1:TextField;
        private var text2:TextField;
        public function Test1()
        {
            text1 = new TextField();
            text1.x = 0;
            text1.y = 0;
            text1.height = 15;
            text1.width = 500;

            text2 = new TextField();
            text2.x = 0;
            text2.y = 20;
            text2.height = 15;
            text2.width = 500;

            var fmt:TextFormat = new TextFormat();
            fmt.size = 10;
            fmt.leading = -5;
            text1.defaultTextFormat = fmt;
            text1.text = "このTextFieldはleading=-5に設定されています。autoSizeの指定をしていません。";

            text2.defaultTextFormat = fmt;
            text2.autoSize = TextFieldAutoSize.LEFT;
            text2.text = "このTextFieldはleading=-5に設定されています。autoSizeは、LEFTに指定されています。";

            addChild(text1);
            addChild(text2);
        }
    }
}

コンストラクタ内でまず、TextFieldのインスタンスtext1とtext2を作成し、二つとも同じ書式で行間が-5に設定してあります。
問題のautoSizeプロパティはtext1がデフォルト値(none)でtext2がLEFTに設定されています。そのため、下側に表示されているtext2の下端が切れています。

何故このような現象が起こるのかというと、おそらくautoSizeが指定されているときのTextFieldのheight(というか、描画領域の高さ）の計算式がおそらくフォントの高さ + 行間になっているのが原因なのではないかと思います。
２行目の描画開始位置をleadingを踏まえて決定すればいいだけだと思うのですが、そうは実装されていないです。無念です。

そう実装されているものは仕方ないということで、次に、どういう作業手順でこの問題が発生しやすいのかを検討してみました。
というか、私がこの問題にたどりついた作業手順は次の通りです。

1. Flash CS3でTextField(A)を設置しフォントサイズを大きくする
2. 行間をマイナスに設定し、見栄えを整える
3. もう一つのTextField(B)を設置し、フォントサイズを小さくする
4. (B)をダイナミックテキストに指定しアクションスクリプトで操作する

この手順だとすばらしいことにTextField(B)を設置した時点で前のTextField(A)の設定がコピーされています。そのため、行間を指定していたことに気づかずアクションスクリプトでautoSizeを設定すると文字の下側が消えます。

しかも、この行間の設定がプロパティウィンドウの中でも分かりづらい位置にあるので設定されていることに気がつきづらいです。

この状態では、行間の設定は隠れているので見えません。

見事に数時間嵌まりました。

DisplacementMapFilterの動作を理解する

DisplacementMapFilterの動作は理解しづらいので、パラメーターとエフェクトの関連を確認するためのツールを作ってみました。

DisplacementMapFilterとは何か？

DisplacementMapFilter クラスは、指定された BitmapData オブジェクト (置き換えマップイメージと言います) のピクセル値を使用して、オブジェクトの置き換え (変位) を実行します。このフィルタを使用して、MovieClip、SimpleButton、TextField、Video オブジェクトなどの DisplayObject クラスから継承したオブジェクト、および BitmapData オブジェクトにワープ効果や斑点効果を適用できます。

ActionScript 3.0 コンポーネントリファレンスガイドの DisplacementMapFilterクラスの説明から抜粋

このフィルタの特徴は、フィルタ適用による元画像の変形の度合いをBitmapData(マップイメージ)によって指定するところにあります。元画像の各ピクセルがどのぐらい移動するのかは、マップイメージの各ピクセルのチャンネルの値によって決定されます。したがって、緩やかなグラデーション画像をマップイメージにした場合、画像は緩やかに変化します。また、X方向とY方向で別々なチャンネルによって変位を指定することが可能です。例えばX方向の変位量の指定には青を使い、Y方向には赤を使うと言ったことが可能です。

具体的に、DisplacementMapFilterは次の９つのプロパティを持っています。

• mapBitmap
• mapPoint
• componentX
• componentY
• scaleX
• scaleY
• mode
• color
• alpha

mapBitmapがマップイメージとなり、mapPointで指定されたマップイメージ上の点から変位量の計算が行われます。componentXとcomponentYはどの変位量を決定するチャンネルの指定です。

エフェクトに大きな影響を及ぼすのは、残りの５つのプロパティで特にscaleXとscaleYの値によって見た目が大きく変わります。scaleXとscaleYはそれぞれ、X方向とY方向の変位量の倍率になっています。そのため、この値を大きくすると大きく変形します。
例えばscaleXを大きくすると、X方向の変化が大きくなります。

残りのプロパティ、mode、color、alphaについては次に紹介するツールを実際に使って確認してみて下さい。

DisplacementMapFilterを実際に使ってみる

このフィルタを適用した結果画像を想像できるようになるには、慣れるしかないと思います。ということで、好きにパラメーターを変更して動作確認をするためのツールを作ってみました。

このツールでは、前回作ったPerlinNoiseを使ってマップイメージを生成しています。アニメーション表示には、HundredthMonkeyさんの手法を参考にさせてもらいました。

例１：波打つエフェクト

PerlinNoise( baseX=100, baseY=100, octaves=5) Filter( scaleX=10 scaleY=10)

例２：輪郭戦をぼかすエフェクト

PerlinNoise( baseX=5, baseY=5, octaves=2) Filter( scaleX=5 scaleY=5)

追記：「アニメーションさせる」チェックボックスのデフォルト値をオフにしました。アニメーションさせるとかなり重いです。

ソースコード

ここからダウンロードできます。

参考にしたサイト

• 百匹目の猿 Flash CS3で水面っぽい画像表示 アニメーション表示の方法を参考にさせてもらいました
• DMFチュートリアル1 このサイトのチュートリアルをみてDisplacementMapFilterの基本動作を理解しました
• DMFチュートリアル2
• DMFチュートリアル3

今後の予定

• エフェクトのコア部分をモジュール化する
• ツールでパラメーターを設定するとコードスニペットが生成されるようにする（Reflectクラスみたいな感じ）

getURL()の挙動を調べる（その１）

とある事情で受け取ったflaファイルに、次のようなactionscriptが記述されていました。

getURL('javascript:doSomething()');
getURL('./somewhere.html');

これをパブリッシュすると、２つ目のgetURL()の呼び出しだけが実行されるのが確認できます。

どうして、そのような挙動になるのか動作検証をしながら原因を究明していこうと思います。

そもそもgetURL()ってどういう関数なのか？

まずはFlash CS3 ドキュメンテーションの説明を見てみましょう。

特定の URL からウィンドウにドキュメントをロードしたり、定義済みの URL に存在する別のアプリケーションに変数を渡したりします。

つまりこの関数を使うと、Flashが読込まれたwindowに別なURLのhtmlを読込むことなどができます。また、"javascript:"疑似プロトコルを指定するとswfがロードされたhtml内のjavascript関数を呼び出すことが出来ます。

疑問その１：getURL()は非同期呼び出しか？

getURL()の仕様がわかったところで、そもそもgetURL()は、非同期呼び出しなのか？という根本的な疑問から確認していきたいと思います。最初のコードでgetURL()が呼び出された順番通りに実行されていないことからgetURL()の呼び出しは非同期呼び出しである可能性が高いですが、念のため動作確認を行います。

確認方法

FlashからgetURL()を使って、処理時間のかかるjavascriptの関数を呼び出します。その直後にactionscriptの関数を記述し、その挙動を調べます。
もしjavascriptの処理が終了後にactionscriptの関数が呼び出された場合はgetURL()の呼び出しは同期呼び出しだと言えます。逆に、javascriptの処理が完了する前にactionscriptが呼び出された場合は、getURL()はjavascriptの処理を待たないで返ってきているので非同期呼び出しだと言えます。

この確認のために次のようなjavascriptとactionscriptを書いてみました。

javascriptは次の通りです。func1()は、引数で渡された整数のフィボナッチ数を計算してalertで表示します。

    function fib(n)
    {
        if ( n < =2 ) return 1;
        return fib(n - 1) + fib(n - 2);
    }

    function func1(num)
    {
        var ret = fib(num);
        alert('func1: fib(' + num + ')=' + ret);
    }

これに対して、Flash側は次のようなものを作りました。

ステージ上に、求めるフィボナッチ数を入力するテキストフィールドと「フィボナッチ数を計算する」ボタン、メッセージを表示するテキストフィールド、メッセージのクリアボタンの４つを配置します。
以下は、「フィボナッチ数を計算する」ボタンが押されときのイベントハンドラです。

on(release)
{
	var num:Number = parseInt(fibnum.text);
	if ( num > 0 )
	{
		getURL('javascript:func1(' + num + ')');
		msg.text = "after func1()";
	}
}

まず、テキストフィールドに入力された値をNumberに変換し0より大きければgetURL()を呼び出します。getURL()の引数にはさきほど変換した値を引数としたfunc1()を呼び出すためのURLを指定します。

また、getURL()の呼び出し直後にメッセージをテキストフィールドに書き込んでいます。

動作結果

実際にここから動作を確認することができます。（※注意　３５とか大きい数字を入力するとブラウザが固まる場合があるので自己責任で御願いします）

テキストボックスに適当な数値（私の環境では２５〜３０くらいが丁度でした）を入力して、何度か入力してみるとFlash側のメッセージ表示が先に行われ、その後、javascriptのalertが表示されることが確認できます。つまり、getURL()の呼び出し後すぐに次のスクリプトの処理に移っておりgetURL()の呼び出しは非同期呼び出しだということがわかります。

結論

getURL()は非同期呼び出しで間違いないようです。しかし、最初のコードの挙動を説明するにはまだ検証が足りません。今後、何回かにわけてこの問題を調べて行こうと思います。

ダウンロード

ソースファイル一式は、こちらからダウンロードできます。

補足

FireFoxで動作を確認した場合は、alertが先に表示される時があるようです。ただ、Flash側が先に呼び出されることもあることからgetURL()の呼び出しが非同期呼び出しであることは間違いありません。しかし、getURL()を呼び出した後の実行順序が何故ブラウザによって異なるのかは今のところ原因不明です。

参考URL

1. Flash CS3 ドキュメンテーション getURL()のヘルプです
2. 404 Blog Not Found フィボナッチ数列を求めるきちんとしたアルゴリズムが紹介されています

BitmapData.perlinNoise()のサンプル

BitmapDataクラスのperlinNoise()メソッドの実行結果を確認するためのFlashを作成してみました。perlinNoise()メソッドは、ランダムな雲模様や縞模様を作成する際に使います。通常は、DisplacementMapFilterと組み合わせるなどして利用し、単体で利用することは少ないです。

BitmapData.perlinNoise()の動作確認

このサンプルでは、右側のコントロールで指定した値がPerlinNoise()に渡され左側のプレビュー領域に表示されます。

使い方１：雲模様を作る

BaseX、BaseYの値を1以上に設定するとノイズは雲模様になります。

使い方２：縞模様を作る

BaseXの値を0にし、BaseYを1以上に設定すると縦の縞模様になります。逆にBaseXを1以上にし、BaseYを0にすると横の縞模様となります。

サンプルファイルのダウンロード

紹介したコードは、ここからダウンロードできます。展開するとflaファイルとasファイルが同梱されています。flaファイルのコンパイルにはFlashProCS3以上が必要です。

参考

1. にゃあプロジェクト - ウェブログ - BitmapDataでノイズ生成 (2) 私が作成したサンプルよりもっと良いサンプルです＾＾；
2. Flash CS3 ドキュメンテーション BitmapData.perlinNoise

SICP 問題1.6の解答

読書会のメンバーmahata氏を見習って、解答の一部をアップしてみることにしました。まずは問題1.6の解答です。

new-ifの評価が始まる前に引数が評価され、その中でsqrt-iterが再帰呼び出しされているので無限ループになる。

解答の説明をする前にまずは、この問題でとりあげている関数の定義を以下に示します。

(define (new-if predicate then-clause else-clause)
        (cond
                (predicate then-clause)
                (else else-clause)
        )
)
(define (sqrt-iter guess x)
        (new-if (good-enough? guess x)
                guess
                (sqrt-iter (improve guess x)
                        x)
        )
)

次に、(sqrt-iter 1.0 2)を例に、実際にnew-ifの評価がいつまでも始まらない様子をステップごとに見て行きます。（説明に不要なステップは飛ばしてます）

(sqrt-iter 1.0 2)
=>
(new-if (good-enough? 1.0 2)
        1.0
        (sqrt-iter (improve 1.0 2) 2)
)
=>
(new-if #f ;; (good-enough? 1.0 2)を評価
        1.0
        (sqrt-iter 1.5 2) ;;(improve 1.0 2)を評価したが、sqrt-iterをまだ評価できるのでnew-ifの評価に進まない
) 
=>
(new-if #f ;; 
        1.0
        (new-if #f ;; (good-enough? 1.5 2)を評価
                1.5
                (sqrt-iter 1.4166666666666665 2) ;;(improve 1.5 2)を評価するが、sqrt-iterがまだ評価出来る...以下ループ
        )
)

処理系ごとの評価戦略の違いを意識させられる問題でした。引数渡しの方法については、五十嵐先生のページが詳しくて参考になりました。