2016-09-19

Scheme Workshop 2016 奈良

行ってきた。朝一で奈良入りでもいけなくはなかった気がしないでもないが、せっかくだしということで奈良に2泊3日してきた。奈良の観光の話でもいいけど、流石にどこも回れなかったのでワークショップの話。

前日の夜にAlexからスケジュールの変更のメールが届く。発表者二人が飛行機に乗り遅れたので、その二人を最後に回すため。結局間に合わずWillとKathyによりカラオケスライドメソッド(後述)が発動した。

ホテルから徒歩15分という距離なのに9時15分のオープニングに間に合わず。油断しすぎでした。

【招待講演1】
プログラムの正当性を検証するプログラムにLispを使ったという話(だと思う)。スケジュールが移動して自分の発表が一発目になったのでそれに意識が行き過ぎてたから話が頭に入らなかった…これ聞きながら、今年のはこんなにアカデミックなのかぁとものすごく緊張した記憶しかない。

【自分の】
そのうちスライド挙げます。単にライブラリの紹介。

【Nash: a tracing JIT for Extension Language】
GuileにトレーシングJITを実装したという話。プログラムで使用される時間の大部分はタイトなループによって発生しているということに注目したJITらしい。本家にマージされるかは不明らしい。されてほしいような、されてほしくないような(Sagittariusが選ばれる可能性が下がるという意味で)。

【Ghosts in the machine】
現在のプログラミング環境はコンピュータ黎明期と比較して劣っている、ということをClojureのREPLを例にして示す話。時間内に終わらなかった発表一つ目。休憩中に発表者に質問してどこを目指しているのか質問して聞いたりしていた。視点としては面白いし、一意見として終わらせるには惜しい気がするけど、何から始めるといいんだろう?となるくらいには壮大なビジョンだった。

【R7RS update】
AlexによるR7RSの近況。まだ見ぬSRFI-142とSRFI-143が並んでいたのでArthurで止まっているのか、Johnがまだ提出してないのかは謎。Red Docketは終わったらしいのだが、正式な発表はまだされてない気がするけど、c.l.sで見逃したかな?

【招待講演2】
Guixという比較的新しいパッケージマネージャの話。インストール履歴をリビジョンで管理しているのでうっかり何かを壊しても動くリビジョンに戻せるというのが他のパッケージマネージャとの大きな違いかな。後はGuileで書かれているのでパッケージの定義もS式(Guileで動くプログラム)というのも大きな特徴かな。

【Function compose, Type cut, And the Algebra of logic】
発表者のコミュニケーション能力があまり高くなかったので何が何だかさっぱり分からなかった。ただ、発表資料自体は面白いことが書いてあったので、論文を後で読むことにする。

【Multi-purpose web framework design based on websocket over HTTP Gateway】
SagittariusにWebsocketを入れたこともあり一番気になってた発表なんだけど、今一発表が雲を掴む様な感じでよく分からなかった。また、コミュニケーションの問題も多少あり、納得のいく答えも得られず。後で論文を読む。

ここからカラオケスライドメソッドが発動する。ちなみに、カラオケスライドとは自分が作ったスライドではないものを発表するもと思えばよい。命名はWill。日本のカラオケが流れてくる文字を歌うことに引っ掛けた上手い名前だと個人的には思った。

【miniAdapton: A Minimal Implementation of Incremental Computation in Scheme】
AdaptonというMemoriseのテクニックに一つをSchemeで実装した話。入力ツリーの一部が変更されても共通部分は再利用しているような感じだった。リポジトリも公開されてるし、ソース見た方が早いかな。しかし、代理の発表(論文の共著者であるが) なのにえらくうまいことやるなぁと前回見た時も思ったなぁ。あれくらいうまくしゃべれるようになりたい(なんか違う)。

【Deriving Pure, Functional One-Pass Operations for Processing Tail-Aligned Lists】
リストの共通サフィックス部分を調べるスクリプトをエレガントに書いたという話。ベンチマークがないのでこれが実際にどこまで効くのかは微妙。ナイーブな実装、エレガントな実装ともにO(N)なので、コンスタントの部分だけなのだが、正直論文の実装だとヘルパー手続きの作成にかかるコストの方が高い気がしないでもない。まぁ、コードは論文に載っているので手元でベンチマークとってJasonにメール投げてみればいい話な気がする。

どうでもいいのだが、僕が喋る英語はオランダ語訛りらしい(Arthur談)。どうも子音の発音がネイティブに比べて強いのだそうだ。普通母語に引っ張られるが、第三言語(第二が英語)に引っ張られるのは珍しいんじゃないの?という話をしていた。確かに寡聞にして聞かない話ではある。

2016-08-30

ログ

