省メモリ計画(スタック編)

自分でも次があるとは予想していなかったｗ

ふとシャワーを浴びながら気づいたのだが、Sagittariusではほぼ全てのSchemeオブジェクトがヒープに作られる。しかし、多くのオブジェクトは使用後すぐに不必要になりGCを待つことになる。これはパフォーマンス的にはメモリ使用量的にも嬉しくない。

なぜこのような作りになっているかと言えば、単なる手抜きである。しかし、初期化用のC APIを用意してやればいいような気がしてきた。全てのオブジェクトに対して用意するのは手間だが、とりあえず頻繁に使用されるかつ使用後すぐに破棄されるようなものだけに絞ってやればそこそこ成果が出るのではないかと思っている。

では何が上記の条件を満たすようなものなのか？実は既にいくつか候補があって、トランスコーダ、ポート、ハッシュテーブル辺りがとりあえずのやってみると効果がありそうなものとなっている。なぜか？ポートはキャッシュを読み込む際に問答無用で作られるので、たとえば(rnrs)を読み込むと20個以上のオブジェクトが作られることになる。トランスコーダはUTF8からUTF32に変換する際に作られているうえに、この処理はreadで常に起きている。ハッシュテーブルはいたるところで共有オブジェクト等の保持に使われていて、たとえば1つのキャッシュファイルの読み込みに2つ使用されるなどかなり使われている。

とりあえず実装してみて効果があれば順次足していくという方向で行くことにする。

Why Sagittarius?

While ago, I saw a comment on Reddit which said 'why Sagittarius?'. At that time, I've just thought 'why not?' and 'then why Racket or other implementations?'. Now I still don't have that much reason but at least there should be a good reason to be chosen! So trying to convince people who are looking for a good reason to switch or start trying new Scheme implementation.

N reasons why you should use Sagittarius.

1. Multiplatform
Sagittarius is supported on number of platforms, such as Windows, Cygwin, Linux, QNX, FreeBSD*1 and Mac OS X. A lot of implementations don't have native Windows binary support. So if you need to run Scheme on Windows, then this is one of your choice!

2. Architecture independent FFI support
Sagittarius is using libffi for its FFI so most of platforms can use FFI.

3. MIT license
GPL or LGPL is not suitable for a lot of situation (say Racket is LGPL).

4. Short term release cycle
Currently Sagittarius is being released once a month so if you find a bug, you would get the fixed version next month.

5. Both R6RS and R7RS are supported
As far as I know, Sagittarius is the only implementation which supports both R6RS and R7RS (currently).

6. Reader macro and replaceable reader
If you don't like S-expression but like Scheme or want to use some of libraries written in Scheme (or Sagittarius' builtin libraries), this would be your choice!

You will probably find more reasons once you start using it. So why don't you give it a shot?

*1: Current FreeBSD ports has Boehm GC 7.1 however this version doesn't work on it. 7.2 or later needs to be installed manually.

省メモリ計画(ポート編)

多分ポート以外にはないと思うけど・・・あってもコーデックくらいかね、次・・・

SagittariusはCで書かれているのだがポート周りはカスタムポートとかの兼ね合いから可能な限り柔軟にしようと思いオブジェクト指向風に書かれている。単に構造体が自身を操作するための関数ポインタを持っているだけだが。

先日ポート位置の不具合を直した際に4つほど関数ポインタを足したのだが、 現状のポートのサイズが不安なことになってきた。現在のHEADでポートのサイズは72バイト(32ビット環境)。単なるオブジェクトとしてはちとデカイ気がする。しかも、これは実装部分を除いた共通インターフェースだけなので、実際には100バイトを超えてくる。(バイナリポートが88バイトと一番でかい・・・)。

これがC++ならクラスが持つメンバー関数のサイズなんて気にしなくてもいいのだが、そこはないものねだりになる。そこで、とりあえず何かいい案はないかなぁと考えたのだが、ポートの構造体に仮想テーブル的なポインタを持たせて実際の操作用関数は静的領域に確保してしまうというのはどうだろうか？問題になるのは関数へのアクセス部分になるが、マクロにするか、関数呼び出しにしてしまうか悩んでいる。マクロにすると仮想テーブルを外に出さないといけないが、関数呼び出しにしてしまうとパフォーマンスが心配になる。

とりあえず書いてみてから悩むことにする。

パッケージとか

Sagittariusは自分が仕事で使うために書き始めた処理系なのだが、ありがたいことにいろんな方からバグ報告をいただいたりパッチをいただいたりしてきた。宣伝とか名前を広める系の活動が苦手で、数回comp.lang.schemeに投稿したのを除けばほとんど何もしていないし、自分でも「自分が最大のユーザー」であればいいかとか思ってて特に気にしていなかった。

