2011-10-24

Math.floor(x / y) は常に期待する値になるか

数学

x, y は0以上2^32未満の整数とし、yは0でないとする。
数式上に ${...} と書いたらECMAScriptで...の部分を評価した結果の値を表すものとする。${...} の外で a + b のように何か演算を書いた場合、それは浮動小数点数の演算ではなく、数学的な実数の演算を表すものとする

${Math.floor(x / y)}} = floor(x / y) は常に成り立つか？

α = floor(x / y) とおくと α <= (x / y) < α + 1 が成り立つ

直近への丸め

ECMAScriptの四則演算は結果を直近の表現可能な値へ丸めることが定められている。すなわち ⊙を四則演算の記号(+,-,*,/)、aを任意の表現可能な値だとすると ${x ⊙ y} < a < (x ⊙ y) や (x ⊙ y) < a < ${x ⊙ y} が成り立つことはない。

α <= ${x / y} <= α + 1 を示す

α, α + 1 はともに表現可能な値である。
α <= (x / y) より ${x / y} < α となることはない。
同様に (x / y) <= α + 1 より ${x / y} > α + 1 となることもない。
したがって α <= ${x / y} <= α + 1 である。

${x / y} != α + 1 ？

${x / y} != α + 1 の場合、α <= ${x / y} < α + 1 より${Math.floor(x / y)} = α が成り立つ。
よって、${x / y} = α + 1 となることがないことを示せばいい。

(整数) + 1 より小さい最大の浮動小数点数

1以上2未満の区間においては浮動小数点数は小数点以下の桁数が52桁の固定小数点数だと考えることができる。
同様に

2以上4未満では51桁
4以上8未満では50桁
......

であるから

2^n 以上 2^(n+1) 未満では (52 - n) 桁である (0<=n<=52)

したがって

nを自然数、aを整数とし、0<=n<=52, 2^n <= a < 2^(n+1) であるとすると
a + 1 より小さい表現可能な値の最大は a + ((1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n))) である

ここで

f(n) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n)) とおく
aを 0<=a<2^32 の整数として a + 1 より小さい表現可能な値の最大をa + g(a)とする
a != 0 のとき g(a) = f(floor(log2(a)))
a = 0 のとき g(0) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^53) であるから f(-1) に一致する

したがってg(a)は f(-1), f(0), f(1), ..., f(31) のいずれか
f(n)は単調減少であるから31以下のすべての整数nについて f(31) <= f(n) である
よって f(31) <= g(a) は常に成り立つ。

y = 3 で確かめる

ここで y = 3 とおいて ${x / 3} = α + 1 になることがあるかどうか確かめる

(x / 3) = α + (r / 3) と表すことができる。 (r = 0,1,2)

(x / 3)  = α + (r / 3)
        <= α + (2 / 3)
        <= α + f(31)
        <= α + g(α)
         < α + 1

よって (x / 3) <= α + g(α) < α + 1 であり α + g(α) は表現可能な値であるから ${x / 3} = α + 1 となることはない。
ここでは y = 3 としたが (y - 1) / y <= f(31) が成り立つならば ${x / 3} != α + 1 は常に成り立つ。
関数 (y - 1) / y は y > 0 で単調増加し f(31) = (2^21 - 1) / 2^21 であるから y <= 2^21 であるとき ${x / y} != α + 1 は常に成り立つ。

yが大きいときについて考える

y <= 2^21 については示せたから、問題はyが2^21より大きいときである。
g(α)の下界としてf(31)を使ったが、yが大きいときにはαは小さくなるから下界をもっと大きくできるはずである。

ここでf(n) を変形しておく

f(n) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n))
     = Σ[k=1,52-n] (1 / 2)^k  # 初項 1/2, 公比 1/2, 項数 52-n の等比数列の和
     = (1 / 2) * (1 - (1 / 2) ^ (52-n)) / (1 - (1 / 2))
     = 1 - (1 / 2) ^ (52-n)
     = (2 ^ (52-n) - 1) / (2 ^ (52-n))

y >= 2^n とする。 (0 <= n <= 32)

α  = floor(x / y)
   <= (x / y)
    < (2^32 / y)
   <= (2^32 / 2^n)
    = 2^(32-n)

よって α < 2^(32-n) すなわち α <= 2^(32-n) - 1
関数g(a)は単調減少をするから

g(α) >= g(2^(32-n) - 1)
       = f(32-n-1)
       = (2 ^ (52-(31-n)) - 1) / (2 ^ (52-(31-n)))
       = (2 ^ (21+n) - 1) / (2 ^ (21+n))

