syntax-rules

マクロ周りは非常に奥が深くて僕では溺れてしまうという話。
昨日の記事を書いた後(しばらくは冪剰余やってたけど)気づいた。そういえば、Sagittariusではsyntax-rulesを使ってdummyみたいなことは出来ないと。
ということで、テスト。

;;(import (rnrs))
;;(import (scheme))
(define-syntax test
  (syntax-rules ()
    ((_ var val)
     (begin
       (define dummy val)
       (define (var) dummy)))))

(test a 'a)
(test b 'b)
(display (a)) (newline)
(display (b)) (newline)

最初のコメントは処理系に応じて入れたり消したり。試した処理系。

• R5RS Gauche、Racket(plt-r5rs)
• R6RS Ypsilon、Mosh、Petite Chez Scheme、Sagittarius(R6RS?)
• R7RS Chibi-Scheme(一応そう謳ってるし)

とりあえず、ほしい結果は多分以下。

#| R6RS的にはこうだよね？
a
b
|#
#| 字面的にはこうでもよさげ？(2)
b
b
|#

dummyというシンボルを使いまわしているように見えるので、(2)でもいいような気がしないでもない。(R6RSまじめに読んでない、R5RSは目を通したことすらない気がする・・・)
結論を言えば、Racket、Ypsilon、Mosh、Petite Chez Schemeは最初の結果、残り(Gauche、Chibi及びSagittarius)は2番目になった。

分かっていたんだけどね、こうなるって(Sagittariusの話)。そして、これは現状のつくりを維持するなら正直直しようがない。原因は2番目の結果になった処理系は、dummyを参照することができるということ。Sagittariusは確定なんだけど、恐らく残りの2つもマクロ展開時にシンタックスの情報を持っていない。なので、dummyとdefineの区別がつけられず、シンボルのrename(もしくはunintern)を行えない。

単純な話、上記の例で言えば、2つのdummyは同じrenameされたシンボルに変換できる。そうすると、トップレベルではdummyというシンボルは何かしらにrenameされているので見えないが、varが束縛(捕捉？)したdummyは同一のものにrenameされているのでそこからは見える。

これ多分、明示的にマクロ展開のフェーズを持たないと無理じゃないかな？もしくは、マクロ展開器がもっといろいろ知っている必要がある。あぁ、でもそれくらいならいけるかな？

結局、テンプレートをre-writeする際に、それがグローバルに束縛されているならそのままで、そうじゃないものならrenameとかすればいいかも。(でも、やるなら0.3.7以降だな。0.3.6はリリースが近いから無理だ)

これって、R5RSとR6RSで明確に定義されている非互換な動作なのだろうか？

マクロ、マクロ、マクロ

Sagittariusを試してもらえているというのは非常にありがたいし、嬉しいことである。それがたとえ動かない動作であっても(T_T)

動かない動作は以下のサイトより

衝突回避と暗黙のimport - 主題のない日記 

id:SaitoAtsushさん(こう書くのがHatena流だっけ？)は僕が絶対書かないタイプのマクロをガンガン書かれて、しかもそのテストにSagittariusも使ってくださっていてなんともありがたい。

ただ、まともに動いたことがない感じがするのがとても心苦しかったりもするだけれど・・・(R6RS名乗るの無理になってきたか・・・？)

さて、今回の不具合はパッと見、恐らく現状のマクロ展開の仕組みを使っていると直すのがかなり厳しい気がする。問題なのは、define-settable内で定義される識別子(ここではset-dummy!)は自身の定義されているライブラリの参照としてオリジナルのライブラリ(settable-variable)を持つ(はず)。そうすると、(test-lib)内で定義されているにも関わらず、参照を解決する際にオリジナルを見に行く。っで、unbound variableが投げられて悲しい思いをする。というのがパッと見た感じのエラーの原因と思う。
(あれ？でもこんな感じのマクロはdefine-record-typeとかでも普通に使われているはずだから、そんなはずないよなぁ？)

見た感じ、このマクロは結構コーナーエッジっぽいみたいで、意図どおりに動く処理系はRacketとYpsilonのみっぽい。実際手元のnmoshで試したらエラー投げた。
ちょっとpriority低めでIssue上げとくか・・・

冪剰余

まだ実装中なんだけど、必要な部分は出来て動いたのでちょっとベンチマークを取ってみた。

(import (rnrs) (crypto) (math) (time))
(time (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4)))

自宅のX60で2048bitの鍵を作るのは自殺行為なので1024bitで。っで、以下が結果。

$ sash test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  4.265625 real    4.188000 user    0.078000 sys

$ ./build/sash.exe -Llib -Lsitelib -Lext/crypto test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  0.953125 real    0.890000 user    0.046000 sys

下が開発版。4倍程度高速になっているのが分かる。これくらい高速なら実用に耐えるだろうか？まだJavaと比較すると2倍から3倍遅いが・・・(比較する対象が間違っているのかもしれないと思い始めてもいる。)

Javaの実装に習って、Miller Rabinテストの試行回数を1024bit以上の時は2回にしてメルセンヌ数をチェックする処理を試したんだけど、結果が返ってこなかった。多分ヤコビシンボルを探すのが遅いのだろう。さすがにそこまでC側で実装するべきか悩むところだ。(Lucus Lehmer法自体がBignumを直接操作しないと遅いのかもしれない。まぁ、後の課題にする。)

mod-exptの動作としては、まだ対称の数(x ^ e mod mのx)が偶数の場合の処理が未テストかつ多分動きがおかしいはず。テストを書きつつ動作を検証していかないと。

Open Monumentendag@Haarlem

I actually didn't know what open monumentendag was. But I went there.

This was meetup stuff and originally it was Utrecht however organiser had just heard that most of the monuments were closed on Saturday so he changed it to Haarlem. Well, I've never been to Haarlem before (even though I've been living here for 3 and half years already!) so there was no reason not to go;)

 Central square? I don't know the place name. The sun glasses guy was the organiser.

 Inside of the city hall (if I following the explanation correctly...)

 They have a huge draw.

 Inside of the church which was on the first photo. Male choir was there. They were pretty good.

Should be a pipe organ. But I also saw a much smaller one, so this might not be the one.

Yes, as you already know I'm not a good photographer, so the photos are that's it.

