Syntax highlighter

2013-03-16

脱BoehmGCへの道 実装編(2)

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

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

とりあえず現状での違いを列挙
【SBCL】
  • 保存するポインタは、スタック及びレジスタのみ
    • 静的領域は持ってない
    • 動的にコードを生成するのだからある意味当たり前ではある
  • 全てのポインタは中身にアクセスすることなくおよそLispオブジェクトかの判別が可能
    • これによって実際にscavenge及びtransportを行う手続きをテーブルで持つことが可能
  • 全てのポインタからおよその割付サイズを割り出すことが可能
【Sagittarius】
  • 保存するポインタは、スタック、レジスタ及び静的領域
    • 結構な勢いでstaticなオブジェクトを持っているので変更したくない
  • Schemeオブジェクトかどうかの判別にはポインタの中身を見る必要がある
    • 単なるコンテナのpairはどうしても一般的なメモリとしてしか判別できない
  •  動的領域から割り付けられたものならばメモリヘッダからサイズの割り出しが可能
    • あいまいなポインタがきた場合に多少困る
    • 一応チェックが走るけど、不安
 今更ながらにオブジェクトをタグにしておけばよかったと多少後悔しているが、まぁ泣くまい。

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

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

2013-03-15

脱BoehmGCへの道 準備編(4)

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

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

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)に証明書をバイトベクタに変換する手続きが追加されました

2013-03-14

脱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

2013-03-06

脱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」なんて本が出たら多分買うと思う。

2013-03-05

脱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ごとの静的領域がルートに入らない気がするのだけど・・・

2013-03-04

脱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の起動をぎりぎりまで遅らせたいとか?)

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

2013-03-03

脱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のコードでもスレッドコンテキスト等を取得する際に多用されている。これがビルド時に生成されるということは、ターゲットの環境によって中身が大きく変わる可能性があるということ(構造体のオフセットまで全部生成されてるし)。

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

2013-03-02

脱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なんだけど、↓なので参考にならない・・・

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

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

2013-02-21

リモート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証明書生成手続きを足そうかと考え中。鍵対生成は既にあるので。

2013-02-16

メモリ使用量

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以上は消費量が抑えられる計算になるが、どうしたものだろうか。実行速度にどれくらいの影響があるかも見てからかな。

2013-02-15

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に変更されました。

2013-02-11

マクロ展開

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を壊してしまうのでうかつなことはできない。さて、どうしたものか・・・

2013-02-08

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的にはコンパイル時に検出してエラーにしなければいけないんだけど、面倒だなぁと思ってサボっていた。っで、いろいろいじっているうちに下地が整ったというか、なんか簡単に検出できるようになっていたので、えいやっと実装してみたという感じである。
実装自体は非常に簡単だったのだけど、問題は既存のライブラリからごろごろと警告が出てきたので全て修正する方が大変だったことだろう。総称関数とか微妙に挙動を変えないとどうしようもないなぁとかだったし。

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

2013-02-06

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ってのがある。こういう、コンパイラを当てにしないコードってポータブルなコードを書くときにはよく使われるのだろうか?

2013-02-05

適用可能なマクロ

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文字列になにか新しいのを追加したいとなった際に、書き方にもよるだろうが、両方をいじる必要がでるかもしれない。

2013-02-02

最近読んだ本


 PRAGUE FATALE: A BERNIE GUNTHER THRILLER

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

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

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

2013-02-01

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.

2013-01-31

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 :-)

2013-01-28

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手続きに明に指定してやるというものになるだろう。

2013-01-25

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...

2013-01-24

補助構文の挙動

バグの調査を兼ねていろいろな処理系の補助構文を調べている。といっても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):


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?

2013-01-21

デバッグしづらいバグ

(多分)マクロ周りの識別子問題なのだが、非常にデバッグしづらいバグの報告を受けた。とりあえず、考えうる限りもっとも小さいと思われる再現コードは以下
(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はマクロ展開器がパターン変数等を参照するために自動でつけられるものなのだが、この場合だとfooprobの両方が持っている。

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

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

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

2013-01-19

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

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

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

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

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

2013-01-18

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

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

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)が追加されました

2013-01-16

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.intuserライブラリの識別子となっているが、これは誤りで、正しくは(sofa compat)にならなければならない。上記のコード片はその辺りの変換を行っているのである。

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

とりあえず、現在の識別子変換の考え方を整理する。
マクロ展開時に生のシンボルが表れた際、識別子へと変換する。その際に使われる環境の選別は以下のように行われる。
  • シンボルはマクロ捕捉時環境で束縛されている
  • シンボルはマクロ展開時環境で未束縛である
  • マクロ捕捉時とマクロ展開時ではライブラリが異なる
  • 束縛されているシンボルはマクロが捕捉されたライブラリで束縛されている
上記全てを満たした場合のみマクロ捕捉時環境を使って識別子へと変換される。今回問題になっているのは最後の項目である。ただ、このチェックを外すと全く動かなくなる。

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

2013-01-12

2013年始動

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

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

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

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

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

2012-12-31

2012年を振り返って

今年はなんだかいろいろ激変した感じがある年ではあるが、プライベートなことを振り返ると気分がへこむのでとりあえずはSagittarius周りのことだけで。

【達成したこと】
  • R6RSマクロ展開器が標準により準拠した
  • R7RS対応がほぼ終わった
  • 月1リリースの継続
あまり目標を立ててないので、自分の中で達成したというのはないなぁ。自分がほしい機能をいっぱい詰め込んだ「俺々処理系」度がえらく進んだ感があるが(リーダの置き換えとか)。


【来年やりたいこと】
  • ドキュメント
  • ライブラリの充実
  • 使い勝手が悪い(と個人的に思っている)部分の改善
ドキュメントは書いてないというのもあるのだが、1個の巨大なファイルになっているのが気になってきたのでその辺も直したい。
ライブラリは仕事で使う分でも足りないなぁと思う部分が出てきたので(主にバイナリいじるようなの)その辺を充実させていきたい。industriaのpackみたいなのがあると汎用的に使えるか?
使い勝手は、僕個人の感想なのだが、使い捨てのスクリプトを書く際にいちいちimportを書くのがさすがに面倒だなぁと思ってきたので、その辺を何とかしたい。
処理系本体に大きな変更を加える気は今のところないのだが、0.5.0か0.6.0あたりでビルド時のオプションで自前のGCを選択できるようにしたいと思っている。ただ、そこまで個人的にやれるかというのはかなり疑問なのであくまで「やりたい」程度ではあるが。

基本的に「必要ドリブン」(泥縄とも言う)開発スタイルなので、来年やりたいことというのは、現状で改善したいことでしかなく、下手をすれば1月中に終わるというものだったりもするのだが。

何はともあれ、来年もよろしくお願いいたします。

2012-12-18

TLVパーサがほしい

最近仕事でAPDUをいじる必要があるのだが(正確には眺めてるだけなんだけど・・・)、中に入ってるデータとかSIMが返すデータとかがTLV形式であることが多い。っで、TLV自体は別に何か特別な仕様というわけでもないのでこのパーサがあってもいいかなぁと思っていたりする。

問題は、現在既にあるASN.1パーサは基本的にはTLVパーサの上にASN.1のオブジェクトを被せるという形になっている点だろう。TLVだけに特化したのを別に作るのは馬鹿らしいのでこれを分離する方向にしたい。ということでちょっと実装方針を考えることにする。

現状のASN.1パーサはDERとBERに特化した形になっているので不定長のバイト列を処理することができるのだが、TLV形式だけならこれは不要になる。っが、これを外すことは当然だができない。また、DER、BERだとタグ部分が1バイトを超えることがあるが、他の形式だとたいてい1バイトである。(この辺ちょっと自信ない。現状の実装が一般的な気もする。)

となると、タグを読む、長さを読む、値を読む手続きとそれらから得られたデータから最終的なオブジェクトを構築する手続きを渡して、TLVパーサを作るような形にするといいだろうか? でも、そこまでやるなら分離する必要ないよな?オブジェクトの構築だけを外出しにすると、今度は不定長データの処理に困るし、どうしようかな。

