アサブロはどこへ向かっているのか2008年06月03日 01時49分

いやあ、萌えキャラ作ってる場合じゃないですよ。それよりも spam 対策を。コメント / トラックバック数制限なんてコメント / トラックバック欄を閉じてるのと変わりないですから。

ちなみにアサブロたんを描いてるのは誰なんでしょうね?

SICP 読書会 #22008年06月10日 23時23分

yukky さん主催の SICP 読書会、その第 2 回に参加しました。今回はあらかじめ予習範囲を提示し、最初の 30 分間でそこを読み進めた上で、後はもっぱら範囲内の問題にあてるという形式でした。私の分も含め各人の解答は当日のチャットログから参照できます。

開始前の空き時間で最初のほうの問題をやっておいたのですが、それでも時間がぜんぜん足りなくて息切れしてしまいそうでした。予習復習をしっかりしておかないとちょっとつらいかもしれませんね。

丸括弧と角括弧

Gauche では (Scheme では?) 丸括弧の代わりに角括弧も使えるので、cond の条件節に使うと読みやすいと教えてもらいました。確かに読みやすくはなりますが、なんだか美しくないような気がするのは私だけでしょうか。

(define (square x) (* x x))

; b の n 乗を求める
(define (expt b n)
  (cond [(= b 0) 1]
        [(even? b) (square (expt (/ n 2)))]
        [else (* b (expt b (- n 1)))]))

ユークリッドの互除法

最大公約数を求めるアルゴリズムとして有名なユークリッドの互除法ですが、英語では Euclidean algorithm といって、「互いに割る」というようなニュアンスは直接的には含まれてないのですね。

反復的プロセスへの変換

累乗と乗算を求める関数を、再帰的プロセスから反復的プロセス (末尾再帰) に直せという問題が出てきます。いろいろ悩んだすえ、以下のように考えにたどり着きました。

; b の n 乗を求める
(define (expt a b)
  (define (iter b n acc)
    (cond ((= n 0) acc)
          ((even? n)
           ; ここをどう書くか
           )
          (else
           ; ここをどう書くか
           )))
  (iter b n 1))

iter はどういう関数かを考えます。S 式表記から離れますが、acc = 1 のとき exp-iter(b, n, 1) は b^n を返します。n = 0 のとき、iter(b, 0, acc) は acc を返します。これらから考えていくと、iter は iter(b, n, acc) = b^n * acc という関数であることが推測されます。n が偶数のときは n / 2 が整数ですから、

  b^n * acc
= b^(n / 2 * 2) * acc
= (b^(n / 2))^2 * acc
= (b^2)^(n / 2) * acc

という変形が成り立ちます。n が奇数のときは、

  b^n * acc
= b^(n - 1 + 1) * acc
= (b^(n - 1) * b) * acc
= b^(n - 1) * (b * acc)

となります。つまり、

  • n が偶数なら iter(b, n, acc) = iter(b^2, n / 2, acc)
  • n が奇数なら iter(b, n, acc) = iter(b, n - 1, b * acc)

となるのです。後はこれを S 式に戻してやれば以下のように完成します。

; b の n 乗を求める
(define (expt a b)
  (define (iter b n acc)
    (cond ((= n 0) acc)
          ((even? n) (iter (square b) (/ n 2) acc))
          (else (iter b (- n 1) (* b acc)))))
  (iter b n 1))

フィボナッチ数の対数的ステップでの計算

問題 1.19 は線形写像の行列表現を利用してフィボナッチ数を O(log N) のステップ数で求める問題です。(bq+aq+ap bp+aq)T = Tpq (a b)T から行列 Tpq が求められるので、Tp′q′ = Tpq2 より p′、q′ も求められますね (行列の右肩の T転置を表します)。

四元数

なぜか SICP とはあまり関係のない四元数の話も出ました。四元数は応用として 3 次元空間での回転を表現するのに用いられますが、四元数そのものは実 4 次元ですよね。

Kanasan.JS Prototype.js CodeReading #52008年06月20日 22時21分

Kanasan.JSPrototype.js CodeReading #5 に行ってきました (当日のチャットログ参加者のブログ記事一覧)。対象は Prototype.js 1.6.0.2 です。ちなみに私は前回お休みしたので、前日にその分をざっとさらえての参加でした。

