Let's start Scheme

2011-12-29

括弧ゴルフ

折角リーダーマクロを作ったし括弧ゴルフでもしてみるかとやってみた。以下のサイトのルールで。
本当にLispはカッコが多い?
最後にあるLispのリーダーマクロを参考にGaucheのfoldを使ったケースを実装してみた。
#! /usr/local/bin/sash
(set-macro-character #\! (lambda (p c) (read-delimited-list #\$ p)))
! import ! srfi :1 $ $
! fold ! lambda ! x y $ ! print ! - x 1 $ "!= " y $ ! * x y $ $ 1
  ! iota ! string->number ! cadr ! command-line $ $ $ 2 $ $
まぁ、ある意味当たり前だが、括弧8個でいける。
set-macro-characterは本来は(sagittarius reader)をインポートして使うべきだが気にしない。
しかし、これ見てSchemeと思う人はおらんだろうなぁ。

リーダーマクロが動いた

まだ、あまりテストしていないが、簡単なリーダーマクロが動いた。
とりあえず当初の目的の通り正規表現を#/regex/と書ける様にしてみた。こんな感じ。
#<(sagittarius regex)
(import (sagittarius regex))
(define rx #/\w+/)
(print (regex-replace-all rx "abcdef@abcdef" "**$0**"))
もちろん#/regex/ixumsのようにも書ける。
汚いなぁと思うのは#<(ライブラリ)のように書かないとリーダーマクロがインポートされない部分。上記のようなプログラムなら(import)がやっても一緒なのだが、ライブラリが問題になってくるので、こんな風にした。
また、loadしたファイルの影響を受けると意味が分からなくなるので影響範囲はファイル単位になっている。

括弧ゴルフに勝つるツールが手に入った(違

2011-12-23

Linuxでコンパイルさせるためのメモ

tarボールでコンパイルさせるテストの一環。
そのうちソースに反映させるが、忘れないようにメモしておこう。

xubuntu 10.xx(細かいバージョン忘れた)ではapt-getでインストールできるcmakeのバージョンが2.8.3だったので、CMakeLists.txtの先頭行にあるバージョンを2.8.3にしてテスト。

手直しが必要だったファイル:
  • library.c
  • core.c 
  • transcoder.c
  • system.c
  • load.c
  • test-lib.c
  • src/CMakeLists.txt
  • ext/ffi/CMakeLists.txt
library.cとsystem.cはミューテックスの初期化問題。まじめにInit関数でやりましょう。特にlibrary.cはInit関数がないので作成して、core.cで呼ぶ必要がある。
system.cは<io.h>がないって言われたのと、environがないって言われた。<io.h>はcmakeを走らせる際にチェックを追加する。environはどうしよう?見つからない理由が分からない。とりあえず通した際にはextern char **environをつけた。
transcoder.cはcodec内で使ってる名前で怒られた。その名もputcとgetc。こいつらマクロなんだ。知らなかった。あればundefするように変更。どうせ中では使ってないし。ってか、こんな極悪なマクロ作るなよ・・・mix、max並みにひでぇ・・・
test-lib.cはuintptr_tがないと怒られた。&t;stdint.h>をインクルードして解決。
src/CMakeLists.txtはpthreadとdlをターゲットリンクに追加。
ext/ffi/CMakeLists.txtはapt-getでlibffiをインストールしたので、ターゲット名が違った。この辺Cygwin版と比較する必要があるなぁ。

以上をなおしたらコンパイルが通った。意外と自動ダウンロード機能も働いていて、BoehmGCは勝手にダウンロードしてコンパイルしていた。(zlibは既にいたのでそのまま使用していたが)
ユニットテストはなんと肝心なrun-test.scmがtarボールに入っていなかった。とりあえずリポジトリからファイルをダウンロードして走らせる(汗。自宅のxubuntuは非常に非力なマシンで動いているので初回テストはガリガリと音を立てていたが(メモリが少ないのよ)、オールクリア。キャッシュテスト用に再度走らせても問題なかった。大枠の出来は割といい感じみたいだ。
ドキュメントの生成も(テストが通ったので当たり前だが)動いている。
まっさらな状態で一応全部いけるということが分かったのは大きい。

それにしても、非力なマシンにもかかわらずコンパイル時間がCygwinでやるより早かった。VCでnmakeを使ったときにも感じていたが、GCCが遅いのだとばかり思っていた。

バージョン0.2.3リリース

今までextディレクトリをtarボールに入れ忘れていたということに気づいて、今回からはそれらが入ってきます。(ということは今までのtarボールってコンパイルすらできなかったということだろうか・・・試してないからなぁ。今後は試すようにしよう。)

今回のリリースは後の拡張に備えたメンテナンスリリースです。

修正された不具合:
  • ライブラリインラインでマーキングミスがあったのが修正されました
  • bitwise-first-set-bitにbignumを与えた際、不正な値を返すことがあった不具合が修正されました
  • renameエクスポートが正しく動作していない不具合が修正されました
改善された動作
  • 文字セットが組み込みになりました
  • gcdにbignumを与えた際のパフォーマンスが改善されました。メモリの使用量が大幅に減っているはずです
  • 正規表現ライブラリが新たに書き直されました。単純な正規表現でかつ巨大なテキストに対してのマッチングもしくは文字列置換であれば以前のものより高速に動作することが期待できます
新たに追加されたライブラリ
  • パフォーマンス測定用ライブラリ(time)が追加されました。現在のところtimeマクロのみエクスポートされています
Windowsバイナリでテストケースを走らせると失敗するテストが2つあります。base64ライブラリのテストとmimeライブラリのテストです。どちらのライブラリもドキュメント化されていないのですが、使用する際は注意してください。

次はリーダーマクロだ!ほぼ正規表現のためだけに入れるといっても過言ではないが、まぁ気にしない。

根本的な解決ではないが

RSA鍵の作成時に素数チェックにgcdを使用していて、Bignumのgcdが非常にナイーブな実装だったため大量のメモリを使用していた。そこで、binary GCDを実装して、メモリの割り当てが最大で4回になるように実装しなおした。そしたら、前述の不具合はとりあえずなりを潜めたのであった。
(あんまり高速化にはなっていないっぽい。512ビットの鍵ペアを作るのに2秒かかる[Core2Duo 3GHz]。Javaでは109ミリセコンドという、20分の1の時間で生成された。う~む)

Windows版のSagittariusでもそれなりにいけるようになってきたような気はするが、テストを走らせると失敗するケースが1つ増えた。正規表現ライブラリを置き換えたからかもしれない。かなりテストを書いたがまだカバーしきれてないらしい。でもテスト外で同じ正規表現、同じ文字列でマッチさせるときっちりマッチするんだよなぁ。メモリ系だろうか、また・・・。Windows版だけというのがまた痛い。メイン環境じゃないからデバッグがしづらい・・・

とりあえず、「よきに計らえ」と勝手に言い聞かせて0.2.3をリリースしてしまおう。

2011-12-22

バグの原因究明

Sagittariusにはドキュメント化されていないライブラリが結構ある。理由はさまざまで、APIが固定されていないとか、近い将来変更になるのでその後とか、バグが取れてないとか、まぁいろいろだ。
その中の「バグが取れていない」の代表格暗号化ライブラリでどこに不具合があるのかがようやく分かった。
結論を言えば、メモリ割り当ての際にオーバーラップして割り当てているせいで、メモリ破壊を起こしているというものだ。
原因はおそらく2つに分けられるだろうが、1つはBoehmGCがマークミスを起こしている。これは回避しようがないので、あきらめるしかない。もう一つは何らかの理由により、割り当てたメモリが使われていないという状態になり、GCによって回収されている(一緒くさいな・・・)。とりあえず前者っぽい挙動をしている。なぜだ?

今回はどうやって直すかというのではなく、どうやって探したかをメモしておく。場所を特定するのに非常に面倒なバグだったので。

起きた環境:
  • VCでコンパイルしたバイナリ
  • 自宅ノートPCのCygwinでコンパイルしたバイナリ
職場のPCでは起きないという隠密バグ(職場もCygwin)。BoehmGCのコンパイル時フラグかな?
使用したツール:
  • WinDbg
  • GDB
NMakeを使っているので、VC++ Expressではデバッグできなかった(評価版なのでプロセスアタッチできない)。
デバッグ方法:
WinDbgでウォッチ式を指定。地道に起きるまでステップ実行(涙)。WinDbgではウォッチ式をしていしても、人の目で監視しないとだめだった。面倒すぎ。
ある程度特定したのちに、自宅PCのGDBでデバッグ。何が壊れているのか分かっているので、ブレークポイントでその値が設定される場所で停めて、アドレスを確認。以下のコマンドを打つ。

watch *0x{上記で調べたアドレス}
最初、丁寧にキャストして実行したらGDBが終わらなかった。キャストせずに上記のように打つとハードウェアウォッチポイントになるらしく、実行がすごく速かった。っで、たどり着いた先はBoehmGCのmalloc。。。どうしろと?
さて、解決方法でも考えるか・・・

2011-12-20

ベンチマークとって見た

新正規表現ライブラリのテストを書いているのだが、どの程度速く(もしくは遅く)なったのか知りたかったので、比較してみた。
コードは以下
(add-dynamic-load-path "./build")
(add-load-path "./sitelib")
(load-dynamic-library "sagittarius--regex2")
(load-dynamic-library "sagittarius--regex")
(import (rnrs)
 (time)
 (srfi :13) (srfi :1))

(define bench
  '(begin
     (define-syntax bench-regex
       (syntax-rules ()
  ((_)
   (begin
     (define rx
       (compile-regex "[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+" 0))
     (define (repeat s c) (string-concatenate (make-list c s)))
     (define s (repeat "abcdefgh" 500))
     (define m (regex-matcher rx s))
     (define times 20)
     (time (do ((i 0 (+ i 1))
         (r (regex-replace-all m " ")
     (regex-replace-all m " ")))
        ((= i times) r)))))))
     (bench-regex)))

(let ((args (command-line)))
  (if (= (length args) 2)
      (cond ((string=? (cadr args) "old")
      (eval bench
     (environment '(sagittarius regex impl) 'user)))
     ((string=? (cadr args) "new")
      (eval bench
     (environment '(sagittarius regex2 impl) 'user)))
     (else 
      (error 'command-line "unknown option")))
      (print "usage: test2.scm old|new")))
で、結果。
$ time ./build/sash -D./build test2.scm old

;;  9.964000 real    9.890000 user    0.000000 sys
./build/sash -D./build test2.scm old  10.06s user 0.03s system 99% cpu 10.176 total
$ time ./build/sash -D./build test2.scm new

;;  0.013000 real    0.015000 user    0.000000 sys
./build/sash -D./build test2.scm new  0.19s user 0.00s system 96% cpu 0.193 total
Pikeさんパネェっす。
別にこのパターンに特化しているわけではないのだが、Perl拡張正規表現が入ってくると別の話になる。それは一つ前のエントリで書いた通り、VMが遅いけど多機能モードに移行するので以前のものより遅くなる可能性が高い。(というか、多分遅くなる)
ただ、個人的に(後方参照はかなり便利だからちょっと考え物だが)先読み、後読み系やpossessiveマッチはあまり使わないので気にしていない。便利なんだろうけど、そんな込み入った正規表現書かないという理由で。

テストケース整備して、APIを以前のものと同じにしたら0.2.3をリリースしよう。

2011-12-19

ハイブリッドVM(正規表現)

正規表現を書き書き直している最中、RE1とRE2を参考にしたPikeVMでは肯定先読み系はおろかpossessiveマッチさえも実装が困難だということに気づいた。
そこでとりあえず普通に再帰を使って書いてみたら恐ろしく遅かった。
どうしたらいいかなぁと電車の中で考えていたら、「ハイブリッドにしちまえよ」という悪魔のささやきが聞こえたのでやってみた。

どうしたか?
拡張正規表現(ここでは上記の2つ+バックリファレンスを指します)を除いた単純な正規表現のみで記述されたパターンはPikeVMで動かし、えらいごてごてした正規表現は再帰を使ったVMで動かしてみた。
これやるとおそらくpossessiveマッチで書いた方が遅いという不思議現象が起きるがそれは置いておいて、後読み(と後方参照もかな?)を除いた210個の単体テストが通った。遅いVMだと異常に実装が楽だったが、涙が出るほど遅く、PikeVMでは速いけどバックトラック系の処理が書けないというジレンマをまぁ使えそうかなぁと思える程度には解消した気がする。
(それでもJavaから移植したコードの方がまだ多少速い・・・まぁ最適化ほとんどしてないからある意味当たり前なんだけど)

後は後読みと細かいフラグの部分を実装して、APIを実装したら一応完成か。クリスマスまでに間に合うだろうか?

2011-12-16

ふと、テレビを見ていて思ったこと

標題に似合わず英語関連です。

文自体は忘れたが、その中にあった単語「labour」を見てふと思ったこと。
そういえば、上記の単語は自然な感じだが、「labor」と書かれると不自然な感じがする。いや、単に英語と米語の違い名だけで意味は一緒なのだが。っでなんとなく自然に感じるつづりと不自然感じがするつづりを並べてみた。
ちょっとしたつづりの比較
英語米語自然だと感じる方
colourcolorcolor
labourlaborlabour
behaviourbehavior両方OK
favourfavor両方OK
favouritefavoritefavourite
centrecentercenter
theatretheater両方OK
とりあえず思いついたのがこんな感じだった。不思議と「ou」になるのが自然と感じるみたいだが、さすがに「color」はこっちのが自然だ。「center」もまぁどちらかと言えばという感じだが、職業柄どうしてもこっちの綴りになる感じ。そのため、「theatre」はこっちの方が自然。(というか街中で見るのはこっちか、bioscoopeだし)
labourは多分カナダにいたときに見た「labour day」が印象に残っているのだろう。
あと何があるだろう?「z」と「s」かな「analyse」とか。うっかり「s」で書いて、Google先生に尋ねたりしてる。
ヨーロッパなのでCMとか英語よりになるんだろう。実際そうだと感じるし。

どうでも話だった。
そういえば、中学、高校の英語のテストで「centre」って書いたら○もらえるのかね?「favourite」はいけると思うけど、どうなんだろう?

2011-12-15

正規表現実装中

ぶっちゃけ行き詰ったのでちょっと問題点の洗い出し。

出来てそうなこと
  • greedyマッチ
  • non-greedyマッチ
  • スタートとエンドアンカー
  • 単語境界
  • グループ(キャプチャリングとそうじゃないの含む)
  • 文字クラス
出来がやばそうなの
  • 肯定、否定先読み及び後読み
  • possessiveマッチ
やばそうなのもある程度は動いてるんだけど、パターンによっては簡単に無限ループに入る。
例えばこんなパターン
\D(?!123)
っで、"ABC123"を与えた場合、文字「C」にマッチしなければいけないが、マッチしない。また、パターンが
\D*(?!123)
になると無限ループする。(ほとんど出来て無いじゃん!)
原因は幅0を実装しているところにあって、2つ目のパターンだと、文字「A」は「\D」と否定先読みの両方を見る。っで、否定先読み(肯定でも)の条件にマッチすると、次の文字に行かずその場にとどまる(幅0の実装)。そうすると、結局文字列"ABCD123"の先頭から同じパターンを繰り返すので無限ループ突入となる。
っと、ここまで書いてちょっと解決案っぽいのが思いついた。要するに先にマッチしたものがあった場合にアサーションに突入しなければいいのではないだろうか?ちょっと試してみよう。

2011-12-12

ジョークプログラム(sleep sort)

sleep sortなるものを実装してみた。
元ネタはここGenius sorting algorithm: Sleep sort
消えてると寂しいので一応引用。
Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22
    Man, am I a genius. Check out this sorting algorithm I just invented

    #!/bin/bash
    function f() {
        sleep "$1"
        echo "$1"
    }
    while [ -n "$1" ]
    do
        f "$1" &
        shift
    done
    wait

    example usage:
    ./sleepsort.bash 5 3 6 3 6 3 1 4 7
2 Name: Anonymous : 2011-01-20 12:27
    >>1
    Oh god, it works.

    But I don't like to wait 218382 seconds to sort '(0 218382)
3 Name: Anonymous : 2011-01-20 12:31
    >>2
    yes the worst case is very big
まぁ、要素ごとにスレッドを止めて終わった順に値を表示するだけ。
Sagittariusで書いてみた。append!が破壊的かつSRFI-18をサポートしてる処理系なら何でもいけるはず・・・
(library (sleep-sort)
    (export sleep-sort)
    (import (rnrs) 
            (srfi :1)
            (srfi :18))
  (define (sleep-sort lst)
    (let* ((new (list '()))
           (threads (map (lambda (e)
                           (unless (integer? e)
                             (assertion-violation 'sleep-sort
                                                  "integer required but got" e))
                           (make-thread (lambda ()
                                          (thread-sleep! e)
                                          (append! new (list e))
                                          e)))
                         lst))
           (r (map thread-start! threads)))
      (map thread-join! r)
      (cdr new))))
こんな感じで使う
(import (sleep-sort))
(print (sleep-sort '(5 4 6 2 8 9)))
;; => (2 4 5 6 8 9)
上記のコメントにもある通り、最悪時間(というか計算時間?)は要素内の最大値になるので、馬鹿でかい数値だと10分くらい返ってこないとか普通にありえるので要注意。(ソートが終わらないから仕事ができないという言い訳にはなるけどw)

追記:
びっくりするくらい2番煎じだった件・・・ scheme(gauche)でもsleep-sort

英語に対する感覚

前に英語で書いた記事にコメントが付いていた(スパム扱いされていたので気づくのに遅れた)。
これはそのコメントを読んでちょっと気になったことについて。

前置きとして、批判的な意味合いはまったく無く、コメントやご指摘がいただけるのは非常にうれしいことだと考えています。もしここから以下を読んで不快に思われたらごめんなさい。ということで一応分けてみる。やたら長くなったし。


2011-12-11

Inside of Sagittarius: Library system

I am not sure whether somebody is interested in this topic or not. However if there is someone who is hesitating to use Sagittarius because he/she does not know about inside. (Well, I just wanted to write something about Sagittarius in English, sorry)

The reason why I am writing this article is Sagittarius has a little bit different library system comparing with Ypsilon and mosh. (Sorry, I don't know about other implementation) Those two implementations does not have real library system, as far as I understood it has more like just alpha-conversion. So you can not operate or explicitly call any library with it. On Sagittarius, however, libraries are also a first class object. So you can actually do something with it. (I have no intention to make its APIs public, though). Because of this, Sagittarius has sort of namespace. (The same symbol can be bind to different values in different libraries).

What is the good things of it? Unfortunately, I can only say one good thing with it which you can re-define existing value somewhere in the library somebody wrote. So you can even patch the libraries which is written in C. Well, this is actually not so secure, however it is very convenient for debugging. (I used this behaviour to debug macro expansion.)

How is it implemented? It is actually really simple. The VM has library table which is created in Scheme or C and hold it to make sure no duplicated library exists. And library itself has a hashtable and some meta information. The hashtable's key is symbol and value is gloc. Gloc is sort of handle for bindings.

What is the *bad* thing of it? Well, I don't like to write this answer but every implementation have good/bad things and user must know it. Because of this library behaviour, Sagittarius can not have explicit macro expansion phase, so all for import keyword will be ignored. And because of this, (could be because of my insufficient skill), Sagittarius' syntax-case can not compromise a few R6RS requirements.

Sagittarius is still under developing however it has already a lot of useful libraries (maybe not documented yet...). If you like the idea and want to try R6RS implementation, why don't you try it?

2011-12-08

コードをいじっていない

一応、1週間の休暇中でコードを触らないと決めたので触っていないのだが、アイデアは出そうなので取り留めないことをメモしておこう。

正規表現書き直しについて
マッチが既存のものより3倍程度遅いが、これはひょっとしたらマッチさせるたびにメモリの割り当てが3回発生してるからかもしれない。なので、現状マッチさせる際に作成しているコンテキストをマッチャー作成時に初期化して再利用したら高速化されるかもしれない。これでなお遅かったらなんだろう?
Possesiveマッチとか後方参照とかどうしよう?RE2はサポートしてないんだよね。パーサーはCL-PPCREを参考にしたので、その辺対応してるのに、VMは対応(まだ、だといいな)してない。考えないと。

リーダーマクロについて
これは実装手順になっていくのかな?現状ではまぁ普通にスイッチ文で一文字ずつ見ている。次のリリースもしくはその次位には細かく分けられたリーダーを用意して都度プロシージャーを呼び出すようにする。ただし、Cで実装されたものを単純にapplyすると遅そうなので、それは直接呼び出すようにする(引数さえ調節可能、ってかVMはそうしてるし)。その後、リーダーマクロ用のテーブルにマクロのセットを足してディスパッチするようにしてやる。ユーザー定義のリーダーマクロはそこができてから実装するようにする。多分、文字の登録もしくはディスパッチャ(2文字)の登録になるはず。CLの実装も確認しておきたい。xyzzyのソースを読む必要があるか?
(まずはCLのリーダーマクロをいじってみろという話もあるが・・・)

CLOSについて
これは0.3.0くらいに入れたい機能だが、実装方針をとりあえず立てておきたい。ソースが結構大きくなっているので、少しずつ置き換えるというのが難しいかもしれないが、最初は即値クラスから実装(fixnum、文字、boolean、etc)。一気に置き換えるなら現状のタグを消してコンパイルかけて一つずつつぶしていくという地味な作業になるだろうか?気になるのはタグの11ビット以降を利用しているもの(文字列とか)。別にフラグを構造体に持たせる必要がでるのか、現状のようにヘッダー内でなんとかしてしまうか悩むところ。
クラス階層として、文字列、ベクタ、バイトベクタをシーケンスクラスのサブクラスにしようかはちょっと悩むところだが、ハッシュテーブルとツリーマップはディクショナリクラスのサブクラスにしたいところ。
総称関数は多分後回しにできるので、先にクラス構造を入れてしまいたい。
まずはTinyCLOSのソースを熟読するところから始める必要はあるだろう。

もし何方かSagittariusを使っていて、こんな機能がほしいってのがあったら是非教えてほしいですm(_ _)m

2011-12-05

Reader macro preparation

Since I want to add CL like reader macro to Sagittarius, I have been thinking how. I think I had a solution for it so I'm going to memorise it.
Since R7RS draft has been released 4 times and it has different reader macro for bytevector (blob in R7RS or also bytevector?), I need to switch readers between R6RS and R7RS. By default, it can be both, but if user (for now only me...) explicitly specified the mode with shabang #!r6rs or #!r7rs, it should enable or disable some R6RS or R7RS specific reader macro. Well, it is actually easy to just switch with current solution (currently I just see the flag of it and check). But it's not so smart when R8RS or R9RS appears.
So, I'm thinking to add reader macro sets to VM and for future even libraries. The concept is really simple, I just need predefine reader macros for R6RS and R7RS it can be shared its implementations and when #!r6rs or #!r7rs appears switch the set. For this purpose, this behaviour must be per file like current shabang and by default it should have everything (just my preference)
How to do it? The point will be 2 or more letters reader macro such as #vu8(...) or #u8(...). I am thinking I will add 2 sets to VM. One is one letter reader macro and other one is 2 letters reader macro and 2 letters are high priority (or else bytevectors will be invalid vector syntax ...)
Well, I wrote about reader macro however first of all I need to finish replacing regular expression library...

LA行ってきた

今回はバカンスではなく、仕事の面接ということでダウンタウンがメインだった。面接の結果はまだ出ていなく、ボールは向こうが持っている状態。ただ、ボールがもしこっちに来た際には決断をしなければならない。いく前は割りとLAに行こうかなと思っていたのだが、今は揺れている感じ。
いくつか理由がある。良いところと悪いところ両方。少し頭の中をまとめていこう。

良い点
  • まず間違いなく給料があがる。それも下手したら3倍くらい。
  • うちの彼女がアメリカに行きたがっている(NYCなので東海岸だが・・・)
  • ビザを出してくれるアメリカの企業はほとんどないので、次はないかも
悪い点
  • アメリカにいるのに日系企業で日本のコミュニティにいたら、なんか違う。
  • 生活面ががらりと変わる。特に気候とか。夏場40度もあるって聞いたから多分融ける。
  • RX-8は諦める必要がある。(持っていくのが不可能に近い)
  • IT系でも今やってる分野からかなり離れるので次を考えたときに不安。
  • あのLA訛は慣れるのに時間掛かりそう。
大きな部分を占めている順に書いてみた。悪い点が多いのだが、よい点の一番上はかなりでかい。悪い点の下2つは割りとどうでもいいしw
良い悪い関係なく揺れる点ももちろんいくつかあって、それらも含めて考えないといけない。正直人生の岐路としてはかなり大きいので、ボールがこっちの来ないまま「あの時は残念だったね」なんて言っていた方が楽かなぁとも思ったりする。優柔不断な性格には結構きつい・・・

2011-12-01

LAに到着

着陸アプローチが2回あったり、空港が停電してたりとあんまりろくなことがなかったが(機内食のチキンカレーは旨かったか)、無事LAに到着。
思っていた100倍でかい街でちょっとうろたえていたり。あまりにでかすぎて既にオランダが恋しいというチキン野郎。

何故ここにいるのか、(しかも独りで)、実は面接を受けに来ているのです。そう、ひょっとしたら(また)移住するかもしれない。オランダ気に入ってるので、給料の額面とか次第ではあるけど。(まだ決まってない)
自分自身こんなに国を転々とするとは夢にも思っていなかった。本当どこでこんなイベントフラグ立てるんだろう?
どうでもいいが、LAの人の英語が聞き取りずらい・・・オランダ訛に慣れすぎたか・・・

2011-11-29

ちょっとひどすぎだろこれ?

橋下知事が高校生をフルボッコwwwwwww
上記のサイトにあった動画を見た。ひどすぎというのは知事ではなくて、高校生の方。
討論になってない。というか嘆願にすらなってない。

というだけでは自分も同類なので、まずは自分がどちら側か。もちろん知事側。
理由、僕は大学受験の際に不景気のあおりで傾きかけていた親の事業のため、母親から「お前だけは国公立に行ってくれ」と言われたので。
この高校生たちに言いたいこと。中学のときに勉強しなかったの?それとも別の理由で私学に行ったの?学力が優秀なら奨学金制度もあると思うけど、それは活用しないの?etc.

と、これだけだと面白くないので、高校生側からなんとか議論に持っていけないかとも考えてみた。
大阪の受験事情を知らないので、僕が高校受験をした際の愛知の事情で。
愛知県は当時A日程、B日程と分かれていて、もちろん両方受けることができる。ただ、進学校を狙って両方とも自分のレベルより少し高い高校を受けた際に、両方とも落ちるということはままある。この辺僕は割りと問題だなぁと思っていて、どうしても滑り止めとして私学を受ける必要があった。(もちろん中学浪人という選択肢もあるはあるが)
僕ならそこを切り口にして、
  • 将来的に○○を専攻したいと思い、その分野に力を入れている公立の進学校を狙ったが、不甲斐なくも両方落ちた
  • 母子家庭で母親の収入だけでは厳しいのを知っていたが、進学校の私立に自分もバイトをして学費を稼ぐからと無理をいって入学
  • そうは言ってもそれだけでは厳しいし、バイトばかりして学業がおろそかになるのも本末転倒なので、補助金も学費の足しにしていた
  • 奨学金は大学の入学費等に当てるため貯金している
という路線で補助金の必要な環境にいることをアピールして、例えば学業の優秀な人には補助金を出して教育に力を入れるよう促すかね。
でも、単に補助金の減額だった上記のようなのは考慮に入ってるかもしれない。全額カットだと議論に余地ありかもしれない。問題は、そこまで考えている高校生には見えなかったのと、話の内容から箸にも棒にも引っかからない成績だったので私学に行ったように見えたので、話に信憑性がでないことか。

2011-11-28

頓珍漢なコメントをしてしまった

えぇ、正直浮かれてました。

事の発端はこちらのブログ
R7RS実装のポイント(改) - .mjtの日記復帰計画
なぜ浮かれたか、Sagittariusの名前が載ってたから。
っで、キーワードのことについて触れてたので、頑張ればポータブルに書ける旨をコメントしたのだが、3回くらい記事を読み返しておかしいことに気づいた。
(コメントを消す機能はないみたいなので、頓珍漢なコメントはインターネットに残り続ける・・・orz)
多分、R6RS処理系全体でポータブルなR7RSのライブラリを書くということなんだと思う。(国語苦手だったんです)
もしそうなら、こんな超マイナー処理系まで考慮に入れていただいて大変ありがたいです。moshを散々disってすいません。でも、moshには負けません(何の勝負?)

こんなとこ読んでないとは思うけど、一応言い訳・・・

2011-11-27

トヨタ「ハチロク」

こんな記事を見つけた
トヨタ「ハチロク」復活へ…来春に200万円台
200万円台といわれると、僕のRX-8(日本にある。売られる前に引き取らねば!)と一緒だわね。まぁ、前半か後半かで大分違うが。(僕のは240万台だったかな?そこから20万値引きがあったけど、諸費用が結構かかった記憶。ブログのどこかに書いたか?)
正直、トヨタがそう好きではないというのを差し引いても、あまり魅力を感じないなぁと思ってしまった。水平対抗なエンジンがいいっていうなら、スバルのインプレッサを買えばいいわけだし、イニシャルDを読んでない20代の若者はハチロクって言われても「何それ?」だろう。
スポーツカー好きな僕としてはメーカーがスポーツカーを作るというのは非常に好ましい状況なのだが、これはどの層をターゲットにしてるのかわからないなぁ。(RX-8のときは4ドアスポーツカーで、多分30代の家族持ちでスポーツカーにもう一度乗りたいという人だったのだろうと思う)
正直今のご時世で2ドアスポーツに200万以上払う人がいるだろうか?マツダのロードスターみたいな「車好きに!」みたいなコンセプトならまだしも、そうは見えないしなぁ。

この辺の意見を見ると、賛否両論だなぁ。まぁ、元が2chなので微妙ではあるが。
下の方みたら、ベースで250万になるとかのレスがある。本当なら正直RX-8より魅力が低いのに価格が上という糞仕様になるなぁ。(多少RX-8贔屓過ぎるか?ロータリーエンジン可愛いよロータリーエンジン)

日本のIT企業とオランダのIT企業の比較

slashdot.jpにこんなのがあった。
日本人プログラマーについての記事が Hacker News で話題になった
元ネタはこっち(英語)
Force Multipliers and Japanese Programmers

要約すると、日本企業は新しいフレームワークを使うことを極端に嫌がるため、生産性を落としているというものだ。
僕が日本のIT企業で働いた経験は(多く見積もっても)4年半なのであまり本質を捉え切れてないかもしれないが、大まかにそうだなぁと思うところが多々あった。スラッシュドットのコメント蘭は特に的を射ていた感がある。
それにプラスしてではないが、自分が感じたオランダ企業との比較をちょっと書いてみようと思う。一つしか知らないのであまり参考にはならないが。

納期を極端に重要視する
日本で働いていた際にどう考えても無理だろうという納期があったが、いわゆるデスマでなんとかした経験がある。その際にプロジェクトマネージャーに「どう考えても間に合わない再スケジュールしてくれ」と頼んだのだが、答えは当然「無理!」だった。
逆にオランダではその辺は割りと柔軟でこちらからあらかじめアラートを挙げると、優先順位の付け直しをしてクライアントとスケジュール調整をしてくれる。

自社製のフレームワークに極端にこだわる
まぁ、これは上記のブログでも言及されていたが、日本では割と元請けのフレームワークの使用を強制される。そのフレームワークが「実際に生産性を向上させるもの」ならいいのだが、4年半(開発者としては2年半)の間にそのような優れたものを見たことがない。おおよそ、「素直にhibernate使えよ」とか(当時なら)「素直にstruts使えよ」というようなものが主だった。個人的にこれらのフレームワークが好きではないのだが(特にspring)、確かに車輪の再開発をする必要がないのでビジネスロジックに集中できる。また、一度これらのフレームワークを習得してしまえば別のプロジェクトでも使えるので習得期間という初期コストを抑えられる。でも、○○社謹製△△フレームワークなんての物の習得がプロジェクト毎に入るんだよね。大抵上記のフレームワークの劣化版かつAPI互換性なしで。まぁ、その期間なにもしなくても金が入るから偽装派遣屋さんには美味しいかもしれないけど。

ユニットテストの概念がない、その為リファクタリングが非常に困難
この辺は今はよく知らないけど、僕が働いていたときはテストといえばテストケースの仕様書があって、人間が手でデータを揃えて都度エビデンスの作成。仕様変更もしくは不具合修正があればやり直し。これが結合テストですらなく単体テストレベルだったから涙が出そうだった。
(じゃあ今テスト駆動でやってるかといえばそうでもないのだが・・・)

PG->SE->PM以外のキャリアパスがない
個人的にはこれは結構問題だと思ってて、それぞれ全然違うものなのにあたかも順当なキャリアパスのように扱っている。例えば日本の求人を見ると、「PG->SEへと着実なスキルアップ」なんて殺し文句をそれこそほぼすべてのSIerの求人でみる。SEというポジションが最早なんなのか分からなくなったけど、SEの先にPMがあるなら、PG->PMになるはずだ。PMってプロジェクトマネージャの略なのでスケジュール管理とクライアントとのミーティングがメインタスクになる。
そうなりたいならいいけど、プログラマからそこに行く道って、大工が保険の営業になるくらい違うと思うのだが、どうしてそれがデフォルトなんだろう?(理由は次の問題で)

PMが最も単価の高い高級職
上も問題の答えだと思う。企業は単価の高い人間を売りたい(IT企業の多くが2次請け=人売りだと仮定)ので、単価の安いPGよりも単価の高いSE、PMを元請けに売りたいわけだ。
でも、これってすごく間違っていて、技術の高いプログラマが育たない、もしくは育っても開発に携わらないということになる。
これはモチベーションの問題だが、PGの単価が安いってことは、がんばっても給料安いのでやる気もでんわね。

思い出せただけでこれだけか。そもそも、文学部出身がPGになるってので間違ってる気がするけど。如何にIT業界(SIerか?)の求める人材がコミュニケーションスキルに偏ってるか分かるところか。

2011-11-24

疎な配列(Sparse Array)

あんまりこれについて書かれてる記事がなかったので書いてみる。
(MathematicaにマニュアルがGoogleでトップにヒットするんだもん)

事の発端
RE2のソースを読んでて、SparseArrayなる入れ物があるのを発見。Sparse Arrayとは何ぞやと思い調べてみた。

分かったこと
タイトル通り、訳としては「疎な配列」。意味は配列自体は巨大なんだけど中身はすっからかんな配列。(実装が腐ってるとそうなる)
ハッシュマップと何が違うの?もともとは行列を扱うのに適したものだったらしい。なのですべての要素に初期値がある。(ハッシュマップにはない)
後、検索、挿入、削除などのアクセスが定数時間(O(1)ってこと?)。イテレーションにかかる時間がO(n)でnは要素数、配列のサイズではない。
普通の配列を使うより高速かつハッシュマップと違ってリサイズの心配がない。(動的な配列ではないた。、実装によると思うが)


何がハッシュマップに比べてよさげか
あくまで配列なので、ハッシュの計算をする必要がない。(RE2のSparseArrayはそうなってる)
RE2の実装ではイテレータはインデックスと値のpairを返す。(多分そうやってO(n)のイテレーションを実現してるのだろう、for(int i = 0; i < size; i++)とは書けないということだね)
リハッシュの心配がないので、メモリの見積もりが聞く。


何が単なる配列よりよさげか
総アクセス時間が要素数に対しての線形になる。(配列のサイズじゃない)

自前で実装するほどのメリットが今のところ見当たらない。結局メモリの節約になるわけでもないし。
あ、まてよ、RE1もRE2もコンパイルされた正規表現のインストラクションの数だけ配列つくってるなぁ。10000以上になってきたらさすがに総アクセス時間がパフォーマンスに影響を与えそうだ。
とりあえず、配列アクセス用のマクロ書いて、パフォーマンスチューニングの段階になったら考えるか。(こういうときC++だとtemplateが使えると便利だよなぁ・・・)

2011-11-23

Inlinable marking

On Sagittarius Scheme, as I wrote before (in Japanese) it has mechanism to inline non exported small procedure and seems constant variable implicitly. Well, it sounds really good, it does optimise like GCC's static functions or static const variables.
However, if it marks wrong way, there is problems. I have introduced define-constant syntax and implicit inliner for non exported constant value since version 0.2.2. The latter one had the problem. The compiler marks some variable which should not be inlinable as inlinable. Let me show my embarrassing staff:
(library (test)
   (export test)
   (import (rnrs))

  (define *inner-value* #f)
  (define *inner-value2* #f)

  (define (test)
    (and (begin (set! *inner-value* #t))
         (begin (set! *inner-value2* '())))
    (display *inner-value*)(display *inner-value2*)(newline))
)
In this case, (I actually did not check if it does mark wrongly or not) *inner-value2* will be marked as inlinable, so the compiler inline it as #f. This is the problem. As you can see, it has to be '().
Inlinable marking is written as conservative as possible. Well, actually it wasn't ...

I was too lazy to open an issue for this on Google code, so I just fixed it.

2011-11-22

俺もアメリカに行くよ

mixiのマイミクが書いた日記の標題をそのままパクリ。
そのままです、アメリカに行きます。3泊4日で。今回はLAです。

期間は11月30日から12月3日まで。何が偶然かと言えば、マイミクは誕生日をアメリカで過ごしたが、どうやら僕もそうなりそうだ。節目の年(と多くの人が考える年齢になる日)をアメリカで過ごすのは何かの暗示だろうか。
まぁ、いろいろ事がうまく(なのか拙くなのか正直自分でも分からん・・・)進むといろんな意味で節目になるだろうなぁとは思っているのだが。

ところで、誰かLAでお勧めがあったら教えて。正直右も左も分からん。
といっても、あんまり身動きが取れる時間がないので手早くいけるお勧めの場所、レストランなどがあるといいなぁ。

2011-11-20

ロードマップを考えてみた

今後のリリースでSagittarius Schemeがどのようになるのかというのを考えてみた。
たいした物ではないし、0.3.0までしか考えてない。
version 0.2.3
  • 組み込み文字セット(完)
  • 正規表現ライブラリの書き直し(in Progress)
    • cl-ppcreの移植
version 0.2.4
  • リーダーマクロの導入
    • 【動機】正規表現を#/regex/と書きたい!
version 0.3.0
  • Tiny CLOSをベースにした組み込みCLOSの導入
    • 【動機】総称関数がほしくなる場面が多々ある
    • 【動機】現状、レコードと公開していない構造体が混在しているのですっきりさせたい
  • 上記をベースにしたレコードの実装
  • (可能なら)VCでの文字列をC++11仕様のU"string"に変更
    • 文字列リテラルをutf-32(ucs4)に統一
    • VCでのコンパイルはCではなくC++になるかもしれない
思ったとおりたいしたものではなかった。もちろんバグフィックスは随時だし、簡単にできそうかつ効果的だなぁと思ったものは実装していくと思う。
なので0.3.0が0.2.4の直ぐ後に来るとは限らないわけだが。(ただCLOSを組み込みにするとなると、結構な修正が入るので、無暗に修正範囲を広げることはしたくないので、多分0.2.4の後は0.3.0になると思うが。もしくはリーダーマクロを0.3.1に回すかもしれないが)
リーダーマクロは実装の目安がある程度あって、試してみたいなぁというのがある。これも内部的に結構いじくることにはなるので、(主にリーダー周りだが)どこで入れようかは実際迷い中。

独自実装を入れすぎだろか?
まぁ、Mostly R6RSと謳っているので問題ないか。ユーザー数1(僕)だし。

2011-11-16

正規表現ライブラリを書き直そう

組み込みの文字セットが完了したので、いよいよ本丸に取り掛かろう。
現在SagittariusではJavaから移植した正規表現を使っている。別にこれで問題はないと言えばないのだが、気になるのはその中で独自のASTを持っていること。
せっかくSchemeなんだしS式でASTを構築したほうがいいんじゃね?とちょっと思えてきた。
なぜそう思ったか?
世の中にはPCREとSREという正規表現のタイプがあるらしい。まぁ、もっとあるだろうが。っで、PCREは超有名なPerlの正規表現。SREはS式で書かれた正規表現らしい。Perl形式の正規表現をSREに置き換えて、ってやれば、PCREもSREも使えて一粒で2度おいしい感じがする。
と、こういうことをやっているのが、irregexというAlex Shinn氏が書いてるScheme用の正規表現ライブラリなわけだ。とりあえず、それを足がかりに文字列->SREなものを作って、ごにょごにょするか、もう少し資料をあさってみるか。(鬼車のソースを眺めてみるのもありか)

2011-11-15

Scheme使いのためのClojure入門

なんてタイトルをつけてみた。別にたいしたことをするわけでもなく、単に文法上の比較というかなんというか。
とりあえず、Clojureを触ってみた感想ではある。
;; 定義
(define hello
 (lambda (name) (string-append "hello, " name)))
;; or
(define (hello2 name)
 (string-append "hello, " name))
;; 定義
(def hello (fn [name] (str "hello, " name)))
;; or
(defn hello2 [name] (str "hello, " name))
特に何も書く必要はないだろうというくらいよく似ている。[]は引数だけど、ベクターのリードマクロでもある。
うわさによるとdefnは構文ではなくマクロだそうだ。 あと、defnはデフォルトでSchemeでいうcase-lambda仕様になっている。
;; 名前付let
(define (factorial n)
  (let loop ((cnt n)
            (acc 1))
    (if (zero? cnt)
        acc
        (loop (- cnt 1) (* acc cnt)))))
;; 名前付let
;; なんてものはないのでloopとrecurを使う
(defn factorial [n]
  (loop [cnt n acc 1]
    (if (zero? cnt)
      acc
      (recur (dec cnt) (* acc cnt)))))
loop構文は多分letのバインド方式だと思う。Clojureではletは括弧が一つでよくて、順に変数名、初期値、以下続くという感じになる。Schemeに慣れているとちょっと混乱しそうになる。
とりあえずこれくらいにしてしまう。本家サイトにドキュメントあるので、興味があればどうぞ。

それはおかしいだろ

マジで言ってるなら人間性を疑うレベルだが。
https://twitter.com/#!/YANA1945/status/136027550081220608
今日の面接。「もし給料が支払われなかったらどうする?」私が必ず訊く質問だ。目をキラキラさせて「構いません!」と叫ぶ人は合格。少しでも戸惑う奴。そんな奴とはプライベートでも口を聞きたくない!さっさと立ち去れ!
「論外ですね」が僕の答えになるだろうなぁ。もしくは何も言わずに立ち去るか。
叫んだ人は奴隷根性丸出しと批判してもいいかもしれない。
業績不振で遅延支払いになるとかだったらまぁ、「理由しだいでは理解します」になるかもしれない。実際、今の会社は今年のベースアップはなしと言われたし、理由もまぁしょうがないかというものだった。
支払われないということは、雇用契約の反故を通り越して「死ね」と言われているのとほぼ同義だと思うので、奴隷なら雇用者の都合で死ねという理念が無ければこの質問は出ないはずだ。

もともとは、
Island Life - 釣りくさいけど
で見つけたものなのだが(べ、別にShiroさんの隠れファンなんかじゃないんだからね!)、豪快に1本釣りされたのかもしれない。
でも、このエントリの追記にツイートした人は面接代行業者とあったので、割とマジなんだろう。整合性も確かにある。
っが、お前同じこと言われたら目をキラキラさせて「構いません!」と叫ぶんだろうな?と問い詰めてやりたい。他のツイートもなんだかキ○ガイじみてるものだったし、まぁ、根性論で走る人なんだろう。
可能な限りお近づきになりたくないタイプの人種だ。

2011-11-14

赤黒木(続)

結局LLRBではなく純正赤黒木を作ることにした。というかJavaのTreeMapの実装をそのまま移植したともいう。
テストができてないが、とりあえずいいだろう。

一つ前の記事で、メモリ効率と書いたが、よく考えればそんなものどうでもよくて、重要な点は順序があることだった。実装してて気づいた。馬鹿か俺は(カカシ風)
この赤黒木はSchemeのAPIにもするつもりではあるが、元々は組み込みの文字セットを実装するためのものである。なので、ハッシュテーブルのようにオーダーがなくなるようなものではなく、データの挿入時にオーダーが保たれるものじゃないと困るわけだ。(範囲等の関係で)

正直赤黒木の中身がどうなっているのかいまいち理解してないが、(2-3-4木を二分木で表現したものということくらいしか・・・)、単に使うだけなら問題あるまい。問題が出たら直せばいいわけだし。
木の回転とバランスが命だということは実装(コピー)してて気づいたが・・・

2011-11-12

赤黒木

(後々の正規表現ライブラリ改善のため)組み込みの文字セットを入れようと考えているのだが、ハッシュテーブルをセットとしてもつより、平衡二分木を持った方がメモリ効率的にいいかなぁと思い、赤黒木を調べ中。(長い)

調べてみると、実装が難儀とあって、LLRBなるものを発見。Javaで200行程度で実装できるらしい。とりあえずこいつを実装して、後から実装を変更するのもありか。
となると、他の二分木も実装(AVL木とか)も試してみたくなるよなぁと思うのが人間で、そうするとインターフェースだけ定義して実装は別にしたい。何を持つべきだろう?
正直、どこまでやるかということになるが、一応Schemeからも実装できるようにしたいなぁと思うと以下のようになるだろうか?
typedef struct tree_map_rec
{
  int type; /* CかSchemeか*/
  union {
    struct {
      int (*insert)(struct tree_map_rec *tree, node_t *node);
      /* so on */
    } c_procs;
    struct {
      /* scheme procs on C object*/
    } scheme_procs;
  } impl;
} tree_map;
問題になりそうなのはnode_tの定義か?まぁ、とりあえずintptr_tの別名にして、実装毎に適当に定義してキャストすればOKだろうか?
あとは、実装ごとにイテレータをどう用意するかとかその辺を煮詰めないとなぁ。この辺C++だともう少し簡単に書けそうだよなぁ。ABIの問題さえなければ・・・

2011-11-11

1年前のネタを拾った

ボーっとどう書く的なネタを探していたら、こんなの発見。

Twitter / ばーるのようなもの: comp.lang.scheme で簡単なリスト操作 ...
comp.lang.scheme で簡単なリスト操作のお題が出ておるな。
っでやってみた。
(import (rnrs) (rnrs mutable-pairs))
(define (acons k v r) (cons (cons k v) r))
(define (process-labeled-list lst)
  (let loop ((lst lst)
      (ans '()))
    (if (null? lst)
 (map cdr (list-sort (lambda (p1 p2) (< (car p1) (car p2)))
       ans))
 (cond ((assv (caar lst) ans)
        => (lambda (slot)
      (set-cdr! slot (append (cdr slot) (cdar lst)))
      (loop (cdr lst) ans)))
       (else
        (loop (cdr lst) (acons (caar lst)
          (cdar lst)
          ans)))))))

(process-labeled-list '((0 a b) (1 c d) (2 e f) (3 g h) (1 i j)
   (2 k l) (4 m n) (2 o p) (4 q r) (5 s t)))
set-cdr!を使うのは卑怯だろうか?
副作用ありだとあんまり関数型っぽくはない気もするが。

他の処理系でも動かすために、aconsを再定義。Sagittariusならなくても動く。というか、import文すら無くてもこれくらいなら動く。

Version 0.2.2リリース

1日寝かせたら不具合を発見したのでそれを直してのリリース。

今回のリリースではコンパイラがさらに定数畳み込みを行うようになりました。また、定数畳み込みを補助する構文としてdefine-constantが正式にサポートされました。
またビルドの際に必要なライブラリがプラットフォームにインストールされていなかった場合、自動的にダウンロードするように改善されました。 ただし、MSVC環境以外ではテストがあまり行われていません。

修正された不具合
  • get-bytevector-n!でcountパラメータがバイトベクターのサイズだった再に&assertionが投げられる不具合が修正されました。
  • Windows版のmake-transcoderがEOLスタイルをlfとして作成する不具合が修正されました。
  • ライブラリのrenameインポートの際に、renameされたものだけをインポートする不具合が修正されました。
  • let*-valuesの右辺値に左辺値が含まれている際にコンパイラがエラーを報告する不具合が修正されました。
  • delete-fileの挙動がR6RSのものと異なっていた不具合が修正されました。
  • ライブラリ内インライン化の際にコンパイラが誤ってインライン可能フラグをつけていた不具合が修正されました。
  •  カスタムポートでclose引数を指定しても呼ばれていなかった不具合が修正されました。
変更された機能
  • パターンマッチライブラリ(match)がAndrew Wright氏のものからAlex Shinn氏のものに変更されました。
  • current-directoryがパラメータ化されました。(current-directory "somewhere")で(set-current-directory "somewhere")と同様の働きをします。これによって(srfi :39)にあるparameterizeとの親和性があがりました。
  • ソケットライブラリ(sagittarius socket)からエクスポートされていた定数が、define-constantで定義されたものと同様の振る舞いをするように変更されました。
新たに追加された機能
  • Zlib圧縮ライブラリ(rfc zlib)が新たに追加されました。
  • プログラム引数処理ライブラリ(srfi :37)が新たにサポートされました。
  • ハッシュテーブルユーティリティ(util hashtables)が新たに追加されました。


個人的に割りといい感じになってきた感がある。正規表現でクラスのサポートをするために文字セットを組み込みにしないと。

2011-11-10

定数畳み込み

コンパイラの最適化をもう一歩進めてみた。
実は以前から構文としてはdefine-constantをサポートしてはいたんだけど、何もしない単なるサポートにしかなっていなかった。
っで、せっかくライブラリのインライン化とかやったので定数も畳み込んでしまおうと思い立ってやってみた。

基本方針は以下の通り。
  • 定数のみ。
  • exportで定義されていない。
  • コンパイラの最適化で定数になるものは含める。例えばこんなの
    (define a (car '(a b c))) ;; コンパイラは'aをaに定義する。
  • define-constantで定義されたものはライブラリ外でも参照する
とりあえず、なんとなく動くようになったっぽい。以下のコードでは定数が畳み込まれていることが確認できた。
(define-constant a (car '(a b c))) ;; carはコンパイル時に計算される(可能なら)

(define (test)
  (print a))
(disasm test)
;; size: 5
;; 0: CONST_PUSH a <-- シンボルaがそのまま渡されている
;; 2: GREF_TAIL_CALL(1) #<identifier print#user(0x5fd1e0)> ;; print
;; 4: RET

(library (inner)
    (export const-value)
    ;; define-constant は(sagittarius)ライブラリにて提供
    (import (sagittarius))
  (define-constant const-value 10)
)

(library (test)
    (export test2)
    (import (rnrs)
     (inner))

  (define a (+ 1 2 3)) ;; a はexportされていない

  (define (test2)
    (display a)
    (display const-value)
    (newline))
)

(import (test))
(disasm test2) 
;; size: 13
;; 0: FRAME 4
;; 2: CONSTI_PUSH(6) <-- 計算された後の定数になっている
;; 3: GREF_CALL(1) #<identifier display#|(test)|(0x73d018)> ;; display
;; 5: FRAME 4
;; 7: CONSTI_PUSH(10) <-- GREF const-valueではない
;; 8: GREF_CALL(1) #<identifier display#|(test)|(0x73efa8)> ;; display
;; 10: GREF_TAIL_CALL(0) #<identifier newline#|(test)|(0x73ef30)> ;; newline
;; 12: RET
ま、まずまずでしょう。Gambitのベンチマークにはなんら影響が出ないところが多少以上に悲しいが。(あれらはR6RSのライブラリを使ってないから、最適化がかからん)
もう少し寝かせてから0.2.2をリリースしよう。

2011-11-09

割と大きめな岐路

このサイズの岐路は3度目なのだが、2度あることはじゃないけど、3度目がきたわけだ。
(まだ、不確かな要素が多いので、歯に衣を着せた物言いだったり)

正直迷ってはいたりするのだが、さてどうしたものか。別に今の位置にそう固執しているわけではないのだが、割と気に入っていたりはするので、迷うわけだ。
う~ん、どうしたものだろう。

2011-11-02

ドキュメント

オープンオフィス(以下OOo) をやめて、RacketのScribbleに乗り換え中。
乗換えと言っても、Racketに付属しているものをそのまま使うのではなく、ドキュメント生成スクリプトも同時に書いている。なので、コンセプトだけを使うといった感じ。
Chibi Schemeに触発された感はあるが。

その際にあんまりうまいこと解決方法が見つからなかったのが以下のセクションを拾って目次に変換する処理。
用件としては、以下のようになっているリストをulとliで作成されたsxmlに変換すること。
((section
  (@ (tag "tag1") (number "1"))
  "Section 1")
 (subsection 
  (@ (tag "tag1.1") (number "1.1"))
  "Subsection 1.1")
 (subsection 
  (@ (tag "tag1.2") (number "1.2"))
  "Subsection 1.2")
 (section
  (@ (tag "tag2") (number "2"))
  "Section 2")
 (subsection 
  (@ (tag "tag2.1") (number "2.1"))
  "Subsection 2.1")
 (subsubsection 
  (@ (tag "tag2.1.1") (number "2.1.1"))
  "Subsection 2.1.1")
 (sub*section 
  (@ (tag "tag2.1.1.1") (number "2.1.1.1"))
  "Subsection 2.1.1.1")
 (section
  (@ (tag "tag3") (number "3"))
  "Section 3"))
期待される出力
(div (@ (id "G137") (class "table-of-contents"))
     (ul (@ (class "section"))
  (li (@ (class "section"))
      (a (@ (href "#tag1"))
  (span (@ (class "section-number")) "1")
  "Section 1")
      (ul (@ (class "sub-section"))
   (li (@ (class "sub-section"))
       (a (@ (href "#tag1.1"))
   (span (@ (class "section-number")) "1.1")
   "Section 1.1"))
   (li (@ (class "sub-section"))
       (a (@ (href "#tag1.2"))
   (span (@ (class "section-number")) "1.2")
   "Section 1.2"))))
  (li (@ (class "section"))
      (a (@ (href "#tag2"))
  (span (@ (class "section-number")) "2")
  "Section 2")
      (ul (@ (class "sub-section"))
   (li (@ (class "sub-section"))
       (a (@ (href "#tag2.1"))
   (span (@ (class "section-number")) "2.1")
   "Section 2.1")
       (ul (@ (class "sub-sub-section"))
    (li (@ (class "sub-sub-section"))
        (a (@ (href "#tag2.1.1"))
    (span (@ (class "section-number"))
          "2.1.1")
    "Section 2.1.1")
        (ul (@ (class "sub-sub-sub-section"))
     (li (@ (class "sub-sub-sub-section"))
         (a (@ (href "#tag2.1.1.1"))
     (span (@ (class "section-number"))
           "2.1.1.1")
     "Section 2.1.1.1"))))))))
  (li (@ (class "section"))
      (a (@ (href "#tag3"))
  (span (@ (class "section-number")) "3")
  "Section 3"))))
単にulとliで構成されたリストにちょっとしたhtmlのメタ情報が入ったものといった感じ。これが結構てこずった。
最終的にはこんな風になったけど、もうちょっといい感じにならないだろうか?
;; sxml toolsをふんだんに使ってます。
(define *section-classes*
  '((section       . "section")
    (subsection    . "sub-section")
    (subsubsection . "sub-sub-section")
    (sub*section   . "sub-sub-sub-section")))

(define (content-list-handler element)
  (define (process contents)
    (define (li-gen content class)
      (let* ((attrs (sxml:attr-list-node content))
      (tag   (cond ((assq 'tag attrs) => cadr)))
      (section (cond ((assq 'number attrs) => cadr)
       (else
        (assertion-violation 'li-gen
        "section is not defined" content)))))
 `((li (@ (class ,class))
       (a (@ (href ,(format "#~a" tag)))
   (span (@ (class "section-number")) ,section)
   ,@(map phase2/dispath (sxml:content content)))))))
    (define (ul-gen class)
      `(ul (@ (class ,class))))
    (define (rec contents generator top)
      (let loop ((contents contents)
   (r top))
 (if (null? contents)
     r
     (let ((content (car contents)))
       (let-values (((class depth) (generator content)))
  (let loop ((i 0)
      (r r))
    (if (= i depth)
        (cond ((and (zero? i) ;; top
      (eq? (car r) 'ul))
        (append! r (li-gen content class)))
       (else
        (let ((tail (car (list-tail r (- (length r) 1)))))
          (cond ((eq? (car tail) 'ul)
          (append! tail (li-gen content class))
          r)
         (else
          (let ((ul (ul-gen class)))
     (append! ul (li-gen content class))
     (if (eq? (car tail) 'li)
         (append! tail (list ul))
         (append! r (list ul)))
     r))))))
        (loop (+ i 1)
       (let((rr (car (list-tail r (- (length r) 1)))))
         (if (eq? (car rr) 'li)
      rr
      (car (list-tail rr (- (length rr) 1))))))))
  (loop (cdr contents) r))))))

    (define (section-generator element)
      (define len (length *section-classes*))
      (define sections (map car *section-classes*))
      (cond ((assq (car element) *section-classes*)
      => (lambda (slot)
    (let ((name (car slot))
   (class (cdr slot)))
      (values class (- len (length (memq name sections)))))))
     (else
      (assertion-violation 'section-generator
      "unknown tag" element))))
    ;; assume first one is section
    (rec contents section-generator (ul-gen "section")))

  (let* ((contents (*table-of-contents*))
  (attr (sxml:attr-list-node element))
  (id   (cond ((and attr (assq 'id attr)) => cadr)
       (else (symbol->string (gensym))))))
    `(div (@ (id ,id)
      (class "table-of-contents"))
   ,(process contents))
    )
  )
リストの作成を破壊的に行っているので、なんとなく反則技を使っている気分。いい点は、*section-classes*に追加のサブセクションを足せば簡単にネストできることか。4つ以上サブセクションが要るドキュメントなんて読みたくないが・・・

2011-10-28

とある面接での質問

つい最近、面接を受けたのだがその際に質問された項目の一つ。 「リストとマップとセットの違いについて説明してください」 この質問を聞いた際に、頭の中で、 「listとmapとset!(これ重要)について説明してください」 と変換したため、何を言っているんだろう?と本気で悩んでしまった。 本来の意味では「コレクションとしての」が接頭辞として付くと分かりやすいのかな? ただ、質問の意図は正直今でも分からず、違いを理解せずに使ってるやつなんているの?と思ってしまう。まぁ、自分の理解が正しいか不安にはなるので、ここで晒してみよう。晒すのが答えなのか、恥なのかは分からないけど。 リスト:要は可変配列、要素は重複を許す。 マップ:キーと値をの対を要素として持つ集合。キーの重複は許されない場合が多い。(許す実装をどっかで見た、気のせいかも) セット:集合。要素の重複を許さない。 順序が保障されるかどうかは実装によるのでどうでもいい。ArrayListなら入れた順番だし、LinkedListなら要素の値で順序が保障される(本当?あんまり使わないから分からん)といった感じ。 これが答えられない、もしくは大きく理解がずれてるとしたらそれはそれで問題な気がする。

2011-10-25

R7RSのドラフト4

45時間前にScheme Working Groupに載ってたので読んでみた。なんだかタイムリーに読んだ気分に。
まぁ大きな点はドラフト3から変わらないだろうと踏んで、モジュールだけを読んでみた。ここがmoduleからdefine-libraryに変わるので。
ぶっちゃけ名前が変わっただけだったので特に特筆すべきところはないかなぁ(まだ、しっかり読んでないけど)
モジュールシステムの項で気になる点:
A library definition takes the following form:
    (define-library <library name>
        <library declaration> ... )
<library name> is a list whose members are identifiers or unsigned exact integers that is used to identify the library uniquely when importing from other programs or libraries. Libraries whose first identifier is scheme are reserved for use by this report and future versions of this report. Libraries whose first identifier is srfi are reserved for libraries implementing Scheme Requests for Implementation.
A <=<library declaration> may be any of:
  • (export <export spec> ... )
  • (import <import set> ... )
  • (begin <command or definition> ... )
  • (include <filename1> <ilename2> ... )
  • (include-ci <filename1> <filename2> ... )
  • (cond-expand <cond-expand clause> ... )
これってこんな風に書けるってこと?
(define-library (test)
  (begin (define a 'a))
  (import (scheme base))
  (export a)
)
リファレンス実装(だと思われる)chibi-schemeで試してみたが、どう動かすのかまったく分からん。 まぁ、この程度の違いならマクロで吸収できるなぁ・・・(いろいろ面倒な部分もあるので)R7RS対応にするかは分からないけど。

O(n^2)正規表現(from Island Life)

Gaucheの河合史郎さんのBlogのエントリーO(n^2)の正規表現をみて、そういえばSagittariusでは正規表現のベンチマークとったことないなぁと思いやってみた。 そのままでは当然動かないので、コンバート。
こんな感じ。
(import (sagittarius regex)
 (srfi :1)
 (srfi :13)
 (rnrs))

(define format.6f
  (lambda (x)
    (let* ((str (number->string (/ (round (* x 1000000.0)) 1000000.0)))
           (pad (- 8 (string-length str))))
      (if (<= pad 0)
          str
          (string-append str (make-string pad #\0))))))

(define-syntax time
  (syntax-rules ()
    ((_ expr)
     (let-values (((real-start user-start sys-start) (time-usage)))
       (let ((result (apply (lambda () expr) '())))
         (let-values (((real-end user-end sys-end) (time-usage)))
           (let ((real (format.6f (- real-end real-start)))
                 (user (format.6f (- user-end user-start)))
                 (sys  (format.6f (- sys-end sys-start))))
             (format #t "~%;;  ~a real    ~a user    ~a sys~%" real user sys)
        (flush-output-port (current-output-port))))
         result)))))

(define (time-this runs thunk)
  (time
   (do ((i 0 (+ i 1)) (r (thunk) (thunk)))
       ((= i runs)))))
       
(define rx1 (regex "[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+"))

(define (regex-test rx text runs)
  (display (string-length text))
  (time-this runs (lambda () (regex-replace-all rx text " "))))

(define (repeat s c) (string-concatenate (make-list c s)))

(print rx1)
(regex-test rx1 (repeat "abcdefgh" 10) 20)
(regex-test rx1 (repeat "abcdefgh" 50) 20)
(regex-test rx1 (repeat "abcdefgh" 100) 20)
(regex-test rx1 (repeat "abcdefgh" 500) 20)
(regex-test rx1 (repeat "abcdefgh" 1000) 20)
結果は散々であった。以下結果。(Core2Duo 3GHz)
#
80
;;  0.005000 real    0.000000 user    0.000000 sys
400
;;  0.100000 real    0.110000 user    0.000000 sys
800
;;  0.400000 real    0.375000 user    0.000000 sys
4000
;;  9.965000 real    9.937000 user    0.000000 sys
8000
;;  39.94300 real    39.70300 user    0.000000 sys
いやぁ、速くはないだろうなぁとは思っていたが、ここまで遅いとは。
Sagittariusの正規表現はJavaのコードを流用(もちろんCに書き直したが)しているので、マッチしなかったら一文字進めて再試行するようになっているので、入力文字列がマッチしないと結構不利にはなる。特にregex-replace-allみたいなのは痛い。
今回のケースだと、クラスのマッチはあんまり遅くないんだよなぁ、組み込みのcharsetを入れても改善の余地は少なさそう。さて、どうしようかね。

2011-10-24

Sagittarius 0.2.1リリース

0.2.0の時はブログに書き忘れたが、今回は書いておこう。
短めのリリース周期で行きたいと思い(どうせ長続きしないが)、早めに出してみた。
バグフィックスリリースなので、目新しい機能は特になし。

修正されたバグ
  • SRFI-42を記述するsyntax-rulesがうまく動かないのが修正されました
  • ライブラリのrenameインポートが動作していないのが修正されました
  • if文内でeqv?などインラインアセンブラに展開され、かつその中でlet式を使用している場合にコンパイラが不正なコードを出力する問題が修正されました
  • (apply = '(1 1 1))が#fを返す不具合が修正されました
  • load関数が#!r6rsや#!compatibleなどのフラグを上書きする不具合が修正されました
新たに追加、更新されたライブラリ
  • (util port)、(util file)のユーティリティライブラリが追加されました
  • (text sxml serializer)が追加されました。これでSXMLからXMLへの変換が可能です
  • (text sxml sxpath)が更新されました。名前空間に対応しているはずです
  • 移植性のためSRFI-38が追加されました。(import (srfi :38))でread/ss及びwrite/ssが使用可能です
  • (text sxml ssax)及び(text parse)のドキュメントが追加されました
 コンパイル時の注意:
テストケースが大幅に追加されたことに加え、sxpathのテストケースが膨大であるために、make testを行うとメモリが足りずにプログラムが終了する可能性があります。キャッシュ化されたものは問題なく動くので、上記の問題が発生した場合は再度make testコマンドを実行してみてください。

さて、誰がこれを見てダウンロードしてみようなんて思うのだろうか・・・割とまじめに書いてみたが・・・

2011-10-17

自分の価値について

いろいろあって最近自分の価値というものについて考えることが多くなった。
そもそも何を持って価値とするかというのは難しいしところだが、今回は自分の市場価値というところに焦点を絞ってみる。(というか、そこについて考えているだけ)
また、細かいことだけど、ここでは他人からの評価+αを価値と呼ぶことにする。

事の発端はいたって簡単で、最近結構頻繁にオファーのメールやら電話やらをもらうことがある。その際に端的に言えば今の職場より割りといい額を提示されているのでそこそこ評価されているのかなぁと感じるわけだ。
でも自分では自分は人と同じもしくはそれ以下くらいの価値かなぁといつも思っていて、「そんなにもらう仕事俺にできるんかい?」と割と躊躇することが多い。つまるところ他人の評価≠自己評価になっていると言うわけだ。
市場という目で見た場合、評価≒賃金ということができる。(まぁ、コンピュータジョークでは無能な人ほど稼ぐなんてジョークがあるがそれは置いておこう)。とりあえず客観的に自分を見てみた場合、30歳(もうすぐ)男、開発者、経験7年(より少し少ないが)、英語話せる。こんなところだろうか?細かく見ればもう少しあると思うが。
何が難しいかといえば、表面から見えるものと中身が違うというのは多々あるので、上記のスペックだけでは何も決められないというところだ。例えば本人が「経験あります、できます」と言ったところでそれを証明するものがなければ単なるやる気ありくらいな評価だろう。特にプログラマという立場なので何をなしたかを証明しにくい。(納品物は基本非公開だし、数字に表しにくい)
履歴書上でこれの経験がある、あれの経験があると言っても、末端の部分を触っただけでも経験だし、コアな部分から使い切っても経験だ。
となれば、他人からの評価を得やすくするために自分を着飾る必要があるのだろう。例えば履歴書で嘘ではないが少し大げさに書くとか、実際には末端の部分をやっただけだがあたかもすべてを知っているように書くとか。正直、こういったことはあまり好きではなく、またそれをすると過大評価を買ってしまうのではないかと思ってしまう。(もちろん評価者がそれを見越した過小評価をすればいいのかもしれないが)

なんとなくまとまりのない文章になってしまったが、言いたいこととしては価値を見定めるのは難しいということだ。それが自分自身のものであればなおさら。
でも、転職ということを考えれば自分の市場価値を見定めれた方が有利な気がする。もしくは履歴書を着飾れたらとか。

2011-10-10

DBI/DBDを導入

CLOSを使わずレコードだけでやったのでDBDの実装が面倒ではあったが、使う分にはそんなに気にならないレベルになったと思う。
実際のコードはこんな感じで書ける。
(import (dbi))
;; とりあえず組み込みでODBCをサポート。
;; 他に標準になっているデータベースアクセス方式があったらサポートするかも。
(define conn (dbi-connect "dbi:odbc:server=XE"
			  :username "username"
			  :password "password"))
;; プレースホルダーに直接値を渡せる
(let ((query (dbi-prepare conn
			  "select * from a_table where id >= ?"
			  10000)))
  ;; (dbi-bind-parameter query 1 10000) ;; こう書いてもOK
  (dbi-execute! query) ;; 実行自体は何も返さない。
  (print (dbi-fetch-all! query))) ;; dbi-fetch!なら一行返す。なければ#f
(dbi-close conn)
直接ODBCのAPIを叩くよりははるかに楽。SQLのDATE型とかは(DBDの実装依存なので、組み込みのODBCではだけど)srfi-19の日付型に変換して、BLOBや長いテキストはポートで返す(現状の実装だと結局全部読み込むのであまり意味はないが、そうするべきという意味合いで)。
なんとなく、仕事で使うような機能はほぼそろいつつあるなぁ。

2011-10-08

ODBCを入れてみた

DBI/DBDの実装をしようと思い、組み込みで1つ入れるには何がいいかなぁと考えた結果ODBCにした。
理由は割りと単純で、
  • 「ある程度」実装依存の部分を回避できること。
  • PostgreSQL, MySQL, Oracleなど実装を限定してしまうとビルド時にそれらが入ってないと組み込めないこと。
  • 一応ISOの標準になっており、(既に)Microsoftの独自実装というわけでもないこと。
といった感じ。特に3つ目は割りと重要で、これのおかげ(か、どうかか知らんが)で Unix系プラットフォームでもODBCが使えるらしい。
とりあえず初期バージョンを作ってみて、CSVファイルを検索してみた。

こんな感じ
(import (odbc))
;; DSNはODBCの設定でつけた名前
(define dsn "TEST")
(define env (create-odbc-env))
;; 今回はCSVなのでユーザー名、パスワードは要らない。
;; Oracleなどに接続する際は必要になる
(define dbc (connect! env dsn "" ""))
;; もちろんプレースホルダーも使える
(define stmt (prepare dbc "select STREET from [ken_all_rome.csv] where CODE > ? and CODE < ?"))

(bind-parameter! stmt 1 23203)
(bind-parameter! stmt 2 23205)
(execute! stmt)
;; 警告レベルの例外を投げたりするので、with-exception-handlerで囲む必要がある。
(with-exception-handler
 (lambda (e)
   (report-error e))
 (lambda ()
   ;; fetch!は行が取得できたかどうかを返す while (fetch(stmt)) ... なイメージ
   (let loop ((next? (fetch! stmt)))
     (when next?
       ;; 現状では列名では取得できない。この辺は改善の余地あり。
       (let ((col1 (get-data stmt 1)))
	 (print col1)
	 (loop (fetch! stmt)))))))
;; 接続解除
(disconnect! dbc)
基本的にはDBDの低レベルAPIな位置づけなので、あまり高機能にする必要もないのだが、Prepared Statement(日本語訳しらない)に束縛された値のリセット機能はいれてもいいかもしれない。あと、DBD用に結果列名の取得とかも。
文字列周りをどうするか考える必要があるかもしれない。現状だとUTF-8しか使えないが、CSVとか使うならSHIFT-JISがどうしても必要になってくる。コネクション辺りにトランスコーダーを持たせるか。(コネクションごとでいいよなぁ?)

どうでもいい話ではあるのだが、ODBCのAPIは資料が少ない気がする。いや、MSDNとかあるんだけど、例えばOracleのVARCHAR2は定義されたSQL型に入ってなくてえらく困った。
あと、SQLBindColとかSQLBindParameterとかの説明が足らん気がする。
ODBC Programmer's Referenceここがすごく役に立った。特にChapter9のBinding Parameters。MSDNには明示的に書いてないこと(読み飛ばしたのかもしれん)が普通に書かれてるのと、サンプルが多くてお勧め。

2011-10-05

Cygwinのヒープ

今更ながらだが、Cygwinのヒープは拡張できることが分かった。
参照:Changing Cygwin's Maximum Memory

何故これが必要だったかというと、SagittariusのビルドをX60で行った際に頻繁にWin32 487エラーが発生していたため。
おそらく原因はここにあるものだろう。LogicoolのWebcamのドライバー入ってるし。
とりあえず、512MBまで増やしてビルド再開。動いている。

call/ccを何とかしたった

方言かこれ?まぁいいや。

call/ccのコピー回数を2回から1回に減らした。今のところばっちり動いているのでOKだろう。
ここまできたらベンチマーク。最初ctakとfibcを除くすべてが遅くなったのであせったが、フルビルドしたら戻った。
結果をmosh(0.2.6)と比較(Core2Duo 3GHz, Cygwin on Windows XP, memory 3GB)
まずはSagittarius:
;;  GABRIEL

;;  boyer   (x3)
;;  0.664000 real    0.610000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  browse  (x120)
;;  6.073000 real    6.031000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  cpstak  (x80)
;;  0.969000 real    0.969000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  ctak    (x25)
;;  2.972000 real    2.953000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  dderiv  (x160000)
;;  1.307000 real    1.297000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  deriv   (x320000)
;;  2.092000 real    2.078000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  destruc (x100)
;;  1.514000 real    1.500000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  diviter (x200000)
;;  1.698000 real    1.703000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  divrec  (x140000)
;;  1.307000 real    1.312000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  puzzle  (x12)
;;  0.619000 real    0.625000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  takl    (x35)
;;  0.704000 real    0.703000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  triangl (x1)
;;  0.677000 real    0.672000 user    0.000000 sys
;;  ----------------------------------------------------------------

;;  ARITHMETIC

;;  fft     (x200)
;;  0.419000 real    0.422000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  fib     (x1)
;;  1.542000 real    1.547000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  fibc    (x50)
;;  0.994000 real    0.984000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  fibfp   (x1)
;;  5.692000 real    5.610000 user    0.047000 sys
;;  ----------------------------------------------------------------
;;  mbrot   (x10)
;;  1.676000 real    1.656000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  nucleic (x1)
;;  1.211000 real    1.188000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  pnpoly  (x10000)
;;  0.639000 real    0.641000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  sum     (x1000)
;;  0.360000 real    0.359000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  sumfp   (x600)
;;  1.162000 real    1.157000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  tak     (x200)
;;  0.592000 real    0.593000 user    0.000000 sys
;;  ----------------------------------------------------------------

;;  MISCELLANEOUS

;;  conform (x4)
;;  0.842000 real    0.844000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  earley  (x20)
;;  0.366000 real    0.375000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  graphs  (x15)
;;  0.572000 real    0.562000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  mazefun (x100)
;;  0.566000 real    0.563000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  nqueens (x150)
;;  0.354000 real    0.344000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  paraffins (x100)
;;  0.616000 real    0.625000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  peval   (x20)
;;  0.949000 real    0.938000 user    0.000000 sys
;;  ----------------------------------------------------------------
;;  ray     (x1)
;;  1.656000 real    1.610000 user    0.046000 sys
;;  ----------------------------------------------------------------
;;  scheme  (x3000)
;;  0.852000 real    0.844000 user    0.000000 sys
;;  ----------------------------------------------------------------
browse及びfibfpが遅いが他はまずまず。ctakは改善前から4秒速くなってるので劇的に良くなったといえるだろう。

次にmosh:
;;  GABRIEL

;;  boyer   (x3)
;;4.444999933242798 real 4.406 user 0.0 sys
;;  ----------------------------------------------------------------
;;  browse  (x120)
;;5.337000131607056 real 5.327999999999999 user 0.0 sys
;;  ----------------------------------------------------------------
;;  cpstak  (x80)
;;1.5829999446868896 real 1.5630000000000006 user 0.0 sys
;;  ----------------------------------------------------------------
;;  ctak    (x25)
;;5.3460001945495605 real 5.311999999999999 user 0.0 sys
;;  ----------------------------------------------------------------
;;  dderiv  (x160000)
;;2.8910000324249268 real 2.875 user 0.0 sys
;;  ----------------------------------------------------------------
;;  deriv   (x320000)
;;2.3340001106262207 real 2.2970000000000006 user 0.0 sys
;;  ----------------------------------------------------------------
;;  destruc (x100)
;;1.9910001754760742 real 2.0 user 0.0 sys
;;  ----------------------------------------------------------------
;;  diviter (x200000)
;;2.055999994277954 real 2.0470000000000006 user 0.0 sys
;;  ----------------------------------------------------------------
;;  divrec  (x140000)
;;1.4830000400543213 real 1.4529999999999994 user 0.0 sys
;;  ----------------------------------------------------------------
;;  puzzle  (x12)
;;1.0709998607635498 real 1.0779999999999994 user 0.0 sys
;;  ----------------------------------------------------------------
;;  takl    (x35)
;;0.9110000133514404 real 0.907 user 0.0 sys
;;  ----------------------------------------------------------------
;;  triangl (x1)
;;0.9219999313354492 real 0.9060000000000024 user 0.0 sys
;;  ----------------------------------------------------------------

;;  ARITHMETIC

;;  fft     (x200)
;;1.8899998664855957 real 1.8119999999999976 user 0.0 sys
;;  ----------------------------------------------------------------
;;  fib     (x1)
;;1.7780001163482666 real 1.75 user 0.0 sys
;;  ----------------------------------------------------------------
;;  fibc    (x50)
;;1.7349998950958252 real 1.7040000000000006 user 0.0 sys
;;  ----------------------------------------------------------------
;;  fibfp   (x1)
;;8.138999938964844 real 7.780999999999999 user 0.0 sys
;;  ----------------------------------------------------------------
;;  mbrot   (x10)
;;3.375999927520752 real 3.344000000000001 user 0.0 sys
;;  ----------------------------------------------------------------
;;  nucleic (x1)
;;1.9010000228881836 real 1.8590000000000018 user 0.0 sys
;;  ----------------------------------------------------------------
;;  pnpoly  (x10000)
;;0.7100000381469727 real 0.7029999999999959 user 0.0 sys
;;  ----------------------------------------------------------------
;;  sum     (x1000)
;;0.4719998836517334 real 0.45300000000000296 user 0.0 sys
;;  ----------------------------------------------------------------
;;  sumfp   (x600)
;;1.9199998378753662 real 1.9059999999999988 user 0.0 sys
;;  ----------------------------------------------------------------
;;  tak     (x200)
;;0.7339999675750732 real 0.7349999999999994 user 0.0 sys
;;  ----------------------------------------------------------------

;;  MISCELLANEOUS

;;  conform (x4)
;;0.009999990463256836 real 0.015000000000000568 user 0.0 sys

;; wrong result: ("(b ^ d)" "c" "(a ^ c)" "d" "any" "none")
;;  ----------------------------------------------------------------
;;  earley  (x20)
;;2.930999994277954 real 2.9070000000000036 user 0.0 sys
;;  ----------------------------------------------------------------
;;  graphs  (x15)
;;2.378000020980835 real 2.3429999999999964 user 0.0 sys
;;  ----------------------------------------------------------------
;;  mazefun (x100)
;;0.8310000896453857 real 0.8290000000000006 user 0.0 sys
;;  ----------------------------------------------------------------
;;  nqueens (x150)
;;0.6979999542236328 real 0.6869999999999976 user 0.0 sys
;;  ----------------------------------------------------------------
;;  paraffins (x100)
;;1.2379999160766602 real 1.2340000000000018 user 0.0 sys
;;  ----------------------------------------------------------------
;;  peval   (x20)
;;1.0770001411437988 real 1.0790000000000006 user 0.0 sys
;;  ----------------------------------------------------------------
;;  ray     (x1)
;;3.0359997749328613 real 3.0 user 0.015 sys
;;  ----------------------------------------------------------------
;;  scheme  (x3000)
;;1.5360000133514404 real 1.531000000000006 user 0.0 sys
;;  ----------------------------------------------------------------
正直moshより速くなったと言っても問題ない気がしてきた。browseが少し負けてるか。何でだろう?boyerの桁が違うのはmoshはdisplay closureを使ってるので名前付letのループがきついのだろう。
GaucheとYpsilonをここに載せないのはあれらは異次元の速さだから。まだしばらく勝てそうにない。

ドキュメントの整備が終わったら0.2.0をリリースしよう。

2011-10-04

call/ccを何とかしたい

何が問題か?call/ccが遅い。
どの程度?Gambitベンチマークのctakが7秒(Core2Duo 3GHz)

とりあえず、前回読んだ論文の内容を実装するのは実は諦めていて、というか上記のベンチマークのような使い方をすると(んなことせんだろうけど)、結局ヒープ割り当てが増えるのと、BoehmGCを使っている以上、一度割り当てたメモリの部分開放ができないので(必要か?)ちょっと断念。
なんか目処が立ったらもう一回チャレンジする。

じゃあどうするか。とりあえずGauche、Ypsilon方式に作成時にヒープにコピーして呼び出しにはコピーをしない方法にしたい。
問題は静的リンクじゃないからスタック(というかフレーム)を単純にコピーしただけだと問題が起きること。
最近行った改善(改悪かも)で、Sagittariusのスタックは以下のように使用されるようになった。
letでスタックを伸ばすイメージ

before            preparing        after
+----------+< SP  +----------+< SP +----------+< SP
|  var 2   |      | v for F1 |     | new var 3|
+----------+      +----------+     +----------+
|  var 1   |      |   F1     |     |  var 2   |
+----------+< FP  +----------+     +----------+
|  Frame   |      |  var 2   |     |  var 1   |
+----------+      +----------+     +----------+< FP
                  |  var 1   |     |  Frame   |
                  +----------+< FP +----------+
                  |  Frame   |
                  +----------+
* F1 = 積みかけのフレーム(let変数の初期化時など)
こうしたおかげで、letをどれだけ書いても単にスタックが伸ばされるだけでほぼノーコストでローカル変数にアクセスできるようになった。
問題は、これを実現するために積みかけのフレームさえも(ダミーとしてだが)ローカル変数としてカウントしていること。実際、preparingの中でもう一つフレームが足されてかつ、F1の上にある値にアクセスしようとした際(ありえるのかは知らんが、やる必要があったのでありえるのだろう)には、LREF(3)ではなくLREF(10)になる。(現状フレームは7ワード占拠する)。
となると、どのフレームに何が引っ付いているのかというのが非常に把握しづらくなる。GaucheのようにARGP(引数フレームポインタ?)を導入してやるのもありなのかもしれないけど、静的リンクが無いからそのフレームより上(下?)にあるものを参照するときに困りそう。
さて、どうしたものか・・・

脱Display closure

正確には脱ではなく、減ではあるが。

call/ccを速くしようとしていた際に、display closureをletごとに作ると不便が生じることがわかったのでletではスタックを伸ばしてdisplay closureを作らないことにした。
そのおかげで、LET_FRAME, POP_LET_FRAME, DISPLAY, MARKの4命令が不要になり、またSHIFTJの意味合いも変わった。
上記の4命令は元をたどればmoshからもらったものだったので、脱moshともいえるかもしれない。(まぁ、moshにPOP_LET_FRAMEとMARKはなかったのだが)
Display closureをやめたからといって静的リンクにしたわけでもなく、本当にスタックを伸ばした感じ。なので、ちょっとletが深くなるとLREF(20)とか見えるようになった。いいか悪いかはしばらく使ってから確かめる。

この変更のおかげでGambitベンチマークのboyerが2秒から0.6秒まで短縮(Core2Duo 3GHz)。逆にctakは2秒増加という結果になり、call/ccがより重たいものになった(その他call/ccを使わないものは劇的ではないが改善された)。理由はいたって簡単で、ヒープの使用量が減り、スタックの使用量が増えたから。また、let, letrec, receive, 及び名前付letなどのループのコンパイル時間が短縮された(はず)。
call/ccの改善だったのに遅くなったという面を除けば悪くない。

2011-09-29

9月が終わる

10月3日はライデンの80年戦争終了記念日(だよな・・・?)
毎年この時期になると街はお祭り準備でバスやらの公共交通機関が半分麻痺状態になる。まぁ、職場はロッテルダムなのでライデンのバスはあんまり使わないんだけど。

今年で3度目。もう少しで今年も終わり。う~ん、一年は短い。もっといろいろやりたかったんだけどなぁという気もしているが、あと2ヶ月でどこまでできるか?

なんとなくお祭り前夜をみて思った。

2011-09-24

call/cc実装論文

Chez Schemeに使われている(らしい)call/ccの実装論文を読んでいるのだが、これで動く理由が分からない。
正確にはこれをSagittariusに適用できるか分からないか。

これが正しい理解かは微妙だが、大雑把に言えば継続が捕捉された時点のスタックポインタ以前のスタックを凍結、スタックフレームに以前のスタックポインタを足す。っで、捕捉された継続が呼び出されたら凍結されたスタックを現在のスタックに置き換える。
確かにこの方法なら作成時にスタックのコピーが無いので作成はほぼノーコスト。でもこれってcall/ccから脱出するとき困らんかな?
call/ccから脱出するときにどうしてもスタックのアンダーフローが検出されるので捕捉された継続を戻す必要がでる気がする。それともなんらか別の方法でその辺は何とかしてるのかな?

思考レベルだがこれを適用する際に問題になりそうなのは積みかけのフレームだと思ってる。例えば以下のケース:
(+ 1 (call/cc (lambda (c) 2)) 3)
というのがあったとして、call/ccが呼ばれた際のスタックは以下のようになる。(呼ばれた時点で、call/ccに渡されたlambda内ではない)
+-----------------+ <-- sp
| (lambda (c) 2)  |
+-----------------+ <-- fp
| Frame(call/cc)  |
+-----------------+ 
|       1         |
+-----------------+
|  Frame(+)       |
+-----------------+
Sagittariusでは上記のすべてが別ヒープにコピーされて、継続が呼び出された際にスタックに戻される。スタックVMで実装する際の一番重たい実装方法だ(よね?)
っで、上記の論文を考えると、数値2が返された段階でアンダーフローが検出される。その際上記のスタックは凍結されているので動かせない、つまり新スタックフレームに既に積まれた数値1とFrame(+)を積む必要がある。
あぁ、アンダーフローが検出された際って新スタックフレームは空であることが保障されているのでフレームポインタのことを考えなければ単にコピーするだけか。ヒープ割り当ててコピーする処理がコピーだけになったと思えば、悪くないだろうか?
理想としてはcall/ccの呼び出しで捕捉された継続が呼び出されないと分かっているなら(上記の例みたいな)、スタックを凍結せずそのままってのが一番だわな。この辺はコンパイラに頼るほかないが。

ブランチ切ってやってみるか。

2011-09-19

結局

Display closureをスタックに移すとcall/ccが激重になることが分かったので、ちょっと整理する程度にとどめた。おかげでインストラクションの意味がかなりすっきりしたと思う。
Gambitのベンチマークもbrowseとctakを除けばほぼmoshと同等かそれ以上に数値を記録しているのでまぁいいだろう。
(GaucheとYpsilonが異次元の速さなのはなぜだ?)

中身がだいぶ変わったし、マクロの書き換えもしたということで、ドキュメントの整備が終わったら2.0としてリリースしてしまおう。(このタイミングでもないと1.xのまま突き進みそうだし)
その間にcall/ccの高速化もしたいが、まぁ無理だろう。

2011-09-17

日本人がオランダに長く居すぎてしまったと感じるとき その2

調子にのってというかふと思いついたのでその2。
  1. 財布の中に20ユーロ入っていればOKと思うとき
  2. 雨が降っても傘をささないとき
  3. ビデオレンタル屋でAVがワゴンで売られていてもなんとも思わないとき
  4. etos(日本で言う杉薬局みたいなの)に大人の玩具が置いてあってもなんとも思わないとき
相変わらず思いつかなかった。解説が必要なのはは1かな?
ATMカードがあれば大抵の場所で支払いOKなので、そんなに持ち歩かなくてもいいんです。英語はDebitだったかな?オランダではPINっていいます。

いきなり雨に降られて濡れ鼠になりつつビデオレンタル屋にいったのでふと思いついた。AVはマジでワゴンで売られてます(普通の本屋にもあるという)。でもレンタル用のコーナーは一応分けられてる不思議。

2011-09-16

とりあえず

boyerが走るくらいの物まではできた(R6RSのテストはSEGVる)。
結果としては2倍から速く、GCも12回と明らかに違う。やる価値はありそうだ。

ここで問題が一つ。
今までヒープに置いていたものをスタックに置くようにしたのでものすごい勢いでスタックを食いつぶす。let*とか使ってると悲惨なことになる。さらにスタックの拡張が不完全だったというのもあり食いつぶすとSEGVる。
スタックの拡張については別に見直す必要があるが(おそらくcall/ccもだろう、うぅ・・・)、それより前に不要なDisplay closureの削除をしたい。
とりあえず思いついたのが、POP_LET_FRAMEされて且つSHIFTJでジャンプしないものはdisplay closureを辿る必要がないので削れそう。
作成時にリンクさせてしまうので、DISPLAYインストラクションにそれが末尾かどうか知らせる必要があるか。
ジャンプがあるかどうかはMARKインストラクションでマークされたdisplay closureがあればジャンプされる可能性があるとすればいいだろう。

スタックの拡張はちょっと考えないとなぁ。保存する前にごちゃごちゃやるとかだろうか?

2011-09-15

Display closureをスタックに置きたい

さすがの遅さにいらいらしたのと、これを解決しないとGaucheやYpsilonに手も届きそうにないので。

事の発端。
Gambitのベンチマークにboyerというのがあるのだが、これの速度が半端なく遅い。(さらに遅いのにbrowseがあるが、原因は一緒だろう)
あまりの遅さにGaucheの統計情報にGC回数を追加してビルドしたものと比較してみた。
GC回数脅威の320回!!!
(ちなみに、Gaucheは8回くらい)
3桁超えてきたかという感じ。

原因は以前も書いたDisplay closureで、letが連なってかつ外側のletの変数を参照してると作られる。要するに自由変数を解決するための仕組み。
これを毎回作っていたのではメモリによろしくないことが数字で出てしまっているので、なんとかスタックに作れないかなぁと試行錯誤中。

メモ:

  1. Display closureはインストラクションDISPLAYで作成される。
  2. DISPLAYは必ずLET_FRAMEの下に現れる。
  3. letが末尾呼び出しならPOP_LET_FRAMEでフレームは取り除かれる
  4. 3以外なら、ENTERとLEAVEが呼び出される
スタックにつむためには以下のことを考える必要がある。

  1. スタック領域に場所を確保し、積み上げた自由変数を移し変える
  2. 空いた場所にスライドさせる
  3. POP_LET_FRAMEが呼ばれた際にスタックにあるDisplay closureを移動させ、フレームポインタを移動させる
  4. LEAVEではDisplay closureが作られていたら除去する必要がある
ここまでやったがうまく動かない。どこかに見落としがある。どこだろう?

2011-09-14

私がSpring Webflowを使いたくないいくつかの理由

いい加減腹立ってきたわ、この糞仕様に!!

ということでどこがまずいか、どうして使ってはいけないかを書き出してみる。(だからといって現状が変わるわけではなく、単なる愚痴である)
  1. スコープまたぎができない
    • これは以前書いたけど、Ajaxとの親和性が悪すぎる
  2. とりあえずデバッグレベルですべてのデータを吐き出す
    • パスワードとか見せたくない(これも以前書いた)
  3. Default***クラスを直接newしてる
    • Defaultそのまま固定です。ユーザーは振る舞いをカスタムできません。
  4. Modelを使わないと入力チェックが非常に面倒になる
    • 2と3番の問題でフォームデータ直接チェックしたくなったけど、どうも無理臭い
  5. 設定ファイルの記述がドキュメントにほとんどない
    • カスタムはあまりするなということか?
  6. そのくせデフォルトの設定はあまりにひどい
    • 主に2,3,4番だわね
めんどくさくなったので、これくらい。使えば使うほどげんなりするのも仕様です。ってか、ほかのプロジェクトとかどうしてるんだろう?特に2番。
リリース後はデバッグログなんて出さないのかな?パッケージソフトには厳しいお言葉過ぎるよ。

ライブラリのインライン展開

1つのライブラリを最適化できないかなぁと思って、とりあえずインライン展開を試みてみた。
(大別するとグローバル最適化?でも、R6RSだとライブラリは1つのS式だから、そうでもないか)

とりあえず試したのは以下のこと。
exportされていない関数でかつ非再帰、相互参照なし、ライブラリ内で代入されていないものを抽出。
最適化時に上記の関数でかつそこそこサイズが小さいものをインライン展開。
たったこれだけ!

1個の巨大なS式と思えばまぁこんなものだろう。
で、効果があるのかちょっと検証。
以下のプログラム。
(library (test)
    (export process set-parameter!)
    (import (rnrs))

  (define *paramter* #f)

  (define (set-parameter! param)
    (set! *paramter* param))

  (define (get-paramter name default)
    (or (and *paramter* (hashtable-ref *paramter* name default))
         default))

  (define (get-count)
    (get-paramter 'count 1))

  (define (get-process)
    (get-paramter 'process (lambda args args)))

  (define (get-args)
    (get-paramter 'args #f))

  (define (process)
    (let ((n (get-count)))
      (let loop ((i 0))
    (unless (= i n)
      (let ((proc (get-process))
        (args (get-args)))
        (apply proc (list args)))
      (loop (+ i 1))))))
)


(import (test))
(define param (make-eq-hashtable))
(hashtable-set! param 'count 500000)
(hashtable-set! param 'args '(a b c d e f))
(hashtable-set! param 'process (lambda (a . b)
                 (fold cons a b)))
(set-parameter! param)
(time
 (process)
)
ちょっと作為的過ぎるだろうか?イメージとしてはオブジェクト指向のプロパティな感じということで。

実際にインストラクションのダンプを取るとprocessの中にget-count、get-process、get-argsの姿はない。

次に速度を比較。
インライン展開あり:
$ ./build/sash.exe -L. test.scm
;;  0.632000 real    0.641000 user    0.000000 sys
インライン展開なし:
$ ./build/sash.exe -fno-library-inline -L. test.scm
;;  0.681000 real    0.672000 user    0.000000 sys
40~50ms速いけど、50万回まわしてこの結果か。一応入れておくか程度だな。うっかりすると遅くなりそうで怖いが・・・

何より悲しいのはこれはGambitのベンチマークではまったく意味がないところか。

2011-09-12

Prefixつけたimportに潜む罠

R6RSでコード書いてて、
(import (prefix (rnrs) r6:))
って書く人はまぁいないだろう。onlyとかrenameならあるだろうけど。
これにこっそりと罠が潜んでいた。(というほどでもないんだけど)
たとえばこんなコード。
(define-syntax test
  (syntax-rules ()
    ((_ a b ...)
     (list a b ...))))
なんのことはないアホみたいなコードだ。
これを上記のprefix付で書くとこうなる。
(r6:define-syntax test
  (r6:syntax-rules ()
    ((r6:_ a b r6:...)
     (r6:list a b r6:...))))
でもこれYpsilonでは通らない。Ypsilonではこう書く必要がある。
(r6:define-syntax test
  (r6:syntax-rules ()
    ((_ a b ...)
     (r6:list a b ...))))
こうするとmosh及びnmoshでは通らない。でもPetite Chez Scheme(v 7.9.4)では通った。psyntax及びAndre van Tonderのsyntax-caseは厳格だということなのだろう。
ちなみにSagittariusも通らない。通るようにすることもできるんだけど、どうしようかなぁ?
こんなコード書かれないよなぁ・・・

Boehm GCが遅かった

Twitterで「速度が出ない」とつぶやいたが、原因が分かった。
まぁ、結論はすでにタイトルに書いてあるのだが、何が違ったかということをば。

調べたこと。
Gambitベンチマークのbrowseがやたら遅い。moshで5秒、Gaucheで1.7秒(速!)、Ypsilonで2.5秒、Sagittariusは12秒という結果だった。(Windows XP, Cygwin, Core2Duo 3.00GHz)
Display closureという構造をとっているmoshと比べても2倍遅いのはおかしいということで調査。
インストラクションの精査から始めて、結局以下のコードが遅くなることに気づいた
(do ((i 0 (+ i 1)))
     ((= i 10000)) ;; iを100000にすると遅くなる
  (cons 'a 'b))
何が問題だったか?
(cons 'a 'b)をコメントアウトするとmoshとの速度にほとんど差がでない。10000の時でもほとんど差が出ない。
ここでGCを疑う。
とりあえずGCの回数を出力してみたら、10000回だと9回で100000回だと10回になっていた。GCが遅い。

ここで出た疑問。なぜmoshでは遅くならないか?現状ではSagittariusもBoehm GCを使っている(絶対そのうち置き換えてやる!)が、Sagittariusでのみ問題になっている。
コンパイルオプションを調べた。moshのCygwinでのオプションは--disable-shared CFLAGS=-DGC_THREADS win32_threads=trueになっていた。
SagittariusはBoehm GCをバンドルしてないが、win32_threads=trueとかCFLAGS=-DGC_THREADSを渡してコンパイルした記憶がない。
上記を渡してリコンパイルしてみた。
5秒短縮!!!
その他のベンチマークもmoshと同等かそれ以上(遅いのもある)という結果になった。

原因探るのに2日かかったがこんな落ちとは正直思っていなかった。

追記:
自宅のX60ノートで同様にリコンパイルしてリンクしなおしたのだが、速度差はなかった。(上記のは会社のマシン^^;)
どうやらまだまだ別の場所に原因がありそうだ。

追記の追記:
やっぱりGCっぽい。別にコンパイルオプションがあるのだろうか?

2011-09-08

静的リンクにしておけば・・・

ベンチマークを取った際に2倍以上Gaucheに放されるテストが多数あったので原因を追求してみた。
端的にはこれ↓
(cond-expand
 (sagittarius
  (import (sagittarius compiler))
  (define flush flush-output-port)
  )
 (gauche
  (define compile-p2 (with-module gauche.internal compile-p2))
  (define compile-p3 (with-module gauche.internal compile-p3))
  )
 (else
  (exit)))

(define sexp '(define (lookup key table)
(let loop ((x table))
 (if (null? x)
     #f
     (let ((pair (car x))) ;; 【*1】ここが問題
(if (eq? (car pair) key)
   pair
   (loop (cdr x))))))))

(compile-p2 sexp)
(flush (current-output-port))
(compile-p3 sexp)
この結果が以下
$ sash -I"(srfi :0)" test.scm
($define () lookup
  ($lambda[lookup.0] (key[1.0] table[1.0])
    ($call[embed] ($lambda[loop.2] (x[3.0])
                    ($label #0
                      ($if ($asm (NULLP)
                             ($lref x[3.0]))
                        ($const #f)
                        ($let ((pair[2.0] ($asm (CAR)
                                            ($lref x[3.0]))))
                          ($if ($asm (EQ)
                                 ($asm (CAR)
                                   ($lref pair[2.0]))
                                 ($lref key[1.0]))
                            ($lref pair[2.0])
                            ($call[jump] ($call[embed] ($lambda[loop.2] (x[3.0])

                                                         label#0)
                                           ($lref table[1.0]))
                              ($asm (CDR)
                                ($lref x[3.0]))))))))
      ($lref table[1.0]))))
size: 5
0: CLOSURE #
  size: 37
  0: LET_FRAME(3) ;; (let loop ((x table)
  1: LREF_PUSH(0) ;; key
  2: LREF_PUSH(1) ;; table
  3: DISPLAY(2)
  4: LREF_PUSH(1) ;; table
  5: POP_LET_FRAME(1)
  6: MARK
  7: LREF(0) ;; x
  8: BNNULL 5 ;; (if (null? x) #f (le
  10: CONST #f
  12: JUMP 23 ;; #f
  14: LET_FRAME(4) ;; (let ((pair (car x))
  15: FREF_PUSH(1) ;; key
  16: LREF_PUSH(0) ;; x
  17: FREF_PUSH(0) ;; table
  18: DISPLAY(3)
  19: LREF_CAR(0) ;; x
  20: PUSH
  21: POP_LET_FRAME(1)
  22: LREF_CAR(0) ;; pair
  23: PUSH
  24: FREF(2) ;; key
  25: BNEQ 4 ;; (if (eq? (car pair)
  27: LREF(0) ;; pair
  28: JUMP 7 ;; #f
  30: FREF(1) ;; x
  31: CDR ;; (cdr x)
  32: PUSH
  33: SHIFTJ(1 1)
  34: JUMP -28 ;; #f
  36: RET

2: DEFINE(0) # ;; (define (lookup key
4: HALT
もう一つはGauche
$ gosh test.scm
($define () lookup
  ($lambda[lookup;0] (key[1;0] table[1;0])
    ($letrec ((loop[2;0] ($lambda[loop;0] (x[3;0])
                           ($if ($asm (NULLP)
                                  ($lref x[3;0]))
                             ($const #f)
                             ($let ((pair[2;0] ($asm (CAR)
                                                 ($lref x[3;0])))
                                    )
                               ($if ($asm (EQ)
                                      ($asm (CAR)
                                        ($lref pair[2;0]))
                                      ($lref key[1;0]))
                                 ($lref pair[2;0])
                                 ($call ($lref loop[2;0])
                                   ($asm (CDR)
                                     ($lref x[3;0]))))))))
              )
      ($call ($lref loop[2;0])
        ($lref table[1;0])))))
main_code (name=%toplevel, code=0x1043bc00, size=5, const=2, stack=0):
args: #f
     0 CLOSURE #      ; (lambda (key table) (let loop ((x table) ...
     2 DEFINE(0) #; (define (lookup key table) (let loop
 ((x ...
     4 RET
internal_closure_0 (name=lookup, code=0x1043bc18, size=6, const=1 stack=8):
args: #f
     0 LOCAL-ENV-CLOSURES(1) (#); (let loop ((x table)) (if (null? x)
#f ( ...
     2 LREF10-PUSH              ; table
     3 LREF0                    ; loop
     4 TAIL-CALL(1)
     5 RET
internal_closure_1 (name=loop, code=0x104c6f78, size=17, const=0 stack=8):
args: #f
     0 LREF0                    ; x
     1 BNNULL 4                 ; (null? x)
     3 CONSTF-RET
     4 LREF0-CAR                ; (car x)
     5 PUSH-LOCAL-ENV(1)        ; (let ((pair (car x))) (if (eq? (car pair ...
     6 LREF0-CAR                ; (car pair)
     7 PUSH
     8 LREF(3,1)                ; key
     9 BNEQ 12                  ; (eq? (car pair) key)
    11 LREF0-RET                ; pair
    12 LREF10-CDR               ; (cdr x)
    13 PUSH
    14 LREF20                   ; loop
    15 TAIL-CALL(1)             ; (loop (cdr x))
    16 RET
適当にスクロールして見てください。
一つ目の結果はそこまで変わらないのに、2つ目のインストラクションがまずいことに。
原因はSagittariusはmoshのようにDisplay closureを持っていて(これは3imp.pdfにあるやつ)、自由変数が現れると作られるのだが、この処理が重い。参照は早いが作成は遅いというもの。
Gaucheは逆に静的リンクで、作成は軽いが参照が若干重いというもの(だと思う)。
問題になるのは【*1】で示した場所で、ここでletをはさむためkeyとtableが自由変数になる。
ここで【*1】のletを削って、(eq? (car pair) key)を(eq? (car (car x)) key)とすると自由変数が無くなりちょっと処理が軽くなる。

この辺最適化でなんとかできるのかなぁ?stalinでも読むか。

2011-09-07

Fatal bug

I have checked the traffic of this blog, like from which country or which searching words. Somehow I got some traffic from Hungary or Ukraine. (I guess form the US are not non-Japanese speaker...)
So I believe it's good to write in English, very sometimes, even once in a blue moon. Sorry, I'm so lazy.
(If somebody eagerly requests me to write in English, I might do it.)

I've just found a fatal bug on my Sagittarius Scheme. How fatal? I need to say VERY!
Here you can see how serious it is.
(define (map) #f)
(display 'buzz) ;; -> COMPILE ERROR!
This is because I was too lazy to implement library system properly. In current implementation, each library has a hash table to store its variables or macros. The problem was it shares global location object by identifier name.
What does it mean?
It's really simple, even though it looks it has library system, it shares all variable in global. That's why the above problem was occurred.

The bug was actually found because I was trying to run Gambit's benchmarks. On its benchmarks, there is a function named "reduce". This is the same name as SRFI-1 has and the compiler is using it.
I am re-implementing the library system with hierarchy of libraries so that Sagittarius can separate global location object by library. It's almost done, I just need to re-write compiler a little bit and support rename or prefix stuff.

The most surprising thing was I even didn't notice this bug even though I was using it whole time. (Of course I don't re-implement those basic function for studying. I guess that's why.)

2011-09-06

竹内関数

最近ベンチマークとってないなぁと思って図ってみた。
使用コードは下記。

(import (rnrs))

(define (tak x y z)
  (if (not (< y x))
      y
      (tak (tak (- x 1) y z)
       (tak (- y 1) z x)
       (tak (- z 1) x y))))
(let ((args (command-line)))
  (let ((n (string->number (cadr args))))
    (tak (* n 2) n 0)))

図ったのは以下の3つ。
Sagittarius pre0.1.4
mosh 0.2.6
Ypsilon 0.9.6update3
結果は以下の通り
Sagittarius

real    0m0.725s
user    0m0.702s
sys     0m0.046s

real    0m0.723s
user    0m0.733s
sys     0m0.015s
-------------------
mosh
GC Warning: Repeated allocation of very large block (appr. size 69632):
        May lead to memory leak and poor performance.

real    0m0.794s
user    0m0.780s
sys     0m0.015s
GC Warning: Repeated allocation of very large block (appr. size 69632):
        May lead to memory leak and poor performance.

real    0m0.797s
user    0m0.796s
sys     0m0.015s
-------------------
Ypsilon

real    0m0.931s
user    0m0.015s
sys     0m0.030s

real    0m0.920s
user    0m0.015s
sys     0m0.015s

両方とも超えてる!最近施したインストラクションのチューニングが効いてるのかな。
竹内関数だけしかベンチマークとってないのであんまり参考にはならないけど・・・
まじめにベンチマークとろうかな。

追記:
試しにgambitのベンチマークを走らせて見たら爆死した。遅い上に途中でエラーで落ちよる。
まだまだだね(こしまえ風)

Spring webflowの話

サーバーサイドJavaをやってる人なら避けて通れないSpring framework。その中の一つにwebflowがあるのだが、これではまっている話。

話は実は2つある。

1つ目。
ステートの対するレスポンスの話。
webflowはフローチャートをwebで簡単に実装するためにあるようなもので、状態遷移の管理のフレームワークだと思えばいいはず。っで、はまったのはそれ+Ajaxで起きた。
ある状態からある状態に遷移する際にAjaxを使って一部だけを更新しようとした際に、以下のように書いてはいけない
<view-state id="state1" >
  <transition on="trans1" to="trans2" / >
</view-state>

<action-state id="trans2" >
  <!-- do something -->
  <render fragments="frag1" />
</action-state>
Ajaxを使っている場合は状態遷移を起こすとレスポンスがおかしなことになるっぽい。上記のは単にtransitionタグに入れてやればいいんだけど、似たような処理を一箇所にまとめるということができない。見事にはまった。
正直現状のバージョン(2.2を使用)はAjaxとの相性が悪い気がする。というか、そもそもこれ自体がAjaxを使いことを想定していないような感じ。

2つ目。
現在進行形。
webflowのログの話。
webflowは当然だがログを吐く。もちろんログの制御はlogback.xmlとかその辺のでできる。っが問題があって、どのレベルでも吐いてほしくないログというのはどこにでも存在する。たとえばパスワード。
どの世界にも平文のパスワードを吐き出してほしいと思う開発者はいないはず(まぁ、よからぬことを考えているなら別だが)。
っが、webflow君はあまりそんなこと気にしない。正確にはflowScopeに格納されたプロパティをDEBUGモードだと全部吐き出す素敵仕様。そもそもスコープにパスワードを入れるなということなのかもしれないが・・・

いつまでたってもSpringが好きになれない。すごいフレームワークだとは思うんだけど、なんだかなぁ感がいつまでたっても拭えないからに違いない。

2011-09-04

スペアリブ食べ放題

Grouponで(ずいぶん前に)キューポン買っていたのについに行ってきた。アムステルダムに行くのが今まで億劫だったというのがおもな原因だ。
予約が6時で、5時半にアムスに到着。トラムにのって目的地周辺へ。っで、ここからが問題で、目的地の通りはあるのにその番号がない。どうなってるんだ?と思いながら散策。っが、見つからない。
そうこうする間に6時。しゃーないと思い道を聞きつつ探す。この通りなぜか2本あって、トラムから見える一本目とその裏にもう一本。当然裏の方。見つかるかよ!
店自体は普通のレストラン。アルゼンチン料理のはずだが、なぜかインド人っぽい人が経営。よくある話ではあるが。店員さんは非常にいい人だった。
キューポンにはマグロのステーキ、鮭のステーキ、チキンステーキかスペアリブ2時間食べ放題を選べるとある。ので僕はマグロのステーキで、彼女がスペアリブを注文。1切れもやらんと息巻いていたなぁ・・・
出てきた料理。
マグロのステーキ
付け合せのポテト
本丸スペアリブ
でかかった。マグロもきっと400gくらいはあっただろう。スペアリブが3つって。
えぇ、2つほど僕が食べましたよ。何時の間にやら皿に乗ってるんだもん!!
結局食べ放題なのにお代わりせずでした。
どうでもいいが、えらい痩せてる黒人の女の子(高校生くらいに見えた)が普通に4つめを頼んでいたのにびっくりした。あの体のどこに入るんだろう?

2011-09-02

bloggerのインターフェースが変わった

別にだからどうということはないのだが、統計なるものがあってページビューとか訪問元はどことかが見えるようになった。 今までその辺まったく気にしてなかったのだが、月に100を超えるページがあったりして面白い。(世間一般よりははるかに少ないけど) っで、たいていそのページは昔書いたC++のことだったりJavaのことだったり、ajaxのことだったりするわけだ。 中身を読み返してみると、「せっかく検索してたどり着いたのにこんなごみ記事でごめん」と思うくらい自分のチラシの裏だったりするのでちょっと申し訳なく思ってしまう。 最近Springを使っているのでその辺の話も書いていこうかな。使い方ではなく、はまった話が中心になるけど。

TODOリスト

主にSagittariusでやっておきたいなぁと思ったTODOリスト。
  • let-valuesおよびlet*-valuesの組み込み構文化
    • 現状は(rnrs base)でsyntax-rulesによるマクロで定義されてるが、よく考えれば組み込みにできそう。
  • コンパイル時ラムダリフティング
  • srfi-98の対応
    • ぶっちゃけファイル作るだけなんだが、絶賛放置中。
  • Threadの見直し
    • かなり不安定なので。ただ、あんまり使ってないから優先度が低い。
  • 組み込みCharset
    • 現状はsrfi-14を使用。ただ、正規表現の実装で似たようなものがあるので、統合したい。そうするとどうしても組み込みで必要になる。
とりあえずこんなところ。多分まだある。

追記:
let-valuesとlet*-valuesの組み込みシンタックス化完了。思ったとおり簡単だった。

2011-08-31

マクロを書き直した

基本的な方針はバージョン0.1.3までと一緒だが、マクロ展開時に渡す環境をVMに持たせて参照できるようにした。また、今まで行っていた環境のスワップやパターン変数の保存などの入り組んだ処理を全部取っ払ってすっきりさせた。
そのおかげか、R6RSテストスイーツのcontributeとletrecの参照テストを除く8881個のテストが通った。(今まではbound-identifier=?のテストが一つ通ってなかった)
ここまでは順調だった(というっても2週間くらいかかったけど)が、やはりスコープは曲がらない。
ちょっとだけゆがむ程度。syntax-caseは不完全なんですって言い張ってしまうことにしよう。個人的な意見だとマクロ展開フェーズを持たないとあれはきついのではないかと思う。っが、単に勉強不足なのかもしれない。(参考資料も無いけどね!!)

このマクロ書き直しに伴ってキャッシュを少し修正。今まで識別子が持っていた環境内にあるマクロの書き出しを行っていなかったが、するように変更。また、不正オブジェクトの検出を強化。そのため、(core syntax)ライブラリが不正になるようになってしまった。
(なんでハッシュテーブルが内部にあるんだよ?)
オブジェクトの書き出しは本当にどうしようか悩むところで、絶対的にすべてのオブジェクトをキャッシュすることが不可能なのが分かっているからだ。基本的にはリスト、ベクタ、文字列、シンボル、識別子、マクロ、それにライブラリ(名前とimport、exportスペックだけ)で問題ないはずなんだけど、どこかのタイミングでそれ以外のものが入った場合どうしようかなぁと。今のところ分かっているのがハッシュテーブルで、ハッシュ関数が組み込みのものまでは入れてもいいかなぁとは思うものの、面倒だなぁというのが勝っている感じ。実際今のところ1つ2つしかないし。

どうでもいいが、キャッシュを使うとライブラリの読み込みがやはり早い。

2011-08-25

マクロの書き直し

をしているのだが、それに伴ってキャッシュが壊れていることが分かった。

事の発端は識別子にマクロ展開時に必要になる情報を足したところから始まる。それこそコンパイル時の環境をそのまま保存しようとしたのだが、どうやらその際に問題が起きる。
ただ、分かっているのはその壊れたキャッシュを読み込みとセグるということだけで、それがキャッシュの書き込み時の問題なのか読み込み時なのかが分からない。
一つ分かっていることとして、起きる場合は必ず一つのオブジェクトを読み込む際に一つ余計に読み込んでいるということ。ここから察するに、ベクターもしくはリストの読み込みもしくは書き込み時に問題が起きていると思われる。
そうは言っても、すべてのキャッシュで起きるわけではなく、正直何故起きるのかさっぱり分からないが、識別子にマクロ用の環境を持っている物に対してのみ起きる(ような気がする)

マクロの実装と同時並行で発生するのでかなり面倒だ。

2011-08-22

マクロ戦争再び

戦争ではないが気分的に。
とりあえず(自分に)必要そうなライブラリは揃った感があるので、先送りしていた問題に取り掛かろうかなぁと気分。

それに伴いマクロの展開とその環境を少しまとめて思い出しておこうというもの。

≪環境≫
マクロには2種類の環境があって、作成時にマクロ自体が持つmac-envと展開時にコンパイラから与えられるuse-envがある。ちなみに名前はChibi Schemeから。
前者の環境が何故必要かというと、例えばパターン変数などを一意にするために用いる(はず、の予定)
後者の環境はローカル変数の識別とか展開時する際にシンボルを識別子に変換するなどに使い

≪方針等≫
基本的には既存の物と一緒。マクロ(この場合はsyntax-case)をコンパイルし展開器を作成。展開器は単に関数を呼ぶだけ。問題となるのは、現状のままだと与えられたS式にmac-envとuse-envをくっつける形になるので、syntax-caseに直接S式を渡すものに関しては環境が取れない。
この辺をどうした方がいいのかちょっと悩み中。そもそも直接S式を渡された場合に環境は必要なのかとか。
また、現状でもそうだが、syntax-caseとsyntaxのコンパイルを別にする必要がある。

困ったことにR6RSは非常に人気が無いのかsyntax-caseの実装が知ってる限りでは3つしかない。1つがnmosh、Larcenyなどで使われているSRFI-78(だったと思う)をベースにした実装。2つ目が超有名なpsyntax。mosh、Chickenなど多数がこれ。最後がYpsilonの独自実装。
Racketも独自実装だった気がするが、ちょっとうろ覚え。
おかげで基本的にこれを解説しているサイトがない!論文もpsyntaxが基本とかで結構げんなり気味。あと、R6RSがマクロ展開とコンパイルを分けることを要求しているので、どれもそこまで参考にならないという落ちつき。
とりあえず比較的読むのが楽だったYpsilonの実装を参考にしているが、う~ん。

気合と根性で空中分解するしかないか・・・

Sagittarius version 0.1.3 has been released

As I mentioned before, I could not manage to write the document... I will do it by next release!!(I hope)
You can download it here

From this release, it has enough libraries(for me). So I will rewrite macro expansion which does not compromise R6RS syntax-case. (If I just use er-macro-transformer, it works perfectly though)

2011-08-17

ドキュメント書かなきゃ

と思いつつ遅々として進まない。
でも、いろいろ追加しちゃったからそろそろ0.1.3のリリース時期かなぁとか思いつつ。

0.1.3で追加される機能
* Cryptographicライブラリ
* 上記の付属する数学ライブラリ(ハッシュ関数とか、乱数とか)
* REPL
* lalrパーサージェネレータ
* ASN.1ライブラリ

(FFIって前回のリリースだったかな?)
最後のASN.1ライブラリができて、PKCS#1 v1.5パディングがRSAの署名と検証に追加できたらリリース予定。それまでにドキュメントが間に合えばそれも・・・
(多分無理-_-)

REPLを除いたライブラリはすべてSagittariusでしか動かないという素敵仕様(なのか?)。他の処理系との互換性なんてまったく考えなくなってきた。やべぇ。なにしろGauche由来のキーワードを使用したdefine(define-with-keyとして(sagittarius control)ライブラリで提供)が便利すぎて、ちょっと手放せない。こいつのおかげである処理の振る舞いを変更することが明示的かつ簡便に行えるので正直互換性を失っても有り余る便利さ。
(まぁ、他の処理系で何か書いているわけではないので、そんなこと言うのかもしれないが。自分用だしいいよね?)

以前書いたsyntax-caseの問題は0.2.0以降に先送りの方向にしている。自分で使う分には問題にならないし。

ちょっと先取り0.1.3
暗号ライブラリの部分を先取り。気に入ったら使ってくださいという宣伝。DES、DES3、RSA辺りはまじめにテストしてあるけど、AESとかは未テスト。仕事で使わないんだもん。
(import (crypto) (sagittarius control))
(define des-key (string->utf8 "8bytekey")) ;; DES鍵は8バイト
(define des-cipher (cipher DES des-key :mode MODE_CBC :iv (make-bytevector 8 0))) ;; :ivはCBCモードでは必須
;; その他:padder :rounds :ctr-modeがキーワードとしてある。必要になりそうなのは:padderとMODE_CTRを指定した際の:ctr-modeかな。
(let1 enc (encrypt des-cipher (string->utf8 "test message"))
  ;; encは上記のDES鍵で暗号化されたbytevector
  (display (utf8->string (decrypt des-cipher enc))))
こんな感じで使える。cipherが使いまわせるのはJavaと同じ感じにしたため。一度作成すると鍵の交換が現在できないけど、必要そうなら入れるかも。
共通鍵方式の暗号化はほぼlibtomcryptの機能なので、他の暗号方式でもよほどOKだと思う。
RSAも上記と同じAPIで指定するキーワードが少し違う。RSAでは鍵の生成も可能(共通鍵の方は用意してない)。問題は1024ビットの鍵を生成すると30秒くらいかかることか。(もちろんマシンスペックによるが)。
この辺は上記のASN.1ライブラリができたら保存と読み込みをサポートする予定。

暗号ライブラリがどれほどの需要があるかは分からないが、僕は年がら年中使うのですごく有用。DES3(DESede)はちょいちょい使ってるし。

仕事で使う使い捨てのスクリプトがSagittariusでかかれるようになってきてるなぁ、いいことだ。

2011-08-16

母が訪ねてきていた

ということで、先週の木曜日から1週間弱(6日)と短いがちょっと遅めの夏休みを取っていた。
(1週間弱で短いというのはヨーロッパ感覚です。休暇は2週間から!!)

だからといって母は去年既に訪れているのでいわゆる、とりあえず行っておけという場所は既に訪問している。なので今回は週末3日間はドイツに行ってきた。
ドイツはデュッセルドルフという人口59万人の都市。市街地だけなら1日あれば周れる。観光バス、観光フェリーもある。とりあえず、バスとフェリーは乗っておいて、市街地+日本人地区を周る。
デュッセルドルフの街は第二次大戦後、日本の各企業が欧州の貿易拠点に選んだらしく、一つの通りが丸ごと日本人地区になっている。いわゆるチャイナタウンの小規模バージョンみたいな感じ。ここでは日本語しか話せないおっさんがパン屋やってた。(いや、ドイツ語も話せるのかもしれんが、日本語だけで対応された)
まぁ、ここだけにいてもしょうがないので、アルトシュタット(Altstadt)に行く。どうでもいいが、ホテルの受付で案内を聞いたときに「old city」って言われてなんだろうと思っていたのだが、Altstadtの直訳がそれだった。
カフェがひしめき合ってるイメージでそこらじゅうにスポーツカフェ(バーか?)があった。どうもサッカーの試合があったらしく、どこも混んでいて人多すぎ状態に。適当にお茶して、フェリーの時間を待つことに。
(写真撮っておけばよかったかなぁ)
っで、フェリーの時間なので乗る。ちなみにフェリーはいまいちだった・・・行く方はバスだけの方がいいと思う。

観光バスはいわゆるHop On Hop Offバスなので適当に乗って適当に降りれる。でも、降りずに一周。ガイド音声に日本語もあるのだが、なぜか途切れ途切れになっていまいち分かりづらかった。話が飛ぶ感じ。「ここ、デュッセルドルフではアルトビールが・・・さてここでデュッセルドルフの歴史を振り返ってみましょう」みたいなの。多分、バスの運ちゃんがドイツ語の音声ベースで切り替えてるとみた。

特に「ドイツ!!」って感じのものはあんまり感じず、普通の街って感じ。少し外れまで行けば城とかあったみたいだけど、そこまでは周れず。
アルトシュタットだけでもいい感じなんだけど、ヨーロッパ中こんな感じだから割と飽き気味^^;
さすがに2泊3日(正味1日半)ではきついか。

余談だけど、ドイツのホテルでみた英語が微妙というか割りとおかしい部分が多々あった。あと、Test your English Freeなんてうたってる英会話の学校もあった。ドイツ人でも英語は苦手なのかもしれない。

ここからはちょっとだけオランダの話。
ドイツに行く前にZaanse schansというオランダの昔ながらの風車とかチーズとかを再現(?)している街に行ってきた。無料の明治村みたいな感じ(名古屋近郊の人しか知らんか)。
普通に人が住んでて、古い風車使って仕事してたり、伝統的なチーズの運び方したと意外と面白かった。キンデルダイクは(実は)行ったことないけど、ここも風車を見るならお勧め。

眠くて頭がまわらないから文章の構成がおかしいが、まぁいいか。

2011-08-06

EMSA-PSS-ENCODE実装

PKCS#1に詳細に処理が書いてあるのでそれをなぞるだけ。難しいことは何もない。(メモリの無駄遣いは多分にあるが、それは後回し)
問題は、これが正しいかを検証する方法が現状ではないことだ。このエンコード方式はランダムな数値を使ってるので
EMSA-PSS-VERIFYを実装して検証すればいいのだろうか?

2011-08-05

PKCS#1を読む

RSA署名に関してとりあえず必要な部分だけではあるのだが、
§8.1.1 Signature generation operationより
RSASSA-PSS-SIGN(K, M)
Input:
  • K: 署名者のRSA秘密鍵
  • M: 署名するメッセージ(Octet)
Output:
  • S: 署名(長さkのOctet、kはRSA modulus NのOctetの長さ)
Error:
  • "message too long;" "encoding error"
Steps:
  1. メッセージMに対してEMSA-PSS エンコーディングを施し(§9.1.1 (後述))、長さが[(modBits - 1)/8]のエンコードされたメッセージEMを作成。OS2IP(EM)(§4.2)で取得できるビット長が最大でmodBits-1のもの。modBitsはRSA modulus Nのビット長。
    EM = EMSA-PSS-ENCODE(M, modeBits - 1)
    EMのOctet長はmodBits - 1が8で割り切れる場合は、kより1小さく、そうでないならばkと等しい。もしエンコーディング処理が"message too long,"を返したら、"message too long"を出力し停止する。"encoding error"についても同様に処理する。
  2. 署名
    1. エンコードされたメッセージEMを数値mの変換(§4.2)
      m = OS2IP(EM)
    2. RSASP1署名プリミティブ処理をRSA秘密鍵Kと数値m施し(§5.2.1)、署名数値sを得る
      s = RSASP1(K, m)
    3. 数値sを長さkのOctet署名Sに変換する(§4.1)
      S = I2OSP(s, k)
  3. 署名Sを出力
Octet配列から数値への変換はすでにあるので特に気にしない。問題はEMSA-PSSエンコーディングか。(encodingって日本語訳なんだろう?)
ということで
§9.1.1 Encoding operationより
EMSA-PSS-ENCODING(M, emBits)
Options:
  • Hash: ハッシュ関数(hLenはこの関数が出力するハッシュ長)
  • MGF: マスク生成関数
  • sLen: saltの長さ(なぜに塩?)
Input:
  • M: 対象のメッセージ
  • emBits: OS2IP(EM)で取得できる数値の最大ビット長。少なくとも8*hLen + 8*sLen + 9必要
Output:
  • EM: エンコードされたメッセージ。長さはemLen = emBits/8
Errors:
  • "encoding error"; "message too long"
Steps:
  1. Mの長さがハッシュ関数の受け付ける最大長よりも長い場合(SHA-1なら2^61 - 1)、"message too long"を出力して終了
  2. 変数mHash = Hash(M)、ハッシュ長hLenの文字列
  3. emLen < hLen + sLen + 2ならば"encoding error"を出力して終了
  4. ランダムな文字列saltを生成。もしsLen=0ならば空文字
  5. 変数M'を定義
    M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt
    M'は長さ8 + hLen + sLenで、先頭から8OctetがゼロのOctet文字列。
  6.  変数H=Hash(M')、ハッシュ長hLenの文字列
  7.  emLen - sLen - hLen - 2で構成されたOctet文字列PSを生成。PSの長さは0でも良い。(構成って中身ってこと?それとも長さ?)
  8. 変数DB=PS || 0x01 || salt; DBの長さはemLen - hLen - 1
  9. 変数dbMask =MGF(H, emLen - hLen - 1)
  10. 変数maskedDB = DB ⊕ dbMask.(⊕= xor)
  11. maskedDBの左から8*emLen - emBitsを0埋めする。
  12. 変数 EM = maskedDB || H || 0xbc
  13. EMを出力
結構厳密に決められていた。でもマスク生成関数MGFって何?§B.2に記述があった。
§B.2.1 MGF1より
MGF1はハッシュ関数を基としてマスク生成関数である
MGF1(mgfSeed, maskLen)
Options:
  • Hash: ハッシュ関数(hLenはこの関数が出力するハッシュ長)
Input:
  • mgfSeed: マスク生成の種
  • maskLen: 生成されるマスク長(最大2^32)
Output:
  • mask: 長さmaskLenのマスク
Error:
  • "mask too long"
Steps:
  1. maskLenが2^32より大きいなら"mask too long"を出力し終了
  2. 変数Tを空文字として定義
  3. 擬似コード
    For counter = 0; counter > maskLen/hlen - 1; counter++
    
    1. counterを長さ4のOctet文字列に変換
    2. 種mgfSeedのハッシュとCのハッシュをTに連結
      T = T || Hash(mgfSeed || C).
  4. 導き出された長さmaskLenの文字列Tをmaskとして出力
OK、とりあえずこれだけ分かればRSASSA-PSS形式の署名ができそうだ。