よって y <= (2 ^ (21+n)) ならば

(x / y) =  α + (r / y)  # rは0以上y未満の整数
        <= α + ((y - 1) / y)
        <= α + (2 ^ (21+n) - 1) / (2 ^ (21+n))
        <= α + g(α)
        <  α + 1

である。

よってnを0以上32未満の任意の整数とするとき 2^n <= y <= 2 ^ (21+n) であるすべての整数yで ${x / y} != α + 1 が成り立つ。
まず、y <= 2^21において常に ${x / y} != α + 1 が成り立つことは既に示した。
n = 21 とおいて 2^21 <= y <= 2^42 で常に ${x / y} != α + 1 が成り立つ。
よってyが1以上2^32未満のすべての整数において ${x / y} != α + 1 は常に成り立つ。
したがって ${Math.floor(x / y)} = floor(x / y) は常に成り立つ。
おわり

まとめ

数学難しいです！でも自分で問題を立てて考えるのは楽しいですね！
間違っているところや、ここをこうした方がいいといった指摘、もっとスマートな方法があればコメント欄に書き込んでくださるとありがたいです！

2011-09-29

Deferredのコールバックスタイルと比較したメリット/デメリット

まだそんなに使い込んでいるわけではないけれど。
使う前はコールバックスタイルに比べてなにか利点あるの？別にコールバックスタイルで困らないんじゃない？って思っていたのでまとめてみる。

メリット

コールバック引数が消えてすっきりする
処理1をやって非同期処理を挟んで、処理2をやって、処理3をやって...というときにコールバックスタイルだと汚くなるのが綺麗にかける
非同期処理でもエラーハンドリングが綺麗にできる
(一部のDeferredライブラリのみ) 非同期処理を行っている最中にキャンセルできる。ちょうどスレッドの使える言語で、バックグラウンドで処理を行っているスレッドをとめるように
ライブラリにもよるが以下のようなことをするためのユーティリティがある。コールバックスタイルでもそういうユーティリティは作れるっちゃ作れるが、あらかじめ存在するDeferredライブラリに任せちゃう方がいいよね
- 複数の非同期処理を一斉に実行して全部揃ったら次を実行する (JSDeferredのparallel)
- 非同期処理をはさむ処理を任意回数順番にやる (JSDeferredのloop)

デメリット

Deferredを理解しないと書けない・読めない
- 僕の場合、Deferredライブラリで何をやっているのか実装を読まないと不安で使えなかったので、僕みたいな人はDeferredライブラリの実装を読む手間もある
ライブラリにもよるが、Deferredを使った場合、何もしていないと非同期処理内で起こったエラーが握りつぶされてしまう
- エラー用のコールバックを追加して、それを表示するとか、setTimeoutして再スローするとかしないといけない
- ちなみにMochiKitのDeferredが元になっているclosure-libraryのDeferredでは捕捉されなかったエラーは再スローされるように改良されている。素晴らしい

処理1をやって非同期処理を挟んで、処理2をやって、処理3をやって...というときにコールバックスタイルだと汚くなるのが綺麗にかける

コールバックスタイルで普通に書くとこういうコールバックのネストになる

function (cont) {
  処理1;
  someAsyncProcess(..., function () {
    処理2;
    someAsyncProcess(..., function () {
      処理3;
      cont();
    });
  });
}

関数に名前をつけてフラットにすることもできるが... この方法は東京Node学園#1「非同期プログラミングの改善」のエッセンスでは「名前でジャンプするなんてgoto文でしょ」と言われている。
個人的にはそんな悪くないと思うけど、書くのがだるいのは確か

function (cont) {
  phase1();
  function phase1() {
    処理1;
    someAsyncProcess(..., phase2);
  }
  function phase2() {
    処理2;
    someAsyncProcess(..., phase3);
  }
  function phase3() {
    処理3;
    cont();
  }
}

Deferred (ここではJSDeferred) を使うとこう

// someAsyncProcessはここでは上と違って
// コールバック引数を受け取る関数ではなくDeferredを返す関数とする

function () {
  return next(function () {
    処理1;
    return someAsyncProcess(...);
  }).
  next(function () {
    処理2;
    return someAsyncProcess(...);
  }).
  next(function () {
    処理3;
  });
}

非同期処理でもエラーハンドリングが綺麗にできる

正直、非同期処理でエラーハンドリングしたいと思ったことがないのであんまり...

