How should include work?

There was a post which asked the behaviour of the include syntax in R7RS. This is the post;

Dybvig's paper about syntax-case, I'm unsure abouttherequirements
of R7RS regarding the use of `include' within macros:

(define-syntax m
   (syntax-rules ()
     ((_) (lambda (a) (include "some/file.sch")))))

where the file "some/file.sch" contains, say,

(+ a 1)

Is the symbol `a' in "some/file.sch" supposed to match the
lambda's argument?

[Scheme-reports] file inclusion (section 4.1.7 of draft 9)

Then R7RS draft 9 says like this;

Both include and include-ci take one or more names expressed as string literals, apply an implementation-specifi c algorithm to find corresponding files, read the contents of the files in the specified order as if by repeated applications of read, and e ffectively replace the include or include-ci expression with a begin expression containing what was read from the files.

So in R7RS include reads from the specified file with read without any syntax information. So, in above case it shouldn't refer the lambda's argument.

Now, John Cowan responded a lot of implementation could see the variable a. Well, yes, this is odd. However I think I know why (only R6RS implementation wise).

Following is the (naive) implementation of the include with R6RS syntax-case

(import (rnrs))
(define-syntax include
  (lambda (x)
    (define (do-include k name)
      (call-with-input-file name
        (lambda (in)
          (do ((e (read in) (read in)) (r '() (cons (datum->syntax k e) r)))
              ((eof-object? e) (reverse r))))))
    (syntax-case x ()
      ((k name)
       (string? (syntax->datum #'name))
       (with-syntax (((expr ...) (do-include #'k (syntax->datum #'name))))
         #'(begin expr ...))))))

The point in R6RS is that syntax-case must always return syntax object so with this implementation, the included expressions wrapped (or converted) by syntax object so that a contains some syntactic information to refer the lambda's argument. (Unfortunately, Sagittarius raises an error with unbound variable. Well, I know it's a bug...)

Then we need to come back to what R7RS says. Yes, it actually doesn't specify but read the file content by read and replace it. Thus, both behaviours can be valid as my understanding.

Now, my big problem is that I need to fix the macro's bug... I thought it could see it but it didn't...

FFIとcallback

最近FFI周りばかり弄っている気がする。取り立てて必要というわけではないのだが、バグが目に付くというか、一貫性の無さが気に入らないというかそんな感じ。

っで、ふとcallbackの実装がメモリ使用量的に嬉しくないことに気づいた。

現状の実装ではcallbackは作られるとSagittariusの静的領域に保存される。これは「呼び出したC関数内でcallback関数が保存された後にGCが走ってcallbackは回収されちゃったけどCから呼び出されちゃった、てへっ♪」って言うのを防ぐためだったりする。FFIで開いた共有オブジェクト内のことはGCは気にしてくれないし、ついでにそこに渡されるcallbackはlibffiが割り付けたメモリなのでそもそもGCはたどることすらできない。

まぁ、callbackなんてそんなに使わないからいいかと言えばいいのだが、たとえばうっかり100万回回るループの中で10個ずつ作成しました！なんてことが起きる可能性が無いわけではない。実際、書く方としてはわざわざ開放してやるなんてことをしたくはないだろう。(推奨してはいないが・・・)

ただ、そうするとどうにかして自動で開放してやる仕組みが必要になるのだが、 どこか見知らぬアドレスに格納されたGC管理外メモリのことなんて知る由もないわけで、いい案どころか無理ゲーな感じが否めない。

なにかしら、適当な落としどころがほしい感じである。

FFIの可変長引数

必要がないのでサボっていたのだがGTKのバインディングをまじめに考えるなら必要になることがわかったのでちょっと頑張って実装してみた。

こんな感じで使える

(import (rnrs) (sagittarius ffi))

(define libc (open-shared-library "msvcrt.dll" #t))

(define snprintf (c-function libc int _snprintf (char* ___)))

(let ((buf (make-bytevector 10)))
  (snprintf buf 10"%d:%s\n" 100 "test")
  (print (utf8->string buf)))

(snprintf) ;; error

まだ実装が適当(与えられる引数の制限が多い)なのと、libffiのバージョンによっては正式にサポートされていないので警告文が出たりする(ぱっとソース見た感じだと特殊な処理が必要なアーキテクチャの方が少ないみたいだし、メジャーどころは要らなさそうなので、デフォルトで警告を出す必要は無いかもしれないが・・・)。

libffiで可変長の引数を扱うのは結構泥臭くて、呼び出し側は全ての引数を把握していないといけないのと、*残り*みたいな引数型はないのでffi_storageを引数個確保しておく必要がある。この制約のせいで通常の関数とは違って多少オーバーヘッドがかかるようになってしまった。

通常はC関数オブジェクトの作成時に必要な領域(引数型情報の配列)を確保しているのだが、可変長の場合は呼び出しごとに作成する必要がある。利便性を取るか速度を取るかといった感じである(ベンチマークとってないのでどれくらい性能に影響を与えるかは分かっていなかったりするが)。

あと、コールバックは可変長に対応していなかったりする。今のところ必要な場面が思いつかないのと、可変長引数を受け付けるコールバックを見たことがないというのが理由。まぁ、単なる手抜きである。

MOP improvement(?)

On Sagittarius,  MOP was not totally compatible with Tiny CLOS's MOP. That's because of my laziness. However I have noticed that once I use non builtin generic class, then it's not possible to use method qualifiers. This is not good to me. So I have improved some stuff.

The problem was that it was only implemented in C code and not in Scheme code so once I used custom generic class then it won't check those qualifiers. So I have removed builtin compute-applicable-method and moved to Scheme. Then implemented all required procedures and duplicated the logic in Scheme. (I actually don't want to do this but so far I couldn't find any better way.)

Now, I can do something like this;

(import (rnrs) (clos user) (clos core) (srfi :1))
 
(define-class <my-generic> (<generic>) ())
(define-generic foo :class <my-generic>)

(define-method compute-applicable-methods ((gf <my-generic>) args)
  (let ((m* (generic-methods gf)))
    (let-values (((supported others)
                  (partition (lambda (m) 
                               (memq (method-qualifier m)
                                     '(:before :after :around :primary)))
                             m*)))
      (for-each (lambda (m) (remove-method gf m)) others)
      (let ((methods (call-next-method)))
        (for-each (lambda (m) (add-method gf m)) others)
        (append others methods)))))

(define-class <human> ()())
(define-class <businessman> (<human>) ())
(define-method foo :append ((h <human>))
  (print "something else")
  (call-next-method))

(define-method foo :around ((h <human>))
  (print "human around before")
  (call-next-method)
  (print "human around after"))

(define-method foo :before ((h <human>))
  (print "human before"))
(define-method foo :before ((b <businessman>))
  (print "businessman before"))
 
(define-method foo ((h <human>))
  (print "human body"))
(define-method foo ((b <businessman>))
  (print "businessman body"))
 
(foo (make <businessman>))
#|
something else
human around before
businessman before
human before
businessman body
human around after
|#

I have no idea what I'm doing in above code!! Well, default implementation of method qualifier refuses non supported keywords so first remove other keywords from generic function then compute builtin qualifiers and adds the removed ones. At last append the non supported qualifier methods in front of the computed ones. The result is the other qualifier one is called first then the rest. If you put this append after the around method then all methods need to call call-next-method otherwise it won't reach there.

I have no idea if I will use this or not but at least I have something if I want to change the behaviour!

総称関数の:beforeとか

ほぼ初めて実用でこの辺の機能を使おうとしてふと不満に思ったこと。

SagittariusのCLOSはXeroxのTiny CLOSの動作を基本にして作られていて、:beforeとかもその動作を元にしている(たぶんこれは以前にも書いた気がする)。っで、ふとそれだとまずいというか、嬉しくないなぁというパターンが出てきて、ちょっと動作のおさらいをしている。

とりあえずは、以下のコード

(import (rnrs) 
        (rename (clos user)
                (define-class %define-class)
                (define-method %define-method))
        (srfi :0))

(define-generic foo)
(define (print . args) (for-each display args) (newline))
(cond-expand
 (mosh
  (define-syntax define-class
    (syntax-rules ()
      ((_ name parents (slots ...))
       (%define-class name parents slots ...))))
  (define-syntax define-method
    (syntax-rules (:before :after :around)
      ((_ name :before (specifiers ...) body ...)
       (%define-method name 'before (specifiers ...) body ...))
      ((_ name :after (specifiers ...) body ...)
       (%define-method name 'after (specifiers ...) body ...))
      ((_ name :around (specifiers ...) body ...)
       (%define-method name 'around (specifiers ...) body ...))
      ((_ name (specifiers ...) body ...)
       (%define-method name (specifiers ...) body ...)))))
 (sagittarius
  (define-syntax define-class (identifier-syntax %define-class))
  (define-syntax define-method (identifier-syntax %define-method))))

(define-class <human> ()())
(define-class <businessman> (<human>) ())
(define-method foo :before ((h <human>)) 
  (print "human before"))
(define-method foo :before ((b <businessman>)) 
  (print "businessman before"))

(define-method foo ((h <human>)) 
  (print "human body"))
(define-method foo ((b <businessman>)) 
  (print "businessman body"))

(foo (make <businessman>))
#|
businessman before
human before
businessman body
|#

まじめに書いてないのでまともに動きはしないのだが、Moshとの互換レイヤが入っている。気になるのは出力結果。動作を合わせてあるので現状は同じ出力を返すのだが、「human before」はcall-next-methodがあった場合にのみに出力されてほしい気がする。というか、そうじゃないと綺麗に書けないコードを書いていて、もにょっている感じ。

本家のCLではどうなっているのかもついでに試してみた(これも以前試したっけ？)

(defclass human () ())
(defclass businessmane (human) ())

(defmethod foo :before ((h human)) (print "before human"))
(defmethod foo :before ((h businessmane)) (print "before businessmane"))

(defmethod foo ((h human)) (print "body human"))
(defmethod foo ((h businessmane)) (print "body businessmane"))

(foo (make-instance 'businessmane))
#|
"before businessmane"
"before human"
"body businessmane"
|#

あぁ、本家もそうなのか。そうなると逸脱するのも微妙だなぁ・・・

CLOS based GUI library

Most of the script I have written so far is command line script and I didn't feel any inconvenience with it. However, sometimes I felt like if there is GUI to do it, it might make my life easier.

So I have decided to write a GUI library using FFI binding (currently working only Windows or Cygwin). There is a huge problem that is I have never written it before so I have no idea what is the best way to do it. After couple of days, I decided to use CLOS based method (named by me :-P).

It's not done yet but the code looks like this;

(import (clos user) (turquoise))

(let ((w (make <frame> :name "Sample" :width 200 :height 200))
      (b (make <button> :name "ok" :x-point 37 :y-point 50)))
  (add! w b)
  (add! b (lambda (action) (print action)))
  (show w))

The library (turquoise) is the GUI library. This piece of code just shows a window contains a button which prints action argument to standard output when it's pressed. The basic idea is using class as a component representation the same as other modern libraries and show thoese classes to users so that they can extend it easily.

I'm not sure if I should make add-component! or add-action-listner! instead of using generic method add!. If you have opinions about it, please let me know.

公用語が英語な会社

この記事が書かれたきっかけ

1. 自分の会社が最近オランダ人を雇っていないと気づく
2. これって募集要項が英語だからじゃね？
3. そういえば公用語を英語にするって表明した会社があったなぁ
4. 募集要項を英語のみにすれば必然的に英語ができるかつ優秀なやつがくるんじゃね？

という流れで、どれくらいの企業が日本人向けの募集要項を英語で出しているのか調べてみた。(ちなみに、自分が今勤めている会社はオランダ語の募集要項は無い。ってか、サイトにオランダ語の選択肢すらない。いいのか、それで？)

楽天とユニクロは有名だけど、他にどこがあるんだろうとまず調査。以下のNaverのページに載っていた公用語を英語にすると発表した企業に限定(昇進に英語必須とか含めると大変だったのでｗ)

楽天とユニクロ以外に「社内英語公用語」を発表している企業様まとめ 

っで以下が結果。

【日本語で募集】
楽天、ユニクロ、日産、SHARP、 日本硝子

【英語で募集】
SMK

SMKはロケールで変わるのかもしれないが、トップページがSMK Japan in Englishに飛ばされたので。日本語ページを見ると日本語の募集要項が載っていた。その他の企業は基本トップページが日本語だった、ひょっとしたら英語ページは英語なのかもしれない。

別に何ということもないのだが、個人的には企業がどれくらい公用語英語をまじめに実践しているかということを外からしる一つの指標になるのではないだろうかと思ったり。もちろん実情は知りようがないし、面接は英語で行われるとかも調べていないが・・・

ついでに、企業がまじめに英語を公用語にしているということは、「英語は話せて当たり前、その上で何ができるの？」というスタンスでいると思うので、「英語話せます」だけでは採用されないということだと思ったりもしている。というか、意思疎通の手段としているわけだからそこを言及すること自体そもそもおかしいわな。

Sagittarius 0.4.5 リリース

Sagittarius Scheme 0.4.5がリリースされました。今回のリリースはメンテナンスリリースです。
ダウンロード

修正された不具合

• define-c-structがアライメントを無視したサイズの構造体を作る不具合が修正されました
• この修正によって(sagittarius ffi)がより正確なアライメントを計算するようになりました
• parameterizeが値を正しく復元しない不具合が修正されました
• (/ 1 -0.0)が+inf.0を返す不具合が修正されました
• sashの-Iオプションがエラーを投げる不具合が修正されました

改善点

• キャッシュファイルがマルチプロセス環境でより安全になりました
• これによりmake -j nでのビルドが可能です
• parameterのメモリ使用量が少なくなりました

新たに追加された機能

• eql sepecializerが組み込みになりました
• open-shared-libraryが共有ライブラリが見つからなかった際にエラーを投げるオプショナル引数を受け付けるようになりました
• generate-secret-keyでDES3の秘密鍵を生成する際に8及び16バイトの鍵を受け付けるようになりました
• lock-port!及びunlock-port!が追加されました(明文化はされていません)
• call-with-port-lockが(util port)に追加されました(明文化はされていません)

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

• (dbi)及び(odbc)のドキュメントが追加されました

Should let-syntax family make a scope?

On R7RS ML, there was a discussion for this topic and I'm wondering about it.

On current draft of R7RS, it says 'The let-syntax and letrec-syntax binding constructs are anologous to let and letrec' so I would say it should make a scope. However the reference implementation, Chibi Scheme, doesn't.

Following quote is from the ML:

Please try to keep a grip on the fact that R7RS-small `let-syntax`, like the R5RS version, is a scope rather than being spliced into the surrounding scope. See ticket #48 and WG1Ballot2Results.

From http://lists.scheme-reports.org/pipermail/scheme-reports/2013-May/003439.html

However, seeing this issue from Chibi Scheme, it's not making a scope intentionally.

The reason I'm wondering about it is actually I don't want to make a scope for neither let-syntax nor letrec-syntax. Current compiler checks the mode and switches the path. Well, it's not heavy operation so it won't improve much performance if I remove it (just a tiny bit). However it does make a big change to write some memory efficient code.

Let's say you want to write sort of following code:

#!r6rs
(library (foo)
    (export command1 command2)
    (import (rnrs))
  (letrec-syntax ((define-command
                    (syntax-rules ()
                      ((_ name body ...)
                       (define name (lambda () body ...))))))
    (define-command command1 (display 'command1) (newline))
    (define-command command2 (display 'command2) (newline))))

This only works when you put #!r6rs annotation on the library defined file (I'm talking about Sagittarius). So, if you want to make some keyword argument or so, then you need to remove the annotation and make define-command global binding.

You might say, "as long as you don't export define-command, then it won't harm your code.", well sort of yes. The problem is acutally on cache file. If you define global macros, then cache file must contain it since we can access it without exporting, using with-library macro. (I know it's a back door stuff, but it's sometimes convenient!) However, if we use let-syntax then cache file won't have it because all local macros are already expanded.

On Sagittarius, if you really don't want to export internal macro you need to write it like above in R6RS mode. Then you don't have any chance to use keyword features.

Should I follow Chibi's behaviour or what R7RS (implicitly) says?

パラメタ

面白いというか、目の付け所が鋭いバグ報告が届いた。(面倒なバグとも言う・・・)

具体的な再現コードは以下のようになる。

(import (rnrs) (srfi :39))
(define x (make-parameter 3 (lambda (x) (+ x 3))))
(print (x))
(parameterize ((x 4)) (print (x)))
(print (x))
#|
6
7
9
|#

SRFI-39的にもR7RS的にも最後の9は6じゃないといけない。原因はすぐに分かったんだけど、問題はどう解決するかという部分。

ちなみに、原因はparameterizeとparameterの実装にある。parameterizeはdynamic-windを使って実装されているのだが、afterのthunkが値をセットしなおす際に保存された値が変換されるという悲しいことがおきる(この場合は6が保存されて、6をセットする際に9に変換される)。 まぁ、解決方法は簡単で、after thunkで保存された値をセットする際に、変換を行わなければいい。

言うは易し、行うは難しの典型である。なぜか、そんなAPIが無いからだ。現状ではパラメタはYpsilonの実装を移植したものを使っている。この実装ではパラメタは単なるlambdaである。つまり、その中身にアクセスする方法などないということだ。(もちろん、同様の問題がYpsilonでも発生する。ちなみにChezでも起きた。意外とこのバグはいろんな実装で穴になっているっぽい。)

とりあえずぱっと思いつく解決方法は2つ。

1. パラメタ作成時に直接値を設定できる手続きを作って一緒に保存する
2. せっかくobject-applyがあるんだし、CLOSで実装してしまう

1の方法だと使用するメモリの量が不安になる、単純計算でパラメタ作成にかかるメモリコストが倍になる。
2の方法だとパラメタを呼び出すときのオーバヘッドが気になる。なんだかんだで総称関数の呼び出しは現状では重たい。

さて、どうしようかな。

eql specializer

This article is continued from the previous one (in Japanese).

Sagittarius has the library to do eql specializer however it was a bit limited if I wanted to use it from C level. So I wanted it builtin, yes I made it :)

Basically almost nothing is changed to use just it became a bit convenient. So you can write it like this (without (sagittarius mop eql) library);

(import (clos user))
(define-method fact ((n (eql 0))) 1)
(define-method fact ((n )) (* n (fact (- n 1))))
(fact 10) ;; -> 3628800

Now you don't have to define a generic procedure before defining methods.

Current implementation is simply ported from the old library so it might not be so efficient. (Well, it's written in C now so it should be faster than before!)


Ah, I thought I wanted to write more but guess not :(

暗号ライブラリの不満

Sagittariusは自前で暗号ライブラリを持っているのだが、ちょっと不満が出てきた。何が不満かと言えば、DES3の鍵生成で必ず24バイト要求するというものだ。これだといわゆるDES2が使えなくて、でも16バイトの鍵がわたってきた場合に困ることになるというもの。

現状では秘密鍵の生成は以下のようにして鍵オブジェクトを作ってやる必要がある。

(import (crypto))
(generate-secret-key DES3 #vu8(...)) ;; must be 24 byte bytevector

generate-secret-keyは総称メソッドなので、DES3がわたってきた際に特異なものを作ってやればいいという話になる。

本来ならという注釈がつくのがポイント。ドキュメントにちょろっと書いてあるのだが、この鍵アルゴリズムの名前は専用のクラスを作って唯一のオブジェクトを登録するのが望ましい、と書いてあるだけだったりする。つまり、なんでもいいのである。 (今思ったのだが、なんでオブジェクトを作る必要があるんだ？クラスだけでもいいんじゃね？) っで、その裏ルールに則って組み込みの秘密鍵なアルゴリズムは文字列が登録されていたりする。(これはバックエンドで使っているLibTomCryptoが文字列でディスクリプタを登録しているため)

そんなときのためにeql-specializerがあるんじゃないかとも思ったのだが、こいつは組み込みではサポートしていないので総称メソッドの定義時にメタクラスとして指定してやる必要があってうまくいかない。

解決方法はとりあえず思いつく中でスマートなものは以下の2つ。

1. RSAと同様に秘密鍵のアルゴリズムも文字列じゃない何かにする
2. eql-specializerを組み込みでサポートする

1.はクラスの階層を考えたり、現在サポートしている全てのアルゴリズムに適用する必要があったりでひたすら面倒だけど王道な解決策。
2.はどこと無くadhocな感じはするが、eql-specializerが組み込みに出来るチャンスともいう。

さて、どっちにしようかな・・・

FFI周りの改善

SagittariusのFFIでCの構造体を定義する際にメタな情報を付与してユーザーにアライメントの計算を強いないようにしている。ここまでは単にユーザーフレンドリな仕様で済むんだけど、内部のアライメント計算処理があまりにも適当すぎて32ビットと64ビットでの違いが吸収できてないとか、オフセット計算が間違ってて特定のメンバにアクセスするとSEGVるとかのバグがちらほらあった。

個人的にあまり問題にしていなかったのだが(Cの構造体を弄る場面が少なかった) 、なんとなく隙間の時間があったので「えいやっ！」と直すことにした。

0.4.4以前で問題になるのは以下のようなコード。

(import (sagittarius ffi))
(define-c-struct foo
  (int   i0)
  (char  c)
  (short s)
  (int   i1))
(size-of-c-struct foo)

定義された構造体のサイズは12(sizeof(int) == 4)でなければならないが、0.4.4では11を返す。これは、構造体のパディングとサイズの(意図的ではないが)ルールを無視しているためだったりする。また、メンバのオフセット計算もおかしかったりで、複雑な構造体を扱うのは危険だったりもした。(メンバが全部intとかvoid *もしくは型が違ってもサイズが同じとかなら問題はない。)

とりあえず、以下のWikipediaのページを参考にしつつ、もうちょっとまともな計算をするように改善。
http://en.wikipedia.org/wiki/Data_structure_alignment
現在のHEADではかなりまともな計算をするようになっている。(個人的に怪しい部分はあったりするが・・・)

また、define-c-structの定義をちょっと変えて、アクセサを同時に定義するようにした。たとえば上記の構造体なら以下のアクセサが自動的に定義される。

foo-i0-ref
foo-i0-set!
 ...
foo-i1-ref
foo-i1-set!
;; 参考 foo-i0-refとfoo-i0-set!の定義イメージ
(define (foo-i0-ref p)
  (c-struct-ref p foo 'i0))
(define (foo-i0-set! p v)
  (c-struct-set! p foo 'i0 v))

実際には内部構造体のメンバを扱うためにオプショナル引数を受け付ける。このオプショナル引数は個人的には美しくないと思っているので(特に-set!側)、なんとかしたいのだがいい案が思いつかない。

さらに、構造体の定義内に配列を含めた際の参照と代入が(ほぼ全く)サポートされていなかったのでそれも直した。配列で定義されたメンバの参照をすると現在はベクタを返すようになっている。代入もベクタで行う必要がある(以前は代入は自前でオフセット計算してやる必要があった)。

個人的にこの辺の機能を使うことがほとんどないので、誰かハードに使ってくれる人を募集してますｗ

Yet Another Syntax-case Explanation

Unlikely my (own) rule, this article is in Japanese (if you want it in English, please comment so).

世の中syntax-caseの解説なんて(たぶん)山ほどあるだろうけど、もう一つGoogleの検索結果を汚してやろうという話。

この記事のsyntax-rulesは使えるけど、syntax-caseとwith-syntaxを絡めて使えないという方をターゲットとしてます。マサカリ大歓迎ですw

【syntax-caseって】
まずは、簡単にsyntax-rulesとsyntax-caseの違いを見てみよう。

(import (rnrs))
(define-syntax print-rule
  (syntax-rules ()
    ((_ o o* ...)
     (begin (display o) (print-rule o* ...)))
    ((_ o)
     (begin (display o) (print-rule)))
    ((_) (newline))))

(define-syntax print-stx
  (lambda (x)
    (syntax-case x ()
      ((_ o o* ...)
       #'(begin (display o) (print-stx o* ...)))
      ((_ o)
       #'(begin (display o) (print-stx)))
      ((_)
       #'(newline)))))

どちらのマクロも同じことをします。これだけ見れば、違いは以下ぐらい：

• syntax-rulesがsyntax-caseになった
• lambdaで囲まれて、syntax-caseの引数(と呼ぶのもおかしいが)にlambdaの引数が渡った
• テンプレート部分がsyntax (#')で囲まれた

はい、この程度のものを書くならsyntax-rulesだけで十分です。じゃあ、syntax-caseを使うと何が嬉しいのか見ていきましょう。

【低レベルな操作】
何を持って低レベルとするのかはさておき、ここでは与えられて式の内容を操作することを低レベルと呼びます。syntax-rulesでは式の変形はできても、中身を操作することはできません。たとえば以下のようなコードは、syntax-rulesでは実現不可能です。

(define-syntax define-foo-prefix
  (lambda (x)
    (define (add-prefix name)
      (string->symbol 
       (string-append "foo-" (symbol->string (syntax->datum name)))))
    (syntax-case x ()
      ((k name expr)
　　　　　　;; need datum->syntax to compliant R6RS
       (with-syntax ((prefiexed (datum->syntax #'k (add-prefix #'name))))
         #'(define prefiexed expr))))))

(define-foo-prefix boo 1)
foo-boo ;; -> 1

さて、ここでwith-syntaxが出てきました。こいつが何をしているのかの説明がこの記事のメインなのでここで解説です。

構文的なものはR6RSでも見てもらえばいいとして、何をしているのか。名前が示すとおり、with-syntaxは新たに構文オブジェクトの束縛を作ります。 ここでは、prefixedがそれにあたります。なぜこんなことが必要かといえば、syntax-caseのテンプレートは構文オブジェクトを返す必要があるからです。そして、syntax (#')構文内では構文オブジェクトの束縛のみが参照可能ということも大きな要因です。上記のような、低レベルな操作を健全なマクロで行うためにあるといっても問題ないでしょう。

また、with-syntaxで作られた構文オブジェクトが保持する情報も重要になってきます。R6RSではテンプレート部分にどこにも定義されていない名前が出てくると、それはユニークな名前に変更されます。define-valuesなどの定義で、dummyとか使われているあれです。しかし、with-syntaxで束縛された構文は束縛された名前がそのまま使えます。

いまいちイメージがつかめない方のために、R5RSとCommon Lispのマクロの議論でよく引き合いに出されるaifをwith-syntaxを使って書いて見ましょう。こんな感じの定義になると思います。

(define-syntax aif
  (lambda (x)
    (syntax-case x ()
      ((_ pred then)
       #'(aif pred then #f))
      ((k pred then else)
       ;; ditto
       (with-syntax ((it (datum->syntax #'k 'it)))
         #'(let ((it pred))
             (if it then else)))))))
(aif (memq 'a '(b c a e f)) it 'boo) ;; -> (a e f)

aifはpred部分の評価結果を変数itに暗黙的に束縛します。なので、マクロユーザからはその定義は見えず、いきなり現れたように見えます。Schemer的にはいまいち気持ち悪い気もしますが、あれば便利な機能です。
ここで使われているwith-syntaxが何をしているかといえば、シンボルitを構文オブジェクトに変換してテンプレート内で参照可能にしています。このitはリネームされないため、あたかも突如現れたかのように使うことができるのです。

【それ、quasisyntaxでもできるよ？】
はい、できます。with-syntaxとquasisyntaxはほぼ同等の力を持っていると思っていいです。なので、上記の例は以下のように書き換えることが可能です。

(define-syntax define-foo-prefix
  (lambda (x)
    (define (add-prefix name)
      ;; ditto
      (datum->syntax name
       (string->symbol 
 (string-append "foo-" (symbol->string (syntax->datum name))))))
    (syntax-case x ()
      ((_ name expr)
       #`(define #,(add-prefix #'name) expr)))))

(define-syntax aif-quasi
  (lambda (x)
    (syntax-case x ()
      ((_ pred then)
       #'(aif pred then #f))
      ((k pred then else)
       ;; ditto
       (let ((it (datum->syntax #'k 'it)))
       #`(let ((#,it pred))
           (if #,it then else)))))))

どちらの方がいいかはユーザの感性に寄るとは思いますが、個人的にはwith-syntaxを使った方が綺麗かなぁと思います。quasisyntaxはCommon Lispのマクロを連想させるという理由だけなのですが・・・。ただ、あまりに多くの構文を導入する必要があると無駄に長くなるという弊害もあるので、ケースバイケースで使い分けるのがいいでしょう。

追記：
Twitterで早速突っ込みが入ったのでdatum->syntaxで明示的に構文オブジェクトに変換するようにコードを修正。SagittariusとYpsilonはこの辺多少チェックがゆるい。
それに伴って多少文言の修正。with-syntaxは構文オブジェクトを束縛する等々。

SRFI-111

今一なんの意味があるのかよく分からないSRFIなんだけど、実装するのが非常に簡単だから実装してみた。こんな感じ。

(library (srfi :111 boxes)
    (export :export-reader-macro
     box box? unbox set-box!)
    (import (rnrs)
     (clos user)
     (sagittarius)
     (sagittarius reader))

  (define-class <box> ()
    ((value :init-keyword :value :reader unbox :writer set-box!)))
  (define-method write-object ((b ) port)
    (format port "#&~s" (unbox b)))
  (define (box? o) (is-a? o ))
  (define (box o) (make  :value o))

  (define ctr #'box)
  (define-dispatch-macro #\# #\& (box-reader port c param)
    (let ((datum (read port)))
      `(,ctr ',datum)))
)

(library (srfi :111)
    (export :all :export-reader-macro)
    (import (srfi :111 boxes)))

要求されているリーダーマクロまで入っているという優れものw
こんな感じで書ける。

#&abc              ;; -> #&abc
(unbox #&abc)      ;; -> abc 
(set-box! #&abc 1) ;; -> #<unspecified>

リーダが読み込んだBoxはimmutableが好ましいとは言われているけど、 そこは気にしない。とりあえず手元にある処理系でこのリーダーマクロをサポートしてるのはRacketのみだったという事実もあったりする。

参照実装がR7RSのライブラリ形式を使っているのも面白い。まだ決まってないけど・・・(まぁ、ここからこけるということもないんじゃないかなぁとは思っているが)

脱BoehmGCへの道 実装編(4)

あきらめてはいないという意思表示ｗ

いや、実際あきらめてなくて、未だに戦ってるんだけど、これ書くということはどうしようかなぁという問題が発生したということでもある。

問題は、あるオブジェクトAの中にあるオブジェクトBがAより後に回収された際に起きるアドレス更新の問題。(ひょっとして#3でも同じ問題を扱ったかもしれない。)
具体的にはユーザー定義のクラスAが同じくユーザー定義のクラスBを基底クラスとして持っていた際に、Aが先に回収されるとAのクラスタグであるBが古いアドレスを指したままとなりさまざまな場面でSEGVを発生するという問題になる。具体的にこれを発生させるコードは以下のようなの：

(import (clos user) (sagittarius control)
        (sagittarius mop validator))
(define-class <person> (<validator-mixin>)
  ((name   :init-keyword :name)
   (gender :init-keyword :gender
           :validator (lambda (o v) (or (memq v '(male female))
                                        (error 'boo))))))
(define-class <business-man> (<person>)
  ((job    :init-keyword :job)))
(let ((man (make <business-man> :name 'john :gender 'male :job 'neet)))
  (dotimes (i 10000) (make-vector 1000))
  (print (slot-ref man 'name))
  (print <person>)) ;; Boom!!

<person>が持ってる<validator-mixin<が回収されても更新されないので出力しようとした際に不正なアドレスを指して死亡する。 こういうのが発生するとクラスタグみたいなのは単なるタグにしておけばよかったと後悔するのだが、これはこれべ便利なので泣かない・・・

うまい解決方法が思いつかないのだが、タグに使われているクラスがGC対象のスペースにあった場合は先に回収してしまうという荒業でいけるだろうか？ただ、scavengeが後で呼ばれることになるのでその際に既に移動してるって怒られる気がするんだよなぁ。 まぁ、とりあえず試してみるか・・・

R7RS ratification vote

The reason why this is English article is simply I don't know the proper translation of  'ratification vote' and felt it's awkward to write it in hiragana or katakana. Sorry, my bad :)

The ratification vote has been started. I'm not quite sure if I will vote or no and if I would, I would vote to 'yes' that's because Sagittarius has whole functionalities, not because I totally agreed with it.

Nobody expects 100% agreement, I believe, probably 70 to 80%. However mine is much lower than it. The reason is it's not stepping forwards but backwards. These are the stuff I think R7RS went backwards from R6RS.

[Low level macro]
A lot of *pure* Schemer think syntax-case is too huge to be in the specification. Actually I totally agree with it (well, that's because it was really hard to implement but as user's perspective it's really convenient). However, R6RS at least put low level hygiene macro in it. I think that's a big step forward. On the other hand, R7RS simply removed it without alternatives. I know it is hard to decide which low level hygiene macro should be in. And now we don't have any way to make R7RS macros compatible with R6RS macros except syntax-rules.

I'm following the discussion since 2011 (I guess) and probably missed why they dropped it without any alternatives. But I can guess the reason, low level hygiene macro is too big to put in RnRS so they probably thought let WG2 handle this. It might be a clever decision but since we already have it, then it is definitely not the best decision, that's because implementations don't have to implement all of libraries defined in WG2.

[Library syntax]
I agree R7RS library syntax much more flexible and convenient than R6RS one. However that simply made existing R6RS libraries not to be able to run in R7RS implementations. As far as I know, currently only 2 implementations are fully implemented with R7RS, Chibi Scheme and my Sagittarius (if you know other, please let me know. I want to try). And Chibi only supports R7RS library syntax means it can't use useful R6RS libraries (like industria or so, before you say 'is there such a library?' :P).

They were probably aiming to use R5RS codes on R7RS implementation easily, like SSAX or so. However, I'm doubting if it was a better way. I don't know why they needed to introduce the brand new  syntax instead of using the existing one. For me, it seems they simply didn't like R6RS or maybe try not to make any confusion.

[Reader macro]
As you already know, reading R6RS source code might not be possible on R7RS implementation because of the difference of bytevector lexical syntax. I totally have no idea why they changed this. I know it's different from SRFI-4 but SRFI is not a specification. Not all Scheme implementation has extensible reader macro like Common Lisp so this simply breaks capability even just reading S-expression file written by R6RS implementation. Honestly, this totally sucks!

I've been feeling that R7RS was for people who didn't agree with R6RS or even hate. I know that's not true. I believe the Scheme spirit is not dropping off the necessary functionalities nor reminiscing good old days. But why R7RS looks like this? Or maybe that's because I'm not a pure Schemer?

At least there are loads of good stuff, one of them is implementing R7RS Scheme would be much easier than implementing R6RS one. So there would be loads of Scheme implementations again :P

Sagittarius 0.4.4リリース

Sagittarius Scheme 0.4.4がリリースされました。今回のリリースはメンテナンスリリースです。
ダウンロード

修正された不具合

•  sqrtに巨大数を与えると非正確数が返される不具合が修正されました
• (atan 0.0)がエラーになる不具合が修正されました
• string-scanが不正な値を返す不具合が修正されました
• get-output-string及びget-output-bytevectorから一度しか値が取り出せない不具合が修正されました
• UTCタイムオフセットがマイナスの地域でcurrent-dateがエラーを投げる不具合が修正されました
• aproposが動作しない不具合が修正されました

 改善点

• 巨大数のexptのパフォーマンスが改善されました

新たに追加された機能

• shared-object-suffix及びset-pointer-value!手続きが(sagittarius ffi)に追加されました
• dbi-fetch-all!に既定処理が実装されました
• key-check-value手続きが(crypto)に追加されました
• ->tlv及びread-tlv手続きが(tlv)に追加されました
• 64bitと32bitの識別子がcond-expandで使えるようになりました

TLVの構築

職業柄TLVとかスマートカードとかよく使うのだが、使う割りにパースするだけで構築するのが無かったので作ることにした。とりあえず現状で必要だったのはAPDUのデータの部分に必要なTLVの構築。

というか、作った。以下のように使える。

(import (tlv))

(->tlv '((#xC9 (#x4F . #xA000000310) ;; AID的な何か
               (#xA0 1 2 3 4))       ;; この行は適当
         (#xEF)))                    ;; タグEF 長さ0の値
;; -> (#<tlv :tag C9> #<tlv :tag EF>)
;;    => C9 0D 4F 05 A0 00 00 03 10 A0 04 01 02 03 04 EF 00

;; バイトベクタに変換するのはちと面倒だけどこんな感じ
;; tlv-list->bytevector作った方がいいかな？
(bytevector-concatenate (map tlv->bytevector (->tlv '(...))))

一応以下のようなS式を受け取ることができる。

tlv-list      ::= (tlv-structure*)
tlv-structure ::= (tag . value)
tag           ::= <integer>
value         ::= ((tlv-structure)*) | <bytevector>
               |  <integer>    | octet*

値部分のオクテットと整数はそれぞれu8-list->bytevector、integer->bytevectorでバイトベクタに変換される。正直これの必要性を今のところ感じていない。半分くらい勢いで入れてしまった。

実装してて思ったのは、TLV形式とS式の親和性は抜群にいいということ。まぁ、バイナリ版XMLみたいなもの(というと大分違うが、柔軟性という意味)なので、なんとなく分かっていたことではある。

自分以外にこのライブラリを使う人がいる気がしないのがポイントだろう。みんなもっとSchemeでスマートカードの操作をするべきである(暴言)

健全なマクロ

探せば山ほど解説があるので、今更というかGoogle検索の妨害するだけな気がするけど。

Twitterで健全マクロの実装をされている方がいて、そういえばコンパイラの環境を重点に置いた解説記事ってあったかなぁと思ったのがきっかけ。たぶんどこかにあるだろうけど・・・

まずは以下のコードを考える。

(import (rnrs))
;; from Ypsilon
(define-syntax define-macro
  (lambda (x)
    (syntax-case x ()
      ((_ (name . args) . body)
       #'(define-macro name (lambda args . body)))
      ((_ name body)
       #'(define-syntax name
           (let ((define-macro-transformer body))
             (lambda (x)
               (syntax-case x ()
                 ((e0 . e1)
                  (datum->syntax
                   #'e0
                   (apply define-macro-transformer
                          (syntax->datum #'e1))))))))))))

;; hygiene
(let ((x 1))
  (let-syntax ((boo (syntax-rules ()
                      ((_ expr ...)
                       (let ((x x))
                         (set! x (+ x 1))
                         expr ...)))))
    (boo (display x) (newline))))

;; non hygiene
(let ((x 1))
  (define-macro (boo . args)
    `(let ((x x))
       (set! x (+ x 1))
       ,@args))
  (boo (display x) (newline)))

;; expanded
(let ((x 1))   ;; frame 1
  (let ((x x)) ;; frame 2
    (set! x (+ x 1))
    (display x) (newline)))

;; frame 1
'(((x . 1)))

;; frame 2
'(((x . x))  ;; *1
  ((x . 1)))

話を簡単にするために、環境フレームは変数と値のペアをつないだもの(alist)とする。まぁ、多くの処理系がこの形式を使ってると思うけど。健全なマクロと非健全なマクロそれぞれの展開形はどちらも同じに(というと嘘が入るが)なる。コメントのframe 1及び2はその下にあるコンパイル時の環境フレームのイメージを示している。

ここで問題にするのは*1がそれぞれの場合で何になるかということ。

健全なマクロではマクロ内で定義された変数をマクロ外から参照することはできない。なので展開後の式とframe 2の環境イメージは実際には以下のようになる。

(let ((x 1))
  (let ((~x x))
    (set! ~x (+ ~x 1))
    (display x) (newline)))
;; frame
(((~x . x))
 ((x . 1)))

実際にどうなるかは処理系によって違うので、上記はあくまでイメージ。ここで問題になるのはletで束縛される変数のみがリネームされるということ。値の方は一つ上の環境フレームから参照されなくてはならない。(正直、これが実装者泣かせな部分の一つだと思っている。)
これの解決方法は僕が知っているだけで2つあって、1つは多くのR6RS処理系が取っている(Sagittarius以外はそうじゃないかな？)マクロ展開フェーズを持たせること。もう一つはSagittariusが取っているマクロ展開器が実行時環境とマクロ捕捉時環境の両方を参照する方法(正直お勧めではない)。

最初の方法だと、マクロ展開器は何が変数を束縛するかということを知っていなければいけない。 そうしないと上記の例のように変更してはいけないシンボルまでリネームしてしまうことになるからだ。値側のシンボルも実はリネームされるんだけど、マクロ束縛時の環境フレーム(frame 1)を参照して外側のletで束縛されたシンボルを見つけて同じ名前にするということが行われる。

2番の方法だと、マクロ展開器は両方の環境を適切に参照しつつ、コンパイラも変数の参照時に多少トリックが必要になる。正直書いててバグの温床にしかならないなぁと思ったのでお勧めではないが、この方法ならマクロ展開器は何が変数を束縛するかということを知らなくてもいいので、重複コードが多少減る。

ただ、どちらの場合もsyntax-rulesを実装するだけならたぶん必要なくて、Chibi Schemeのようにsyntactic closureを使ってer-macro-transformerを実現するとかでなんとかなる。(syntactic closure自体の実装で環境の束縛とか参照が必要にはなるけど、上記ほど複雑にはならない・・・はず。)

非健全なマクロではシンボルはリネームされないので、例で上げた展開後フォームそのままとなる。CLだと上記のようなマクロをSchemeのように動かしたいなら(gensym)とかwith-unique-namesとかを多用する必要がある。Lisp-2だったらたぶんそれでもいいだろうけど、Lisp-1だと泣けるだろうなぁと思う。

思ったとおり普通のマクロ解説記事の劣化版になってしまった。

OCI binding

If you are a professional programmer, then you can't avoid Oracle (or you need to be really lucky). I'm also one of them.

I was using either GUI (mostly Quantam DB) or Sagittarius ODBC binding. Both have some problems but by now it worked pretty fine for me. The reason I've decided to write it was it's getting annoying to use some thing not supporting to dump BLOB data thoroughly or requiring to configure connection setting somewhere difficult to find.

As you already knew, there is the API to use Oracle directly called OCI (Oracle Calling Interface). Well, since I have FFI then why not write a binding for it? It would make my life much easier than now. I was really hoping like that. If everything would have gone well, I wouldn't have written this article. Yes, I've met THE problem.

If you have an experience using ODBC, then you might have thought like this: 'this API requires cast no matter what'. OCI also has this and I call it problem. When this become a problem is actually certain situations such as binding parameters. Sagittarius converts input Scheme object to relevant C object. However it doesn't support casting. So at this point, my motivation had disappeared.

Then it revived like phoenix. My FFI doesn't support cast however most of the values can be converted to bytevector (it can be done by R6RS). Now I have got some lights to go through this crappy API jungle (it's well designed actually).

脱BoehmGCへの道 実装編(3)

ちょぼちょぼ動くようになってきたのだが、やはり一筋縄ではいかないなぁと言うのが正直な感想。

とりあえず現状で問題になっているもの。

1. eq?なハッシュテーブル
2. 昇格された領域にあるオブジェクトから参照されているオブジェクトの移動

1.はシンボル等のアドレスが変わると起きる問題。とりあえず急場でGC中に見つけたテーブルを全てリハッシュをするようにしたけど、これだと何の移動も起きなかったテーブルも影響するし、見つけられなかったテーブルは大変なことになる。けど、うまいやり方が思いつかない。

2.は昇格したオブジェクトから参照されているオブジェクトが移動した場合に起きる問題。とりあえず、理解を整理するための図が以下：

             Eden              |             Survivor
+------------------------------+------------------------------------+
|                              |             obj B                  |
|                              |            +-----+                 |
|             +----------------+------------+--*  |                 |
|        +----+----+           |            +-----+    +-------+    |
|        |  obj A  |           |            |  *--+----+ obj C |    |
|        +---------+           |            +-----+    +-------+    |
+------------------------------+------------------------------------+

obj Bはまぁ配列でも構造体でもなんでもいいんだけど、要するにポインタを格納するオブジェクト。っで1回目のGCで生き残って昇格したんだけど、次のGCとの合間に若い世代のオブジェクトobj Aを内に宿すことになったと。(具体的にはコードベクタが参照する識別子のルックアップを終えてglocを対象の場所に入れるとこれが起きる。まぁ、他にもあるだろう。)

っで、GCが起きると困ることになる。だれが移動先を解決するのかと・・・

実際はこの手のものはある程度解決されてるんだけど、どうも見逃しがあるっぽい。

コードベクタはクロージャとVMで同じものが共有されてるから、クロージャ側だけ更新してやればいいはずなんだけどなぁ、何を見落としてるんだろう・・・

詳解SBCL - Genesis

今日が土曜だということをすっかり忘れて「明日書く」なんて書いてしまった。自分の言動を曲げるのは好きじゃないので、家事の合間の時間で書く(土曜は以外にも忙しい)。

 GenesisとはSBCLがビルド時に生成するCコードのことだと思えばいい。実際にビルドプロセスを走らせると、src/runtimeディレクトリ以下にgenesisディレクトリが作成され、Lisp構造体からconfig.hまで必要な設定が生成される。要するにconfigureスクリプトである。

ビルド時に生成するなら設定とか環境依存の値だけでもいいような気がするが、なぜLispオブジェクトの構造体まで生成するのだろうか？

この辺実はまじめにソース(及びコメント)を読んでいないので推測の域を出ないのではあるが、たとえば世代別GCで使われているgeneration構造体あたりのコメントがなぞを解く鍵になるだろう(大げさ)。要約すると、コメントには以下のような記述がある。

注意：これの変更をしたら、Lisp側のコードも変更するように！もしくはそこにあるFIXMEに書かれてるようにしてくれ。

っで、FIXMEを見る。

 注意：GENERATION(とPAGE)はLisp内で定義されてGenesisでヘッダーに書き出されるべきだ。こことgencgc.cで二重定義なってやがる。

まぁ、要するにランタイム以外の部分って全部Lispで書かれてるから、メンテナンス性を考えると一箇所で定義した方がいいよねって理由だと思う。

これだけだと、「ふ～ん」で終わりそうなので(いや、実際書くほどのことはないのだ)、世代別GCに関係するGenesisを多少紹介。src/compiler/x86/parms.lispにLispオブジェクトが割り当てられるヒープ領域がある。定義はこんな感じ。

#!+win32   (!gencgc-space-setup #x22000000 nil nil #x10000)
#!+linux   (!gencgc-space-setup #x01000000 #x09000000)
#!+sunos   (!gencgc-space-setup #x20000000 #x48000000)
#!+freebsd (!gencgc-space-setup #x01000000 #x58000000)
#!+openbsd (!gencgc-space-setup #x1b000000 #x40000000)
#!+netbsd  (!gencgc-space-setup #x20000000 #x60000000)
#!+darwin  (!gencgc-space-setup #x04000000 #x10000000)

!gencgc-space-setupはsrc/compiler/generic/parms.lispに定義がある。第一引数はスモールスペースのアドレス(どこで使われてるかは確認してない)、第二引数が動的領域の開始アドレスである。これはX86の固有設定だが、他のアーキテキチャにも同様の定義があり、固定値を使っている。

合計4つになるとも思ってなかったけど、これをきっかけにSBCLのソースコードも怖くない、と思って読み手が増えることを願って。

詳解SBCL - 世代別GC(3)

昨日はルートのマーキングまで書いたので、今日はいよいよ実際にオブジェクトを動かすところ、つまりSBCLの世代別GCの肝の部分に触れていこう。

【scavenge】
この処理がすべての処理の鍵であるといってもまぁ、過言ではないだろう。とりあえず中身を見ていこう。(src/runtime/gc-common.cより、一部整形及び削除)

void scavenge(lispobj *start, sword_t n_words)
{
    lispobj *end = start + n_words;
    lispobj *object_ptr;
    sword_t n_words_scavenged;

    for (object_ptr = start; object_ptr < end; object_ptr += n_words_scavenged) {

        lispobj object = *object_ptr;

        if (forwarding_pointer_p(object_ptr))
            lose("unexpect forwarding pointer in scavenge: %p, start=%p, n=%l\n",
                 object_ptr, start, n_words);

        if (is_lisp_pointer(object)) {
            if (from_space_p(object)) {
                /* It currently points to old space. Check for a
                 * forwarding pointer. */
                lispobj *ptr = native_pointer(object);
                if (forwarding_pointer_p(ptr)) {
                    /* Yes, there's a forwarding pointer. */
                    *object_ptr = LOW_WORD(forwarding_pointer_value(ptr));
                    n_words_scavenged = 1;
                } else {
                    /* Scavenge that pointer. */
                    n_words_scavenged =
                        (scavtab[widetag_of(object)])(object_ptr, object);
                }
            } else {
                /* It points somewhere other than oldspace. Leave it
                 * alone. */
                n_words_scavenged = 1;
            }
        } else if (fixnump(object)) {
            /* It's a fixnum: really easy.. */
            n_words_scavenged = 1;
        } else {
            /* It's some sort of header object or another. */
            n_words_scavenged =
                (scavtab[widetag_of(object)])(object_ptr, object);
        }
    }
    gc_assert_verbose(object_ptr == end, "Final object pointer %p, start %p, end %p\n",
                      object_ptr, start, end);
}

与えられたstartの中身を順番に見ていき、Lispオブジェクトでかつ既に移動されたものならば移動先に置き換える、まだならscavtabテーブルに格納された実際の処理に処理を委譲する。*object_ptrが何を指すのか今一理解できなくて、SBCLのGCはどう動いているのだろうなんて疑問に思ったのは秘密である(well if you have read my articles or twitter, you know...)。ここで、ポイント(と僕が思う部分)は与えられたstartは必ずヒープ領域を指すことだろう。また、特に何もしなくてもオブジェクトの割り付けられたメモリ境界を指すということだ。これは、scavengeが呼ばれる部分を見れば分かるのだが、事前にページもしくはリージョンの開始位置を計算しているのと、割り付けられたオブジェクトの位置を直接渡していることに起因する。詳しくはsrc/runtime/gencgc.cにあるgarbage_collect_generationを参照されたい(多分後で多少触れるけど)。

ではscavtabには何が入っているのだろうか？

この辺は実は非常に読みやすくて、scav_のプリフィックスがついた関数がsrc/runtime/gc-common.cにある。それらを眺めればどの処理がどのオブジェクトに対応しているのか大体わかるという寸法。実際の振り分けは、widetag_ofが適切にオブジェクトからタグを取り出すのでそれにしたがっている。また、テーブルの設定も同様に行われる。タグが255もあるのでテーブルの設定はすごく長い処理になっているのはまぁご愛嬌だろう(src/runtime/gc-common.cのgc_init_tables参照)。

とりあえず、一つ中身を見てみよう。Lispといえばでリストを見る。

static sword_t scav_list_pointer(lispobj *where, lispobj object)
{
    lispobj first, *first_pointer;

    gc_assert(is_lisp_pointer(object));

    /* Object is a pointer into from space - not FP. */
    first_pointer = (lispobj *) native_pointer(object);

    first = trans_list(object);
    gc_assert(first != object);

    /* Set forwarding pointer */
    set_forwarding_pointer(first_pointer, first);

    gc_assert(is_lisp_pointer(first));
    gc_assert(!from_space_p(first));

    *where = first;
    return 1;
}

処理としては非常に簡単で、与えられたリストobjectをtrans_listでコピー、その後whereが指すポインタと入れ替える。trans_listはリストの指すcarとcdrを単にコピーしているだけで、その中身までは見ない(コード貼り付けると無駄に長くなるので割愛)。これによってリニアタイムの処理になる。

では、リストの中身が指すポインタは一体誰が救うのか？

ここまで読んでいれば勘のいい人は既に分かっているだろうが、scavengeである。実際にscavengeは以下の3つの段階で呼ばれる。

1. 割り込みハンドラ、バインディングスタック及びSBCLの静的領域の回収
2. GC対象外の世代の回収
3. 新しい世代の回収

の3つである。ものすごく簡単に言えば、GC対象のヒープ領域以外のヒープをすべて回収し、GC対象の領域でピン止めされたページ以外はごみとするという感じである。

これで大まかなSBCLのGCの流れは終了。書き忘れたこととかあるかな？

今日はここで時間切れ。Genesisについては明日触れることにする。

Bignumの最適化

事の発端は以下の記事

#:g1: XCLがSBCLより速いところ

最終的に行き着くのはBignumのexptでそいつが遅いことは実は分かっていた(手元のマシンで測ると、Gaucheで20秒ちょっと、Sagittariusでは30秒以上かかっていた)。っで、まぁ、遅いのは気に入らないので何とかならないかと無い知恵と頭をフル回転させることにした。

大抵Bignumが遅い一番の理由はメモリである。で、実装を見てみると豪華に作っては捨てるを繰り返していたのでここを何とかしようと頑張ってみた。ちょっとしたベンチマーク。

(import (time))
(time (begin (expt (* 100000 100000) #x2FFFF) 1))

乗数が半端なくでかい場合という感じのもの。結果(上が0.4.3、下が開発版)。

% sash test.scm

;;  (begin (expt (* 100000 100000) 196607) 1)
;;  147.578838 real    147.4670 user    0.000000 sys

% ./build/sash.exe test.scm

;;  (begin (expt (* 100000 100000) 196607) 1)
;;  28.751352 real    28.68900 user    0.016000 sys

大きく効果があった感じがする(とは言っても5倍か)。ついでにこの記事の元になったベンチマーク結果。

% sash test.scm

;;  (begin (^^ 10 6) 1)
;;  33.010235 real    33.01000 user    0.000000 sys

% ./build/sash.exe test.scm

;;  (begin (^^ 10 6) 1)
;;  4.867294 real    4.867000 user    0.000000 sys

7倍程度の高速化。まぁ、何が悲しいかと言えば、これでもYpsilonに並んだ程度なのと、Mosh(gmp)より50倍程度遅いことか。ま、SBCLに並んだということで満足してしまおう・・・

詳解SBCL - 世代別GC(2)

今日はいよいよメモリの割付とGCについて。朝の暇な時間を使っているのでGCは最後まで書けないかも。

【メモリ割付】
SBCLではメモリの割付はリージョンを通して行うというのは昨日書いた。それをすると何がうれしいかという話である。
たとえばBoehm GCではメモリは要求サイズをフリーリストから取ってくる。もちろん実際にはもっと最適化されていて、(記憶が正しかったら)8、16、24、といった感じでよく使われる小さいオブジェクトと大きいオブジェクトで別に管理している。っで、8バイトなら8バイト領域のフリーリストから取ってくるのでメモリがフィットするかどうかを調べる必要がないといった感じ(だったはず)。
では、SBCLではどうか？多くのコピーGCと同じくメモリの割付は先頭メモリのポインタを返すだけである。なので(おそらく)高速に動く。もちろん、ページ単位でメモリの割付を行うのでリージョンが管理しているアドレスの末尾を超えるようなサイズのチェック等はある。
実際に割付のコードを見てみよう。 (src/runtime/gencgc.cより、一部整形及び削除)

static inline lispobj *
general_alloc_internal(sword_t nbytes, int page_type_flag, struct alloc_region *region,
                       struct thread *thread)
{
    void *new_obj;
    void *new_free_pointer;
    os_vm_size_t trigger_bytes = 0;

    if (nbytes > large_allocation)
        large_allocation = nbytes;

    /* maybe we can do this quickly ... */
    new_free_pointer = region->free_pointer + nbytes;
    if (new_free_pointer <= region->end_addr) {
        new_obj = (void*)(region->free_pointer);
        region->free_pointer = new_free_pointer;
        return(new_obj);        /* yup */
    }
              :
    /* 削除 (GC起動用コード)*/
              :
    new_obj = gc_alloc_with_region(nbytes, page_type_flag, region, 0);

    return (new_obj);
}


/* Allocate bytes.  All the rest of the special-purpose allocation
 * functions will eventually call this  */
void *
gc_alloc_with_region(sword_t nbytes,int page_type_flag, struct alloc_region *my_region,
                     int quick_p)
{
    void *new_free_pointer;

    if (nbytes>=large_object_size)
        return gc_alloc_large(nbytes, page_type_flag, my_region);

    /* Check whether there is room in the current alloc region. */
    new_free_pointer = my_region->free_pointer + nbytes;

    if (new_free_pointer <= my_region->end_addr) {
        /* If so then allocate from the current alloc region. */
        void *new_obj = my_region->free_pointer;
        my_region->free_pointer = new_free_pointer;

        /* Unless a `quick' alloc was requested, check whether the
           alloc region is almost empty. */
        if (!quick_p &&
            void_diff(my_region->end_addr,my_region->free_pointer) <= 32) {
            /* If so, finished with the current region. */
            gc_alloc_update_page_tables(page_type_flag, my_region);
            /* Set up a new region. */
            gc_alloc_new_region(32 /*bytes*/, page_type_flag, my_region);
        }

        return((void *)new_obj);
    }

    /* Else not enough free space in the current region: retry with a
     * new region. */
    gc_alloc_update_page_tables(page_type_flag, my_region);
    gc_alloc_new_region(nbytes, page_type_flag, my_region);
    return gc_alloc_with_region(nbytes, page_type_flag, my_region,0);
}

前提条件として要求サイズは8の倍数(src/runtime/alloc.cで切り上げられる)である必要がある。gc_alloc_internalを見ると分かるが、要求されたサイズが末尾アドレスを超えない場合は先頭アドレスを返し、末尾アドレスを増やす。超える場合は新たにリージョンの割付を行い、やはり先頭アドレスを返す(gc_alloc_with_region)。
Boehm GCと違いSBCLではヒープから割り付けられるオブジェクトはLispオブジェクトのみと割り切っている(はずな)ので、メモリはヘッダ情報等を持つことはない。 逆に、consを除く全てのオブジェクトはヘッダ情報を持っていて、そこからオブジェクトのサイズ等を割り出すことが可能である(はず、自信ない・・・)。
まぁ、メモリの割付なんてそう面白いところはないので、適当に切り上げて次へ(逃走ともいう)。

【GC】
さて、ようやく本題のGCである。SBCLではGCの起動方法は2種類あって、ユーザーが直接Lisp手続きのgcを叩くのと、リージョンの使用メモリがトリガーバイト以上になった際に勝手に起動されるのの2種類である。(前者しか用意されてなかったらGCじゃないわね・・・)

では、GC起動の大まかな流れを見てみよう。流れとしては以下のようなフローになる。

1. メモリ割付時に*gc-pending*フラグにtをセットする
2. ついで擬似アトミックに割り込みフラグをセットする
3. 割付終了後、擬似アトミックの割り込みをチェック
4. 割り込みがあれば割り込みを処理させる
• 割り込みはCPU割り込みで実現される(int3もしくはud3命令)
5. 使ってないスタックをきれいにする
6. 世界を止める
• SBCLではincrementalマーキングとか、mostly concurrent GCとか軟弱なものはなく、漢らしくGCの間世界には止まってもらう
7. ごみ集めする
• 基本的には第一世代のみを行うが、必要(次の世代もメモリが足りない)ならば以降の世代も行う
• 明示的にどの世代をGCするかの指定も可能
8. *gc-pending*にnilをセットする
9. 世界を動かす
10. ファイナライザを起動させる

ファイナライザはGC終了後に起動されるのは(多分)Boehm GCでも同じだと思う。(ファイナライザがメモリを要求したらとか考えるとそうあった方が便利な気がするし。)
SBCLのファイナライザはLisp側で実装されていて、起動時にはGCが起きないようになっている(src/code/final.lisp参照)。

世界を止めるのはマルチスレッドでは重要だけど、今回はシングルスレッドの流れを追っているので深くは言及しないが、pthread_killでUSR2(内部でGC用シグナルとして定義)を送りスレッドを止めている。開始はその逆。わざわざシグナルを使っているのは、標準POSIXのpthreadではサスペンドがサポートされていないことと、Linuxのpthreadには拡張としてのpthread_suspend_npに対応するものがないことだと思われる。(Windows、*BSDとかだとスレッドのサスペンドが可能)。

【ルートマーキング】
SBCLにおいてGCルートと考えられているのは2つ、スタックとレジスタである。 マーキングは非常にシンプルで、スタックの底から現在のスタックポインタまでにあるヒープ領域に取られたLispオブジェクトもしくはコード(マシンコード)っぽいものを保存する。レジスタ上でも一緒。スタックの底はpthread_attr_getstackで取得(Windows除く)。

実際に何をするかと言えば、ルート上にあるそれっぽいオブジェクトが所属するページ丸ごとピン止めするのである。ページは最低でも4096バイトあるので、ある意味漢らしい。まぁ、いろいろ考えるよりは楽だわね。(詳細はsrc/runtime/gencgc.cにあるpreserve_pointerを参照)

 タイムオーバーなので今日はこのくらいで。続きはまた明日。

詳解SBCL - 世代別GC(1)

全てのSBCLソースリーディングをしている人の手助けになることを願って。

そろそろ詰め込んだものがページアウトしそうなのでちょっと外部記憶に書き出しておこう。タイトル的には仰々しいことを書くような煽りだが、実際はそうでもないのでかなり釣りです。また、誤りが含まれている可能性が多分にあるので見つけたら指摘していただけるとうれしいです。

(1)となっているのは次がある予定だから。というか、全てを一つの記事するのはきついので。

以下の記事は世代別GCとは何ぞやということが分かっている人が対象になります。また、話を可能な限り簡略にするため、環境はX86、POSIX、シングルスレッド環境とします。言及しているSBCLのソースはバージョン1.1.5のものです(2013年3月20日現在の最新)。

【概要】
SBCLではメモリの管理は、リージョン、エリア、世代、ページの4つのグループを使って行われる。簡単なイメージは以下のような感じ。

                 mutator
                    |
                 gc_alloc
                    |
+-------------------------------------------+
|                region                     |
+-------+------+----------------------------+     +---------------------------+
|  page | page | ...                        |  -- |         * area            |
+-------+------+--------------+-------------+     +---------------------------+
| generation 0 | generation 1 | ...         |
+--------------+--------------+-------------+

* エリアはGCの際にのみ使われます。

メモリは割付は必ずリージョンを通して行われ、リージョンはページの開始アドレス、現在のフリーなアドレスを保持します。
ページは使用されているバイト、リージョンからのオフセット、所属している世代、その他もろもろの情報を保持します。リージョンからのオフセットは結構重要で、ページのアドレスから実際のリージョンの開始アドレスを割り出せます。
世代は所属しているページの最初のアドレス、その他GC回数等の情報を保持します。

恐らくここまでは他の世代別GCとは大きく変わらないと思います。

実際のメモリ割付及びGCに入る前に登場人物の説明。

【ページテーブル】
SBCLでは全てのページはページテーブルで管理されます。ページテーブルはページの配列で、その個数はヒープサイズから割り出されます。実際のコードは以下の通り(src/runtime/gencgc.cのgc_initより)

    /* Compute the number of pages needed for the dynamic space.
     * Dynamic space size should be aligned on page size. */
    page_table_pages = dynamic_space_size/GENCGC_CARD_BYTES;

                           :

    /* The page_table must be allocated using "calloc" to initialize
     * the page structures correctly. There used to be a separate
     * initialization loop (now commented out; see below) but that was
     * unnecessary and did hurt startup time. */
    page_table = calloc(page_table_pages, sizeof(struct page));

GENCGC_CARD_BYTESはビルド時にgenesis(多分2以降の記事で書く)で定義される値。ちなみにX86環境では4096。
dynamic_space_sizeは大域変数でSBCL起動時にヒープ指定用。デフォルトはsrc/runtime/gc-common.cで以下のように定義:

os_vm_size_t dynamic_space_size = DEFAULT_DYNAMIC_SPACE_SIZE;

ちなみに、DEFAULT_DYNAMIC_SPACE_SIZEの定義はsrc/runtime/validate.hにあり、以下の通り：

#ifdef LISP_FEATURE_GENCGC
#define DEFAULT_DYNAMIC_SPACE_SIZE (DYNAMIC_SPACE_END - DYNAMIC_SPACE_START)
#else
#define DEFAULT_DYNAMIC_SPACE_SIZE (DYNAMIC_0_SPACE_END - DYNAMIC_0_SPACE_START)
#endif

この記事では世代別GCを扱っているので、LISP_FEATURE_GENCGCは定義されている。DYNAMIC_SPACE_ENDとDYNAMIC_SPACE_STARTはgenesisでビルド時に割り出される固定アドレスである。

話が逸れたので、ページテーブルに戻す。 ページテーブルはSBCLが管理するヒープ外で管理されており、具体的にはcallocで割り付けられたメモリ、当然だがGCの対象にならない。ページ、ページテーブルは実際のヒープを指すわけではなく、そのメタ情報を扱っている。実際にあるページが指すヒープは以下のように割り出される(src/runtime/gencgc.c
より)：

/* Calculate the start address for the given page number. */
inline void *
page_address(page_index_t page_num)
{
    return (heap_base + (page_num * GENCGC_CARD_BYTES));
}

heap_baseはDYNAMIC_SPACE_STARTと同値である(gc_initで設定されている)。1つのページはGENCGC_CARD_BYTESで区切られるのでこのように計算できる。

【リージョン】
シングルスレッド環境ではリージョンはたったの2つ、boxed_regionとunboxed_regionである。基本的な違いは、前者は割り付けられたメモリ内にポインタを持ち、後者は持たないというだけのもの。たとえば、CLのconsは前者のリージョンから、basic_stringは後者のリージョンから割り付けられる。

リージョンは実際のヒープアドレスを持ち、メモリの割付を行う。

【世代】
SBCLでは6つの世代＋スクラッチ用世代の7つの世代が用意されている。スクラッチ用世代はGCの際にコピー用のヒープを保持する世代で、GC対象の世代がプロモートしない場合に使用される。
他の世代別GCと同様にある一定回数のGCが行われかつ生き残ったオブジェクトは次の世代にプロモートされる。ちなみに、デフォルトでのプロモートGC回数は1回。つまり、2回生き残ると次の世代に昇格する。このパラメータはLISP側から世代毎に調整できる(src/code/gc.lisp参照)。

疲れたので今日のところはここまで。明日辺りにメモリの割付以降の話を書く。

脱BoehmGCへの道 実装編(2)

昨晩BBCのコミックリリーフを見ながら(寝ながら)実装方針のようなものを考えていた。

とりあえず、SBCLがどのようにポインタ内のポインタを解決しているのかは考えないようにして(たぶんscavengeがその辺をうまいこと扱っているんだと思うけど)、まずは動くものを作ろうという感じである。

とりあえず現状での違いを列挙
【SBCL】

• 保存するポインタは、スタック及びレジスタのみ
• 静的領域は持ってない
• 動的にコードを生成するのだからある意味当たり前ではある
• 全てのポインタは中身にアクセスすることなくおよそLispオブジェクトかの判別が可能
• これによって実際にscavenge及びtransportを行う手続きをテーブルで持つことが可能
• 全てのポインタからおよその割付サイズを割り出すことが可能

【Sagittarius】

• 保存するポインタは、スタック、レジスタ及び静的領域
• 結構な勢いでstaticなオブジェクトを持っているので変更したくない
• Schemeオブジェクトかどうかの判別にはポインタの中身を見る必要がある
• 単なるコンテナのpairはどうしても一般的なメモリとしてしか判別できない
•  動的領域から割り付けられたものならばメモリヘッダからサイズの割り出しが可能
• あいまいなポインタがきた場合に多少困る
• 一応チェックが走るけど、不安

 今更ながらにオブジェクトをタグにしておけばよかったと多少後悔しているが、まぁ泣くまい。

っで、実装戦略(というほどでもないが)だけど、現状で困っているのはポインタ内ポインタの保存である。とりあえず、スタック及びレジスタ上で参照されているポインタを動かすのは嬉しくないのでこいつは無視して(不可能ではないが)、静的領域である。
いったん保存されたアドレスはページ単位で移動を禁止される、なので保存先のアドレスから中身をたどっていき全てのオブジェクトを新たな世代(もしくは単にページ)に移動させる。この際に既に保存されているものであれば動かしてはいけないのでそのままにする必要がある。そうすると、たどれるポインタのうち、スタック、静的領域及びレジスタ上にないものは全て昇格することになり、世代別GC的に動く(ような気がする)。
ここで気になるのは、スタック上で保存されたポインタで、こいつからたどれるものはどうしようかなぁというところである。まぁ、静的領域と同様にやってしまってもいいような気はするのだが、そうするとまだ保存されていないポインタを動かすことになるような気がしている。あぁ、でも動いた先をいれてやれば問題ないのか？あんまりアグレッシブに動かすと1が10になる問題が起きるよなぁ。

とりあえずこの方針で行くことにする。

脱BoehmGCへの道 準備編(4)

実装編書いたのに準備編に逆戻りｗ

コードリーディングに関するのは準備編にまとめようと思っているだけなので実装をしていないわけではないんだけど、妙な感じではある。

SBCLのコードを読んでてどうも納得がいかないというか、理解ができていない部分がある。オブジェクトのコピーである。他のGCと同様SBCLも世代別GCも最初にスタックエリア、静的エリア(SBCLが内部で持ってるもので、.dataとかではない)におかれているポインタの保存をした後にごみ集め(scavenge)するようになっている。

まぁ、これだけ見れば特に問題ないように見えるんだけど、世代別GCではコピーが発生する。コードを読んでいるとscavenge_newspace_generationがコピーを行うとコメントに書いてあるのだが、 最終的にそいつはscavengeにたどり着き普通に回収しているように見える。また、ポインタを保存する際にそのオブジェクトが保持している中身には一切の興味を示していない。つまり、ルートからたどれる最初のオブジェクトしか保存していないようにみえるのだ。(実際は、ページ丸ごと保存しているので4096バイト(32ビット？)ごそっと保存してるんだけど。)

これはLisp側のコードも解析しないといけないかなぁと思い、ちょっと眺めてみた。知っている人は知っていると思うけど、SBCLはVOPと呼ばれる仮想アセンブリ言語があってこいつが非常に読みづらい。頑張ってたどっていくと、X86環境ではメモリの割付はallocation手続きからalloc_overflow_*(ecxとかとか)が呼ばれ最終的にCで定義されたallocそして、世代別GCならgeneral_allocが呼ばれることが分かった。ということは、Lisp側で割り付けられようが、CのAPI使おうが(SBCLは外部にAPIを公開してないので不可能だけど)、最終的には同じメモリが同じように割り付けられているはずである。

となってくると、たとえばベクタなんかが中にLispオブジェクトを保持していた場合どうにかしてコピーしないとまずいことになると思うんだけど、どうなってるんだ？確かに、scav_other_pointerではオブジェクトの最初のアドレスからヘッダをとってコピーしてるんだけど、こうあるべきなのか？

そもそも、general_allocを勘違いしている可能性があるといえばあるんだけど・・・

Sagittarius 0.4.3 リリース

Sagittarius Scheme 0.4.3がリリースされました。今回のリリースはメンテナンスリリースです。
ダウンロード

【修正された不具合】

• evalがunbound variable errorを投げる不具合が修正されました
• 閉じられたソケットに対してsocket-sendを呼ぶとSIGPIPEで落ちる不具合が修正されました
• キャッシュファイルをロードする際にライブラリのインポート順序が逆順になっている不具合が修正されました
• bytevector->stringがSIGILLを起こす不具合が修正されました
• R7RSのloadにenvironment引数を渡すとカスタムリーダが認識されない不具合が修正されました

【改善された点】

• メモリの使用量が多少少なくなりました

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

• リモートREPLライブラリ(sagittarius remote-repl)が追加されました

【新たに追加された機能】

• (rfc tls)がサーバソケットとTLS 1.2をサポートするようになりました
• (rfc x509)ライブラリに基本的な証明書を作成するための手続きが追加されました
• (rfc x509)に証明書をバイトベクタに変換する手続きが追加されました

脱BoehmGCへの道 実装編(1)

SBCLの保守的世代別GCを参考(*1)に自前GCをちょぼちょぼ実装している。メモリの割付はいけるがGCがうまいこと動いていないのですぐにSEGVる。

とりあえず現状ぶつかっている妙な挙動と実装上のメモ

【実装上のメモ】

• SBCLではヒープに割り付けられたメモリは*ほぼ*Lispオブジェクトとして扱える
• 一部違うものもあるっぽいが、少なくとも2ワードはあると断定できるらしい
• Lispオブジェクトならヘッダーが第一ワードにきて、そいつからサイズも特定できるっぽい
• さすがにこれは真似できない
• ↑をなんとかするためにメモリブロック＋ヘッダという構造を導入
• サイズとフォーワードチェック用の構造体
• フォーワードチェック用に1ビット、残りはファイナライザを詰める
• アライメントの関係上2ワード取るようにする
• 32ビットなら8バイトの無駄
• でも、ファイナライザもいれないといけないしということで妥協
• スタックの底は頑張ってOSコールで取るようにした
• データセグメントは_data_startとかで頑張る
• Windowsはどうしようかね？
• 前に書いたハックで頑張るか
• Cygwin上のmmapについて
• MAP_NORESERVEを指定しないようにした
• 512MB必要としているので、Cygwinのメモリだとスワップ領域を確保しないときついはず、ということで

【妙な挙動】
主な開発環境はCygwinなので、とりあえずの妙な挙動はCygwinということになる。っで、妙な挙動。

静的領域を取るためにCygwinでは_data_start__系の値を使うのだが、GDB上で見ると正しく取れているように見えるんだけど、実際には意味不明な値が飛んできている。 たとえば、GDB上では開始アドレスは0x6a5a4000となっているんだけど、実際には0x3000とどう見てもアドレスに見えない値が取れている。

追記：
多分メモリ破壊的な何かが起きてる感じである。最初のGCではOKなのに2回目で死んでる。

追記の追記：
単にアホなミスであった。まず自分から疑うべきである・・・

*1 参考＝コピペとも言う。コピペプログラマは適当にアジャストするのも得意なのであるw

脱BoehmGCへの道 与太話

SBCLのコードを読んでいると、コンパイラとかデバッガを作るということがいかに環境べったりのコードを書く必要があるかということを実感させられる。もちろん、それを#ifdefで区切るのか、もっと抽象化してやるのかは実装者の好みだろう。

コード読んでて感動したのが以下のコメント。

    /* On entry %eip points just after the INT3 byte and aims at the
     * 'kind' value (eg trap_Cerror). For error-trap and Cerror-trap a
     * number of bytes will follow, the first is the length of the byte
     * arguments to follow. */
    trap = *(unsigned char *)(*os_context_pc_addr(context));

これは、Windowsなら、handle_breakpoint_trap、x86環境ならsigtrap_handlerにあるコードなんだけど、どうやってその'kind'を飛ばしているかというと以下のアセンブラから飛んでくる。

 .globl GNAME(do_pending_interrupt)
 TYPE(GNAME(do_pending_interrupt))
 .align align_16byte,0x90
GNAME(do_pending_interrupt):
 TRAP
 .byte  trap_PendingInterrupt
 ret
 SIZE(GNAME(do_pending_interrupt))

別にdo_pending_interruptである必要はないけど、ようするにこんな感じで飛ばすのである。んで、C側ではEIP(x86)の次のバイトを読む。SIGTRAP飛ばすのにint3もしくはud2使ってる。ud2だとSIGILLか。

最初なんでOSのPCなんて必要なんだろうと思ったけど、こういう理由でいるみたい。「完全解説SBCL」なんて本が出たら多分買うと思う。

脱BoehmGCへの道 準備編(3)

実際のコードの準備に入る。

Twitterでも呟いたのだが、SBCLは*_SPACE_(START|END)という奇妙な固定アドレスがあって、これらは環境(OS、アーキテクチャ)によって値が違う。Genesisというビルド時に走るソース生成のLispがこいつらを作るのだけど、この値を使ったら負けな気がしてるのと、ポータビリティが下がるどころの話じゃないのでなんとかデータセグメントをランタイムで取れないかを探っている。(ここまで前置き)

Linuxとか*BSD環境だと、etextとかedataとか使えるのだけど(GCC?)、Windowsだとそうは問屋がおろしてくれない。Boehm GCはこの辺をMEMORY_BASIC_INFORMATIONと多少のハックで何とかしているのだが、.dataセグメントをとるのなら以下の方法でもいけることが分かった。

/* dll.c */
#include <windows.h>
#include <winnt.h>
#include <dbghelp.h>
#include <stdio.h>

__declspec(dllexport) void dump(HANDLE hModule)
{
  char *dllImageBase = (char*)hModule;
  IMAGE_NT_HEADERS *pNtHdr = ImageNtHeader(hModule);
  IMAGE_SECTION_HEADER *pSectionHdr = (IMAGE_SECTION_HEADER *) (pNtHdr + 1);
  int i;
  printf("base   : 0x%p\n", dllImageBase);
  for (i = 0 ; i < pNtHdr->FileHeader.NumberOfSections ; i++) {
    char *name = (char*) pSectionHdr->Name;
    printf("name   : %s\n", name);
    printf("section: 0x%p\n", dllImageBase + pSectionHdr->VirtualAddress);
    printf("size   : %d\n", pSectionHdr->Misc.VirtualSize);
    pSectionHdr++;
  }
}

__declspec(dllexport) int show()
{
  HANDLE hModule = GetModuleHandle("dll.dll");
  dump(hModule);
  return 0;
}

/* linked.c */
#include <windows.h>
#include <winnt.h>
#include <dbghelp.h>
#include <stdio.h>

__declspec(dllimport) int show();

int main()
{
  HANDLE hModule = GetModuleHandle(NULL);
  char *dllImageBase = (char*)hModule;
  IMAGE_NT_HEADERS *pNtHdr = ImageNtHeader(hModule);
  IMAGE_SECTION_HEADER *pSectionHdr = (IMAGE_SECTION_HEADER *) (pNtHdr + 1);
  int i;
  printf("base   : 0x%p\n", dllImageBase);
  for (i = 0 ; i < pNtHdr->FileHeader.NumberOfSections ; i++) {
    char *name = (char*) pSectionHdr->Name;
    printf("name   : %s\n", name);
    printf("section: 0x%p\n", dllImageBase + pSectionHdr->VirtualAddress);
    printf("size   : %d\n", pSectionHdr->Misc.VirtualSize);
    pSectionHdr++;
  }

  printf("should be in DLL\n\n");
  show();

  return 0;
}

/* load.c */
#include <windows.h>
#include <stdio.h>

typedef void (*Dump)(HANDLE);

int main()
{
  HMODULE handle = LoadLibrary("dll.dll");
  Dump dump;

  dump = (Dump)GetProcAddress(handle, TEXT("dump"));
  if (dump) {
    dump(handle);
  } else {
    printf("something wrong\n");
  }
  return 0;
}

問題なのはLoadLibraryではなくリンクされた方だったりする。GetModuleHandleは.exeのハンドルを取得するらしく、DLLの名前を渡さないと.exeと同じアドレスになった。おそらくDllMainでDLLがアタッチされた際に引数として渡されるハンドルを保存しておくのがいいだろう。LoadLibraryの方は逆にハンドルが返されるので、既存の拡張DLLのコードをいじることなくいけそうである。

唯一これが問題だなぁと思うのは、dbghelp.libをリンクする必要があることだろうか。おそらくXP以上の環境ならMSVCライブラリを入れなくてもあると思うんだけど、ちょっと不安。

ふとBoehm GCのこの辺のハックを読んだときに思ったのだが、Boehm GCってDLLを呼ぶたびにGC_INIT呼ばないとまずいのかな？それともLoadLibraryをフックしてる？じゃないとDLLごとの静的領域がルートに入らない気がするのだけど・・・

脱BoehmGCへの道 準備編(2)

Scheme48の世代別GCを読むと言ったな、あれは嘘だ・・・orz

引き続きSBCLの世代別GC。さすがにこの規模のコードを2,3時間でっていうのは無理があって、読んでるうちにいろいろ発見がある。

GC自体はcode/gc.lispで定義してあって、こいつが世界を止めてごみ集めしてまた世界を動かしてる。これは誰が読んでるんだ？メモリ割付はGCが必要かどうかのフラグをセットしてるだけだし。
以下はメモ：

• Windows以外の環境ではsignal (SIG_STOP_FOR_GC: SIGUSR2)を使って世界を止めてる
• Windowsではそんなシグナルないので、safepointと呼ばれるものでごにょごにょしてる
• 多分CreateEventで何とかなるか？
• 世界を止めるために作られたスレッドを全て管理している
• そんで、pthread_killでSIG_STOP_FOR_GCを送りスレッドを止める
• なんで現在のスレッド以外を再び起こしてるんだろう？
• そして起こせたらエラーで死んでる・・・
• 単なる再チェック？
• シグナルを送らないとGCが発生しないように見えるけど、シグナル送るのはstop the worldという矛盾
• interrupt_handle_pendingのコメントに書いてあった
• allocが*gc-pending*にtを入れる
• set_pseudo_atomic_interruptedが呼ばれる
• do_pending_interruptが呼ばれる(アセンブラなんだぜこれ・・・)
• int3もしくはud2命令でSIGTRAPを送る
• 後ろにtrap_PendingInterruptをつけて識別する
• handle_trapが起動される
• ようやくinterrupt_handle_pendingにたどり着く・・・

なんでここまでしてシグナルを使いたいのかは不明。いろんな兼ね合いがあるのだろう。(シグナルを送るとスレッドのことを考えなくてもいいとか？GCの起動をぎりぎりまで遅らせたいとか？)

なんとなくばらばらなピースが合わさってきた感じがする。

脱BoehmGCへの道 準備編(1)

2があるかは知らない。(たぶんある、Scheme48で)

SBCLは2種類のGCをサポートしていて、(たぶん)デフォルトでは保守的世代別GCが使われている。しかも、ランタイムの部分はCで書かれているといるので、これは読まなければならないだろうと思って読んだ(理解は微妙・・・)。

世代別GCがなんぞやという人はここが詳しい：GCアルゴリズム詳細解説

GCを実装する上で(個人的に)重要な点は、割付とGC部分の2箇所。メモリに対してどんなメタ情報を付与するのかと、どのようにルートをたどるのかという部分。この辺はGCレベル(何それ？)が高い人は違うのかもしれないが、レベル1以下の僕にはそう見える。

SBCLはメモリの割付をリージョンと呼ばれるヒープから割り付ける(スモールオブジェクト)。っで、こいつはページテーブル内で管理されていて、必要に応じて拡張されたりしている。(まじめに追ってない・・・)。

GCは保守的になる必要がある場合のみに保守的に行われる。具体的にはX86、X86_64な環境。ただし、それらの環境でもgc_and_saveで呼び出された場合はPreciseで行われる。(たぶんコアイメージの保存用？)。
保守的なGCは外部C呼び出し(Foreign C call)の際にのみ起きる(とコメントにある)ので、スレッドコンテキストからその辺りのPCを持ってきてポインタらしきものをマークしている。マークが終わると回収なのだが、回収はX86、X86_64以外の環境ではスタックを問答無用で回収する。どういう仕組みでX86、X86_64以外の環境がPrecise GCになるのかは(今のところ)不明。(FFIが無いとか言うシンプルな理由かもしれない)。回収自体はポインタサイズ(種類？)で回収の仕組みが違う。それぞれに適した回収と移動が実装されている。(うへぇ・・・)

読んでて気になったというか、やっぱりなぁと思ったのは、保守的GCという性質上どうしてもOS、アーキテクチャ依存の部分が出ざるを得ないということ。SBCLはその辺がかなりうまく分離されているので対象のコードを読むこと自体はあまり苦ではないのだが、自前でGCを持つということはBoehmGCが行っているハックを大なり小なりやる必要があるということが分かってちょっとがっかり。
後、SBCLはビルド時にホストとターゲットをビルドするのだけど、ホストがランタイムの設定及びヘッダファイル郡(genesis)を生成する。もっとも気になるのはthread.hでこいつはGCのコードでもスレッドコンテキスト等を取得する際に多用されている。これがビルド時に生成されるということは、ターゲットの環境によって中身が大きく変わる可能性があるということ(構造体のオフセットまで全部生成されてるし)。

規模が規模だけに全部を把握するのは難しいが、参考になる部分はたぶんにありそう。

脱BoehmGCへの道 計画編

別にBoehmGCに対してそこまで不満があるわけではないのだけど、Sagittariusは既にインストールされているライブラリ(Unix系環境)もしくは新規にダウンロードして特に手を入れることなく使う(Windows環境)という手法をとっているので、サポートしていない環境で動かすのに支障がでる。(たとえばFreeBSDの最新のportsでは不具合があってSEGVる)

それ以外だとGaucheやMoshみたいにGC_sizeから割り付けられたサイズを求めてごにょごにょするといいったことができないとか、多少の不満があったりはする。

そこでとりあえずなんとかならないだろうかと思い計画＋どうしようこれ？的な問題点を思いつくままにずらずらと。

計画(妄想)的な何か

• 世代別GCにしたい
• 特に理由はないけど、大域定義とかはGCされる率は極めて低いので効果的な気がする
• Scheme48の最新版は世代別GCを実装してるし
• パラメータでGCの挙動をチューニングできるようにしたい
• メモリ割付を安価にしたい
• Ypsilonはメモリの割付がおそらくすごく高速(ctak見て思ったこと)
• BoehmGCはベンチ取ったことないから知らないけど・・・

問題的な何か

• Conservative GCかPrecise GCか
• 世代別ならPreciseじゃないとまずいのか？
• 現状のコードを書き直さないようにしたい
• Conservativeな世代別GC？(可能なの？)
• マルチスレッド環境をどうするか
• ヒープの場所をどうするか
• スレッド毎に持つ
• 子スレッドが死んだ時にどうする？
• ヒープはメインスレッドのみが持つ
• 割付ごとにロックする
• 遅くね？
• スタックの底をどうするか
• あんまりスレッドモデル依存にしたくない
• かといってアーキテキチャ依存もなぁ(espとかrspとか？)

たとえばYpsilonは自前GC(コピーもしくはコンパクションはしなかったはずだからマーク&スイープかな)だが、ヒープはVM毎に持っていて子は親を参照できるけど書き換えられないとかあったはず。http://d.hatena.ne.jp/fujita-y/20081121/1227252054

RacketはPrecise GCなんだけど、↓なので参考にならない・・・

RacketのPrecise GCをうまいこと移植できないかなぁと眺めていたが、なんでBoehmGCが梱包されているのかの理由とまず不可能だということだけが分かった。Boehm版でソースコードの変換してからPrecise版作ってるんだ。
— Keiさん (@tk_riple) 2013年2月27日

Scheme48の実装を理解しつつ分散GC的な何かを理解するという地道な方法しかないだろうか。できれば、サクッと作って「GCは自前じゃないとね」とか軽口を叩いてみたいのだが・・・

誰かこの本を献本してくだしぁ(ぉぃ

リモートREPLとTLS

別に今のところ使う必要がないのだけど、あると便利かなと思ってリモートREPLを作ってみた。最初はYpsilonのtrunkにあったような簡単なのにしてたんだけど、そうするとreadがエラー投げまくりだったので、もう少しまともなプロトコルを使うようにした。以下のような感じで使える。

;; server side
(import (sagittarius remote-repl))
(define auth (make-username&password-authenticate "test" "test"))
(define server (make-remote-repl "5000" :authenticate auth))
(server)

;; client side
(import (sagittarius remote-repl))
(connect-remote-repl "localhost" "5000")

リモートでいろいろやれるようになるとそのうち便利なことがあるだろうけど、当然問題もでてくる。認証とセキュリティの問題がまずあがるだろう。認証はコードを見ればなんとなく分かると思うけど、ユーザ名とパスワードの認証が実装してある。:authenticateキーワードを省略すると認証なしになる。

さて、セキュリティの問題だが、通信を覗かれるとこのままでは丸見えである。そこで今まで割りと放置気味だったTLSのサーバーソケットを急いで実装した。使い方は以下のようになる。

(import (rnrs) (rfc tls) (rfx x.509))
(define certificate (call-with-input-file make-x509-certificate :transcoder #f))
(define server-socket (make-server-tls-socket "5000" (list certificate))
;; (rfc tls) exports server-accept method so that
;; user can use it for both usual socket and TLS socket.
(let ((socket (server-accept server-socket)))
  ;; so is call-with-socket
  (call-with-socket socket
    (lambda (socket)
      ;; do whatever
     )))

クライアント側がDHEなプロトコルを実装しているなら秘密鍵は要らない。DHE以外のCipher specも使いたいなら秘密鍵を:private-keyで渡してやる必要がある。

TLSの実装はかなりと汚いのでソースを見たい人は覚悟してほしい。そのうちリファクタリングとかまじめにステートを追うようにする予定(今はクライアント、もしくはサーバーが正しい順序でパケットを送ると仮定している)。

この辺まで作ってといざリモートREPLをTLSでと思ったときに証明書がないことに気づいた。(手元にあるときはそれを適当に使っていた)。なので(rfc x.509)ライブラリに簡単なX509証明書生成手続きを足そうかと考え中。鍵対生成は既にあるので。

メモリ使用量

Sagittariusはかなりのメモリ喰いである。割と富豪的にメモリを使用するように書いてあるのでしょうがないのだが、テストを走らせるとメモリ不足で落ちることがしばしばある。実際の用途でこんなにメモリを大量に使うプログラムをまだ書いたことがないので、問題になるのかどうかも分からないのだが、精神衛生上よろしくないということで多少何とかしようと重い腰を上げたところである。

とりあえず分かっているところから潰していくべきだろうと思い、ライブラリのルックアップ用に確保してある部分を削ってみることにした。現状ではSagittariusはインポート時に全てのリネーム、プリフィックス等を解決して、それらをライブラリのバッファに確保している。その方が楽だったのと、たぶん高速だと思ったからである。っが、このバッファたとえば(rnrs)をインポートすると、リネームしてもしなくても全てのシンボルがalistとして保管されるという極めて燃費の悪い仕様になっている。

そこで、特に何も指定せずにインポートした際はバッファを作らないように変更してみて、どれくらいメモリ使用量が減るかを検証してみた。(まだ全部は動いてない・・・)
以下が(import (rnrs)) だけ書いたスクリプトを流した結果。

$ ./build/sash.exe -s -c test.scm

;; Statistics (*: main thread only):
;;  GC: 5591040bytes heap, 11359562bytes allocated, 8 gc occurred

$ sash -s -c test.scm

;; Statistics (*: main thread only):
;;  GC: 5591040bytes heap, 10980426bytes allocated, 8 gc occurred

$ ./build/sash.exe -s test.scm

;; Statistics (*: main thread only):
;;  GC: 4190208bytes heap, 6942600bytes allocated, 7 gc occurred

$ sash -s test.scm

;; Statistics (*: main thread only):
;;  GC: 5591040bytes heap, 7885440bytes allocated, 6 gc occurred

交互にキャッシュなし、キャッシュありで試している。キャッシュなしの場合はキャッシュを作成する必要があるのとかがあいまってあまり違いはない(むしろ変更後の方が多少悪い)。しかし、キャッシュがある場合を見ると、GC回数は増えているがヒープ、アロケートともに1MB程度減っている。

もちろん、今まで使っていた部分を削ったのだから減るのは当たり前なのだが、効果としてはそこまで大きくないような感じがする。ちなみに、(rnrs)をインポートすると20以上のライブラリがインポートされる。つまり、20以上のライブラリからバッファを削ったところで1MB程度しか抑えられないということだ。テストはおそらく合計で200以上のライブラリを作成することになるので、単純計算では10MB以上は消費量が抑えられる計算になるが、どうしたものだろうか。実行速度にどれくらいの影響があるかも見てからかな。

Sagittarius Scheme 0.4.2リリース

Sagittarius Scheme 0.4.2がリリースされました。今回のリリースはメンテナンスリリースです。また、R6RS準拠度が上がっています。
ダウンロード

修正された不具合

• エクスポートされたシンボルが特定の場合に不可視になる不具合が修正されました。
• マクロ展開器がライブラリのスコープを壊す不具合が修正されました。
• datum->syntaxが未束縛のシンボルに対して動作しない不具合が修正されました。
• syntax-case内で局所マクロを定義するとコンパイル時エラーが発生する不具合が修正されました。
• コンパイルキャッシュがSEGVを起こす不具合が修正されました。
• environment手続きが0個の引数を受け付けない不具合が修正されました。
• integer->bytevector手続きにオプション引数を与えた際に非正確な値が返る場合がある不具合が修正されました。
• プリフィックスをつけてインポートした際に予期しないシンボルに変換される不具合が修正されました。
• make-variable-transformerが可視なシンボルを不可視にする不具合が修正されました。
• exact-integer-sqrtに巨大数を与えると無限ループする不具合が修正されました。
• #!でモードを指定していないライブラリをロードした際に予期せぬコンパイル結果を起こす不具合が修正されました。

改善点

• (expt 2 x)のパターンが最適化されました。
• マクロ展開器が可能な限り先にマクロを展開するようになりました。
• 未束縛な識別子をコンパイラが検出し、R6RSモードなら&undefinedを互換モードなら警告を出すようになりました。警告は-Ewarn以上のオプションをつけて起動した場合に表示されます。
• bytevector-fill!手続きがオプション引数startとendを取るようになりました。

新たに追加された機能

• crc32及びadler32手続きが(rfc zlib)に追加されました。
• split-key、combine-key-components及びcombine-key-components!手続きが(crypto)に追加されました。
• ->odd-parity手続きが(util bytevector)に追加されました。
• (tlv)ライブラリがDGIスタイルのTLVをサポートするようになりました。

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

• バイナリパック、アンパックライブラリ(binary pack)が追加されました。

非互換な変更点

• 実行時の未束縛なシンボルに対するエラーが&assertionから&undefinedに変更されました。

マクロ展開

Sagittariusのマクロ展開のタイミングを他のtoplevelと同じではなく、多少先んじて行うようにしたのだが、その際にふと以下のコードはR6RS的にはOKなのか気になった。

#!r6rs
(library (foo)
    (export d)
    (import (rnrs))

  ;; def ;; <- NG?
  (define-syntax def
    (lambda (x)
      (syntax-case x ()
        (k
         (with-syntax ((d (datum->syntax #'k 'd)))
           #'(define d 'ok))))))
  def ;; OK
  )

#!r6rs
(import (rnrs) (foo))
d

NG?っとマークが打ってある行なのだが。OKのマークの行は正しく動くべきだと思っているのだけど(Ypsilonはエラーになった、ChezはOK、Moshは現在手元にない)、マクロの展開がコンパイルされる前に行われるのであれば、NG?の部分もvalidな気がするんだけど、どうなんだろう？(ちなみに、パターンの部分を普通のマクロ(？)形式にすると当然Ypsilonでも動く。)

正直これがだめでも困ることはないんだけど、現状の実装ではこれをはじくことができない(実装方針は一つ前の投稿に書いてあるのでそっちを見て) 。ものすごく頑張ればいけるような気もするけど、割とどうでもいいエラー処理な気がするのでたぶん放置すると思う。問題になってから考えればイイ系。

マクロ展開のタイミング

R6RSポータブルなコードを書く際に、書く処理系の癖を熟知してなんてことよほど暇じゃないと出来ないだろうということに気付いた。現状で一番問題になっているのはマクロ展開フェーズ周りの処理である。

Sagittariusはマクロ展開フェーズなんてまどろっこしいものを持たないのだが、なんとかしてそれっぽくエミュレートできないかということちょっと知恵を搾り出し中(正直、搾取しすぎて搾りかすしか出ないが・・・)。とりあえず、library内のtoplevelなdefine-syntaxについては強引に先にやってしまうおう的に解決。(一度library内のtoplevelにある式を全部舐めて、define-syntaxだけ先にコンパイルするという割とお粗末な解決方法。なので、マクロ展開後に出てくるdefine-syntaxとかは対応してない。やろうと思えば出来る気もするが・・・)。頑張ってもう少し賢くした。R6RSより多少制限がゆるいけど。

問題になってくるのは局所マクロである。

R6RSでは以下のようなコードが動かないといけない。

(import (rnrs))
(let ()
  (define-syntax define-inline
    (syntax-rules ()
      ((_ (name . args) body ...)
       (define-syntax name
         (syntax-rules ()
           ((_ . args)
            (begin body ...)))))))

  (define (puts args) (display args) (newline))
  (define-inline (print args) (puts args))
  (print "abc"))
;; abcを表示

(let ()
  (define-syntax define-inline
    (syntax-rules ()
      ((_ (name . args) body ...)
       (define-syntax name
         (syntax-rules ()
           ((_ . args)
            (begin body ...)))))))
  (define-inline (print args) (puts args))
  (define (puts args) (display args) (newline))
  (print "abcde"))
;; abcdeを表示

最初のパターンは何とか(そこそこスマートに)解決できたんだけど、次のパターンのうまい方法が思いつかない。

起きていることそしては、define-inlineで展開されたprintはputsが内部defineとして保持される前にコンパイルされる。そうするとprintのマクロ展開器はputsが内部defineだと知らないので展開器は特に環境情報を付加することなくシンボルputsを識別子に変換する。っで、コンパイラは何も持ってない識別子を大域変数と解釈しコンパイルする。

コンパイラが上記のputs識別子から内部defineのputsを参照できればいいのだが、本当に何の情報も持っていない識別子の参照を許すとマクロのhygieneを壊してしまうのでうかつなことはできない。さて、どうしたものか・・・

make-variable-transformerに潜む罠

正確には、潜んでいる(進行形)か、潜んでいた(過去形)の方がいいのだろうか？

コード見て原因を確認していないんだけど、動き的に何が起きているのか分かったのでとりあえず書く。問題になるのは以下のコード。

#!r6rs
(import (rnrs))

(define-syntax pack
  (make-variable-transformer
   (lambda (x)
     (syntax-case x ()
       ((_ fmt vals ...)
        #'(begin vals ...))))))

(define-syntax define-crc
  (lambda (x)
    (syntax-case x ()
      ((k)
       (with-syntax ((crc-finish (datum->syntax #'k 'crc-finish)))
         #'(define (crc-finish r) r))))))

(let ((a 1))
   (define-crc)
   (pack "<C" (crc-finish a)))

上記のコードは0.4.1では実行時に、0.4.2(HEAD)ではコンパイル時にunbound variableエラーがでる。何が問題かと言えば、おそらくvariable transformerは実行時の環境ではなくマクロ捕捉時の環境で入力式をラップしているのが問題のはず。解決策は実行時環境でラップすればいいだけだと思うのだが、何でマクロ捕捉時の環境使っているのか確認しないといけない(推測が正しければ)。

さて、上記のコードは再現できる最小規模のコードなのだが、このバグを発見できたのはコンパイラが未束縛の識別子を検出するようにしたからである。もともとR6RS的にはコンパイル時に検出してエラーにしなければいけないんだけど、面倒だなぁと思ってサボっていた。っで、いろいろいじっているうちに下地が整ったというか、なんか簡単に検出できるようになっていたので、えいやっと実装してみたという感じである。
実装自体は非常に簡単だったのだけど、問題は既存のライブラリからごろごろと警告が出てきたので全て修正する方が大変だったことだろう。総称関数とか微妙に挙動を変えないとどうしようもないなぁとかだったし。

何はともあれこの修正でマクロ周りのバグがコンパイル時に発見できるようになったのでいろいろ便利になったと思う。

define-constant

MessagePackのR6RS Scheme用ライブラリを書いてたときにふと思いついたマクロ。

(import (for (rnrs) run expand)
        (for (rnrs eval) expand))

(define-syntax define-constant
  (lambda (x)
    (define (eval-expr k expr)
      (if (pair? (syntax->datum expr))
          (let ((r (eval (syntax->datum expr) (environment '(rnrs)))))
            (datum->syntax k r))
          expr))
    (syntax-case x ()
      ((k name expr)
       (with-syntax ((value (eval-expr #'k #'expr)))
         #'(define-syntax name
             (lambda (y)
               (syntax-case y ()
                 (var (identifier? #'var) value)))))))))

(define-constant const-1 1)
(define-constant const-2^16 (expt 2 16))

(display const-1) (newline)
(display const-2^16) (newline)

仕組みは簡単で、マクロとして束縛しつつ、define-constantマクロ展開時にexprを実行しておいてしまおうというだけのもの。込み入ったことはできないけど、(expt 2 16)とか見たいな(rnrs)の中だけで済ませられるものに対しては有効ではある。

Sagittariusには構文としてdefine-constantがあって、それで定義されたものはコンパイル時に定数として畳み込まれるんだけど、MoshやYpsilonにはない。しかも、2^16とかいいけど、もっとデカイ数字になったときにわざわざ数値リテラルで嫌だなぁと思い書いてみた。結局使ったの(expt 2 32)までだけど・・・

これと似たようなので、Vicareの中の人がよく使っている、define-inlineってのがある。こういう、コンパイラを当てにしないコードってポータブルなコードを書くときにはよく使われるのだろうか？

適用可能なマクロ

2chのLisp Schemeスレでsyntax-caseを毛嫌いしているカキコを見たので、こんなことが出来るのはsyntax-caseだけなんてのでも書いてみようかと思った、だけ。
実際、覚えるまでは「なんでこんなもの」なんて思ってたけど、実装者泣かせなだけで使用する分にはこの上なく便利だと思うし、毛嫌いされる理由の一つに「サンプルが少ない」というのがある気がするので、その解消になればとも思う。実際、syntax-rulesだって十分複雑じゃね？とも思うが、こいつはR5RSからのサンプルが結構あるから慣れたというのが大きい気がする。(未だに、複雑なパターンマッチは書けないけど...)

とりあえず以下が便利そうに使えるのではないかと思われるコード片。

(import (rnrs))

(define (format** . args) ...)

(define-syntax format*
  (lambda (x)
    (syntax-case x ()
      ...)))

(define-syntax format
  (lambda (x)
    (syntax-case x ()
      ((_ fmt args ...)
       (string? (syntax->datum #'fmt))
       #'(format* #f fmt args ...))
      ((_ port fmt args ...)
       (string? (syntax->datum #'fmt))
       #'(format* port fmt args ...))
      ((_ . rest)
       #'(format** . rest))
      (var (identifier? #'var) #'format**))))

さすがに中身までは実装してないけど、見た目で何をしているのかなんとなくは分かってもらえると思う。formatはエントリポイントで、そこから引数に応じて適切にdispatchするという寸法。format文字列を動的に作るってのは(やらないわけじゃないけど)かなり少数派なのでマクロ展開時文字列だと分かっているのであれば展開してしまおうという寸法。
また、syntax-caseでは最後のパターンのように「残り全て」みたいな書き方ができるので、その際にformat単独で現れているのであれば、下請け手続きを返すみたいなことをすれば以下のようにapplyにも渡すことができる。

(apply format "~a" 'a '())

これは単純に、以下のように展開されるだけ；

(apply format** "~a" 'a '())

identifier?でチェックしているのは、そうしないと妙なものまで使えるようになってしまうから。(まぁ、上記の場合だと、3つ目のパターンではじくはずだけど)

この手法はIndustriaの(weinholt struct pack)ライブラリで使われていて、ちょっと目から鱗だった。

「適用可能なマクロ」なんて書いたけど、実際にapplyで使えるわけではなく、「そう見せかける」だけである。っがこれを使えばCLにあるコンパイラマクロっぽい挙動が可能になるので処理系のコンパイラに依存したくないとか、使ってる処理系の最適化がしょぼいとか、逆にここを展開できれば処理系の更なる最適化が期待できるなんてときにはいいかもしれない。
もちろん、弊害もある。マクロ版の実装と手続き版の実装の2つをメンテしないといけないこと。上記の例なら、format文字列になにか新しいのを追加したいとなった際に、書き方にもよるだろうが、両方をいじる必要がでるかもしれない。

最近読んだ本

 PRAGUE FATALE: A BERNIE GUNTHER THRILLER

８月くらいに買った本を今年の１月に読み終えるというていたらくっぷり。

物語は１９４１年のドイツ、ベルリンでオランダから単身赴任していた男が殺害されていたところから始まる。
話としてはナチス将校のHeindrichが、オランダ人殺人事件を追っていたベルリン警察刑事のGuntherをボディーガードとしてチェコのプラグに呼び、といった感じでつながっていく。個人的には、殺害されたオランダ人の伏線の回収がちょっと強引じゃないかなぁ？とか、途中でたぶんこれ殺したのあの人だなぁ(コナン風)ってなんとなく分かっちゃったりとかしたけど、全体をみれば面白いと思う。Heindrichが僕の中で人のいいおじいさんでイメージされてたのが、最後になってやっぱり典型的なナチス将校になったというのもあるが。どこを読み間違えたんだ？

なぜ読むのに５ヶ月もかかったかといえば、かなり断続的に読んでいたというのもあるんだけど、１９４１年当時のドイツとかチェコとかの情勢が全くイメージできずにいまいち話にのめりこめなかったというのが大きい気がする。(英語を読むのが遅いというのもあるが、それでもまともに読めば１０日から２０日かからないくらいで読める)。そういう意味では当時の情勢が分かっているともっと楽しめたかもしれない。ペーパバックの表紙に'UTTERLY CONVINCING'なんて書いてあったりするのだから、いろいろリアルに書いてあるんだと思う。

How to add Twitter widget to blogger

It took a day to realise how to make it work properly for me. So there might be loads of people who want to add but somehow it didn't work.

This site describes the basic process really well and it's really useful.
How To Add Twitter Updates Widget in Blogger Blogs - HOWTOQUICK.net

The problem I've got was I could see it on your preview but I didn't see it in real one. If you are living in the US or somewhere using .com you don't have this problem. But if you are living somewhere doesn't use it (.nl for example), you have the problem. Blogger redirects viewers' country specific domain automatically.

The workaround is really simple. Just add viewers' domain to 'Domain' text area. For example, if you want to show your tweets people from Japan, then add ${your blog name}.blogger.jp.

I'm not sure if there is a generic solution for this problem and so far I couldn't find it. If you have solved this with clever way, please let me know.

Reading a smart card with Sagittarius

If you are a lisp user (whichever your preference is), you would already know S-expression is the best way to write DSL. I have been writing a library which allows you to read (in future write) a smart card via winscard or PCSC (it's not tested, though). You can download it from here. It's still under development state so be aware the APIs or commands might be changed in future.

The simple use of this library is really simple, you only need to write a Scheme script and run it with load.scm contained in the library. Let me introduce a simple script.

(import (rnrs)
        (pcsc operations control) ;; for apdu-pretty-print
        (pcsc shell commands)
        (pcsc dictionary gp)
        (srfi :39))

(establish-context)
(card-connect)
;; transmit a select command without any parameter
(select)

(define key #xFFFFFFFFFFFFFFFFFFFFFF) ;; your key must be here
(channel :security *security-level-mac* 
         :option #x55
         :enc-key key
         :mac-key key
         :dek-key key)

(parameterize ((*tag-dictionary* *gp-dictionary*))
  (print "applications")
  (apdu-pretty-print (strip-return-code
                      (invoke-command get-status applications))))

(card-disconnect)
(release-context)

Looks really a Scheme code right? The commands are influenced by GPShell, so if you know it, it would be familiar for you. The result would be like this;

$ sash.exe -Lsrc -Lcontrib load.scm -f status.scm
applications
[Tag] E3: GlobalPlatform Registry related data
  [Tag] 4F: AID
    [Data] �0��: A0 00 00 00 30 80 00 00 00 04 A6 00 01
  [Tag] 9F70: Life Cycle State
    [Data] 07 01
  [Tag] C5: Privileges
    [Data] 00 00 00
  [Tag] EA: TS 102 226 specific template
    [Tag] 80
      [Data]
  [Tag] C4: Application's Executable Load File AID
    [Data] A0 00 00 00 30 80 00 00 00 04 A6 00
  [Tag] CC: Associated Security Domain AID
    [Data] A0 00 00 01 51 00 00 00

... so on if you've got any result

The Sagittarius version must be 0.4.2 (current HEAD version) otherwise apdu-pretty-print raises an error. The document is not really done yet. There are 2 ways to refer which command does what, 1 is looking up the code, the other one is starting the REPL and type (help 'command) like this;

$ sash.exe -Lsrc -Lcontrib start.scm
pcsc> (help 'select)
select :key aid

Sends select command.
;; If you evaluate (help), the it will show all defined commands.
pcsc> (help)
help [command]
Show help message.
When [command] option is given, show the help of given command.
Following commands are defined:
    card-connect
    card-disconnect
    card-readers
    card-status
    channel
    close-channel
    establish-context
    exit
    get-status
    help
    load-script
    release-context
    select
    send-apdu
    set-keys!
    trace-off
    trace-on

Note: even though it shows the help string, it is better to look up the code when you really want to understand for now. I will write the document later.

There are a lot of missing features such as DELETE commands or LOAD, INSTALL etc. I will add those eventually.

Again, it's still under development state, so your feedback and contribution are always welcome :-)

evalとdatum->syntax

packとunpackの実装をしていて、実行時にbytevector-**-native-ref/set!系の手続きを生成してごにょごにょしようかなぁと思ってこんなのが有効かちょっと試してみた。別にR6RSな処理系コンパチにする必要はないだけど、なんとなく。以下がちょっとしたテスト用スクリプト：

(import (except (rnrs) string-copy) (rnrs eval)
        (for (only (rnrs) bytevector-u16-native-ref) (meta -1))
        (only (srfi :13) string-index-right))

(define (->native sym)
  (define (finish sym) (datum->syntax #'->native sym))
  (let* ((s (symbol->string sym))
         (i (string-index-right s #\-)))
    (finish
     (string->symbol
      (string-append (substring s 0 i) "-native" 
                     (substring s i (string-length s)))))))

(display (eval `(,(->native 'bytevector-u16-ref) #vu8(1 0) 0)
               (environment)))
(newline)

動作確認はいつもの処理系、Chez、Mosh、NMosh、Racket、Ypsilon。Sagittariusはenvironment手続きにバグがあって、0.4.1までは0引数を受け付けなかった。HEADでは修正済み。後、ChezはSRFIが(恐らく)一切使えないので、実行する際は、string-index-right周りをごっそり削って、datum->syntaxの第二引数にbytevector-u8-native-refを直接渡すようにした。

以下は結果
予定通り動いた処理系：NMosh、Racket、Sagittarius
何かしらエラーな処理系：Chez、Mosh、Ypsilon

正直なところ上記のスクリプトがR6RS的にValidなのかすら自信がないのは確かなのだが、 psyntax的にはアウトみたいである。Ypsilonはなんでだろう？NMoshとRacketはフェーズを明に指定してやる必要がある処理系なのだが、それらではOKだった。関係があるかは謎(多分あるはず)。SagittariusがOKなのは分かっていたことなので省略。

この手ではコンパチにできないっぽいので、まぁやるならどうせその辺りの手続きは(rnrs)にあると割り切ってenvironment手続きに明に指定してやるというものになるだろう。

pack for Sagittarius

I have committed the pack library. The implementation is influenced Industria's (weinholt struct pack) library. The string format, procedure/macro names and idea for optimisation during macro expansion are taken from it. And I have added indefinite length argument format. But don't look at the code ;-)

The basic use is like this;

(import (binary pack))
;; pack makes bytetevector
;; Fixed length
(pack "4C" 1 2 3 4)  ;; => #vu8(1 2 3 4)
;; (pack "4C" 1 2)   ;; => &syntax

;; Indefinite length
(pack "*C" 1 2 3 4)  ;; => #vu8(1 2 3 4)
(pack "*C" 1 2)      ;; => #vu8(1 2)
;; It can only be allowed for the format position.
;; (pack "*C*S" 1 2) ;; => &syntax

;; pack! sets destructively
(let ((bv (make-bytevector 8)))
  (pack! "*C" bv 0 #xFF #xFF #xFF) ;; => #vu8(255 255 255 0 0 0 0 0)
  ;; the third argument is the offset
  (pack! "*S" bv 4 1 2)            ;; => #vu8(255 255 255 0 1 0 2 0)
  ;; #\x is padding, #\! put next data as big endian
  (pack! "6x!S" bv 0 3)            ;; => #vu8(0 0 0 0 0 0 0 3)
)

Both pack and pack! are macro however it can be passed to apply. (Thanks to R6RS).

I still need to make unpack though...

補助構文の挙動

バグの調査を兼ねていろいろな処理系の補助構文を調べている。といってもmosh、nmosh、Ypsilon、Chezの4種類だけだけど。とりあえず、以下のようなファイルを用意する。ライブラリの名前が変なのは気にしない。

;; named prob.scm or so.
(library (prob)
    (export printer this) ;; this line might be modified for testing
    (import (rnrs))
  (define-syntax this (syntax-rules ())) ;; here as well.
  (define-syntax printer
    (syntax-rules (this)
      ;;((_ bit x) (display (list 'this x))) ;; 間違ってた
      ((_ this x) (display (list 'this x)))
      ((_ x)     (display x))))

  (display 'loaded) (newline)
  )

次に、以下のようなスクリプトを用意する。

(import (prefix (rnrs) rnrs.) (prefix (prob) prob:))
(rnrs.define (print . args) (rnrs.for-each rnrs.display args) (rnrs.newline))
;; should this work?
(prob:printer this      123)
(prob:printer prob:this 456)

(rnrs.define-record-type (pare kons pare?)
  (rnrs.fields 
   (rnrs.mutable a kar set-kar!)
   (rnrs.mutable d kdr ser-kdr!)))
;; somehow nmosh doesn't allow me to call this. why?
(print (kons 1 2))

準備完了。とりあえず、この状態なら全ての処理系で動作する。(Ypsilon除く、多分HEADは動作する)。気になっているのは(prob)からexportされているthisは名前が変わっているはずだが全ての処理系で動く。いいのか？

次に、最初の(prob)ライブラリのexport句のthisをコメントアウトする。 やはり全ての処理系で動く。

さらにthisの定義をコメントアウトする。全ての処理系で動く。ということは、補助構文(というか、syntax-caseもしくはsyntax-rulesのリテラル)はその辺関係ないのかなぁ？と結論付けたいところだが、define-record-typeの中の(なんでもいいんだけど)、rnrs.mutableをmutableに変更するとmosh、Chezが怒る。意味不明である。psyntax組みか？nmoshはOKだった。

さて、どの挙動が正しいのだろうか？
指摘が入ってテストスクリプトを修正。上記のコメントは全部無効になりました。つまり、全処理系(除Sagittarius)予定通りに動く。

pack

Sagittarius currently doesn't have pack procedure (or macro). That's simply because I wrote specific procedures to handle binary packing each time. However it's better to have generic one.

Then I need to consider its interface. I was thinking something similar with Industrial's pack however I have re-read this tweet (it's in Japanese):

Sagittarius scheme には pack ないのか。 サイズが一定ならバイトベクタを確保して並べるのも手間っていう程ではないのだが、不定長になると一気に面倒くさくなるんだよなぁ。
— (32) 齊藤敦志さん (@SaitoAtsushi) 1月 22, 2013

Does it handle indefinte size?

I actually have 2 problems to implement: Firstly, I'm not good with pack stuff. Even when I was still using Perl, pack is only for hex to ascii or other way around (you can easily guess what is for :-) ). Secondly, if we support indefinate length, what would be the better solution?

The first thing, I just need to learn so it just takes fine time. The second one, I don't have much use cases so all what I can is guessing. There are, I think, 2 ways to implement indefinate length. One is like Perl way using some keyword inside of the format string (* or +?). The other one is providing a procedure to pre-compute the given data and generate format string. So it must be like this;

;; #\C is u8
(let ((fmt (generate-format-string #\C indefinite-bv)))
  (pack fmt indefinte-bv))
#|
Let's say indefinite-bv has 8 bytes then format string would be "CCCCCCCC".
Or if we use #\L as a bace character then format string would be "LL"
|#

The problem of this is that we can't optimise it in macro. So it always needs to be computed in runtime. I don't think this will be a big problem, though.

Ah, wait, format string can have indefinite marker if I check it macro expansion time. Hmm, which way is better?

デバッグしづらいバグ

(多分)マクロ周りの識別子問題なのだが、非常にデバッグしづらいバグの報告を受けた。とりあえず、考えうる限りもっとも小さいと思われる再現コードは以下

(import (rnrs))
(define-syntax foo
  (lambda (x)
    (syntax-case x ()
      ((_)
       (let ()
         ;; こいつが問題。syntax-rulesでも起きるけど
         ;; syntax-caseの方が通常はデバッグが楽なので
         (define-syntax prob
           (lambda (x)
             (syntax-case x ()
               ((_) #'ok))))
         #t)))))

要するにsyntax-caseのテンプレート部分で局所的マクロを定義すると&compileが投げられるという不具合。

エラーのメッセージは局所変数.varが参照されているけど、その定義がIForm上で見つからないというもの。 .varはマクロ展開器がパターン変数等を参照するために自動でつけられるものなのだが、この場合だとfooとprobの両方が持っている。

何がこの不具合をデバッグしづらくしているかというと、(デバッガがないというのは置いておいて)probがコンパイル時にコンパイルされるのでどんな感じの中間コードになっているかというのが出力できないこと。コンパイラはいくつかのステップを踏んでVMコードを出力するのだが、このパターンはどのステップで不具合が入るのかとか、なんで入るのかというのを全て推測するしかないのが辛い。

なんとなく推測としてある不具合の原因としては、prob側で参照されている.varがfoo側で定義されたものになってるんだろうなぁ、くらいのものである。(恐らく正しいはず)

さて、なんでこんなことが起きるんだ？

なんとなく分かってきた(昨日の続き)

いろいろ動作確認をChezでしているうちになんとなくどうあるべきかが分かってきた。

基本的にはマクロが定義されたライブラリ内にあるシンボルはそこで、展開時のライブラリにあるシンボルはそこでという感じで定義時のコンテキストを使って識別子を変換すればいいような気がする。

問題になるのは、シンボル自体はなんの情報も持たないのでそのシンボルが実際にどこで出現したかを確認する術がないことだろう。Sagittariusではマクロ展開時にsyntax構文の展開が行われるのでどちらの場合も補足している環境的には同じものに見えるのだ。

こうなってくると展開時ではなく、syntax構文のコンパイル時にシンボルから識別子に変換してしまった方がいいような気がする。そうすれば、少なくとも補足時には識別子になっているので、このような混乱が起きることもない。ちょっとこの方法を試してみるか。

マクロがスコープを壊していた

まぁ、マクロ周りは完全とは言いがたいと分かってはいたのだがこうも立て続けに不具合が出てくるとは・・・

Google code上でIssueを発行したのだけど、まぁ前回のマクロの不具合とばっちり関連している、というかそれの延長線上である。

Vicareの中の人が報告してくれたIssue 84と今発行したIssue 85はちょうど真逆の動作をするのだけど、原因する場所及びその原因は全く一緒。どちらもシンボルから識別子へ変換する部分の処理が正しいライブラリを見つけることができていないのが問題になっている。怪しいなぁとは思っていたのだけどこんなにも怪しかったとは思っていなかった。完全にその部分の理解が間違っていたということになる。

どうあるべきなのか？
問題はこれである。今のところ考えがまとまっていないので、どうあるべきかすらわかっていない。一番大元で(たぶん正しく)理解しているのは、基本的に字面上参照できないものは参照できない、ということ。その逆もしかり。84の方は後者になり、85の方は前者になる。ここで、字面上というのは、コードから読み取れる情報上という意味。(蛇足)
この大元だけが分かっていても、いくつかの要因が複雑に絡み合うと全く分からなくなる。だれだよ、こんな複雑な仕組み作ったの！正直な話、あまり複雑に考えなくてもいいはずなのだ。

ふと、後者の問題はVMをいじれば解決できることに気づいた。マクロ展開の問題なんだけど、解決をランタイム(しかもVMレベル)まで遅らせれば解決できる。ただ、これは本質的な解決じゃないので、どこかで破綻する気がしているのと、本質的な解決じゃないのはあまり入れたくない。

あぁ、待てよ、マクロ展開時とマクロ補足時の環境は取れてるんだからVMレベルまで遅らせる必要はなく分かってるよな？となると、問題となるのはIssue 25のパターンを無理やり何とかしようとしているところか。具体的には以下ようなコード：

(library (foo)
  (export bar)
  (import (rnrs))

  (define (problem) (display 'ok) (newline))

  (define-syntax bar
    (lambda (x)
      (define (dummy)
        `(,(datum->syntax #'bar 'problem)))
      (syntax-case x ()
        ((k) (dummy)))))
  )

(import (rnrs) (foo))
(bar)

barがへんてこな風に解決しないと&assertionを投げるのだけど、これ何とかならないかな？ちょっと考えよう。

Sagittarius 0.4.1リリース

Sagittarius Scheme 0.4.1がリリースされました。今回のリリースはメンテナンスリリースです。ダウンロード

修正された不具合

• 同名の内部defineが存在した場合にASSERTで落ちる不具合が修正されました
• sqrt手続きにBignumを渡すとASSERTで落ちる不具合が修正されました
•  bitwise-bit-count及びfxbit-countに0を渡すと不正な値を返す不具合が修正されました

改善点

• ODBCライブラリを探すプロセスがiODBCにも対応するようになりました(Linux)
• SRFI42がR6RSモードでも動くように改善されました

新たに追加された機能

• pointer->bytevector手続きが(sagittarius ffi)に追加されました
• import、library及びdefine-libraryのみがデフォルトで使用可能になる起動オプション-tが追加されました

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

• TLVデータライブラリ(tlv)が追加されました

winscardを使ってみる

仕事柄最近UICC(SIM)を扱うことが多い。まぁ、基本的には中にインストールされているアプリケーションを覗いたり、APDUを実行したりするだけではあるのだが。

こういった作業をするツールとしてGPShellというものがあるのだが、いかんせんドキュメントが少ない上に今一使い勝手が悪い。内製のツールもあるのだがドキュメントが無いためAPDUのショートカットコマンドがよく分からない。

ということで、簡単に作れそうなら作ってしまおうかなぁと思いちょっと実験してみた。まぁ、FFIの実験ということでもあるのだが。とりあえずインストールされているカードリーダの一覧を取得するところから始めてみた。以下がコード。

#!read-macro=sagittarius/regex
(import (rnrs) (sagittarius ffi) (sagittarius control) (sagittarius regex)
        (srfi :13))

(define win-scard-library (open-shared-library "winscard.dll"))
(define-syntax define-c-function
  (lambda (x)
    (define (scheme-name->c-name name suffix)
      (let1 items (string-split (symbol->string name) #/-/)
        (string->symbol
         (string-append
          (string-concatenate (map (^s (string-titlecase s)) items))
          suffix))))
    (syntax-case x ()
      ((_ ret-value name arguments ...)
       (symbol? (syntax->datum #'ret-value))
       #'(define-c-function "" ret-value name arguments ...))
      ((_ suffix ret-value name arguments ...)
       (and (symbol? (syntax->datum #'name))
            (symbol? (syntax->datum #'ret-value))
            (string? (syntax->datum #'suffix)))
       (with-syntax ((c-name (scheme-name->c-name (syntax->datum #'name)
                                                  (syntax->datum #'suffix))))
         #'(define name (c-function win-scard-library ret-value c-name
                                    (arguments ...))))))))

(define-c-typedef void* SCARDCONTEXT)

(define-c-function long s-card-establish-context short void* void* void*)
(define-c-function long s-card-release-context SCARDCONTEXT)

(define-c-function "A" long s-card-list-readers SCARDCONTEXT char* char* void*)
(define-c-function long s-card-free-memory SCARDCONTEXT char*)

(let* ((hSC (empty-pointer))
       (r   (s-card-establish-context 0 null-pointer null-pointer hSC))
       (readers (empty-pointer))
       (cch (integer->pointer -1)))
  (s-card-list-readers hSC "" (address readers) (address cch))
  (for-each print (string-split (utf8->string (pointer->bytevector 
                                               readers 
                                               (pointer->integer cch)))
                                #/\x00/))
  (s-card-free-memory hSC readers)
  (s-card-release-context hSC)
)

pointer->bytevectorは割りと汎用的かなと思い追加(0.4.1から使用可能)。とりあえずこれを実行するとなんとなく登録されているカードリーダが列挙される。ある程度満足のいくものになったら別モジュールとしてGitHubに登録するかもしれない。

マクロ(戦争)は続くよどこまでも

Vicareの中の人からバグ報告があって、まぁマクロ周りだろうということまで判明していた。っで、実際に問題が起きるコードを見てみると、「あぁ、やっぱりこのコードはバグを含んでいたか」というまさにドンピシャの部分のバグであった。実際のコード(Sagittariusのマクロ展開器側)に多分これはおかしくてバグの匂いがするってコメントまで書いてある。学習した自分を見ている感じだ(以前はこんなの残さなかった)。

件のコード片は以下の感じ。

(define expand-syntax
  (lambda (vars template ranks p1env)
    ...
    ;; wrap the given symbol with current usage env frame.
    (define (wrap-symbol sym)
      (define (finish new) (add-to-transformer-env! sym new))
      ;; To handle this case we need to check with p1env
      ;; other wise mac-env is still the same as use-env
      ;; (define-syntax foo
      ;;  (let ()
      ;;    (define bar #'bzz)
      ;;    ...
      ;;    ))
      (let* ((mac-lib (vector-ref p1env 0))
             (use-lib (vector-ref use-env 0))
             (g (find-binding mac-lib sym #f))
             ;; if the symbol is binded locally it must not be
             ;; wrapped with macro environment.
             (lv (p1env-lookup use-env sym LEXICAL)))
        ;; Issue 25.
        ;; if the binding found in macro env, then it must be wrap with
        ;; macro env.
        ;; FIXME: it seems working but I smell something wrong with
        ;;        this solution. The point of the issue was inside
        ;;        of the macro it refers to the macro itself but the
        ;;        expansion did not occure until it really called.
        ;;        that causes library difference even though it's in
        ;;        the macro defined library.
        (if (and (identifier? lv)
                 (not (eq? mac-lib use-lib))
                 g (eq? (gloc-library g) mac-lib))
            (let ((t (make-identifier sym '() mac-lib)))
              (finish (make-identifier t (vector-ref mac-env 1) mac-lib)))
            (let ((t (make-identifier sym '() use-lib)))
              (finish (make-identifier t (vector-ref use-env 1) use-lib))))))
    ...
  ))

まぁ、見事にFIXMEなんて書いてある部分がそれにあたる。問題になったコードは以下で見える。
https://github.com/marcomaggi/r6rs-sofa/blob/master/lib/sofa/compat.sagittarius.sls
同様にFIXMEと書いてある部分が問題になる。多分、問題は2つあって、c-functionが何かしらおかしなことになっているのと、define-c-functionの展開系からはffi.int等が見えなくなる問題である。

後者の問題がコメントに書いてある部分の不具合に当たる(はず)。出力されるエラーを見ると、ffi.intがuserライブラリの識別子となっているが、これは誤りで、正しくは(sofa compat)にならなければならない。上記のコード片はその辺りの変換を行っているのである。

なぜ起きるか？
もちろん書いてあるコードがおかしいので起きるのだが、シンボルから識別子に変換する際のマクロ展開時とマクロ捕捉時の環境の選別がうまく出来ていないことに起因している。上記のコードではどうも厳しすぎるみたいである。

とりあえず、現在の識別子変換の考え方を整理する。
マクロ展開時に生のシンボルが表れた際、識別子へと変換する。その際に使われる環境の選別は以下のように行われる。

• シンボルはマクロ捕捉時環境で束縛されている
• シンボルはマクロ展開時環境で未束縛である
• マクロ捕捉時とマクロ展開時ではライブラリが異なる
• 束縛されているシンボルはマクロが捕捉されたライブラリで束縛されている

上記全てを満たした場合のみマクロ捕捉時環境を使って識別子へと変換される。今回問題になっているのは最後の項目である。ただ、このチェックを外すと全く動かなくなる。

ちょっと難航しそうな感があるので、0.4.2以降で直すことにする。

2013年始動

あけましておめでとうございます(遅

日本にいた3週間はブログ、コードともにほとんど何もしないという快挙(？)を達成したのでそろそろ始動しないと鈍るなぁと思い開始します。

About Sagittarius
直近は今週か、来週末当たりに0.4.1をリリースする予定。前回のEnbug修正とTLVライブラリの追加しかないです。(微妙に起動オプションが足されてたりするけど)
R6RS、R7RSともにかなり準拠度が上がったのと、仕事で使う範囲だと結構カバーされているので開発状況が多少倦怠期的なものに入ったかなぁとも思っているので、(もしあれば)要望などを受付中です。(使ってくれている人いるのかなぁ・・・)
MoshがAndroidで動くなんてのを見てちょっと触発されつつあるので、(現在仕事で使っている)BlackBerryで動くようにするなんてのを目指すかもしれません(超未定)。
なんにしろ、今年は緩やかに進行するような気がしてます。月一でリリースするつもりでは一応いるけど・・・

その他
鋭意転職活動中です、興味があれば連絡ください。勤務地がオランダかイギリスあたりだとフットワーク軽めです。
6月にスペインでELSがあるらしいけど、行こうか迷い中。

今年こそ腹筋を6つに割りたい。
ギターの練習をもう少し頻度を上げる。