Syntax highlighter

2015-05-23

互換レイヤを書く

R6RS処理系の過半数(6個)についてFFIの互換レイヤを書いたので(Larcenyはまだテストが通らないけど)、今後のためにどういうことを気をつければいいかを記しておく。要するに愚痴である。

ドキュメントを当たる


まぁ、超基本である。ここだけで済むのであれば優秀なドキュメントを持っていると言える。互換レイヤを書くということは、言い換えると処理系依存の機能を同一APIに落とし込むということなので、まずはターゲットとしている処理系がほしい機能を備えているかを調べる。ここで見つけられなかったら諦めるという手もある。

ちなみに、今回ここだけで済んだ処理系はRacketとGuileのみである。この2つはドキュメントがかなり優秀といえる。(GuileはどうやってFFIのライブラリをロードするのかがドキュメントに書いてなかったけど・・・)

Schemeで書かれたソースを当たる


Schemeで書かれたソースは大体どこかに付属しているものである。たとえバイナリ配布されているものであったとしてもである(例:Sagittarius、Larceny)。明文化されていないとはいえ機能自体を持っているということは割りとよくある話で、そういう場合は今後後方互換性が損なわれる可能性があることを考慮にいれつつ書く必要がある。まぁ、変わったら泣く覚悟が必要という話である。

Schemeで書かれたソースも処理系によって大分違う。例えば、Mosh、Vicare、Sagittariusは基本的にライブラリ形式なので見つけてしまえばそのままライブラリを呼ぶことができる。Larcenyは多少違って、ライブラリ外の手続き・マクロは(primitives foo ...)のようにしてやる必要がある。これはvan Tonderのマクロで共通なのでNMoshもこの形式である。

今回ここまでで済んだ処理系はVicareであった。まぁ、VicareはFFIの機能的に多少物足りなかったのでなんとかならんかなぁとCソースまで覗いたが。

Cで書かれたソースを当たる


正直ここまで来たら諦めた方がいいレベルである。処理系によっては全くどこにも書かれていないが利用できる機能というものがある。具体的にはMoshのbytevector-pointerである。まともな感覚で書かれたものであれば、大体機能ごとにまとまっているものなので適当にファイル名からあさるという手がある。Mosh的にはFFIProcedures.cppという名前がずばりという感じであったので覗いたら見つけた。ファイル名から見つけるのはソースが一箇所に固まっているとやりやすいがそうではない場合もある(具体的にはLarceny)。そういう場合は以下のような古典的な方法を使ったりする。
find . -name '*.c' | xargs grep 'keyword'
探したいファイルの拡張子は適当に変える必要があるかもしれない。今回はFFI関連だったので、pointerとか
ffiとかがよく使われた。
Larcenyはソースがいろいろなところに配置されていたり、ドキュメントではなくREADMEにAPIの使い方が書いてあったり(具体的にはlib/Ffi/README)と手当たり次第当たる必要があった。

Schemeオブジェクトのメモリ配置に依存したコードを書く


ここまでやりだしたら正直いろいろ考え直した方がいいレベルである。Larcenyにはバイトベクタからポインタを作る手段がない。Vicareはバイトベクタをコピーする不便は振る舞いをするがそれでも存在したのであるが、Larcenyでは存在すら確認できなかった。偶然にもffi/handle->addressというものを発見したのでその振る舞いを確認。こいつは最終的にsrc/Rts/Sys/primitives.cに定義されているprimitive_object_to_addressが呼ばれることを確認し、この関数は与えられたオブジェクトからタグを取り除いたものを返すという振る舞いをすることが分かった。そうすると、バイトベクタの構造を知ってしまえばその要素がどのように配置されているかが分かる。いくつかのソースを覗いてbytevector_refというものが多用されているのを見つけて、その定義まで飛ぶ。include/Sys/macros.hで定義されているのだが、ここからLarcenyは構造体などという優男が使うようなものは使用しておらず、メモリのオフセットを直接弄るという男らしい方法をとっていたことを知る。最初の1ワードはサイズを格納して、残りは要素という感じになっているので、上記のScheme手続きで得られるアドレスにポインタのサイズを足した分をポインタとすることにした。

いい悪いは別にして、こんな超が付くレベルの危険な操作も可能にしているのは「何かしら打つ手がある」という希望があるので個人的には好きである。(この機能は必要だったのでSagittariusにもあったりはするが。)

まとめ


月並みな言葉になるが、ドキュメントは重要である。今回分かったのはユーザー視点で見ればRacketレベルのドキュメントはとてもありがたく、Mosh、Larcenyレベルのドキュメントは涙が出るということであった。VicareはなぜかFFIの項目だけやる気がないのでそれもどうかと思ったが。

後は、Chez、IronSchemeとYpsilonをやればR6RS処理系を網羅したライブラリになるのだが、正直もうやりたくないです感が自分の中に漂っている。

2015-05-20

Introduction of Portable Foreign Function Interface (pffi) library

I think it has kinda fixed for API wise, so let me introduce Portable Foreign Function Interface (pffi)

