Syntax highlighter

2016-08-24

暗黙の総称関数 (部分解決編)

昨日の続き

総称関数が暗黙的に大域定義されるという話なのだが、昨日のアイデアを元に直してみた。現在のHEADでは以下のようにしても大域には定義されない。
(import (rnrs) (clos user))

(let ()
  (define-generic foo)
  foo)
foo ;; -> &undefined
define-genericは今まで無条件に大域に束縛を挿入していたが、現在はトップレベルで定義された際のみとしている。これは別に難しいことではなかったので割愛(実現するのに他の不具合を直す必要があったが)。

問題はdefine-methodである。現状ではほぼうまく動くのだが、以下のような使い方をすると動かない。
(import (rnrs) (clos user))

(let ((foo 'foo))
  (define-method foo (o) o)
  (print (foo 1)))
;; -> error
define-methodが局所定義された際には局所定義された総称関数をまず探し、なければ大域定義されたものを探すという手順を取っている。そして両方とも見つからなかったらdefine-genericを挿入する。ちなみにここで挿入されたものは局所定義になるので、大域には定義されない。上記の例がうまく動かないのは、メソッド名と局所変数名が同一だから。マクロ展開は当然コンパイル時に行われるので、同名の変数を探すことはできるが、その変数が何を指しているかというのは、指しているものがリテラルである場合を除き、実行時まで分からない。この使い方をすることはそうないだろうと踏んで、現状ではこれで妥協することにした。何か妙案が浮かんだ時にまた直すかもしれない。(どうでもいいが、投げられるエラーが&assertionなのはおかしい気がしてきた。少なくとも&errorじゃないと…)

これとは直接は関係ないのだが、変数名の重複をチェックするようにした。以下のようなものが動なる。
(let ((a 1) (a 2)) a) ;; -> error
(let (("a" 1)) 1)     ;; -> error
もともと単にサボっていただけなのだが、総称関数が以下のように定義された際に混乱を招きそうだったので:
(let ()
  (define foo)
  (define-generic foo)
  (define-method foo (o) o)
  (foo 1))
;; ???
そもそもエラーなので何が起きても問題ないんだけど、変な混乱を招くよりはコンパイラに怒られた方がいろいろ楽な気がしたというのが本音。

完璧な解決ではないが、メソッドの局所定義とか(個人的には)やらないだろうし、9割くらいの混乱を未然に防げるんじゃないかなぁ。

2016-08-23

Implicit generic function creation

define-method would create a generic function implicitly if there's none defined yet. It's convenient and I've written libraries (probably only one) depending on this behaviour. (c.f. (binary data))

Convenience would usually be a trade-off  of consistency, at least in my case. For example, this is a long standing bug (though, I've just issued):
(import (clos user))

(let ()
  (define-generic foo))
foo
;; -> should be &undefined
This is because define-method would create a generic function during macro expansion, and it would be an unexpected result in this case if it didn't:
(begin
  (define-generic foo)
  (define-method foo (o) #t))
In this case, define-method should not make implicit generic function, but macro expansions are done in the same compilation time as define-generic. Thus, it's impossible to know if it should create or not. To let define-method know it shouldn't, define-generic also inserts binding into current environment (a library) during macro expansion.

Can't I do better? Creating global binding during macro expansion is rather ugly, but I don't I can get rid of it (or maybe the future?). Yet, I think I can avoid to create unwanted one like above example. It's still just an idea but if define-generic and define-method can see if they are used in a scope, then it seems there's a way. Since Sagittarius has current-usage-env and current-macro-env procedures, it is possible to access compile time environment during macro expansion. Thus, it should even be able to detect whether or not define-method should create an implicit generic function or not.

This should work, let's see.

2016-08-22

Cトランスレータ

ふとスタンドアロンのバイナリができるといいかなぁと思ってこんなものを書いてみた(使うには0.7.8のHEADが必要)。以下のように使う:
$ ./scheme2c -o out.c foo.scm
$ gcc `sagittarius-config -L -I -l` -O2 out.c
中身はほぼなんでもいいんだけど、引数を受け取るにはSRFI-22のmainがないとたぶんうまいこと使えないはず(command-line手続きで引数が取れない)。 ちなみに出来上がりCファイルは超巨大になる可能性がある。参考までに、このスクリプト自信をCに変換したら45MBのファイルになった(64bit環境)。ファイルが巨大になるのはこのスクリプトが何をやっているかを見ればすぐにわかるのだが、端的に言うとキャッシュファイルを引っ張ってきてCのバイト列にしてるから。

なんでこんなものを書いたかというと、特に理由はないんだけど、バイナリ一個で動くといいかなぁと思ったから。今のところランタイムとして最低でも DLL か .so (OSXなら .dylib) がいるがこの辺はそのうち気が向いたら何とかする予定。

キャッシュをそのままダンプしているので、性能的なメリットは一切ない。強いて言えば多少ファイルアクセスが減るくらい。今のところsagittarius-configは Windows 版にはつけてないので VC でバイナリを作りたい場合は多少の工夫が必要。ちなみに、インストール時にパスが決まるからインストーラでやらないといけないというのがついてない理由。

作っておけば気が向いたときに改善されていくのではないかというメソッドなので、しばらく実用にはならない可能性が高い。

2016-08-11

不要レジスタの除去とSchemeコード

VMにレジスタを追加するとスレッドセーフなパラメタと同様な感じで使えるということがあり、SagittariusではVMにいくつかマクロ展開器用のレジスタを持たせていた。あまりいい手ではないし、無駄にVMのサイズを増やすことになるのでいつかは何とかせねばと思いつつもかなりの期間放置していた。っが、最近いい方法を思いついたのでえいや!と除去。VMのサイズが5ワード減って752バイト(64ビット環境)になった。焼け石に水もいいところである。

【やったこと】
基本的には非常に簡単で、VMのレジスタをScheme側でパラメータ化してそれらを使っていたCの実装を全てScheme側に移動させただけ。Scheme側といってもプレビルドされているものなので、本体サイズが小さくなるということは残念ながらない。単にVMのサイズが多少減るのと、自己満足度が多少上がっただけである。

言うは易し行うは、キャッシュのせいで、多少難かった。除去したVMレジスタはマクロ展開器ようにしぶしぶ追加したもの。こいつのせいでマクロのキャッシュが無駄に複雑になっていた(今でも不必要に複雑だが)。SchemeのパラメータをCから呼び出すということは可能な限り避けたいと思ったので、マクロ展開器に関するコードをごそっとScheme側に移動させる必要があった。そうすると、Cで作られた展開器と密接につながっていたキャッシュの読み出しと書き出しが壊れる。キャッシュ機構自体が無駄に複雑なので面倒なデバッグに突入。後は気合でって感じだった。

これによるパフォーマンスの低下があるかなぁと思ったけど、顕著に表れるようなものはなかったのでよし。

【Schemeコードの混在】
VMのレジスタにはリーダーマクロやR7RSのincludeのためにあるものもあった(取っ払ってやった、更に2ワード減ったぜ)。こいつらはコンパイラが依存していたり、load手続きが使用していたりするので、単純にプリコンパイルされたSchemeに放り込むことができなかった。気合でパラメータ関連をCで書いて何とかするという手もなくはなかったんだけど、年を取ると楽な方に逃げたくなる。ということで、スタブファイル内にSchemeコードが書けるようにしてみた。

Schemeコードのプリコンパイル自体はすでにあるのだから、ちょっと手を入れればいけるだろうと思って手を入れてみたら動いたという感じ。残念ながらCで書かれた手続きからSchemeの手続きを呼ぶことはできないし、SchemeからCの関数を直接呼び出すこともできない。それでも、混在可能というのは非常に楽である。依存関係があるので純粋にSchemeで書くより多少気は使うものの(ちなみにマクロは使えない)、Cでごにょごにょやるより遥かに楽である。これを使って(sagittarius)ライブラリ内に簡易パラメータを作り、load周りのVMレジスタをそいつで実装。それに伴って関連するCのコードをごそっと消してやった。すっきり。

流石にこれはパフォーマンスに影響がでて、例えば(rfc http)のように大量に他のライブラリ(数えたら131個あった)に依存するものをキャッシュなしで読み込むと大体10~15%程度パフォーマンスが落ちた。Cでは手続き内でやっていた処理がScheme側に移動したことで手続き呼び出しに変わったこと等によるオーバーヘッドだろうなぁとは思っているものの、まぁしょうがないか。キャッシュになってさえいればほぼ変わらないので(キャッシュはCなので当たり前だが)、初回起動のみが遅いと思えばそこまで気にすることでもないかなぁ。そもそもコンパイルとマクロ展開が遅いでそっちを先に何とかしないとという話である。(text sql)のコンパイルとか環境によっては10秒かかるし…2000行以上にわたるマクロを10秒で展開すると思えばそこまで悪くないともいえるのか?っがコンパイル待ってる間にコーヒー飲み終わる勢いなのは流石になぁ…

この調子でVMの不要もしくはあってほしくないレジスタを削除していきたいところである。

2016-08-03

WebSocketクライアント

連投の二つ目

なんとなくやる気とか刺激とか取り戻すためにWebsocketのライブラリを書いてみた。WebSocketはRFC6455で定義されているプロトコル(詳細はRFC読むべし)で、実装もそんな大変そうでもないので書いてみた。

書いてる途中でSaitoAtsushiさんの実装の存在を思い出してライブラリの名前を確認したら、(rfc websocket)とまるかぶりだった。Pegasus用のformulaまで書いていただいているのにこのままぶつけるのもなぁと思い確認してみたところ
とのことだったので、遠慮なくぶつけさせていただいた。他の名前の候補としては、(rfc :6455 websocket)とか(rfc websockets)(Cのlibwebsocketsに倣って)とかあったけど、「普通の名前」(RFCの名前)を使うことにした。

簡単な使い方。
(import (rnrs) (rfc websocket))

;; Creates WebSocket object
(define websocket (make-websocket "wss://echo.websocket.org"))

;; Sets event handlers
(websocket-on-open websocket
  (lambda (ws) (display 'CONNECTED) (newline)))
(websocket-on-text-message websocket
  (lambda (ws text) (display text) (newline)))

;; Connects to the server
(websocket-open websocket)

;; Sends a message
(websocket-send websocket "Hello")

;; Close it
(websocket-close websocket)
ユーザーレベルAPIは基本的にWebSocketオブジェクトを返すので、以下のようにも書ける。
(websocket-close 
 (websocket-send 
  (websocket-open 
   (websocket-on-text-message
    (websocket-on-open (make-websocket "wss://echo.websocket.org")
     (lambda (ws) (display 'CONNECTED) (newline)))
    (lambda (ws text) (display text) (newline))))
  "Hello"))
どっちがいいかは好みだろうけど(流石に下のはあまり使わないか?)。ドラフトのまま絶賛放置中(期限切れてるから破棄されてるの?)のWebSocket over HTTP/2にも頑張れば対応できるようにはしてある(プラグイン書くだけ)。

すでにあるライブラリにぶつけにいったということもあり、例外とかかなり頑張って作っている。こんなに例外階層作って、しかも例外ハンドリングをまじめにやったのってたぶん初めてじゃないかなぁ。ライブラリ自体の構成は割とスタンダードで、ユーザーレベルAPI、中間レベルAPI、低レベルAPIという感じになっている。低レベルAPIはサーバー書くときに便利に使え(現状ではサーバーをどうするかあんまり考えていない)、中間レベルは何かしらプログラム的にやるのに、ユーザーレベルはJavaScriptのWebsocketみたいな感じで使える。

作って2日なので、作りこみが足りない部分はあるかもしれないが、簡単なチャットサーバークライアントみたいなのは作れたので紹介してみた。

例外ハンドリング

連投の一つ目。

一つ前の記事guardの例外の再送出をwith-exception-handlerで受けると無限ループに陥る問題を解決した話。結論を先に書くと、raiseraise-continuable及びwith-exception-handlerをSchemeで実装して、継続の境界を作らないようにした。

ぼ~っと考えて実装したら動いちゃった系の解決方法で、特に苦労とかなかったんだけど、実装前に気になっていた点が以下:
  • Cでwith-exception-handlerを使っているか
    • 使ってなかった。なんでこれC側にあるんだろう状態だった。
  • C側で例外投げたらどうなるの
    • この記事の肝、気になったら続きを読んで。
一つ目は特筆することもなく。Cで書くと複雑怪奇になるんだけど(なってた)、使ってないしSchemeに移動させてコードがかなりすっきりした。VMのサイズも1ワード減っていい感じだと思われる。(core)ライブラリだけでは使えなくなったけど、これに依存するコードはないと思うのでまぁ、問題ないだろう。

二つ目はC側のコールスタック。継続の境界はSg_Apply系の関数で作られるんだけど、コールスタックの深いところで例外が投げられたらどうする?ってのをぼ~っと考えていた。はい、longjmpを使うだけでした。

具体的にはこんな感じで例外が投げられたとする。
Call stack
  +----------+  +---------+  +---------+  +---------+
--| Sg_Apply |--| C func1 |--| C func2 |--| C func3 |
  +----------+  +---------+  +---------+  +---------+
                                            ^^^^^^^
                                             C error
こんな感じでCのraiseは呼ばれた時点でVMのスタックにSchemeのraiseを呼び出す継続フレームを入れる。
Before
   PC = CALL
   Stack
   +--------------------------+
   | Return to previous frame |
   +--------------------------+
                :
After
   PC = RET
   Stack
   +--------------------------+
   | Return to calling raise  | --> PC to return = CALL raise
   +--------------------------+
   | Return To previous frame |
   +--------------------------+
                :
with-exception-handlerraise-continuableの組み合わせだと、呼び出し元に戻る必要があるので一つ前のフレームを飛ばすわけにはいかない。この状態にしておいて、longjmpを呼び出し、VMのループを再起動する。もともとVM自体はVMループへのjmpbufを持っているのでそれを使うだけ。割とお手軽に解決できてしまった。

このバグのおかげで別のバグをつぶすこともできたし、YpsilonとMoshのバグを発見することもできたのでいいバグ(?)だった。

2016-07-29

Exception handling in C world

The following piece of code goes into infinite loop on Sagittarius.
(import (rnrs))
(with-exception-handler
 (lambda (k) #t)
 (lambda ()
   (guard (e (#f #f))
     (error 'test "msg"))))
I couldn't figure it out why this never returned at first glance. And it turned out to be very interesting problem.

The problem is related to continuation boundary and exception handlers. If you print the k, then only the very first time you'd see error object with "msg" after that it'd be "attempt to return from C continuation boundary.". But why?

This happens when you capture a continuation and invoke it in the different C level apply. Each time C level apply is called, then VM put a boundary mark on its stack to synchronise the C level stack and VM stack. This is needed because there's no way to restore C level stack when the function is returned. When a continuation is captured on the C apply which is already returned, then invocation of this continuation would cause unexpected result. To avoid this, the VM checks if the continuation is captured on the same C level apply.

Still, why this combination causes this? The answer is raise is implemented in C world and exception handlers are invoked by C level apply. The whole step of the infinite loop is like this:
  1. guard without else clause captures a continuation.
  2. When error is called, then guard re-raise and invoke the captured continuation. (required by R6RS/R7RS)
  3. Exception handler is invoked by C level apply.
  4. VM check the continuation boundary and raises an error on the same dynamic environment as #3
  5. Goes to #3. Hurray!
There are 2 things I can do:
  1. Create a specific condition and when with-exception-handler received it, then it wouldn't restore the exception handler. [AdHoc]
  2. Let raise use the Scheme level apply. (Big task)
#1 probably wouldn't work properly. #2 is really a huge task. I need to think about it.

2016-07-12

リモートREPLとライブラリ依存関係

最近ちょっとしたツールを作るのにPaella(に付属しているPlato)を使っているのだが、リモートREPLの問題とリロードの問題が面倒だなぁと思ってきたのでちょっとメモ。

リモートREPLの問題

これは非常に簡単で#!read-macro=...のようなのが送れない。問題も分かっていて、#!から始まるリーダーマクロは値を返さないで次の値を読みにいく。マクロはリーダー内で解決される。スクリプトや通常のREPLなら特に問題ないんだけど、それ自体を送りたい場合にはあまり嬉しくない。解決方法はぱっと思いつくだけで以下:
  • リモートREPL用のリーダーを作る
    • 面倒
  • リモートREPL用ポートを作って、リードマクロを読ませる
    • アドホックだけど、悪くない気がする
一つ目のは既存のリーダーマクロ機構をどうするんだ?という話になるので、最後の手段にしたい(作れば確実に動くのは分かっているので)。二つ目は何とかいけそうな気がしないでもないんだけど、ソースポート(この場合は標準入力ポート)まで影響が出るかが疑問(出ない気がしてる)。そもそもソースポートにまで影響はでる必要はない気もするなぁ。試してみるか。

ライブラリ依存関係

Platoを使う最大の理由はREPLでリロードができるからなんだけど、ハンドラ(と呼んでいるライブラリ)が依存しているライブラリを変更した際に上手いことその変更を反映する方法がない。ハンドラであればリロードが可能なのだが、依存ライブラリだとロードパスの問題とかも出てきて嬉しくない。手動でloadを呼ぶとか、コード自体をリモートREPLに貼り付けるとか(上記の問題が出ることもあるが)方法がないこともないけど今一面倒。
依存関係の子に当たる部分を親が解決できればなんとかなりそうなんだけど、現状の仕組みでは子が親を探すことができても親は子を知る術がない。突き詰めていくとincludeされたファイルの変更は追跡できないとかあるし。
あるとよさそうなものとして、
  • ライブラリファイルの変更を検知したらリロードする機構
  • 依存関係の親が子を知る手段
かなぁ。一つ目はそういえばファイルシステムの監視機構を入れたからやろうと思えばやれなくもないのか(自動監視だと任意のタイミングでやれないから微妙かな)。二つ目はC側に手を入れてやればやれるけど、必要な場面がかなり限定されているので単なるオーバーヘッドにしかならない気がするなぁ(メモリも喰うだろうし)。こっちはかなり考えないとだめっぽい。いいアイデア募集。