"On Lisp―Advanced Techniques for Common Lisp" (Paul Graham)

を読んだ。

・Lispの基礎から、マクロ、遅延評価、Schemeと継続、継続をCommonLispで実装して、継続を使った非決定的アルゴリズムの実装、Prolog

初めて関数型プログラミング、というかLispを勉強した身にとっては全編興味深い、特に22章の「非決定性」が面白かった。

On Lisp - 非決定性

非決定的アルゴリズムはある意味では超自然的な予見に基づいて動作するものだ．超能力を持ったコンピュータに触れることのない私達に，どうしてそんなものが必要なのだろうか？\ それは非決定的アルゴリズムを決定的アルゴリズムでシミュレートできるからだ．純粋に関数的なプログラム ---すなわち副作用の一切ないもの--- では，非決定性は特に直截的になる．純粋に関数的なプログラムでは非決定性はバックトラックを用いた探索で実現できる．

バックトラックによる非決定性の実装例が紹介されてる、乱暴に言うと「複数の選択肢がある時、その時点の継続を保存しとりあえず一つの選択肢を選んで処理を続ける。成功すればOK、もし選択が失敗してた場合選択前の過去に戻って、別の選択肢を選んで処理を継続する」で良いのかな。

とりあえず理解のためにRubyで実装してみた。

class Nond
  def initialize
    @paths = []
  end

  def choose(choises)
    if choises.empty?
      failed
    else
      return callcc do |c|
        @paths.unshift(lambda{ c.call( choose(choises[1..choises.length]) ) })
        choises[0]
      end
    end
  end

  def failed
    if @paths.empty?
      raise "Can't find more choises."
    else
      @paths.shift.call
    end
  end
end

Ruby1.8 にも継続があるので、ほぼ本のまま。試してみる。

@nond = Nond.new

def parlor_trick(sum, firsts, secounds)
  first = @nond.choose(firsts)
  secound = @nond.choose(secounds)

  if sum == first + secound
    "The sum of #{first} #{secound}"
  else
    @nond.failed
  end
end

p parlor_trick(7, [1,2,3,4,5], [1,2,3,4])

二組の数字のリストから加算の結果が sum と等しい組み合わせを返す。

実行してみると確かに3と4で7になってる。

もう一例、今度は名前のリストから "Igor" を見つける

def igor(names)
  name = @nond.choose(names)
  if name=="Igor"
    p "Found Igor!"
  else
    @nond.failed
  end
end

p igor(["Yakov", "Yulli", "Raisa", "Iwan", "Igor", "Daniel", "Egor"])

肝の関数 choose と fail の実装を見れば納得できるけど、アプリケーションのコードだけを見るとまるで choose が超能力で正解を導き出したように見える、その実装も「失敗したら過去に戻ってやり直す」てのは凄いな。

この22章非決定性の発展で、24章ではLispの埋め込み言語としてPrologを実装してるけど、ここまでいくと正直理解があいまい。。また読み直そう

On Lisp - Prolog

Prolog面白そうだな、どこから勉強するのが良いんだろ。とっかかりとして。

Google Social Graph API

Googleが面白いAPIを出した、Web上にあるソーシャル情報に関するメタデータ（XFNとFOAF）をGoogleがクロールしてWebAPI化する Google Social Graph API

これに合わせて fooo.name の本人リンクにも、メタデータとして rel="me" を付けました（メタデータ的に "me" は意味が間違っている気もするけど）http://fooo.name/accounts/tkmr

これでfooo.nameが整えたデータもGoogle APIに反映されるかな。そういえば昔 fooo.nameでもXFN解析やろうかなと思ったけど「XFNなんてどうせ誰もつけてねえよ」と思って無視してた、でもこう見ると意外に面白いな。。

例えばTwitter、Twitterは "me" や "contact" というXFNのメタデータを埋め込んでいるので上手くソーシャルグラフが取れてる。

