2016/06/23
Self-callの書き換え
(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))みたいな非末尾再帰を自動的に(累積変数を導入して)末尾再帰に変えたら、なんて議論を見てちょっと思い出したのでメモっとく。
Gaucheでは、ローカル定義された関数の自己末尾呼び出しはただのジャンプになる。
gosh> (define (loop) (define (rec) (rec)) (rec))
loop
gosh> (disasm loop)
CLOSURE #<closure (loop)>
=== main_code (name=loop, code=0x139b340, size=4, const=0 stack=6):
signatureInfo: ((loop))
0 LOCAL-ENV-JUMP(0) 0 ; (rec)
2 RET
3 RET
でも、トップレベル定義された関数への自己再帰呼び出しにはグローバル変数のルックアップが入る。 他の関数を末尾呼び出しするのと同じ。
gosh> (define (loop) (loop))
loop
gosh> (disasm loop)
CLOSURE #<closure (loop)>
=== main_code (name=loop, code=0x139b8a0, size=3, const=1 stack=3):
signatureInfo: ((loop))
0 GREF-TAIL-CALL(0) #<identifier user#loop.13f2b40>; (loop)
2 RET
スタックは消費しないが、グローバル変数へのアクセスがひとつ余分に入るので、
マイクロベンチマークで多少差が出る。数値は忘れたが
fibで数%くらいだったような気がする。
グローバル自己再帰を検出してローカル自己再帰に書き換えてしまうのは簡単なのだが それをやっていないのは、「ループ中にトップレベル束縛が書き換えられる」という 可能性があるからだ。これは確かCLの流儀に倣ったんだと思う。 CLではいつでも実行を中断してデバッガに落として環境を書き換えられるから。
ただ、Schemeはもうちょい静的寄りな感覚だし、R6RS風にモジュール外部からの トップレベル束縛の変更を禁止すれば(実はそういうフラグはもう実装してある)、 モジュールを読んだ時点でそのトップレベル束縛が変更され得るかどうかわかるので、 トップレベルへの自己再帰をローカル自己再帰に変えることはできる。
マイクロベンチマークで数%の速度を稼ぐのと自由度とを天秤にかけて
今は自由度を取ってるんだけど、冒頭のfactみたいにトップレベルでの
非末尾自己再帰を末尾自己再帰に書き換えるってところまでサポートするなら、
天秤を逆の方に傾けるメリットもあるかもしれない。
しかし、訓練されたSchemerは末尾呼び出しを無意識に書くから、そもそも そういう自動変換の需要は無いのではないか、という気もする。 いや、それは人間コンパイラとして馴らされてしまっただけなのかな。
Tags: Programming, Scheme, Gauche
2016/06/17
スロットの初期化をチェックする
Gaucheのオブジェクトシステムでは、オブジェクトの作成時にスロットを初期化しないで
おくことができる。初期化されないスロットはunboundという状態になる。次の例では、
スロットaには初期値 (:init-valueもしくは:init-form)が
設定されていないので、makeに :a で初期値を渡さない限り、
作られるオブジェクトのaスロットはunboundになる。
gosh> (define-class A ()
((a :init-keyword :a)
(b :init-keyword :b :init-value 1)))
A
gosh> (make A)
#<A 0xb280e0>
gosh> ,d
#<A 0xb280e0> is an instance of class A
slots:
a : #<unbound>
b : 1
describeでは #<unbound> と表示されているが、#<unbound> という
値が入っているわけではない。unboundはあくまでスロットの状態であって、
値を取り出そうとするとエラーになる。
gosh> (~ (make A)'a) *** ERROR: slot a of object of class #<class A> is unbound Stack Trace:
この仕様はCLOSに準じたものだ。
unbound slotは、インスタンス初期化中に、複数のメソッド間で情報をやりとりするのに使える。
スロットの初期化(makeに渡された初期化キーワードの処理と、:init-valueや
:init-formの処理) はベースクラスの
initializeメソッドで処理されるので、自分のinitializeメソッド中で
スーパークラスのメソッドを呼んだ後にスロットがboundかどうかチェックすることで、
独自の初期化処理を書ける。特に、既に初期化された他のスロットに依存する計算を初期化時に行える。
次の例では、上で定義したクラスAについて、初期化キーワード:aが
makeに渡されなかった場合に、bスロットの値に基づいた初期化を行う。
gosh> (define-method initialize ((obj A) initargs)
(next-method)
(unless (slot-bound? obj 'a)
(set! (~ obj 'a) (+ (~ obj 'b) 1))))
#<generic initialize (18)>
gosh> (make A :b 10)
#<A 0xb655c0>
gosh> ,d
#<A 0xb655c0> is an instance of class A
slots:
a : 11
b : 10
gosh> (make A :a 1 :b 10)
#<A 0xb72c60>
gosh> ,d
#<A 0xb72c60> is an instance of class A
slots:
a : 1
b : 10
現実のプログラムでのunboundスロットの使いどころってほぼこれくらいで、
unbound slotを抱えたままのインスタンスをずっと持ち歩いて嬉しいことというのは
多分ほとんどない。unboundスロットへのアクセスはメソッドslot-unboundで
インターセプトできるので、
それを利用したトリックはあり得るけど、特殊な用途と言えるだろう。
むしろ、初期化キーワードを間違えていたりして
初期化したつもりがされてない、なんてバグの方に足を取られることがある。
(関連して、makeに渡す初期化キーワードに無効なものがあったらエラーに
できないか、という話もあるのだけれど、初期化キーワードの解釈は
allocateとinitializeメソッドの定義次第でどうにでもできるので
機械的にはじくのは難しい)。
それなら、初期化が済んだ時点でスロットをチェックしてunboundなものをはじいて
しまったらどうか。MOPを使ってmakeにメソッドをつければ
全ての初期化が終わった後のタイミングで検査ができる。
(define-class <ensure-slot-initialization-meta> (<class>) ())
(define-method make ((class <ensure-slot-initialization-meta>) . args)
(rlet1 instance (next-method)
(dolist [s (class-slots class)]
(unless (slot-bound? instance (slot-definition-name s))
(errorf "Slot ~s of object ~s is not initialized"
(slot-definition-name s) instance)))))
こんな感じ。
gosh> (define-class B ()
((a :init-keyword :a)
(b :init-keyword :b :init-value 1))
:metaclass <ensure-slot-initialization-meta>)
B
gosh> (make B :a 1 :b 10)
#<B 0xbb4ef0>
gosh> ,d
#<B 0xbb4ef0> is an instance of class B
slots:
a : 1
b : 10
gosh> (make B)
*** ERROR: Slot a of object #<B 0xbbcc20> is not initialized
Stack Trace:
これなら初期化キーワードを間違えたケースも(それによって意図したスロットが unboundになりさえすれば)捕まえられる。
さて、<ensure-slot-initialization-meta>は
MOPライブラリにしようと思って書いたのだけれど、
かなり本質的な機能のような気がするし、むしろ標準の<class>に
:disallow-unbound-slot みたいなオプションをつけてしまう方が
良いような気がしてきた。どうしようかなあ。
Tags: Programming, Gauche
2016/05/13
誤差が生じるとき
Ruiさんがおもしろい問題をtweetしてた。もすこし厳密に書き直すとこんな感じ。
IEEE単精度浮動小数点数演算で、
x + 0.25 - 0.25がx - 0.25 + 0.25と同じにならない数xを求めよ。
xをひとつだけ求めるなら簡単だけれど、xを全て求めるのは難問になると思う。
実は、浮動小数点数の誤差についてはこれまで何度もはまってきたので、このくらい簡単さ、 と思って舐めてかかったんだけど、 全部のケースを網羅するのはやっぱり難問だった。 浮動小数点数はどこまでも油断ならない。
(1) 0.25が分解能の半分に近い場合
すぐに考えつくのはこれだろう。 浮動小数点数の分解能d(ここでは隣の浮動小数点数までの距離とする)の半分より 小さな数値は足しても引いても元の数に影響を与えない。
0.25がd/2未満なら演算の順番を入れ替えても結局変わらないんじゃないか、 と思うかもしれないが、 浮動小数点数には、プラス側とマイナス側で分解能が違う場合があるのだ。 ちょうど±2^mの場合である。 2^mを境に仮数部が受け持つ範囲が一桁シフトするので、2^mより上では隣との距離が 2^(m-p) (pはhidden bitを含まない仮数部の桁数)になるけれど、2^mより下ではその半分の距離になる。
![[image]](http://blog.practical-scheme.net/images/flonum2.png)
この絵は昔のを流用してるのでdoubleって書いてあるけどfloatでも同じ。
(厳密に言えば、これは±2^mの両側が正規化数の場合。非正規化数領域ではそれ以上分解能を 細かくできないので両側の分解能は同じになる。 以前これに起因するバグを踏んだ)
プラス側のdが0.5、マイナス側が0.25になるような2^mを選ぶと、
- 2^m + 0.25 は隣の浮動小数点数2^m + 0.5とのちょうど中間に落ちるので、 デフォルトの偶数丸め規則により結果は2^mに丸められる
- 2^m - 0.25 は浮動小数点数として正確に表現可能。
であるので、
- 2^m + 0.25 - 0.25 だと、最初の2^m + 0.25が2^mに丸められちゃうので、 結果は2^m - 0.25の値。
- 2^m - 0.25 + 0.25 だと、最初の2^m - 0.25は正しく計算され、 その次の+0.25も正しく計算されて、結果は 2^m。
と言う具合に差がでる。xが -(2^m) でもプラスとマイナスが逆になるだけで同じ議論。
(なお、丸め設定が切り上げの場合、2^m+0.25は2^m+0.5に切り上げられるが、そこから0.25を引いた結果も2^m+0.5に切り上げられるので、やっぱり同じにならない)
後は、こういうmは何かってことになる。IEEE単精度浮動小数点数は仮数部が23bitあるので、
[]内を2進表記とすると:
[1.00000_00000_00000_00000_000] * 2^m が x
[1.00000_00000_00000_00000_001] * 2^m が x+0.5
となるような値ってことだから、0.5 * 2^23が x、つまり x = 2^22。
符号を逆にした場合も含め、このケースに該当するのは x = ±2^22。
(2) 0.25が分解能に近い場合
類似のケースとして、0.25を足すことが2のべき乗の境界をまたぐというのもある。 2^mのプラス側の分解能が0.25、マイナス側の分解能が0.125だったとしよう。 xを 2^m - 0.125 とすると、これに0.25を足したものは2^m + 0.125だが丸められて2^mとなる。 ここから0.25を引くと 2^m - 0.25 になってしまう。 減算から先にやった場合は丸めが生じない。桁を揃えて書いてみると：
[1.00000_00000_00000_00000_000] * 2^m が x + 0.125
[0.00000_00000_00000_00000_0001] * 2^m ← これが0.125 = 2^-3
なので、正負も考慮するとxは ±(2^21 - 2^-3)。
(3) 0.25を基準にしてxが分解能の半分に近い場合
0.25は
[1.00000_00000_00000_00000_000] * 2^(-2)
である。(1)とは逆に、xが小さくて、この数値の分解能の 半分以下であった場合にも、同様の可能性が生じる。例えばxが2^-26だった場合。
[1.00000_00000_00000_00000_000] * 2^(-2) 0.25
[0.00000_00000_00000_00000_0001] * 2^(-2) x
0.25+xは丸められて0.25になるが、0.25-xは有効桁数に収まる。 (わかりやすく0.25-xと表記したが、-(x-0.25)と同じなので議論に影響はない。)
このケースは少々複雑だ。xが2^-26より少しでも大きければ0.25+xは 0.25の次の浮動小数点数に近くなるため、そちらに丸められ、加算を先にやっても 減算を先にやっても結果は同じになる。
しかし、xが2^-26より少しだけ小さい場合、加算は0.25に丸められて無かったことになるが、 減算は0.25よりひとつ下の浮動小数点数に丸められる。たとえばx = 0.875*2^(-26)なら、
[1.00000_00000_00000_00000_000] * 2^(-2) 0.25
[0.00000_00000_00000_00000_0000111] * 2^(-2) x
0.25+xは
[1.00000_00000_00000_00000_0000111] * 2^(-2) 正確な結果
[1.00000_00000_00000_00000_000] * 2^(-2) 丸め結果
だが、0.25-xは
[0.11111_11111_11111_11111_1111001] * 2^(-2) 正確な結果
[1.11111_11111_11111_11111_111001] * 2^(-3) 正確な結果、正規化
[1.11111_11111_11111_11111_111] * 2^(-3) 丸め結果
となる。xが次のパターンで#にひとつでも1があれば差が生じる。
[0.00000_00000_00000_00000_00001######...] * 2^(-2)
したがって、このケースでのxは 2^-27 < x ≦ 2^-26 、およびその符号を 反転したもの。
(4) 0.25の加算で桁数が増えて丸めを生じる場合
xの分解能が0.25に対して十分にあっても、丸めが起きてしまうケースがある。 次の例を見てみよう。
[1.11111_11111_11111_00000_001] * 2^13 x
[0.00000_00000_00001_00000_000] * 2^13 0.25
加算すると、次々と繰り上がりがおきて、最上桁がひとつ増え、仮数部の有効桁数を 越えてしまい、最後のビットが失われる。
[10.00000_00000_00000_00000_001] * 2^13 x + 0.25、正確な結果
[1.00000_00000_00000_00000_0001] * 2^14 正規化
[1.00000_00000_00000_00000_000] * 2^14 丸め結果
0.25の減算から先にやった場合は丸めが起こらないので、結果が食い違う。
これが起きるケースはどういったパターンだろうか。
- 0.25による加算の繰り上がりがカスケード的に最上位まで伝搬する
- xのLSBが1であり、0.25のビットより下位桁にある
という条件を満たせば良いので、以下の23通りのパターンがあり得る。
#の部分は0でも1でも構わない。
[1.#####_#####_#####_#####_##1] * 2^-2 x
[1.00000_00000_00000_00000_000] * 2^-2 0.25
[1.1####_#####_#####_#####_##1] * 2^-1 x
[0.10000_00000_00000_00000_000] * 2^-1 0.25
[1.11###_#####_#####_#####_##1] * 2^0 x
[0.01000_00000_00000_00000_000] * 2^0 0.25
[1.111##_#####_#####_#####_##1] * 2^1 x
[0.00100_00000_00000_00000_000] * 2^1 0.25
…
[1.11111_11111_11111_11111_111] * 2^20 x
[0.00000_00000_00000_00000_010] * 2^20 0.25
符号が逆の場合も同様。
(z) NaNはNaNにしてNaNにあらず
あと、イレギュラーな回答として「xがNaNの場合」というのもあり得る。 NaNには何を足し引きしてもNaNだが、NaNとNaNを比較すると必ず偽になるので、 プログラムコード上で数値比較していた場合は「等しくない」となる。 ただ、ビットパターンで比べれば等しいかもしれない。等しくないかもしれない (NaNを構成するビットパターンは複数あるので)。
これは問題の「同じにならない」の解釈次第である。
他にあるかな?
多分これで全部だと思うんだけど、他のパターンを見つけたら教えてください。
なお、大元のテスト課題は、答えがpow(2, n) {n > 0} のnを埋める形だったそうなので、 (1)のパターンのみ考慮すれば良かった模様。
Tag: Programming
2016/04/24
演劇の授業
本筋とは違うところに反応するけど
http://toyokeizai.net/articles/-/115149?page=4
平田[オリザ]: …演劇を学べる高校は3年前の数字で50校ほどありますが、そのうち8割を東京、神奈川、大阪、兵庫の都市部が占めています。
50校、結構あるんだなあと思った。ここでは都市部と地方の文化資本格差の話で、その文脈では「足りてない」んだけれど、それでもやってるところがあるというのは希望だなあ。
もちろん部活動としての演劇部のある高校ははるかに多いだろうし、中には顧問が熱心に指導しているところもあるだろうけれど、公演に向けての準備と、体系的な学びは違うんで、体系的に基礎を身につけた指導者が講座として教える形がもっと広まればいいなあ。
(しかし正式な科目にするとなると、文科省が指導要項作ったりすることになっちゃうんだろうか。それはちとまずい気がする。芝居の技術というのはこれをやっとけばいいってもんじゃなくて、色々な技法を体験して各人が自分に合うものを見つけるor編み出すといったものだから。指導者は複数の技法に習熟してないとならないし、それぞれの生徒に合うものを一緒に探すこともできないとならない。あらかじめカリキュラムを決めてそれを全部やらせる、という形態には合わなさそう。となるとオプション的な位置づけの方が現場の都合は良いのかもしれない。)
2016/03/06
訛り
今のところ、自分の英語を聞いていて一番耳につく日本語訛りは二重母音が連母音になるところだなと思った。頭の中で連母音で記憶してしまっていて、気をつけないとすぐにそれが出てきちゃう。日本語での活舌練習で連母音をはっきり発音する習慣がついてるのでなお目だつのかもしれない。通じさせるだけなら曖昧になるよりは連母音でもはっきりしてる方がいいんだろうけど。矯正するには音として覚え直すしかないように思う。
母音自体も日本語訛りを感じさせるんだけど、母音って英語話者間でも結構バリエーションがあるので、何が日本語っぽいのかまだ良くわからない。各英語方言ではそれぞれシフトの方向が一貫しているから外国語っぽくならないのかな。
アクセントのクラス、LAとかにはあるんだけど、前にハワイで探したけどみつからなかったんだよなー。今ならオンラインで何かあるかなあ。
Tag: 英語
Comments (0)