そういえばSagittariusにはずっとログを吐き出すためのライブラリがないということをふと思い出した。附属させてるライブラリがログを吐き出すのはさすがにどうかと思うのであんまり考えてなかったのだが、Paellaみたいなのが何のログも吐かないというのはいろいろ面倒だなぁと思ってはいた。

あまりいいデザインというのも思い浮かばないんだけど、なんとなくこんな感じのロガーがあればいいかなぁと思い30分くらいで作ってみた。こんな感じで使える。
(import (srfi :18) (util logging) (util file))

(define (print-log logger)
  (trace-log logger "trace")
  (debug-log logger "debug")
  (info-log logger "info")
  (warn-log logger "warn")
  (error-log logger "error")
  (fatal-log logger "fatal")
  (terminate-logger! logger))

(print-log (make-logger +info-level+ (make-appender "[~l] ~w4 ~m")))
(print)
(print-log (make-async-logger +debug-level+ 
         (make-appender "[~l] ~w4 ~m")
         (make-file-appender "[~l] ~w4 ~m" "log.log")))

(print (file->string "log.log"))
#|
[info] 2016-08-30T16:02:29+0200 info
[warn] 2016-08-30T16:02:29+0200 warn
[error] 2016-08-30T16:02:29+0200 error
[fatal] 2016-08-30T16:02:29+0200 fatal

[debug] 2016-08-30T16:02:29+0200 debug
[info] 2016-08-30T16:02:29+0200 info
[warn] 2016-08-30T16:02:29+0200 warn
[error] 2016-08-30T16:02:29+0200 error
[fatal] 2016-08-30T16:02:29+0200 fatal
[debug] 2016-08-30T16:02:29+0200 debug
[info] 2016-08-30T16:02:29+0200 info
[warn] 2016-08-30T16:02:29+0200 warn
[error] 2016-08-30T16:02:29+0200 error
[fatal] 2016-08-30T16:02:29+0200 fatal
|#
ロガーがログレベルと同期をコントロールして、アペンダーが実際にログを吐き出す。どこかでみたことあるようなモデルではある。まぁ、本職はその言語を使うのでなんとなく似通ったのだろう。make-appenderでつくられるアペンダーは標準出力(正確にはcurrent-output-portが返す値)に吐き出す。アペンダーの第一引数はログのフォーマット。現状手の込んだ出力はできないが、当面はこれでも問題ないだろう。ちなみに、~wの後ろに続く4はSRFI−19で定義されているフォーマットの一つ。現在は一文字しかみないが、そのうちなんとかするかもしれない。

make-async-loggerはスレッドを一つ消費する代わりにログの書き出しをバックグラウンドでやってくれる。アペンダーが複数あったり、処理が重い(メール送るとか) 等あるときに役に立つと思う。

とりあえずこれを適当に使ってるスクリプト等に組み込んで使用感を確かめていくことにしよう。

2016-08-29

Ephemeron and reference barrier

Recently, there's the post on SRFI-124 ML about reference barrier. The SRFI doesn't require reference-barrier procedure due to the non-trivial work to implement. Now, there's a post which shows how to implement portably, like this:
(define last-reference 0)
(define (reference-barrier x)
  (let ((y last-reference))
    (set! last-reference x)
    y))
It seems ok, but is it? The SRFI says like this:
This procedure ensures that the garbage collector does not break an ephemeron containing an unreferenced key before a certain point in a program. The program can invoke a reference barrier on the key by calling this procedure, which guarantees that even if the program does not use the key, it will be considered strongly reachable until after reference-barrier returns.
Due to the lack of knowledge and imagination, I can't imagine how it should work precisely on like this situation:
(let loop ()
  (when (some-condition)
    (reference-barrier key1)
    (reference-barrier key2)
    (do-something-with-ephemerons)
    (loop)))
Should key1 and key2 be guaranteed not to be garbage collected or only the last one (key2 in this case)? If the first case should be applied, then the proposed implementation doesn't work since it can only hold one reference. To me, it's rather rational to hold multiple reference since it's not always only one key needs to be preserved. However if you extend to hold multiple values, then how do you release the references without calling explicit release procedure? If the references would not be released, then ephemerons would also not release its keys. Thus calling reference-barrier causes eternal preservation.

Suppose this assumption is correct, then reference-barrier should work like alloca with automated push so that the pushed reference is on the location where garbage collector can see them as live objects. In this sense, allocated references are released automatically once caller of reference-barrier is returned and multiple references can be pushed. Though, it's indeed non-trivial task to implement. I hope there's no errata which says reference-barrier is *not* optional, otherwise it would be either a huge challenge or dropping the support...

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の不要もしくはあってほしくないレジスタを削除していきたいところである。