http://socialgraph-resources.googlecode.com/svn/trunk/samples/findcontacts.html?q=http%3A%2F%2Ftwitter.com%2Ftkmr

逆にXFNやFOAFを埋め込んでないサイトの関係は取れない、http://blog.tkmr.org/ と http://twitter.com/tkmr が "me" の関係なのは自分（や一部の人）は判るけどメタデータとしてマークアップしてないのでGoogleには判らない。まあ当然の話だけど。

メタデータ

Social Graph API に近い目的をもったfooo.name はSocial Graph API があれば要らないか？と考えると、fooo.nameは他人がメタデータを補完する、Social Graph APIは本人が書いたorシステムが書いたメタデータを集める。レイヤーの違いというポジションがあるかも。fooo.nameの利用者がカオスなWebにメタデータを補完してくれる。

Social Graph API はGoogleらしいアプローチで面白いし王道だと思う。でも現実的にWebの大部分にはメタデータが付いてないし、自分のサイトにリンクを貼るとき rel="me" を付ける人なんてネットユーザの1%にもすぎないと思う。

例えば、皆が "次のページ" へのリンクにメタデータ rel="next" を付けるとAutoPagerize（とOpera）で超快適にネットブラウジングできるけど、それを強制することはできないし、なかなかそう上手くもいかないので AutoPagerizeはWikiで各サイトのメタデータ（SITEINFO）を登録して人間が補完している。なんだかんだで microformats が本当に世界中で整備されるのは、Web 99.0 ぐらいまで待つ必要があるのかなーと思う。ので今はある程度人間が補完する部分も必要なんじゃないかな；)

ちなみにこの辺、otsuneさんが「メタデータとしてxFolkを付けよう」と啓蒙活動をしてて偉いと思う。http://www.otsune.com/diary/2007/11/08/1.html#200711081

Googleと分散クローラ

結局、XFNやFOAFをクロールするだけなら、今回Googleは技術的に大した事やってないとも言える。まあ、それは冗談として；D

Googleは数億オーダーのデータを扱える、その量が凄い。数千台のサーバ群が常時動いててWebをクロールしまくってる、でクロールしたテラバイト級のデータをGFSなんかにガンガンぶちこんで、MapReduceで数千台規模のサーバ群が解析する。想像だけどおおまかにこんな情報工場が24時間365日フル稼働してるんだと思う。十二分に凄い。

これと同じことを個人でやるのは余りにもつらい、、のでオープンな分散Webクローラがあれば面白いのかなと最近思う。常時Webをクロールし続けるサーバ群のP2Pネットワークがあって、URLのドメインとかをキーにして分散ハッシュテーブル的に目的のピアを探索する、とか。XPathで //a[@rel="me"] とクエリーを投げるとマッチするページを返す、とか。

- *.user.jsというファイル名

- @include http://example.com/* という文字列が含まれる

ページを探すクエリーを投げる事ができれば、http://example.com 向けのGreasemonkeyスクリプトのリストを取れる。とか色々できそう。

「ネットに 繋がってないパソコン ただの箱」じゃないけど、Webにある情報だけで十分相当な事ができる。ちょうど今日クリップボードをWebで共有するサービス ControlC というのを見つけて登録してみた。Win/Mac/Linux 用のネイティブアプリをインストールして、Ctrl+C するだけでWebにアップされるというサービスで「これは面白い！」と思ったけど、いざPCの中を探してもこれといってクリップしたい情報がない。しかたないのでWeb上のページをクリップ試してみたんだけど、これならTumblr + Tomblooで十分だった；D

続々と情報にURLが付いてWebに繋がってきている、あとはWebから目的のデータを取り出すクエリーを変えるだけで相当色々な可能性があるのに、現状それを自由にできるのはGoogleだけでまだまだ試し尽くされていないってのはもったいない。

そういえば分散型クローラと言えば「buzztterの裏側で動いているTwitter用クローラが、Twitterのトラフィックが膨大で大変。分散クローラを作りたい」という話も見た事がある