The library is written mostly R6RS portable. Of course, it's impossible to write FFI without implementations' support so it just provides some of greatest common interfaces. One of the purpose is that if you want to write bindings written in C for R6RS Scheme, you always need to refer FFI APIs per implementations. This is pain in the ass. Most of the R6RS implementations provide the way to write compatible layer, so if there is an abstraction layer then users can write portable code without the pain. (don't ask me, how many people want to write portable code.) Currently the following implementations are supported:

  • Sagittarius (0.6.4)
  • Mosh (0.2.7, only SRFI Mosh, so called NMosh)
  • Vicare (0.3d7)
  • Racket (6.1.1, plt-r6rs)
  • Guile (2.0.11)
This is more than 50% of R6RS implementations which support FFI, so I think I'm allowed to call it portable.

How to use


Suppose you have the following useful function written in C.
int plus(int a, int b)
{
  return a+b;
}
Very useful isn't it? Now it's compiled to libtest.so. Then the Scheme code which uses this C function would look like this:
#!r6rs
(import (rnrs) (pffi))

;; load C library
(define lib (open-shared-object "libtest.so"))

;; load C function
(define plus (foreign-procedure lib int plus (int int)))

;; loaded C function can be called as if it's Scheme procedure.
(plus 1 2) ;; => 3
This code works for all implementations listed above. Simple, easy, isn't it?

Callback


If a C function requires function pointer such as quicksort, then you want to write it in Scheme. Suppose our quicksort has the following signature:
int quicksort(void *base, const size_t num, const size_t size,
              int (*compare)(const void *, const void *));
The first one is the array of elements you don't know the size, the second one is the number of the elements, the third one is the size of an element, then the last one is comparison function. To use this in Scheme, then you can write like this:
;; suppose this is in libtest.so
(define qsort
  (foreign-procedure lib int quicksort
     (pointer unsigned-long unsigned-long (callback int (pointer pointer)))))

(let ((callback (c-callback int
                            ((pointer a) (pointer b))
                            (lambda (a b)
                              (let ((ia (pointer-ref-c-uint8 a 0))
                                    (ib (pointer-ref-c-uint8 b 0)))
                                (- ia ib)))))
      (bv (u8-list->bytevector '(9 1 2 8 3 7 4 6 5))))
  (qsort (bytevector->pointer bv) (bytevector-length bv) 1 callback)
  (free-c-callback callback)
  (bytevector->u8-list bv));; => (1 2 3 4 5 6 7 8 9)
It's slightly uglier than the plus since you need to specify the callback procedure's types twice (if you want to write portable thing, sometimes this kind of things are inevitable). Some implementations doesn't free callback either, so you need to release it explicitly with free-c-callback procedure (of course, if the callback is created globally, then you don't have to since it's bound forever).

Global variables


I'm not sure if you want to handle this kind of code, but sometimes it's inevitable. Suppose your C library exports the following variable:
int externed_variable = 10;
Now, you need to get this value and modify this value from Scheme world. You can do like this:
(define-foreign-variable lib int externed_variable)
;; can also be written to specify the binding name
;; the name is converted to Scheme way if the macro is only given 3 arguments.
(define-foreign-variable lib int externed_variable global-variable)

externed-variable ;; => 10
global-variable   ;; => 10

;; this overwrites the value of C world
(set! global-variable (* global-variable 10)) ;; unspecified
global-variable   ;; => 100

;; so if the address is shared, then it's got affected.
externed-variable ;; => 100
I hope there is no actual use case for this but it's always good to have some workaround.

C Structure


Most of C functions requires pointer(s) of structure. C's structure is mere chunk of memory so you can simply pass a bytevector and get its value calculating offset/padding of the structure. But this is kinda pain in the ass. This library provides define-foreign-structure macro which is pretty much similar with define-record-type and calculates padding/offset for you.

Suppose you have the following C structure and its operations:
struct st1
{
  int count;
  void *elements;
};

struct st2
{
  struct st1 p;
  short attr;
};

static int values[] = {0,1,2,3,4,5,6,7,8,9};

#define CONST 1L
#define INT_ARRAY 1L<<1;

void fill_struct(struct st2 *s)
{
  s->p.count = sizeof(values)/sizeof(values[0]);
  s->p.elements = (void *)values;
  s->attr = CONST | INT_ARRAY;
}
To use this, you can write like this:
(let ()
  (define-foreign-struct st
    (fields (int count)
            (pointer elements)))
  ;; either way is fine
  (define-foreign-struct st2
    (fields (st p)
            (short attr)))
  ;; if the first member of struct is a struct
  ;; then you can also use 'parent' clause
  (define-foreign-struct st2*
    (fields (short attr))
    (parent st))

  (let ((st  (make-st2 (make-st 0 (integer->pointer 0)) 0))
        (st* (make-st2* 0 (integer->pointer 0) 0))
        (fillter (foreign-procedure lib void fill_struct (pointer))))
    ;; created struct is mere bytevector
    (fillter (bytevector->pointer st))
    (fillter (bytevector->pointer st*))
    ;; accessors are just accessing calculated offset
    (st-count st) ;; => 10
    ;; so this is also fine
    (st-count (st2-p st)) ;; => 10
    (st2-attr st) ;; => 3
    ;; this can also work. NB different accessor
    (st2-attr st*) ;; => 3
    (st2-p st) ;; => bytevector
    ))
parent might look weird since there is no hierarchy mechanism on C struct. But in practice, you see a lot of code which uses this kind of technique to emulate sub class thing. So I thought it might be useful. If you don't want to use it, you don't have to. You can also specify the struct member.

You might not want initial value for structures, then you can also use protocol like this:
(let ()
  (define-foreign-struct st
    (fields (int count)
            (pointer elements))
    (protocol
     (lambda (p)
       (lambda (size)
         (p size (integer->pointer 0))))))
  ;; either way is fine
  (define-foreign-struct st2
    (fields (short attr))
    (parent st)
    ;; child must have protocol if the parent has it
    (protocol
     (lambda (p)
       (lambda ()
         ((p 0) 0)))))

  (let ((st  (make-st2))
        (fillter (foreign-procedure lib void fill_struct (pointer))))
    (fillter (bytevector->pointer st))
    ;; accessors are just accessing calculated offset
    (st-count st) ;; => 10
    (st2-attr st) ;; => 3
    ))
The protocol is just the same as define-record-type's one. So the same rules are applied.

The define-foreign-struct also creates size-of-struct-name variable which contains the size of the structure. So you don't have to allocate memory to know the size.

What can't do


  • Currently, there is no way to pass address of pointers.
  • Union is not supported.
  • Bit field is not supported.
Probably many more, but I think it can still cover basic usages.

As usual, your pull requests / feedbacks are always welcome.

2015-05-18

FFI library comparison for R6RS implementations

I'm writing Portable Foreign Function Interface for R6RS and have found some interesting things to share. Currently the library supports the following implementations and this article mentions them mainly:
  • Sagittarius (0.6.4)
  • Vicare (0.3d7)
  • Mosh (0.2.7)
  • Racket (plt-r6rs 6.1.1)
  • Guile (2.0.11)

API wise


Most of the implementations supports common procedures with different names. Only Mosh, Sagittarius and Vicare provide similar APIs. (Well, at least Sagittarius took some of the API names from Mosh, I don't know about Vicare.) Unfortunately, Mosh has much less APIs and seems incomplete. For example, Mosh doesn't have any API to convert bytevectors to pointers or APIs to set unsigned char/short/int/long to pointer. This might be critical in some cases. Vicare and Sagittarius have enough APIs to do almost everything.

Racket has interesting APIs. Almost all foreign variable need to have types.  For example, it distinguish char * and void * whilst above 3 not really do.

Guile has limited pointer operation procedure. It seems users always convert pointers to bytevectors, I think this is pretty inconvenient though. And it doesn't accept bytevector as pointer directly. So it needs to be converted by bytevector->pointer procedure.

Documentation wise


Racket provides excellent documents so I could write the library without referring its source code.

Guile provides good documents it's not so user friendly means I needed to do some try and errors to figure out how it works (especially, document doesn't provide library name. It took me some time to figure it out).

Mosh is OK document, though I also referred the source code. (because of lack of APIs, I hoped there is hidden ones).

Sagittarius is also OK document. Though, some of APIs documents are missing so it would be hard to write this library without referring the source code.

Vicare has poor document for FFI (unlikely the other documents). It just have shallow intruductions. This basically means there might be a chance that APIs would be changed. To write the library, I needed to refer the source code.

Other implementations


There are 4 more R6RS implementations which support FFI, Chez, Ypsilon, IronScheme and Larceny. These are the reasons why I didn't do it in first place:

Chez: I can only use Petite Chez Scheme but this doesn't support FFI. So to make it I need the comercial one which is not available anymore.

Ypsilon: Released version of Ypsilon has very limited APIs to create foreign functions/variables. And no document. Trunk version is far more APIs but not maintained nor released (I think it's sad but I can't help it). Just gave up.

IronScheme: .NET ... well simply not familiar to use it

Larceny: I might support, even it has good document. But there is no proper install script. So it's kinda hard to run/test.

Conclusion



I don't mean which APIs are the best or worst. Just figured out that if I want to write a portable library, then it might be better to have rather low level APIs exposed. And if low level APIs are there, then most of the concepts can be shared even they look completely different. (In this sense, Ypsilon's APIs are too high level to handle, unfortunately.)

2015-05-14

オランダで働くということ

妹からWhat's Appでオランダの労働環境的なものの質問が来て、「これはブログのネタになる」と思ったのでまとめてみることにする。法律的なことは詳しくないし、あくまで僕の経験+聞いた内容なので正確性は低いと思ってもらえるとありがたい。断定的な言葉を使っているが後ろに「と思う」とか「のはず」とかを捕捉してもらいたい。

雇用形態


オランダでは基本的に「無期限契約」か「期限付き契約」しかない。どちらも扱いは正社員という扱いになるが、後者は期限がくると契約更新がある。僕は最初の会社は「一年契約」の後に「無期限契約」になった。当然だが、ずっと「一年契約」が続くかもしれないし、契約を打ち切られるかもしれない。また、オランダでは基本的によほどのことがない限り解雇はない(あるけど、かなりの金額を労働者に払う)ので、「無期限契約」であれば懲戒免職を除き職にあぶれる心配はないとも言える。

労働時間も変更できる。基本的には週40時間だが、働き方によっては週36時間とかも可能。もちろん減らした時間分の給料は減額され、有給の日数は減ることになるがペンションプランとかに変更はない。

ちなみに、日本で言うアルバイトは存在せず、学生が行う仕事も普通に有給及びペンションプラン(25歳以上は加入必須)とかあるらしい。こういった仕事は大抵「0時間契約」になり、働いた時間分だけ給料が支払われるそうだ。

待遇


上でも述べたが、雇用契約の違いによる待遇の差というのはない。日本のパートやアルバイトのように福利厚生が一切ない雇用契約というものも基本的にはない。ただし、家族手当等の基本給を上げずに額面を挙げるとうの小細工も存在しないので、下記に述べる理由もあり、契約で決まった給料以上の給料はもらえない。ベースアップは会社にもよるが、基本は年に一回。当然だが業績の悪い年はない。

手当てではないが、交通費は基本出る。会社によっては健康保険料も出る。月に€150くらいかかるので出ると結構でかい。コーヒー、お茶は基本無料。昼食もある場合もあるが、こちらは有料になる(今の会社は仕組みがよく分からないので払ってるかは疑問だが・・・)。当然だが外に食べに行ってもよいし、弁当持参してもよい。

ちなみに、高い高いといわれている税金だが、引かれる額は大体3割である。Expatだと30%ルールというのがある。これは額面の30%には税金がかからない(丸々もらえる)というもの。残念ながら僕には適用されないので縁のない話。国外からの優秀な労働者に与えるものなので、パートナービザには適用されないのである。

働き方


基本残業はない。有給は3週間まとめて取るとか普通。戻ってきたときに仕事が山積みということも基本ない。その人のポジションによるが。2社しか働いたことないので、一般的ではないかもしれないが、金曜の夜は会社がビールを振舞ったりする(ただ酒が飲める)。

所謂「上司と飲みに行く」とか「強制参加慰安旅行」とかもない。あるけど、当然自由意志で断ることもできる。別に断ったからといって雰囲気が悪くなることもない。

人によっては副業を持つことも可能。例えば本業で8時-17時まで働いて19時-21時まで別の仕事とかもある。会社既定で禁止していることもあるので注意が必要ではある。僕の場合は決められた8時間を会社のフルにコミットできれば別に副業してもいいという話だったので、雇用契約を結ぶ前に確認した方がいい。

個人的な意見だが、日本で働いていたときより100倍は楽である。いろんな面で。

転職


これは僕自身も日本で経験したことはないのだが、職場を変えると「昨日の味方は今日の敵」になることが日本ではあるらしい。そんなものはない。そもそも、職を転々とする人が多いので(コの業界だからかもしれないが)毎回敵を作っていては身が持たないし、次は顧客として会う可能性もかなりあるのでそんなあほなことはしない。

転職自体は「新卒主義」とか全然ないのでいろいろ楽。周りを見渡しても大体転職組。


隣の芝なので青く見えるかもしれないが、個人的な意見としては労働環境だけを見れば青いと思う。まぁ、僕が日本で働いた会社がそんなによくなかっただけという話もあるかもしれないが。

2015-05-13

Breaking privacy

R6RS has a record which is much more flexible than the one R7RS provides. You can consider the R7RS one is a subset of R6RS record. One of the differences between R6RS record and R7RS record is that R6RS provides inspection layer. Using this makes us having sort of peeping Tom ability.

Scenario


Suppose you want to have a record type which is only used in the library defines the record type. Later on, you notice that it might be convenient if users can pass the record so you decided to export its constructor.
#!r6rs
(library (private-record)
    (export make-private2)
    (import (rnrs))

  (define-record-type private
    (fields field1))
  (define-record-type private2
    (fields field2)
    (parent private))

  ;; you may want to do some
  ;; private operation here 
  
  )
So far so good. It seems no one can access the record fields except the library itself. So you can have some privacy here.

Is that really so?


Actually not. You would still have peeping Tom. Let's see how we can do it.
#!r6rs
(import (rnrs)
 (private-record))

(define private2 (make-private2 1 2))
(define private2-rtd (record-rtd private2))

;; predicate
(define private? (record-predicate (record-type-parent private2-rtd)))
(define private2? (record-predicate private2-rtd))

;; get field accessors
(define (find-accessor rtd field)
  (let loop ((rtd rtd))
    (if rtd
        (let ((fields (record-type-field-names rtd)))
          (let lp ((i 0))
            (cond ((= i (vector-length fields)) (loop (record-type-parent rtd)))
                  ((eq? (vector-ref fields i) field)
                   (record-accessor rtd i))
                  (else (lp (+ i 1))))))
        (lambda (o) (error 'find-accessor "no such field" field)))))

;; parent field
(define private2-field1 (find-accessor private2-rtd 'field1))
;; record field
(define private2-field2 (find-accessor private2-rtd 'field2))

(display (private2? private2)) (newline)
(display (private? private2)) (newline)

(display (private2-field1 private2)) (newline)
(display (private2-field2 private2)) (newline)
#|
#t
#t
1
2
|#
Even though the library only exports constructor, we can still access to the fields including parent's one and checks if the object is the particular record.

The inspection layer is really convenient in some cases. Suppose you want to write a destructuring matcher which can also handle records. The essence of this kind of macro would be like the following:
(define-syntax destructuring-record
  ;; actually we don't need to put 'record' keyword at all
  ;; to show only this...
  (syntax-rules (record)
    ((_ (record r field ...) body ...)
     (let ((tmp r))
       (when (record? tmp)
         (let* ((rtd (record-rtd tmp))
                ;; definition of find-accessor is above
                (field ((find-accessor rtd 'field) tmp))
                ...)
           body ...))))))

;; use it
(destructuring-record (record private2 field2) (display field2) (newline))
If you know the field names of records, then you can write without calling predefined accessors. (Though, this would cost a bit of performance since it creates closures each time.)

How to prevent it?


If you are treating something you really don't want to show such as password (I don't argue holding password here), you just need to specify (opaque #f) in the record definition.

Caveat


R7RS or SRFI-9 define-record-type can be implemented by R6RS's one. Since R7RS's one doesn't specify record inspection, there is no way to prevent this as long as wrapper doesn't specify (opaque #f). One of the implementations made by Derick Eddington allowed to be inspected. Should this behaviour be the case for R7RS one?

2015-05-12

秘伝のタレマクロができるまで

Schemeでこのマクロ便利なんだけど、どうやったらこんな複雑なマクロ書けるんだ?と疑問に思ったことはないだろうか?ふと自分が書いているマクロが機能追加とともに巨大に(まだ小さいけど)になっていっているの(成長途中)をみて答えの一つを見た気がしたので駄文として残すことにした。

最初は小さいものだった


僕はテストはSRFI-64を使って書くことが多い。というかほぼ100%である。SRFI-64は便利なのだが、多値を扱うテストを書くAPIを標準で提供していない(と思う、真面目に仕様眺めてない、でかいし)。毎回let-valuesを書くのは馬鹿らしいので以下のようなマクロを書いた。
;; version 1
(define-syntax test-values
  (syntax-rules ()
    ((_ (expected ...) expr)
     (test-values 'expr (expected ...) expr))
    ((_ name (expected ...) expr)
     (test-equal 'expr (expected ...) (let-values ((results expr)) results)))))
非常に単純に多値をリストで受け取ってequal?で比較するだけだが、最初のうちはこれで十分だった。しかも、let-valuesを毎回書く必要もない上に、何のテストをしているのか(この場合は多値)というのが一目で分かるし、やっぱりマクロは便利だなぁ、程度で済んでいた。

リスト内の値を一つずつ比較したくなった


多値を返す手続きのテストを行っていると、どの値が失敗しているのかということが知りたくなる。そうするとリストにまとめて比較するのでは辛い部分が出てきたので以下のように変更した。
;; version 2
(define-syntax test-values
  (syntax-rules ()
    ((_ "tmp" name (e e* ...) (expected ...) (var ...) expr)
     (test-values "tmp" name (e* ...) (expected ... e) (var ... t) expr))
    ((_ "tmp" name () (expected ...) (var ...) expr)
     (let-values (((var ...) expr))
       (test-equal '(name expected) 'expected var)
       ...))
    ((_ (expected ...) expr)
     (test-values expr (expected ...) expr))
    ((_ name (expected ...) expr)
     (test-values "tmp" name (expected ...) () () expr))))
これなら返ってくる値を一つずつ比較するので、どの値が失敗するのかということが分かりやすくなった。マクロの量は2倍程度に膨らんだが、毎回test-equalを書く必要もないし楽だという感じであった。

予想される結果が複数ある場合が出てきた


このマクロはSASMを書いているときに使っているのだが、x86の一貫性のなさから返し得る値が複数ある場合が出てきた(例: ADD)。そうすると、何かを弄った拍子に結果が入れ替わるとかが起きると毎回テストを書き換えなければならない。それではテストを書いてる意味が薄れると思ったので、こういった場合にも対応できるようにした。
;; version 3
(define-syntax test-values
  (syntax-rules (or)
    ((_ "tmp" name (e e* ...) (expected ...) (var ...) (var2 ... ) expr)
     (test-values "tmp" name (e* ...) (expected ... e) 
                  (var ... t) (var2 ... t2)
                  expr))
    ((_ "tmp" name () (expected ...) (var ...) (var2 ...) expr)
     (let ((var #f) ...)
       (test-assert 'expr
                    (let-values (((var2 ...) expr))
                      (set! var var2) ...
                      #t))
       (test-values "equal" name (expected ...) (var ...))))
    ;; compare
    ((_ "equal" name () ()) (values))
    ((_ "equal" name ((or e ...) e* ...) (v1 v* ...))
     (begin
       (test-assert '(name (or e ...)) (member v1 '(e ...)))
       (test-values "equal" name (e* ...) (v* ...))))
    ((_ "equal" name (e e* ...) (v1 v* ...))
     (begin
       (test-equal '(name e) e v1)
       (test-values "equal" name (e* ...) (v* ...))))
    ((_ (expected ...) expr)
     (test-values expr (expected ...) expr))
    ((_ name (expected ...) expr)
     (test-values "tmp" name (expected ...) () () () expr))))
正直自分が書いたものじゃなければ見ただけでは理解できないレベルになりつつあるが、複数ある場合用のマクロ(test-values/altとか?)を作るのも嫌だなぁという気がしたのでこれはこれでいいかということになった。

単純なequal?では比較できない場合が出てきた


返ってくる値がequal?で比較できない、具体的には述語でテストしたい場合が出てきた。既にorで場合分けされているので同様にキーワードを追加すればいいだけだしということで追加した。
;; version 4
(define-syntax test-values
  (syntax-rules (or ?)
    ((_ "tmp" name (e e* ...) (expected ...) (var ...) (var2 ... ) expr)
     (test-values "tmp" name (e* ...) (expected ... e) 
                  (var ... t) (var2 ... t2)
                  expr))
    ((_ "tmp" name () (expected ...) (var ...) (var2 ...) expr)
     (let ((var #f) ...)
       (test-assert 'expr
                    (let-values (((var2 ...) expr))
                      (set! var var2) ...
                      #t))
       (test-values "equal" name (expected ...) (var ...))))
    ;; compare
    ((_ "equal" name () ()) (values))
    ((_ "equal" name ((? pred) e* ...) (v1 v* ...))
     (begin
       (test-assert '(name pred) (pred v1))
       (test-values "equal" name (e* ...) (v* ...))))
    ((_ "equal" name ((or e ...) e* ...) (v1 v* ...))
     (begin
       (test-assert '(name (or e ...)) (member v1 '(e ...)))
       (test-values "equal" name (e* ...) (v* ...))))
    ((_ "equal" name (e e* ...) (v1 v* ...))
     (begin
       (test-equal '(name e) e v1)
       (test-values "equal" name (e* ...) (v* ...))))
    ((_ (expected ...) expr)
     (test-values expr (expected ...) expr))
    ((_ name (expected ...) expr)
     (test-values "tmp" name (expected ...) () () () expr))))
最初は6行のマクロだったのに、現状では30行までに膨れ上がった。多分そのうち、返ってくるレコードの中身を調べる必要がある、ということが発生するのでまだ大きくなる予感がしている。

結局何が言いたいのか?


複雑怪奇なマクロというのは時として秘伝のタレ的に継ぎ足し継ぎ足しで大きくなっていく場合があるということである。今回はテストケース用APIの薄いラッパーなので、都度変えていくという選択肢もあったのだが、既に公開されているマクロを後方互換性を保ったまま拡張する必要がある場合などいかんともしがたい場面もあるのではないだろうか?

特になにという結論は用意していないのだが、巨大なマクロを見たら「お前にも歴史があったかもしれないんだねぇ」という目で見てみるのも面白いかもしれない。

2015-05-11

R6RS小ネタ

最近ブログを書く際に、この程度のこととか、こんな文量だと読み応えがないとか、実際の問題に即した話題じゃないとというようなことが頭をよぎり自分自身のハードルを上げているような気がしたので、しょうもないことを書いて多少ハードルを下げようといういう試みを始めてみることにした。(純粋に時間がないというのもあるのだが。)

世間(少なくとも僕の観測範囲)ではR6RSはオワコン的な風潮が多少出ていてさびしい感じがするので、R6RS処理系製作者の一人(と名乗ってもいいよね?)としては多少なりとも流行らせる努力をしたいところ。(ひいては自分の処理系の宣・・・げふんげふん)

リハビリを兼ねているので今回は簡単な小ネタを一つ。R6RSにはトランスコーダという概念がある。これを使うと、例えばUTF-8のファイルをUTF-16に変換して書き出すということが可能になる。例えば以下のようにする:
#!r6rs
(import (rnrs))

(define (convert-port input file transcoder)
  (call-with-port (open-file-output-port file (file-options no-fail) 
                                         (buffer-mode block)
                                         transcoder)
    (lambda (out)
      (put-string out (get-string-all input)))))

(call-with-input-file "utf-8.txt"
  (lambda (in)
    (convert-port in "utf-16.txt" 
     (make-transcoder (utf-16-codec) (eol-style crlf)
                      (error-handling-mode raise)))))
R6RS的には書き出し時のBOMの有無は必須ではないので、実はこれはポータブルな処理ではない点を念頭にいれていただきたい。Sagittariusは0.6.4でBOMを出力するように変更した。(BOMを書き出さないことに依存したコードは書いてないはず)。ちなみに同様の処理であるstring->utf16はBOMを出さないことが既定されている。

R6RSの範疇ではUTF-8⇔UTF-16しかできないが、Sagittariusを使うとSJISとEUCも入れることができるので多少便利(宣伝)。

2015-04-26

いつかきっと

なんとなく夢想したことをメモしておく。

きっかけはRustでOSを書くというツイートを見たことから始まる。もとのツイートが探せない程度のツイート検索力なのはご容赦いただきたい。それを見たときにCでOSが書けるのはGCCがアセンブラとリンカを持っていてるからではないかと思ったわけだ。まぁ、実際にはリンカが重要で後は単にファイルフォーマットだと思うのだが。そこで、こいつらを全部Schemeで書いてしまえば、SchemeがC並みのことをできる、つまり現状ではほぼCの独占状態である低レベルプログラミングの一角をSchemeが崩すことができるとふと夢想した。

実際にこれらを実装するとなるとかなりの労力が必要になるので夢想するだけで終わらせようかなと思ったのだが、せっかくだし暇を見つけてできるところまでやってみようかなぁと思い立った。まず必要になりそうなのは以下だろうか?
  • アセンブラ(とりあえずx86、x64で)
  • リンカ(ELFとPE辺りで)
っで、この上にSchemeの処理系を作るとさらに以下が必要になる(と思われる):
  • libc相当の何か
  • コンパイラ
リンカを作るのならlibc相当の何かはlibcでいいような気もするが、折角なのでCに全く依存しない処理系にしたいところである。

とりあえず下調べしたところでは、Schemeで実装されたアセンブラは2つある。一つはx86用のsassyで、もう一つはindustriaに実験的に組み込まれているx86、x64用ライブラリ。どちらもELFを吐くことができる。個人的にはsassyがいいかなぁと思ったのだが、これをx64用に拡張するのは酷く面倒そうに見える。問題になるのはx86用のレジスタ等がハードコーディングされているので、いろいろ考えるとこの辺はルールベースで良しなに扱ってほしいところ。例えば、x86だけをサポートするようとかだとフラグ立てるよりは、組み込むルールを限定した方が変なバグを埋め込まない気がする。一番の問題は、僕がこの辺に明るくないことか。とりあえずNASMのソースを見つつ、Intelのマニュアルを見つつやるしかないだろう。

残念ながらSchemeで書かれたリンカは見つけられなかった。 リンカのことを扱った本があった気がするのだが、名前を思い出せない。LLVMのリンカ部分を読めばいいだろうか?一番の不安材料である(ここで挫折して放置する可能性が高い)。

libc相当はとりあえずLinux(気が向いたらWindowsも)限定にすればシステムコール上に構築すればいいだけなので、ひたすら地味な作業になるだけと踏んでいる。dietlibcのような小さい実装もあるし(読みやすいと踏んでいるだけ)。

コンパイラはCPS変換するものにしておけばcall/ccの実装が楽になる(はず)。マクロ展開は辛いところではあるが、 既に実装しているので何とかなると思いたい。最悪ポータブルなものを使ってしまってもいいわけだし。

全てをR6RSポータブルにすれば、ホスト処理系を(理論上は)限定する必要がなくなるはず。R7RSじゃないのは浮動少数点の扱いが弱いから。いずれ実装する必要があるとしても、楽できるところは楽したい。

さて、これ何かしら動くものができるのは何年後になるのかね?

2015-04-14

Comparison of er-macro-transformer 2

Previous article: Comparison of er-macro-transformer

I've heard er macro and syntax-case can do the same things (or they have almost the equal power). Now I'm wondering if this is really true or not. Once upon a time, there was an R6RS portable OOP library called nausicaa-oopp. For some reason its repository is removed from GitHub. The library used syntax-case to its limit (I think) and provided CL like multi method and other OOP things.

One of the remarkable thing of the library was it inserts identifiers which renamed by syntax-case or syntax and binds a macro to it, then inside of the macro it refers the original identifier. For example, it can do like this thing:
;; <beta> is a macro which represents a class of object o.
;; with-tags binds a macro which name is o, thus the o in its body
;; refers to the macro. however inside of the macro o, it refers
;; given o.
(define (beta-def-ref o)
  (with-tags ((o <beta>))
    (list (o d) (o e) (o f))))
If you just read the comment, it seems pretty much normal thing however the macro with-tags requires to have the same name as the o passed to beta-def-ref. Thus this would raise an error.
(define (beta-def-ref o)
  (with-tags ((oo <beta>))
    (list (oo d) (oo e) (oo f))))
Can this be done on er macro? The answer is yes. This is the piece of code: https://gist.github.com/ktakashi/63745cf1b7e0a018b64f

Then how portable is this? I know there is no concrete specification of er macro so I would expect this type of code may not be portable. So I've run it on Chicken, Chibi, Gauche and Sagittarius. And the following is the result:
Chicken:
dispatched!
dispatched!
dispatched!
(a a a)
dispatched!
dispatched!
dispatched!

Error: unbound variable: oo

 Call history:

 <eval>   (cdr2441 x2345)
 <eval>   (pair?2514 x2440)
 <eval>   (null?2515 (cdr2516 x2440))
 <eval>   (cdr2516 x2440)
 <eval>   (car2519 x2440)
 <eval>   (pair?2536 w2518)
 <eval>   (car2539 w2518)
 <eval>   (cdr2541 w2518)
 <eval>   (display (quote dispatched!))
 <eval>   (newline)
 <eval>   (r src)
 <syntax>   (beta-def-ref2 (quote a))
 <syntax>   (quote a)
 <syntax>   (##core#quote a)
 <eval>   (beta-def-ref2 (quote a))
 <eval>   [beta-def-ref2] (list2684 (oo2680 d2685) (oo2680 e2686) (oo2680 f2687)) <--

Chibi:
dispatched!
dispatched!
dispatched!
(a a a)
dispatched!
dispatched!
dispatched!
ERROR in beta-def-ref2: undefined variable: oo
  called from <anonymous> on line 1039 of file /home/takashi/sandbox/share/chibi/init-7.scm
  called from <anonymous> on line 542 of file /home/takashi/sandbox/share/chibi/init-7.scm
  called from <anonymous> on line 622 of file /home/takashi/sandbox/share/chibi/init-7.scm
Searching for modules exporting oo ...
... none found.

Gauche:
dispatched!
dispatched!
dispatched!
*** ERROR: unbound variable: o
    While loading "./er.scm" at line 154
Stack Trace:
_______________________________________
  0  o

  1  (beta-def-ref 'a)
        At line 154 of "./er.scm"

Sagittarius:
dispatched!
dispatched!
dispatched!
(a a a)
dispatched!
dispatched!
dispatched!
Unhandled exception
  Condition components:
  1. &undefined
  2. &who oo
  3. &message unbound variable oo in library user

stack trace:
  [1] beta-def-ref2
    src: (lambda (o) (with-tags ((oo <beta>)) (list (oo d) 
    "er.scm":157
  [2] load
Chicken, Chibi and Sagittarius worked as I expected. It seems Gauche can't resolve the original binding. I guess Chicken requires to put explicit phase when importing a library if I want to use it in procedural macro but I don't know how on R7RS extension. Updated on 11/05/2015: Using import-for-syntax resolves this. Thanks evhan!

During writing the code, I've notice a small thing. Chibi and Chicken accepts the following:
(define-syntax foo (er-macro-transformer (lambda (f r c) (r '(display "hoge")))))
(foo)
;;-> prints "hoge"
However Gauche and Sagittarius raise an error. As a user, it's convenient if I can rename a list with rename procedure but is this actually common in sense of er macro?

2015-04-10

Improving string->utf8 and utf8->string

The procedures string->utf8 and utf8->string can be categorised in those mostly used procedures (at least in my mind). Until 0.6.2, the conversion was done via textual port allocated however this approach allocates lots of chunk of memory (one conversion allocates at least 32bytes for binary, and 128bytes for text) and calls bunch of C function which may not be inlined because of function pointer.

If we don't know which encoding to use, then this is not bad. But we know it's UTF8. So I've made changes to use UCS4->UTF8 and UTF8->UCS4 conversion directly. And making sure memory allocation only happens once at a conversion. Now, if changes are for performance improvements, then I must measure how much it's improved. So, I've used the following piece of code to benchmark.
#!r6rs
(import (rnrs) (time))

(define t)

(define (file->string file) (call-with-input-file file get-string-all))

(define-syntax dotimes
  (syntax-rules ()
    ((_ (i count) body ...)
     (do ((i 0 (+ i 1)))
         ((= i count) #t)
       body ...))))

;; CMakeLists.txt has appox 20KB contents.
(define bv (string->utf8 (file->string "CMakeLists.txt")))
(define s (file->string "CMakeLists.txt"))

(time
 (dotimes (i 10000)
   (set! t (utf8->string bv))))

(time
 (dotimes (i 10000)
   (set! t (string->utf8 s))))
If I use small string or bytevector, then I probably wouldn't see much improvements, so I used a bit bigger one. (the CMakeLists.txt now contains 20KB of data... I feel like I need to refactor it...)

And the result.
$ sash test2.scm

;;  (dotimes (i 10000) (set! t (utf8->string bv)))
;;  4.170478 real    4.163981 user    2.8e-500 sys

;;  (dotimes (i 10000) (set! t (string->utf8 s)))
;;  2.646136 real    2.638321 user    0.003989 sys

$ ./build/sagittarius test2.scm

;;  (dotimes (i 10000) (set! t (utf8->string bv)))
;;  1.437317 real    1.431425 user    0.003978 sys

;;  (dotimes (i 10000) (set! t (string->utf8 s)))
;;  1.210154 real    1.208894 user    0.000000 sys
It's now as twice as faster than befure. The result doesn't show but the GC occurrence is also improved. (approx. it occurs a half number.) This is kinda obvious because it doesn't allocate unnecessary memory at all now.

I've also compared with other implementations, Vicare, Mosh and Ypsilon. To run on Vicare and Mosh, I needed to create the compatible layered (time) library like this:
;; time.vicare.sls
(library (time)
    (export time)
    (import (only (vicare) time)))

;; time.mosh.sls
(library (time)
    (export time)
    (import (only (mosh) time)))
I couldn't find out how to create such a library on Racket, so just skipped.
Then this is the results.
$ vicare -L . test2.scm
running stats for (dotimes (i 10000) (set! t (utf8->string bv))):
    103 collections
    1818 ms elapsed cpu time, including 98 ms collecting
    1821 ms elapsed real time, including 100 ms collecting
    864268560 bytes allocated
running stats for (dotimes (i 10000) (set! t (string->utf8 s))):
    26 collections
    1539 ms elapsed cpu time, including 7 ms collecting
    1539 ms elapsed real time, including 7 ms collecting
    216186272 bytes allocated
$ mosh --loadpath=. test2.scm

;;3.1819961071014404 real 3.178515 user 0.0 sys

;;6.042346000671387 real 6.038440000000001 user 0.0 sys

$ ypsilon test2.scm

;;  0.198673 real    0.211882 user    0.021317 sys

;;  0.087744 real    0.108816 user    0.012085 sys
Ypsilon is the fastest. It's because Ypsilon uses UTF-8 as its internal string representation. Thus it just needs to copy it without conversion.Whenever I saw this type of difference because of the different choice, I would always think I've made a wrong decision. Well, it's too late anyway...

For now, it's only for UTF8 conversion procedures but if I start using other encodings (e.g. UTF16) a lot, I might apply the same trick.

2015-03-29

Emulate modular programming

It'll be long to put on reddit (mostly piece of code) and kinda pain in the ass to format code for reddit. So I've decided to write an article as an answer for this: R7RS modular programming struggle..

I'll answer the easier one first. The different behaviour is because the define-library is wrapped by begin. Larceny is using SRFI-78 (a.k.a van Tonder expander) and this expander creates a library at runtime. Thus, when the cond-expand is expanded, the library (dummy) is not created yet. Sagittarius, on the other hand, it creates a library at compile time. Thus, whenever define-library or library is found on the code, then the library is created at that time. So cond-expand can find the (dummy) during expansion. I guess, if you want to make the code work as expected, then removing begin should be enough.

NOTE: On R7RS (or even R6RS), the library definition can not be anywhere in program so the example code itself is not portable. For example, Chibi would raise an error if you write this on its REPL (which I think pretty much inconvenient).

NOTE: Removing begin works only on REPL because van Tonder's expander reads all expression first then expands it. Thus, at compile time there is no library created yet.

It is basically impossible to do the ML like modular programming on R7RS Scheme, if I understood the question correctly. But there is a technique that emulate it. The key is eval. It is easy to see on the code so code first.
;; without SRFI-39
(define-library (peano)
  (import (scheme base) (scheme eval))
  (export one add
          load-peano
          make-peano-impl)
  (begin
    (define-record-type peano-impl (make-peano-impl one add) 
      peano-impl?
      (one peano-impl-one)
      (add peano-impl-add))
    (define global-impl #f)
    (define (load-peano env)
      (let ((impl (eval '(load-peano-impl) env)))
        (set! global-impl impl)))
    (define (one) (peano-impl-one global-impl))
    (define (add a b) ((peano-impl-add global-impl) a b)))
  )


;; peano-numeral.sld
(define-library (peano-numeral)
  (import (scheme base) (peano))
  (export one add load-peano-impl)
  (begin 
    (define (load-peano-impl)
      (make-peano-impl 1 +))))

;; peano-symbol.sld
(define-library (peano-symbol)
  (import (scheme base) (peano))
  (export one add load-peano-impl)
  (begin 
    (define (load-peano-impl)
      (make-peano-impl
       '(s z)
       (lambda (x y)
         (if (eq? 'z x) y
             `(s ,(add (cadr x) y))))))))

(define-library (four)
  (import (scheme base) (peano))
  (export four)
  (begin
    (define (four)
      (let ((two (add (one) (one))))
        (add two two)))))

(import (scheme write) (scheme eval) (four) (peano))
(load-peano (environment '(peano-numeral)))
(four)
;; -> 4

(load-peano (environment '(peano-symbol)))
(four)
;; -> (s (s (s (s z))))
eval can take an environment so we can use that. Specifying which implementation should be used via load-peano by passing library name, and the (peano) sets the actual implementation to the global context. If the implementation supports SRFI-39, then using parameter would make it thread safe.

NOTE: If the implementation supports CL like method dispatch, then this can be much simpler. (Well, using TinyCLOS provides it and it wouldn't be so difficult to make some syntax sugar for that and provide it with R7RS library system. I just don't have motivation since Sagittarius already has it...)

NOTE: Parameter in R7RS doesn't specify when parameter object (or procedure) received one argument. As far as I know, all R7RS implementations behave the same as SRFI-39 but there might be an implementation that doesn't accept it in future.

NOTE: If the implementation supports identifier-syntax which is added on R6RS, then one can be defined like this:
(define-syntax one (identifier-syntax ((peano-impl-one global-impl))))
Then four can be like this:
(define-syntax four
  (identifier-syntax
   ((lambda ()
      (let ((two (add one one)))
 (add two two))))))
So you don't have to write four with parenthesis.

2015-03-27

R6RS protobuf

仕事でprotobufを使っている部分があることに気づき、そういえばR6RS用のライブラリがあったということを思い出す。これ:r6rs-protobuf

っで、早速使ってみたのだが、まともに動かない。プロジェクトも1年近く更新がないし、バグ報告するよりは自分で直した方が早いという結論にいたりforkする。これ:ktakashi/r6rs-protobuf

とりあえず直したバグと機能追加
  • /* */形式のコメントのサポート
  • トップレベルのoptionで例外を投げない(無視する)
  • ネストしたmessage/enumのサポート
  • レコードコンストラクタの引数違いの修正
  • generate-temporariesで作られた識別子からのシンボル生成
    • 処理系によってはポータブルじゃないシンボルが作られるので
  • (srfi :13)と(rnrs)でぶつかる束縛の修正
  • レコード型名の使用
    • Psyntax系の処理系だとマクロとして定義されている
    • record-type-descriptorマクロを使用するようにする
  • テストケースの修正
    • 不正なimport文
    • evalにdefine等を渡す
  • テストケースの追加
  • contrib/sagittarius/protoc-scmの追加
  • 処理系毎のpretty-printの追加(Mosh、Sagittarius、Vicareのみ)
プロジェクトページを見るとGuileでは動いているみたいなのだが、にわかには信じられない話であるというレベルのバグり具合だった。ものすごく単純なデータ構造のみなのかもしれない。

とりあえず、本家Googleのexampleにあるaddressbook.protoは動くようになった。一応開発者用MLに投げたので取り込まれるかもしれないし、僕のリポジトリが本流になるかもしれない(流行のゾンビOSS化してたらの話)予定。MLで即日返信が来てたので、近いうちに取り込まれると思われる。

個人的には(今のところ)関係ないのだが、(protobuf private)ライブラリだけはLGPLにしておいてほしかったなぁと思う。 Sagittarius用のライブラリを生成する際に、スタンドアローンでいけるオプションをつけたのだが、このライブラリがGPLv3なライセンスなので生成されるライブラリも(全部ひっくるめて一個のファイルにするので)必然的にGPLv3になってしまうという。個人的にProtobufを仕事用のスクリプト以外につかうことはないとは思うので(自分で何か作るならmsgpackとかあるし、自作のr6rs-msgpackはMIT互換の2項BSDライセンスなのでかなり自由だし)、どうでもいい話なのかもしれないが。

2015-03-26

Comparison of er-macro-transformer

In future, I don't know if it would be near or far yet, R7RS will have explicit renaming macro as its low level hygienic macro. So I thought it's nice to have some comparison. (though, I've just made one for now.)

There are some R7RS implementations which support er-macro-transformer. For now, I've used Sagittarius, Chibi, Gauche and Chicken (with R7RS egg). The main part that I was wondering for now is comparison of renamed symbols. So I made the following script to compare:
(import (scheme base) (scheme write) (scheme cxr))

(cond-expand
 (chibi (import (chibi)))
 (gauche (import (gauche base)))
 (sagittarius (import (sagittarius)))
 (chicken #t)
 (else (error "not supported")))

(define-syntax comp
  (er-macro-transformer
   (lambda (form rename compare)
     (define (print . args) (for-each display args) (newline))
     (let ((a1 (cadr form))
           (a2 (caddr form)))
       (print "eq?:               " (eq? a1 a2))
       (print "simple compare(0): " (compare a1 a2))
       (print "simple compare(1): " (compare a1 'a))
       (print "rename (eq?):      " (eq? (rename a1) a1))
       (print "rename (compare):  " (compare (rename a1) (rename a1)))
       ;; is a bound?
       a1))))

(define-syntax rename-it
  (er-macro-transformer
   (lambda (f r c) 
     (let ((cont (cadr f))
           (target (caddr f)))
       `(,@cont ,(r target))))))
(define-syntax rename-it2
  (er-macro-transformer
   (lambda (f r c) 
     (let ((cont (cadr f))
           (target (caddr f))
           (rest (cdddr f)))
       `(,cont ,(r target) ,@rest)))))

(guard (e (else (display "a is not bound") (newline)))
  (let ((a 1))
    (rename-it (rename-it2 comp a) a)
    (display "a is bound") (newline)))
It basically renames a symbol a and compare it in the macro.If you expose the renamed symbol, then implementations may raise an unbound error.
The result of above code is the following:
Chicken:
eq?:               #f
simple compare(0): #t
simple compare(1): #f
rename (eq?):      #f
rename (compare):  #t
a is not bound

Chibi:
eq?:               #f
simple compare(0): #t
simple compare(1): #f
rename (eq?):      #f
rename (compare):  #t
a is bound

Gauche:
eq?:               #f
simple compare(0): #t
simple compare(1): #f
rename (eq?):      #f
rename (compare):  #t
a is not bound

Sagittarius:
eq?:               #f
simple compare(0): #t
simple compare(1): #f
rename (eq?):      #t
rename (compare):  #t
a is not bound
In this case, Gauche and Chicken have the same behaviour. On Chibi, a is bound (which I think wrong behaviour since the macro rename-it is bound on global environment and referring the local environment. But there is no proper definition for explicit renaming yet, so who knows). Sagittarius doesn't rename if the given argument is not either a symbol or global defined identifier. I'm not sure if this is actually correct (feels not), but again there is no definition and R7RS mode is working properly with this behaviour. So I don't care much for now.
Updated on 29 March 2015: I've changed Sagittarius behaviour to rename (most of) identifiers as well so for this case it's similar to Chicken or Gauche.

During testing, I've got couple of bugs on Gauche and Chibi. Gauche's one was C level assertion error and Chibi's one was SEGV.

So far, there are not many difference among the implementations. Maybe I need to investigate more to find out (if I have time and motivation).

2015-03-25

R6RS compliant

Recently, I've improved R6RS compliance on Sagittarius. To check how much improved, I've run the test cases of nausicaa-oopp. Unfortunately, original Github repository seems gone somewhere but if you have it on your local machine, then checkout the revision '26c6994' which it still supported other R6RS implementations.

The library is R6RS portable yet so hard to run. As far as I know, there are only a few implementations which can run the test without raising an unexpected error (Racket and Vicare, I've tested). Now, it's time to add Sagittarius to the list.

Conclusion first, this is the result: https://gist.github.com/ktakashi/d6232d5ac7ae6a5d6fc1

To run the test, I need to patch some libraries. One is getenv and the other one is adding required argument otherwise Sagittarius compiler would raise an error during the compilation. There are couple of failures but these are either too specific test or enhancement of Sagittarius. The error of catch-syntax-violation can be consider test case's bug and some are Sagittarius enhancement. Sagittarius actually doesn't check duplicated bindings on let or letrec. Some are because of eval doesn't inherit current environment. (So the class <n> and <t> can't be seen). The test case itself expects specific value of &syntax's subform slot. It might be better to have some convension but R6RS doesn't specify this. The same goes catch-assertion test cases. The fixnum issue is that on 64 bit environment, Sagittarius uses 62 bits as fixnum (this seems the same on Vicare, so it fails as well).

I've also made an execution option that given script runs strict R6RS mode. Which basically reads all expression ahead and wrap with special syntax so that compiler can expand macro first and compile the expressions.
# Run the `script.scm` on strict R6RS mode
$ sagittarius -r6 script.scm
This mode is similar with the behaviour of Andre van Tonder's expander. Thus the script can contain library in it. Be careful, define-library can't be in it.

Now, I believe I can say, Sagittarius is also the R6RS implementation :) (unless otherwise there's a bug which is always the case.)

2015-03-23

Dynamic compilation (failure)

I don't have much problem with current performance of Sagittarius but it's always better to be faster. And I thought (yes, just thought), a good idea has come up. Well, conclusion first, it wasn't at all so if you want to read successful story, don't waste your time.

The idea was like this: if I can compile procedures to C, then it would be faster. Sounds fine, right? Of course there is always caveats:
  1. Calling Scheme procedure from C is expensive
    • I've learnt this from JIT experiment
  2. Macro can not be simply mapped to C procedure
  3. Which compiler should use for this?
2 and 3 are later stage issue, so I've checked item nr 1 first.

To check it, I've created a Gist: https://gist.github.com/ktakashi/8d9271600348db136877 There are 3 revisions but the most important ones are first and second one. The last one is just squeezing a bit of performance. The first revision is simply mapped procedure call to internal apply function. This is super slow as I expected. So I've switched to the second revision which uses CPS to do things. Well, as you can see it, it's not bad but not faster than pure Scheme. (NOTE: hashtable-map is implemented in Scheme world.)

Now, I didn't get satisfied result so I've also created very simple tail recursive fact in C. It's like this:
static SgObject fact(SgObject *SG_FP, int SG_ARGC, void *data_)
{
  SgObject m = SG_MAKE_INT(1), r = SG_MAKE_INT(1);
  SgObject n = SG_FP[0];
  
  while (TRUE) {
    if (Sg_NumEq(m, SG_FP[0])) {
      return Sg_Mul(m, r);
    } else {
      SgObject t1 = Sg_Add(m, SG_MAKE_INT(1));
      SgObject t2 = Sg_Mul(m, r);
      m = t1;
      r = t2;
    }
  }
  return SG_UNDEF;  /* dummy */
}
 
static SG_DEFINE_SUBR(fact__STUB, 1, 0, fact, SG_FALSE, NULL);
Tail recursive call can be a mere loop, so this must be much much much (times 100) faster than pure Scheme (this was my hope). So I've compared.
;; Scheme implementation
(define (fact n)
  (let loop ((m 1) (r 1))
    (if (= m n)
        (* m r)
        (loop (+ m 1) (* m r)))))

;; Expression to compare
(time (dotimes (i 10000) (fact 1000)))
Then I've got the incredible result!!
Scheme implementation

;;  (dotimes (i 10000) (fact 1000))
;;  0.000000 real    0.000000 user    0.000000 sys
C implementation

;;  (dotimes (i 10000) (fact 1000))
;;  4.692019 real    2.483000 user    1.622000 sys
Hooray!!! It's incomparable! WHAAAATTT???!!!

Well, if I just close my computer without evaluating this result, I would do the same thing in future. It's painful but I need to digest it... I guess there are couple of reasons but the biggest thing is that the VM is extremely turned especially those basic arithmetic operations. For example, addition of fixnum doesn't call C function but just do it on VM. If I disassemble the fact, then I can only see 21 VM instructions and only MUL uses C function call.
(disasm fact)

;; size: 21
;;    0: CONSTI_PUSH(1)
;;    1: CONSTI_PUSH(1)
;;    2: LREF_PUSH(1)
;;    3: LREF(0)
;;    4: BNNUME 5                  ; (if (= m n) (* m r) (loop (+ m ...
;;    6: LREF_PUSH(1)
;;    7: LREF(2)
;;    8: MUL
;;    9: RET
;;   10: LREF(1)
;;   11: ADDI(1)
;;   12: PUSH
;;   13: LREF_PUSH(1)
;;   14: LREF(2)
;;   15: MUL
;;   16: PUSH
;;   17: SHIFTJ(2 1)
;;   18: JUMP -17
;;   20: RET
The rest is simply done on VM. Thus, there is no overhead of calling C function.The C code version, on the other hand, it requires 3 C function calls for each iteration, plus inside of the C function. 3 times difference can be a huge difference (well, it actually is).

If I couldn't get any performance improved in this micro benchmark, then it wouldn't be any improvement in practice either. So, I just record this result and move forward...

2015-03-18

R6RS非準拠部分

Vicareの作者のブログを眺めていたらSagittariusでは(最初のリリースから)放置していた非互換を指摘されていた。こんなの。
;; from: http://marcomaggi.github.io/weblog/2015-February-16.html#fn-2
#!r6rs
(import (rnrs))

(define (fun)
  (mac))
(fun)
(define-syntax mac
  (syntax-rules ()
    ((_)
     (begin
       (display 123)
       (newline)
       (flush-output-port (current-output-port))))))
原因は分かっている。Sagittariusではスクリプトとして読まれたファイルは全て読まれた順に評価されるが、R6RSは「全て読み込んでマクロを展開してから実行しろ」という風に定めている。ちなみに0.6.2(か0.6.1からだっか)からはbeginで囲むと動く。ついでに、libraryフォームの中でも動く。このケースであればオプションを追加してそのオプションが指定された場合は一度ファイルを全部読み取って何かしらで包んでやればよいということになる。beginではまずいのでそれように何か足してやる必要はある。考えているのはAndre van Tonderの展開器で使われているprogramとか。

じゃあ、それを入れればいいじゃん?という話になるのだが、話はそんなに簡単でもない。現状ではトップレベルで定義されたdefine-syntaxのコンパイル及びトップレベルのマクロの展開しかしない。つまり、let(rec)-syntaxを用いてトップレベルに定義されるマクロは展開されないのである。つまり、これはbeginで包んでやっても動かない。
#!r6rs
(import (rnrs))
(define (fun)
  (mac))
(fun)
(let-syntax ()
  (define-syntax mac
    (syntax-rules ()
      ((_)
       (begin
         (display 123)
         (newline)
         (flush-output-port (current-output-port)))))))
これもlet(rec)-syntaxで定義されているマクロを評価してやればいいじゃん?と思うかもしれないが、話はそんなに簡単でもない。この例であれば動くのだが、例えば内側にdefineがあって、その中で局所マクロが使われていた場合に困る。

と、ここまで書いて案が浮かんできた。問題になるのは、局所マクロの評価をした後にdefineがコンパイルされない(すると問題になる)という部分だったのだが、ライブラリ及びトップレベルのbegin展開時に対応するコンパイル時環境を式に保持させればちょっとした手間でいけるような気がしてきた(現状よりさらにメモリを喰うようになるのが気になるが・・・)。ちょっと頑張ってみようかな。

New SRFI process proposal

Recently, one of the SRFI editors declared that he'll retire SRFI. When I read the post on c.l.s., it was shocking to me and on the same time I saw how much burden it was even he wasn't really a member of Scheme community for many years. Thank you so much for your service.

I think SRFI is one of the most important things for Scheme community. It can be pre-standard (see R6RS and R7RS-large). As a Scheme user, it is useful and convenient to write portable libraries. I can use it and just put a note that says this library requries SRFI-n. (well, if you aren't interested in writing portable libraries, then not that much. But I am.) So I hope it remains.

Needless to say, there are bunch of problems on the current SRFI process (not really the process but I use the word). Most of them are listed here. In short, it is heavily relied on only one person. If someone is willing to take over, then history might repeat again. So, in my opinion, we would need a new process.

How about using GitHub? GitHub has the ability to generate a web site. So finalised SRFIs can be located there. For new drafts, SRFI editors can create a new repositories for them and give the authors to commit right so that they can update their SRFI by themselves. The discussion can be done by issue based. All issues need to be closed before finalised. If mailing list is wanted, then  we can use Google group.

What can be the pros and cons for this? I can think of some.

Pros:
  • No maintenance needed for server machine
  • Reducing the task of SRFI editors
    • making repositories
    • finalising SRFIs
  • More open
  • Easy to hand over
Cons:
  • Too open?
  • Less control
  • Trusting SRFI authors too much?

In my opinion, the process should be outsourced as much as possible and amount of task for SRFI editors should be as less as possible.

Who should do it? Well, I would like to say 'me' but due to the personal reasons and luck of knowledge (especially domain transfer), it's kinda hard. (if I can, then earliest would be after October this year.) Plus, I'm not sure if this approach is acceptable for other Schemers. So for now, just thinking about it.

2015-03-05

Amazon面接記

1月の終わりから3月の初めまでの面接記。誰かの参考になるといいなぁ。

1月中旬、AmazonリクルータからLinkedIn経由でAmazon欧州採用イベントのメールを受け取る。このときは「まぁ、どうせ1000通以上送ったメールの一つだろう」くらいな気持ちで、興味があるという旨だけ3行くらいで返す。

同1月。そのリクルータの上司(?)からコーディングテストがあるから受けろといわれる。内容は、ストリームから文字列トークンの切り出し+αの問題と、配列操作+αの問題の2問。46時中プログラムを書いていればそんなに難しい問題ではないと思う。時間制限1時間(最長90分)の制限があった。2問目が難しいという脅しを受けていたのだが、40分で完了。(今イベント最速だったらしい) 今回は欧州採用イベントということで、コーディングテストが先だったらしい。よく知らん。

しばらく間があいて、すっかり忘れていたころにMixerイベントと面接の3月。メールの内容に寄れば2月中にアメリカから電話がかかってきて、面接でどんなことが聞かれるとかのヒントがあるとかないとかだったのだが、それはなかった。(これがなかったので、2月の間はマジで頭から抜けてたという話もある)

っで、面接。ここからは記憶がまだ新しいので多少詳しく書く。

面接は1対1、45分を4回。これを半日で行う。正直かなりの苦行だった。面接官は1日8回x3日なので頭が融けるんじゃないかな?ちなみに、面接官はTPM(Technical Programme Manager)かSDE(Software Development Engineer)のどちらか。内容はテクニカルなこと一辺倒。

最初の面接。データベースモデルの話。既存のテーブルモデルを拡張して新機能を入れたい。どんな風に設計する?という感じのもの。最初に大まかなアイデアを出して、面接官が突っ込んで、修正を入れてという形式だった。正直あれでよかったのかは自信ない。その後に今までのプロジェクトでイニシアチブを取って何かをしたことがあれば教えてくれみたいな質問。普通に答える。

次の面接。Amazonのシステムの一部がクラックされた上にチームの開発者も消された、しかもサーバのバックアップも燃えた(どんな状況だ?) 。そこで新たに雇われた君にそのシステムを設計してほしい。どのような手順でやるかを列挙した後に、細かい部分の説明をしてもらう。割と意味不明な状況だなぁと思いながら、要は上から下まで全体像を描けるかというものだと理解してそんな感じで答える。最後に本番用サーバ台数が不明だけど、どれくらい要る?という質問があったが、
毎秒のリクエストと1リクエストにかかる時間、さらに要求レスポンスから適当に割り出す。1リクエスト200msと適当に仮定してしまったのでサーバが1000台いるとかになって、流石にこれはありえんなぁと思いつつ。残りの時間は、締め切りとプロジェクト要求のプライオリティについての質問。まぁ、これも普通に答える。

3つ目の面接。コーディングテストその1。プロダクト、顧客及びその画面が見られた回数を保持するクラスのリストを、k個の顧客毎に最も多く参照されたプロダクトを保持するクラスのリストに変換するというお題(日本語むずい)。最初は優先度付きキューを使ってO(n*nlogn)で解こうとしたのだが、kはランダムなあんまり大きくない数字といわれたので、普通にバッファ持たせてO(nk)で解いた。リスト処理のお題をSchemerに出しては駄目だなという感じで、ささっと解法説明。んで、紙の上にコーディング(これに30分くらいかかった)。 終わった後に最初の面接と同じ質問。まぁ、定型文ですよね。

4つ目の面接。コーディングテストその2+システムデザイン。コーディングテストは配列の要素間の最大差を求める問題。愚直にやるとO(n^2)かかるけど、O(n)の解法を見つけられるかというもの。多少頭をひねってなんとかひねり出す(この段階では既に頭がまともに働かなかった)。システムデザインはある機能を実装するのにどんなコンポーネントを使ってどのようなシステムを構築するかというもの。正直こんなハイレベル(上流?)の設計はしたことがないのでしどろもどろ。正直にやったことねぇっすとゲロる。っで、2つ目の面接と同じ質問と今までで最も誇れる成果は何?という質問。仕事の成果なんて覚えていないので、Sagittariusのことをここぞとばかりに出してみた。興味を引いたらしいw

んで、結果。受かったw
それなりに経験積んでて、46時中プログラミングしてればいけるっぽい。正直なんで受かったのかは謎だが、こんな僕でもそこそこいけてるプログラマを自負してもいいだろうか?

2015-02-24

カスタムポート

R6RSにはカスタムポートという機能があるのは十分に知られていることだと思う。個人的にかなり使っているし非常に便利な機能だと思う。ただ、使っていると不満も出る。例えばカスタムポート自体をストレージとして使うことはできないし、port?とそれに準ずる手続きしかないため全く別のカスタムポートでも識別することができないという点である。

最初の問題は、例えばこのカスタムポートを使ってSRFI-6(open-output-stringget-output-string)を実装することはできない。バッファに溜め込んで返すようなポートをカスタムポートの機能を使って作成する場合は、open-string-output-portのような形にする以外にないのである。

次の問題は、幅があるのであるが、例えばポートがgzipポートなのかbzipポートなのかで処理を切り替えたい場合があるかもしれない。しかしながら、そのような判別を行うことはできないので、ポートを開く側で何とかするしかない。それが正しいといえばそうなんだけど、この例なら、gzipポートのときはヘッダ情報がほしいとかそういうこともできないので割りと不便なのである。あくまでポートはバイナリもしくは文字のI/Oのみに特化したもので、それ以外の処理は真面目にバイナリを扱えという位置づけともいえなくはないのだが、多段にポートをかませてフィルタをかけたいというのは割りとよくある使用例な気がしないでもない。(個人的によくやるので)

例えばGaucheにはvportという仕組みがあり、ポート自体を特殊化することができる。最近、本当につい最近なのだが、この仕組みの上にR6RSのカスタムポートを乗せた方がよかったのではないかなぁと思い始めてきた。90%くらいは現状の仕組みで問題ないのだが、10%くらい不満がでる。その10%は上記で述べた問題が主であるのだが。

問題になるのはクラス階層だろう。入力と出力、バイナリと文字という基本のクラスがありそこからファイル、バイトベクタ、文字列という感じに派生する。職業Javaプログラマになって10年以上経つのだが、こいつらを綺麗に階層化できるほどのオブジェクト指向能力がないというのが問題だろう。(一番上をインターフェースにしてとかでもいいんだけど、それはそれでなぁ。)

ちょっとポート周りのコードを見直してみたのだが、これを書き直すのはかなり大掛かりな変更になりそうな雰囲気があるのでかなり悩みものである。10%のためにこれをやるのかという話でもある。どうしたものかな。

2015-02-18

Benchmark of 2 match libraries

I've found a match library for Sagittarius on Github: match-sagittarius. It looks a bit different style of pattern syntax from Andrew Wright's pattern match library or Alex Shinn's one  which is fully compatible with Wright's one so understandable. There are couple of example on the repository so you can find how it looks like. (I think it's pretty cool!)

Now, if there are more than one the same concept library, then you always want to benchmark, don't you? So I made the following script to do:
(import (time) (match) (rename (match match) (match m:match))
        (srfi :1))

(define (count-pair lis)
  (let loop ((i 0) (lis lis))
    (match lis
      (((a . d) rest ...)
       (loop (+ i 1) rest))
      ((x rest ...)
       (loop i rest))
      (() i))))

(define (m:count-pair lis)
  (let loop ((i 0) (lis lis))
     (m:match lis
       (`((,a . ,d) . ,rest)
        (loop (+ i 1) rest))
       (`(,x . ,rest)
        (loop i rest))
       (x i))))

(define lis (list-tabulate 50000 (lambda (i) 
                                   (if (zero? (mod i 5))
                                       (iota (mod i 100))
                                       'x))))

(time (count-pair lis))
(time (m:count-pair lis))

It seems the library doesn't have variable length list match with ... so using pair notation. (This means it can't distinguish pair and list but not sure if it really can't match variable length...)
And I made the library name (match match) for my own sake.
The benchmark result was like this:
$ ~/projects sash -L. -S.sld match-bench.scm                                                                                                                                           

;;  (count-pair lis)
;;  14.316742 real    14.304623 user    0.003922 sys

;;  (m:count-pair lis)
;;  0.009591 real    0.005592 user    0.003994 sys
Boom! Wow! It's pretty fast! For this type of very simple pattern match which I believe most of the cases, this match library can be a good alternative.