ふと、構文をあたえてその構文にしたがった文を発生させるものを書いてみる。
require 'syngen'
$KCODE = 'EUC-JP'
syntax = {
:sent => [[:subj, :adjs, :obj, :verb]],
:subj => [["私は"], ["コンピュータは"], ["あれは"]],
:adjs => [[], [:adj, :adjs]],
:adj => [["青い"], ["どろどろした"], ["どんよりした"]],
:obj => [["バグを"], ["豆腐を"], ["バッテリを"], ["if文を"]],
:verb => [["直した"], ["埋め込んだ"], ["食べた"], ["装着した"], ["ひっくりかえした"]],
}
syngen(syntax, :sent, 3) {|_, ary| p ary.join }
で、実行すると以下のように文を生成する。
"私はバグを直した" "私はバグを埋め込んだ" "私はバグを食べた" "私はバグを装着した" "私はバグをひっくりかえした" "私は豆腐を直した" "私は豆腐を埋め込んだ" "私は豆腐を食べた" "私は豆腐を装着した" "私は豆腐をひっくりかえした" "私はバッテリを直した" "私はバッテリを埋め込んだ" ... "あれはどんよりしたどんよりしたif文を埋め込んだ" "あれはどんよりしたどんよりしたif文を食べた" "あれはどんよりしたどんよりしたif文を装着した" "あれはどんよりしたどんよりしたif文をひっくりかえした"
adjs のように再帰的な導出も可能で、指定した導出回数の制限の範囲内で生成する。
まぁ、日本語に使おうと思って作ったわけではないが...
syngen.rb:
def syngen_rhs(syntax, rhs, size)
return if size < 0
if rhs.empty?
yield size, []
else
syngen(syntax, rhs[0], size) {|size1, child|
syngen_rhs(syntax, rhs[1..-1], size1) {|size2, arr|
yield size2, [child, *arr]
}
}
end
end
def syngen(syntax, sym, size, &b)
return if size < 0
if String === sym
yield size, sym
else
derivations = syntax[sym]
derivations.each {|rhs|
if rhs.length == 1 || derivations.length == 1
size1 = size
else
size1 = size-1
end
syngen_rhs(syntax, rhs, size1, &b)
}
end
end日本語でないなら何に使うかというと、Ruby に使う。
たとえば、0 と nil と配列から構成される式を生成するには以下のようにできる。
% ruby -rsyngen -e '
syntax = {
:exp => [["0"],
["nil"],
["[]"],
["[",:exps,"]"]],
:exps => [[:exp],
[:exp,",",:exps]],
}
syngen(syntax,:exp,2) {|_, ary| puts ary.join }'
0
nil
[]
[0]
[nil]
[[]]
[[0]]
[[nil]]
[[[]]]
[0,0]
[0,nil]
[0,[]]
[nil,0]
[nil,nil]
[nil,[]]
[[],0]
[[],nil]
[[],[]]
また、Ruby 1.8 での多重代入のあたりを生成するには、parse.y のそのあたりの規則を写して次のようにする。
syntax = {
:exp => [["0"],
["nil"],
["[]"],
["[",:exps,"]"]],
:exps => [[:exp],
[:exp,",",:exps]],
:arg => [[:exp]],
:mrhs => [[:args,",",:arg],
[:args,",*",:arg],
["*",:arg]],
:args => [[:arg],
[:args,",",:arg]],
:mlhs => [[:mlhs_basic],
["(",:mlhs_entry,")"]],
:mlhs_entry => [[:mlhs_basic],
["(",:mlhs_entry,")"]],
:mlhs_basic => [[:mlhs_head],
[:mlhs_head,:mlhs_item],
[:mlhs_head,"*",:mlhs_node],
[:mlhs_head,"*"],
[ "*",:mlhs_node],
[ "*"]],
:mlhs_head => [[:mlhs_item,","],
[:mlhs_head,:mlhs_item,","]],
:mlhs_item => [[:mlhs_node],
["(",:mlhs,")"]],
:mlhs_node => [["var"]],
:massign => [[:mlhs," = ",:mrhs]],
:lmassign => [[:mlhs," = ",:exp]],
:rmassign => [["var = ",:mrhs]],
}
まぁ、この文法だと変数名は常に var だが、そこを適当な変数名に置換すれば実行可能な文になる。
1.8 と 1.9 で実行して、結果を比較すると、何が違うか見えてくるというわけだ。
Ruby の多重代入において、配列の分解には丸括弧 "(", ")" を使うが、これがなぜ角括弧 "[", "]" でないのかという疑問がある。
また、多重代入の左辺におけるカンマの扱いもかなり謎である。
配列の分解は ML や Haskell のパターンマッチのしょぼいやつと思えば、生成と分解には同じ形式を使用するのが自然である。具体的には、配列の生成には角括弧をつかうのだから、分解にも角括弧を使うほうが明らかに自然である。
では、角括弧を使えない理由があるかと考えると、パーサの都合はそれなりにある。
仮に、生成時の配列の文法をそのまま代入の左辺に使えるとしてみよう。そうすると、[a, b, c] = [1, 2, 3] と記述できることになる。
ここで、[a, b, c] は左辺であるが、単独で [a, b, c] が表れたときには、配列を生成する式とみなせる。つまり、パーサが左から読んでいったとき、[a, b, c] が左辺であるかどうかは = を見つけるまではわからない。したがって、a, のところまで読んで、a に対応する構文木を生成する場合、これは左辺の一部かどうかはわからず、後でどうにかする必要がある。
これに対し丸括弧を使うと、同様な文は (a, b, c) = [1, 2, 3] と記述することになる。
ここで、(a, b, c) は左辺であるが、角括弧の場合と異なり、普通の式とはみなせない。(C と違い Ruby にはカンマオペレータはない) つまり、パーサが左から読んでいったとき、最初のカンマを見つけた時点で、普通の式ではないことがわかり、左辺と判断できる。したがって、a, のところまで読んで a に対応する構文木を生成する場合、これは左辺の一部であることがわかっているので、左辺用のノードを生成することができる。
さて、丸括弧ならばいつも区別できるかというと、そうでもない。配列の角括弧を丸括弧にすると、カンマという手がかりが使えるようになるが、配列にはカンマを使わない場合がある。カンマを使うのは 2要素以上で、それ未満であれば使わないのである。
とすると (a) = val などという場合は、a が左辺の一部であることを判断するには = まで待たなければならない。ここで、ネストすると ((((((((((a)))))))))) = val とかなるわけで、a と = の間には任意個のトークンが入りうる。ということは有限個のトークンの先読みで判断するのは無理である。そして、Ruby が使っている yacc は LALR(1) なので無理である。
これに対して Ruby がどう対処しているかというと、1要素でもカンマを必須にするというものである。つまり、((((((((((a,)))))))))) = val と記述するのである。こうすればたしかに、変数 (や他の代入対象) の直後にカンマが表れるので、先読みひとつで判断ができる。
これで、1要素以上の配列に対応する記法が用意できたことになる。
というように、パーサの都合をみてとることは可能である。しかしこれはネガティブな理由であり、丸括弧が素晴らしいという理由ではない。
角括弧よりも丸括弧のほうが良いという理由はあげられるだろうか?
駅の階段で、登りと下りの区分けがあるところがある。
そして、その分けかたが、偏っていることがある。つまり片方が広く、もう片方が狭いのである。
この理由をしばらく考えて、いくつか仮説をたてた。
最後のがそれっぽい、かな。
さて、多重代入な文を片っ端から生成し、1.8 と 1.9 で実行して比較すれば、違いを調べることはできる。
しかし、1.9 が (私の考えるところの) 正しい 1.9 であるか、というのはわからない。
1.9 の正しさを調べるには、正しい 1.9 が必要である。それさえあれば、現状の 1.9 と、正しい 1.9 を比較できる。
というわけで、実装してみた。
しかし、文法自体が腐っていることは検出できないのは盲点であった。
Valgrind User Manual を読む。頭から memcheck まで。
で、保守的 GC で怪しげな場所を読まざるを得ないときには、VALGRIND_NON_SIMD_CALL1 を使い、valgrind 管理下から抜け出て読めばいいということに気がついた。
そうすれば、V bits や A bits を変更せずに、かつ、エラーも出さずに読むことができる。
Index: gc.c
===================================================================
--- gc.c (リビジョン 12720)
+++ gc.c (作業コピー)
@@ -35,6 +35,8 @@
#include <windows.h>
#endif
+#include <valgrind/memcheck.h>
+
int rb_io_fptr_finalize(struct rb_io_t*);
#if !defined(setjmp) && defined(HAVE__SETJMP)
@@ -727,12 +729,20 @@
return Qfalse;
}
+static VALUE read_uninitialized_value(VALUE thread_id, VALUE *x)
+{
+ return *x;
+}
+
static void
mark_locations_array(register VALUE *x, register long n)
{
VALUE v;
while (n--) {
- v = *x;
+ if (RUNNING_ON_VALGRIND)
+ v = (VALUE)VALGRIND_NON_SIMD_CALL1(read_uninitialized_value, x);
+ else
+ v = *x;
if (is_pointer_to_heap((void *)v)) {
gc_mark(v, 0);
}
これで valgrind ./ruby sample/test.rb はきれいに動く。
でも、valgrind --trace-children=yes ./ruby bootstraptest/runner.rb とすると、なんかエラーが出るな。
しかし、valgrind は初期化されているかどうかを bit 単位に管理しているとは驚きであった。
memcheck 以降も読んでみる。
massif (heap profiler) はとりあえず図が生成されるのが楽しいな。
valgrind --tool=massif --format=html --alloc-fn=ruby_xmalloc --alloc-fn=ruby_xrealloc --alloc-fn=ruby_xrealloc2 --alloc-fn=ruby_xmalloc2 --alloc-fn=ruby_xcalloc ./ruby sample/test.rb
というあたりで、どこでメモリを食っているのかなんとなくわかる。(Ruby な用語でいうところの) ヒープ自体で食っているのは予想通りで、あと st がかなりあるようだ。
Fiber でスタックをコピーするところは valgrind 管理下から抜け出てコピーするわけにはいかないか。
スタック内のデータの定義・未定義状態 (V bits) を含めてコピーするには、valgrind 管理下でコピーしなければならない。
しかし、スタックの先頭を越えたところにアクセスすると valgrind が文句をいうので、それも避けなければならない。
アクセスしてはいけないかどうかを示すのは A bits という情報らしいが、これはいまのところ自由には調べられないようである。
うぅむ。スタックの先頭を正確に検出するコードを入れざるを得ないか。これはポータブルにならないからやりたくなかったのだが、しょうがないな。
それをやってしまうのであれば、保守的 GC のほうでもスタックの (未定義かもしれない) 値を読んだ後、読んだデータを VALGRIND_MAKE_MEM_DEFINED で定義済みに変えてしまえばいいので、valgrind 管理下で済むか。
スタックの先頭を正確に得るには、というのは、x86 であれば、よーするにスタックポインタの値を得ればいい、ということである。(SPARC V9 の stack bias のように、そうはいかないアーキテクチャもある)
とすると、GCC であれば、asm で次のようにできる。
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 int main()
5 {
6 int *sp;
7 int v;
8 __asm__("mov %%esp, %0" : "=r" (sp));
9 v = sp[3];
10 v = sp[2];
11 v = sp[1];
12 v = sp[0];
13 v = sp[-1];
14 v = sp[-2];
15 v = sp[-3];
16 exit(0);
17 }
valgrind をかけると、sp[0] が問題なく読める限界で、それより前の sp[-1] などは問題が検出される。
% valgrind ./a.out ==989== Memcheck, a memory error detector. ==989== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al. ==989== Using LibVEX rev 1658, a library for dynamic binary translation. ==989== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP. ==989== Using valgrind-3.2.1-Debian, a dynamic binary instrumentation framework. ==989== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al. ==989== For more details, rerun with: -v ==989== --989-- DWARF2 CFI reader: unhandled CFI instruction 0:50 --989-- DWARF2 CFI reader: unhandled CFI instruction 0:50 ==989== Invalid read of size 4 ==989== at 0x8048399: main (s.c:13) ==989== Address 0xBEA718DC is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes ==989== ==989== Invalid read of size 4 ==989== at 0x80483A4: main (s.c:14) ==989== Address 0xBEA718D8 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes ==989== ==989== Invalid read of size 4 ==989== at 0x80483AF: main (s.c:15) ==989== Address 0xBEA718D4 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes ==989== ==989== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 11 from 1) ==989== malloc/free: in use at exit: 0 bytes in 0 blocks. ==989== malloc/free: 0 allocs, 0 frees, 0 bytes allocated. ==989== For counts of detected errors, rerun with: -v ==989== All heap blocks were freed -- no leaks are possible.
いちおう他の方法も試してみる。
% cat r.c
#include <stdio.h>
#include <stdlib.h>
int *fp()
{
return __builtin_frame_address(0);
}
int main()
{
int *sp;
int *sp2;
int v;
__asm__("mov %%esp, %0" : "=r" (sp));
printf("%lx\n", sp);
printf("%lx\n", fp());
printf("%lx\n", alloca(0));
exit(0);
}
% gcc -g r.c
% ./a.out
bfd9c700
bfd9c6f8
bfd9c708
呼び出し先での __builtin_frame_address(0) や、alloca(0) では、正確なスタックポインタの値は得られない。
positive/negative lookahead/lookbehind assertion を総称して lookaround assertion と呼ぶそうだ。
日本語にはなんと訳すのだろう?
プログラミング Perl 第3版 volume I を見ると、「ルックアラウンドアサーション」と書いてあった。
ふと、test_integer.rb を書いてみる。
狙い目は Fixnum と Bignum の境目なわけであるが、平坦にテストを羅列していくのには飽きたので、もうちょっと楽なやりかたを考える。
適当に選んだ数の並びを VS = [...] として用意し、足し算であれば以下のようにして実行する。
VS.each {|a|
VS.each {|b|
c = a + b
ここで c が正しいかテスト
}
}
問題は、テストをどうやって行うか、である。
もし + を使わずに a + b を求めることができれば、それと c を比較すれば良い。
だが、+ を使わないで足し算するのは厄介である。
素朴には succ でインクリメントすることが考えられる。だが、これは遅すぎる。
d = a
b.times { d = d.succ }
効率的なものを自分で実装するのは面倒だし、複雑なコードを書くとそこにバグが入り込みやすいので本末転倒である。
また、bc や python を呼び出すということも考えたが、インストールされているとは限らない。
いろいろ考えた後、Hacker's Delight を思い出した。これには、足し算と論理演算の関係がいくつか書いてあるのでそれを利用できる。
たとえば、a+b = a-~b-1 という関係が載っていて、これはテストに使える。
あと、足し算の結果を比較するのとは違うが、c - a = b とかの検算も行う。
「検算」で検索して九去法なるものを知る。
でも、そのままやるにはまず 10進に変換しないといけないから、ちょっとよろしくない。
16進でやると、九去法ならぬ十五去法になるかな?
いや、単に mod 15 で比較すればいいだけか
assert_equal(((a % 15) + (b % 15)) % 15, (a + b) % 15)
むしろ、15 じゃなくて適当な素数を使ったほうがいい?
assert_equal(((a % 127) + (b % 127)) % 127, (a + b) % 127)
ふと思ったのだが、暗証番号に生年月日を使う人が多くて困る、というなら、暗証番号を 4桁じゃなくする (たとえば 5桁にする)、という対策を行うところはないのだろうか。
ふと、バックトラッキング型の正規表現エンジンで、正規表現の否定をあつかうことを考える。
ふむ。素朴にやるとちょっと嫌な部分が出てくるが、問題設定をちょっと変えればかなりうまくいくな。
来週の講義資料に入れるかどうか...
とりあえず書いてみた。
第12回の資料だが、61枚になってしまった。多すぎ。
それでも、なぜ「否定」じゃなくて「含まない」にしたのかも説明していない。それを説明するには「否定」の実装を示さないといけなくてさらに枚数が増えてしまう。
あきらめてばっさり削るか?
ふと、Computer Science Teaching to be Redesigned を読む。
teaching students a lot of facts and then giving them a problem to solve という、旧来のやりかたはまさに自分がやっていることであり、どうもうまくないなぁ、と思っていたことでもある。
代わりに、starts out by giving them a problem とする、というのは、できればやってみたい。
でも、そうするには、講義の初期段階で、その時点では理解できないプログラムを与えて使わせることになる。まぁ、しょうがないか。
ふと「蒟蒻畑 白桃味」を買ってみる。蒟蒻ゼリーというのはいったいどのように危険な食感なのであろうか。
その後の帰り道で職質される。危険なものをもっていないかどうか、かばんをあけて見てもらうわけである。刃物は持ち歩かないのでとくに危険なものはない... と思いきや蒟蒻ゼリーが出てきた。
蒟蒻ゼリーは危険ではないかと主張してみたが、とりあってくれなかった。
帰ってからひとつ食べてみると、うぅむ、たしかに普通のゼリーとは全然違う食感である。
注意書きによると、凍らせると固くなるので注意、とあったので、凍らせてみる。
たしかに (当然) 固くなる。固くなった結果、噛みきりやすくなっているようにおもう。
ふと『ホッキョクグマに「涼」の贈り物』というニュースが目に止まった。
動物園のホッキョクグマに氷柱が寄贈された、という話なのだが、その氷柱について『高さ一メートル、幅五十五センチ、重さ約百三十五キロの氷柱六本』と記載されている。
高さと幅と重さが載っているが、奥行きは載っていない。なんか、算数の問題っぽい匂いがする。
氷の比重を 0.9 としてみると、奥行きはだいたい 27センチか。
そういえば、氷のサイズって標準の類があるのだろうか、と思って調べてみると、やはりというかなんというか、135Kg, 36貫のこのサイズが基本らしい。
http://www.tdiary.org/20070723.html とのことなので、base_url を設定しておいた。
http://www.tdiary.org/20070723.html とのことなので、base_url を設定しておいた。
ここのところ、『ハッカーのたのしみ』を読んでいる。
というか、かなり前に読みはじめて、全ての式を理解しようと考えて途中で止まってしまい、最近もういちど止まってしまったところを読んでかなり考えた挙げ句にわかってそれでやっとまた進み始めた、のである。
引っかかったのは p.23 の x<=y を求めるふたつめの式であり、なんで x-y や y-x を使っていないのに比較ができるのか、というのがなかなか難しかった。
そこからも興味深いものが端々に出てきて、いまはやっと p.36 である。先は遠い。
ここまででも、今まで気がついていなかった話としては、加算器で (2の補数を使って) 減算を行ったときのキャリーがボローの反転だとか、乗算の入力を 2の補数とみなすかどうかは結果の下位ワードに影響しないとか、いろいろある。
なかなか楽しい。
ここのところ、『ハッカーのたのしみ』を読んでいる。
というか、かなり前に読みはじめて、全ての式を理解しようと考えて途中で止まってしまい、最近もういちど止まってしまったところを読んでかなり考えた挙げ句にわかってそれでやっとまた進み始めた、のである。
引っかかったのは p.23 の x<=y を求めるふたつめの式であり、なんで x-y や y-x を使っていないのに比較ができるのか、というのがなかなか難しかった。
そこからも興味深いものが端々に出てきて、いまはやっと p.36 である。先は遠い。
ここまででも、今まで気がついていなかった話としては、加算器で (2の補数を使って) 減算を行ったときのキャリーがボローの反転だとか、乗算の入力を 2の補数とみなすかどうかは結果の下位ワードに影響しないとか、いろいろある。
なかなか楽しい。
日曜まで network unreachable
LC2007 のプログラム委員会
なかなか面白い論文があって、その論文は他の人も面白いといっていた。
[latest]