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にしてしまいたかった。思いの他時間がかかったが、動くのそれまでの苦労が吹き飛ぶ。

quicklispのインストールからcl-annotまで

Lisperになるつもりはあまりないのだが、試してみたいライブラリが結構あるのでquicklispをインストールしてみる。対象はclisp on Cygwin。
とりあえずquicklisp 。
手順に従ってquicklispをインストールしようとしたら、早速curlがないと怒られた・・・しょうがないのでインストール。
Installationにしたがって以下の用にquicklisp.lispのダウンロードと、clispの起動。上記サイトはsbclなので多少コマンドラインのオプションが違う。

$ curl -O http://beta.quicklisp.org/quicklisp.lisp
$ clisp -i quicklisp.lisp
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.48 (2009-07-28) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2009

Type :h and hit Enter for context help.

;; Loading file quicklisp.lisp ...

  ==== quicklisp quickstart loaded ====

    To continue with installation, evaluate: (quicklisp-quickstart:install)

    For installation options, evaluate: (quicklisp-quickstart:help)

;; Loaded file quicklisp.lisp

っで、clispのREPL上でプロンプトに表示されている注意書きにしたがってインストールを続行。

[1]> (quicklisp-quickstart:install)
; Fetching #<URL "http://beta.quicklisp.org/quickstart/asdf.lisp">
; 159.59KB
==================================================
163,424 bytes in 0.89 seconds (180.28KB/sec)
; Fetching #<URL "http://beta.quicklisp.org/quickstart/quicklisp.tar">
; 210.00KB
==================================================
215,040 bytes in 0.16 seconds (1280.11KB/sec)
; Fetching #<URL "http://beta.quicklisp.org/quickstart/setup.lisp">
; 4.88KB
==================================================
4,995 bytes in 0.00 seconds (1625.43KB/sec)
; Fetching #<URL "http://beta.quicklisp.org/dist/quicklisp.txt">
; 0.40KB
==================================================
408 bytes in 0.01 seconds (56.90KB/sec)

  ==== quicklisp installed ====

    To load a system, use: (ql:quickload "system-name")

    To find systems, use: (ql:system-apropos "term")

    To load Quicklisp every time you start Lisp, use: (ql:add-to-init-file)

    For more information, see http://www.quicklisp.org/beta/

NIL

何か読み込まれた。本当はql:aproposとかで何があるか調べるんだろうけど、cl-annotがあることはすでに知っているのでそのままインストール。

[2]> (ql:quickload "cl-annot")
; Fetching #<URL "http://beta.quicklisp.org/dist/quicklisp/2012-04-07/systems.txt">
; 123.72KB
==================================================
126,685 bytes in 0.10 seconds (1236.79KB/sec)
; Fetching #<URL "http://beta.quicklisp.org/dist/quicklisp/2012-04-07/releases.txt">
; 175.60KB
==================================================
179,810 bytes in 0.15 seconds (1170.87KB/sec)
To load "cl-annot":
  Install 2 Quicklisp releases:
    alexandria cl-annot
; Fetching
#<URL
  "http://beta.quicklisp.org/archive/alexandria/2012-04-07/alexandria-20120407-git.tgz">
; 47.16KB
==================================================
48,296 bytes in 0.04 seconds (1274.98KB/sec)
; Fetching
#<URL
  "http://beta.quicklisp.org/archive/cl-annot/2011-12-03/cl-annot-20111203-git.tgz">
; 8.16KB
==================================================
8,356 bytes in 0.00 seconds (2720.05KB/sec)
; Loading "cl-annot"
[package alexandria.0.dev]........................
[package cl-annot.util]...........................
[package cl-annot.core]...........................
[package cl-annot.expand].........................
[package cl-annot.syntax].........................
[package cl-annot.helper].........................
[package cl-annot]................................
[package cl-annot.std]............................
[package cl-annot.eval-when]......................
[package cl-annot.doc]............................
[package cl-annot.class]..........................
[package cl-annot.slot]
("cl-annot")

パースに時間がかかるのか、落としてくるまでに結構時間がかかった。が、うまいこといっている感じがする。REPL上のコマンドは基本的にはどの処理系でも動くはずなので、後は省略。っで、cl-annot

[4]> (asdf:load-system :cl-annot)
0 errors, 0 warnings
T
[5]> (use-package :cl-annot)
T
[6]> (enable-annot-syntax)
T
[7]> @print 1