(一部のDeferredライブラリのみ) 非同期処理を行っている最中にキャンセルできる

これはJSDeferredにはない機能。MochiKitのDeferredで可能。これのためにDeferredを使い始めた。

// 0.1秒間隔で0, 1, 2, 3, 4, 5 .. と永遠に出力する
function f() {
  return loop(0);
  function loop(i) {
    console.log(i);
    return MochiKit.Async.callLater(0.1, loop, i + 1);
  }
}

var deferred = f();

// 一秒後に処理を中断する
// （ボタンが押されたら処理を中断、のように変えてももちろんいい）
setTimeout(function () {
  deferred.cancel();
}, 1000);

2011-09-23

for (var v in nantoka()) yield v とか書かなくちゃいけなくね問題

JavaScriptのジェネレータについて思うこと - fujidigの雑記

案外そうでもなかったかもしれない。一個一個の関数を扱いにくいジェネレータ関数のまま放っておくのではなく、継続を引数にとる普通の非同期関数化してしまえばいいんだ。

お題は、これを出力するたびに0.1秒のウェイトいれるようにかえるというもの

function a() {
	for (var i = 0; i < 3; i ++) {
		console.log("a"+i);
	}
}

function b() {
	for (var i = 0; i < 3; i ++) {
		console.log("b"+i);
	}
}

function main() {
	a();
	b();
}

main();
console.log("done");

runnable関数はKazuho@Cybozu Labs: JavaScript/1.7 で協調的マルチスレッドより

function runnable(generatorFunc) {
	var generator;
	var resume = function (value) {
		try {
			generator.send(value);
		} catch (e if e instanceof StopIteration) {
		}
	};
	generator = generatorFunc(resume);
	resume(undefined);
}

function a(cont) {
	runnable(function (resume) {
		for (var i = 0; i < 3; i ++) {
			console.log("a"+i);
			setTimeout(resume, 100);
			yield;
		}
		cont();
	});
}

function b(cont) {
	runnable(function (resume) {
		for (var i = 0; i < 3; i ++) {
			console.log("b"+i);
			setTimeout(resume, 100);
			yield;
		}
		cont();
	});
}

function main(cont) {
	runnable(function (resume) {
		a(resume);
		yield;
		b(resume);
		yield;
		cont();
	});
}

main(function () {
	console.log("done");
});

まあこうするぐらいだったらdeferred-generatorの方が洗練されてるかなー

var a = Deferred.generator(function () {
	for (var i = 0; i < 3; i ++) {
		console.log("a"+i);
		yield Deferred.wait(0.1);
	}
});

var b = Deferred.generator(function () {
	for (var i = 0; i < 3; i ++) {
		console.log("b"+i);
		yield Deferred.wait(0.1);
	}
});

var main = Deferred.generator(function () {
	yield a();
	yield b();
});

main().then(function () {
	console.log("done");
});

ちなみに普通のDeferredライブラリ (ここではMochiKit) を使うとこう

var Async = MochiKit.Async;
function a() {
	return loop(0);
	function loop(i) {
		if (i >= 3) return Async.succeed();
		console.log("a"+i);
		return Async.callLater(0.1, loop, i + 1);
	}
}

function b() {
	return loop(0);
	function loop(i) {
		if (i >= 3) return Async.succeed();
		console.log("b"+i);
		return Async.callLater(0.1, loop, i + 1);
	}
}

function main() {
	var deferred = Async.succeed();
	deferred.addCallback(a);
	deferred.addCallback(b);
	return deferred;
	// return a().addCallback(b) でもいいんだけど気分的にaとbは同じ書き方で並べたい。
}

main().addCallback(function () {
	console.log("done");
});

2011-09-23

JavaScriptのジェネレータとDeferredを組み合わせたライブラリ

JavaScriptのジェネレータとDeferredを組み合わせるといい感じ！（JS1.7のyieldでharmonyのawait式ぽいことをする) - fujidigの雑記でいったことをライブラリにしてみました

GitHub - fujidig/deferred-generator

まだ実際に使ってみていないので便利か分かりません。結局Array#forEachの中でyieldするとかできないし微妙かな...普通のDeferredライブラリ使った方がいいかも

2011-09-21

JavaScriptのジェネレータとDeferredを組み合わせるといい感じ！（JS1.7のyieldでharmonyのawait式ぽいことをする)

repl.it経由でtraceur-compilerを知った。そしてharmonyにはawait式というものがあるということを知った。

