ひ日誌

_ [sicp][scheme] SICP読書会 #36 記号微分

サイボウズラボにて(会場提供どうもです)。記号微分。問題2.56まで。4章超循環評価器への布石っぽい気がしないでもない。

_ [rubycocoa][rubyosa][macosx] GUIのテスト自動化

RubyOSA の ML で流れていた Sending keystrokes via System Events を見て、System Events.app あたりを使えば、サンプルアプリを起動して操作するテストもある程度自動化できるかなと思った。

perform v : cause the target process to behave as if the action
                  were applied to its UI element
perform action : The action to be performed.

を使うとNSResponderのインスタンスのactionを外から実行させられそう。実行後、スクリーンキャプチャして、画像の比較(パターンマッチ)でテストするとか…

_ [ruby] 標準入出力を自前IOに切り替えるとして

$stdout と $stderr を自前のIOオブジェクトに置き換えようか、などと考えてるんだけど、その場合、何を実装する必要があるんだろうか？StringIOも一通り実装してるぽいし、全部実装しなきゃいけないのかな？JavaだかPowerPlantだか忘れたけど、とりあえず read_byte と write_byte くらい実装しとけば効率はともかく動く、みたいになってると思うんだけど、そんな風なのはないんだろうなぁ。普通、IOを自前で作る必要はあんまりなさそうだからしょうがないけど…

_ [macosx][rubycocoa][ruby][objective-c] addRubyMethod_withType の構文糖

普通のRubyCocoaプログラムの中で、addRubyMethod_withType という名前をそのまま使うのは、生々し過ぎて ruby-ism に少し欠ける気がしたので、構文糖(syntax sugar)あるいは DSL みたいなものを考えてみました。

RubyCocoa 0.4.2から0.4.3d2の間に、OSX::NSObjectの派生クラスでは addRubyMethod_withType というクラスメソッドが追加されてる。これは、Rubyプログラムで定義したメソッドとその型をObjective-Cランタイムに対して宣言する、というような意味を持っている(ですよね？)。このメソッド名は、実装がやることをObjective-C世界の立場で説明しているものなのだけど、Rubyプログラムに書くと:

class Foo < OSX::NSObject
  def foo_bar(view, index)
    ...
  end
  addRubyMethod_withType(foo:bar:', '@@:@I')    
end

こんな感じになって、普通のRubyCocoaプログラマ視点から見るとどうにも違和感がある。それから、CamelCase + '_' はちょっと…。そこで、まず第一段階として別名を考えてみる。これは要するに型宣言みたいなものなので、それっぽい雰囲気で:

class Foo < OSX::NSObject
  def foo_bar(view, index)
    ...
  end
  objc_form 'foo:bar:', '@@:@I'
end

というような感じ。objc_form という名前の他に、objc_type, objc_prototype, method_form, method_type などなどを思いついたけど、ここではとりあえず objc_form を使った。

さて、objc_form (仮名) の第一引数は、Rubyのメソッド名と同じ名前を指定できる方が普通のRubyCocoaプログラマにやさしくていいかもしれない。引数の数がわかっているので、Objective-Cのセレクタ名に解決可能なはずだ。

class Foo < OSX::NSObject
  def foo_bar(view, index)
    ...
  end
  objc_form :foo_bar, '@@:@I'
end

宣言しなくてはいけないところがRubyっぽくなくてやや悲しいが、それでも、addRubyMethod_withType と書くより気分はでる。さらに、rails後の現在では、foo_bar が二度出てくるのはDRYじゃなくていや！という気がしなくもないので:

class Foo < OSX::NSObject
  def_with_form(:foo_bar, '@@:@I') do |view,index|
    ...
  end
end

というようなDSL的疑似構文を追加するのもいいかもしれない。

さらに、'@@:@Iabracadabra' と呪文のような型指定文字列(詳しくはこちら)も、普通のRubyCocoaプログラマにやさしくないから:

'I -> @ -> @'

と書けるといいかもしれない、などと一瞬思ったのだけど、これは、僕が半端にHaskell入門しかけた素人だからです、多分。

_ サーバ引っ越し

ひ日誌のサーバーホストを引っ越した。tDiaryもようやく新しいバージョンに更新。ローカルで動作チェック後、引っ越ししたとたん半日ほどダウン…うむむ。ローカルで動作確認してるときにできたRSSがそのまま出てしまったorz

_ [scheme][sicp] SICP読書会 #38 抽象化のTPO

三田会場にて(会場提供どうもです！)。今回は2.3.3集合演算の部分。

問題2.59は、集合の和を演算する関数 union-set を実装せよ、集合は順序づけられないリストで表現する。というようなもの。これを:

;; (a) 集合の表現に依存してない(つもりだった(後述)) union-set
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (adjoin-set (car set1)
                          (union-set (cdr set1) set2)))))