1
1

動いた。

知る権利、個人情報保護

一つ前の投稿の続きである。武雄市図書館問題のごく1部、具体的には知る権利及び個人情報保護を扱ったものでもある。

注意書き。

• 私は法律の専門家ではないので、下記の文章には誤りが含まれている可能性があります。
• 断りがない限り下記の文章は武雄市図書館問題に置けるTwitter上の議論に対しての意見です。
• 断定する形で書いていますが、すべて下記の資料に基づく私の個人的意見です。法律的正しさを証明するものではありません。

参照資料

1. 表現の自由 (日本国憲法第21条第1項)
2. 個人情報の保護に関する法律 
3. 図書館法 
4. 図書館の自由に関する宣言 
5. 個人情報保護とプライバシー保護の違い(朝日中央インターネット法律相談)

はじめに知る権利について述べます。 Twitter上でTカードの導入は知る権利の侵害になるというツイートを見ました。この意見は、「貸出履歴と知る権利を混同している」と言えます。武雄市市長は図書館の利用は無料である、と名言しています。
https://twitter.com/#!/hiwa1118/status/200220121770373120

図書館の本は図書館法により無償です。 RT @mikozakuran @hiwa1118 お疲れ様です。時々ツイート拝見させていただいています。武雄市図書館について質問です。業務委託後、図書館の本にレンタル料を課す可能性はありますか？ #takeolibrary

また、図書館法にも貸出に関しての記述は一切ありません。利用者は無料でいかなる図書をも閲覧可能であるため、知る権利の侵害にはなりません。ただし、Tカードなしでの図書館の利用については言及されていないので、図書館利用者はTカードに登録する必要があるということがあればこの限りではありません。

次に個人情報保護法についてです。この問題の焦点は武雄市市長のブログで言及されていた、

「５月６日２０時４０分、４２歳の市内在住の男性が、「深夜特急」「下町ロケット」「善の研究」」

From 図書館貸出情報の扱い、ご安心ください！

という情報が個人情報保護法で保護されるべき個人情報に当たるかどうか、という点である。個人情報の保護に関する法律第二条によれば、

この法律において「個人情報」とは、生存する個人に関する情報であって、当該情報に含まれる氏名、生年月日その他の記述等により特定の個人を識別すること ができるもの（他の情報と容易に照合することができ、それにより特定の個人を識別することができることとなるものを含む。）をいう。

と定義されている。定義のみを見れば明確ではなく、読み手の裁量によって大きく範囲が動くものだ。ここでは、不特定多数の第三者によって容易に特定できる情報とする。その仮定に基づけば上記の情報には氏名、生年月日及び特定の個人を識別する情報は含まれていない。 となれば、上記の情報は個人情報保護法ではなくプライバシー保護に分類されるものである。(過去の判例があればその限りではない)。個人情報保護とプライバシー保護の違いについては参照情報の5を参照されたい。また、図書館の自由に関する宣言はあくまで宣言なので法的束縛はない。事実、第3条の1には裁判所の令状があれば情報を開示するとある。ただし、私が寡聞ゆえに誤認している可能性はある。

Twitter上でこの問題についてのハッシュタグを見た際に、知る権利の侵害及び個人情報保護法違反だという批判を見かけ、法律上だけ見ればそのようなことはないという旨の意見を比較的曖昧な表現を用いて書いたところ、複数の方から突込みが入ったので具体的に記載した。また、私はこの問題自体についてはいくつか批判または議論すべき点が多々あると思っているが、ここでは言及しない。

なおこの問題において、武雄市市長は個人情報保護法には抵触していないという旨を上記のブログで言及しているが、プライバシー保護については言及されていない。 Twitter上では現在個人情報保護ではなくプライバシー保護の観点から問題について言及しているようである。

以下、チラシの裏

図書館利用しないからあんまり関係ないけど

こんなツイートを見つけた。
https://twitter.com/#!/fmht7/status/200074782732075008

CCCとの提携の件白紙に戻し再検討が良いとお考えの方はRTを。 #takeolibrary RT @ryoumax: @fmht7 @hiwa1118 @kokusanlaw 沢山いらっしゃる？何人ぐらい？そんな何の根拠もない言い方するから反対にしても上っ面にしかならないんだよ

