Rui

Gaucheでこつこつプログラムを書いていました……が、最近はあまり書いていません（このごろは家でそんなにプログラムを書かなくなってしまいました）。メールはrui314@gmail.com。Twitter。

高水準スレッドライブラリ

Rui:ThreadLibrary

Gaucheのソースコードを読む

Gaucheのソースコードは次のような順番が読みやすいんじゃないかと思うのですがどうでしょうか。

1. Schemeオブジェクトのメモリ上での表現を理解する ―― 次のことを頭に入れとくべき： 小さな整数、文字は1ワード(ポインタのサイズと同じ)に直接入れられている。一般のオブジェクトは、先頭の1ワードがクラスへのポインタになっている。
2. stringやportといったコアライブラリを読む ―― 独立性が高く、C言語で書かれた文字列ライブラリやIOライブラリとして読むことができる。
3. スタックの構造を意識しつつVMを読む ―― VM本体は単なる大きいswitch文。スタック上のデータ構造がわかれば理解できるはず。
4. 理論をおさえつつコンパイラを読む ―― なにを意図しているのかがわかれば読めると思うが……。

• Shiro(2007/09/18 18:56:03 PDT): そうっすね。順番はそれが妥当だと思います。 あと、本来あるべき姿と現実への対応のための飾りとが混ざってるんで、 その両者をわけて考えられないと難しいと思います。そのためには他の処理系も 並行して読んでみるといいんじゃないでしょうか。共通する部分は一般的な 原理ってことですし、そうでない部分はGauche独自の設計上の選択があるってことで。

Gaucheクックブック

http://d.hatena.ne.jp/rui314/

Perl Cookbookに倣って、Gaucheクックブックというレシピ集を始めることにしました。

Gaucheスクリプトの実行ファイル化

→ Gauche:gauche-statifier

パーザコンビネータ

→ Rui:ParsingExpressionGrammar

正規表現の最適化

実装プランの概要に沿って、Gaucheの正規表現の最適化を実装していく予定。Shiroさんに正規表現のベンチマークスイートをいただいた。失敗をメモ化するという自分ではユニークだと思っている手法を思いついたので、実装してその実地での効果を見たい。

ヒアドキュメント

→Rui:ヒアドキュメント

正規表現の拡張

→Rui:正規表現の拡張

Conservative GC

3ヶ月ほど動いているデーモンがあって、プロセスイメージが80MBくらいになっている。起動したときは50MB程度だった。このデーモンはそれなりに仕事をしており、毎秒数パケットのUDPメッセージを送受信し、バックエンドのRDBMSにデータを書き込み/読み出している。GaucheはBoehm GCなので、メモリリークが本質的には避けられず、こういう用途ではなんとなく時々再起動しなければいけないんじゃないかと思っていたけど、実際にその必要は生じていない。consavertive GCに対する信頼感がアップした。

ライブラリ

• Gauche:Zlib: Zlib圧縮ライブラリのバインディング。

• Gauche:ObjectPrevalence: サーバがデータを保持するために書いた ライブラリです。はじめはDBIを使ってRDBMSにデータを保存していたのですが、 サーバの本来の処理とデータの書き込み・読み出しの処理が混在して、 見通しが悪くなったのがいやだったので、透過的にデータ保存を するライブラリを書きました。Object prevalenceというのはメジャーでは ないテクニックのようですが、結構実用的だと思っています。

• Gauche:RedBlackTree: red-black treeの実装。ハッシュテーブルでは 不十分だった（キーの小さい順に要素にアクセスしたかった）ので書いたものです。 red-black treeを書くまでは、代わりにキーの昇順に要素が並べられた連想リストを 使っていたのですが、それだと挿入や探索のコストがO(n)であり、プロファイラでみると そこに実行時間のかなりを費やしていました。red-black treeにして パフォーマンスが改善されました。

