2008/10/01
らむ太語録
- つまに、ばっしゃーん (津波、ばっしゃーん)
- いーっぱいたべる。おーちくなる。ちかわもちになる。よぼっとになる。 (いっぱい食べる、大きくなる。力持ちになる。ロボットになる)
らむ太はロボットになりたいようだ。
Tag: 生活
2008/09/13
多バイト文字とDFA
flex の森 - ひげぽん OSとか作っちゃうかMona-
誰か多バイト文字に対するDFA構築手法をわかりやすく解説してくだちい。
文字クラス中の文字は大抵近接した領域に固まってるので、 全部utf-8にしてオクテット列をacceptするDFAにできなくはなさそうな (文字クラスでの分岐が一段じゃなくツリーになるけど、近い領域に固まっていると ツリーの根元が多く共有される&リーフは何でも良い場合が出てくる、ので 圧縮できるんではないかなあと)。 ただ、DFAでそれをやってるのは見たことないから思ったより圧縮できないのかも。 Spencerの新しい方のDFA(Tclに使われてるやつ)も確かいちいちucs-4に展開して、 さらにDFAをon-demandで作ることでサイズを抑えていたと思う。
GaucheのregexpエンジンはNFAだけど基本的にオクテット列に対して動作する ように展開される。ただ、文字クラスについてはオクテット列のツリーに するのが面倒だったので、一度文字を構築してレンジチェックをかけている。 オクテット列のままやったらどのくらい差が出るか測ってみたいんだけど 当分そんな暇は無さそう。
Tags: Programming, Gauche
2008/09/04
v8とかスクリプトとか
lucille development blog - V8 benchmarked
py2llvm の経験から、スクリプト言語はネイティブの 100 ~ 1000 倍遅く、JIT したとしても数十 ~ 100 倍くらい遅いもんだと思ってました.
[...]
もはやあと数年もしたら、動的言語やスクリプト言語が、ネイティブ版とほぼ変わらないくらいの速度で実行できるほどに JIT 技術が進化しそうだ.
「スクリプト言語」の定義が曖昧なので厳密な議論にはならないのだ けれど、大島さんも書いているように 動的言語であるCommon Lispはon-the-flyでコンパイルして Cにほぼ匹敵する速度(*)も可能だったわけで、何が足を引っ張っていたかというと 単に実装者がさぼっていただけだと思うなあ。
もちろんここでの「さぼる」は悪い意味じゃなくて、工学はトレードオフなので、 そこに手間をかけるよりも優先度が高いところがあったってことだ。 特にネイティブコードでがりがり最適化をかけるような話は開発リソースを 喰うので、開発リソースがscarceな状況で手を出すのは得策ではない。 従って、Googleみたいにリソースをつぎ込めるところが手を出してくれるのは 有難いことである。
C++が速い、というが、その速さの源は言語そのもののの性質だけではなく、 コンパイラベンダが巨大な開発リソースをつぎ込み、プロセッサ メーカもそれに合わせたアーキテクチャを作ってるってところが大きいと思う。 一般の開発者は、その成果に乗っかる形でコードを書いているわけだ。 ある意味、分業による効率化とも言える。
Clojureを作ったRich Hickeyは、 「VM、GC、JIT、OSインタフェースなどはリソースのあるところにまかせて、 言語開発者はもっと上の方の言語デザインに力を割くべき」みたいな ことを言っていた (ClojureはJVM上で走る)。
その見方をとれば、Googleがリソースをつぎ込んで爆速JavaScript実装を 広めてくれれば、「JavaScriptへとコンパイルして後はJavaScript処理系に 任せる」という方針はぐっと現実味を帯びてくる。 BiwaSchemeとか、 時代を先取りしてたかもね。
いずれにせよ、速い実装がポピュラーになれば既存の実装への プレッシャーになることは間違いなく、 Gaucheでもますます 色々試してみたい時代になってきた。
(* Cコンパイラもナイーブだった頃。global analisysをやるような最適化 コンパイラに対しては、ローカルな情報しか使えないインクリメンタルコンパイルは 負けるだろう。ただ、開発中のインクリメンタルなモードではコンパイル速度を重視し、 アプリが完成したらバッチでコンパイルするといった複数のモードをつけられない 理由はない)
そうそう、 http://d.hatena.ne.jp/squeaker/20080904 :
高速化のためには数値型や文字列に関する仮定は置かなくてはならないので、 例外なしに完全にできるわけではないですが、四則演算みたいなものの 定義は書き換えたら遅くなっちゃうけど、それら以外は別にIntegerやStringであっても 少々変えても大丈夫、というようなものにはできると思います。
Lispのネイティブ実装は、例えば加算ならデフォルトのfixnum additionのコードを 吐いておいて、オペランドがfixnumでなかった場合はtype error例外が飛ぶので それを捕まえてより複雑な加算処理を行う、みたいなのがよく使われてたと思う。 この方式だと加算の意味を後から追加していっても、多くのケースで性能は犠牲にならない。 ただこれはハードウェア命令がタグチェック→例外をサポートしてくれてる ことが大きいんで、現代のプロセッサでタグチェックを一般命令で挿入すると どのくらいアドバンテージが出るかはわからない。
Tags: Programming, Lisp
2008/09/02
100年後の言語
LL Futureにはかなり前から出演を 頼まれていたのだけれど、7月のキプロス行きの後で腰を痛めて、 今回もLA行きの直後に飛行機旅行が続くと腰が持つかどうか心配になり、 えんどうさん他スタッフに申し訳ないけれど辞退させてもらった。 (開催が近くなってからのキャンセルでご迷惑おかけしました)。 実際、体力的にきつかっただろうなと思う。
さて、blogをあちこち見ていたんだけれど、 「100年後の言語」セッションに関してとてもおもしろい問題提起が あったのでちょっと考えてみた。
それこそコンピュータアーキテクチャがノイマン型(プログラム内蔵方式のコンピュータ)で あるならば、どっかのレベルではメモリという概念が必要になってきて、 関数型のOSやらshellを用意したところで、どうしてもC的なレイヤがでてくる。
ここで言う「C的」とはハードウェアの状態変化によく対応しているという意味だと思う。 実際、C言語は長らくポータブルアセンブリとして活躍してきたわけだが、 ぼちぼちその抽象化がハードウェアに合わなくなっているんではないかという気がしている。
ハードを気にしてコードを書くなら、今や階層化されたメモリや メモリアクセスのリオーダリングなどを考えざるを得ないが、C言語そのものには そういった機構を明示的に扱う仕様は組み込まれていない。 その一方で、aliasing ruleを破っているコードは何の警告もなく直感に 反するような動作をする (e.g. strict aliasing rule)。
要するにCで書いてハードに直接触っているというのは全くの幻想で、 Cで書いててもプログラマはやっぱり抽象化されたモデルを扱っているにすぎず、 しかもそのモデルにはあちこち漏れがあるというわけだ。 (むしろ、怪しい動きがあれば開発中のREPLで直ちにdisassembleして ネイティブコードを確認するLispプログラマの方が、 ハードに近いかもしれない←単にコンパイラを信用してないだけとも。)
メモリとプロセッサのやりとりがどんどん非同期になっていって、 マルチコアやヘテロなコアになって、ひとつのファイル内で ある部分と別の部分は違うアーキテクチャのコアで実行されているなんて ことになってくれば、見た目はCでもハードからの距離はさらに遠いものに なってゆくだろう。
で、別にCが悪いとかそういう話ではない。 ただ、「C言語的」なモデルが「ハードに近いレイヤ」であったのは歴史の一時点の ことであって、C言語をこれからもそのように扱うのは多分間違いだ。 たとえノイマン型は変わらないとしても、スレッドやメモリバリア、 キャッシュ、ヘテロなコアなどを最初から考慮に入れて新たに 「ハードに近い、高級アセンブラ」を考えるとすれば、 違ったモデルが出てくるだろう。 そして、それが例えば疎結合なメッセージパッシングに基づいたものになったとしても 私は驚かない。その時C言語は、メッセージパッシングなプリミティブが エミュレートする「古き良き時代のCPUとメモリのモデル」上で走る高級言語になるかもしれない。
文法の独自拡張は、そのコミュニティを分断することになるのではないかと思ったりする。 つまりXXの機能を利用するためにYYという文法定義が必要で、 それが従来のZZとコンフリクトするので素直には利用できない。 ライブラリやパッケージでも同様な問題はおきなくはないが、 文法は通常一緒なので最悪コピペ的に回避することは不可能ではないが、 文法をいじってしまうと、それも簡単ではない。
これはLispのマクロに対して良く言われることと同根なのだけれど、 このような懸念はモジュラリティの問題であって文法の話とは全く関係がない。
ライブラリであってもグローバルな影響をもたらすライブラリ同士は 回避不可能なコンフリクトを起こす。 (動的言語でありそうなtrivialな例としては、演算子'+'の意味をグローバルに 変えてしまうようなライブラリを複数使いたい場合とか。 もっとnon-trivialな例として、ライブラリAとライブラリBが異なるGCを採用している場合とか。)
結局、文法だろうがライブラリだろうが、 モジュール機構などで「スコープを限定できること」が コンフリクト回避の鍵であって、スコープを限定できないようなものがあれば それは本質的にコンフリクト回避不可なのだ。
(ただし、ライブラリがリンクもしくは実行時に影響してくるのに対し、 文法の拡張はコンパイル時に影響を与えるので、依存関係の処理が若干面倒に なるのは確かだ。これはどっちかというと処理系作成者が悩むところだが)
Programming language design and security
I think programming language designers are not exempted from the responsibility of (at least trying to) making computer systems secure. If I could hear more constructive ways of solving the security problems in the answer from one of the panelists, such as:
- protecting the language from the buffer-overflow bugs;
- preventing the garbage collector from crashing even in a hostile environment where the external attackers try to deliberately manipulate the pointers or variables to hack into the protected memory area;
- implementing a syntax or semantics validation system in the programming language so that the programmers can apply it to validate the external data, such as those from the network-connected users; or
- preventing the race condition, deadlocks, or any sort of resource starvation by the intentional or unintentional programming;
then I would have been much more convinced. But now I should suspect that quite a few programming language designers just don't care about the security consequences of the features they build into the language.
こちらは、これからの言語はセキュリティを考えに入れないといかんでしょうという 問題提起。
で、私が考えるのは、セキュリティの問題というのは仕様と実装の齟齬の問題の 一形態であるということ (セキュリティポリシー(=仕様)を決めない限り、 何がセキュリティフローかは決まらない)。なので、究極の回答というのは 仕様からそれを満たすプログラムを合成するって話かなあと思う。 たぶんあろはさんが詳しそう。 (仕様をどう記述するのが良いかって問題は別に残るけど)。 ただそれが実用規模で実現するのはもうしばらくかかりそうだ。
なので、ポイントになってくるのは静的動的さまざまなプログラム検証って ことになると思う。
プログラム検証は検証で色々やられているが (例えば、上に引用した部分でrace conditionについて触れられてるけど、 Tachio Terauchi, Checking race freedom via linear programmingは実用規模のCプログラムに対して 静的解析でメモリアクセスに対する競合が起き得るかどうかを検証している)、 言語作成者としては「実用性を保ちつつ、かつ検証しやすい言語仕様とは何か」 を考えてゆくことになる。
鍵となりそうなアイディアはいくつか。
上でも挙げたけど、モジュラリティ。ある操作の影響範囲が明確に限定できて、それが 必要以上に大きくないこと。検証は範囲を限定すればするほどやりやすい。
なおモジュラリティという意味では、スレッド+グローバルなmutationというモデルは 最悪で、そこだけ見てればちゃんと動くはずのプログラムが、全然関係なさそうな ところの変更に影響を受ける可能性がある。なので言語としては別のモデルを 提供するのが吉。
関数型のモデルは状態の管理がローカルになるという点で強力な武器になる。 けれど、それとは別に複数の制御の流れを綺麗に扱えるモデルが必要だろう。 π計算みたいなものをうまく取り入れられるのか、それともlindaみたいに 同期機構をマクロに見るのがいいのか、そのへんはよく知らない。
ただし、これらの理論を純粋に採り入れて 制限をきつきつにしてしまうと今度は実用プログラムが書きづらくなる。 で、実用のために制限に穴をあけたくなるわけだが、無制限に穴をあけると そこで「何でもあり」になってしまう。 なので、下の層として「ハードに近いけれど頑健な」モデルがあるといい (それは間違ってもC言語じゃない)。上で挙げたようなメッセージパッシング かもしれないし、型付きアセンブラみたいなものが使えるかもしれないし、 そのへんは住井さんが詳しいと思うけれど、 under the hoodに降りてビットを直接いじってるんだけどそれが検証可能である、 というふうになって行くんじゃないだろうか。
もひとつ、これも上に挙げた文法のカスタマイズにつながるんだけれど、 問題のドメインがはっきりしている場合、それ用のDSLで書いてある方が 検証しやすい。たとえばAlan KayのとこでIan Piumartaらが やってるプロジェクトでは、RFCに書かれてるTCPの仕様をDSLとして解釈して コンパイルすると実際に動作するTCPプロトコルスタックになる、というのを 書いたそうだが(大島さん、間違ってたらツッコミお願い)、 ここまでやって問題が出たらそれは仕様のバグってことになるわけだ。 ここまでやらずとも、DSLを使うというのは、問題領域で使われる概念に良く対応する 言葉を組み合わせてプログラムするということだら、プログラマの意図がより明確であり、 その意図に照らした検証がしやすいと言えるだろう。
あともひとつ。これもIanの受け売りに近いんだけど、こうやってメタプログラミングを 極めて行くと複雑なシステムがえらくコンパクトに書けるようになる可能性がある。 実際、彼らはOS・言語処理系からアプリに至るまでの全てを20000行で書くという プロジェクトをやっていて、ネイティブコンパイラが1000行ちょい、とかは 既に実現されてる。 で、1000万行のシステムと2万行のシステムなら後者の方が検証ははるかに 楽だろう。1000万行のシステムの99.8%が機械的に除去可能な冗長性でない限り。 (そうそう、Ianのやつは上の「C的なレイヤ」の話の反例にもなってると思う。)
私としては未来はそっちの方向かなあという気がしてて、Gaucheのシステムも だんだんメタに記述していって記述量を減らして行きたいと思っている。
Tags: Programming, Gauche
2008/08/27
『ミスト』のラスト
こちらと こちらで 批判されてる映画評論家がいて、 好奇心でその人の映画評 をいくつか読んでみた。私もまるきり勘違いすることがよくあるので人の批判はできない んだが、『ミスト』評 (リンク先ネタバレ注意)でラストを「救済」としているのが気になった。 というのは、『蝿の王』を知らないとあのラストは救済に見えるかも、と思うからだ。 (あと、あのラストを「衝撃狙いの悪趣味な演出」みたいに言っている評も見たけど、 それもバックグラウンドを知らないせいだと思う)。 もちろん観客それぞれの背景によって解釈は色々あっていいんだけれど、 あれを救済で済ませてしまうのはあまりに勿体ないと思うので書いておこう。 できるだけ見た人にしかわからないように書くつもりだけど、 どうしたってラストに触れるので『ミスト』未見の人は注意。
『蝿の王』はもう古典なのでストーリー出しちゃっていいかな。 出しちゃうよ。ネタバレ嫌な人はここでストップ。 少年達を載せた飛行機が無人島に不時着し、大人がいない状況で 少年達のコミュニティが理性と秩序から次第に本能と混沌へと変貌してゆく様子を描く。 で、まあ最後には大人がやってきて少年達は助かる。
助かるのだけれど、助けにやって来たのは軍隊だ。 『蝿の王』小説中でわずかに触れられるが、外の世界では戦争をしている。 このラストの意味についてはGolding自身の言葉が的確だろう。 Stephen Kingは『Hearts in Atlantis』の中で『蝿の王』を出したときに この言葉を紹介している。
The boys are rescued by the crew of a battle-cruiser, and that is very well for them, but who will rescue the crew?
『蝿の王』の見事さは、「特殊な環境下での集団の変貌」を圧倒的な説得力を もって描いたのちに、「ローカルに見れば救出」「けれどグローバルに見れば、 救出者達もまた、同じ状態の集団の中にいる (そして読者もそうかもしれない)」 という一種のどんでん返しを、ひとつの瞬間でやってみせるところだ。
で、『ミスト』である。
父親の叫びに応えて霧の向こうから現れたのがアレだったことの意味は何か。
子供が怖れた "Monster" とは何だったのか。
果たして人々は救済されたのか。
果たして我々は救済されるのか。