(bloggerでTwitterの参照ってどうやるんだ？)
っで、何のことだろう？と思い、元ネタを探してみた。多分これ？
図書館貸出情報の扱い、ご安心ください！

あまり詳しく知らないのでなんともいえないが、貸し出し履歴って個人情報か？というか、管理される情報って

「５月６日２０時４０分、４２歳の市内在住の男性が、「深夜特急」「下町ロケット」「善の研究」」

このレベルらしいのだが？(真偽の程は定かではないが)。噂では炎上しているらしい？もちろん、提携先のCCCという会社のセキュリティがどれほどかとか、その会社は取得した個人情報(上記の情報？)を悪用しない、または管理目的以外には使用しないということが保障されるのかというのは別の話だが。

そもそも、日本の図書館は大分優遇されていると思うのだが、どうだろう？カナダもそうだが、オランダの図書館は有料である。カード作ったことないので分からないけど、多分図書カードも有料じゃないかな？閲覧自体は無料。
正直Twitterの議論って的外れな感じではあるのだが、「知る権利」の保障と貸し出し履歴は関係ないだろう。また、図書の閲覧自体はTカードがなくてもできる(と仮定する)なら、保障されてるよね？自宅に持ち帰るということは、「その本が返却される、またはされなかった際になんらかの行動が取れる」状態にしておかないと、「他の人の知る権利の侵害」ならないかね？(もちろん、Tカード作らなきゃ閲覧も不可っていうなら話は違ってくるが)
ツイートを全部読んだわけじゃないし、何を問題視してるのかも漠然としてるんだけど、これが炎上することがいまいち不思議。
(時間がない、面倒くさいというのもあり)詳しく知らないので、賛否の意見は控えるけど(ずるいのは承知の上)、問題視する点が違わないかな？

https://twitter.com/#!/kuippa/status/200088650367774720

これをうまく収めることができるなら図書館だけじゃなくて炎上対策のモデルケースにもなるね・・・！　（キリッ #takeolibrary

これには激しく同意した。

まじめに意見を書いた。

セキュリティについての考察

SSL/TLSのおけるセキュリティの考察。

実装がまったく行き詰っていて、息抜きにふと思いついたことをつらつら書いているとも言う。

以下に記載した内容に基づいて盗聴、改竄を行ったとしても当方は一切責任を取らない。また、この記事はそのような犯罪行為を推奨するものでもない。(お約束の免責事項)

ふと、ひょっとしたらハッキング(世間一般的に通じる言い方、本当はクラッキングと言う。一応)できるんじゃね？と思ったのでその手順。もちろん試してないし、僕にそのようなことが出来る技術はない。ただ仕様書を読んでいて出来そうだと思っただけ。

【用意するもの】

• 偽のサーバー証明書
• なりすまし用のルータ
• SSL/TLSのパケットを作れる技術

【手順】

1. クライアントが送ってきたCLIENT-HELLOのcipher suitesからDHなsuitesを取り除いてサーバーに送る。このときクライアントの乱数を記録しておく。
2. サーバーが送ってくる情報のうち、決定したcipher suite、サーバーの乱数、サーバー証明書を抜き取る。また、サーバー証明を用意した偽の証明書と置き換えてクライアントに送る。
3. クライアントがpre master secretを暗号化したものを送ってくるので、偽の証明書の秘密鍵で複合。master secretを作成する。また、送られてきたpre master secretを本物の証明書で暗号化してサーバーに送る。
4. 以下、暗号化されたメッセージは手元のマスター鍵で複合したり、MACを合成したりしてなりすます。

【簡単な解説】

1. Deffie-Hellmanを使われると現在のところ現実的な時間で鍵を手に入れることができないので、クライアントがサポートしているcipherから抜き取る必要がある。
2. この時点でサーバーの証明書を抜き取ってしまえば、クライアントは成りすまし証明書を検出する方法はない。
3. クライアントに対してはサーバーの振り、クライアントに対してはサーバーの振りをする。しないと不整合が起きるので。

3番が重要で、まともなクライアントなら偽の証明書にはルートCAがないということで警告を出すはず。でもユーザが構わずOKしたら、う～ん怖い。
もちろん、この程度のことはきっと議論され尽くしているはずなので基本的には問題にならないと思う。っが、RFCだけ見た感じだとそんなこと考えられてなかったので、どうなんだろう？

プロトコルの実装とナンパ

なんとなく2つは似ている気がする。TLSの実装をしていてふとそう思った。

