とある面接での質問

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

R7RSのドラフト４

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を入れても改善の余地は少なさそう。さて、どうしようかね。

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コマンドを実行してみてください。

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

自分の価値について

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

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

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

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や長いテキストはポートで返す(現状の実装だと結局全部読み込むのであまり意味はないが、そうするべきという意味合いで)。
なんとなく、仕事で使うような機能はほぼそろいつつあるなぁ。

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には明示的に書いてないこと(読み飛ばしたのかもしれん)が普通に書かれてるのと、サンプルが多くてお勧め。

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をリリースしよう。

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の改善だったのに遅くなったという面を除けば悪くない。

9月が終わる

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

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

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

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の呼び出しで捕捉された継続が呼び出されないと分かっているなら(上記の例みたいな)、スタックを凍結せずそのままってのが一番だわな。この辺はコンパイラに頼るほかないが。

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

結局

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

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

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

調子にのってというかふと思いついたのでその２。

1. 財布の中に20ユーロ入っていればOKと思うとき
2. 雨が降っても傘をささないとき
3. ビデオレンタル屋でAVがワゴンで売られていてもなんとも思わないとき
4. etos(日本で言う杉薬局みたいなの)に大人の玩具が置いてあってもなんとも思わないとき

相変わらず思いつかなかった。解説が必要なのはは1かな？
ATMカードがあれば大抵の場所で支払いOKなので、そんなに持ち歩かなくてもいいんです。英語はDebitだったかな？オランダではPINっていいます。

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

とりあえず

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

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

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

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が作られていたら除去する必要がある

ここまでやったがうまく動かない。どこかに見落としがある。どこだろう？

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

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

ということでどこがまずいか、どうして使ってはいけないかを書き出してみる。(だからといって現状が変わるわけではなく、単なる愚痴である)

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

めんどくさくなったので、これくらい。使えば使うほどげんなりするのも仕様です。ってか、ほかのプロジェクトとかどうしてるんだろう？特に2番。
リリース後はデバッグログなんて出さないのかな？パッケージソフトには厳しいお言葉過ぎるよ。

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

１つのライブラリを最適化できないかなぁと思って、とりあえずインライン展開を試みてみた。
(大別するとグローバル最適化？でも、R6RSだとライブラリは１つの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のベンチマークではまったく意味がないところか。

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も通らない。通るようにすることもできるんだけど、どうしようかなぁ？
こんなコード書かれないよなぁ・・・