ところがここ数日(本当に2,3日)でArch LinuxのAUR(Arch linux User Repository)に乗ったり、Mac OS XのHomebrewに乗りそうだったりと、4年前(公開したのは2年半前)には想像もしていなかったことが起きた。どちらの環境も持っていないので(Arch Linuxはインストールに挫折した・・・)、その意味でもありがたいことだ。

こうして本格的に自分以外の人の手によって広まっていくのを(広まってない？)目の当たりにしていると、雛が巣立っていくような感覚を覚えて嬉しいような寂しいような感じである。もちろん自分が最大のユーザーであることは多分変わらないだろうし(譲る気もないｗ)、開発自体を誰かに譲るとかも考えていないのだが・・・

そういえば、開発者MLってないの？って聞かれたのだが、あった方がいいのだろうか？登録者自分だけっていうことになりそうな雰囲気ありまくりだし、作ったことすらないのでどうすればいいのかさえ知らないけどｗ

訛り

(元ネタ Island Life - 訛りとか)
本題とは関係ない部分でなんとなく引っかかっていたのがなんとなく分かった気がしたのでつらつらと書いてみることにした。

オランダでは英語はほぼ全ての人にとって第二外国語であるといえる。もちろんイギリス人もいるし、アメリカ人やカナダ人、オーストラリア人だって住んでいるので例外もままある。そうすると、まぁ大抵の人がしゃべる英語は訛っているわけだ。

もちろん個人差はあるし、中にはすごく綺麗(典型的)な英国訛りでしゃべる人もいれば、がちがちのインディアン訛りで何言ってるのか理解するのに苦労するなんて人もいる。(インド人を例にあげたのに特に理由はない。別にスペインでもフランスでもいい。ロマンス系言語訛りはひどく聞きづらいし。)

僕の職場はかなり多国籍で東は日本(俺だよ！)から西はカナダや南米とまぁ多種多用である(最近は中東出身の同僚が増えてきた感もあるが。) 会社自体はそんなに大きくないので、人は少ないのだが、これだけ種類があるとまぁ慣れる。自分の英語の発音がどれほど訛っているのかというのは実に知りようがなくて(だれも指摘しないし)、少なくとも意思疎通は問題なくできるレベルではあると思う。ただ、確実にいえるのは、いい悪いは別にして、昔と思うと発音が大分変わったなぁということ。Tomatoがトメイトからトマートになったとか、そんなレベルではあるが。

本題に絡みそうなところに無理やり戻すと、北米(特にアメリカ)出身の人は特に訛りや別名に対して非寛容であるというのが経験から学んだこと。たとえば、aubergineとかcourgetteはほぼ通じない。ついでに同じwaterでも「ウォータ」では通じない(飛行機内で通じなかった経験あり)。個人的にPGが対象にしているのはおそらく米国内のみの話じゃないかなぁと思ったりはする。あの国ほどに言語に非寛容な国は後フランスぐらいしか知らん。

SRFI 110

Today the SRFI 110 will be the final state (according to the latest ML topic). So for the celebration, I have supported it on Sagittarius.

Basically I have only added compatible layer to the reference implementation and run some scripts. There is one exception which is not satisfying requirement. That is, again the same as previous curly-infix SRFI, hash-bang directive. I don't have any intention to support these SRFIs in core Sagittarius so it's always uses reader macro or replaceable reader. So to use this SRFI on Sagittarius, it must look like this;

;; #!sweet for compatibility
#!sweet
#!reader=sweet

define factorial(n)
  if {n <= 1}
     1
     {n * factorial{n - 1}}

print(factorial(10))

define a 4

define g(x y)
  {x * y}

let <* x sqrt(a) *>
! g {x + 1} {x - 1}

It might not be a big issue as usual.

The good thing about this SRFI is that it can be used in real world. If you are familiar with Python or Ruby which I don't know much about, this might be a good alternative. So the next step for this would be an Emacs lisp to support this :)

Well, again (the same as SRFI 105) I don't think I use this SRFI but it's always good to have choices for users.

TLSライブラリのバグ

WebSocketをTLSで使うためにSNIがサポートされてないといけないという話からバグを発見。元々は、wssでアクセスするとフリーズするという話だったのだが、これSNIが問題ではなく単にバグを踏んでいただけだったという話。

問題はTLSのレコードが複数のハンドシェイクメッセージを持つことが可能であることに起因する。現状の実装では1レコード1メッセージを期待していて、複数のメッセージが乗っていた場合2レコード目以降を捨ててしまうというバグである。(単にRFCの読みが甘かったという話でもある。)