[buzztter]buzztterの裏側とその周辺技術

twitterのデータをキャッシュしてインデックスし続けるサーバ群がいれば、今盛り上がっているキーワードを抽出するクエリー (buzztter) 以外にも、場所／時間で抽出するクエリ、@名前で行われるコミュニケーションの流れを抽出するクエリ、、まだまだ色々な切り出し方を試せると思う。

Googleもきっと内部では、Webクローラが収集した一次データは各サービスで共有して、メインの検索用に加工した二次データ／イメージ検索用の二次データ／Social Graph API用の二次データ・・・とそれぞれ加工してる、んだと思う。極論すれば

- イメージ検索 - //img

- Social Graph API - //a[@rel="me"]

と膨大な一次データからそれぞれ違うクエリーで切り出している、と言えなくもない。かも。

via Dr Nic - Autotesting Javascript in Rails

script.aculo.usのunittest.jsを使ったRailsプラグインの javascript_test なかなか良さそう。generatorでテストのひな形作成、auto_testに対応してくれる。unittest.js単体もBDD的な記述、ベンチマーク、辺りが良い。

#インストール
ruby script/plugin install javascript_test
mkdir test/javascript
ln -s vendor/plugins/javascript_test/assets/ test/javascript/assets

#テスト作成
ruby script/generate javascript_test hoge
> create test/javascript/hoge_test.html
> create public/javascripts/hoge.js

#テスト書いて
# test/javascript/hoge_test.html
testTruth: function() {with(this) {
  assertEqual(X, "hoge");
}}

#実際のjsコード
# public/javascripts/hoge.js
X = "hoge";

#テスト実行
rake test:javascripts

手元のMacだとSafariとFireFoxが自動で立ち上がって、テスト結果が表示される筈

BDD的に書きたくても大丈夫。String, Array, Number辺りの基本クラスを拡張して、shouldEqualみたいなメソッドを追加してくれる。

Test.context("BDD-style testing",{
  "setup": function(){
    console.log("Now setup!!");
    hoge = "Test";
  },
  "teardown": function(){
    console.log("Now teardown!!");
  },
  "should automatically add methods to strings": function(){
    hoge.shouldEqual("Test");
    hoge.shouldNotEqual("HoHoHo");
    hoge.shouldNotBeNull();
    hoge.shouldBeA(String);
    hoge.shouldNotBeA(Number);
  }
});

unittest.jsについて、詳細はこちらのサイトが詳しい。

script.aculo.usのUnitTestの使い方 前編 - Yak blog

script.aculo.us付属のユニットテスト(unittest.js)の使い方 後編 - Yak blog

今年の書き初めはJavaScripでSchemeっぽい物、70行くらいで書き捨て。置く所が無かったのでAppJetに置いた。

http://tk-scheme.appjet.net/

AppJetは第三者の書いたコードを気軽に読み込み&実行できるのが良いな、eval(wget("http://hogehoge"))とか。最悪悪いコードが入って来ても困るのはappjet.netだし；D

"第三者のコードを気軽に実行できる" ってことで何か面白いことができないかな。

例えば、GoogleのMapReduceを独自にオープン／分散／P2Pで実現しようと思うと、まずネックなのが（色々あるけど）実行ロジックをworkerへ送り込む方法だと思う。

GoogleのMapReduceをいまさら妄想した - YappoLogs

実際問題としてオレオレでMapReduce作る時に考える事は、データとコードを各worker serverに送る仕組みを真っ先に考えなければいけない。単純にjobを分散出来た所で、それはMQとかに毛が生えた程度の面白さしかないから

worker群がいて、そこへロジックと処理すべきデータを送り込む。データは良い、でもロジックはセキュリティとパフォーマンスの懸念が常にあって "絶対安全" というのが難しい、と思ってたけど実際こうやってAppJetが動いているのをみると、何とかなるかなと思ってくる。AppJetの場合サーバサイドJavaScriptを多分Rhinoとかで動かしてると思うんだけど、パフォーマンスのチェックとかはどうやってるんだ。