Element.Methods.Simulated.hasAttribute (2521 行目)

IE 7 は DOM 2 Core の Element#hasAttribute を実装してないので、その代替です。

Element.addMethods (2583 行目)

可変引数の処理を、引数の値が新かどうかで判断したり、arguments.length を見たりと一貫性がありません。増改築を繰り返してきた結果でしょうか?

findDOMClass (2625 行目)

Firefox などでは DOM HTML の各インターフェースに対応する擬似コンストラクタ関数とでもいうべきオブジェクトが実装されています。たとえば、DOM HTML では p 要素の要素ノードオブジェクトは HTMLParagraphElement インターフェースを実装することとなっていますが、Firefox では p 要素ノードオブジェクトのプロトタイプが HTMLParagraphElement コンストラクタ関数 (new 演算子は使えませんが) の prototype プロパティの値と同じオブジェクトになります。

HTMLParagraphElement;
// Firefox 3 => [object HTMLParagraphElement]
// コンストラクタ関数に相当するが、
// new 演算子を使ったオブジェクトの作成はできない

HTMLParagraphElement.prototype;
// Firefox 3 => [xpconnect wrapped native prototype]
// コンストラクタ関数に相当するので、
// 関数オブジェクトと同様に prototype プロパティを持つ

// p 要素ノードオブジェクトを作成
var p = document.createElement("p");

p.__proto__ == HTMLParagraphElement.prototype;
// Firefox 3 => true
// p 要素ノードオブジェクトのプロトタイプは
// HTMLParagraphElement.prototype と等しい

findDOMClass 関数は Element.addMethods の中で内部的に使われる関数で、この要素ノードのコンストラクタ関数 (のようなオブジェクト) を取得します。

Selector#shouldUseXPath (2706 行目)

should~というメソッド名はあまり見ないという声がありましたが、個人的には is~、does~と同様に時々見かける気がします。can~とはニュアンスが違いますし。

私が実際に使ったパターンとして、特定のメニュー項目を表示させるかどうかチェックするメソッドに shouldDisplay と名づけたことがありました。canDisplay だと「表示できるか」となって、表示しようと思えば表示できるので常に true を返しそうですが、使えないメニュー項目を表示させたところで意味がありませんからね。

Selector#compileMatcher (2724 行目)

CSS セレクタを基に、特定のノードを選択する関数を動的に作成しています。関数のソースを文字列としてつなげていき、最後に eval 関数を使って関数を生成、matcher プロパティにその関数を設定します。途中、関数のソース文字列を収めた配列も matcher プロパティに設定しているのがわかりづらいですね。この配列はローカル変数で持っておけばいいと思うのですが。

処理の流れとしては、CSS セレクタからトークンを切り出し、それに対応するソース文字列を追加していきます。たとえば、CSS セレクタが "#foo" (id が foo である要素を選択) だったときは以下のようになります。

// this.expression に CSS セレクタ
// (この例では "#foo") が収められている。
//
// ps は CSS セレクタの各トークンに
// マッチする正規表現を収めた連想配列。
// ps = {
//   tagName: /^\s*(\*|[\w\-]+)(\b|$)?/,
//   id:      /^#([\w\-\*]+)(\b|$)/,
//   ...
// }
//
// c は CSS セレクタの各トークンに相当する
// 処理を行うソース文字列を収めた連想配列。
// c = {
//   tagName: 'n = h.tagName(n, r, "#{1}", c); c = false;',
//   id:      'n = h.id(n, r, "#{1}", c);      c = false;',
//   ...
// }
//
// h はここでは使用しない。(消し忘れか?)
var e = this.expression, ps = Selector.patterns, h = Selector.handlers,
    c = Selector.criteria, le, p, m;

// すでに同じ CSS セレクタから関数を
// 生成したことがあれば、それをそのまま使う。
if (Selector._cache[e]) {
  this.matcher = Selector._cache[e];
  return;
}

// 関数のソース文字列を収める配列。
// これは this.matcher ではなく
// ローカル変数を使ったほうがわかりやすいかも。
this.matcher = ["this.matcher = function(root) {",
                "var r = root, h = Selector.handlers, c = false, n;"];