ナンパはしたことがないのでネットで読んだ知識になるのだが、以下の流れだろう。

1. 異性に声をかける
2. 交渉する
3. 目的を達する
4. バイバイする

っで、TLSはこんな感じ

1. ハローってサーバーに言う
2. 交渉する
3. データ交換する
4. バイバイする

ぶっちゃけ、HTTPでもFTPでも一緒だ。交渉の部分があるかどうかはプロトコルによるが。
並べてみただけだが、既にほとんど一緒だなぁ。どちらも成功するか失敗するかは声のかけ方、交渉の仕方による。(まぁ、ナンパはさらに顔面偏差値などもいるだろうが、これは声のかけ方に含める)

ただ一点絶対的に違うのは、手順さえきっちりしてればプロトコルの実装は失敗しないという点。サーバーに選択権はないけど、異性にはあるということだ。そういう意味ではサーバーを落とす方がはるかに簡単といえるだろう。

何書いてんるんだろう、俺・・・orz

プログラマはキチガイじゃないよ

こんなのを見つけた。
プログラム板キチガイすぎワロタwwwwww
ム板とマ板は違うとあれほど(ryというのはほっといて。
内容は2004年に立てられた何かのスレに対してのコメント。そのスレの>>1が2進数で何か書いていて何言ってるんだろう？という話。
2進数なら単に2->16->変換でいけるだろうとこんなの書いてみた。文字コードの判別は面倒だったのでSJIS決め打ち。(2004年だとUTF-8はそんなに普及してなかったなぁ・・・遠い目)

#< (sagittarius regex) >
(import (rnrs) (getopt)
 (sagittarius)
 (sagittarius control)
 (sagittarius regex)
 (encoding sjis)
 (util file))

(define (sjis->string bv)
  (let1 tr (make-transcoder (sjis-codec))
    (bytevector->string bv tr)))

(define (main args)
  (with-args args
      ((i (#\i "input") #t (usage)))
    (let1 s (regex-replace-all #/\s/ (car (file->string i)) "")
      (print (sjis->string (integer->bytevector (string->number s 2)))))))

Sagittariusはこっそり拡張コーデックを持っているので、sjisとeuc-jpが使える。今回はsjisだけど。っで、満を持して元スレの>>1を解読したら、>>2になった。
元スレの>>1がEBCDICでも使っているのか、でたらめだったのかは知らないけど。朝の15分であんまり頑張りたくないのでやめた。

元ネタがなんて書いてあるか知りたい人は是非Sagittariusをダウンロードして

$ sash {スクリプト名} -i {2進数を貼り付けたファイル名}

コマンドラインから上記スクリプトでw

SSL/TLSを実装したいの１

2があるかは知らない・・・ついでに、OpenSSL使えよという囁きが頭の中で木霊しているけど無視。

TLS1.1と1.2をSchemeで実装してhttpsとか使えるようにしたい、という願望の元とりあえず資料集めをしてみた。

• RFC 5246
• MiracleCat's - SSL FAQ

基本はRFCを読めば全部書いてあるんだけど、分量が多いのと送信データが分かり辛い。2つ目のリンクは最初のネゴシエーションで使うデータが詳しく書いてあって参考になる。解説自体はSSL3.0のものだが、TLSでも基本的な部分は変わらない。違いはRFCを見て吸収。

CLIENT-HELLOを送ってSERVER-HELLOを受け取る事まではできた(データ送ればサーバが送り返してくるから当たり前だが)。っで、気づいたこと。

• 生のバイトベクターをゴリゴリやるより、クラス作って抽象化した方が楽。
• ASN.1(というかDER)と同じ方式。
• パフォーマンスとコード量が気になるが、まぁいいか。
• サーバーから返ってくるデータをどう処理しよう。
• TLS1.2(SSL version 3.3)としてハローって言ったのに、TLS1.1でハローって返される。
• 違いってCipherSuiteだけ？

まだ、最初のハンドシェイクさえクリアしてないからなぁ。先は長そうだ・・・

Wicketが腐っているなぁと思った瞬間

Apache Wicketのことです。

事の発端はCheckGroupにAjaxFormComponentUpdatingBehaviorが渡せないということに昨日から1日悩んでいた話。サンプルはまったく見つからないし、Javadocにも特にその辺の説明はない。Google先生で検索をかけてもキーワードが悪かったので見つからない(今は解決した)。

っで、今日ちょっと頭を冷やして検索してみたらこんなスレッドを発見。
DropDownChoice, AjaxFormComponentUpdatingBehavior and dijit.form.FilteringSelect
最初に検索したときは使っているのがCheckGroupなので無視したのだが、藁にもすがる思いで覗いてみた。書いてある指摘としては、AjaxFormChoiceComponentUpdatingBehaviorを使えというもの。しかも、それがさも当たり前のように、「驚いた、実に驚いた、またこのスレだ・・・」みたいな回答がついてる。(まぁ、確かに過去ログ見ろというのも分かるが)
でも、一日3つも同様の質問が出るくらい頻繁に使われるものなのに、ドキュメントはないわ、サンプルはないわじゃ、あまり嫌味を言える立場ではないと思うのだが。 しかも、何このクラス名。混乱を招くに決まっている。せめて「このBehaviorは無視されます」、みたいなログ出してもいいだろうに、それもない。あほか！

単に、昨日一日無駄にしたので愚痴りたくなっただけ。どこかにあったなぁ、私がモダンフレームワークを嫌う理由みたいなネタ。そこからじゃないけど、「それってドキュメントあるんだよね？」って気分。

The reason to be here

Since I don't have any reason, I have been thinking why I'm still here and where I want to go. I haven't found any answer of it. One thing I know for sure is, I don't want to be here so long and even I'm not sure whether I can or not because of the visa.

The problem is, however, I got too much use to be in non harsh working environment. Yes, European working style is excellent if I compare with Japanese one. So I'm also seriously looking for a job in Japan or somewhere in the world. Well if it's not in the Netherlands, it would be fine by me... maybe not... in UK maybe, at least no language barrier.

Things are not so going easy. But I must get out from this suffocating atmosphere. What can I do for it? Think.

Twitterに投稿できた！

(net oauth)というライブラリを作成中。cl-oauthの移植なんだけど、drakmaとかのライブラリはあるわけ無いのでAPI名と処理の流れだけ。
Service Providerまで作る必要はないよなぁと思っているのでConsumerだけ。気が向いたらそのうち実装するかも。
っで、とりあえずTwitterに投稿できたので浮かれて書いてる。コードは以下。

(import (rnrs) (net oauth) (text sxml ssax)
 (sagittarius io)
 (srfi :26 cut))

(define (call/twitter-api->sxml token method path param . opt)
  (define (call)
    (if token
 (access-protected-resource (string-append "http://api.twitter.com" path)
       token
       :user-parameters param
       :request-method method)
 (assertion-violation 'call/twitter-api->sxml
        "later")))
  (define (retrieve body status hint advice)
    (call-with-input-string body (cut ssax:xml->sxml <> '())))
  (call-with-values call retrieve))

(define (twitter-update/sxml token message . opt)
  (call/twitter-api->sxml token 'POST "/1/statuses/update.xml"
     `(("status" ,message))))

(define access-token (make-access-token 
        :key "アクセストークンを入れてね"
        :secret "アクセスシークレットを入れてね"
        :consumer
        (make-consumer-token
         :key "コンシューマトークンを入れてね"
         :secret "コンシューマシークレットを入れてね")))
(print
 (twitter-update/sxml access-token "Hello world from Sagittarius Scheme!!"))

これだけで投稿が出来た。まぁ、アクセストークンを作る部分とかもあるんだけど、一度作ったら使いまわしなので略。Twitter用のAPI集はSagittarius本体に入れるつもりはないんだけど、どこかに置けたらいいなぁ。
これで仕事してる振りして呟ける(違

そういえば、OAuthの2.0どうしよう。今の作りだとガッツリ1.0用だ・・・

OAuthを調べる。

その昔(3ヶ月くらい前？)にSagittariusからTwitterに投稿してみようとして挫折したことがあった。理由はHMACがないから。っで、今はあるので、仕様を理解すればいけるのかなぁと思いちょっと調べてみた。

とりあえず現行のバージョンは1.0なんだけど、2.0も策定中でFacebook、mixi及びその他(忘れた)が先行採用しているらしい。2.0の方はSSLが必須になるので、サポートするのはちと厳しい。(TLSが実装できたらやることにするとして、中身を簡単に入れ替えられるように実装する必要はあるか・・・)
詳しい中身はRFC5849を見ることにして、概要をとりあえず頭に入れたい。っで下記のページが分かりやすかった。
APIアクセス権を委譲するプロトコル、OAuthを知る - @IT

署名とかの処理を除けば処理フローは割りと簡単な感じ。サーバー側を書くつもりは今のところないので、必要な登場人物としては、Consumer(RFCではClientになっている)だけだろう。流れとしては、

1. リクエストトークンの取得
2. ユーザー認証

上記2つは事前に行う必要がある。コンソールアプリだと、リダイレクトが面倒だ。どうしよう？

1. アクセストークンの発行
2. APIを叩く

これらはまぁ問題ないだろう。ユーザー認証で取得できた情報をどこに格納するかとかもそれなりに問題か。暗号化するとかしないとか考えた方がいいだろうか？

しかし、OAuthと書いてオースとは読めない自分。どうしてもオーオースになる。

簡易PEMファイルリーダー

とりあえずささっと作ってみた。X509証明書のみに対応という手抜きっぷり。

#!/usr/local/bin/sash

#< (sagittarius regex) >
(import (rnrs) (asn.1) (getopt)
 (sagittarius)
 (sagittarius regex)
 (sagittarius control)
 (rfc base64)
 (rfc x.509)
 (util file))

(define (read-content p end)
  (let loop ((line (get-line p))
      (r ""))
    (if (eof-object? line)
 (assertion-violation 'read-content "unexpected eof")
 (cond ((looking-at #/-----END (\w+)-----/i line)
        => (lambda (m)
      (unless (string=? (m 1) end)
        (assertion-violation 'read-content
        "invalid pem file"))
      r))
       (else
        (loop (get-line p)
       (string-append r line)))))))

(define (parse-pem-file in)
  (call-with-input-file in
    (lambda (p)
      (let loop ((line (get-line p)))
 (unless (eof-object? line)
   (cond ((looking-at #/-----BEGIN (\w+)-----/i line)
   => (lambda (m)
        ;; read until end comes
        (let1 base64 (base64-decode-string (read-content p (m 1))
        #f)
   (print (make-x509-certificate 
    (open-bytevector-input-port base64))))))
  (else
   (loop (get-line p)))))))))

(define (usage args)
  (format (current-error-port) "usage: ~a -i file~%" (car args))
  (exit -1))

(define (main args)
  (with-args args
      ((in (#\i "input") #t (usage args)))
    (parse-pem-file in)))

まぁ、使い捨てのスクリプトとしては短めに書ける方ではないだろうか。よく言えばこの辺りを処理をするライブラリがそろっていると。というか、そんなライブラリくらいしかないのだが。偏りが激しい。ちょっと手を入れれば、RSAの公開鍵と秘密鍵も読めるようになる。けど、今のところいらないので無視。

鈍足な正規表現だった・・・

なんとなく正規表現のベンチマークをGauche (0.9.2)、mosh (0.2.7)、Sagittarus(HEAD)の3つでとってみた。
正規表現は以下のページのものを使用。
思い立ったが吉日 (正規表現・続き) - Island Life

まぁ、結果はGaucheより速く、moshより遅いといったもの。moshは鬼車を使っているので、鬼車が速いのだろう。ただ、Gaucheは次のバージョンで速くなるらしいので、Sagittariusは鈍足な正規表現を持っていることになる。(特に最適化してないし、リニアタイムであることくらいしか保障してないからしょうがないのだが)。

どうでもいいのだけど、string output portとbytevector output portの実装が今まで腐っていたので直した。というか、上記のコードを移植するに当たって、直さないとメモリが尽きるというあほみたいな問題があった。単純な修正だが結構効果があって、bytevector output portで約2倍の速度を出すようになった。メモリも無駄に枯渇するということもなくなったので、いいことだ。

JSP2.1と2.2の非互換ではまったこと

基本的には2.1→2.2でなんら問題は起きないはずなんだけど、起きた。しかも、解決方法みつからずの難問。

まずは以下のコードを見てほしい。

public class Foo implements Serializable {
  public FooEnum getEnum() {
    return new FooEnum();
  }
}

一見なんの変哲もないBeanである。実際何の変哲もない(勘のいい方はもう気づいたかも・・・)。
問題はこのBeanをJSPで使うと起きるのである。 以下がJSP。Fooのインスタンスfooをどっかから受け取っているという前提。

${foo.enum}

これ、JSP2.1ではOKで、JSP2.2ではNG。理由は'enum'は識別子として認識しないから。JSP2.2で書きたかったら以下のように直接メソッドを呼ぶ必要がある。

${foo.getEnum()}

問題はJSP2.1はメソッドの直接呼出しをサポートしていないということ。つまり、JSP2.1で合法にすると、JSP2.2では非合法になる。逆も同様。逃げ場なし。

どうしたか？直接Javaコードを書きなぐりましたよ・・・
開発環境をTomcat 6からTomcat 7にしたら発生した逃げ場のない不具合。そりゃTomcat 7だけサポートするなら別に問題ないんだけど、他のサーバー(JBossとか)がどのバージョンのJSPをサポートしているか分からないので、どれでも動くようにする必要があるんだよ・・・なんでJavaにはCみたいなマクロがないんだろう。バージョン違いの非互換をどうにかする方法がないなんて・・・

やっつけ仕事

に近い感じではあるのだが、キャッシュの実装が終わった。思ったより時間がかからなかったなぁ。

とりあえず、正規表現(Cの実装)とSRFI-4(Schemeの実装)で両方とも動いているのを確認。キャッシュ用のAPIを追加して、ごにょごにょ。追加で、コンパイル時の定数畳み込みにキャッシュ可能かの判定を追加。これで、define-constantにうっかりハッシュテーブル(キャッシュできない！)とか書いてもキャッシュを壊すことがなくなった。
問題になるとすれば、複雑な構造を持つオブジェクトのテストは全然してないので、いろいろ足りないかもしれない。まぁ、そんな物をリーダーマクロで書くなんてことしないだろう。

しかし、キャッシュのソースがひどいことになっている。リファクタリングくらいはしたいなぁ。でも迂闊に手を入れたくもないなぁ・・・

cachable or cacheable?

何の気なしにずっと「cachable」という単語を使っていたのだが(造語だと自分では思っていた)、これって辞書もしくは標準があるのかとググッて見た。したら、「cachable」と「cacheable」が一応あるっぽい。

なんか1997年くらいに議論されている。Spelling of "cachable"
どうやらWiktionaryではcacheableみたい。cacheable
1995年に現れた単語みたい。Weblio
JEE6ではcacheableというクラスがある。

どうやら主流は最初の議論(メーリングリスト)で推されているcachableではなくcacheableっぽいなぁ。直すの面倒だし、僕は造語の方で。

どうやら、W3C的にはcacheableみたい。Standardize "cachable" and "cacheable" to "cacheable"
知るか！

キャッシュの改善をしたい

前に書いたのだが、ちょっとソースを眺めなおした結果一筋縄ではいかなさそうだなぁと思い再びメモ。

とりあえず作成と読み込みのプロセスがある。っで、問題は作成時だと思われる。読み込みは単にタグみてオブジェクト作ってるだけなので。

【作成時のプロセス】

1. コンパイルされたコードのスキャン
2. スキャン時に検出できたライブラリの書き出し
3. コード本体の書き出し
4. マクロのスキャン
5. マクロの書き出し

基本的にはスキャンと書き出しの2パスということになる。スキャンがある理由は共有構造の検出というのが主な理由になる。


改善における現状見えている問題はスキャンをどうするかということ。現状では対象になるのは、シンボル、文字列、キーワード、識別子、マクロ、ペア、ベクタとクロージャである。最初の3つを除いたものは、自身の中に共有構造を持つ可能性があるオブジェクトを持っている。たとえば、識別子はそれ自身の中に環境を保持しているが、その環境の中にはペアとかベクタが入ってくる。C側、Scheme側でそれぞれ問題が出てはくるのだが、C側の方が問題の解決は楽だろう。
現状Cで書かれているオブジェクトでキャッシュしたいものは、文字セット、正規表現と日付くらいか。特に正規表現はリーダーマクロが単にS式を返すので多少効率が悪い。これがキャッシュ可能になれば、読み込み時にオブジェクトをそのまま返すということができるようになるため、正規表現使用時のパフォーマンスがあがる(多分)。残りはdefine-constantでも使わない限りはあまり恩恵がない。(コンパイル時の畳み込みをキャッシュ不可能なオブジェクトは除外するように直さないとなぁ・・・)

とりあえずC側の改善を試みて、後にScheme側に取り掛かるべきだろうか・・・