TechCrunch Japanese - AppJet、シンプルなウェブアプリ制作を簡単に

新入社員がグーグルの発想のスケールに慣れるまでに数カ月はかかるという。「ある日、誰かが、数千台のコンピューターを一斉にぶん回すような“ヤバイ”仕事を考えつく。すると“ヤツは分かってきたみたいだな”ということになる」

http://business.nikkeibp.co.jp/article/world/20071221/143754/

こんな面白そうな話、放っとくのは勿体ない。

で、あまり関係ないけどSchemeっぽい物を書き始めたけど、なんか違うな。Scheme on JavaScriptならもっとちゃんとしたのがあるし

BiwaScheme

なんだろ、(map 実行ロジック データリスト) と書いてmapが並列に分散する様な。いっそこんな感じにJavaScriptの配列で良いんじゃないか

[scm.map, function(n){return n*n;}, [10, 20, 30, 40]]

上手くまとまんない、もうちょっと考えてみよう。

ActiveJaxというRailsプラグインを見つけた

ActiveJax - Simpltry Rails

「ActiveRecordのモデルをJavaScriptから叩ける」と書いてあり、RESTなWebAPIを叩くJesterの競合になりそうかな、と思ったら全然違った。

Jester-RESTfullなRails向けJavaScriptライブラリ

Jesterの場合はあくまでもRESTなWebAPIに向かって、それっぽいURLでアクセスする。Railsのscaffold resourceで作られたWebAPIを想定してるけど、細かくカスタムも可能で別にPerlでもPHPでもJava, C# 相手は何でも良い。

ActiveJaxの場合は、ActiveRecordモデルの構造を見て動的にJavaScriptを作成しちゃう。こんな感じ

#Model
def _active_jax_meta()
  @@active_jax_meta.values.each do |ajc|
    if ajc[:finders].empty?
      ajc[:finders] =  ajc[:class].public_methods.select { |m| m.match(/\Afind/)  }.reject { |m| ajc[:class].superclass.respond_to?(m) && !m.match(/\Afind\Z/) && !m.match(/\Afind_all\Z/) }
    end
  end
  @@active_jax_meta
end
#Controller
def js
  response.headers["Content-Type"] = "text/javascript"
  Dir.glob(File.join(RAILS_ROOT, "app", "models") + "/**/*.rb").each { |f| require f }
  Dir.glob(File.join(RAILS_ROOT, "app", "controllers") + "/**/*.rb").each { |f| require f }
end
#View  
<% ActiveRecord::Base._active_jax_meta.keys.each do |klass| -%>
  ActiveJax.<%= klass.name.to_s -%> = {};
  <% klass.active_jax_finders.each do |finder| -%>
    ActiveJax.<%= klass.name.to_s -%>.<%= finder -%> = ActiveJax.query_function("/active_jax/service", {klass: "<%= klass.name.to_s -%>", finder:"<%= finder -%>"});
  <% end -%>
<% end -%>

「俺はRailsさえあれば良い！ペロカパ！」って人はこれでも良いんだろうけど、なんだこれ。ある意味凄い、ビックリ。Jesterと比べるとこんな感じ

　・Jester = RESTfullなWebAPIを作ってくれれば、空気を読んでそれっぽいURIにアクセスするよ。カスタムも可能。サーバのことは知らない

　・ActiveJax = ActiveRecordのクラス名やメソッドを解析して、それっぽいJavaScriptのオブジェクトを出力するよ。ControllerやViewは自動生成するから気にしないで；)

みたいな。JesterみたいにWebAPIでサーバ & クライアントが分かれていると

　・クライアント= Jester以外のライブラリから叩く、API公開して色々叩いてもらう

　・サーバ = 重い機能をRails以外で書き直す

と粗結合になって色々おいしい事がある。例えばの話で、はてブWebAPI用に作ったJavaScriptのUIでdel.icio.usを叩けたりする、Tumblr用のツールでsoup.ioが叩けたりする。（WebAPIが似ていれば）