これ結構大きめな問題で、設計からやり直しかねぇと思いながら15分くらい考えたらなんとなく隙間を縫っていけそうな解決案が思い浮んだのでメモ。現状レコードで運ばれてきたメッセージはとりあえず一度に全部取得し、その後先頭バイトを見てメッセージの振り分けをしている。ここで、アプリケーションメッセージ以外のメッセージは取得した内容をバイナリポートに変換して扱いやすくしている。

問題になるのは、変換したポートが空になるまで読んでいないことなのだ。1メッセージ読んだ後に1バイト先を見てやりEOFでないならセッションオブジェクトにでも保存しておけば次に読むのはメッセージであるということが分かるのでソケットにアクセスしにいって無限に待つということもなくなるのではないか、という案。レコードを読む部分の処理とセッションオブジェクトの変更のみで残りの部分は特に問題なくいける気がする。

とりあえず、明日試してみることにする。 しかし、原因を追究するためにRFCを読み直したり、パケットログを取ったりといろいろやったが、ほぼ空回りというのが自分らしいというか・・・

SchemeでJSON-RPC

SchemeでRAM over Httpだとさすがに誰得すぎるというのがあったので、まだ需要がありそうなJSON-RPCにw (どちらも仕事で使っているという点は一緒)

最近自社プロダクトでJSON-RPCを使っている外部インターフェースがあることに気づいた。ついでにその機能をテストする必要も出てきて、毎回SoapUIで作られたテスト用のスクリプトを数個走らせるのはたるいので、えいやっと作った。最新のHEADに入ってる。

JSON-RPC自体は仕様がネットで公開されているので、それを参照してもらうとして、実際にSagittarius上で使うと以下のような感じになる。

(import (rpc json) (rpc transport http))