• event: 試行錯誤中。Perlのeventパッケージやlibeventに影響を受けて、 イベントを統一的に扱う手続きを書いています。ここでイベントとは、 fdが読み書き可能になったということ以外に、アプリケーションが設定した タイマが切れたことや、シグナルの受信も含みます。（内部的には、 最も短いタイマが指定する時間をtimeoutに指定してselectを呼びます。 red-black treeはこのタイマのリストの保持に使うために書いたのでした。）

• シグナルハンドラでちょっとハマりました。シグナルハンドラから統計情報を 標準出力に書き出すという変更を一時的に加えて、Ctrl-Cで統計情報を出力させて いたら、たまにプログラムがエラーを出力して終了してしまうのです。一瞬処理系の バグかと思いましたが、実際は、call-with-output-portを使っているためでした。 call-with-input-portで現在の出力ポートが切り替えられており、その動的な環境 の中でシグナルハンドラが呼ばれた場合、統計情報が端末ではなくその環境の標準 出力に送られてしまいます。それにより異常なデータが生成され、エラーになって いました。
• 現状は、とりあえず、シグナルハンドラが生成される環境でのエラーポートを ローカルに束縛しておいて、そちらに出力するようにしています。本当はScheme コードのメインループの安全なポイントからハンドラ本体を呼ぶようにしたほうが いいんでしょうね。

• trie: Trie (トライ)を構築したりアクセスしたりするライブラリ、欲しいですね。 いまは適当にアクセッサだけ書いて、trieはS式手書きしています。文字列以外の シーケンスに対してもちゃんと動き、かつノードの数は可能な限り少なく持つような ものがあるといいのですが。Trieについては高林さんの説明が詳しいです。Wikipediaも なかなか。

• Trieの用途の例: 電話番号が正しいか否か、また、正しいならどの地域なのかを 知りたいとします。ここで番号が正しいとは、空きブロックに含まれていない番号で、 かつ桁数が正しいこととします。つまり入力は電話番号(03-2345-6789など)と 番号計画表(電話番号のリスト)であり、出力は、電話番号が番号計画表にマッチ するかを意味する真偽値とします。番号計画表にマッチする場合は、エリア名称を 一緒に返し、マッチしない場合は、番号の桁数が不足しているのか多すぎるのかを 一緒に返すことにします。
• Wikipediaの説明の図を見てもらえればピンとくるかと思いますが、上記の目的 を達するには、与えられた電話番号の先頭から順にtrieを下っていって、(1)電話番号 を読みつくしたのにTrieの葉まで達していない場合は桁数不足、(2)葉に達した場合は 桁数一致、(3)葉に達したが番号がまだ残っている場合は桁数が多すぎ、という判断を 下せばよいわけです。これに必要な時間は、与えられた番号の桁数nに対してO(n)で 済みます。エリア名称は葉においておけばよいでしょう。
• ところでtrieの構造ですが、空間の効率がよくないと困るのですね。電話番号10桁 に対して10^10個のノードを作って全パターンをカバーすることも不可能ではないとは いえ、それは効率が悪すぎます。共通のプレフィックスは1つのノードにしたりしない といけません。
• ここらへんを書くのが面倒なのでいまはtrieを手で書き下しているのでした。 データを直接書き下せるのって、やっぱりSchemeの利点ですね。
  • leque: ここを読んで簡単なものを書いてみました。 http://www.katch.ne.jp/~leque/software/gauche/trie.scm 各ノードは子を表すハッシュ表と値のペアで表現してます。 現在は単純にキーのあるなしだけしか判定できませんが、ノードに値を 持たせたり、キーの足不足をかえすようにもできると思います。

• binary tree: Red-black treeを書いといてなんですが、目的とする用途には binary treeで十分と思えてきました。

cc-arity.patch

継続のarityをちゃんと取得できるようにするパッチでしたが、現在のVMに対しては 当たらないので削除します。基本的なアイデアはScheme:継続のarityで 説明している通りです。継続のarityというのはいいアイデアだと思いましたが、 実際は難ありでした。