まあ明らかに書き捨てのWebアプリケーションとかなら、ActiveJax的な密結合も楽で良いけど。ちゃんとするなら、ちょっと面倒でも粗結合が良い、まあ当然の話で。

追記：早速破られた！

 
safeCall("var w=(function(){return this;}).call();w.alert(w.document.cookie);");
id:kazuhooku - http://b.hatena.ne.jp/kazuhooku/20071206#bookmark-6709542

サイ本よく見ると確かに「オブジェクトのメソッドとして呼び出された関数内でも、入れ子にされた関数内のthisはグローバルオブジェクトを参照します」て書いてあった。あとMDCにも http://developer.mozilla.org/ja/docs/Core_JavaScript_1.5_Reference:Operators:Special_Operators:this_Operator

=========

面白い記事があった、GreasemonkeyのunsafeWindowを安全にすることは可能か

[JavaScript] GM_xmlhttpRequestを使えなくする - 実用
GM評価のsandbox - ゼロメムはてな支店

この記事はGreasemonkeyのunsafeWindowについて（GM実行中サイトが悪意を持っていた場合 or XSSの穴が合った場合対策）だけど 自分もちょうど、JavaScriptを安全に実行する方法が無いか考えていたので、ここに書いてみる。まず目的は

・自サイト上でユーザにJavaScriptを（限定的に）許可したい

例えば、はてなダイアリー等でユーザがブログパーツを張れるよう許可するとか。但し
・document.cookie等、危険な機能は操作不能にする
・あくまでサイト上でJSを許可する（iframeは不可）

で、幾つか考えられるのが以下。

・iframe内で実行
iframeを生成して、そのwindowの中で実行させる。これなら確実に安全なサンドボックスが用意できそうだなと思うけど、今回はスルー

・Facebookアプローチ（変数・関数名にプレフィックスを付けて無害化）
Facebookがユーザに許可するJSでは、変数・関数名にプレフィックスを付けて無害化するらしい
[Facebook] FBJSでFacebookアプリ内でJavaScriptを利用 - Kawa.netブログ（川崎有亮）
面白いな、とも思うけど無害化するロジックに穴があるとセキュリティホールになりそうな気がする。

で、色々調べていて一つ思ったんだけど、こんなのどうだろう

function safeCall(users_code){
  var sandbox = {
    window: null,
    document: null,
    alert: null
  };
  with(sandbox){
    console.log(eval(users_code));
  }
}

これならsandboxオブジェクト内に列挙したwindow, document, alert,,,等は、無効化してevalできる筈

確かに列挙したオブジェクトはnullになる、逆に許可したいオブジェクトは含めなければ良い筈。Sandbox.myDocument.myGetElementByIdみたいに許可するネームスペース／クラスを決めてそれを叩いて貰えば制御可能になるかな。と思ったけど、deleteでプロパティ削除されると意味ない

じゃあvarで宣言すればどうだろ？

function sandbox(){
  var window = null;
  var document = null;
  var alert = null;
  this.do = function(code){
    with(this){
      console.log(eval(code));
    }
  }
}

原則varで宣言した変数はdelete不可能な筈、これで一応大丈夫？

どうだろ、やっぱり抜け穴がある気がしてならない。。 あと、実際にはwindowのプロパティを列挙する必要がある。

で実際に運用する時は、無害なタグとして記述して貰ってsandbox経由に実行すれば良いかな。今流行の俺俺スクリプト風に

<script type="text/my-safe-javascript">
  alert("Hello world from sandbox!!");
</script>

とか書いて貰って、ページ起動時に //script[@type="text/my-safe-javascript"] な要素を探してsandbox経由で実行みたいな。//script[@type="text/javascript"] はサーバ側のフィルタで潰す

うーん、どうだろ？やっぱ何か抜けがあるかな、ある気がする。きっとあるな。