Then we went through the city and into some museums. It was quit interesting to me. The city itself was totally different from other cities such as Leiden, Amsterdam or the Hague. (I don't know much about Rotterdam even though I work there:P)

冪剰余実装中

単にメモリ割り当てを減らしただけでは鍵対生成に対して実用的なパフォーマンスが得られないことが分かったので(2048bitで5秒からかかる)、どこが遅いかを調査した。結果、素数テストを行っている手続きで使用されている冪剰余の計算が遅いことが判明。x^e mod mを計算する際のx, e, m全ての数が2048bitあった際に20秒かかるという脅威の遅さだった。(3GHz Core i7)

Javaは2048bitの鍵対生成でも同マシンで1秒以下の時間で作ってくる。篩とかあるけど、何より素数チェック、その中で使われている冪剰余が高速なのだと仮定して実装をチェック。素数チェックはTwitterでも呟いたけど、Miller Rabinテストが1024bitを超えると試行回数が2回で、その代わりメルセンヌ数のチェックが入っていた。冪剰余についてはColin PlumbのBignumライブラリを元にした高速な実装になっている。

現状Sagittariusでは冪剰余を求める際に単純なバイナリ法を使っている。普通に

(mod (expt x e) m)

とするよりは遥かに高速なのだが、数値がBignumになってくると計算の度にメモリ割り当てが入りあまり嬉しくない。(eは1bitずつ右シフトされるので、2048bitあると、32bit環境では単純計算で2000回以上の割り当てがexponent部分だけで発生する)。
上記の実装(とりあえずはJavaの)ではメモリ割り当てがかなり削られている。正確には数えていないが、最大でも20回行かない程度に抑えられそうである。

ならばやらないわけには行くまいと、とりあえずJavaから実装を移植したら嵌った。

問題になったのはJavaのBigIntegerは内部で持っているintの配列のオーダーがSagittariusとは逆順になっているのだ。理由は知らないんだけど、きっとその方が効率がいい場面が多いのだろう。もしくはPrimitiveな配列でさえサイズを取ることができるからなのかもしれない。なので、単純にJavaから実装を持ってくるのは失敗に終わった。

恐らく中で何をやっているのか理解してやれば逆順に対応するのも難しくはないのだろうが、高速なモントゴメリ法の実装自体に興味があるわけではないので、可能な限りその労力は避けたい(ものぐさ)。ということでオリジナルの実装を当たってみることにした。←いまここ

マクロ展開時のライブラリ

以下のツイートを発見。

文字列補間マクロ書いたけど Sagittarius で動かない。
— (32) 齊藤敦志さん (@SaitoAtsushi) 9月 5, 2012

動かないのは許せない(というか、バグだし)ので、原因を探る。元コードはきっとこれだろう。

文字列補間 - 主題のない日記 

とりあえず、走らせる。&assertionか。なんとなく既に嫌な予感がしている。 いろいろ省略して原因箇所：

(datum->syntax #'string-interpolate 'x->string)

これ。全体というよりも、#'string-interpolateの部分のみ。

何故か？これ多分マクロ展開器の根幹の問題で、(syntax foo)という構文は定義されたライブラリ内ではなくimportされた先のライブラリで解決される。つまり、識別子が所属するライブラリがおかしいのである。なので、datum->syntax手続きが、#'string-interpolateからx->stringを作る際に本来ならば定義されたライブラリの情報を付加しないといけないんだけど、importしたライブラリの情報を付加する。結果、unbound variableといって怒られる。

とりあえず、一時的なしのぎとしてx->stringもexportしてしまうのが最も簡単な解決方法であろう。0.3.6以降のどこかで頑張って直そう。ちょっと(かなり？)大き目のバグが2つになった。燃える(φΛφ)

やはりいろいろな人に検証してもらうのは非常にありがたい。僕一人では恐らく未来永劫気づかなかったバグだ。

相手の言いたいことを想像する

こっそり転職活動をしていて、ふと思ったこと。ちなみに、行間を読むのではなく、もっと物理的な話。

こっちでは(僕があんまり熱心に転職活動をしていないからなのか)、エージェントが電話もしくはメールを送ってきて求職条件にマッチしたら先に進めるという、どちらかといえば受動的な感じでことが進む。もちろん、自分から応募した場合は向こうの条件に職歴等がマッチした場合のみ先に進む。この辺はどこでも一緒だろう。

さて、現在僕は1件面接が予定されていて今日の午後にそれに行く予定である。っが、それは別の話。今回はその面接をアレンジしたエージェントの話である。

よく、「オランダ人では話しかけた言語で会話を進められる」といわれるくらい言語能力が高いと信じられている。まぁ、ヨーロッパ内の言語なら概ねそうと言えるが、もちろん例外もいる。件のエージェントはどちらかと言えばその例外に当てはまる方のタイプで、ちょっと英語能力が怪しい。そうすると、たまに「何が言いたいのかいまいち分からない表現」というのが出てきて、多分これかなぁと想像することがある。正直なところこれが結構きつい。

何故きついか？普通に日本語を勉強している外国人と会話する際のことを思い浮かべればいいだろう。途切れ途切れで話すとか、言い回しがなんだかわけの分からないものだったりとか、そんな感じ。そうすると、多分こういいたいのかな？と推測をするわけだ。問題は、母語であればその推測が大抵当たるし、そんなに大変じゃないんだけど、第二外国語以降の言語だと習熟度に応じて難易度が変動する。僕の英語はリーズナブル(なんて訳すといいんだろう？)レベルだと思っていて、その手のことをするのは結構しんどいのである。特に、つっかえつっかえだと1秒前に言われた言葉が頭から抜けるのだ。

理解できなかった部分はどうするのか？聞きなおしても同じことが起きるので、「とりあえず最後にメール送ってくれるように聞いてみるか」となって理解を放棄する傾向にある。水は低い方に流れるのだ。あまり、相手の言いたいことを想像しない。よくない傾向である。

ちなみに、この現象は人ごみの中で電話をとったときとか、バスの中、電車の中でも起きる。雑音の中から向こう側の声を拾えないのである。(取りこぼすといった方がいいか？)。これは単純に言語能力の問題なのでヒアリング能力を上げるしかないのだが。

こういう細かい部分ってどうやって鍛えればいいのだろう？なにかいい方法があれば是非教えて欲しいです。

メモリ使用量

Sagittariusは割りと富豪的にメモリを喰う傾向にある。理由はいたって単純で、いろんなところで利便性のため冗長な情報を持たせているからである。

っが、それでは困ることが出てきた。テストを走らせるとかなりのメモリを消費し、Cygwin上でメモリ不足で落ちることがあるのである。地道に不要なオブジェクトをGCフレンドリにしたりして、50MB程度使用量を削ったのだが、焼け石に水感が拭えない。結局後100とかテストファイルが増えれば元の木阿弥な気がするからだ。

実は何が冗長な情報を持っているかは分かっている。ライブラリだ。どこかで書いたがSagittariusではライブラリもオブジェクトでその中にいくつかのメタ情報を持たせてある。importやexportの情報だ。 この二つは必須なので削りようがないのだが、もう一つ、そして恐らく大量にメモリを消費している情報で、親ライブラリ情報がある。これは何をしているのかと言えば、どのライブラリから何がimportされたかという情報である。たとえば以下のコード；

(library (lib1) (export v1) (import (rnrs)) (define v1 1))
(library (lib2) (export v1 v2) (import (rnrs) (lib1)) (define v2 2))

(lib2)は(rnrs)と(lib1)を親ライブラリとして持ち、(lib1)からv1を(rnrs)からは全てのシンボルをimportしているという感じである。

これが、かなり冗長(無駄ともいう)情報を持っていて、たとえば、(rnrs)は親に(rnrs base)とか持っていて、(lib2)はそれが何をexportしているという情報を全て持っている。なんでそんな冗長にしてあるかと言えば、ライブラリから値を引っ張り出してくる際に、その方が楽だからなのだが、はっきり言えば無駄である。実際、import情報だけあれば、全て解決するものであるのだからだ。

このライブラリの実装は複雑怪奇になっていて、正直自分でも必要がなければ構いたくないレベルになっている。(キャッシュもそうだが・・・)。っが今回必要が出てきてしまったので、頑張ってリファクタリングすることにする。とりあえず、意思表示だけ。

RSA key generation

I wasn't satisfied with the performance of RSA key pair generation at all since Sagittarius supported cryptographic operations. So I've done a lot of performance tuning such as bytevector->integer, integer->bytevector procedures. These changes, however, did not make that much difference even it's been improved 100 times faster than previous implementation.

Why? Actually I knew why. The prime number generation was really slow. It reads random number each time and checks if the number is prime or not with Millar Rabin test. In this prime number generation procedure, bytevector->integer is used so I thought if I improve the performance it would be changed dramatically. I've bet on the wrong horse, unfortunately.

Then I let it be for long time (I guess 3 month or so?) and I've got an idea today. The random number generation creates fresh bytevector each time, what if I modified it to read destructively. So I have introduced read-random-bytes! procedure and modified random-prime to use it. Now it's benchmark time. I used following code which generates 1024 bits RSA key pair.

(import (crypto) (math) (time))
(generate-key-pair RSA :prng (pseudo-random RC4))

To make sure the key generation procedure uses the same random generator, I specified :PRNG keyword. The result is below;

% sash test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  1.7565269470214844 real    1.826000 user    0.047000 sys

% ./build/sash.exe -Llib -Lsitelib -Dbuild -L./ext/crypto -Lext/time test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  0.769230 real    0.749000 user    0.031000 sys

Yes! It's improved as twice fast as before. The problem is, however, this change, more specificaly read-random-bytes!, introduced imcompatiblity of 0.3.5. Well, the change only affects custom pseudo random generator and I guess it's used by only me. So just wrote note on the document.

続 exportされた変数

一つ前の記事で、実行時エラーにしていたがえいやっとコンパイル時エラーにすることにした。

Sagittariusではライブラリも(実は)First class object(訳語忘れた)で、普通のR6RS処理系がするようなライブラリをrenameしてごにょごにょということは(いい悪いは別にして)行わない。 マクロ展開フェーズというものもなく、全てコンパイル時に解決している。これは、マクロ展開器とコンパイラで定義が被るのが嫌だったので。似たようなコードがそこかしこに出てくるのが我慢ならなかった。

本題に戻る。なので、ライブラリが別であれば、識別子は被っても問題ない。lookup(訳語知らない)時にimportされているものを調べて合致したものを返しているだけなので。なので再定義されても、参照される先が変わるだけ。正直特に必要性を感じていなかったし、今では面倒になっただけかも感があるのだが、規格に準拠するのもポータブルなコードを書くのには欠かせない部分だろうと重い腰を上げた感じ。

どう実装したか？
実は非常に簡単で、グローバルに値を定義できる構文と値を変更できる構文ってSchemeでは合計で3つしかない(よね？)。つまり、define、define-syntaxとset!の3つ。前2つは定義された値が同じライブラリ外で既に定義されていればエラーを投げる。set!は先に局所変数を探して、違ったら大域変数なので、その際にチェック。
問題だったのは、bootコードを生成するSchemeコードが再定義を前提で書かれていること。全部ライブラリ形式に書き換えてすっきりさせるというのもありだったのだが、面倒だったのでとりあえず再定義可能なモードを急遽入れて対応。ごにょごにょ黒魔法的な何かを使うよりはいいだろうと思う。そのうち書き直そう。

ちょっとした課題？
正直デフォルトで書き換え不可はあまりに面倒だなぁと思っているので、R6RSもしくはR7RSモードの際だけにするかもしれない。テストケースをコンバートしている際に思った。どうも僕はゆるい開発スタイルの方が好きらしい。

Shiroさんのコメントで何故R6RSが再定義を許さないかというのが非常に面白かった。既存の名前空間(モジュールシステム？)を実装していない処理系でもライブラリが持てるような考慮なんだろうか？psyntaxとか他の展開器(Andre van Tonderのしか知らないけど)ではlibraryも展開するようになってるし。

exportされた変数

一つ前の記事に言及していた記事の著者さんからコメントが付いてた。っで、自分の書いたコメントに疑問が(ぉぃ

set!で変更可能となると、「取り扱い注意」のラベルが必要かもしれませんが。

よく考えてみると、Sagittariusでは以下のようなことができる。

(library (test)
    (export variable)
    (import (rnrs))
  (define variable 1))

(import (test))
(set! variable 2)
(print variable)
#|
;; Output
2
|#

これはR6RS的にはエラーにならないとまずい。記憶が正しかったら、R7RS的にもエラーだったはず。
Sagittariusではデフォルト(というか、現状だと必ず)「取り扱い注意」のラベルが要ることになる。直すかなぁ。変更できた方が便利だろうかと思ったんだけど、変更されない方が便利だよなぁ。

でも、Ypsilonでも#!r6rsをつけないとエラーにならないなぁ。 どうしよう？

パラメタ

Schemeのparameterはわざわざ評価してやらないと値が取れないから使うのが面倒だ、と常々思っていたのだが、

識別子マクロとパラメタによる大域変数エミュレート

にそれを解消するマクロが紹介されていた。確かに、ぱっと見よさげだなぁと思ったのだが、これってSRFI-39が提供するparameterizeマクロと相性最悪じゃね？と思ってちょっと実験してみた。

(import (rnrs) (srfi :39))
(define-syntax define-identifier-parameter
  (syntax-rules ()
    ((_ var val)
     (begin
       (define t (make-parameter val))
       (define-syntax var
         (make-variable-transformer
          (lambda(x)
            (syntax-case x (set!)
              ((set! _ a) #'(t a))
              (_ #'(t))))))))))
(define-identifier-parameter *variable* 1)
(display *variable*) (newline)
(parameterize ((*variable* 2)) (display *variable*) (newline))
(display *variable*) (newline)

検証はいつもどおり、Sagittarius、YpsilonにMosh。
っで結果：

Sagittarius

Ypsilon

1を3回出力。(parameterizeされてない)

Mosh

&assertion: (1)は関数じゃないと怒られた

ふむ、パラメタはparameterizeと一緒に使われること(というか、僕は常にそれを想定)が多いと思うので、これだと、値が変更できるライブラリ変数という位置づけでしか使えないということだろうか？
面白いけど、使いどころが限定されそうだ。

{}の扱い

SRFI-105関連なのか、R7RSのGoogle Groupsに以下の投稿があった。

From   John Cowan

I know it's the last minute, but I've just a filed a ticket to add [ ] { }
to the list of delimiters, along  with ( ) " ; | and whitespace.
Implementations do use them for various things (R6RS systems of course
treat brackets as equivalent to parens), but I can't see people using them as
parts of identifiers (though some Schemes do allow it).

R6RSでは「[]」は使われているけど、「{}」ってそうでもないよなぁと思いちょっとテスト。試した処理系はYpsilon、Mosh、Petite Chez SchemeとSagittarius。(なんで自分の処理系もかって？忘れてるからだよ、言わせんな恥ずかしい///)
単発の「{」と「}」に加えて「{-reader」と「}-reader」というシンボルを読ませる。っで、結果。

処理系	{	}	{-reader	}-reader
Ypsilon	reader error
Mosh	reader error
Petite	\x7B;	\x7D;	unbound variable \x2D;reader
Sagittarius	|{|	|}|	|{-reader|	|}-reader|

R6RSのリーダの定義(読めよ)を忘れたのでどれが正しい動作かはよく分からないけど、Ypsilon、Moshはシンボルに「{}」は使えない。Petiteは「{}」はデリミタになるので、事実上使えないっぽい。Sagittariusは特別視していないらしい。
ちなみに、Gaucheでは「{}」もリストを読むのに使えるので、エスケープなしではシンボルとして読まない。

これをシンボルとして読み込んでうれしいことはあまり無い気もするのだが、R7RSの精神がミニマリズムなのであれば、実装者から自由を奪うのは多少その精神から外れる気がする。

追記：
Sagittariusでも#!r6rsをつけるとYpsilon、Moshと同じ動作になる。
R6RS的には「{}」はシンボルに使ってはいけない文字である。(調べた)

SRFI-105を試してみる。

リーダをいじる系のSRFIを割りと簡単に試すことが出来るのもSagittariusの特徴の一つだと信じているので、早速新SRFIを試してみる。
(自分でも使い方忘れてて、ドキュメントを探したのは内緒だ)

;; From reference implementation

;; Return true if lyst has an even # of parameters, and the (alternating)
;; first parameters are "op".  Used to determine if a longer lyst is infix.
;; If passed empty list, returns true (so recursion works correctly).
(define (even-and-op-prefix? op lyst)
  (cond
   ((null? lyst) #t)
   ((not (pair? lyst)) #f)
   ((not (eq? op (car lyst))) #f) ; fail - operators not the same
   ((not (pair? (cdr lyst)))  #f) ; Wrong # of parameters or improper
   (else (even-and-op-prefix? op (cddr lyst))))) ; recurse.

;; Return true if the lyst is in simple infix format
;; (and thus should be reordered at read time).
(define (simple-infix-list? lyst)
  (and
   (pair? lyst)           ; Must have list;  '() doesn't count.
   (pair? (cdr lyst))     ; Must have a second argument.
   (pair? (cddr lyst))    ; Must have a third argument (we check it
                    ; this way for performance)
   (symbol? (cadr lyst))  ; 2nd parameter must be a symbol.
   (even-and-op-prefix? (cadr lyst) (cdr lyst)))) ; true if rest is simple

;; Return alternating parameters in a list (1st, 3rd, 5th, etc.)
(define (alternating-parameters lyst)
  (if (or (null? lyst) (null? (cdr lyst)))
      lyst
      (cons (car lyst) (alternating-parameters (cddr lyst)))))

;; Not a simple infix list - transform it.  Written as a separate procedure
;; so that future experiments or SRFIs can easily replace just this piece.
(define (transform-mixed-infix lyst)
  (cons 'nfx lyst))

;; Given curly-infix lyst, map it to its final internal format.
(define (process-curly lyst)
  (cond
   ((not (pair? lyst)) lyst) ; E.G., map {} to ().
   ((null? (cdr lyst)) ; Map {a} to a.
    (car lyst))
   ((and (pair? (cdr lyst)) (null? (cddr lyst))) ; Map {a b} to (a b).
    lyst)
   ((simple-infix-list? lyst) ; Map {a OP b [OP c...]} to (OP a b [c...])
    (cons (cadr lyst) (alternating-parameters lyst)))
   (else  (transform-mixed-infix lyst))))

;; set macro characters
(set-macro-character 
 #\{ (lambda (p c) (process-curly (read-delimited-list #\} p))))
(set-macro-character 
 #\} (lambda (p c) (error '|}-reader| "unexpected #\\}")))

;; test
(print '{a + b})
(print '{a * {b + c}})

#|
;; output
(+ a b)
(* a (+ b c))
|#

なんとお手軽。
ポイントは、閉じ括弧もリードマクロとしてマークすること。じゃないとread-delimited-listがnon-termな文字として識別しちゃうので、意味不明のエラーが出て悩む。(ってか、3分くらい悩んだ・・・orz)

これくらいお手軽に試せるからいいけど、そうじゃない処理系はこれを入れる気になるんだろうか？そこまで中置記法にこだわる理由が(もはや)分からない。

Libraryのルックアップ

ずっと悩んでいる問題の一つ。
SagittariusではR6RSが禁止しているexportされたシンボルの上書きを許している。理由はその方が便利だから。

ただ、これ便利なんだけど、プログラマが重複するシンボルを含むライブラリをimportした際にどちらが使われるのか意識できないと拙い。Sagittariusでは「後からimportしたものが使用される」というルールを作っている。もちろん明にexceptとか使えば問題ない。ただ、スクリプトとして走らせた際がちょっと困って、既にimportされているライブラリがトップレベルにある。

直接exportされているものなら別に問題ないんだけど、問題になるのは間接的にexportされているもの。SRFIライブラリなんかはもろにこれで、

(import (srfi :1))

とかってやると全部間接的に解決される。っで、上記の例でトップレベルでは既に(rnrs)がimportされているので、removeとか使うと、SRFI-1の方を使って欲しいのに、R6RS定義の方が使われて悲しい思いをする。

原因は0.3.5までは、間接解決されたものは解決リストの末尾に追加されているため。これではいろいろまずいので修正した。
修正方法は非常に単純な発想で、直接importの次に間接importを追加してから既にある解決リストを追加するというもの。
今まで不便だなぁと思いつつ放っておいたのだが、重い腰をよっこらせっとあげた。これで今まで明示的に

(import (srfi :1 lists))

と上記の問題を回避するために書いていたのをやらなくても済む、はず。

スライドを作ってみた

別にどこかで発表するわけでもないのに、スライドを作ってみた。

Sagittarius 0.3.5リリース

Sagittarius Scheme 0.3.5がリリースされました。今回のリリースはメンテナンスリリースです。

修正された不具合

• format関数が長さを指定した際に空文字を返す不具合が修正されました。
• EMSA-PSSを用いた検証がときどき失敗する不具合が修正されました。
• SRFI-13ライブラリにあるxsubstringが&assertionを投げる不具合が修正されました。

新たに追加された機能

• ライブラリ名に負の数でない正確数が使用可能になりました。R7RS 6th ballot
• vector-append、bytevector-append (R7RS 6th ballot)、vector-concatenate及びbytevector-concatenateが追加されました。
• 即値な浮動小数点数がサポートされました。(現状では5の倍数以外には適用されません)
• (eqv? 0.0 -0.0)が#fを返すように修正されました。(R6RS及びR7RS 6th ballot)
• port-for-each、port-mapが(util port)に追加されました。
• drop*が(util list)に追加されました。

改善点

• utf8->string、string->utf8、bytevector->string及びstring->bytevectorがオプショナル引数startとendを受け取るようになりました。
• equal?がレコードの中を再帰的に調べるようになりました。
• (exit #t)が(exit)または(exit 0)と同様の振る舞いをするようになりました。(R7RS 6th ballot)
• Windows版のバイナリがMSVD*.dllを必要としなくなりました。
• 正規表現の速度が改善されました。
• list-sortの速度が改善されました。

新たに追加されたライブラリ

• RFC 4122 ライブラリ(rfc uuid)が追加されました。
• RFC 1421 ライブラリ(rfc pem)が追加されました。

新たに追加されたドキュメント

• (util list)がドキュメント化されました。
• (sagittarius io)がドキュメント化されました。

続 正規表現エンジンのチューニング

とりあえず、昨日のコードがGauche(0.9.3)と同程度の速度が出るように改善できた。

やったこと

1. 疎な配列をエミュレートしていたのだけれど、それに付随していたイテレータの削除
• 10%程度
2. 地味にコードのリファクタリング
• 10%程度
3. インストラクションコードの2番目がアトムチェックのコードならマッチする場所までチェックする
• これが効いた、900% 

もともと昨日のコードでは、1000個の'a'と'01:23'という文字列が1000回繰り返して最後に':45'とつくのだけれど、途中の'a'の部分は絶対にマッチしないくせにわざわざキュー操作していたのがまずかったのだ。なら、最初にマッチする場所まで先読みしてやれよかったという話。

現状ではものすごく手抜きな先読みなので、#/(\d\d):\d\d:\d\d/と変更されるだけで遅くなるんだけど。また気になったら直すことにしよう。

正規表現エンジンのチューニング

SagittariusではRE2(Pike VM?)ベースの正規表現エンジンを積んでいて(実際にはハイブリッドなのだが、今回はこっちのエンジンが対象)、基本的な正規表現ならO(n)で走る。実際にはO(n+α)だったりするが、O(n)でいいだろう。リニアに走るなら速度はそんなに気にしなくてもいいんじゃないかと思うのだが、以下のようなコードを走らせると不満が出るほど遅い。

#< (sagittarius regex) >
(import (time) (srfi :1)
 (text tree)
 (sagittarius control)
 (sagittarius regex)
 (only (sagittarius regex impl) dump-regex))

(define s
  (tree->string `(,(make-list 1000 `(,(make-string 1000 #\a) "01:23")) ":45")))

(define (time-this count thunk)
  (time (dotimes (i count) (thunk))))

(print (time-this 10 (^[] (#/\d\d:\d\d:\d\d/ s))))

以下が実行結果(Cygwin on Windows XP CoreDuo 1.6GHz)

$ sash reg.scm

;;  (dotimes (i count) (thunk))
;;  2.921875 real    2.969000 user    0.000000 sys
#t

ちょっとねぇ・・・とりあえず、本質的な問題を脇に置いておいて、不必要な計算を減らして400ms程度速くしたのだが、やはり枝葉の最適かなので2割程度にしかならない。

何が問題か？エンジンの走り方以外の何者でもないのだが・・・
 PikeVMはバックトラックをしないNFAなエンジンである。っで、バックトラックさせない為に、内部で仮想スレッドとスレッドキューを持っていて、一文字チェックする毎にスレッドキューに次に実行させるインストラクションとマッチした状態を保存したスレッドを溜め込む。文字がマッチしなければキューにあるスレッドは1個なんだけど、例えば4文字までマッチしたスレッドがあるとすると、他にも3スレッド脇で走っていたりする。
以上を踏まえて、上記のコードを見ると、途中で「01:23」と4文字マッチして、捨てられるという処理が1000回ほど必要になる。そのため、内部で回すスレッドの関係でガッツリ遅くなる。のではないかと結論付けている。
現実的にこれほどベンチマークに特化したかのような入力文字列の処理が必要になるかどうかは別にしても、遅いというのは悪であるのでなんとかしたい。しかし、問題の幹の部分はそれこそ正規表現エンジン自体を改善(可能ならDFAにするとか)しないと無理なので、そこまで大掛かりにしたくない(ものぐさ)。
とりあえず、やってみて効果のあったもの。

• 不要コードの削除
• キューをクリアするに最小限の要素のみクリア

無駄だったもの

• 急場のダイレクトスレッドコード

枝葉のチューニングではこの程度が限界だろうか？せめて倍速まで持っていきたいのだが、う～ん。

Lisp啓蒙活動(?)

自動SQL生成スクリプトを書いているときに、同僚がふと作業風景を覗き込んできた際に発生した会話から。

Colleague: You like Emacs, don't you?
Me: I do.
Colleague: Is it Lisp?
Me: Sort of. (It's Scheme but I think Sagittarius is already sort of 'MY LISP' now...)
Colleague: It's one of the languages I can't understand?
Me: It's not so difficult, you know?
Colleague: It is. I don't think I can accept the parenthesis.
Me: (I wish I could show this site : 本当にLispはカッコが多い？)

これ以外にも、なんだか毛嫌いというか、Lispは近寄りがたいみたいな雰囲気で話すので、なんでだろうなぁ？と思い考えてみた。
そういえば僕も昔はLispを避けていたのだから、似たような考えがあって、何かがきっかけで考えが変わったはずである。っで、避けていた理由を探してみた。

1. Lisp入門のサイトとかで必ずある「consとリスト」の解説。
•  正直読んでも、だから何ができるの？という気になった。
•  更に、なんか面倒だなぁという気にさせられた。
2. How to become a hackerの悟り体験の話。
• なんだか小難しい言語ではないのかという錯覚を起こさせた。
3. 関数型言語と再帰。
• 手続き型言語から始めると再帰の概念は分かりにくい。(少なくとも僕はそうだった)
4. 無名関数、クロージャ、高階関数。
• 手続き型、以下略。
• これに関しては、言語ごとに(特にクロージャ)定義が違うのも問題な気がする。
5. lambdaという言葉。 
• boost::lambdaでlambda = 無名関数 = クロージャみたいな理解したなぁ。(遠い目)

とりあえず、思いついただけではこんな感じ。じゃあ、何がこのとっつきにくさを変えたかという点だけど、これは正直よくわからない・・・SICP読み始めて、処理系作り出して、折角作ってるんだし使い倒さないとと言うのが最初のモチベーションだった気がする。

それではあまりにもと思うので、啓蒙するにはどうすればいいか。
※僕が考える最強の啓蒙活動的な感じです。当てにしないでください

1. 可能な限りシンプルに、かつC言語とかの最初のステップに合わせる。
• Hello Worldでもいいし、ファイルを一行処理してとかでもいいと思う。
• いきなり、consとリストではひく。
2. エディタの支援を当てにしてもいいということを教える。
• 括弧の対応とか目視では無理。
• Emacs最強(これも啓蒙してしまえ！)
• S式一個切り取って貼り付けとか知ると、Javaとか面倒すぎて編集する気になれなくなるはず。
3. 再帰を可能な限り隠す。
• CLならloopで大抵いけると思う。
• Schemeならnamed letで。
4. クロージャは単なる関数だとしておく。
• 名前に臆することもあるよね？
5. でも、処理系がたくさんあってどれ使えばいいのさ？
• 入門レベルのCLならどれでもいいはず。
• Schemeは、Gaucheかなぁ。実績あるし。(自分の処理系を推したいが、名前を横に並べるのもおこがましい気になる・・・)

う～ん、いまいちだな。多分、こんなことしなくてもプログラムが好きな人は自分の好きな言語を見つけるし、いろんな言語を書けるんだよね。毛嫌いする人はどちらかと言えば「ぷろじぇくとまね～じゃ～」とかあんまり自分ではコードを書かない人たちなイメージ。実際、職場の開発者で数人は関数型言語やってる。(ClojureだったりHaskellだったりするけど)
とりあえずリスト作って、後はfor-eachでもmapでもfoldでも使えばいいじゃん、見たいな感覚になると早いと思うんだけど、そこまでが遠いなぁ・・・

list-sortを書き換え

ふとTwitterで以下のページを言及しているツイートを見つけた。

ソート済みのリストに対する破壊的マージソートの改良

これはlist-sortのパフォーマンス改善に使えると思い、早速実装。この記事書く前に全部置き換えてコミットしてしまったのと元々Sagittariusのlist-sortはYpsilonのものを使っていたので、以下のコード(速度計測)はYpsilonで確認。

(import (rnrs)
        (time)
        (srfi :8)
        (srfi :27)
        (srfi :42))

(define sorted-list (list-ec (: x 100000) x))
(define reverse-sorted-list (reverse sorted-list))
(define nearly-sorted-list1 (list-ec (: x  100000)
                                     (if (zero? (random-integer 1000))
                                         (random-integer 100000)
                                         x)))
(define random-list (list-ec (: x 100000)
                             (random-integer 100000)))

(time (list-sort < sorted-list))
(time (list-sort < reverse-sorted-list))
(time (list-sort < nearly-sorted-list1))
(time (list-sort < random-list))

(define (list-sort2 proc lst)
  (define (merge-list! proc head lst1 lst2 tail)
    (let loop ()
      (cond ((proc (car lst2) (car lst1))
             (set-cdr! tail lst2)
             (set! tail lst2)
             (let ((rest (cdr lst2)))
               (cond ((null? rest)
                      (set-cdr! lst2 lst1)
                      (cdr head))
                     (else
                      (set! lst2 rest)
                      (loop)))))
            (else
             (set-cdr! tail lst1)
             (set! tail lst1)
             (let ((rest (cdr lst1)))
               (cond ((null? rest)
                      (set-cdr! lst1 lst2)
                      (cdr head))
                     (else
                      (set! lst1 rest)
                      (loop))))))))
  (define (fast-merge-list! proc try? head lst1 tail1 lst2 tail2 rest)
    (if try?
        (cond ((not (proc (car lst2) (car tail1)))
               (set-cdr! tail1 lst2)
               (values lst1 tail2 rest))
              ((proc (car tail2) (car lst1))
               (set-cdr! tail2 lst1)
               (values lst2 tail1 rest))
              (else 
               (values (merge-list! proc head lst1 lst2 head)
                       (if (null? (cdr tail1))
                           tail1
                           tail2)
                       rest)))
        (values (merge-list! proc head lst1 lst2 head)
                (if (null? (cdr tail1))
                    tail1
                    tail2)
                rest)))
  (define (do-sort lst size head)
    (define (recur lst size)
      (cond ((= size 1)
             (let ((h (list (car lst))))
               (values h h (cdr lst))))
            ((= size 2)
             (let* ((a (car lst))
                    (ad (cadr lst))
                    (h (if (proc ad a)
                           (list ad a)
                           (list a ad))))
               (values h (cdr h) (cddr lst))))
            (else
             (let ((half (div size 2)))
               (receive (lst1 tail1 rest) (recur lst half)
                 (receive (lst2 tail2 rest) (recur rest (- size half))
                   (fast-merge-list! proc (>= size 8) head
                                           lst1 tail1
                                           lst2 tail2
                                           rest)))))))
      (receive (lst tail size) (recur lst size)
        lst))
    (define (divide lst)
      (let loop ((acc 1) (lst lst))
        (cond ((null? (cdr lst)) (values acc '()))
              (else
               (if (proc (car lst) (cadr lst))
                   (loop (+ acc 1) (cdr lst))
                   (values acc (cdr lst)))))))
    (receive (n lst2) (divide lst)
      (if (null? lst2)
          lst
          (let* ((head (cons '() '()))
                 (r (do-sort lst2 (length lst2) head)))
            (merge-list! proc head (list-head lst n) r head))))))

(newline)
(display 'list-sort2) (newline)
(time (list-sort2 < sorted-list))
(time (list-sort2 < reverse-sorted-list))
(time (list-sort2 < nearly-sorted-list1))
(time (list-sort2 < random-list))

オリジナル(SBCL)のコードはdevide相当のものはないのだけれど、これがあるのと無いのではソート済みのリストが渡された際のパフォーマンスが全然違う(10倍程度)ので入っている。
以下が結果。

% Ypsilon test2.scm

;;  0.006001 real    0.0 user    0.0 sys

;;  0.16501 real    0.327602 user    0.0 sys

;;  0.194012 real    0.374402 user    0.0 sys

;;  0.302017 real    0.624004 user    0.0 sys

list-sort2

;;  0.007 real    0.0 user    0.0 sys

;;  0.116007 real    0.202801 user    0.0 sys

;;  0.16201 real    0.249602 user    0.0 sys

;;  0.254015 real    0.343202 user    0.0 sys

ソート済以外は高速になっているのが分かる。(ソート済みは一緒のはず)。
Sagittariusで検証した際はreversed-sorted-listで倍速、nearly-sorted-list1ではほぼ倍速。random-listは2割程度とYpsilonと同程度の速度改善であった。

どうでもいいのだが、 moshで上記のコードを走らせる(list-headをtakeにする等の変更が必要だが)と劇的に遅くなる。どの処理系でも速度改善になるというわけではないらしい。

どうでもいい追記その２。
moshのlist-sortはスタックを激しく使用するらしく、reversed-sorted-listで45回のスタック拡張が発生した。(ちょっと手を入れて、スタックの拡張が起きるとwarningメッセージ出すようにしてある。)

どうでもいい追記その３．
Ypsilonでもリストの要素数を200万個以上にするとメモリが足らなくなった。オリジナルは末尾再帰じゃないのでしょうがないのか。改善されたのは速度だけではないのもいい感じである。

Bug of EMSA-PSS

I have just fixed the bug in EMSA-PSS verify. It has been there since version 0.2.x.

The problem was test case for EMSA-PSS verify failed *sometimes*, like once in 100 times or once in a month. It was really annoying and made this procedure unreliable.

Because of this random frequency, I suspected it was random number generator. In the test case, it uses secure random number generator so that it generate different number each time. (well, thank god I used secure random, otherwise I would never notice this bug.)

So first step to fix this bug was create a proper (improper?) state of PRNG. To create it, I made this code;

(import (crypto) (math) (getopt))

(define key-pair (generate-key-pair RSA :size 512 :prng (pseudo-random RC4)))
(define valid-rsa-message (string->utf8 "test message"))

(define prng (pseudo-random RC4))
(with-args (command-line)
    ((c (#\c "count") #t "1"))
  (let ((count (string->number c)))
    (do ((i 0 (+ i 1))
  (r (read-random-bytes prng 100) (read-random-bytes prng 100)))
 ((= i count) r))))

(let* ((rsa-sign-cipher (cipher RSA (keypair-private key-pair)))
       (rsa-verify-cipher (cipher RSA (keypair-public key-pair)))
       (em (sign rsa-sign-cipher valid-rsa-message :prng prng)))
  (verify rsa-verify-cipher valid-rsa-message em))

And this shell script;

#!/bin/sh

for i in `seq 1 $1`
do
    count=`expr $i + 100`
    echo $count
    `sash -Lext/crypto crypto.scm -c $count`
done

Then ran the script and check which number was the key number! After the inspection, the number was 181.

Now, it's time for debug. once I could find the PRNG state, it was really simple to fix. The problem was the signed message's first 2 bytes. RSA operation deletes left most 0's so verify procedure needs to add removed 0's in front of the message. However previous implementation did not add more than 2 zeros. That was the problem.
So I modified to add propert 0's in front of the message, and now it works!

I hope Sagittarius is now a bit more reliable. Even though I have no idea if it was the only problem that causes test case failed.

Haskell風の$マクロ その２

さすがに前回のはあんまりだよなぁと思い、もう少しだけR6RSっぽくしてみた。

(import (rnrs))
(define-syntax $
  (lambda (x)
    (define (build es)
      (let loop ((es es) (r '()))
        (syntax-case es ($)
          (() (reverse r))
          (($ es ...)
           (append (reverse r) (list (loop #'(es ...) '()))))
          ((e . es)
           (loop #'es (cons #'e r))))))
    (syntax-case x ()
      ((k es ...)
       (build #'(es ...))))))
 
(define (print . args)
  ($ for-each display args) (newline))
 
($ newline)
 
($ for-each print
   $ list 1 2 3)

($ for-each print
   $ map cons '(1 2 3) $ list 4 5 6)

単に自前で分解するのをやめてsyntax-caseに頼っただけとも言う。前回同様、mosh、Ypsilon、Sagittariusで確認。 reverseをreverse!にappendをappend!するときっとメモリ節約。処理系が対応していればだけど。

Haskell風の$マクロをR6RSで

ChatonのGauche部屋を見ていて、Shiroさんが$を多用しているなぁと思い、流行は$なのだろうかと勘違いして書いてみた。R5RSで動くやつはGaucheにあるので、R6RSのsyntax-caseを使って。

(import (rnrs))
(define-syntax $
  (lambda (x)
    (define (build k es)
      (define $ (datum->syntax k '$))
      (define (build-es es)
 (let loop ((es es) (r '()))
   (cond ((null? es) (reverse r))
  ((and (identifier? (car es))
        (free-identifier=? $ (car es)))
   (append (reverse r) (list (loop (cdr es) '()))))
  (else
   (loop (cdr es) (cons (car es) r))))))
      #`(#,@(build-es es)))
    (syntax-case x ()
      ((k es ...)
       (build #'k #'(es ...))))))

(define (print . args)
  ($ for-each display args) (newline))

($ newline)

($ for-each print
   $ list 1 2 3)

なんというか、syntax-caseを使っているのは単にS式を直接扱いたかっただけという・・・僕の頭ではマクロ展開中に値を貯めてとか、分解してとかが無理だった・・・
動作はmosh、Ypsilon、Sagittariusで確認。恐らく、syntax-caseの動作としては信頼が出来る順に確認してるはず(moshはpsyntax使っているので多分マクロ周りの信頼が高い、はず・・・)

マクロ展開中に式を分解したりするのってどうやって考えれば身につくのだろうか？低レベルのマクロが書けると面倒になってS式そのままいじってしまう・・・

sxpathメモ その2

XSDをサポートするモジュールを書いていて、名前空間付きのsxmlをsxpathでいじる必要があった。すっかりどうやっているのかを忘れてググッたら自分のページが出てきた。っが、いまいち何がどうなっているのか詳しくなかったので、もう一回書くことにする。
ちなみに、これがその1

以下のコードを実行する。(sample.xsdはXSDで記述されたXMLファイルである)

(import (rnrs)
 (text sxml ssax)
 (text sxml sxpath)
 (sagittarius control)
 (pp))

(define-constant namespace '((xsd . "http://www.w3.org/2001/XMLSchema")))
(call-with-input-file "sample.xsd"
  (^p 
   (and-let* ((sxml (ssax:xml->sxml p namespace))
       (path (sxpath "//xsd:schema" namespace))
       (doc  (path sxml)))
     (pp sxml)
     (pp doc))))
#|
Output:
(*TOP* (@ (*NAMESPACES*
            (xsd "http://www.w3.org/2001/XMLSchema")))
       (*PI* xml
             "version=\"1.0\" encoding=\"ISO-8859-1\" ")
       (xsd:schema
         (xsd:element
           (@ (name "shiporder"))
           (xsd:complexType
             (xsd:sequence
               (xsd:element
                 (@ (type "xs:string") (name "orderperson")))
               (xsd:element
                 (@ (name "shipto"))
                 (xsd:complexType
                   (xsd:sequence
                     (xsd:element
                       (@ (type "xs:string") (name "name")))
                     (xsd:element
                       (@ (type "xs:string") (name "address")))
                     (xsd:element
                       (@ (type "xs:string") (name "city")))
                     (xsd:element
                       (@ (type "xs:string") (name "country"))))))
               (xsd:element
                 (@ (name "item") (maxOccurs "unbounded"))
                 (xsd:complexType
                   (xsd:sequence
                     (xsd:element
                       (@ (type "xs:string") (name "title")))
                     (xsd:element
                       (@ (type "xs:string")
                          (name "note")
                          (minOccurs "0")))
                     (xsd:element
                       (@ (type "xs:positiveInteger") (name "quantity")))
                     (xsd:element
                       (@ (type "xs:decimal") (name "price")))))))
             (xsd:attribute
               (@ (use "required")
                  (type "xs:string")
                  (name "orderid")))))))
()
|#

sxpathに名前空間を渡しているのに、何も返してこない。これに昨日30分くらいはまった。これは指定している名前空間がまずくて、正しくは以下のものを渡さないといけない。

'((xsd . "xsd"))

sxpathに渡される名前空間は、ssaxのそれとは違い、「XPath内にある名前空間の解決」に使われる。つまり、上記のコードで言えば、"//xsd:schema"の部分の"xsd:"である。この部分が、「渡された名前空間のcar部」で、「cdr部は操作するSXMLのエレメントの名前空間」になる。
なので、渡されたSXMLがフルネーム(ここではURIを指す)で修飾されていれば、上記のコードのような名前空間を渡しても問題ない。
この仕様のいいところは、名前空間さえ正しく指定してやればXPathを変更せずに異なる名前空間プリフィックスが処理できること。たとえば、上記のSXMLのプリフィックスがxsとかでも、'((xsd . "xs"))を渡してやれば、XPathの修正は要らない。
嫌なところは、ssaxに名前空間を渡してでパースされたSXMLと非常に相性が悪いこと。
これは、挙動からの推測だが、この名前空間の解決はXPathでのみ発生していて、SXPathでは起きないみたい。なので、"//xsd:schema"の部分を'(// xsd:schema)とすると名前空間なしでも値が返ってくる。この奇妙なチグハグ感もなかなか「トリッキーなライブラリを使ってるぜ！」的な陶酔感をかもし出していていい感じではある。(正直勘弁してほしいが・・・)

その1のページで言及されているメールのリプライに答えというかsxpathにおける名前空間の扱いが書いてあるので、単に蛇足ではあるが。

R7RSの6th Ballot

ザーッと目を通した。

とりあえず、この辺は変更されないだろうと当たりをつけたもの、もしくは変更されてもあればあった出便利なものを実装。
実装したものは以下：

• ライブラリ名に数字を使用可能にする
• ドラフトの6には符号なし正確な整数とあったので、一応Bignumも入れてある
• (exit #t)でEXIT_SUCCESSを返す。
• (exit 0)と書くよりは確かに分かりやすい
• vector-appendを追加
• bytevector-appendを追加
• レコード型のequal?
• 再帰的に中身を見るように変更
• それに伴ってeqv?もちょっと変更
• utf8->stringとstring->utf8のオプショナル引数
• ついでに、string->bytevectorとbytevector->stringにも追加
• UNICODEを6.1.0にアップデート
• string->vectorとvector->stringのオプショナル引数

とりあえず、残りというか、include-library-declarationsとかは後回し。正直残り数日の間で消えてほしいなと思ったり・・・

Racketが異様に速い

Sagittariusはfibを走らせる程度ならGaucheやYpsilonと同じくらいの速度で走るのだが、Racketはさらにその倍くらいの速度が出る。
正直、なにこれ？状態なのだが、ちょっとテストコードを書いてみてなんとなくどうやっているのかが分かった。(追いつけるという意味ではない)。
以下がテストコード。

#include 

SgObject fib(SgObject n)
{
  if (Sg_NumLt(n, SG_MAKE_INT(2)))
    return SG_MAKE_INT(1);
  return Sg_Add(fib(Sg_Sub(n, SG_MAKE_INT(1))),
  fib(Sg_Sub(n, SG_MAKE_INT(2))));
}

int main(int argc, char **argv)
{
  int n = atoi(argv[1]);
  GC_INIT();
  printf("%d\n", SG_INT_VALUE(fib(SG_MAKE_INT(n))));
  return 0;
}

Schemeじゃないじゃん！イメージとしては、SchemeのコードをCにしただけ。ちなみに、以下のコマンドで実際に動くバイナリが出る。(メモリアロケートしてないからGC_INIT()は要らないんだけど)

% gcc -O3 test.c -o fib `sagittarius-config -I` -DHAVE_CONFIG_H -lsagittarius `sagittarius-config -L` -lgc

-DHAVE_CONFIG_Hとかちょっとダサいが、まぁそれは置いておく。(0.3.3辺りからいけるはず、ただ明文化はあえてしてない)
これでできた実行ファイルを実行するとRacketより多少速く動いた。ということは、Racketはこれに+α程度の処理をくっつけた何かしらで動いているということなのだろう。バイトコード動かすVMだと思っていたのだが、違うのだろうか？

さて、ここからは考察。
JITを実装していて気づいたことがあって、

1. VMオプコードのディスパッチは処理時間をそんなに悪化させていないということ
2. FRAMEとRETインストラクションで起きる継続フレームのPUSHとPOPがやたら遅いということ

2番目は現状のVMを貫くならどうしようもなくて、やれそうなこととしては継続フレームのサイズを減らすことくらいなのだが(現状では6ワード)、正直現状では削れて1ワードかなぁといったところ。しかも、その1ワードはfibを走らせるだけなら使われることはない部分だったりする。
ものすごく気合を入れて頑張るなら、上記のプログラムは末尾再帰に置き換えることができるので、コンパイラがそんな雰囲気を感じたら、置き換えるようにするとかだろうか？そうすればFRAME命令はなくなるし、速度も改善されるが、そうするとプログラムが書いてある通りにコンパイルされてないよな？(やれるやれないは別にして)
(どうでもいいのだが、Racketでfibを末尾再帰で書いても速度が2倍弱程度しか改善されない。Sagittariusでは50倍くらい。いろいろ不思議な処理系だ)

Cygwinのmprotect

mprotectだけではなくposix_memalignもなのか、さらにこれがCygwin限定なのか他のUnix系環境もなのか調査してない。
(少なくともCygwinのposix_memalignはあるサイズを境に同一のアドレスを返すっぽいが)

何が問題か？とりあえず2つほど見つかっていて、

• mprotectが失敗する
• posix_memalignがなぜか重複したアドレスを返す

1つ目はページ境界の問題かなぁとおも思っていたりするので(でもposix_memalignでページサイズ割り当ててるよなぁ？)ちょっと保留。
2つ目は正直意味不明だが、10回くらい4096バイトを割り付けると9回目と10回目が同一のアドレスを返す。Cygwin環境だとヒープサイズが著しく少ないのでそれがあるのかもしれないが。

とりあえず、2つ目を考える。(もし最大４Mくらいしか使えないって言われると後々問題になるが、)現在１つのクロージャに1つのページを割り付けている。実際に使用されるサイズとしては10分の1程度に収まることが多いのにも関わらずだ。(デバッグ用のトレースとかつけると10倍に膨れ上がるけど。)
なので、とりあえずメモリの管理をもう少し切り詰めてやる必要がある。おそらく8バイト境界に開始位置をそろえてやればいいと思うので、割り付けたメモリを細切れに使うようにしたい。JITコンパイルに使用しているXbyakはその辺も可能みたいなので、メモリ管理を自前でやるように修正する。

速度面でだんだん不満になってきているのだが(JITしてもあんまり改善していないので)、最適化をかける前にきっちり動くようにしておきたいというのもある。我慢我慢。

JIT苦戦中

正直これだけ苦労してまで入れる意味はあるのだろうかと思い始めていたりはする。他の処理系に速度で差をつけるという意味では重要なのかもしれないけど、いまいち速度も出てないし・・・

とりあえず、現状では末尾再帰が上手いこと動かない場合がある。理由もある程度分かっていて、RETが一回足りてない(もしくは多すぎる)。 ただ、いまいち解決方法が分からない。う～ん。

ネイティブ内でVMのスタックの状態を保つようにしたらべらぼうに遅くなった。一応やらないよりは速いかくらい。あまりに切ないなぁとは思いつつ。なぜスタックの状態を保つようにしたか？これはcall/ccとかdynamic-windとかのVMのスタックと(現状)切っても切れない関係の機能をなんとかするため。でも逆に言えば、JITコンパイル時にこれらの呼び出しが無ければCスタックだけ使ってもOKなんだよねぇ？と思っているので(ちょっと自信ない)、その辺は頑張れば最適化できそう。

以下はとりあえずメモ。(一応ソースのコメントにも書いてるけど、頭の中を整理する意味合いも含めて)
【X86】(以外はまだ手をつけてない)

• レジスタは通常のeax、ecx、edx以外にebx、esi、ediも使う。
• eaxは基本的にVMのacレジスタをエミュレート。
• ecxとedxは汎用的に基本的にいつでも使用可能(なはず)。
• ebxは引数で渡されてくるVMのインスタンスを保持
• esiはargc引数、ediはargs引数を保持。
• ただ、ediに関しては別の用途に使った方がいいかもしれない。現状ではあんまり効率よく使われていない。
• 書けるところはアドレスべた書き。
• GREF_CALLとか
• Scheme手続きの呼び出しにはVMのスタックを使用。
• 遅い(VMのスタックを整備する必要がある)
• フレームを入れたり出したりするのが致命的
• スタックに直接関係ない普通の手続きはVMのスタックを使わないべき。
• 組み込みインストラクション(CARとかCDRとか)がまだ手抜き実装。
• インライン展開して無い。Cの関数呼んでる。
• これは後回しでもいいだろう。

まだ、ソース上にeaxとedxべた書きなので、X64対応するまでにはもう少し抽象度を上げておきたい。(楽したいという)
なんだかランタイムさえあればアセンブラ書ける気がしてきた。(気がしてるだけ)。

JITアイデアメモ

そんなにナイーブな実装ではないとは思いたいのだが、速度が出ない。多分いたるところでVMのレジスタを参照したり書き換えたりしているからだろう。(主にスタックポインタなんだけど)
GaucheのJIT予備実験を見る限り、(多分)似たような壁にぶち当たっていると思われる。
Gauche:VMの最適化:JIT:予備実験

とりあえず、現在のところJITコンパイルには2パス使っていて、最初にVMインストラクションを舐めて最適化できそうな情報を集めてから実際にコンパイルしている。というか、これやらないとJUMP命令の飛び先が取得できないので(+方向だけなら問題ないんだけど、-方向があるので)。
この1パス目をうまく使えば、どのPUSH命令が実際にCのスタックが必要かどうかがわかる(はず)。これが分かれば、末尾呼び出しの際に、現在与えられている引数フレームを再利用可能になる。であれば、わざわざVMのスタックをいじる必要がなくなるのではないだろうか？問題はどのPUSH命令がどの位置をいじる必要があるのかということさえも引っ張り出さないといけない点ではあるのだが・・・

とりあえずfibとtak程度が5から10倍程度高速になるように頑張ってみてから実際にJITを入れるか考えよう。上記の方法だと継続をどうするとかの問題が出てくるわけだし・・・でも、Racket並みの速度を出すには必須だろうし・・・


それにしても、汎用レジスタ6本て・・・せめてもう3本あればなぁ・・・(x86の話)

JIT実装中

目指せRacketの速度ということでJITを実装中。とりあえず、X86でfibとtakが動くようにしてみた。(どうでもいいが、X86はレジスタの本数が少なすぎて辛い。やりくりを考える主婦の気分を味わえる)。

とりあえず方針として、

• Xbyakを使ってC側で実装する。
• コンパイル中に見つかったクロージャーもコンパイルして呼び出しは可能な限りネイティブにする。(これの恩恵はでかい、実装がかなり楽）
• 他の手続き呼び出し用引数フレームはVMのスタックを使う。

こんな感じでやっている。末尾再帰をどう実装しようとか(クロージャーはいいけど、問題は組み込み手続き)、スタックオーバーフローとかまったく考えてない状態ではある。

まぁ、気になるのはパフォーマンスだろう。以下のコードでベンチマークを取ってみた。

(add-load-path "sitelib")
(add-load-path "lib")
(import (sagittarius vm) (time))
(define (fib n)
  (if (<= n 2)
      1
      (+ (fib (- n 1)) (fib (- n 2)))))
(print "vm")
(time (fib 35))
(newline)
(jit-compile-closure! fib)
(print "native")
(time (fib 35))
(newline)

(define (tak x y z)
  (if (not (< y x))
      z
      (tak (tak (- x 1) y z)
           (tak (- y 1) z x)
           (tak (- z 1) x y))))
(define (run-tak count)
  (do ((i 0 (+ i 1)) 
       (r (tak 18 12 6) (tak 18 12 6)))
      ((= i count) r)))

(define count 200)
(print "vm")
(time (run-tak count))
(newline)
(jit-compile-closure! run-tak)
(print "native")
(time (run-tak count))
(newline)

JITという割りに、VMは現状では勝手にコンパイルしないので手動でコンパイル。テストだけならこの方が便利。っで、結果は以下(CoreDuo 1.6Ghz, Cygwin on Windows XP)

$ ./build/sash.exe test.scm
vm
;; (fib 35)
;;  3.093750 real    2.797000 user    0.000000 sys

native
;; (fib 35)
;;  1.875000 real    1.859000 user    0.000000 sys

vm
;; (run-tak count)
;;  2.015625 real    1.875000 user    0.000000 sys

native
;; (run-tak count)
;;  1.312500 real    1.187000 user    0.000000 sys

速くはなっているんだけど、驚くほどということも無く。なんか、頑張ればVMとコンパイラの最適化で叩きだせるんじゃね？というくらいの速度改善なのがなんとも悲しい。問答無用で5倍くらい速くなるならやる気も格段に違うんだけど・・・
ベンチマークのコードを多少修正。(Gambitベンチのと同じ回数まわすようにした)

Muiden and Pampus

Be activeの第２弾。(要はmeetupに行っただけとも言うが)、Daytripに行ってきた。
場所はAmsterdamからバスで２０分くらいのMuidenとそこから更にボートに乗って１５分くらいのところにある要塞跡地Pampus。

Muidenは古い感じのオランダの町並みを残した港町ちっくな場所。要塞跡地Pampusは元はアムステルダムに運河が開通する前に物資を経由させるための人工島だったらしい(ガイドの兄ちゃんは英語が堪能じゃなかったのでちと理解できなんだ)。

以下は写真。

旅の始まりは、アヒルの親子から(関係はない）

Pampusに行くためのボートを待つ

 船乗り場の近くにあった城。待ち時間３０分を潰すために17.50ユーロ払う気にはなれず、中には入っていない。

目的地のPampus。iPhoneのカメラでは・・・

門構え？

この辺りで僕の写真を撮ろうという情熱が尽きた(早

夕食もMuidenで食べて帰る。レストランはいいけど選ぶものがなかった感じ。

どうでもいい話。
同じ英語でもスコットランドとイングランドではアクセントが違うのだが、発声の仕方まで違うとは知らなかった。(聞いたわけではないのだが)。イングランド出身の女声はすごく鼻に息が通っていた感じ。合唱で言えばこもる声ってやつ？よく言えば響きがあるけど、芯がない感じのあれ。逆にスコットランド出身の人は通る声というか、そんな感じ。

どうでもいい話その２。
スウェーデン出身の人がいたのだが、スウェーデンをスイスと勘違いしてドイツ語を話す国だと思っていた自分。意味不明である。どっちもSWで始まるからきっとそんな勘違い(恥

どうでもいい話その３。
日本人名前は聞き取り難いらしい。きっと音が３つもあるからだろうけど。自己紹介をするたびに聞きなおされた。

BoehmGCとCMakeとMSVC

あんまりCMakeは関係ないかも。

BoehmGCをMSVC上のマルチスレッドでコンパイルしようとすると/MDオプションによって暗黙的に定義される「_DLL」というマクロを期待している。困る。という話。

事の発端はMSVCR100.dllを依存関係に入れたくないために/MTオプションを指定したのが始まり。とりあえず、コンパイルするとビルドの途中で0xc000007bといって落ちる。いろいろ調べた結果(たどり着くまでに2時間くらいかかった)、gc.dllが何もエクスポートしていないことに問題があった。
っで、gc_common_macros.hを覗いてみると、上記の「_DLL」というのが定義されていないとGC_DLLが定義されずおかしなことになる。じゃあ、面倒なので外部から「GC_DLL」を定義しちゃえってやったら、今度はBoehmGC内のテストのビルドでリンカーエラーが起きる。もうね、いたちごっこだね。

とりあえず、どうしたか。CMakeLists.txtの最終行にあるADD_SUBDIRECTORYをコメントアウト。 BoehmGCのテストなんて走らせたこと無いから問題ないだろう。信用する。
しかし、基本フルオートでビルドしてたのにMSVCのみ手を入れるのは嫌だなぁ。どうしよう。ビルド時に作り直すようにしろということか？面倒くさい・・・

逆FizzBuzz問題

逆FizzBuzz問題なるものを発見した。元ネタ５月だから遅れること２ヶ月くらいか。
逆FizzBuzz問題をTrieでトライ - athosの日記

とりあえず、Schemeで解いてみた。(#0=記法をサポートしてれば、どの処理系でも動くはず・・・)

#!/bin/env sash
(import (rnrs) (srfi :2 and-let*))

(define (inverse-fizzbuzz ls)
  (define one-cycle-count 7)
  (define inverse-fizzbuzz-list
    '#0=((fizz . 3) (buzz . 5)  (fizz . 6)
  (fizz . 9) (buzz . 10) (fizz . 12)
  (fizzbuzz . 15) . #0#))
  (define (check-input ls)
    (let* ((len (length ls)) (max-try (ceiling (/ len one-cycle-count))))
      (define (count-up s c) (if (eq? (car s) 'fizzbuzz) (+ c 1) c))
      (let loop2 ((in ls) (tmpl inverse-fizzbuzz-list)
    (r '()) (times 0)
    (matched? #f) (tried 0))
 (cond ((null? in) (reverse! r))
       ((eq? (car in) (caar tmpl))
        (loop2 (cdr in) (cdr tmpl)
        (cons (+ (cdar tmpl) (* 15 times)) r)
        (count-up (car tmpl) times)
        #t
        (count-up (car tmpl) tried)))
       ((> tried max-try) #f)
       (else (loop2 ls 
      (if matched? tmpl (cdr tmpl))
      '() 0 #f
      (count-up (car tmpl) tried)))))))
  (and-let* ((r (check-input ls)))
    (cons (car r) (last-pair r))))

(print (inverse-fizzbuzz '(fizz)))
(print (inverse-fizzbuzz '(buzz)))
(print (inverse-fizzbuzz '(fizz buzz)))
(print (inverse-fizzbuzz '(buzz fizz fizz)))
(print (inverse-fizzbuzz '(fizz fizz buzz)))
(print (inverse-fizzbuzz '(fizz buzz fizz fizzbuzz)))
(print (inverse-fizzbuzz '(fizz fizzbuzz fizz)))
(print (inverse-fizzbuzz '(fizz fizzbuzz fizz fizz)))

reverse!はSRFI-1だったかな？まぁいいか。
あんまり美しくないなぁ。最初はSRFI-41使ってパターンマッチ的に解こうかなぁとも思ったんだけど、不正なリストを渡された際にどうしようかなぁとか思ってやめた。

家事と家事の合間に解いたのにしては上出来だと思う・・・

なんとなく、REPLに色をつけてみた。

別に0.3.4固有のものでもないのだけど、なんとなくREPLの画面に色をつけてみた。
WindowsのDOS窓は無理だけど。

(import (sagittarius vm)
 (sagittarius vm debug)
 (sagittarius interactive))
(cond-expand
 ((not windows)
  ;; colouring
  (define-syntax with-color
    (lambda (x)
      (syntax-case x ()
 ((_ color expr more ...)
  ;; on emacs it's useless.
  (if (getenv "EMACS")
      #'(begin expr more ...)
      #'(dynamic-wind
     (lambda () (display color))
     (lambda () expr more ...)
     (lambda () (display "\x1b;[m"))))))))
  (define-syntax with-color-red
    (lambda (x)
      (syntax-case x ()
 ((_ expr more ...)
  #'(with-color "\x1b;[1;31m" expr more ...)))))
  (define-syntax with-bold
    (lambda (x)
      (syntax-case x ()
 ((_ expr more ...)
  #'(with-color "\x1b;[1m" expr more ...)))))
  (define (printw . args) (for-each write/ss args) (newline))
  (current-printer (lambda args
       (with-bold
        (for-each printw args))))
  (current-exception-printer
   (lambda (c)
     (define (print-stack-trace)
       (let* ((stack (get-stack-trace-object))
       ;; skip the first get-stack-trace-object itself
       ;; and print-stack-trace
       ;; the last 2 are always evel and #f so skipt it as well
       (interesting (if (null? stack) stack (cddr (reverse! (cddr stack))))))
  (unless (null? interesting)
    (print "stack trace:")
    (do ((i 0 (+ i 1))
  (stack interesting (cdr stack)))
        ((or (= i 20) (null? stack)))
      (let* ((record (car stack))
      (index (- (car record) 2))
      (proc  (caddr record))
      (tmp   (cadddr record)))
        (format #t "  [~a] ~a~%" index proc)
        (when (and tmp (not (null? tmp)))
   (let* ((src (last-pair tmp))
   (info (source-info (cdar src))))
     (display "    src: ")
     (let ((s (call-with-string-output-port
        (lambda (o)
          (write/ss (unwrap-syntax (cdar src)) o)))))
       (if (> (string-length s) 50)
    (print (substring s 0 50) " ...")
    (print s)))
     (when info
       (format #t "    ~s:~a~%" (car info) (cdr info))))))))))
     (with-color-red
      (print (describe-condition c)))
     (print-stack-trace)))
  (current-prompter (lambda () (with-color "\x1b;[32m" (display "sash> "))))
  )
 (else #f))

ソース情報とか取得できないけど、いいかという感じでは動く。ソースもとるようにした。
これだけだとつまらないので、一応0.3.4から入った機能。「.sashrc」というファイルを$HOMEに置いて上記のソースを書いておけばREPL起動時に勝手に読み込んでくれる。このファイルはREPLだけが読み込むので、スクリプトでは無駄なライブラリのロードは起きない。

Sagittarius 0.3.4リリース

Sagittarius Scheme 0.3.4がリリースされました。
今回のリリースはメンテナンスリリースです。

修正された不具合

• bytevector-***-set! (*** はs32、s64)にfixnumのマイナス値を与えるとエラーを投げる不具合が修正されました。
• (lambda ())及び(begin)が不正なクロージャを返す不具合が修正されました。現在は未定義値を返します。
• スタックサイズを超える引数をapplyするとSEGVする不具合が修正されました。
• bytevector->integerがオプショナル引数を無視する不具合が修正されました。
• (net oauth)ライブラリでエラーレポート手続きが不正な例外を投げる不具合が修正されました。
• SEFI-1ライブラリがeveryをエクスポートしていない不具合が修正されました。

新たに追加された機能

• SRFI-17 一般化されたset!がサポートされました。
• 64ビット環境でのビルドがサポートされました(Windows 7、及びUbuntu 64bitで動作確認)

改善点

• コンパイル済みキャッシュのディレクトリ構造が32ビットと64ビット混在環境を許可するように変更されました。
• SRFI-1ライブラリの多くの手続きがimproper listを与えると例外を投げるように修正されました。(SRFI-1に準拠した形になります)
• fold-right及びunfoldが末尾再帰するように書き直されました。

新たに追加されたライブラリ

• Gaucheライクなrefや変換を提供する(sagittarius object)が追加されました。
• REPL内でドキュメントを参照可能にする(sagittarius interactive support)が追加されました。
• eql specializerライブラリ(sagittarius mop eql)が追加されました。

新たに追加されたドキュメント

• (text sxml sxpath)がドキュメント化されました
• (rfc uri)がドキュメント化されました
• (util bytevector)がドキュメント化されました

マクロ、マクロ、マクロ・・・

マクロの不具合を少しでも潰していこうと思っているのだが、いろいろげんなりしてきた。

とりあえず、現状でもっとも問題になっているのは、free-identifier=?とbound-identifier=?が正しく動いていないこと。後者はあんまり気にしていないんだけど、前者がまずい。(どうでもいいけど、この2つの手続きは、手続き名から何をするのかあんまり想像できない気がする)。

free-identifier=?は(理解が間違っていなければ)、引数としてとった2つの識別子が同一のオブジェクトを指していれば#tを返す手続き。基本的にグローバルなオブジェクトなら単に名前が一緒とかで十分なんだけど、ローカルに束縛されたものの解決が現状うまくいっていない。

マクロ内で束縛した環境はとりあえず放っておいて、コンパイル時環境だけ探せばいいだろうか？とりあえずやってみることにしよう。

構造体のアライメント

X86_64な環境で構造体のアライメントが不思議な現象を起こしている気がする。
(そういえば、以前FFIをサポートした際に問題になるかも的なことを書いたような・・・)

以下のコードが予想と違う。

#include <stddef.h>
#include <stdio.h>

struct align_struct
{
  int value1;
  struct {
    int value2;
    char *str;
  } inner;
};

int main (int argc, char **argv)
{
  printf("offsetof: %d\n", offsetof(struct align_struct, inner));
  return 0;
}

結果が、32bitのCygwin(多分32bitならどれでも同じ、と信じる)では、4。これは期待通り。で、X86_64では8。これが8になられると大問題で、なぜかといえば、以下のコードはどちらの環境でも4を返すから。

#include <stddef.h>
#include <stdio.h>

struct align_struct
{
  char c;
  int  x;
};

int main (int argc, char **argv)
{
  printf("offsetof: %d\n", offsetof(struct align_struct, x));
  return 0;
}

何か勘違いしているのかもしれないのだが、FFIのサポートにlibffiを使っていて、アライメントの計算はそこにどっぷり依存している。

中身を展開してやったら期待通りの値になった。構造体のアライメントが変わってくるのかなぁ？単にフラットにしてくれれば問題ないのに。libffiをもう一回見直すか・・・

64bit environment

I have received an email that said Sagittarius build process crashed on Open SUSE 64 bit. This is the first email I've got, yes, I was really excited! And at the same time, I felt the time had come at last.

I was maybe avoiding to apply 64 bit environment, the reason why is my main environment is Cygwin and I don't know if it can be 64 bit or only 32 bit. (As far as I know, it's only for 32 bit). So I didn't have it until now. (even thought my computer at my work is 64 bit hehe).

So I installed Open SUSE 64 bit into my VM (at my work), and build version 0.3.3. Yes, it broke as I expected. It seems cache problems. So I have checked the both writing and reading cache, then I saw the problem. The cache must be read as intptr_t or word size, but it used int (on 64 bit environment this is somehow not the size of pointer). So it read something weird value and SEGV. I thought if it was just this easy, then I can send a patch. Of course it wasn't this much easy. After I fixed it and ran the test, a lot of things complaining, and one of the test caused SEGV as well.

Well, most of the failed tests were related fixnum operation which I used int instead of long. So I fixed it, but I gave up to send a patch because the procedures are generated from stub files and if I make a patch, it would be huge.

I have also noticed that on 64 bit environment, cache files are huge. How huge? It's as twice as bigger than 32 bit environment. Why? It's because the word(pointer, not a document) size, even though most of the serialized values need only 32 bit length. Hmm, I guess I need to reduce the size.

The next release 0.3.4 should be run on 64 bit. (I still need to fix some bugs, though...)

3,2,1,0 バグッてハニー

コンパイラに少し手を入れたらなんだかSEGVが起きるようになった。
まぁ、普通はいじった部分がおかしいだろうということになるのだが、どうも様子がおかしい。

Cygwinではいまいちなにが起こっているのかわからなかったのでUbuntuで走らせてみてなんとなく見えてきた。(CygwinだとSEGVが起きてもSEGVだと知らせなかったり、意味不明に突然死ぬので)。

とりあえず、再現する方法と、回避できる方法がある。
再現する方法は非常に簡単で、make testをマルチスレッドバージョン(デフォルト)で２回走らせること。２回目はキャッシュを使うのだが、キャッシュを使うとなぜかアウト。
回避するには、test/tests.scmに手を入れてテストをマルチスレッドで行わないこと。こうするとなぜかコンパイルされたキャッシュが正しく作られるっぽい。(複数回走らせてもOKな上に、マルチスレッドで走らせてもOKになる)。

正直意味不明ではあるのだが、とりあえず仮説を立てる。マルチスレッドにしなければ動くということは、コンパイル結果自体には問題はなくて、(実際、キャッシュ読み込みで死んでるわけだし)、キャッシュ作成時に問題が起きている、はず。
ぱっと考え付いたのは以下の３点。

• コンパイラをいじったために速度が改善されて今まであまり起きなかったロック取得部分の競合でおかしくなった。
• コンパイル時間が増大したためロック取得で競合が起きるようになった。
• コンパイルをいじったためGCのタイミングが変わり、今までは起きなかったメモリエラーが起きるようになった。

ロック周りが問題になっているなら、多分２番目・・・。ただ、起きているライブラリはテストケース内では１ファイルででしか使われていないので、読み書きは同一のスレッドで行われているはず。
３つ目はありえそうで、実際つい最近８要素いるはずの配列が７要素しかメモリを割り付けてなかったというのを発見した。同様のことが起きてて、シングルなら回収されないけどマルチだと回収されちゃったっていうのはあるかも。
さて、どうしたものか・・・

解決した。

英語というより国語の問題だろうこれ？

世の中頭のいい奴はいるもんだ、ということを実感できるスレ。
東大の入試問題すごすぎワロタｗｗｗｗｗｗｗｗｗｗ

っで、上記のスレで紹介されていた問題回答速報が以下。
東京大学解答速報

この前期外国語の最初の問題。非常に平易な英語で書かれていて読むのは全然苦労しない。英語自体も非常に分かりやすく書かれていて(個人的に平易と分かりやすいのは違うと思っている)、それこそ単語が分かれば中学生でも読める。問題は、どう考えても日本語で500文字くらい(原稿用紙1枚くらいはありそう)のものを5分の1の100文字以下にするって、国語の問題じゃね？

解答例見たんだけど、なんか概要というか、序文というか、なんか2つあるパラグラフの最初の1文をまとめましたって感じ。この手の要約ってすごく苦手(物事の本質を捉えられないとも言う)なのと、英文自体が例も踏まえて簡潔に書かれているので、合格した人たちはすごく本質に迫れる人なんだろうなぁと少しうらやましく思ってしまった。

他の問題は見てない。

一方で京大の英訳問題は、日本語が難しくて無理。文学表現の英語なんて知らん。さすが２大天才大学や・・・

REPL support

Before when I forgot the signature of procedures, I always search the internet (usually these procedures were defined in R6RS). However Sagittarius has a document which contains R6RS procedures as well. Why didn't I use it? It's because searching the internet was usually faster than open the document HTML and look it up.

And now, I thought this is inconvenient. (It was!). So I made a library called (sagittarius interactive support) which provides a macro 'document'. This macro look up given name from the document. For this purpose, from 0.3.4 document will be located in the install path.

Then I have also noticed, it was really pain in the ass to type '(import (sagittarius interactive support)' each time when I run the REPL. So I added initialisation file '.sashrc' loading to REPL. REPL will search the file from either $HOME or $USERPROFILE and if it found, then load the contents to the REPL environment.

Now it's a bit more convenient.

(lambda ())

What should this expression return?

According R6RS and R7RS (draft 6), lambda form must have at least one expression. So I guess this must be syntax error. (I could not find explicit sentence said raise an error, neither R6RS nor R7RS draft).

So, I checked some implementations, Gauche, Ypsilon, mosh, chibi-scheme, guile and Sagittarius.

The implementations raised syntax error: mosh, chibi-scheme, guile.
I guess these are strict for syntax.

Gauche returned a procedure which returns 0 or unspecified value, depending on how you defined.

Ypsilon returned a procedure which returns unspecified value.

The funniest behaviour was actually mine. It returned procedure which returns itself. This expression was valid;

(define (test))
(((test)))
;; #<closure test>

But don't try this expression, it will abort with out of memory;

(((lambda ())))
;; abort or never return

I guess this must be either syntax error or returning unspecified value.

Githubのアカウントを作ってみた

Mercurialに慣れていて、Gitは構ったこと無かったんだけど、Googleコードですごく小さなリポジトリを作るのに気が退けてなんとなくGithub。

Githubはチュートリアル充実してるなぁというイメージだった。Googleコードはどうだったかなぁ？難しくは無かった記憶だけど、Mercurial自体の使い方は自力で調べた気がする。

とりあえず、Twitter用のAPIライブラリをどこかに置きたかったので作っただけ。気が向いたら使ってやってください。
Sagittarius-net-twitter

そういえば、作るつもりないってどこかで言ったような気がする。2ヶ月くらい前に・・・あの時は本当に無かったんだ。

正規表現

#/(?:aa?){n}a{n}/という正規表現(nは任意の数)がどれくらい遅くなるかをチェックしようとしたら正規表現のコンパイラがエラーを飛ばした。ソースを見ると特にコメントも無く、

/* ugh, ugly */

とだけある。(よくこういうのを書く。)問題はこう書いてあるということは何らかの問題があってそうせざるを得なかったはずなのだが、思い出せない。とりあえず、必要そうに見えないのでコメントアウトしてコンパイル。テストも全部通る。なんだったんだろう？問題が見つかったら考えることにしよう。こういうことが多々あるのだから、コメントは都度書くようにしないとなぁ。やっつけで直してコメント書かないことが多いから・・・(仕事ではそれを反面教師にしているのかまじめに書いてる)

っで、件の速度チェック。 ここを見て、Sagittariusではどうなるんだろう？と実験してみたかった。
これどうやってたんだっけな (正規表現・続々) - Island Life
見た感じO(n)の正規表現エンジンの方が使われるはずだからSagittariusではO(n^2)にはならないはずだけど、と思いつつ以下のコードで実験。

#< (sagittarius regex) >
(import (rnrs) (sagittarius regex) (srfi :42) (time)
 (sagittarius control))
;;(use srfi-42)
(define s (apply string (list-ec (: x 100) #\a)))
(print ((#/(?:aa?){40}a{40}/ s) 0))
(time
 (dotimes (i 100)
   (#/(?:aa?){40}a{40}/ s)))

いい加減、毎回正規表現のリーダーマクロを有効にするのが面倒だが、ライブラリをインポートしないと正規表現自体使えないからなぁ・・・
っで以下が結果。

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

;;  0.125000 real    0.125000 user    0.000000 sys

普通。単発で走らせた結果が、0.014くらいだったのでリニアだろう。単純な正規表現ならO(n)が保障されているのはそれなりに強みだろう。(エンジン自体が遅いので、微妙だけど・・・)

Lisp

声優ユニットではない。(違ったっけ？名前だけで見たことないから)

ふと昨日のレーベンシュタイン距離の実装でScheme(というかSagittarius)では速度が出ないので、バイナリ吐けるSBCLで書き直した時に思ったこと。(そのうちLisp版のコードも貼り付けよう。汚いけど)

Lispという言葉を知ったのは大学3年の研究室配属の際に教官の一人がLispを使った何かの研究をしていたというのが最初だろうか。ちょっと調べて括弧だらけな上に、リストとか繋げてなにが出来るんだよこれ？みたいな感想しかない上に、研究内容も面白くなさそうだから別の研究室に行った。
っで、配属された研究室の教官がemacs使いでWindows版emacsとしてxyzzyを使っていた。xyzzyはまぁ、有名なCommon Lisp版emacsでもちろん拡張Lisp入れまくりになった。その際に自分でも書けたら便利じゃね？とか思って中身を見たけど、書ける気がしなくて挫折した記憶がある。
それからもずっとxyzzyを使ってはいたけど、時は流れて2009年某BlogでSICPなるものを知りオランダに来たばかりで職探しに困難を極めていたのでスキルアップも兼ねてSchemeをさわり始めた。Javaの仕事探してるのにSchemeなんてというのもあったが、基本的なアルゴリズムとかはなにやっても一緒だと思っていた。
っで、なにを思ったのか自分の処理系を作り始めた。これは職が見つかってから。ずいぶんSchemeにも慣れて仕事で使うスクリプトをSchemeで書きたいと思ったけど、既存の処理系には暗号関係のライブラリがあんまりなかったので(今思えばRacketとかChickenにはあったかも)、じゃあ作るかと思い立ったのが最初。もちろん、思い立ったらできるわけはなく、実際に鍵が作れるとか、X.509の証明書が読めるとかまで3年かかっている。今思えばGaucheで拡張ライブラリ書いた方がよかった気もするが、まぁいいか。

っで、ついこの間SBCLと速度勝負をした際に、ほぼ初めてCommon Lispのソースを書いた気がする。(もちろん読むということはしていた)。今まで、「なんでもありのCLに手を出したら、Schemeが窮屈に感じるかもしれない」と思って敬遠していた。必死になってCで書いたコードでたたき出した速度をLispであっさり実現できるというのは正直かなりショックだった。ただ、速度が欲しい処理にはLispで書けばいいかと思えるようになった。もちろん、そんな処理に出会うことなどほとんどないだろうと思っていた。
と思っていたんだけど、昨日のレーベンシュタイン距離である。ちょっとバイナリ吐けないと厳しいなぁと思いSBCLで書いてみた。 単にSchemeからCLへの移植なのだが、同じ機能でもCLの方がいろんなものが標準で揃っている分書きやすいなぁという印象だった。マクロとか、パッケージとか込み入ったものは全然使っていないので、実際はそうでもないのかもしれないが。(loopマクロとかずるいよね。手続き型言語的な感覚で書ける。)

Lisperになる(なれる？)気はあんまりしないんだけど、選択肢が増えるのはいいことだと思う。と自分に言い聞かせる。

追記：
nilが'()であり#fであるというのは結構便利だと思った。デザイン的には首をかしげるところだけど、実用的には便利。

レーベンシュタイン距離

某求職掲示板で見つけたパズル。あわよくば答えつけて応募してやろうと思ったのだが、かなりハードルが高い。

問題はレーベンシュタイン距離が1の単語のネットワークを計算するというもの。レーベンシュタイン距離自体を求める処理は以下のように書ける。

(define (levenshtein-distance word1 word2)
  (define (table-ref t i j)
    (vector-ref (vector-ref t i) j))
  (define (table-set! t i j v)
    (vector-set! (vector-ref t i) j v))

  (define (make-table word1 word2)
    (let1 table (make-vector (+ (string-length word1) 1) 0)
      (dotimes (i (+ (string-length word1) 1))
 (vector-set! table i (make-vector (+ (string-length word2) 1) 0)))
      (dotimes (i (string-length word1))
 (table-set! table (+ i 1) 0 (+ i 1)))
      (dotimes (i (string-length word2))
 (table-set! table 0 (+ i 1) (+ i 1)))
      table))

  (let ((d (make-table word1 word2))
 (word1-size (string-length word1))
 (word2-size (string-length word2)))
    (dotimes (i word1-size)
      (dotimes (j word2-size)
 (if (char=? (string-ref word1 i) (string-ref word2 j))
     (table-set! d (+ i 1) (+ j 1) (table-ref d i j))
     (table-set! d (+ i 1) (+ j 1)
   (min (+ (table-ref d i (+ j 1)) 1)
        (+ (table-ref d (+ i 1) j) 1)
        (+ (table-ref d i j) 1))))))
    (table-ref d word1-size word2-size)))

普通にWikipediaに載っていたものをSchemeで書き直しただけ。メモリのアロケーションを気にして2次元配列を1次元で表現したバージョンも作ったんだけど、Sagittariusでは普通に書いた方がわずかに速かったので却下した。なんでだろう？

レーベンシュタイン距離を求めるアルゴリズムはO(mn)で、距離が1の物を自前で見つけるよりは速いと思うんだけど、問題なのはネットワークを構成するのに使用される単語リストが26万くらいあること。とりあえず与えられた単語をリストから順番に見ていくようにしたのだが、世代が4を超えた辺りで計算オーダーがとんでもないことになるっぽく、ちょっと現実的な時間で帰って来ない。(10分とかでは無理)。

根本的にO(n^m)になるような気がするのだけど、(nが単語リストでmが与えられた単語)、これに更に世代が入ってくるとげんなりするよなぁ。第一世代のmは一個だけど、二世代目以降は複数になるわけだし。なんか、別な方法があるのだろうか？

apply argument limit

It was yesterday evening I was considering that values might have to be implemented not to allocate any memory such as mosh or Gauche. (well, currently values returns first class object named values too).

Then I wrote test code like this;

(import (rnrs) (srfi :42))
(apply values (list-ec (: x 150000) (* x x)))

Well, it just applies a list contains 150000 elements to values. I don't know why I put such a huge number but it revealed a bug in Sagittarius. (could be mosh as well).

The problem is really simple. Sagittarius' compiler compiles apply procedure as a builtin instruction APPLY. This instruction pushes given arguments to stack, however it does not check whether or not stack overflows and current maximum stack size is 10000.Yes, it breaks something I don't want to.

The solution can be 2 ways. The easiest way is check arguments count and if it's more than maximum then raises an error. The not so easy way is change the behaviour of APPLY a bit.

The first one is a bit awkward even if nobody applies such huge number of arguments. So I will do the latter one.

I don't know when I can say it's stable...

(net twitter)

なんてライブラリを作成中。(というか、あとドキュメントだけ)。これだけ特異化されているライブラリを処理系本体に入れるつもりは全然なくて、別パッケージにする予定。(そのために突貫で作ったものがあるし)

一応XMLとJSON両方サポートしてるけど、JSONの方を使う気がしない。というか、自分では仕事してる振りしながらコマンドラインで呟くくらいしかしなさそう・・・

肝になる部分ってOAuthなのでひたすらTwitterのAPI見て実装するだけという結構疲れる作業であった。

しかし、今更感が拭えないなぁ。まぁ、いいか。

Sagittarius 0.3.3 リリース

Sagittarius Scheme 0.3.3がリリースされました。
今回のリリースはメンテナンスリリースです。

修正された不具合

• sjis、euc-jpコーデックがASCIIコードを認識できない不具合が修正されました。
• string portによる改行コードの読み取り不具合が修正されました。
• stringを扱う手続きが'\0'をうまく読み取らない不具合が修正されました。
• Unicode周りの不具合が大幅に修正されました。
• bytevector->string系の手続きがEOLにLFを使っていた不具合が修正されました。
• Transcoder周りの不具合が修正されました。
• string->symbolが特定の場面においておかしなシンボルを返す不具合が修正されました。
• リテラルリストが変更可能な不具合が修正されました。
• (srfi :14 char-set)ライブラリにunbound variableが含まれている不具合が修正されました。
• PKCS EMSAエンコード及びMGF-1手続きの実装が間違っていたのが修正されました。
• csv-readが複数コメント行を読み取れない不具合が修正されました。

新たに追加された機能

• object-applyが追加されました。
• pointer-c-ref-pointer及び、decrefが(sagittarius ffi)に追加されました。
• OAuthライブラリにサービスプロバイダ機能が追加されました。
• 正規表現ライブラリに便利なマクロが追加されました。
• unwind-protectが(sagittarius control)に追加されました。

改善点

• map、for-each、fold-left及びfold-rightが末尾再帰になるよう実装しなおされました。
• (clos user)ライブラリで提供されているマクロがsyntax-caseで実装しなおされました。
• bytevector->integer及びinteger->bytevectorの性能が改善されました。
• out-of-treeビルドが可能になりました。

新たに追加されたライブラリ

• (www cgi)ライブラリが追加されました。
• (www fastcgi)ライブラリが追加されました。
• (text html-lite)ライブラリが追加されました。
• (text tree)ライブラリが追加されました。

新たに追加されたドキュメント

• (rfc :5322)ライブラリがドキュメント化されました。
• (rfc base64)ライブラリがドキュメント化されました。
• (rfc quoted-printable)ライブラリがドキュメント化されました。
• (packrat)ライブラリがドキュメント化されました。
• (json)ライブラリがドキュメント化されました。
• (text csv)ライブラリがドキュメント化されました。 

ダウンロードページ

Sagittarius vs SBCL その２

さすがにワード単位での比較(というか、機能が違うものの比較)はおかしいだろうと思い、SBCL限定で動くbytevector->integerをまじめに実装してみた。以下がコード。

(defun u64vector->integer (bvec)
  (declare (optimize (safety 0) (speed 3) (debug 0)))
  (let* ((len (length bvec))
  (ans (sb-bignum:%allocate-bignum len)))
    (loop :for e :of-type (unsigned-byte 64) :across bvec
          :for i :of-type fixnum :from 0
          :do (sb-bignum:%bignum-set ans (- len i 1) e))
    ans))

(defvar u64 (make-array 25 :initial-contents
   (loop :for i :of-type fixnum :from 0 :to 24 :collect i)))
(time (dotimes (i 100000)
 (u64vector->integer u64)))

(defvar *sbcl-bignum-element-size* 8)

(defun bytevector->integer (bvec)
  (declare (optimize (safety 0) (speed 3) (debug 0)))
  (let* ((len (length bvec))
  (bignum-size (ceiling (/ len *sbcl-bignum-element-size*)))
  (ans (sb-bignum:%allocate-bignum bignum-size)))
    (loop :for i :of-type fixnum :from 0 :to bignum-size
   :do (let ((e 0)
      (pos (- len 1 (* i *sbcl-bignum-element-size*))))
  ;; FIXME the size must be calculated by element size
  (declare (type (unsigned-byte 64) e))
  (loop :for j :of-type fixnum :from 0 :to *sbcl-bignum-element-size*
        :do (unless (< (- pos j) 0)
       (setf e (+ e (ash (aref bvec (- pos j))
           (ash j 3))))))
  (sb-bignum:%bignum-set ans i e)))
    ans))

(defvar bv (make-array 100 :initial-contents
         (loop :for i :of-type fixnum :from 0 :to 99 :collect i)))
(time (dotimes (i 100000)
 (bytevector->integer bv)))

基本的にはSagittariusで実装しているやり方と一緒。(もっとうまいやり方があれば教えてください。)
オリジナルも動作がおかしかったので多少修正。(Bignumに入れる順番が逆だった)。
Sagittariusのベンチマークは以前と一緒。環境はUbuntu (Virtual BOX)。バージョンは忘れた。確認方法も忘れたorz
っで、結果：

~/build$ sbcl --script bv-int.lisp
Evaluation took:
  0.023 seconds of real time
  0.024001 seconds of total run time (0.024001 user, 0.000000 system)
  104.35% CPU
  76,849,374 processor cycles
  10,399,624 bytes consed
  
Evaluation took:
  0.595 seconds of real time
  0.596037 seconds of total run time (0.596037 user, 0.000000 system)
  [ Run times consist of 0.004 seconds GC time, and 0.593 seconds non-GC time. ]
  100.17% CPU
  1,935,858,048 processor cycles
  304,000,848 bytes consed
  
~/build$ sash bv-int.scm 

;;  0.034603 real    0.032002 user    0.000000 sys

あ、確かにSBCLのbytevector->integerの方が10倍遅い。多分、ashがまずいんじゃないかな、と勝手に推測。bvecがfixnumのベクタだと宣言できて、ashの結果がbignumにならないことが宣言できればもう少し速くなる気がするけど、そこまでは面倒なのでやらない。
同じ機能がSBCLより速かったという事実だけで十分です。

タイトルが「vc」になっていたので修正。

Sagittarius vs SBCL

My ubuntu does not have Japanese input environment, so I need to write it in English. I need to install something later but that's not the topic for now.

The previous topic I mentioned SBCL implementation of bytevector->integer and it said Sagittarius was faster then SBCL. And I thought it was because of the machine spec that I took the improvement benchmark. So now, my question is 'Is Sagittarius really faster than SBCL?'

Conclusion first, SBCL was faster. Then how much faster is it?
The benchmark result is this.

~/projects/build$ sbcl --script test.lisp 
Evaluation took:
  0.036 seconds of real time
  0.036003 seconds of total run time (0.032002 user, 0.004001 system)
  100.00% CPU
  105,786,338 processor cycles
  5,600,520 bytes consed
  
~/projects/build$ sash test.scm 

;;  0.075894 real    0.072005 user    0.004000 sys

The used code is the same as my bytevector->integer topic and the one on gist. (So it was actually not the same data and might be a bit advantaged for SBCL. Because compiler can optimise the embedded array.)

OK, here comes my  excuse. The CL one is not actually for bytevector but for u64 vector. The author told me, vector access for word size is faster than octet size, so u64 size is the fastest code and other must have one or more loops to construct bignum. And he also told me, if he add one more loop, it became 10 times slower (I tried but my CL skill was not good enough to implement it).

On the other hand, Sagittarius does construct bignum from bytevector so that it has nested loops inside. If the author was correct, then Sagittarius is faster than SBCL. Well, I know this is just dreaming...


Could someone provide the code? I want to test.
I tested with my own implementation of bytevector->integer on SBCL and Sagittarius was actually 10 times faster. For more details, see this page (in Japanese)

integer->bytevector

前回の手続きの逆である。折角bytevector->integerを高速化したんだし、逆もベンチマークとって見るかとやってみた。以下がコード。

(import (time) (sagittarius control))
(define bv (do ((i 0 (+ i 1)) (bv (make-bytevector 100 0)))
        ((= i 100) bv)
      (bytevector-u8-set! bv i i)))
(define n (bytevector->integer bv))
(define count 100000)
(time (dotimes (i count)
 (integer->bytevector n)))

っで、結果：

$ sash test.scm

;;  5.609375 real    5.515000 user    0.016000 sys
#|
Core Duo 1.66GHz
|#

もちろん、前回と同じ理由で遅い。ということで、Fixnumの場合とBignumの場合で分ける。
どこまでいってもポイントとしては無駄なアロケーションを避けるという点と、直接Bignumの演算をするのではなく、構成しているlongの値だけで計算するというもの。これで、Cのプリミティブなビット演算だけで片付く。
っで、結果：

$ ./build/sash.exe test.scm

;;  0.156250 real    0.156000 user    0.000000 sys

環境はもちろん一緒。50倍くらい速い。とはいっても、この辺りの処理は単発で使われることの方が多いので、ベンチマーク用ともいえる。

CLで、bytevector->integerみたいなのを作ってみたけど、こんなに速くできない。 fixnumの範囲で計算して、後で合体ってのが一番速いだろうか: 時の羅針盤＠blog: bytevector->integer 【 compassoftime.blogspot.jp/2012/06/byteve… 】
— ⠗⠐⠥ ⠵⠱⠊⠷さん (@g000001) 6月 14, 2012

これを見て調子の乗ってやった。反省はしていない。

bytevector->integer

かなりの頻度でこの手続きを使うなぁと思い、適当にパフォーマンスを計測。
100バイトのbytevectorを100000回ほど変換してみた。

コード：

(import (time) (sagittarius control))
(define bv (do ((i 0 (+ i 1)) (bv (make-bytevector 100 0)))
        ((= i 100) bv)
      (bytevector-u8-set! bv i i)))
(define count 100000)
(time (dotimes (i count)
 (bytevector->integer bv)))

結果。

% sash test1.scm

;;  3.245882 real    4.336000 user    0.453000 sys

高速ではないね。現状の実装では、与えられたbytevectorを地味にビットシフトして足しているので、値がbignumになると余計なアロケーションが走る。せっかくC側で実装しているのだし、ちょっと最適化。
与えられたbytevectorのサイズを見ればfixnumの範囲なのか、bignumが必要なのかは分かる。また、どれだけのサイズのbignumが必要なのかも分かる。ということで、その辺を考慮してゴリゴリと書き換えた。
結果として、メモリのアロケーションはbignum作成時のみの最大1回に抑えられている。どれほどパフォーマンスに影響を与えるか試してみた。コードは同じもの。
結果。

% ./build/sash test1.scm

;;  0.027005 real    0.015000 user    0.000000 sys

圧倒的じゃないか、わが軍は。(違ったっけ？)

これでcrypto周りのスピードが改善される(はず)。

必要に駆られて

Sagittariusに拡張ライブラリをインストール可能にしようという話。
なんとなく必要に駆られてきたのでそれっぽいのを作った。Gaucheのgauche-packageに似せたけど機能はしょぼしょぼ、インストールとかはCMakeまかせというやる気の無い仕様。

Twitterに呟くのとかを別プロジェクトにして、どこかに置きたいという理由だけ。

作ってる最中に間違って/usr/local/shareを消してしまい(Cygwin上)、(util file)が(math)に依存しているという致命的な不具合を見つけた。(ビルド時に動的にコードを生成しているので、作成されていないライブラリに依存するとビルドがこける)。この辺のライブラリ依存関係をいい加減何とかしないとなぁ。

とりあえず、0.3.3に入る予定。多分明文化はしばらくしない。

JScript sucks!

I have been working for 2 days for IE specific bug. And I could not even reproduce it on my usual environment such as IE8 or IE9 on Windows 7 or Windows XP. The platform I could only see it was Windows Server 2003 with IE 8.

Until now, I still couldn't figure out how I can solve it and couldn't find any article about this bug either. So let me memorise what happened and what was different between working environment and incorrect environment.

Before starting explanation, let me describe the background environment. We are using Wicket on the server and some process requires AjaxRequestTarget which is created Wicket's internal request cycle depending on the browsers request of course. And the problem was somehow browser did not request with AJAX but usual GET request in this case just click the link.

The problem seemed javascript did not work properly on 'A' tag's 'onclick attribute. It did not report any error but just processed 'href' value instead of 'onclick' javascript. First I thought this is IE8 specific bug if 'A' tag has both 'href' and 'onclick' then it process both and 'href' will be the latter so that browser send non AJAX request to server and die.

As I already mentioned the usual client environments work very fine, but on Windows Server 2003. So I made the test environment and tried to debug with IE8's ugly javascript debugger. First I added following code to 'onclick' attribute; 'alert(this)'. Then it suddenly raised error said 'JScript runtime error: Object required'. And from there if I delete the line it also raised error unless I refresh the page. So it seemed 'this' object was incorrect. However it is just 'A' tag itself how could it be wrong? (NOTE: we are using JQuery and in onclick $('') function was called.)

Now, at least I have one hint, alert message I added to the attribute. It said 'javascript:void(0)' means the same value as 'href' had. I'm not JScript expert but as far as I know usual IE showed 'Object' or something not 'href's value. This looked really weird to me. So I check the JScript engine's version both working and non working environment. Yes, the version was not the same. On working environment which is using IE 9 had version 5.8.16982 however non working environment had 5.8.23141! I have no idea if this is specific version for Windows Servers but smelled crappy as hell.

So I copied jscript.dll from server to XP on VM and see what happened. Unfortunately it wasn't the case. Not the version different of JScript engine but platform dependency? I'm stuck. So we concluded don't use Windows Server as a client.

If you know what is wrong and how we can solve it, PLEASE let me know.

rotate left

さすがに落ちたかな、ちと課題が難しかった・・・

電話とネットコードシェアみたいなサービスをつかったインタビューを受けていた。課題はメモリアロケーションをしないリストの回転。いろいろ考えて大分力尽きた感じであった。さすがに残念である。

っで、 そのまま放っておくのももったいないと思い、調べてみたりした。
std::rotate を読んでみた - d.v.d
C++のSTLにはそのようなアルゴリズムがあるらしく、上記のサイトに解説があった。ということでSchemeで写経。swap部分は適当。

(define (rotete-left vec m)
  (define (itr s m e)
    (if (or (= s m) (= e m))
 vec
 (let loop ((s s) (mm m))
   (if (or (= s m) (= mm e))
       (if (= s m)
    (itr s mm e)
    (itr s m e))
       (let ((v1 (vector-ref vec s))
      (v2 (vector-ref vec mm)))
  (vector-set! vec s v2)
  (vector-set! vec mm v1)
  (loop (+ s 1) (+ mm 1)))))))
  (let ((len (vector-length vec)))
    (itr 0 m len)))

なにをやっているか分かるし、知っていれば直ぐに解けるんだろうなぁとは思うけど、正直知らなきゃ無理って感じのものだ。特に30分とかで解けるようなものではないと信じたい。凡才では閃かないよこんなの・・・
入れ替え、入れ替えでいけるよなぁとか考えてたけど違う路線で考えていた。基本的なアルゴリズムの知識が足りない。

あきら～めまっしょお～、あきらめまっしょお～♪

DONT_ADD_BYTE_AT_END

Yes, it's GC again. For some reason, GC_size did not return proper (means I wanted) value for pair pointer. It always returns 16 bytes instead of 8. I needed to figure it out why?

So I started to read Boehm GC's source code again. GC_size just returns header's size and the size is defined before allocation. So it must be in GC_init. (Well, it wasn't this easy to find out, first I needed to know how gran size came and so on...). In GC_init, there was a function named GC_init_size_map, ah, this is it.

So I stepped into the function and figured it out what's going on. Well, it's just calculating the gran size with extra byte. Now I have got other problem, how can I remove this without rebuilding gc library? GC_set_all_interior_pointer causes other problem. So far, I can't see any solution. Hmm...

How to use FastCGI on Apache2 on Cygwin

I wanted to run FastCGI on Cygwin Apache2 server and I could not find specific article for it. If there is no documentation, then I would be the first one;)

So, the first step is downloading mod_fcgi from http://httpd.apache.org/mod_fcgid/. You can easily find the source code form the link 'your local mirror'.

Then next step is compiling and installing. I believe this step is the most difficult step to find a clue. Well, just the linker problem actually. The following command you need to run. And make sure you have all related Cygwin modules, such as libapr-1 and libuuid-devel.

$ APXS=/usr/sbin/apxs2 ./configure.apxs
$ make LDFLAGS="-lapr-1 -laprutil-1 -lhttpd"
$ make install

The point is LDFLAGS. Somehow created Makefile does not contain the necessary libraries.

Now, it's time to configure the httpd.conf.
Add this line after your final line of LoadModule

LoadModule fcgid_module lib/apache2/mod_fcgid.so

And put a file end with .conf extension in conf.d directory. Then add this configuration in the file.

<Directory /home/*/public_html/fcgi-bin/>
  SetHandler fcgid-script
  Options +ExecCGI
</Directory>

I assume you are using the userdir_module.

When you finish it, then run Apache2. Before run it, make sure your cygserver is running otherwise Cygwin complains.

$ /usr/sbin/cygserver &
$ CYGWIN=server /usr/sbin/apachectl2 start

OK, let's test. Put this script into the directory 'fcgi-bin' in your public_html directory named hello.cgi.

#!/usr/bin/perl
use CGI::Fast;

while (my $q = CGI::Fast->new) {
  print("Content-Type: text/plain\n\n");
  foreach $var (sort(keys(%ENV))) {
    $val = $ENV{$var};
    $val =~ s|\n|\\n|g;
    $val =~ s|"|\\"|g;
    print "${var}=\"${val}\"\n";
  }
}

Make sure you have FCGI module in your platform. Then access http://locahost/~username/fcgi-bin/hello.cgi
You can see the environment variables if it successfully installed. Enjoy.

CLOSのqualifierで遊んでみる

前にも書いたような気がするが、まぁいいか。

とりあえず、組み込みのprint関数の呼び出し前に与えられた引数をエラーポートに出力したいとする。ここではprintにしたけど、別に何でもいい。
そうすると、こう書ける。

(import (rnrs) (clos user))

(define org:print print)

(define-method print objs
  (apply org:print objs))

(define-method print ((num <integer>) . args)
  (format #t "~b" num)
  (apply print args))

(define-method print :before args
  (display args (current-error-port)) (newline (current-error-port)))

(print 1 2 3)
#|
(1 2 3) ;; これらがエラーポートに出力された引数
(2 3)   ;; printが呼ばれた回数だけ:beforeが呼ばれている
(3)
()      ;; もちろん'()もある
11011
|#

ついでに、先頭の引数が数字だったら2進数で出力するようにしてある。意味はない。オリジナルの名前を変えているのはqualifierがどのパターンでも適用されるようにするため。単にオリジナルと同じ引数を取る総称関数がほしいだけともいう。

なにが嬉しいか？Aspect指向的なことが簡単に出来そう。(多分前にも書いたな)。とりあえずこれを使って何か出来ないか考えたい。問題は、通常の呼び出しに比べて遅いことか・・・

Transcoderがバッファを持つとこうなる

BOM関連のバグを直していて気づいた。Transcoderは状態もバッファも持ってはいけないということに。
以下が端的な不具合再現コード。

(import (rnrs))
(define tr (make-transcoder (utf-16-codec)))
(call-with-port 
 (open-file-input-port "utf16file.txt" (file-options) 'block tr)
 (lambda (in)
   (display (get-char in))(display (lookahead-char in)) (newline)))
(call-with-port 
 (open-file-input-port "utf16file2.txt" (file-options) 'block tr)
 (lambda (in)
   (display (get-char in))(display (lookahead-char in)) (newline)))

ファイルはUTF-16である必要は無いんだけど、このコードで、2つ目のcall-with-portは変な値を返す。なぜか、Transcoderが最初にlookahead-charで読んだ文字をバッファに溜め込んでいるので、2度目はバッファから返してくる。すると、2度目のlookahead-charのBOMチェックになって、ごにょごにょ。(詳しく理解してないorz)
コードを修正、最初にBOMチェックをさせてからバッファに溜め込まないと意味がない。

Transcoderはあくまで単なるプロセスでないとまずいはずので、 バッファ自体はポートが持つべきである。直す。

Moshにパッチを送った。

Moshにバグレポートしたら「時間が無いからパッチを送って」みたいなニュアンスでコメントが付いたので送ったった。僕も誰かからパッチを送ってほしいよ。こっちは開発人員一人だっつ～の！

っで、よく考えてみたらパッチの作り方とか全然知らないので、どうするのか調べてみた。以下のサイトが非常に分かりやすかった。(というか、まんま使い方)
パッチの作り方と当て方はこうするもんね - 檜山正幸のキマイラ飼育記

当てたパッチは、MoshのIssue 232にまるっと貼り付けた。githubのアカウントなんて持ってないし・・・賞味時間半の大作業であったｗ
しかし、MoshはCygwin上でテスト走らせると結構こける。これは僕のパッチが問題ではなく、もともとこけるみたい。 test/print.scmのテストは0.2.7では2テストこけて、そこでmake checkが終了する。メインのターゲットではないのだろうが、もう少しCygwinユーザをいたわってほしいものだ。

運がよければパッチが採用されて、いつリリースされるか分からない0.2.8でBOM周りのチェックが改善されているはず。
Sagittariusの初期の頃いろいろコードを参考にさせてもらったので、まぁ恩返し。

Unicode変換処理の実行時間差

Larcenyのベンチマークにbv2stringという処理がある。名前の通りバイトベクターからストリングに変換する処理である。普通の処理と違うのは、これがあほかというくらい繰り返す点であろう。最近Transcoder周りを改善したのでちょっとチャレンジしてみた。

っで、標題の件である。この処理については意外なことにYpsilonが苦手としている。逆にSagittariusはかなり高速に処理をする。(moshはもっと速いんだけど、出てくる結果が不正確)。以下はbv2stringの中から抜粋して上記3つの処理系で速度を計ってみた結果。

(import (rnrs) (rnrs mutable-strings))

(define (test-char-range name lo hi tostring tobytevector)
  (let* ((n (+ 1 (- hi lo)))
  (s (make-string n))
  (replacement-character (integer->char #xfffd)))
    (do ((i lo (+ i 1)))
 ((> i hi))
      (let ((c (if (or (<= 0 i #xd7ff)
         (<= #xe000 i #x10ffff))
     (integer->char i)
     replacement-character)))
 (string-set! s (- i lo) c)))
    (string=? (tostring (tobytevector s)) s)))

(define (test-exhaustively name tostring tobytevector)
  (test-char-range name #x10000 #x1ffff tostring tobytevector))
(test-exhaustively "UTF-8" utf8->string string->utf8)
(test-exhaustively "UTF-16"
     (lambda (bv) (utf16->string bv 'big))
     string->utf16)
(test-exhaustively "UTF-32"
     (lambda (bv) (utf32->string bv 'big))
     string->utf32)

$ time sash test.scm
sash test.scm  0.73s user 0.12s system 94% cpu 0.906 total

$ time mosh test.scm
GC Warning: Repeated allocation of very large block (appr. size 524288):
        May lead to memory leak and poor performance.
mosh test.scm  0.52s user 0.12s system 97% cpu 0.656 total

$ time Ypsilon test.scm
Ypsilon test.scm  0.01s user 0.06s system 0% cpu 1:49.86 total

YpsilonはWindows版をCygwin上で走らせているのでトータルのタイムのみが出ている点に注意。

moshが最速なのだが、結果が不正確である。実際string=?の部分を出力するとUTF-8のテストで#fが返っている。 (これはbv2stringの一部なのでUTF-8だけなのだが、全部を走らせると鬼のように不正確な値を返す。恐らくUTF-16及びUTF-32に変換した後のチェックが省かれているのだろう)。

Sagittariusは実用的な速度で正確な結果を返す。ただし、開発版である。0.3.2以前は不正確な値を返す。これはmoshの項で記載したチェックが省かれていたため。

以外だったのはYpsilonである。今まで異次元の速さを誇っていたのがここにきて異次元の遅さになってしまっている。 Ypsilonのutf16->string、string->utf16、utf32->string及びstring->utf32はSchemeで実装されているのでそれが原因かと思ったのだが、utf8->stringとstring->utf8も遅かった。(ちなみに、この2つはC++で実装されている。見間違えていなければ)。ここからは推測になるのだが、これは内部エンコーディングの差ではないだろうか？moshとSagittariusは内部で文字列をUCS4で持っているが、Ypsilonはutf-8で持っている。なので、bv -> ucs4 -> utf8と2回変換が走ることになって、その分のオーバーヘッドが処理時間に如実に反映されているのではないだろうか？

なにはともあれ、一つでもYpsilonに勝ったと言える部分があるのは嬉しいことである。

Unicode対応

Larcenyのベンチマークを走らせようとしているのだが、リーダーや走らせるたびに文字コード周りでテストが失敗する。よくも悪くもかなり厳しくテストが作られているようだ。(正直、リーダー周りは処理系が#!r6rsを付けた際にR6RSに準拠することを前提に作られているので結構厳しかった。)

Unicode周りはそんなに厳密に作っていなかったので、結構な修正を迫られた。おかげでかなり厳密にエンコード、デコードするようになった(と思う)。
UTF32やUTF16に関しては単に範囲のチェックを入れるだけだったのだが、UTF8が結構問題だった。
マルチバイト文字列というのは最初の途中のバイトが不正バイトでも、最初の1バイトのみを不正として扱わないといけないというのにはまった。まぁ、言われてみればそうだよなぁとは納得するのだが、読み取った数バイトをポートに戻すということが出来ないので、ポートから1バイトずつ読み込む場合は不正バイトを検出しても戻らないという糞仕様で回避。(Ypsilonも戻ってないように見えるし、ファイルを読み込むときはいいよね、ファイルを信用しても？)
utf8->stringみたいなすでにバッファに取ってあるバイトのみ不正バイトを検出するようにして、とりあえずベンチマークが要求する部分は解決した。

ただ、このベンチマーク、走らせる条件も厳しいけど、要求してる速度も厳しい。特にCygwinは相手にしてないみたいで、(というか、R6RSの処理系の多くはCygwin対応してない気がする)、一気に1M以上メモリを割り当ててみたり、テスト回数が5桁からだったりとセットで走らせるとしばらく応答がないということがしばしば。
これがあんまり待つことなくさくさく動いたら、多分最速の処理系だろうなぁ。とりあえずはmoshと速度比較かなぁ。

Transcoderを改善したいのその２

書き出し側は昨日やったので今日は読み込み側。とりあえずUTF8だけで実装してみた。
検証コード：

(import (rnrs) (time))
 
(define times 10000)
(define test-data 
  (string->utf8 "12345678901235678901234567890123456790123456789\r\n"))
 
(define tr (make-transcoder (utf-8-codec) 'crlf))
 
(time
 (do ((i 0 (+ 1 i)))
     ((= i times) (display times)(newline))
   (let ((in #;(transcoded-port (open-bytevector-input-port test-data) tr)
   (open-file-input-port "test.scm" (file-options no-fail) 'block tr)))
     (get-string-n in 100)
     (close-input-port in)))
 )

実行結果：0.3.2、開発版の順。

$ time sash test.scm
10000

;;  7.765625 real    3.734000 user    3.235000 sys
sash test.scm  3.98s user 3.41s system 88% cpu 8.391 total

$ time ./build/sash.exe test.scm
10000

;;  4.062500 real    1.359000 user    2.235000 sys
./build/sash.exe test.scm  1.61s user 2.44s system 86% cpu 4.688 total

$ time Ypsilon test.scm
10000

;;  5.015625 real    0.65625 user    3.9375 sys
Ypsilon test.scm  0.03s user 0.06s system 1% cpu 5.312 total

およそ倍くらい速い。Ypsilonより多少速い。ただ、IOに関してはmoshが一番速かった。上記の検証コードの(time)を(mosh)に変更してmoshで実行。

$ time mosh test.scm
10000

;;3.765625 real 1.2029999999999998 user 2.265 sys
mosh test.scm  1.36s user 2.45s system 90% cpu 4.219 total

system時間はそんなに変わらないので計算に掛かっている時間の差なのだが、変換の処理自体にそんなに差はないと思うんだけどなぁ？moshのIOは遅いというのをどこかで見たのだが、嘘だったのだろうか？
ちなみに、上記のコードでblockをnoneに変更したら最速になった。というか、他の処理系が2倍程度遅くなって、Sagittariusの速度は変わらないだけ。

もう少し気になる点として、バイトベクタのポートにするとあほかと思うほど遅くなるんだけど、なんでだろう？それでも、0.3.2よりは速いので、今までどんだけ遅かったんだということにはなるのだが・・・

Transcoderを改善したい

普通に使っているとテキストファイルのIOなんて(なぜか)そう使わないので気にならなかったのだが、httpsとか普通のhttpとかで一文字ずつ変換して流してると無駄だよなぁと思いはじめてきた。

とりあえずどれくらい違うのか試してみたいなぁと思い、utf8コーデック＋put-stringだけの変更という形でベンチマーク。
ベンチーマークに使ったコードは以下。

(import (rnrs) (time) (sagittarius control))

(define times 10000)
(define test-string "12345678901235678901234567890123456790123456789\r\n")

(define tr (make-transcoder (utf-8-codec) 'crlf))

(time
 (let ((out (open-file-output-port "tmp.txt" (file-options no-fail) 'block tr)))
   (dotimes (i times)
     (put-string out test-string))
   (close-output-port out)))

これを0.3.2と開発版で比較。 結果は以下。

% ./build/sash.exe test.scm
;;  0.013002 real    0.016000 user    0.000000 sys

% sash test.scm
;;  0.312032 real    0.141000 user    0.172000 sys

上が開発版。びっくりするほど違う。これはやる価値ありだな。とりあえずやることにする。

Sagittarius version 0.3.2リリース

なんだかんだ言って、月1でリリースする。

Sagittarius Scheme 0.3.2をリリースしました。今回のリリースはメンテナンスリリースです。

修正された不具合

• call-next-methodがsyntax-caseマクロ内で呼び出せない不具合が修正されました。
• 特定のプロシージャ呼び出しが失敗する不具合が修正されました。
• transcoded-portを使ってカスタムバイナリポートを変換するとput-string等のプロシージャでSEGVを起こす問題が修正されました。
• R6RSで定義されていて、実装されていなかったマクロassertが追加されました。
• portクラスの階層が修正されました。
• ソケットポートを使用してget-bytevector-allを呼び出すと終了しない場合がある不具合が修正されました。
• X.509証明書を読み込む際にmake-basic-constraintsがエラーを投げる不具合が修正されました。
• open-inflating-input-portのreadプロシージャで読み込み数が1より大きい場合に例外を投げる不具合が修正されました。これは今回のカスタムポート改善で発覚したもので、0.3.1以前では発現しません。
• X.509証明書をキーストアから読み込む際、秘密鍵のみを読み込んで証明書自体を読み込まない不具合が修正されました。
• bytevector、stringアウトプットポートから出力されたデータを読み出した際に、ポート位置がリセットされていない不具合が修正されました。

改善点

• カスタムバイナリアウトプットポートの出力の際に、ある程度のサイズのバッファを渡すように修正されました。パフォーマンスが改善されているはずです。
• bytevector-copyがオプション引数startとendをとるように改善されました。
• base64-decode-stringがオプショナル引数のtranscoderで#fを受け取った際に生のバイトベクタを返すように改善されました。
• バイトベクタ及びストリングのアウトプットポートのパフォーマンスが改善されました。およそ2倍程度高速になっているはずです。
• 擬似乱数クラスがハッシュやCipherと同様拡張可能になりました。
• キャッシュ機構がScheme側からも制御できるようになりました。
• 上記の改善により、正規表現パターンのリーダがS式ではなくパターンオブジェクトを返すようになりました。

 互換性の無い変更

• 擬似乱数クラスの変更により、custom-prng?プロシージャが削除されました。

新たに追加されたライブラリ

• OAuthライブラリ(net oauth)が追加されました。OAuth 1.0のコンシューマをサポートしています。
• TLSプロトコルライブラリ(rfc tls)が追加されました。TLS1.0からTLS1.2までをサポートしていますが、1.2に関しては動作保障がありません。セキュリティホール等があるかもしれません。
• (srfi :27 random-bits)が追加されました。
• バリデーションメタクラスライブラリ(sagittaius mop validator)が追加されました。

継続してリリースをするということ

ふと、moshにバグレポートをして思ったこと。軽くdisるので先に謝っておこう、ごめんなさい。

前提として、開発版は使わないとします。 なので、trunkからとってくれば直っているよっていうのは議論からは外します。

Sagittariusは意図していなかったのだが月1ペースでリリースをするという習慣になっている。いい悪いはとりあえず置いておくとしてだが。
っで、moshなのだが、最新版は0.2.7でリリースされたのが2011年6月7日とほぼ一年前。その前のバージョン0.2.6も2010年11月7日と半年以上の期間が空いている。もちろん製作者側がすでに「moshは十分に枯れていて、今後新しい機能を足すことも少なく、バグもほぼない」と判断しているならば問題ないのかもしれないのだが、メインで使っていない僕が3つほどバグレポートをし、そのうちの1つはクリティカル(mosh自体が止まる)ものだったりする。大多数はバグレポートにある使い方をしないだろうので、問題ないといえばそうなのだが、レポートにある使い方をする必要がある少数派の人間はいつ直ってリリースされるか分からない処理系を使う気にはならないだろう。

一方で僕は月1でリリースしている。正直必要性をあまり感じない上に、ユーザーもいない(更には自分以外のバグレポートはない)のだが、レポートした人はそれなりに速いうちにそのバグが直されてリリースされるだろうということが予測できる。もちろん弊害もあって、そんな頻繁に更新される処理系怖くて使えないという話にもなる。

もちろん、僕がリリースするということを甘く見ているだけなのかもしれない。WindowsとLinuxでテスト通して、ドキュメント整備してくらいにしか考えてない部分はある。moshと違ってFreeBSDのポート作ってとかないので。

月1でリリースするならそろそろ準備しないとなぁ・・・

TLSを実装したった

ようやく動くものが出来た。まだまだ、作りこみが甘いので予期せぬ挙動が起きると直ぐエラーを投げるが、ある意味セキュアであろう。また、セッションの復元も行えない。
現状ではTLS 1.0と1.1に対応している。1.2もサポートをしたいのだが、動作を検証できる環境が簡単に構築できそうにないので、厳しいところではある。多くのサーバーは1.0もしくはで動作しているはずなので大きな問題になるとは思わないが、ハンドシェイクで0x0303を投げるので、1.2対応のサーバーが多くなると問題が起きそうではある。
また、現状ではクライアントソケットのみの対応である。サーバーソケットが必要な状況が当面僕にはないので、しばらくは対応する予定はない。

なぜわざわざ自前で実装したのか？
世の中にはOpenSSLとか優れた実装がたくさんあるのだから、それをおとなしく使えばいいではないか？実際そうしようかなぁと思ったのだけど、ビルド時の依存関係を極力減らしたいのと、暗号ライブラリが自前であるのにさらに他の実装に依存するのがイヤだったというだけ。ビルド時の依存関係は、現状Windowsでのビルドを極力簡便にするため。現状ではWindowsでのビルドはネットに繋がってさえ要れば何も用意することなくビルドが進むようになっている(もちろんCMakeとVCは要るけど)。この方針を崩したくなかった。
また、Cの実装はたくさんあるけど、Pure Scheme(Lispを含めても)な実装ってないのであってもいいかなぁと。

セキュアなの？
実装上のセキュリティーホールはまだまだあるだろうとは思う。サーバーの証明書を検証してないし。また、実装してて思ったことだが、TLSは暗号セッションが始まってしまえば現状安心して使えるプロトコルだと思うが、ハンドシェイクの段階から盗聴されていた場合はその限りではないと思う。理由はこの辺。

急いで作った理由はOAuth使ってTwitterに呟いているときに、TwitterのAPIにはhttpsがあることに気づいたから。折角だし、セキュアなOAuthにしてしまいたかった。思いの他時間がかかったが、動くのそれまでの苦労が吹き飛ぶ。