と提示したら、adjoin-set は cons でいいんじゃないの？という話になった。もともとは自分でも:

;; (b) 順序づけられないリストで表現した集合用の union-set (のつもりだった(後述))
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (cons (car set1)
                    (union-set (cdr set1) set2)))))

cons を使って書いてたのだけど、「集合の表現にはいろんな方法があってそれぞれ一長一短」みたいな論旨の2.3.3を読み進めるうちに、cons よりも adjoin-set を使って汎用的にした方がいいような気がしてきて書き直した。しかし、計算量を考えると、cons 使用のときはunion-setの単純な繰り返しでθ(n)、adjoin-set 使用のときはadjoin-setの分が加わってθ(n*2n) 、のような差が出てくる。そもそも、計算量以前の問題として、null? を使ってる時点で、空集合は空リストで表現するという実装に思いっきり依存してた。

ここで実装する adjoin-set, union-set, intersection-set は、集合の「順序づけられないリストによる表現」を扱う演算のグループである、と考えると、このunion-setでは、データ表現の抽象化ではなく計算量を重視すべきだろう。ここは抽象の壁の向こう側。ブラックボックスの内部なのだ。ところ構わず抽象化すればいいもんじゃないということを思い知った。

この話は、二次会のとき話した、ファクトリパターン、Ruby の Enumerable#each、$stderr.write あたりの話とつながってますね。今気付いた。

とここまで書いてから…ん？上の (b) は union-set になってないじゃん！

もともと、こんな風に実装してたことを思い出した。

;; (c) 順序づけられないリストで表現した集合用の union-set
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((element-of-set? (car set1) set2) (union-set (cdr set1) 
                                                      set2))
        (else (cons (car set1)
                    (union-set (cdr set1) 
                               set2)))))

これを見ると adjoin-set に置き換えたくなってくる。忘れてたけど、もともと、そうして(a)に行き着いたのだった。

この(c)の計算量はθ(n*n)で、(a) との差は最大2倍。見た目だと(a)の方が読みやすいので、やっぱり (a) がいいね。抽象化云々はなかったことにして…

_ ひ日誌へのリンクが変

調べてみると、外からこの日誌へのリンクをクリックしてもつながらなくなってる模様。いつからそうなってるのかよくわからないけど、多分、ホストを移動してtDiaryのバージョンを上げてから。人力HTTPクライアント(telnetで手入力)してみると、HTTP GETのヘッダーからRefererを省略した場合にはサーバは普通に応答して問題なしだけど、Refererを入れると接続したまま黙ってしまう。Refererがひ日誌内部かGoogleの検索結果ページの場合は問題なくつながるけど、del.icio.us, flickr, hatena などではだめ。うーん、どーなってるんだろう？

OK:

• Refererなし
• ひ日誌自身
• Yahoo検索の結果ページ
• Google検索の結果ページ

NG:

• del.icio.us からのリンク
• flickr からのリンク
• Hatenaアンテナ
• Yahooブログ検索の結果ページ
• Goo検索の結果ページ
• 他にもたくさん

Yahoo検索とGoogle検索だけOKというところが謎。Googleブログ検索からは根本的にリンクされてなかったorz

(追記) tDiaryのspamフィルタ設定の「DNSBLに問い合わせを行わないホストを指定します」で指定するとうまくいくらしい。ということはDNSBLへの問い合わせで時間がかかっている・失敗してるということだろうか？→あたり！

_ [programming][scheme][c][sicp] Joelのひっかけ問題

Javaスクールの危険の試してみようをやってみた。自分が学生だったときのことを考えてみると、まず一問目で立ち往生してしまった可能性が高い。その時点で高階関数をまともに学んでなかったからとはいえ、どうやら向いてなかったらしい。さて、一問目にaccumlateの定義が出てくるという文脈で、2問目を:

int main(int argc, char **argv) {
  if (argc == 1) {
    putchar('\n');
    return 0;
  } else {
    putchar(argv[1][0]);
    return main(argc-1, argv+1);
  }
}

と、やや手続きくさい再帰(しかも末尾再帰)で書いてみた。なかなかいい感じに書けたなと悦にいったあと、解答例を見たら普通にforで書いてた…JoelひどいよJoel