function deferredTimeout(delay) {
    var deferred = new Deferred();
    setTimeout(function() {
        deferred.callback({
            called: true
        })
    },
    delay);
    return deferred;
}

function a() {
    for (var i = 0; i < 4; ++i) {
        console.log("a"+i);
        await deferredTimeout(1000);
    }
}

function b() {
    for (var i = 0; i < 4; ++i) {
        console.log("b"+i);
        await deferredTimeout(1000);
    }
}

function main() {
	await a();
	await b();
}

main().then(function () { console.log("done"); });

ほほう。
で、これJS1.7のyieldでだいたい同じことできるよねって思ったので試した。

function deferredTimeout(delay) {
    var deferred = new Deferred();
    window.setTimeout(function() {
        deferred.callback({});
    },
    delay);
    return deferred;
}

function generatorToDeferred(func) {
	return function () {
		var deferred = new Deferred();
		var generator = func.apply(this, arguments);
		function loop(val) {
			try {
				var waitTask = generator.send(val);
				waitTask.then(loop);
			} catch (e if e instanceof StopIteration) {
				deferred.callback();
			}
		}
		loop(undefined);
		return deferred;
	}
}

var a = generatorToDeferred(function () {
	for (var i = 0; i < 4; ++i) {
		console.log("a"+i);
		yield deferredTimeout(100);
	}
});

var b = generatorToDeferred(function () {
	for (var i = 0; i < 4; ++i) {
		console.log("b"+i);
		yield deferredTimeout(100);
	}
});

var main = generatorToDeferred(function () {
	yield a();
	yield b();
});


main().then(function() { console.log("done"); });

おお、これはいいんじゃないか？

JavaScriptのジェネレータについて思うこと - fujidigの雑記で考えた「ジェネレータで非同期処理が同期的に書けるいうてもfor (var v in nantoka()) yield v;とかしないといけないやん」って問題がyield nantoka();で済むようになってる
waitTaskのエラーを戻り値のdeferredに伝搬させる処理は実装してないけどすぐ実装できるはず
deferredのcancellerでwaitTaskのcancelを呼ぶようにしたら現在アイドル中のdeferredがキャンセルできるはず！
そうすればMochiKitのDeferredのような複雑なDeferredライブラリを使わなくてよくなりそう！チェイン機能のないDeferredライブラリでOKなんじゃないだろか

で懸念点。generatorToDeferredに渡す関数内でreturnしたらその値がdeferred.callbackに渡ってほしいんだけど、ジェネレーターはStopIterationオブジェクトからreturnされた値がとれるのかと思いきやどうやらそういうのはなさそうだ...？んーreturnではなく終了することを表す特別な値をyieldするという方法で代替できるけど...
っていうかジェネレーターの関数でreturnに戻り値を書いてたらパース時にエラーになるね...

function f() { yield 1; return 2; } // TypeError: generator function f returns a value

リンク

http://traceur-compiler.googlecode.com/svn/branches/v0.10/demo/repl.html traceur-compilerでコンパイルした結果が見れる (await式を含む関数はステートマシンなコードに変換されていることが分かるね)
GitHub - google/traceur-compiler: Traceur is a JavaScript.next-to-JavaScript-of-today compiler traceur-compilerのDeferredオブジェクトの実装 (とても小さい！)
GitHub - google/traceur-compiler: Traceur is a JavaScript.next-to-JavaScript-of-today compiler await式を含むコードの変換

2011-09-08

JavaScriptで非同期処理の途中で中断したいよぉお

JSDeferredのcancelだと目的のことはできなくて、それは構造上無理なんだろうなーと。
で、こんなのを書いてみたものの使いにくい。
https://gist.github.com/1200041

function Trampoline(func) {
	this.task = new Task(func);
}

Trampoline.prototype.step = function() {
	if (!this.task) return;
	this.task = this.task.cont();
	if (this.task) this.task.nextStep = this.step.bind(this);
};

Trampoline.prototype.cancel = function() {
	if (this.task && this.task.canceler) {
		this.task.canceler();
	}
	this.task = null;
}

function Task(cont) {
	this.cont = cont;
	this.nextStep = null;
	this.canceler = null;
}

Task.prototype.getCallback = function() {
	var self = this;
	return function() { self.nextStep() };
};

function wait(cont, sec) {
	var task = new Task(cont);
	var timerId = setTimeout(task.getCallback(), sec * 1000);
	task.canceler = function() { clearTimeout(timerId) };
	return task;
}

function f1() {
	console.log(1);
	return wait(f2, 1);
}