(define request (make-json-request 'someMethod :params #((p1 . 1) (p2 . 2)))

(let-values (((status header response)
       (rpc-http-request "http://somewhere.com/jsonrpc-service" request)))
  (json-response-result response))

たったこれだけ！

JSON-RPC自体は非常に簡単な仕様なので、JSONを読み書きできるライブラリがあれば実装可能。 HTTPはSRFI-106で頑張ればいけるので、その気になればそこそこポータブルな実装でもいけるかもしれない(やる気はない)。

実装した際に一応気にしたのは、トランスポートとメッセージは可能な限り分離するということ。これは(今のところ予定はないが)他のRPC(Message PackとかXML-RPCとか)をサポートする際に自分が楽をしたいため。ただ、現状どちらの実装も一個しかないので上手いこと分離できてるかは多少不安。ついでに、JSONの読み書きに使っているChicken Schemeからの移植JSONライブラリはベクタをマップとして扱うので多少使い勝手が悪い部分もある(主にレスポンスデータの探索等)。まぁmatchが使えたり、メモリ気にしなくていいなら手間がかかる程度ではあるが・・・

実際のコードは実に合計で500行以下くらいなので、こういうのがサクッと作れる位には下地になるライブラリが揃っているということになる。多分に偏りがあるというか、一転集中型で揃っているだけだが・・・

Sagittarius 0.4.8 リリース

Sagittarius Scheme 0.4.8がリリースされました。今回のリリースはメンテナンスリリースです。

修正された不具合

• bytevector-u8-set!が負のインデックスを受付けかつデータを破壊する不具合が修正されました
• マクロ展開でlambdaが未束縛エラーになる不具合が修正されました
• cond-expandがネストした条件を処理できない不具合が修正されました
• bitwise-ior、bitwise-xor及びbitwise-andが0引数を受け付けない不具合が修正されました
• write-emv-tlvが長さバイトを正しくエンコードしない不具合が修正されました

改善点

• bitwise-ior、bitwise-xor、bitwise-and、fxior、fxxor及びfxandのパフォーマンスが改善されました

新たに追加された機能

• bytevector-split-at*及びbytevector-splicesが(util bytevector)に追加されました
• SRFI-106がサポートされました
• CMACライブラリ(rfc cmac)が追加されました
• c-variableマクロが(sagittarius ffi)に追加されました
• QNX (BlackBerry 10)環境でのビルドがサポートされました(x86のみ)
• socket-sendto及びsocket-recvfromが(sagittarius socket)に追加されました

非互換な変更

• let-syntax及びletrec-syntaxの既定の振る舞いがR6RSのものになりました。R5RS/R7RSの振る舞いにするには#!r7rsをつける必要があります。

速度改善

Pure SchemeでCRC32のベンチマークを取った方がいて、ありがたいことにSagittariusも結果に入っていた。

Scheme で CRC 計算の件について、いくつかの処理系で動かして時間を計ってみた。 表の数値は 200MB のデータを対象にしたときにかかった時間。 CRC32 改は値を 16bit ずつに分けて計算するバージョン。 pic.twitter.com/COhgUkOYWv
— (32) 齊藤敦志 (@SaitoAtsushi) August 16, 2013

問題は結果のほうである。後ろから数えた方が早い位置にいる。Sagittariusは最速を目指しているわけではないのだが、(明示してないけど)高速であることも売りにしている。幸いにもソースは公開されていらしたのでプロファイルを取って速度改善に望むことにした。

Fixnumは30ビット幅しかないので(32ビット環境)CRCテーブルの要素ほぼ全てはBignumになると思っていい。これは避けようがないので放置。ざっとソースを見ると(当たり前だが)ビット演算が多用されているので実装を眺める。Fixnum-Bignumの組み合わせの場合にFixnumをBignumに変換してBignum同士で演算するようにしていたので、とりあえずこいつのメモリ割り当てをやめるようにする(ちょこっと改善された)。

次にプロファイルを取る。するとbitwise-xorやたら遅い。実装もまぁ、そりゃ遅いわという感じだったので、ゴリゴリ書き直し。(15%くらい改善)。次いで気になったのでbytevector-u8-refがやたらサンプリングされていた。こんなの単なる配列アクセスだからどれだけ呼ばれてもそんなにあるわけ無いだろうと思ったら実装があほなことをしていたので直す(微々たる改善)。

とりあえず、この段階で既存のものと比較してみた。結果は以下。

$ sash crc.scm

;;  (crc32 data)
;;  121.992214 real    124.3640 user    6.130000 sys

$ ./build/sash.exe crc.scm

;;  (crc32 data)
;;  100.720778 real    101.5090 user    3.6040000915527344 sys

うむむ、まだ遅い。bitwise-xorが処理時間の半分を占めているのでそこの改善がほぼダイレクトに効くのだが、どうやら効かせ方が足りないらしい。

Boehm GCとQNXとBB10と

いろいろ動くようになってきたので多少のメモを含めて。

BB10(Blackberry 10)上でSagittariusを動かせないだろうかというのはそれこそ発売当初くらいから考えていたりする(2月か？)。BB10はQNXをベース(というかOSはQNX)にしたデバイスなのでPOSIX準拠(なはず)。POSIXをサポートしてるんだし、いけるだろう程度にしか考えてなかったのだが、Boehm GCが鬼門であった。

Twitterでも呟いたのだが、Boehm GCの環境依存コードはよく言えば歴史を感じさせる継ぎ足しっぷり、悪く言えば全くもって嫌気がするレベルのコードである。QNX自体は結構歴史あるUNIX系OS(らしい)ので当然サポートされてるだろうなぁ、なんてあまっちょろいことを考えていたのだが、世の中そううまくいくわけはなかった。がっつりパッチを書きました。幸いだったのは、FreeBSD依存のコードとか、OpenBSD依存のコードが結構流用できたので最低限サポートしなければならない部分だけ書けばよかった点かな。最新のHEADはQNX用のBoehm GCのパッチが入ってたりする。できに自身はないので、本家に取り込んでもらおうということは考えていない。

元々はSagittariusのC APIを使って実装しようと思ったんだけど、RIMが提供するIDEでの設定が分からなかったのでbarファイルにsashごと全部放り込んでリモートREPLを立ち上げるというかなり強引な手を使って実現してたりする。ソケット通信なのでセキュリティ等々をもう少し考えないとまずいのだが(俺々証明書作ってTLSで通信するか？)、まぁそれはもう少し後にする。GUIのデザインは正直苦手なのと今一Widgetの融通が利かないのとで多少異常に満足のいかないものになっているのも愛嬌だろう・・・

とりあえず、実装詳細的なもの。

• sashプロセスが立ち上がってもREPLサーバは立ち上がっていない
• 回避するためにサーバが立ち上がったらマークファイル作るようにした
• (exit)を実行するとプロセスごと死ぬ問題
• 死んだことを検地して再起動を促すように
• Qt側のソケットとプロセスの状態をQtのシグナル/スロットで監視
• これ、便利なんだけど、スロット内で他のシグナルを起動するようなことすると意味不明のバグになる
• 既に悩んだ
• しかも、どれがシグナルを送るのか今一わからなかったりするしｗ

ふと思ったのだが、この手法(リモートREPL)で行けば他のモバイルで動かすのも簡単にいけるのではないかと妄想。

以下はTODO

• 起動ポートを設定可能にしたい
• 既に準備はしてある
• 実行履歴があると便利だと思う
• 外部に出す？
• 実機で動かしてみたい
• Blackberry Worldに登録

仕事で山ほどBB7(一つ前のモデル郡の総称)の実機を使ってるのに、BB10の実機はない現実。ここではまだ売ってないので買うという選択肢もないという(まだ北米だけか？もう欧州でも売ってる？買うつもりはないんだけどｗ)。ストレステストみたいなことはしてないので、Boehm GCがまともに動いてるのかは微妙なんだけど(多分動いてると思う)、気になってるのはシミュレータと実機ではCPUが違うこと。実機はARMなんだよね。CPU依存の部分は特に変更なかったと思うから大丈夫だとは思うけど・・・


ということで、だれかBB10ください(違

Porting to BB10

A lot of Scheme implementations are ported to mobile device such as Gambit (iPhone), Mosh(Android), Gauche(iPhone, developing state though). Well, I'm feeling like it's time for me to ride the wave! Unfortunately, I have no developing environment neither iPhone nor Android but Blackberry. So I've so far decided to do with BB10 environment.

First of all, I needed to build Sagittarius on BB10 environment. This wasn't so difficult actually, I just needed to provide proper CMake tool chain configuration and some patches for Boehm GC (which only makes compiler satisfied currently though).

After that, I was trying to use Sagittarius as a library so that the application only needs to do eval and outputs the result. However this wasn't easy for me to handle standard I/Os. On BB10 environment, as far as I know, it is impossible to redirect keyboard input and standard output to GUI panels. So I thought I needed to create custom port to handle these things but I was too lazy to do it. So I've decided to use remote REPL which is already in library.

The basic idea I'm trying to do is really simple. Put all Sagittarius component into bar (Blackbarry ARchive, I guess) file and run the remote REPL as a child process. So what I need to implement is only send user input and receive the result. Then I'm facing a problem that for some reason sash is not executable. So I wrapped with shell which add permission of execution then run it. Now I've got core dump.

What am I missing?

Why I think macro is necessary for programming language!

DRUNKEN ARTICLE CAUTION: the article might not make any sense!

Macro, that is the last resort for all programmers. Macro, it's a sweet temptation. Macro...

Well, if you are familiar with macros and doing job with Java (or any other languages don't have macro), you must be really frustrated like me. I was thinking why I've got so irritated without macros and got a conclusion.

I assume all programmers want to write clean, fast and maintainable code without any inconsistency. Suppose you are a Java programmer and need to write really similar code multiple times and all of the classes are not the same region. In this case, I would create an abstract class or utility class to put all common process in. However I think it's ugly because the abstract class is not the behaviour of the derived class and utility class is not object oriented. Then what is the cleanest and consist way to resolve it? Copy&Paste? I have yet no solution.

If I'm using C++ then I could use template for that situation. It allow me to write common process without creating super class and inject dependency. If I can use Lisp for this situation, this is, I think, the best situation to use macro to avoid code duplication or writing ugly code.

What makes macro so powerful? Well, after writing this I felt I'm so stupid to write such obvious question. If you have written any code, then you must know how powerful modifying source code before it's compiled is. You can feel you became a god or so (not really). So far, I only know the language which allows you to do such free things is only Lisp. It has macro, read macro, reflection, aspect oriented and so on. (Well, even though I listed some other stuff but I'll focus on only macro.) Which other language can make own *syntax* within its language specification?

I know it has also some crappy things like it doesn't allow me to do much things within the specification (Scheme), not so portable between implementations (CL, Scheme) and all. And I think each language needed to decide not to have all *nice to have* features. So everything is trade off but if that's so, I would rather go more comfortable one and to me comfortable means freedom. More precisely, the language which can extend itself if I needed.

Yes, as I expect there is no conclusion nor sense in this article. Don't write something in drunk.

引数の上限

引数の上限を超えるとどうなるだろうと以下の記事を読んで気になった。

Chibi schemeの多値は単に多値オブジェクトで、call-with-values等で明示的に受け取らないと悲しいことになる。もっともChibi schemeのような実装にも、多値の長さに制限がないというメリットがある。nmoshは多値の長さ(= 事実上手続き引数の個数制限)が100程度に制限されている。現状のSchemeではこの制限をクエリする良い方法が無い。

引数個数制限はご無体な気もするが、Cの呼び出し規約のように関数呼び出しをスタック経由で行う規約は基本的にヒープサイズ制限よりもスタック長制限が先に来る。常識的に考えて固定arityの引数が100を越えることは無いので、可変arityの手続きの呼び出し規約をスタック渡しとオブジェクト渡しに分けるのは効果的かもしれない。
[scheme][nmosh] Unspecifiedの数とarity - .mjtの日記復帰計画

まぁスタックサイズに限界はあるわけだし、SEGVのが普通かなぁと思いつつ、以下のスクリプトを用意。

(import (rnrs) (only (srfi :1) iota))

(define-syntax apply-100000-values
  (lambda (x)
    (syntax-case x ()
      ((k)
       (with-syntax (((v ...) (datum->syntax #'k (iota 100000))))
         #'(list v ...))))))

(apply-100000-values)
(display 'ok) (newline)

以下はGauche用

(define-macro (apply-100000-values)
  `(list ,@(iota 100000)))
(apply-100000-values)
(apply-100000-values)
(print 'ok)

でっ、結果。(Chezはiotaを自前実装した。Chibiは低レベルマクロの使い方が分からないので割愛。)

Chez - ok
Gauche - SEGV
Mosh - ok
Sagittarius - 返ってこない(マクロの展開が終わらなかった)
Ypsilon - ok

意外だなぁと思ったのはMoshで、以前valuesに10000以上の個数をapplyするとSEGVるというバグを報告している経験からこけるものだと思っていた。(スタックを壊してる可能性があるので、他の操作をしたら予期しない場所でこける可能性はあるが。)

Chez及びYpsilonはどうして動いているのかは分からない。

Why does this call/cc go into infinite loop?

I've found interesting call/cc stuff in Chaton's Gauche room (this)

The code is this one;

(let ((x 0) (cc '())) 
  (set! x (+ x (call/cc (lambda (c) (set! cc c) (c 1)))))
  (if (< x 4) (cc 2) x))

As far as I investigate, Chez, Chicken, Mosh, Sagittarius and Ypsilon went infinite loop. Chibi and Gauche returned 5. Well I'm not a guy from continuation world so I can't say which is correct. However if the call/cc is located to left hand side, then it won't be infinite loop.

;; This returns 5
(let ((x 0) (cc '())) 
  (set! x (+ (call/cc (lambda (c) (set! cc c) (c 1))) x))
  (if (< x 4) (cc 2) x))

It seems the order of evaluation so I can probably get the answer.

I don't know about other implementations but Sagittarius so following guess is based on its call/cc implementation.

On Sagittarius, continuation is stack and it contains return address. So call/cc captures arguments and return address. Following is the image;

#first one
before call/cc
 +----------+
 |   cont   |
 +----------+ <- captured
 |   pc(+)  |
 +----------+
 |    x=1   | *1
 +----------+
 | pc(set!) |
 +----------+

#second one
before call/cc           after call/cc
 +----------+             +----------+
 |   cont   |             |    x     |   
 +----------+ <- captured +----------+
 |   pc(+)  |             |   c(1)   |
 +----------+             +----------+
 | pc(set!) |             |   pc(+)  |
 +----------+             +----------+
                          | pc(set!) |
                          +----------+

NOTE: pc is return address, cont is call/cc's argument. 
      Stack is growing upwards.

Well it's already obvious but I will describe just in case.The point is *1. The first one, the x is not a box means it's mere value (in this case 1). Then call/cc will capture the stack with the value. So the second call of (cc 2) will always be addition of 1 and 2. Thus it will never be greater than 4. On the other hand, the second case, stack doesn't have x yet so that VM will always compute what is inside of the box (x). Then (cc 2) will always compute the value of x and 2.

I think implementations caused infinite loop are using the similar method to implement call/cc as Sagittarius and Chibi and Gauche use something different. And again, I'm not the those guys from continuation world, so can't say which is correct or not but as my understanding both can be correct and this case is sort of edge case of call/cc.

Bignumの速度改善(調査編)

SBCLがGMPを使うようになったらしく、こんなツイートをもらった。

これで @tk_riple さんの第二次VS SBCL Bignum戦争開幕？
— llibra (@l_libra) July 5, 2013

期待されているなぁ・・・相手GMPだけど・・・

期待されると応えようともがく性分なので、とりあえず現状でどれくらいGMPと差があるのか適当にテストしてみることにした。GMPと言えばMoshが使っているのでここと比較。なぜか？機械語吐き出すSBCLと戦う前に同じバイトコードなScheme処理系のMoshを倒さないとオーバーヘッドの部分で確実に負けることが確定しているから。

テストコードは以下(ここのPython用のをSchemeに移植)：

(import (rnrs) (time))

(define (factorial n stop)
  (let loop ((n n) (o 1))
    (if (> n stop)
        (loop (- n 1) (* o n))
        o)))

(define (choose n k)
  (/ (factorial n k) (factorial (- n k) 0)))

(time (choose 50000 50))
#|
;; Mosh用timeライブラリ
;; time.scm
(library (time) (export time) (import (mosh)))
|#

以下が結果。

% time sash test.scm

;;  (choose 50000 50)
;;  6.536399841308594 real    11.13800 user    1.669000 sys
sash test.scm  11.17s user 1.76s system 194% cpu 6.661 total

% time mosh --loadpath=. test.scm

;;1.4351999759674072 real 1.264 user 0.172 sys
mosh --loadpath=. test.scm  1.28s user 0.20s system 99% cpu 1.482 total

まぁ、分かってはいたのだがここまで差があるのか・・・
SagittariusはBoehmGCがGC用スレッドを持ってるからRealとUser時間が倍違うのか？とりあえずReal時間だけ気にすることにする。

このベンチだと単純に乗算だけなんだけど、とりあえずそこからか・・・先は長そうである・・・

Loop macro for Scheme

The inspiration came from this article's comment: 10.times - Island Life

I'm not a CL user but I sometimes think CL's loop macro is really convenient if I want to write something really small. (I don't think I want to write big stuff with it. It's too complicated to me.) So why don't I write something looks like it?

Here is that something. It doesn't cover whole loop macro but some.

#!r6rs
(import (except (rnrs) for-each map) (only (srfi :1) iota for-each map))

(define-syntax %loop
  (syntax-rules (:for :in :do :repeat :collect)
    ((_ (vars ...) (body ...) op :for var :in l rest ...)
     (%loop ((var l) vars ...) (body ...) op rest ...))
    ((_ (vars ...) (body ...) op :repeat n rest ...)
     (%loop ((tmp (iota n)) vars ...) (body ...) op rest ...))
    ((_ (vars ...) (body ...) op :do expr rest ...)
     (%loop (vars ...) (expr body ...) for-each rest ...))
    ((_ (vars ...) (body ...) op :collect expr rest ...)
     (%loop (vars ...) (expr body ...) map rest ...))
    ;; last
    ;; do trivial case first
    ((_ () (body ...) op)
     ;; infinite loop
     (do () (#f) body ...))
    ((_ ((var init) ...) (body ...) op)
     (op (lambda (var ...) body ...) init ...))))

(define-syntax loop
  (syntax-rules ()
    ((_ clause ...)
     (%loop () () #f clause ...))))

#|
(loop :for i :in '(1 2 3 10) 
      :for j :in '(4 5 6)
      :do (begin (display i) (display j) (newline)))

(loop :repeat 10 :do (begin (display 'ok) (newline)))

(display
 (loop :for i :in '(1 2 3 10) 
       :for j :in '(4 5 6)
       :collect (+ i j))) (newline)
;; (loop :do (begin (display 'ok) (newline)))
|#

I'm not sure if this is useful or not and I don't want to go deep inside of the crucial loop macro specification either, though :-)

NOTE: I've tested above code Racket (plt-r6rs), Mosh, Ypsilon and Sagittarius but Ypsilon raises an exception when the given list length are not the same.

TLSとFTPと

FTPライブラリを書いてたらTLSにバグが混入しているのを発見。しかも、0.4.4から紛れ込んでいたものだったという切ないものだった。まぁ、TLS周りはテストを書いていないので発見しようが無かったという話ではあるのだが、あんまり使わないんだなぁ自分でも・・・テスト大事だよ！(どうテスト書こう、テスト用にサードパーティの何かを入れるのは嫌だが、セキュリティ周りのテストを自家製だけで書くのはまずいし、さてさて・・・)

まぁ、原因はSRFI-6の挙動をポートから取り出してもポートを空にしないように直した際のバグなのだが、何しろ3ヶ月前のこととあまり直接的な原因ではないこともあいまって最初はどこが悪いのかさっぱり分からんかったりした。っで、どう見つけたか？もうね、ローラー作戦ですよ。0.4.3までソースを巻き戻してどこで起きるかというのを一個ずつ潰していくという何とも地味な作戦。0.4.3から0.4.4の間ではBignumのパフォーマンス改善してたのでそこかなと当たりをつけてたらまんまと外れたという、思い込みもよくないという話。

原因が分かれば直すのは簡単で、さくっと直してFTPの実装を再開。データコネクション周りが実は面倒だということが発覚して、どうしようというのが現在直面している課題。

問題になるのはアクティブモードなのだが、クライアント側がサーバソケットを作ってFTPサーバからの接続を待つ必要があるのだが、現状のソケットライブラリでサーバソケットを作るとgetsocketnameで取れるアドレスがループバックアドレス(0.0.0.0)になってしまう。じゃあと思ってAI_PASSIVEを外してやると今度は127.0.0.1が取れるのだが、これって他のサーバとやり取りできないよなぁという感じでごにょごにょしている。(どうでもいいのだが、socket-nameというAPIがあるんだけど、こいつが非常に紛らわしくなっているので変更してやろうと思っていたりする。) 普通にNICに割り付けられたIPアドレスを取る方法ってないのだろうか？

どうでもいいのだが、職場のFTPはFTPSは受け付けていないという事実が分かって驚愕している・・・SFTPじゃないとだめなのかよ・・・orz

ほしいライブラリ

ちょっと開発意欲が低下気味な6月、ほしいものはあるんだけどモチベーションが高まらないというなんともだめな感じである。

とりあえず、何がほしいかをメモっておいて後で頑張ろうという先送り作戦を展開してみんとす。といっても、今のところは2つしかないんだけどね。

【Lexer】
CのヘッダをパースしてFFIのバインディングを吐き出すような何かを作ろうとしているんだけど、Packratという強力なパーサジェネレータはあるくせにLexerは毎回手書きという切ない状態にある。 ということで、Packratで使えるLexerを生成する何かしらがほしい。妄想的に以下のように書けると嬉しいかもしれない。

(define generator
  (lexer
    (D #("0-9"))    ;; vector indicates a charset?
    (L #("a-zA-Z_"))
    ...
    ("/*" comment)  ;; here comment is a procedure takes one argument which is a port?
    ("auto" 'AUTO)  ;; returns token kind?
    ...
    ((/ "[" "<:") '#\[)
    ...))

細かいことは全然考えてないのだけど、とりあえずこんな感じでルールを書いたら適当にLexerを作ってくれる何かしらな感じ。RacketにLexerジェネレータなライブラリがあるから参考にしようかと考えている。(Pure Schemeな実装があったら是非教えてほしいなぁ)

【FTP】
仕事でちょいちょいFTPでwarを上げてJBossにデプロイなんてことがあるんだけど、現状でMavenをSchemeで叩いているのだから出来上がったwarもSchemeで上げてしまえたら一手間減るよなぁと考えている。FTPなんて実装はどこにでもあるわけだし移植するだけなんだけど割りと億劫になっているのと、APIをどうしようとか、TLSなソケットも使えるようにしてFTPSもサポートしないと使い物にならんとか考えていて手が動いていない状態。まぁ、なんとなく構想ができてきている段階ではあるので、テスト用の環境をでっち上げて作るだけではあるのだが・・・

個人的にはIMAPとかあるとiPhoneで音が鳴ったら適当にシェルからメールがチェックできたりして便利かもとか考えていたりはする。まぁ、これは必要に迫られていないので妄想すらないが・・・

Sagittarius 0.4.6リリース

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

修正された不具合

•  parameterize内でcall/ccを使うとパラメタの値が正しく復帰しない不具合が修正されました
• パラメタの束縛を変更しても変更が反映されない不具合が修正されました
• define-libraryで(scheme base)をインポートしないとcond-expandが使えない不具合が修正されました
• define-classが他のライブラリに依存している不具合が修正されました
• #x800000がマイナスの値を返す不具合が修正されました
• (sagittarius mop validator)のobservevrがエラーを投げる不具合が修正されました
• 組込み総称関数がSEGVを起こす不具合が修正されました
• current-jiffyが正確な整数を返さない不具合が修正されました
• ((and and))がREPL上でSEGVを起こす不具合が修正されました
• datum->syntaxが正しく構文オブジェクトを作成しない不具合が修正されました
• importがexcept句を無視する不具合が修正されました
• 組込み総称関数が:primary以外のqualifierを持てない不具合が修正されました
• list-sortが第一引数をチェックしない不具合が修正されました
• make-bytevectorの第一引数にマイナスの値を渡すとSEGVを起こす不具合が修正されました
• (clos user)をprefixインポートした際にunbound variable例外が投げられる不具合が修正されました

改善点

• define-c-structが局所的に扱えるようになりました
• FFIがwchar_t*を扱えるようになりました
• c-functionが可変長引数を扱えるようになりました
• MOPがより柔軟になりました
• コンパイラが使用されていないインストラクションを生成しないようになりました

新たに追加された機能

• object->pointer及びpointer->objectが(sagittarius ffi)に追加されました