while (e && le != e && (/\S/).test(e)) {
  le = e;
  // 正規表現を収めた連想配列をなめていく。
  // i には "tagName"、"id" といった文字列が入る。
  for (var i in ps) {
    // i == "id" のとき、p には正規表現オブジェクト
    // /^#([\w\-\*]+)(\b|$)/ が入る
    p = ps[i];
    if (m = e.match(p)) {
      // "#foo".match(/^#([\w\-\*]+)(\b|$)/)
      // が成功すると、ソース文字列に c["id"]、すなわち
      // 'n = h.id(n, r, "#{1}", c); c = false;'
      // を追加する。ここで、Template を使うことにより
      // #{1} が m[1]、すなわち最初の後方参照に
      // 置換されるので、最終的にソース文字列には
      // 'n = h.id(n, r, "foo", c); c = false;'
      // が追加される。
      this.matcher.push(Object.isFunction(c[i]) ? c[i](m) :
        new Template(c[i]).evaluate(m));
      // CSS セレクタから正規表現のマッチ部分を
      // 削除する。マッチ部分は "#foo" なので、
      // この場合 e は空文字列になる。
      e = e.replace(m[0], '');
      break;
    }
  }
}

この、正規表現オブジェクトを収めた連想配列をなめていき、マッチしたらそれに対応する文字列なり処理なりを別の連想配列から引き出すという流れは、CSS セレクタから XPath 式を作成するときなどにも使われています。

正規表現オブジェクトのメソッド

正規表現オブジェクトには、文字列を引数にとり、正規表現パターンがその文字列にマッチしたかを真偽値で返す test メソッドがあります。文字列の match メソッドとは異なり、マッチが成功したとき、結果を収めた配列を作成するコストがかかりません。

/(a)(b)(c)/.test("abcde");
// => true

"abcde".match(/(a)(b)(c)/);
// => abc,a,b,c
// マッチが成功すると、最初の要素にマッチした
// 文字列全体、続いて各後方参照の結果を
// 収めた配列が返る。失敗すると null が返る。

なお、Prototype.js では、test メソッドの別名として match メソッドを定義しています。

/(a)(b)(c)/.match("abcde");
// => true
// Prototype.js を使った場合のみ。

また、Firefox や Opera では正規表現オブジェクトを関数のように呼び出せます。ゴルフのときなんかお世話になりますね。これは exec メソッドを呼び出したのと同じに扱われ、次のマッチ部分を探します。グローバルフラグ付きの正規表現に対しては、Perl でいうところのスカラコンテキストにおける m 演算子と同じように動作します。

# Perl
$str = 'abc';
while ($str =~ m/(.)/g) {
  print $1, "\n";
}
# => a
# => b
# => c
// JavaScript
var str = "abc";
var re = /(.)/g;
var match;
// Firefox/Opera では re(str) でも OK。
while ((match = re.exec(str)))
  print(match[1]);
// => a
// => b
// => c

compileXPathMatcher (2757 行目)

CSS セレクタから XPath 式を生成します。CSS セレクタと XPath での表現の対応表が参考になるかもしれません。

CSS セレクタでは属性セレクタや lang 擬似クラスなどを除き、基本的に要素を元にした選択しか行えないのに対して、XPath では文書ノードやテキストノードも扱えれば、文字列処理や四則演算も可能なので、より大きな表現力を持つことになります。しかし、XPath はユーザインターフェースとの連携はあまり考えられてなかったせいか、CSS セレクタの hover 擬似クラスや focus 擬似クラスを再現することはできません。Prototype.js では CSS セレクタに checked 擬似クラスが含まれるときなどはあえて XPath を使わないようです。

正規表現の文字クラスと後方参照

Selector.patterns.attr (2972 行目) は CSS セレクタの属性セレクタにマッチする正規表現です。ここから文字列リテラルにマッチする部分だけを抜き出し、再構成すると以下のようになります。