function f2() {
	console.log(2);
	return wait(f3, 1);
}

function f3() {
	console.log(3);
	return null;
}

var trampoline = new Trampoline(f1);
trampoline.step();
setTimeout(function () {
	console.log("cancel!");
	trampoline.cancel();
}, 1500);

で、どうやらMochiKitのDeferredなら目的のことができるみたい
https://gist.github.com/1202768

function main() {
	var d = accessAndShowEntries();
	d.addCallback(function() {
		console.log("finish");
	});
	setTimeout(function() {
		console.log("cancel!");
		d.cancel();
	}, 2500);
}

function accessAndShowEntries() {
	function loop(i) {
		if (i >= 5) return;
		return accessEntry(i).addCallback(function (data) {
			console.log(data);
			return callLater(0, loop, i + 1);
		});
	}
	return callLater(0, loop, 0);
}

// XHR で何かアクセスする代わり
function accessEntry(i) {
	var d = new Deferred();
	var cb = d.callback.bind(d, "foo"+i);
	var timerId = setTimeout(cb, 1000);
	d.canceller = function () {
		clearTimeout(timerId);
	};
	return d;
}

でも、JSDeferredの超絶シンプルさに比べてMochiKitのDeferredは複雑だなー。ちょっと理解しようとする気力が起きない
それから、DeferredListのcancelを呼んでも、list全部のcancelを行うっていうふうになっていないのが不思議。なんでだ？

余談

ちなみに動機はTumblrでlikeしておいたものをまとめて自動でリブログと画像の保存をするっていう変なvimperatorプラグイン https://gist.github.com/1194341
(全く関係のない話で、このプラグインは新しいタブを開いてそこのdocumentにあれこれ書き込むっていうのをやっていてなんだかマズそう。実際このタブで別のページを開くとなぜか書き込んだ要素が残っていたりするし...)
これに処理の途中で中断できるボタンとか、タブを閉じようとしたときに中断できる機能をつけたいと思ったのだ。
ところで、Vimperatorプラグインで_libly.js以外ではなにかライブラリを使っているコードとかほとんど見かけないんだけどライブラリを使うときはどうすればいいだろう...ライブラリのコードをソースに含めちゃうとか、あらかじめファイル名の先頭にアンダースコアをつけてプラグインディレクトリに保存してねって形にするとか？

でももう疲れちゃってやる気なくなったからもういいやー感

2010-11-27

Lazy K方式のYコンビネータは分かりやすいなー

Lazy Kで再帰をしようとしたら以下のようなイディオムを使うんだけど

;; fact
((lambda (x) (x x))
 (lambda (self)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((self self) (- n 1)))))))

このイディオム部分をくくりだすとそれがYになる

(lazy-def '(Y f)
 '((lambda (x) (x x))
   (lambda (self)
     (f (self self)) )))

とても分かりやすい

本来のYコンビネータ

(lambda (g) ((lambda (x) (g (x x)))
             (lambda (x) (g (x x)))))

はLazy K方式の((lambda (x) (x x)) ...) の部分を展開(β変換っていうのかな)した形だなーと気づく

先行評価でもOKなバージョン

; 本来のYコンビネータ
(define Y0 (lambda (g) ((lambda (x) (g (x x)))
                        (lambda (x) (g (x x))))))

; http://blog.livedoor.jp/dankogai/archives/51524324.html など
(define Y1 (lambda (f) ((lambda (g) (lambda (m) ((f (g g)) m)))
                        (lambda (g) (lambda (m) ((f (g g)) m))))))

; http://www.loveruby.net/ja/misc/ycombinator.html
(define Y2 (lambda (f) ((lambda (proc) (f (lambda (arg) ((proc proc) arg))))
                        (lambda (proc) (f (lambda (arg) ((proc proc) arg)))))))

; http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/35058
(define Y3 (lambda (g) ((lambda (f) (g (f f)))
                        (lambda (f) (g (lambda (y) ((f f) y)))))))

探してみるといくつかのパターンがあったけど、どれも本来のYコンビネータでは先行評価だと無限再帰になるのでlambdaでラッピングしただけだなーと気づく。

本来のYコンビネータから入らずに先行評価でもOK版Yコンビネータを作っている記事は昔読んだことがあるけどそのときの僕には難しかった

追記 (2010-11-27T22:13:35+09:00)

せっかくだからLazy K方式の先行評価でもOK版を作った

(define Y4 (lambda (f) ((lambda (x) (x x))
                        (lambda (self) (f (lambda (y) ((self self) y)))))))