この本を読んでいると一問目はごく自然に見えるようになってきます。ただし、二問目を解くときforループを使いたくなくなるという副作用を伴うことがあります。

_ [c][programming] gcc の末尾呼び出し最適化

上のCプログラムのしょーもないバグをこっそり直したついでに、gccでどんな風に末尾呼び出し最適化されるのかやってみた。Mac OS X 10.4 に入っているManページgcc(1)を見ると:

-foptimize-sibling-calls
    Optimize sibling and tail recursive calls.
    Enabled at levels -O2, -O3, -Os, -Oz (APPLE ONLY).

とあったので、このオプションを付けて、さっきのプログラムをコンパイル:

$ gcc -arch i386 -S -foptimize-sibling-calls joel.c

すると:

_main:
        pushl   %ebp            ; 呼び出し前のベースポインタ保存
        movl    %esp, %ebp      ; ベースポインタ更新
        subl    $40, %esp       ; スタック更新
        cmpl    $1, 8(%ebp)     ; test(argc == 1)
        (中略)
        movl    12(%ebp), %eax  ; %eax := argv 
        addl    $4, %eax        ; %eax += 4      (argv + 1)
        movl    8(%ebp), %edx   ; %edx := argc
        subl    $1, %edx        ; %edx -= 1      (argc - 1)
        movl    %eax, 4(%esp)   ; argv + 1 (引数としてスタックに積む)
        movl    %edx, (%esp)    ; argc - 1 (同上)
        call    _main           ; main

あれれ、末尾呼び出し最適化されてないような気がする。それじゃ-O2でコンパイルしてみよう:

$ gcc -arch i386 -S -O2 joel.c -o joel-o2.s

今度は末尾呼び出し最適化された模様。

_main:
(中略)  
        movl    8(%ebp), %eax   ; %eax := argc
        cmpl    $1, %eax        ; test (argc == 1)
        je      L4              ; goto L4 if the test
        movl    12(%ebp), %esi
        xorl    %edi, %edi      ; %edi := 0
        subl    $1, %eax        ; %eax -= 1  (argc - 1)
        movl    %eax, -12(%ebp) ; 
L5:
        movl    4(%esi), %eax   ; %eax := argv + 1 
        movsbl  (%eax),%eax     ; %eax := *(%eax)
        movl    %eax, (%esp)    ; 1starg := *(%eax)
        call    L_putchar$stub
        addl    $1, %edi        ; %edi += 1
        addl    $4, %esi        ; argv += 1
        cmpl    -12(%ebp), %edi ; test (%edi == argc - 1)
        jne     L5              ; goto L5 if not the test
L4:
        movl    $10, (%esp)
        call    L_putchar$stub
(以下略)

しかし、ループを制御してるargcの扱いも最適化されてて、バイナリアンじやない僕(バイナリアン度33点)にはパッと見何してるんだわかりにくいコードになってた。それでも、元のソースがわかっているので i386 のコードはどうにか読み解けなくもない。ところが、ppc のコード(-arch ppcで出力)するともうこれは完全に解読不可能。

Binary Hacksという本が大人気らしいので、ついつい釣られて少しバイナリくさいことをしてしまった。この本には、RubyCocoa 1.0で使用されているlibffiやGNUstepで使用されているffcallについても少し書いてありました。バイナリアン度チェックしたら、33ポイントでバイナリ成分が不足してるから読め！と言われたんだけど、積ん読がまた増えるだけかもしれないorz

_ [sicp][scheme] SICP読書会 #39 二進木としての集合

月島にて(会場提供どうもです！)。二進木としての集合。

問題 2.63の計算量を考える問題では、そもそもステップ数って何？というあたりでちっょとひっかかる。appendのあたりで話が噛み合なかったのは、問題を考える手順や頭の回転の差が影響していて、最終的な結果はおそらく同じ。僕の場合は、この問題をいっぺんに全て見通す頭をもってないので、問題を切り分けて考えないとわからなくなる。まず、appendの存在は気になるけど、とりあえずそれは無視して、ループの回数がどうなってるかというところに着目する(1章のフィボナッチ数列あたりでやっていたこと)。プログラムを眺めていると、ループの回数(tree->list-1 あるいは copy-to-listが呼ばれる回数)はどちらも同じであることがわかる。そこで初めてappendの有無による影響について考える。ループ回数が同じであることがわかる人には当たり前のように一瞬でわかるので、しょっぱなからappendの差に目がいっている、というあたりで、噛み合なかった模様、脳クロック数の違い…とこんなこと分析してもしょうがないけど。