(['"])([^\1]*?)\1

作成者の意図としては、単一引用符か二重引用符で始まり、その引用符以外の文字が続いて、その引用符で終わる部分ということでしょう。しかし、この正規表現にはエスケープシーケンスを考慮していないという以外にも過ちが存在します。

後に foo と続かない foo という文字列 (foo という文字列、ただし foofoo という文字列を除く) を表す正規表現パターンを考えてみましょう。よくある間違いとして foo[^foo]foo[^(foo)] が挙げられます。文字クラスは 1 文字のみを表し、文字クラス中で多くのメタ文字は意味を持ちません。正解は foo(?!foo) となります。

さて、foo[^(foo)] が間違いなら (foo)[^(foo)] も間違いであることはすぐわかります。とすれば二つ目のグループを後方参照に置き換えた (foo)[^\1] が間違いであるということも導き出せるでしょう。文字クラスが 1 文字を表現するものである上、複数文字からなる文字列を取りうる後方参照は文字クラス内では意味を持たないからです。これはその後方参照が 1 文字のみにマッチしていたときも例外ではありません。

間違いなら間違いでどう間違って解釈されるのかというと、これは 8 進エスケープシーケンスとして扱われます。つまり、文字クラス内の \1 は、U+0001 START OF HEADINGという制御文字を表すのです。

とはいえ、元の正規表現に戻って考えると、これが実用上問題になることは少ないと思われます。元の正規表現ではエスケープシーケンスの存在を考えず、引用符に囲まれた内容を最短一致で抜き出しているからです。この場合、文字列リテラル中に文字 U+0001 (大元の Prototype.js では U+0004 END OF TRANSMISSION) が含まれていれば問題になりますが、現実には文字列中に制御文字を含めることはないでしょう。エスケープシーケンスも考えると単一引用符の場合と二重引用符の場合を分けて書くのが簡単でしょうが、そうでないなら (['"])(.*?)\1 で十分だと思います。

Selector.handlers.concat (3002 行目)

なぜ a.concat($A(b)) と直接書かずにユーティリティー関数を用意しているのかと思ったら、IE ではこの部分を上書きしていました (3357 行目)。IE では getElementsByTagName メソッドでコメントノードも取得してしまうことがあるので、それをはじくために関数をかましているようです。

Selector.handlers.mark (3009 行目)

真偽値をとれば十分なプロパティに対し、true ではなく Prototype.emptyFunction を代入しています。確かにそれでも真と判定されますが、なぜわざわざ関数オブジェクトを使うのか謎です。

Selector.handlers.tagName (3095 行目)

どうもこのあたり読みづらいコードが続きます。個人的に気になったのは 3105 行目付近、

if (combinator == "descendant") {
  for (var i = 0, node; node = nodes[i]; i++)
    h.concat(results, node.getElementsByTagName(tagName));
  return results;
} else nodes = this[combinator](nodes);

if 節の最後に return 文があるので最後の文が else 節内にある必要はありません。else 節をなくし、最後の文を if 文の外に出したほうが読みやすいと思います。ほかにも、Selector.handlers.id 内の if 文の連続 (3120 行目) は switch 文にしたほうがわかりやすいという意見もありました。

ライトニングトーク

今回は一度に時間をとるのではなく、コードリーディングの合間合間を縫ってライトニングトークが行われました。

37to さん
jQuery を使って作られたプレゼンテーションツール QueryNote の紹介です。QueryNote 中でダブルクリックするとシェル (Jarminal) が起動します。ls でメンバ一覧を表示できたり、cd document などとしてスコープを変更できたりして面白いです。
hoge1e3 さん
iPhone ライクなスクリーンキーボードを実現する iPhone.js の紹介です。キーボード部分をドラッグすると入力可能な文字がポップアップされ、ドロップするとそれが入力されるという仕組み。補完にも対応しており、A で alert() と入力できたり、E で入力したソースコードを実行できたりします。ただし、iPhone ではマウス関係のイベントは click しか取れないそうで (それ以外はスクロールや拡大縮小などシステムに取られる) 動かないとの報告がありました。フォームコントロールなどの編集領域以外では文字列選択もできないようで、製作者側としては困ったところです。
Kanasan さん
ページ内に widget を表示するための Greasemonkey スクリプト USWManager の紹介です。USWManager を利用して widget を作れば、複数タブ間で widget の表示位置を共有できたりします。ただ、大量にタブを開いていると動作が非常に重くなってしまうのが難点とのこと。
ujihisa さん
自分のマシンに同一ネットワーク内から接続があると有須子を表示するスクリプト usukod の作成と実演。誰かが侵入してくるとその人を驚かせる……ではなく自分が驚きます。

雑感

正規表現、CSS セレクタ、XPath が絡んでくる Selector はなかなかの難所でしたが、ここを越えたことで残りは 847 行。終わりが見えてきました。ここまで来れたのも Kanasan さん始めスタッフの皆さんのおかげ、参加者ともども感謝です。

Greasemonkey スクリプトとイベントで通信2008年06月26日 08時12分

Greasemonkeyスクリプトとウインドウ間で安全に通信する」にて、DOM イベントを用いた Web ページと Greasemonkey スクリプトとの通信について述べられています。そちらでは dispatchEvent メソッドの返り値による 1 bit 通信に触れていますが、やはりもっと自由にデータをやり取りしたいもの。そのためにはどのような方法があるでしょうか。

独自プロパティ

真っ先に思いつくのは、Web ページ側でイベントオブジェクトを作成した際、独自プロパティを追加する方法ですが、これはだめです。Greasemonkey スクリプト側ではイベントオブジェクトの独自プロパティを取得できません。event.wrappedJSObject.myProperty のように wrappedJSObject を介せば取得できますが、せっかく安全のため Firefox 側でラッパーに包んでくれたのに、それを外すべきではありません。wrappedJSObject は危険です。

CustomEvent

こんなこともあろうかと DOM 3 Events 草案では CustomEvent というイベントが用意されています。これを使えばイベントオブジェクトに独自のデータを保持できます。しかし、Firefox 3 は DOM 3 Events に対応していません。終了。

CommandEvent

Firefox 3 では新しく CommandEvent というイベントに対応しています。これは XUL での利用を考えて追加されたものですが、Web ページから作成することもできます。CommandEvent には文字列型の command プロパティがあるので、ここにデータを格納できます。JSON などを使えば複雑な構造のデータもやり取り可能です。

// Greasemonkey スクリプト
document.addEventListener("GMPingCommand", function (request) {
  var response = document.createEvent("CommandEvent");
  response.initCommandEvent("GMPongCommand", true, false,
                            'You said "' + request.command + '"');
  document.dispatchEvent(response);
}, false);
// Web ページ
window.addEventListener("load", function (event) {
  var request = document.createEvent("CommandEvent");
  request.initCommandEvent("GMPingCommand", true, false,
                           "Hello, world!");
  document.dispatchEvent(request);
}, false);

document.addEventListener("GMPongCommand", function (response) {
  alert(response.command); // => You said "Hello, world!"
}, false);

DataContainerEvent

Firefox 3 では新しく DataContainerEvent というイベントに対応しています。これも XUL での利用を考えて追加されたものですが、Web ページから作成することもできます。DataContainerEvent に専用の初期化メソッドはありませんが、getData メソッドと setData メソッドがあります。つまり、このイベントオブジェクトは辞書として扱えるのです。基本的に任意の型の値を格納できますが、Web ページと Greasemonkey スクリプトの間で使おうとするとセキュリティ制限がかかります。

Web ページで値を設定し、Greasemonkey スクリプトでそれを取得する場合、プリミティブ値 (undefined、null、文字列値、数値、真偽値) はそのまま取得できますが、JavaScript のオブジェクトや配列は取得できず null が返ります。Window オブジェクトや DOM ノードオブジェクトはラッパーに包まれます。なお、存在しないキーの値を取得しようとすると null が返ります。

逆に、Greasemonkey スクリプトで値を設定し、Web ページでそれを取得する場合、JavaScript のオブジェクトや配列もそのまま返されます。しかし、権限の異なるオブジェクトをさらすことになるので、データのやり取りはプリミティブ値のみにとどめるべきでしょう。Window オブジェクトや DOM ノードオブジェクトに関しては、ラッパーを値に設定してもラッパーが外されて返されます。

// Greasemonkey スクリプト
document.addEventListener("GMPingDataContainer", function (request) {
  alert(request.getData("number")); // => 42
  alert(request.getData("object")); // => null
  alert(request.getData("window"));
  // => [object XPCNativeWrapper [object Window]]

  var response = document.createEvent("DataContainerEvent");
  response.initEvent("GMPongDataContainer", true, false);
  response.setData("data",
                   'You said "' + request.getData("data") + '"');
  document.dispatchEvent(response);
}, false);
// Web ページ
window.addEventListener("load", function (event) {
  var request = document.createEvent("DataContainerEvent");
  request.initEvent("GMPingDataContainer", true, false);
  request.setData("number", 42);
  request.setData("object", { foo: 42 });
  request.setData("window", window);
  request.setData("data", "Hello, world!");
  document.dispatchEvent(request);
}, false);

document.addEventListener("GMPongDataContainer", function (response) {
  alert(response.getData("data")); // => You said "Hello, world!"
}, false);

MessageEvent

Firefox 3 では新しく MessageEvent というイベントに対応しています。これは HTML 5 草案で定義されているもので、文書間メッセージングなどで利用されます。文書間メッセージングについては、現在好評発売中の WEB+DB PRESS Vol. 45 の連載「JavaScrit + ブラウザ探検 第 2 回 気になる Firefox 3 の新機能」に詳しく載っていますので、ぜひ購入しましょう。MessageEvent には文字列型の data プロパティがあるので、ここにデータを格納できます。

// Greasemonkey スクリプト
document.addEventListener("GMPingMessage", function (request) {
  var response = document.createEvent("MessageEvent");
  response.initMessageEvent("GMPongMessage", true, false,
                            'You said "' + request.data + '"',
                            location.protocol + "//" + location.host,
                            "", window);
  document.dispatchEvent(response);
}, false);
// Web ページ
window.addEventListener("load", function (event) {
  var request = document.createEvent("MessageEvent");
  request.initMessageEvent("GMPingMessage", true, false,
                           "Hello, world!",
                           location.protocol + "//" + location.host,
                           "", window);
  document.dispatchEvent(request);
}, false);

document.addEventListener("GMPongMessage", function (response) {
  alert(response.data); // => You said "Hello, world!"
}, false);

ここでは initMessageEvent メソッドの第 5 引数 origin と第 7 引数 source にそれぞれページの生成元と Window オブジェクトを渡しましたが、これは空文字列と null でも構わないでしょう。

XULCommandEvent

Greasemonkey スクリプトではなく拡張機能ですが、分割ブラウザイベントを用いた API を提供しています。そこで使われているのが XULCommandEvent で、上記三つとは異なり Firefox 2 以下でも使えるという利点があります。ただし、直接文字列を格納することはできないので、別のイベントのイベント名を使うという荒業に出ています。ちなみにこの API は Stylish の作者の提案をきっかけに作られたそうです。

独自属性

以上の方法はイベントのみで完結する、すなわち文書構造をいじらないことを前提としたものでした。文書構造を変更し、時には不正な HTML 文書になってもいいというのなら、HTML 要素を追加したり要素に独自属性を追加したりすることで、その要素、属性経由で値をやり取りできます。Firebug がとっているのと同じような方法です。

名前空間

イベントを用いて通信する以上、あらかじめイベント名を決めておく必要があります。ここで、安易にイベント名を決めてしまうと、複数の Greasemonkey スクリプトや拡張機能の間で名前が衝突してしまうかもしれません。そこで、DOM 3 Events 草案ではイベントの種類を特定するのに、従来のイベント名に加えて名前空間 URI を用いるようになっています。しかし、Firefox 3 は DOM 3 Events に対応していません。終了。

と終わってしまうのもなんなので、ここは DOM 2 Events の流儀に従うことにしましょう。MyGMMessage のようにイベント名に接頭辞 (この例では MyGM) をつけるのです。ただし、DOM という接頭辞は DOM Events によって予約されているので使ってはいけません。DOMContentLoaded や DOMMouseScroll などはだめな名前の典型です。

なお、DOM 3 Events のことも考えれば、イベント名は XML 名前空間における NCName、すなわち名前空間接頭辞を含まない XML の要素名に使える文字列にすべきでしょう。

まとめ

個人的には、Firefox 3 を対象にするなら CommandEvent がよいと思います。上で書いた中では使い方も一番シンプルですし、やり取りするデータが文字列に限定されるので余計な心配を減らせます。

さて、使えそうなイベントが三つも追加された Firefox 3 ですが、これ以外にもさまざまな新機能が搭載されています。現在好評発売中の WEB+DB PRESS Vol. 45 の連載「JavaScrit + ブラウザ探検 第 2 回 気になる Firefox 3 の新機能」に詳しく載っていますので、ぜひ購入しましょう。大切なことなので 2 回言いました。