2012-12-15

Enbug

かなり大きめなバグを0.4.0で埋め込んだみたいである。問題になるのは以下のコード。
(define (foo)
  (define (bar n) (print n))
  (bar 1)
  (let ()
    (define (bar n) (print 'hoge))
    (bar 1)))
何の変哲もないコードだが、0.4.0では「CレベルのASSERTで落ちる」という脅威の振る舞いをしてくれる。

マクロ直しの一環でのEnbugなのだが、正直全く気づかなかった。久しぶりにベンチマークでも取るかとGambitベンチマークを走らせてはじめて発覚。この問題の面白い(いやな)ところは、実行されたインストラクションから見ると問題の箇所はラムダリフティングに見えた点。実はそこではなく、barが2箇所で使われている点にある。

なぜこんなバグを混入することになったかといえば、R6RS及びR7RSではdefine-syntaxが内部defineと同様に書けることに起因する。たとえば以下のコード。
(let ()
  (define even?
    (lambda (x)
      (or (= x 0) (odd? (- x 1)))))
  (define-syntax odd?
    (syntax-rules ()
      ((odd?  x) (not (even? x)))))
  (even? 10))
こんなコードがあった際に、コンパイラはまずマクロのコンパイルをする。その後、内部defineのコンパイルをする。っが、実は一箇所大きめの落とし穴があって、どちらのコンパイルの際でも内部defineの名前を局所変数として登録する。つまり2重登録が発生する。っで、これの解決の方法がまずかった。

2重で登録されているのなら、2つ目に来るものは無視すればいいのだろうと安易に考えたのだが、そのをしたら最初のコードが動かなくなった。ある意味当たり前である。同名がくることは一切考えていなかったのだから。

リリース直後に気づいた不具合の致命的度としては最大級な気がする・・・orz

2012-12-14

Sagittarius 0.4.0リリース

Sagittarius Scheme 0.4.0がリリースされました。ダウンロード
今回のリリースはマイナーバージョンアップリリースです。大きな変更点は以下、
  • R6RS準拠度(マクロ周り)の改善
  • R7RS small (draft 8)の要求仕様への準拠
修正された不具合
  • datum->syntaxが与えられたテンプレート識別子を解決しない不具合が修正されました。
  • 深くネストしたリストを出力するとSEGVを起こしていた不具合が修正されました。
  • import句でのforキーワードが無視されていた不具合が修正されました。
    • ただし、run、expandなどのフェーズ指定句は従来どおり無視されます。
  • let-syntax及びletrec-syntaxがR6RSモードでスコープを作っていた不具合が修正されました。
  • カスタムコーデックがtranscoded-portで使用できない不具合が修正されました。
  • path-map及びpath-for-eachに:all #fを渡した際に処理が終わらない不具合が修正されました。
  • bytevector-u64-set!及びbytevector-s64-set!が値を正しくセットしない不具合が修正されました。
  • port-eof?がカスタムポートに対して使用できない不具合が修正されました。
  • random-integerが与えられたサイズと同じ値を返すことがある不具合が修正されました。
  • (eqv? 0.0+0.0i 0.0-0.0i)が#tを返す不具合が修正されました。
改善点
  • マクロのR6RS準拠度が大幅に改善されました。
  • リーダマクロがファイル単位からポート単位に変更になりました。
  • 4096文字を超える文字列の読み取りが可能になりました。
  • Debian Linuxがサポートされました。
新たに追加されたライブラリ
  • SRFI-25及びSRFI-78が追加されました。
    • ただしSRFI-78はcheck-ecがR6RSモードでは動きません。

2012-12-12

パターン変数

リリース直前にバグに気づいた。もちろんマクロ周り・・・
問題となるのは以下のようなコード。
(define-syntax loop
  (lambda (x)
    (syntax-case x ()
      [(k e ...)
       (with-syntax
           ([?break (datum->syntax #'k 'break)])
         #'(call-with-current-continuation
            (lambda (?break)
              (let f () e ... (f)))))])))
(let ((n 3) (ls '()))
  (loop
   (if (= n 0) (break ls))
   (set! ls (cons 'a ls))
   (set! n (- n 1))))
R6RSテストスイーツでは?breakの部分はbreakになっている。これがすごく長い間誤解を招いていた。何が問題かといえばコードではなく、(もちろん)実装の方で、現状の実装ではマクロ展開後の式をもう一回総舐めするのだが、その際に上記のbreakを正しいものに置き換える処理をしている。ただ、その際にパターン変数の中身ではなく、パターン変数そのものを見て置き換えるので上記のコードだと?breakが対象になる。

もちろん、よく考えればそれはおかしいと気づくのだが、なぜかずっと現状の実装が正しいと思い込んでいた。っで、R6RSへの準拠度を高めようとマクロの書き直しを終えた後に、いろいろなマクロを試していて気づいたと・・・orz

気づいたからには直さないと気が済まないので現在修正中なのだが、ほぼ全てのテストは通るのに、SRFI-86のテスト1個だけが通らない。他のテストは勘所などが分かったのだが、こいつは長巨大マクロライブラリなので全く分からん。まず間違いなく誤参照をしているのだけど、どこがそれを引き起こしているのかが分からない。

リリースを引き伸ばすか、こいつは次のリリースで直すか悩むところである。R7RSのドラフト8対応と称して出してしまおうか・・・(悪魔の囁き

2012-12-10

R7RS 8thドラフト斜め読み

7thドラフトから1ヶ月しか経っていないのにもう8thが出るとは。ちょっと油断していた。

今回のドラフトは7thのtypoと非正確数のeqv?あたりぐらいだろうと思っているので軽く斜め読み。Chibi-Schemeもこれにあわせてか、0.6.1とバグフィックス版を出してきている。

前回からの変更点
  • (eqv? 0.0 -0.0)が処理系が負の0.0を識別するなら#fと明示された
  • read-bytevector!の引数順が変更になり、それに伴ってオプショナル引数が4つに増えた
これくらいしか見つけられなかった。さすがに斜め読みすぎたか。eqv?の変更はメーリングリストでかなり険悪な状態までいっていたりしてどう落ち着くのか不安ではあったが、R6RSとの整合性が保たれていたのでちょっと安心。でも、未だに(eqv? 0.0 -0.0)が#fでなければならないプログラムを見たことないが、atanとかバリバリ使う人だと問題になるんだろうか?

やべ、こんなに変更点がないとは思っていなかった。書くことがないw

とりあえず、宣伝。
0.3.8でドラフト7に対応したんだけど、Chibiのテストが結構こけてたりしてたんだけど、次のリリースでは全て問題なく通る。それにプラスして、Chibiでは(たぶん、まだ)サポートされていないinclude-library-declarationsもサポートされているので、現状ではR7RS Smallをフルサポートしている処理系ということになる。今週末リリースする予定(あくまで予定)。

2012-12-09

Rewrote case-lambda

Sometimes it's good to review what I've done so far. Yes, I've found something not efficient and it can be more efficient. This time it was case-lambda.

The original was SRFI-19 and since R6RS it's a standard macro (or syntax) for Scheme. However neither of implementations is efficient. At least it can be written better in R6RS. The problem of the reference implementation is it creates closures per lambda formals and apply it with given arguments. If the implementation is smart enough, the apply could be inlined however Sagittarius is not so smart (unfortunately).

If the implementation is not smart enough, then programmers need to be smart to let compiler emit efficient codes. So I rewrote it. This is what I think at least better than the references.
;; this is almost only R6RS except reverse!
(define-syntax case-lambda-aux
  (lambda (x)
    (define (construct args formals clause*)
      (define _car #'car)
      (define _cdr #'cdr)
      (define (parse-formals formal args inits)
        (syntax-case formal ()
          (() (reverse! inits))
          ((a . d)
           (with-syntax ((arg `(,_car ,args))
                         (args `(,_cdr ,args)))
             (parse-formals #'d #'args
                            (cons (list #'a #'arg) inits))))
          (v
           (reverse! (cons (list #'v args) inits)))))
      (with-syntax ((((var init) ...) (parse-formals formals args'()))
                    ((clause ...) clause*))
        #'(let ((var init) ...) clause ...)))
    (syntax-case x ()
      ((_ args n)
       #'(assertion-violation #f "unexpected number of arguments" args))
      ((_ args n ((x ...) b ...) more ...)
       (with-syntax ((let-clause (construct #'args #'(x ...) #'(b ...)))
                     (expect-length (length #'(x ...))))
         #'(if (= n expect-length)
               let-clause
               (case-lambda-aux args n more ...))))
      ((_ args n ((x1 x2 ... . r) b ...) more ...)
       (with-syntax ((let-clause (construct #'args #'(x1 x2 ... . r) 
                                            #'(b ...)))
                     (expect-length (length #'(x1 x2 ...))))
         #'(if (>= n expect-length)
               let-clause
               (case-lambda-aux args n more ...))))
      ((_ args n (r b ...) more ...)
       #'(let ((r args)) b ...)))))

(define-syntax case-lambda
  (syntax-rules ()
    ((_ (fmls b1 b2 ...))
     (lambda fmls b1 b2 ...))
    ((_ (fmls b1 b2 ...) ...)
     (lambda args
       (let ((n (length args)))
         (case-lambda-aux args n (fmls b1 b2 ...) ...))))))
The trick is really simple. Just let macro compute the given arguments. Even length is called only once.

With this code, at least on Sagittarius, the compiler emits better code than references (there is no extra closure created).

2012-12-08

最後の砦

マクロの書き換えを始めて1週間(以上か?)、大詰めまで来ている気がする。美しくなかった機能をばっさりと切り捨て、マクロ展開器は(個人的に)かなりシンプルになったと思う。既存のテストが全て通るようになり、いよいよ本丸のindustriaを走らせて見たら、以前と同じエラーで落ちる。これは何かを見落としているなと思い、落ちている原因のdo/unrollマクロを眺めることにした。

正直、中で何をしているのか理解するのに時間がかかるくらいでかく複雑(に僕には見える)マクロだが、本質的な原因は以下のマクロが動かないことにあることが分かった。
(import (rnrs))
(define-syntax expand-it
  (lambda (x)
    (define (gen-return var) (with-syntax ((v var)) #'v))
    (syntax-case x ()
      ((_ (v init) expr ...)
       (with-syntax ((r (gen-return #'v)))
         #'(let ((v init))
             (when (= v r)
               expr ...)))))))

(expand-it (v 1) (display 'ok) (newline)) 
Chezで試したが当然動く。正直、何がいけないのかすでに分かっていて、以前あったパターン変数の問題の展開された識別子版である。
入力として与えられてvが二箇所のsyntaxで展開されているためにそれぞれ別の識別子として出力されるのが問題なのである。

それこそ、マクロ展開器との格闘を始めて結構長いと思うが、このパターンは完全に見落としていた。こんなマクロ書いたことないし、見たこともないからである。パターン変数の問題はいくらか書いたし、見たことがあったので何が原因かも分かっていたのだが、これは思いもよらなかった。なんというか、目の前に大穴が空いているのに全く気づかなかった気分である。

パターン変数の際と同様の方法で解決するとするか。

しかし、この1週間でマクロ展開の実装は所詮環境の参照と識別子のリネームだけなんだと痛感させられた。ただ、それが異様に面倒なだけで・・・

2012-12-05

expanded internal define

It's aboud the macro expander of Sagittarius Scheme. I'm re-writing it to get better conformity with R6RS. Now I've got a (well not only one) problem and found a bug of current version.

Short description of the bug;
;; Doesn't matter what equal? return.

;; Bug 1
(let ()
  (define-record-type (pare kons pare?)
    (fields (mutable x kar set-kar!)
     (immutable y kdr)))
  (define a (kons (vector 1 2 3) '(a b c)))
  (define b (kons (vector 1 2 3) '(a b c)))
  (equal? a b))
kons ;; -> #<closure kons>
;; this should be &assertion of unbound variable

;; Bug 2
(let ((c #t))
  (define-record-type (pare kons pare?)
    (fields (mutable x kar set-kar!)
     (immutable y kdr)))
  (define a (kons (vector 1 2 3) '(a b c)))
  (define b (kons (vector 1 2 3) '(a b c)))
  (equal? a b))
;; -> &assertion
The first one is obviously wrong, it broke the definition of internal define. The second one is releated to comple time environment lookup. The kons is defined by define-record-type and it must be the same identifier as the one in internal define. But it's not. That's because macro expander re-name it to different identifer.

The simplest solution I have tried was to wrap all given expression first then expand macros. It's simple it worked (mostly) but broke constant literals such as quoted lists or vectors. The problem was not only it but also broke some other codes (mostly related with er-macro-transformer used for generating bootstap code and R7RS). So I've decided not to do this (even though I feel like it's the easier way to do it).

The second solution is modifying the environment lookup process. An identifier can hold some environment without any restriction on current branch and if I can find a better way to look up proper variable from compile time environment, it can be resolved. The problem is I don't know how...

Consider the case of Bug 1. The kons and environment have following frames;
;; kons identifier's frame
((0))
;; when 'a' is being compiled
((0 (kons#user . #(lvar ...)) ...) ;; kons#user is an identifier
 (0)) ;; &lt-- the same environment as the kons identifier
So when a is being compiled, compiler can see the same environment at the very top of the frame chain. But how can we assume kons#user and kons in internal define are the same variables? If the root of the frame are the same, would we be able to assume? Or when it's expanded to internal define, should it be stripped to mere symbol?

Hmm..., I need to think ...

2012-12-02

SchemeでReader Macro

この記事はLisp Reader Macro Advent Calendar 2012の記事として書かれました。

3日目はSchemeでリーダマクロを使ってみます。

僕が知る限り、Schemeの仕様にはユーザ定義のリーダマクロはありません。しかし、いくつかの処理系は独自にそれらを定義する方法をもっています。僕が知る限りではRacket、Gambit、Chicken、Sagittarius(拙作)は独自のリードテーブル拡張手続きを持っています。前2つはあるということくらいしか知らないので、ここでは拙作Sagittariusのリーダマクロの簡単な使い方、及びこれが使えると何がうれしいかということを宣伝を兼ねて紹介します。

世界的にはRacketがよく使われている(らしい)のですが、日本でSchemeと言えばGaucheがまず挙げられるのではないでしょうか。しかし、GaucheはR5RS準拠の処理系ということで、R6RSで書かれたライブラリを実行することが不可能です(2012年12月3日現在)。でも、Gaucheの独自拡張されたリーダマクロを使いつつ、R6RSのライブラリも使いたい!そんなこと考えたことありませんか?そこでSagittariusの出番です(宣伝ここまで)。

SRFI-14な文字セットをリード時に読み込むことを考えます(*1)。Gaucheでは以下のように書けます。
#[a-zA-Z] ;; -> 文字セット(#[a-zA-Z]と表示されます)
これはGaucheの独自拡張なので、他のScheme処理系とは互換性がありません。でも便利そうですよね?じゃあ、こう書けるようにしてみましょう!
(library (char-set reader)
    (export :export-reader-macro)
    (import (rnrs) (sagittarius reader)
            (srfi :14))

  (define-dispatch-macro charset-reader #\# #\[
    (lambda (port subc param)
      (let loop ((cs (char-set-copy char-set:empty)))
        (let ((c (get-char port)))
          (if (char=? c #\])
              cs
              (let ((nc (lookahead-char port)))
                (cond ((char=? nc #\-)
                       (get-char port)
                       (let ((c2 (get-char port)))
                         (if (char=? c2 #\])
                             (char-set-adjoin! cs c nc)
                             (loop (ucs-range->char-set!
                                    (char->integer c)
                                    (+ (char->integer c2) 1)
                                    #f
                                    cs)))))
                      (else
                       (loop (char-set-adjoin! cs c))))))))))
)
#!read-macro=char-set/reader
'#[a-zABC] ;; -> #<char-set #\A-#\C #\a-#\z>
#[a-]      ;; -> #<char-set #\--#\- #\a-#\a>
たったこれだけでGauche互換な文字セットリーダが書けます(*2)。
2日目の記事を読まれた方には簡単すぎるかもしれませんが、簡単な解説です。上記のコードは#\##\[の組み合わせをリーダマクロとして使用することを宣言しています。(CLでいうset-dispatch-macroと同義。)定義はリファレンスマニュアルを参照していただくとして、問題の中身です。コードを見ればすぐに分かるレベルの単純なものですが、最初に空の文字セットをコピーして読み取った文字、もしくは文字範囲(#\-でつながっている文字)を文字セットに破壊的に追加していき、#\]を読むまで続けます。(ちなみに、EOFまで読んでしまうとchar=?&assertionを投げます。あまりよくない振る舞いですので、実用する際はeof-object?で検出して適切な例外を投げた方がいいでしょう。)

しかし、最新のリリース(0.3.8)で上記のコードを使うとキャッシュを壊すので以下のように書く必要があります。
(library (char-set-good)
    (export :export-reader-macro)
    (import (rnrs) 
            (sagittarius reader)
            (rename (only (srfi :1) alist-cons) (alist-cons acons))
            (srfi :14))

  (define-dispatch-macro char-set-reader #\# #\[
    (lambda (port subc param)
      (let loop ((ranges '()) (chars '()))
        (let ((c (get-char port)))
          (if (char=? c #\])
              `(char-set-union (string->char-set ,(list->string chars))
                               ,@(map (lambda (range)
                                        `(ucs-range->char-set 
                                          ,(car range) ,(cdr range))) ranges))
              (let ((codepoint (char->integer c))
                    (nc (lookahead-char port)))
                (cond ((char=? nc #\-)
                       (get-char port)
                       (let ((c2 (lookahead-char port)))
                         (cond ((char=? c2 #\])
                                (loop ranges (cons nc chars)))
                               (else
                                (get-char port)
                                (loop (acons codepoint (+ (char->integer c2) 1)
                                             ranges)
                                      chars)))))
                      (else
                       (loop ranges (cons c chars))))))))))
)
#!read-macro=char-set-good
(import (srfi :14))
#[a-zABC]  ;; -> (char-set-union (string->char-set "CBA") (ucs-range->char-set 97 123))
#[a-]      ;; -> #<char-set #\--#\- #\a-#\a>
これは、一部の組込みオブジェクトをキャッシュ機構がうまくキャッシュできないことに起因しています。次期リリースではある程度この問題が解決される予定です(少なくとも文字セットとハッシュテーブルは最新のHEADでは解決されています)。ユーザ定義のオブジェクトに対しては明示的にキャッシュとして書き出し、及び読み込みをするための手続きを定義することが可能です。

リーダマクロは処理系依存な機能な上に、処理系によっては(主にSagittariusですが)制限もあったりと使いどころが難しいものかもしれません。しかし、SRFI-105等のリーダ拡張を必要とするライブラリにScheme側のみで対応できたり、処理系の独自拡張の差異を吸収できたりと便利かつ強力な機能でもあります。

3日目はSchemeでもリーダマクロを使う方法を紹介しました。

*1: Sagittariusでも正規表現の読み込みははC側で実装されているので例として使いにくかったのです。
*2: 実際にはGaucheの文字セット読み取り機能はもっと多機能なのでこれだけだと完全に互換とはいえないですが・・・

R6RSとR7RSのライブラリ比較

この記事はLisp Advent Calendar 2012の3日目の記事として書かれました。

3日目は最近出たR7RSドラフトセミファイナル(とWG1が読んでいる)と、R6RSのライブラリシステムの文法的な違い(意味的なものも多少)を見ていこうと思います。

まずは、R6RSのライブラリのおさらいです。R6RSは制定されてすでに数年(2007年だったっけ?)経っているので、皆さんもうご存知ですよね。なので以下はごく簡単な例;
(library (foo)
   (export bar)
   (import (only (rnrs) define quote))
  (define bar 'bar))
#|
ライブラリ構文の定義
(library <library-name>
   (export <export-spec> ...)
   (import <import-spec> ...)
  <body> ...)
|#
R6RSのライブラリは暗黙もしくは明示的なマクロ展開フェーズを持ちます。これはマクロ内で使われる手続きと、ランタイムで使われる手続きを明示的に分ける必要があったから(らしい)です。(個人的にこのフェーズ分けは考えるのが面倒なので、暗黙的に解決してくれる処理系の方が好きです。好みの問題ですけど。)

次はR7RSのライブラリの例;
(define-library (foo)
  (import (scheme base) (scheme write))
  (begin (define foo 'foo)
         (define (print . args) (for-each display args)(newline)))
  (define (printw . args) (for-each write args)(newline))
  (export foo print)
  (export bar)
  (begin (define bar 'bar))
  (cond-expand
   ((library (srfi 1))
    (import (rename (only (srfi 1) alist-cons) (alist-cons acons))))
   ((library (srfi :1))
    (import (rename (only (srfi :1) alist-cons) (alist-cons acons))))
   (else
    (define (acons a b c) (cons (cons a b) c))))
  (export acons))
#|
ライブラリ構文の定義
(define-library <library-name>
   <library-declaration> ...)
|#
あえて違いを出すように書いてありますが、普通はexportとimport句はまとめると思います。
R7RSではR6RSと違い順番がライブラリ定義の順番及びその個数が規定されていません。なので、上記のコードは既存のR7RS処理系(ChibiとSagittariusしか知らない)で正しく動きます。(規定されていないので処理系依存になるかもしれません。)
R7RSのimport句はR6RSとは異なりforがありません。これはR7RSではマクロの展開フェーズが規定されていないからです。処理系は暗黙的にしかマクロ展開フェーズを持つことができません。(問題になる処理系の方が少ない気はしますが)
一方export句でもrenameのあり方がR6RSとは異なります。R6RSではrename句の中に複数の識別子を定義することができましたが、R7RSでは一つのrenameに対して一つの識別子しか定義することができません。
また、cond-expandはSRFI-0のものとは多少違い、featureとしてlibraryが追加されています。これによってライブラリが存在するかのチェックが可能になり、上記のように無ければ定義、みたいなことが可能(なはず)です。
また、以下の例はR7RSが既存のR5RSで書かれたプログラムをそのまま使用することが可能であるということを強く意識して作られたことを示す例です。
;; bazz.sls (for Sagittarius) or bazz.sld (for Chibi)
(define-library (bazz)
  (export bla)
  (import (scheme base))
  (include "bazz.scm"))

;;--
;; bazz.scm
(define bla 'bla)
ライブラリ内で使用されるinclude、include-ci(case insensitive)はライブラリ上にそのままファイルの内容が展開されるイメージです。処理系によっては以下のように解釈するかもしれませんが、まぁ無視できる程度の差異でしょう(Sagittariusはこのように解釈する)。
(define-library (bazz)
  (export bla)
  (import (scheme base))
  (begin (define bla 'bla)))
事実、Chibi-Schemeのほぼ全てのライブラリはincludeを用いて記述されています。また、今回のドラフトから追加されたinclude-library-delarationsは以下のように使えば処理系ごとの拡張子の違いを簡単に吸収することが可能です。(ただし、現状ではSagittariusのみがこの構文をサポートしている状態です)。
;; boo.sls or boo.sld
(define-library (boo)
   ;; もちろん、この上下にいろいろ書いてもOK
   (include-library-declarations "boo.decl"))

;;--
;; boo.decl
(export bah)
(import (scheme base))
(include "boo.scm")

;;--
;; boo.scm
(define bah 'bah)
include-library-declarationsはinclude、include-ciとほぼ同様の動作をしますが、include先のファイル(この場合はboo.decl)は<library-declarations>で構成されている必要があります。R7RSの議論の中ではこの構文は巨大なexport句を外出しにし共有化するために作られてのですが(*1)、このような使い方もできるのではと思っています。

R7RSはまだドラフトで上記の構文を試せる処理系はまだ少ないですが(2012年12月現在)、多くの処理系製作者がすでに追従するということを表明しています(*2)。個人的にはR7RSの構文の方がR6RSに比べて柔軟かつ処理系の差異も吸収しやすいのではと考えています。

3日目はR6RSとR7RSのライブラリ構文の比較を行いました。

*1: たとえば(srfi :1)と(srfi :1 lists)は同一のexport句を持ちますが、R6RSのライブラリではどちらのライブラリも同一のexport句を記述する必要があります。Sagittariusは:allキーワードがあるので、多少手が抜けたりしますが・・・
*2: Kawaはすでに可能な限り追従するとR7RSのメーリングリスト上で製作者が言っています。Larceny、Gauche、及びChickenも最初のドラフトの段階では追従するということを回答していました。参照

2012-12-01

Andre van Tonderの展開器を読む

やっぱりマクロ周りの問題は割りと大きくのしかかってくる感じなので、まじめに戦略を練るために既存の展開器を理解しようかなぁと思い読み始める。

とりあえず以下が理解したこと;
  • マクロ展開時にユニークなマークを作成
    • colorとなっているもの
    • これによってbound-identifier=?を実装している
  • 展開フェーズはdefine-syntaxが現れると+1される
    • Sagittariusは暗黙に解決する方向をとるので、これは要らない
  • syntax-caseのマッチはランタイムに生成される
    • パフォーマンス的にはうれしくないよなぁ
    • ただ、その分いろいろな情報解析で手を抜けそう
  • 式が渡された段階で全てのシンボルが識別子に変換されている
    • 重要だけど、リテラルなリストとかどうしようかな・・・
  • 環境は全ての束縛を保持する
    • 局所変数から大域変数、はたまた構文まで全部
    • free-identifier=?の実装には必要
      • 僕の考え方は間違ってなかったのかと納得
  • パターン変数を識別するものがある
っで、現状のSagittariusの実装とは大きく異なる部分;
  • パターンマッチは組み込みである
    • コンパイルが2度走る必要がないの多少高速なはず
  • テンプレート展開部分も組み込みである
    •  Andre van Tonderの方はこいつもマクロごとに生成される
  • ラップする式は束縛されている変数のみかつ、コンパイラが行う
    • しかも、複数回走る
    • 全体を1回だけにした方がいいが、リテラルリストをどうするか
ある意味当たり前なんだけど、マクロ展開の部分だけに目を向けるなら、syntax-caseとsyntaxだけが解決されている。つまり、それ以外のR6RSが提供する低レベルマクロ用何かしらは、すべてこの2つの組み合わせのみで解決できる。
ということは、この2つが完璧に動作さえすれば、他の動作は保障されているわけで、現状いろいろごにょごにょやっている部分がすっきりする可能性が高い。

Andre van Tonderの展開器ではポータビリティのために生成されるGUIDはシンボルなのだが、gensymがある処理系ならばこれはgensymに単純に置き換えることができる(検証もした)。ついでに、GUIDは一時変数とか、ユニークなシンボルの生成以外には使われていない。
ライブラリの関係(だけじゃないかも)で、グローバルもしくはローカルに束縛されたシンボルの実態はGUIDに変換されている。ただ、ルックアップ自体は識別子で行うので、Sagittariusではやる必要はないと思う。

全体を1回だけラップすることで起きえる問題を考えてみる;
  • リテラルリストが壊れる
    • 完全にリテラルだと分かっているならラップしないということも可能
    • quasiquoteが困りそうだがどうする?
      • ラップ時にquasiquoteだけ特別視?
    • ベクタもリテラルであるよな?
  • libraryやdefine-library構文に手を入れる必要がある。
    • exportやimportがシンボルを期待しているが、識別子になってしまう
      • まぁ、大きな問題ではない
リテラルリストだけなんとかすれば大きく問題はないと思う。ずっと使わずあるだけだったpass0手続きがついに使われるときが来たか。
気になるのは、ただでさえメモリ喰いなのにさらにメモリを喰うようになることか。読んだS式全部トラバースして、丸コピーしないといけなくなるから。まぁ、現状も似たようなことやってるし、考えるだけ無駄か。

2012-11-30

続 マクロ戦争再び

すこぶる体調が悪いが頭はそれなりに稼動するので案をベッドの上で考えていたりした。

現状の問題としては、同一の環境でリネームされた識別子(本来はシンボル)が同名にならないというものだ。これは本質的に2つの問題を含んでいることを示唆している。
  1. 識別子を用いてシンボルの同一性を取ろうとしていること
    1. α変換が不完全である
  2. 識別子が本来の意味を越えて使用されているため、複雑なものが複雑怪奇にグレードアップしている
    1. 識別子=構文オブジェクト=パターン変数=リネームされたシンボルになっている
では、どうすればいいかということを考えていた。とりあえず1と2の問題の一部を解決するアイデアが以下である。
  • 使用されている環境に応じて適切にシンボルのリネームを行う
王道である。実際これくらいしか思いつかなかったともいう。問題になるのは、どの環境をもって同一の環境というかという点である。Sagittariusではマクロ展開時に3つの環境を参照することができる。
  1. コンパイル時の環境
  2. マクロ束縛時の環境
  3. マクロ展開時の環境
自分の中でもなんでこんなに環境が必要なのか実は整理できていないのが問題なのだが、それぞれ全て違う。細かいこと(細かくないが)はとりあえず置いておいて、とりあえず以下のプログラムを考える;
(import (rnrs))
(let ((bv #t)) ;; ※1
  (define-syntax foo
    (lambda (x)
      (syntax-case x ()
        ((_)
         (with-syntax ((set (let ((type #'bytevector-u8-set!))
                              #`(#,type bv 0 1))))
           #'(let ((bv (make-bytevector 1)))
               set
               bv))))))
  
  (let ((bv #f))
    (display (foo))))
まぁ、前回とほぼ同じコードである。違いは、マクロ束縛時環境が何かを捉えている点である。ここで問題になるのは、全てのbvが同一のシンボルになる必要がある点である。そうすると、コンパイル時環境を使うのはまずいことになる。letで束縛されたtypeが入ってくるからだ。そうすると、二つ目のbvと環境が異なるため、生成されるシンボルが異なる。
この状態では、マクロ束縛時と展開時の環境が多少違う。このパターンを考えるとマクロ束縛時の環境を使ってリネームするのが正しい気がする。ただし、リネームされたシンボルは※1と同名になる必要がある。これは、with-syntax>で生成されたものがそれを参照している必要があるからだ。また、最終的に返される構文で束縛されるbvも同様である。それによってシャドウイングされて結果正しい値を返す。
もし、このスクリプトでマクロ展開時の環境を使うと、(まぁ、結果的には問題ないのだが)、二つ目のbvにリネームされることになるのでうれしくない。

なんとなくどうすればいいのか見えてきた。結果として以下のように修正すれば、いいのではないだろうか?
  1. コンパイラ側のリネームを(uninterned)シンボルを使うように修正
  2. マクロ展開器ではマクロ束縛時の環境を元にシンボルを(uninterned)シンボルにリネーム
方針は固まったので、後は実装か・・・

2012-11-27

マクロ戦争再び

正直何度目だ、戦争が勃発するのは・・・

ほぼピュアR6RSで書かれたライブラリでindustriaというものがある。驚嘆するほどでかい上に、Sagittariusのお株の一つである暗号処理がサポートされている。(別にライブラリの宣伝をしたいわけではない)

このライブラリ内で使われているマクロが動かないというバグレポートを受けた。最初はmake-variable-transformerが参照している環境が違うだけかと思ったのだが、実は裏にもう一つ潜んでいた。こっちは非常に厄介な、しかもずっと悩んでいる問題の一つ。端的に問題を顕在化させるコードが以下;
(import (rnrs))
(define-syntax foo
  (lambda (x)
    (syntax-case x ()
      ((_)
       (with-syntax ((set #'(bytevector-u8-ref bv 0)))
  #'(let ((bv (make-bytevector 1)))
      set
      bv))))))

(foo)
with-syntaxで作られた新しいパターン変数(ということにしている)内にあるbvと最終的に返される構文内で使われているbvが同じでなければならないという問題。

これはSagittariusではうまく動かない。なぜかという原因も分かっていて、最初のbvと2回目のbvは使用される環境(正確には違うけど便宜上こう呼ぶ) が違うから。これと類似の問題に、R6RSテストスイーツのbreakがあるが、あれはwith-syntax上ですでにパターン変数として作られているので、なんとか識別する。

これの本質的な問題は、syntax構文が同一環境で呼ばれても同一の識別子を返さないことにある。本来ならば、最初と2回目は同一の環境なので、どちらのbvも同じ名前にリネームされるから最終的な形としては問題なく動くようになる、はずなのだけど、そうは問屋がおろさないので困っている。

解決策としては2つあると思っていて、一つは王道、識別子にリネームされた際の環境、フェーズその他もろもろの情報を付加してやり、identifier=?はそれらをまじめに比較するようにする。二つ目は邪道(というか、スパゲッティ生成法)、マクロ作成時に作られる環境にフィールドを一つ追加して、何が何にリネームされたかということ保持しておき、それを環境が拡張されるても共有する。

正直、どちらの方法もかなり大掛かりな変更が必要になる。やりたくないが、バグとして報告された以上なんとかしないわけにもいくまい・・・

ってか、これってR6RSで動くって保障されてるのかな?されてるよなぁ・・・

2012-11-22

キャッシュを考える

ふとQiitaのLisp Reader Macro Advent Calendar 2012のネタを考えているときに思ったこと。

Sagittariusはパフォーマンス(ほぼレスポンスだが)向上のためにライブラリ単位でFASLのようなものを持っている (正確にはライブラリファイル単位だが)。普通にスクリプトを書く分には気にする必要はないのだが、リーダーマクロが絡んでくると多少考える必要が出てくる。たとえば、組み込みの正規表現はリーダーマクロを用いて読み取った場合リテラルオブジェクトとして扱われる。これはその方がパフォーマンスがいいからに他ならない。

ここで、ユーザー定義のオブジェクトを考える(Qiitaに書く予定のネタは文字セットなんだけど)。たとえばCLOSを用いてオブジェクトを作成するが、リーダーマクロでリテラルとしても返せるようにしたとする。そうすると何が起きるか?普通にスクリプトとして使用されるだけなら特に問題はないのだが、ライブラリ内で使用すると話が違ってくる。

現状ではキャッシュ機構はユーザー定義のオブジェクトをキャッシュする方法を暗に知る方法がない。SRFI-4ではユーザー定義のリテラルを返すようにしているが、これは明示的にどうそのオブジェクトをキャッシュするかということをScheme側で制御しているからできるのである。しかし、いちいちそれを書くのが面倒な場合の方が大体多い。

なんとかならないかなぁと思っていたのだが、なんとなく「完全Scheme」で定義されたオブジェクトなら一般的な方法でいけるような気がしてきている。それは、CLOSのオブジェクトは基本スロットの中身さえ保存してしまえば何とでもなるからだ。スロット名と値を保存して、復元時は単にslot-set!でセットしてやる。

ここで、問題になるのは、「キャッシュできない組み込みオブジェクト」だろう。現状でsubrをうまいことキャッシュする方法を思いついていない。また、自由変数を含むクロージャーがスロットに入っていた場合とかも困る。まぁ、あくまでベストエフォートだと言えばいいので、こういったキャッシュ不可能なものが来たら弾いてしまえばいいといえばそうなんだけど。

不安材料の方が多い気もするし、どうしたものか・・・?

2012-11-18

Hoge VeluweとKröller Möller美術館

Meetupのイベントで行ってきた。Utrecht以東に行くのは実はこれがはじめて。Adventureはたどり着く前から始まっているのである。(MeetupのグループがAdventureを冠している)

ま、何はともあれ写真。僕の気力が続く限り撮った。加工するのが面倒だったからファイルが巨大だw
Utrecht Central。いつきても代わり映えはしない。そしてトラブルが多いというイメージの駅。(実際帰りはLeidenへの直通がなかった・・・orz)

ハイキング開始。きれいな丘だろ?これでもオランダなんだぜ。

もう少し傾斜があれば軽く山登りな気分。

オランダとは思えない風景の一つ。

森の中を進む。

森が終わると今度はサバンナw

あたり一面まっ平ら。ま、やっぱりオランダだよね。

微妙にこの風景はSaskatchewanとかManitobaを思い出す。何もない平らな風景。

3時間に及ぶハイキングの後、小さなレストランに到着。あの小屋みたいなのがレストラン。

ここからはKröller Möller美術館の中。これは正確にはその庭。

途中で見つけた何かしら。これの裏に、三段腹をモチーフにした何かがあったけど、写真取り忘れたw

木漏れ日が差してる絵って好きなんだよね。 ま、iPhoneのカメラではこの程度が限界だけど。

芸術家の考えることは一般人には理解できないけど、これはひときわ、なんぞこれw?だった。

改装中の部屋にあった絵。

本物(だと思う)のゴッホの絵。この美術館はゴッホのコレクションがオランダで2番目に多いらしい。一番はアムステルダムのゴッホ美術館だと思う。

ありがたや~w

自分が写りまくりw合わせ鏡があって、どれくらい光が届くんだろうと気になって撮った。

夜の帳が下りようとしている中、正門まで2kmのウォーキング。10分後にはえらい暗くなっていた。

帰り道はUtrechtからLeidenへの電車がなかったので、Den Haag経由で帰る必要があったがまぁ無事に帰宅。3時間+30分のウォーキングで足が痛いw
正直、オランダにこんなところがあるんだ、と感動した一日だった。そして、山っぽいところを歩いているときに、あぁ、やっぱり自分は山の方が好きなんだなぁと実感した。

2012-11-16

writeがスタックを食いつぶす

Gaucheのソースツリーを眺めていて、writeがCのスタックを食いつぶすのを直したというようなコミットを見つけた。同じことが起きるよなぁと思いつつ、とりあえずテスト。以下は使用したコード(R7RS形式なのは最後にチェックしたのがChibiだから。当然Sagittariusでも動く)
(import (scheme base) (scheme write))
(define (call-with-string-output-port proc)
  (call-with-port (open-output-string)
    (lambda (p) 
      (proc p)
      (get-output-string p))))

(display
 (let loop ((cnt 0) (ls '()))
   (if (< cnt 1000000)
       (loop (+ cnt 1) (list ls))
       (string-length (call-with-string-output-port
                       (lambda (p) (display ls p))))))) 
(newline)
とりあえず、どのくらいの処理系がこれをSEGVを起こさず処理するのかチェック。以下は結果。
200002を正しく返した処理系
Chez Scheme, Racket (plt-r6rs), Larceny (R6RS)
SEGVもしくは処理が終わらなかった処理系
Sagittarius, Chibi, Mosh, Ypsilon
動く処理系で、ソースを確認できるのはRacketとLarcenyだけなので、とりあえず確認してみた。

Larcenyはなぜ動いているのか正直分からなかった。コードがSchemeで書かれているので、ひょっとしたら最適化でうまいこと動いているのか、Cで書いていない分スタックの消費が少なくなっているのかは不明。

Racketはスタックの底にたどり着いたらlongjmpするという荒業だった。たしかに、ありだよね。

Gaucheは0.9.4は再帰呼び出しをせず、gotoで済ますという方法。ただ、そのためにメモリを結構使用するんじゃないかなぁと思ったり。

Sagittariusは(ユニットテストの)メモリの使用量が半端ないので、可能な限り省エネで行きたいところ。なので、やるならRacket方式か、気合でなにか良い案思いつく必要がある。longjmpのオーバーヘッドってどれくらいなんだろう?

Sagittarius 0.3.8 リリース

Sagittarius Scheme 0.3.8がリリースされました。今回のリリースからR7RSドラフト7がサポートされます。ダウンロード

修正された不具合
  • ローカルマクロをマクロ内で定義した際にSEGVが起きる不具合が修正されました。
  • (dbd odbc)を用いて存在しないレコードを更新しようとした際にエラーが投げられる不具合が修正されました。
  • get-bytevector-allがソケットポートからデータを全て読み込まない不具合が修正されました。
  • binary-port?及びtextual-port?がカスタムポートに対して適切に動作しない不具合が修正されました。
  • #n=をリーダが適切に読み込まない不具合が修正されました。
  • remainderの第一引数に浮動小数点数を与えるとSEGVが起きる不具合が修正されました。
  • (sqrt -1)が非正確数を返す不具合が修正されました。
  • (zero? 0.0+0.0i)が#fを返す不具合が修正されました。
  • -1iのような形式の複素数が正しくない符号を返す不具合が修正されました。
  • ライブラリのバージョンに0が使えない不具合が修正されました。
  • ライブラリバージョンリファレンスの形式がエラーを投げる不具合が修正されました。
  • appendが引数1つで呼び出された場合に()を返す不具合が修正されました。
  • 全ての未束縛exportが束縛された値を持つよう修正されました。
改善点
  • (cond ((assq a b) => cdr))の形式をコンパイラが可能であれば組込みインストラクションを使うように改善されました。
  • ビルドプロセスが改善されました。
    • 多くの依存ライブラリがFIND_PACKAGEを用いて検索されるようになりました。
    • libffiが見つからなかった際にLinuxでもバンドルされたlibffiが使用可能になりました。(Ubuntu 32 bitでのみテストされています)
  • ODBCライブラリのblob型ポートが作成時に全てのデータを読み取らないように変更されました。
新たに追加された機能
  • リーダーマクロの有効範囲がファイル単位からポート単位に変更になりました。
  • R7RSドラフト7がサポートされました。
  • glob手続きが追加されました。
  • sashの-Lオプションが-L'*'形式をサポートするようになりました。これはglobで見つかった全てのディレクトリをロードパスに追加します。
新たに追加されたライブラリ
  • SRFI-105が追加されました。#!read-macro=curly-infixで有効になります。#!curly-infixではないことに注意してください。
非互換な変更
  • R7RSのライブラリが大幅に変更になりました。これらはドラフト5からの変更で、後方互換性はありません。

2012-11-15

ブレインストーミング

考えをまとめるのに紙に書くのが面倒なのと、記録を残しておいた方がいい類のものなのでメモ。

以下のコードを考える。
(read (open-string-input-port "#!fold-case ABC"))
(read (open-string-input-port "ABC")) ;; こいつは何を返すか
恐らく書いている方の期待する結果はABCというシンボルだろう。だが、これは予想に反してabcを返す。(Sagittariusでは#!fold-caseは全部小文字にして返す) 。こんなの書くやついないよ!と思っていたのだが、意外なことに自分がこれではまったのでやはり問題かなと思うようになってきた。

何が問題か?

現状ではSagittariusはファイル単位でリードテーブルの切り替えを行う。っが、上記のようなものだと同一ファイル上でreadが走るのでファイル単位で行うと残念な結果になる。つまり、ファイルではなくポート単位で行う必要があるということになる。

どう直すか?

ポート単位にするというのは結構大掛かりな変更になる。現状の実装では、VMが現在のリードテーブルを保持して、loadが走る際にポートに保存、loadが終わったら保存したテーブルをVMに戻すという割と回りくどいことをしている。
これをポート単位にするにはどうすればいいのか?とりあえず簡単に思いつくのはVMが現在loadしているポートを保存するというもの。loadは必ずファイル単位で行われるので、現在のloadingポートが分かれば何とかなりそうである。となると問題になってくるのは、どの段階でポートにリードテーブルを持たせるかというもの。可能性としてあるのは、
  1. ポート作成時。(全てのポートはリードテーブルを持つ)
  2. リードテーブルを変更するようなものを検出したとき。(オンデマンド)
上記のようなコードだと、2つ目のポートに持たせるのは無駄以外のなんでもないような気がするので、やるならオンデマンドだろうか。

方針は決まったので実装するか。

2012-11-14

この発想はなかった

Chibi-SchemeのIssue 149にあった面白い発想のdefineをsyntax-caseで実装してみた。
(import (rnrs))
#|
;; ※1
;; 投稿した2分後にsyntax-case一回だけでいけることに気づいた。
;; なので、コード直下のぼやきはこのコードに対してのもの。
(define-syntax define-function
  (lambda (x)
    (define (compose expr)
      (let loop ((expr expr))
        (syntax-case expr ()
          (((name . formals) body ...)
           (identifier? #'name)
           #'(define name (lambda formals body ...)))
          (((name&formals . rest) body ...)
           (not (identifier? #'name&formals))
           (loop #'(name&formals (lambda rest body ...)))))))
    (syntax-case x ()
      ((_ exprs ...)
       (compose #'(exprs ...))))))
|#
;; すっきしたバージョン。これなら処理系関係ない。
(define-syntax define-function
  (lambda (x)
    (syntax-case x ()
      ((k (name . formals) body ...)
       (identifier? #'name)
       #'(define name (lambda formals body ...)))
      ((k (name&formals . rest) body ...)
       ;;(not (identifier? #'name&formals)) ;; この行要らない
       #'(define-function name&formals (lambda rest body ...))))))

(define-function ((f x) y) (+ x y))

(print ((f 1) 2))
多少以上に余計な手間をかけているのだが、マクロ周りがR6RS準拠な処理系と違ってSagittariusでは識別子のリネームに制限がある。それは、同一のsyntax構文内でリネームを行わないと識別子が同じにならず、unbound variableエラーを投げるというもの。なので、上記は本来ならquasisyntaxを使ってもう少し分かりやすく書けるのだが(まぁ、どちらが分かりやすいかは人によるが)、Sagittariusで動かすために式を全部一緒に処理してやる必要がある。(※1のコード)

この制限はずっと気づいているし、問題だと思っているのだが、いかんせんスマートな解決方法が思い浮かばないのと、慣れてしまえば別に気にならないので放置してある。0.4.0辺りまでに直したいという思いはあるが、あるだけともいえる・・・(マクロ周りは本当に鬼やぜ)

さて、ようやく本題。上記のマクロがどのように展開されるかというのが個人的には面白いなぁと思ったという話。Chibiのissue見れば答えは載っているのだが、引数の個数にも寄るが、この構文簡易カリー化と取れなくもない。上記の手続きfは以下のように展開される。
(define f (lambda (x) (lambda (y) (+ x y))))
たとえば、SXPathはこんな感じの手続きをころころ作るのだが、実装を見てみると(当然なんだけど)明示的にlambdaをいっぱい書いている。でも、これ使えばそのわずらわしさから開放される!というわけだ。

僕自身、あまりそんな使い方しないんだけど、マクロ使えばこんなこともできちゃう!というちょっとした例。

2012-11-11

R7RS対応

ドラフト7の範囲の実装が大体終わった。Chibi SchemeのR7RSテストケースもほぼ通るようになっている。(通らないのは、R6RSと競合する部分とFlonumの精度が決め打ちになっている部分と、R7RS上では不明瞭に見えてかつ僕がChibiの挙動の方がおかしいと思う部分)

他の人が仕様書に対して書いたテストというのは意外と自分ではチェックしない部分の挙動があったりしてバグ潰しに役立つということが分かった。実際、Chibiのテストケースを通るようにした際に6個くらいバグをつぶした。中にはSEGVを起こすようなのもあって、普段使わない、書かない系のコードというのの中にこそバグが含まれているというのがよく分かった。

現状でR7RS準拠度はevalが環境を破壊的に変更するのと(問題だとすら思っていない)、R6RSなのでbinary、textualポートの区切りがはっきりしている点を除けば全て準拠していると思う。Chibiですら対応していないinclude-library-declarationsも入っているw

今週末にリリース予定の0.3.8からR7RSドラフト7に対応しているという宣伝。

未束縛エクスポートのチェック

R6RS及びR7RSではexport句に未束縛なシンボルを書くとエラーになるとある。しかし、Sagittariusでは実装上の手抜きでチェックをしていない(やれば実はできるんだけど、コンパイル時間の増大を防ぎたいとか、メモリ使用率を減らしたいとか、まぁいろいろ言い訳をつけてやってない)。

っで、近頃(昨日)R7RSのドラフト7が出て、結構な数の手続きが追加または削除になったのがあり、実際に手続き及びマクロが定義されているかのチェックを目視とかテストケース書いてたらやってられないなぁと思ったのでこんなスクリプトを書いた。
(import (rnrs) (util file)
        (sagittarius vm) (match)
        (srfi :26) (srfi :64))
;; この部分を適当に変える。
;; R7RSだけ調べたいなら"./sitelib/scheme/*"とか
(define files (glob "./lib/**/*"))

(test-begin "bound check")
(define (check-exports file)
  (define (do-check name exports)
    (guard (e (#t 
               (when (message-condition? e)
                 (print (condition-message e)))
               (print "failed to find library: " name)))
      (let ((lib (find-library name #f)))
        (define (check orig export)
          (unless (keyword? export)
            (test-assert (format "~a:~a" name orig)
                         (let ((gloc (find-binding lib export #f)))
                           (and gloc (gloc-bound? gloc))))))
        (for-each
         (lambda (export)
           (match export
             (('rename renames ...)
              (for-each (lambda (rename)
                          (check rename (car rename))) renames))
             (_ (check export export))))
         exports))))
  (guard (e (#t (print "failed to read: " file)))
    (when (file-regular? file)
      (let ((expr (file->sexp-list file)))
        (match expr
          ((('library name ('export exports ...) rest ...))
           (do-check name exports))
          (_ #f)))
      )))
  

(for-each (cut check-exports <>) files)

(test-end)
やっていることは至極単純で、見つけたファイルを読み取って、中からlibraryで始まるS式見つけて、ライブラリ見つけて、exportしているものが存在するか調べる。それだけ。
なぜか、||なシンボルを読まなかったり、キーワードをキーワードとして読み取らなかったりと、変な挙動があるけど、それなりに便利。 既存のライブラリで未束縛なエクスポートを含んでいたのものさえ発見できたし・・・orz

2012-11-10

R7RSの7thドラフト

ようやく出た。正直、出る出る詐欺じゃないかと心配していたw

Ballotの結果なんかは追っているので、もしR7RSで検索してたどり着いたのであればそちらを見ていただきたい。
Sagittariusは6thドラフトに追従していないので5thドラフトから変更となるが、まぁ問題はないだろう。7thドラフトは個人的に割りとインパクトが大きくて、ライブラリの修正だけではなく、コンパイラもいじらないといけない。以下に自分用のメモも兼ねて修正ポイントを記載する。

【コンパイラ】
include-library-declarations
define-library構文に追加になった。include先のライブラリのexport句のみを対象に持ってくる。単なる便利構文。正直、いるかこれ?と思っている。
【ライブラリ】
(scheme base)
いろいろな手続きが削除、移動になった。
(scheme cxr)
cxxr以上の手続きが(scheme base)から取り除かれてこっちに移動。
(scheme char normalization)
Unicodeサポートが必須じゃなくなったので削除。
(scheme division)
たしか6thドラフトの段階で消えてた気がする。
(scheme r5rs)
R5RSコンパチライブラリ。(7thからだったかな?記憶あいまい)
(scheme lazy)
delay-forceが追加になった。
ライブラリの修正は、面倒なだけで特にインパクトは小さいんだけど、コンパイラは面倒だ。まぁ、そこまで面倒でもないんだけど。include-library-declarationsは個人的に非常に醜いと思うのでできれば入れたくないが、たぶんファイルに残るだろうなぁ。

【文字と文字列】
勘違いしていたことと、やはり納得がいかないので一応。
7thドラフトで文字列がサポートしなければならない範囲が明確に定義された。処理系は最低でも「NULLを除いたASCII文字の文字列」のサポートしなければならない。 まぁ、ここまではいいだろう。ただ、「文字列を文字の集合」として捉えた際に現状のドラフトでは不整合がでる。なぜか?問題はこの一文;
All Scheme implementations must support at least the ASCII character repertoire: that is, Unicode characters U+0000 through U+007F.
 7thドラフトでは明確に文字がサポートしなければならない範囲にNULLが含まれているが、文字列ではNULLを省いていいよって言ってるのだ。まぁ、文字列 != 文字の集合なら何の問題もないけど。R7RSに明確に文字列は文字の並び(sequenceってどう訳すの?)と書いてあるね。

2012-11-08

curly-infix (SRFI-105)

I have merged my SRFI-105 implementation on Github to Sagittarius itself. So it can be used from version 0.3.8.
I haven't follow all the discussions nor read all specification (WTF?!), so I'm not sure if the following code is too much #\{ and #\} or it's supposed to be like this;
;; Sagittarius need this line
#!read-macro=curly-infix
;; For portability with other implementations.
#!curly-infix

(import (rnrs))

(define (fact n)
  (if {n = 0}
      1
      ;; Here, it seems too much. If I could write
      ;; fact(n - 1), it seems way better. But my
      ;; implementation (mostly taken from reference
      ;; implementation) doesn't allow me.
      {n * fact({n - 1})}))

{print fact(5)} ;; -> 120
As far as I understood, inside of #\( must be treated the same as usual Scheme way. So if I want to pass calculated argument(s) with infix style, then I need to wrap with extra pair of #\{ and #\}. If I'm not understanding correctly, please let me know :-)

Some part such as {n = 0} might be easier to understand for people who are not so familier with polish notation. However for people who already wrote a lot of Lisp programme, this might make them confused (or maybe not?).

Anyway, providing choices to users is a good thing, I believe.

2012-11-03

SQLiteをODBCで使う

せっかくODBCをサポートしてるんだし(WindowsとCygwinだけだが)、SQLiteでも使ってみるかと思いちょっといじってみた。目的としてはdbi-preparedでバイトベクタとポートを受け付けるようにしたかっただけなのだが・・・

結論を言うと、SQLiteでは(というか、SQLite ODBC Driverでは)BLOBを扱うのが無理。正確には巨大なBLOBを扱うのが不可能くさい。

なぜか?SQLGetDataがここに書かれている動作をしない。(おそらく)呼び出すたびに先頭からデータを取ってくる。もしくは、一度の呼び出しで全部取得できてしまったら二度目の呼び出しでまた全部データを取ってくるため。なので、以下のコードが無限ループに陥った。
(import (rnrs) (dbi))

(define conn (dbi-connect "dbi:odbc:server=SG"))
(define sql "insert into test (id, data) values (?, ?)")

(let ((query (dbi-prepare conn sql 1 "ok")))
  (dbi-execute! query))
(define sql "select * from test")
(let ((query (dbi-prepare conn sql)))
  (print (dbi-execute! query))
  (print (dbi-columns query))
  (let loop ((col (dbi-fetch! query)))
    (when col
      (vector-for-each (lambda (v)
                         (if (binary-port? v)
                             (let loop ((bv (get-bytevector-n v 20)))
                               (unless (eof-object? bv)
                                  (print bv)
                                  (loop (get-bytevector-n v 20))))
                             (display v))) col)
      (newline)
      (loop (dbi-fetch! query)))))
(dbi-close conn)
dataカラムはblobになっている。問題になった、get-bytevector-nの部分。ポートになっているが、中身はSQLGetDataを呼び出して必要なだけ取り出すというもの。ただ、ポートの部分は普通のファイルと共通になっているので(昨日そうした)、まずバッファに溜め込もうとする。問題は、SQLGetDataが常に先頭からデータを読み出すので、EOFが返ることがないこと。

これが、get-bytevector-allだと予定通りに動くのだが、今度はデータが空のblobが半端なくでかいサイズを要求するのでメモリが足りないといわれる。データ空なのに・・・

SQLiteを仕事で使うことはないので、割とどうでもいいのではあるが、解決するため(結局できなかった)に2時間は無駄にしたのでせっかくだしと思い書いた。