Syntax highlighter

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.

2015-02-16

Keystore

3 years ago (or maybe 2 and half years), I've written incomplete PKCS#12 library which could at least load PKCS#12 keystores. Then it's been neglected for couple of years because there was no need to handle PKCS#12 keystores. Recently I needed to read it and remembered I've written it long time ago. So I thought it's a good timing to finish up the library at least making it work a bit properly like storing keys and certificates. It took couple of days to finish it but kinda looks good enough to expose so let me introduce a bit. (I still need to write documents, *sigh*)

The basic usage of PKCS#12 library is like the followings:
(import (rnrs) (rsa pkcs :12))

(define keystore (load-pkcs12-keystore-file "test.p12" "test"))

(pkcs12-keystore-get-key keystore "ca")
;; -> private key (currently only RSA is supported)

(pkcs12-keystore-get-certificate keystore "ca")
;; -> certificate (currently only X509 is supported)

;; storing a private key
;; private-key must be an RSA private key
;; certs must be a list of certificate for above private key.
(pkcs12-keystore-set-key! keystore "ca2" private-key certs)

;; storing a certificate
;; cert must be an X509 certificate
(pkcs12-keystore-set-certificate! keystore "ca2" cert)

;; dump to a file
(store-pkcs12-keystore-to-file keystore "test2.p12" "test2")
There are couple of more APIs but basic ones are above (I guess). There are couple of issues such as it can't handle empty password. These are because of my laziness and would be fixed when it became a problem (as usual).

There are bunch of types of keystores, one of the most famous one is PKCS#12 (also JKS is pretty famous but not supported yet). Since there are so many, it would be better to have abstract layer that absorbs the different. (I know it's not really Scheme way but I like convenient way.) So I also made a generic layer.
(import (rnrs) (security keystore))

;; passing 'pkcs12 as the keystore type
(define keystore (load-keystore-file 'pkcs12 "test.p12" "test"))

;; retrieving a key.
;; the last argument is password which is ignored on PKCS#12 keystore
(keystore-get-key keystore "ca" "test")

;; storing a key
;; the same as pkcs12-keystore-set-key! but with password
(keystore-set-key! ks "key" private-key "ignore" certs)

;; dump to a file
(store-keystore-to-file keystore "test2.p12" "test2")
For PKCS#12, key entry doesn't have password (well, if I read the specification correctly, it can be different password from store pass. But this is how Bouncy Castle behaves so should be proper behaviour).

I'm also working on JKS (and JCEKS) so the generic layer would be able to handle it (not the current HEAD but definitely 0.6.2).

2015-01-26

JSONパーサの性能改善

現状ではJSONパーサは(packrat)を用いて記述されている。(packrat)はBNFに近い形でパーサが記述できるという点においてはよくできているのだが、性能という点ではあまり(かなり)よろしくない。特にJSON程度の文法であれば、専用のパーサを書くのもそんなに面倒ではないのだが、いかんせん自分があまりタイトに使わないのでとりあえず気にしないでいた。

っで、以下のツイートと性能評価までしていただいた記事が昨日(だったかな?)でてきた。




JSON パーサの性能評価 - 主題のない日記

Guile用のライブラリをR6RS修正したものとの比較で30倍程度の差があるようである。 まぁ、性能に関して遅い方がいいなどという要件は見たことがないので、ここはえいやっとやってしまおうということにした。

せっかく書き直すのだから、後で多少色を付けやすいように(text json)というライブラリを作り、(json)はそれを使用するという形にすることにした。まぁ、実装はゴリゴリと地道にパーサを書くだけなので省略。

っで、ベンチを取る。上記の記事で使用したデータは非公開のようなので、Twitterから適当にJSONデータを取得。(Sagittarius-net-twitterを使用した。これももう少しTwitter API v1.1に対応しないとなぁ・・・) 25KBと多少小さめだがまぁいいだろう。ベンチマークには以下のスクリプトを使用。
(import (rnrs) 
 (prefix (text json) new:)
 (prefix (json) old:)
 (time))

(define (run-bench json-read)
  (call-with-input-file "bench.json"
    (lambda (in)
      (time (json-read in)))))

(run-bench old:json-read)
(run-bench new:json-read)
以下が結果:
;;  (json-read in)
;;  0.815046 real    1.310000 user    0.000000 sys

;;  (json-read in)
;;  0.032002 real    0.031000 user    0.000000 sys
25倍程度の高速化になったみたいである。まぁ、これくらい高速になるのであれば置き換えてもいいかな。

2015-01-23

Implementing non portable syntax-case

There are 2 portable syntax-case implementations, psyntax and SRFI-72. Both can be run on R5RS implementations and provide not only syntax-case but also library mechanism defined in R6RS. It is very reasonable to have such a huge mechanism instead of just providing syntax-case only because bunch of things pretty much related with syntax-case (or more precisely procedural macro and library system).

You can use it as your expander however if an implementation already has own module system then it might not a good idea to use it as it is. As my understanding, at least SRFI-72, expands all bindings to only one namespace which makes the namespace or symbol table really huge and may impacts memory usage. And again, this is reasonable decision because R5RS doesn't provide module system and if you need to write portable library then everything needs to be defined in one single namespace.

Since Sagittarius is using none of them but implementing own syntax-case expander and library system, it wouldn't hurt to write an article for this. Plus, apart from my lack of searching skill, I couldn't find any article mentioning how to implement it, other then couple of papers (could be that's enough for everybody...), I thought I can contaminate the search engine result a bit more with mine. This is basically my memo before I forget everything.

WARNING: The following sections may or may not contain mistakes. DO NOT TRUST :P

How to implement syntax-case on top of own library system


Implementing syntax-case is not an easy task to do especially in a portable way. The 2 portable implementation provides syntax-case expander and library system. This is because R5RS doesn't provide module system and R6RS procedual macros require phasing to resolve from where the bindings are imported during macro evaluation (not expansion) period. However if an implementations already has own library system, it is better to implement syntax-case on top of it so that the implementations can reuse the existing libraries without modifying anything. The following sections describe how Sagittarius' macro expander is implemented on top of own library system.

Pre-requirements


On Sagittarius, 2 Scheme objects were introduced for syntax-case, identifiers and macros. Identifier has the following slots:
  • name: raw name of the identifier, symbol
  • envs: compiler environment frame, alist
  • library: a library where this identifier belongs, library object
  • identify: a unique symbol generated per macro expansion, uninterned symbol
  • pending: a flag that indicates if the identifier is a template variable or not, boolean
The last slot, pending, is used to make an identifier unique so that evaluating template variable makes unique identifier each time. This may not needed if macro expander itself generates unique bindings like SRFI-72. However doing so may cause symbol explosion so I decided to introduce this. Internally, macro expansion is done by renaming symbols or identifiers. Each expansion remembers which symbol or identifier renamed to which so that if a symbol is renamed to an identifier twice then it will be the same object in sense of eq?.

Macro has the followings slots:
  • transformer: a procedure which expands given expassion
  • envs: a compile time environment when this macro is bound, vector
Whenever a macro is invoked, then VM swaps current macro environment with the one the macro has. And new identity is generated to rename symbols or identifier properly. Swapped environment and identity are restored when the transformer returns.

Renaming


Renaming, on this context, means converting symbol or identifier to new identifier. There are 2 rules when renaming is invoked:
  • Symbols are renamed to be global identifier (passing null environment frame)
  • Not all identifiers are renamed (pattern variables, non local variables, etc.)
The idea of the first rules is inspired by SRFI-72 implementation which very first step is wrap all symbols to identifiers with empty environment. To avoid unnecessary memory allocation, I've decided to delay this step as late as possible. Thus raw symbols and identifiers created with empty environment are treated the same.

The second one is preservation. For example, local variables need to be preserved so that it can be referred. The same goes pattern variable and pending identifier which the pending slot contains #t.

Renaming is done 3 times in total. The first one is during syntax-case compilation. In this step, both pattern and template are renamed. Then the pattern variables are stored in compile time environment. The second one is during syntax compilation. In this step, only raw symbols are renamed to identifiers. The last one is during expansion. The target template needs to be renamed so that it can generate fresh identifier each time. After the expansion, raw symbols are also renamed if there is. The raw symbol conversion is required because of R6RS procedures. (actually not needed if I don't care about compliance but unfortunately I do.)

Identifier equivalence


Comparing identifiers are crucial. R6RS defines 2 types of comparison procedures, bound-identifier=? and free-identifier=?. On Sagittarius, returning #t from bound-identifier=? means given 2 identifiers have the same identities and libraries. Thus they are generated on the same macro expansion phase. Free identifiers are pretty much simple, it just checks if the given 2 identifiers are bound to the same value. This also means different named identifier can be #t in sense of free-identifier=?. (R6RS allows implementations to behave like this.)

Local variables are also simply looked up. Compiler just needs to compare variables in sense of bound-identifier=?. Because of the trick described above section, the same source identifiers are renamed to the same object. This makes look up process simply and easy. Even though the process is simple, however, comparing identifier and symbol needs special treatment. In basic concept, raw symbols and global identifiers are the same. The special treatment is when an identifier contains the same environment frame as current compile time environment frame. Variable look up is done per frame and whenever an identifier is generated by macro expander, then it contains environment frame of that moment. Following is the example case:
(import (rnrs))

(let ((a 1))
  (let-syntax ((foo (syntax-rules () ((_) a))))
    (let ((a 2))
      (+ (foo) a))))
The macro foo contains the first a which will be an identifier when it's expanded. However the compiler environment frame contains raw symbol a. So to look up it properly when the identifier contains the same frame, then it needs to compare the target as either raw symbol or global identifier.

Pit falls


Fresh template variables: R6RS requires the following template variable to be unique:
(import (rnrs))

(define-syntax define-dummy
  (syntax-rules ()
    ((_)
     (define dummy))))

dummy
;; -> unbound variable error
As I described above section, SRFI-72 resolves this by renaming all bindings to unique symbols. However this might be overkill if implementations already have its module system or namespace. A symbol can have different bindings if module system allows. On Sagittarius, a binding uses the raw symbol name of an identifier. Thus without any treatment, above piece of code can be run without problem. To resolve this, I introduced pending slot. The syntax which creates bindings such as define, then it always swap raw symbol name of pending identifier to uninterned symbol so that the identifier can not be seen out side of the template where it's defined. This is rather ugly solution, so I want something better.

Pattern variables: pattern variables are also identifiers except its environment frame is not a valid compiler environment frame. This is needed because pattern variables need to be preserved. However preserving pattern variable made incompatibility of portable implementations. The particular issue is following:
(import (rnrs))

(define-syntax foo
  (syntax-rules ()
    ((_ x)
     (let-syntax ((bar (syntax-rules (x)
                         ((_ a) #t)
                         ((_ b) #f))))
       (bar b)))))

(foo a)
;; -> #f
The pattern variable a is not renamed so the first pattern of bar won't match (because the pattern variable a and input variable a are not the same in sense of free-identifier=?). I believe this behaviour is still R6RS compliant since it doesn't specify this type of pattern variable renaming (if I read it correctly). To avoid this, the following is one of the solution:
(import (rnrs))

(define-syntax foo
  (syntax-rules ()
    ((_ x)
     (let-syntax ((a (syntax-rules ())))
       (let-syntax ((bar (syntax-rules (x)
                           ((_ a) #t)
                           ((_ b) #f))))
         (bar b))))))

(foo a)
;; -> #t
This behaviour is, again if I read R6RS correctly, specified in R6RS. In this case, pattern variables need to be renamed.

Conclusion


Using portable implementations is much easier then implementing own syntax-case. As long as implementations don't have own module system, it is better to use it. I just wanted to show at least there is a way not to use portable implementations. If you can integrate syntax-case on your own implementation, then core part can be really small (less than 1000 LoC in my case).

味園ユニバース(La La La at Rock Bottom)

ロッテルダムでやっている国際映画フェスティバルで日本語の映画がやるということで、同僚(もうすぐ元になるが)と映画を見に行った。詳細はこちら(オランダ語):味園ユニバース(La La La at Rock Bottom)

以下はネタばれを含むので見てない方、これから見ようと思っている方は読まない方がいいかも。

2015-01-18

SRFIを書く/採用する理由

まだドラフトにもなっていないが新しいSRFIを提出した。ぶっちゃけ大したものではないが、あると便利系のものである。実装はR7RS+既存のSRFIで行ったのだが、これがまた面倒であった(多少SRFIを書く理由にかかる)。一つの処理系のみを使ってる、もしくは手元に過去の資産としてある程度のコードがあるという状態であればSRFIは特に必要ないだろう。ただ、それだと非常に面倒なのである。ソート手続き一つを取ったとしても、たとえ20行もあれば書けるとはいえ、毎回書きたくはない。開発効率を見れば、よく使うものは処理系がサポートしているべきである。そう、私がSRFIを書くもしくは採用する一つの理由はあれば便利だからである。特に最近のR7RS-large絡みのSRFIはScheme用ライブラリの拡充に近い部分があり、あると便利なのである。

私はちょいちょいポータブルなライブラリを書く。 R6RSかR7RSかはそのときの気分次第ではあるが。最近はR7RSの方が多い気がする、処理系の更新があるから。よく使うR6RS処理系(Mosh、Ypsilon)は更新とまってるんだよねぇ、はぁ・・・。ポータブルなものを書く理由は特にない、あるとすれば名前を売るか自己満足くらいだろう。Schemerが増えてSagittariusへのフィードバックが多くなるといいなぁとかも考えてはいるが、期待はしていない(正直特に反応もないし)。これはポータブルなものに限った話ではないのだが、ライブラリを書く際に部品が足りていないと非常に辛い。例えば優先度つきキューを考えてみる(最近適当なのを書いたのだ)、こんな超が付くほど有名なデータ構造は標準もしくは準標準でサポートされていてほしいと思うのが多少なりともプログラムを書いた人間なら思うだろう(学習用とかは除く)。しかし、残念ながらSchemeにはどちらにもないのである。

なければその場で書いてもいいだろう、 実際適当な実装であれば50行もあれば書けてしまうのだ。問題はそれがこれか何万回と続く可能性があることだ。誰もが使う可能性があるデータ構造、アルゴリズムというものは裏を返せば(返さなくても)自分もよく使うのである。R5RS以前のSchemeはモジュールという概念がなく、そういったものを標準の範囲内でまとめておくことができなかったが、R6RS以降はライブラリがあるのだ、使わない手はない。

もう一つ理由がある。インターフェースの統一である。例えばスレッド関連のSRFIとしてSRFI-18があるのだが、不思議なことに採用している処理系はそんなに多くない。POSIXスレッドモデルを採用している処理系であれば互換レイヤを書くのはそんなに難しくないのだが、世の中そんなに甘くない。私がよく使うR6RS処理系、MoshとYpsilon、はMutexすらユーザに見せていない。 そうすると同期を必要とするライブラリを書くのが非常に面倒になる(それらをサポートしないという手ももちろんあるが・・・)。こうなったときに処理系側にサポートを強要することが可能な一つの手段としてSRFIがあると思っている。

例えばSRFI-1を考えてみる。リスト処理に特化したこのSRFIは数多くの処理系がサポートしている(ポータブルに書けるというのは置いておくとしてだ)。多くの処理系がサポートしているデファクトSRFIというのは他の処理系もないがしろにしないだろう(個人的感想)。例えばSagittariusは元々SRFI-25とSRFI-78をサポートしていなかったが(特にSRFI-78はSRFI-64とコンセプトが似ているので)、ユーザからのフィードバックでサポートするようになった(実装まで送られてきたのではしないわけにもいくまい)。こういう経験から、あるSRFIが幅広く使われるようになれば、例えポータブルなものが使えない処理系でも、サポートされるのではないかという期待が持てるのである(その処理系が継続的に開発されてればではあるが・・・MoshもYpsilonも数年新しいリリース出てないなぁ・・・)。

特に何のオチもないのだが、終わり。

2015-01-13

マクロの健全性または如何にして私はerマクロを使うのをやめsyntax-caseを愛するようになったか

メモワール(Memoir)という単語をTwitter上で見かけて、自分も何か(主にあほなこと)を書きたくなっただけ。

Schemeにはhygienic macroなるものがあり、清潔なマクロとか健全なマクロとか訳されるのであるが、それを使うと変数の衝突などの問題をあまり考えなくてもよくなるである。Scheme界では長年このマクロについて議論されてきたらしいのだが、R6RSで終に低レベルかつ健全なマクロの一つであるsyntax-caseが標準に入ることになった。これでマクロ展開時に式変形以上のことができると喜んだのもつかの間、R7RSではまた不便なsyntax-rulesだけに戻されてしまった。理由はよく分からない。風の噂ではR7RS-largeではExplicit Renamingと呼ばれる別の低レベルな健全マクロが入るとされている。

erマクロとはどんなものか?大まかに言えば、Common Lispのマクロに健全性を追加する機能を備えたものである。与えられた式の解析、どのシンボルを衝突しないものにするか等は全てユーザーに任される。どのような見た目になるのか、伝統的なaifをerマクロで作ってみることにした。
(define-syntax aif
  (er-macro-transformer
   (lambda (form rename compare)
     (let ((test (cadr form))
           (then (caddr form))
           (els  (if (null? (cdddr form))
                     #f
                     (cadddr form))))
       `(,(rename 'let) ((it ,test))
         (,(rename 'if) it ,then ,els))))))

(aif (assq 'a '((a . 0))) it)
;; -> (a . 0)
マクロの定義が与えられただけではどのような式を渡せば良いのか皆目検討もつかない。さらにはこのままでは期待する式が与えられなかった際のエラーもよく分からないものになる。
;; Oops!
(aif (ass 'a '((a . 0))))

#|
*error*
#<condition
  &compile
    program: (aif (assq 'a '((a . 0))))
    source: "macro.scm":17
  &assertion
  &who car
  &message pair required, but got ()
  &irritants ()

>
stack trace:
  [1] raise
  [2] caddr
  [3] #f
    src: (caddr form)
    "macro.scm":7
  [4] macro-transform
  [5] pass1
  [6] #f
  [7] with-error-handler
  [8] load
|#
きっちりやるのであればかなりのコードを書く必要があり、僕のようなずぼらな人間には使うのが辛いものである(もちろん式解析などパターンマッチでやってしまえば良いのではあるが...)。

ではsyntax-caseではどうだろう?同様のものは以下のように書ける。
(import (rnrs))

(define-syntax aif
  (lambda (x)
    (syntax-case x ()
      ((aif test then)
       #'(aif test then #f))
      ((aif test then else)
       (with-syntax ((it (datum->syntax #'aif 'it)))
         #'(let ((it test))
             (if it then else)))))))

(aif (assq 'a '((a . 0))) it)
;; -> (a . 0)

(aif (ass 'a '((a . 0))))
#|
*error*
#<condition
  &compile
    program: (aif (assq 'a '((a . 0))))
    source: "macro.scm":32
  &syntax
    subform: #f
    form: (aif (assq 'a '((a . 0))))
  &who aif
  &message invalid syntax

>
stack trace:
  [1] raise
  [2] macro-transform
  [3] pass1
  [4] #f
  [5] with-error-handler
  [6] load
|#
マクロ定義からどのような構文なのか分かりやすいし、エラーも構文がおかしいといってくれる(パターンを列挙する等もう少しエラーメッセージが詳しいとうれしいかもしれないが)。なにより、erマクロにはない必要な部分のみを記述しているという感じがよい。

僕にもsyntax-caseは人間が使うには複雑すぎる、erマクロのような式が直接いじれるマクロの方がいいと思っていた時期があった。しかしその思いは簡単なマクロを書くには問題ないのだが規模が大きくなればなるほど逆転していった。これは式解析、変形を記憶しておくことができる頭のいい人間用のマクロではないのではないかと。事実、入力された式の何番目にこの要素を期待してというようなおよそ僕の頭では処理しきれないような処理を負担さてくるではないか。確かにerマクロは直感的である。マクロとは単なるリスト操作であるということさえ分かっていればその使用感は単なるリスト操作プログラムとほぼ同等である。逆にsyntax-caseはwith-syntax等の新しい概念を要求するため初期投資はerマクロより大きいかもしれない。しかしながら、余計なことを考えなくてもよいというその払い戻しは計り知れない。特に僕のようなまずは目的を達すること、その後で手段を見直すような人間にはとても便利なツールである。

こうして僕はerマクロには別れを告げsyntax-caseを愛するようになった。

2015-01-10

Shallow string copy

Since Sagittarius 0.5.10, symbols and keywords are also target of GC. And both are using string as it's real name. The strings were copied and made as literal string before so that symbol->string could just return the given symbols name. It's not the same story now. The whole purpose of GCable symbols and keywords is saving memory. For example, what would happen if symbols were not GCed:
(dotimes (i 10000000)
  (string->symbol (format "symbol.~a" i)))
;; -> 10000000 symbols will be created
You would think nobody writes this type of code. But what if the input was user dependent? To avoid these type of out of memory, I've decided to introduce GCable symbols and keywords.

Now, I didn't make literal string GCable. I don't remember the exact reason but I think it was too naive implementation to do it and caused a lot of problem (maybe I should try again but feels like it would be very tricky to do it since symbols' and keywords' names are string). So whenever symbol->string is called and the name is not a literal string then the procedure copies the string. Thus it can be O(n) process. Stupid isn't it? So I'm thinking to introduce shallow string copy that only takes O(1).

To do it, I need to reconstruct C world string structure. It's currently defined like this:
struct SgStringRec
{
  SG_HEADER;
  unsigned int literalp: 1;
  int size             : (SIZEOF_INT*CHAR_BIT-1);
  SgChar value[1];
};
This is because of GC efficiency. Strings are allocated as atomic memory means there is no pointer inside. This makes GC impact a bit lighter because collector won't traverse inside of allocated pointer (according to Boehm GC document). If I make shallow string copy takes O(1) then the structure should be something like this:
struct SgStringRec
{
  SG_HEADER;
  unsigned int literalp: 1;
  int size             : (SIZEOF_INT*CHAR_BIT-1);
  SgChar *start;
  SgChar *end; /* or add one more flag if this is shallow copied */
};
Then copy string just puts the source pointer. If modification happens, it just make sure the pointer will be deep copied. Seems fine, the consideration is how much GC performance impact it would cause.

The GC impact can be 2 parts:
  • Making string non atomic pointer
  • Limited range shallow copy
The first one is Boehm GC thing so I just need to profile it. The second one can be a problem. Lets say you create a huge string and substring it like this:
(define (split-string s)
  (values (substring s 0 10)
          (substring s 10 20)
          (substring s 20 30)))
The number of character you want is only 30. However if the input string is, let's say, 10000, then the original source pointer would remain until all 3 strings are GCed (or modified). On the other hand, if string copy happens so many times with small string, then actual memory consumption would be smaller. Well, it's not about memory consumption but processing order so this might be kinda trade off.

So to estimate how much impact we would have, I've counted the number of possibly affected procedures.
string-copy103
substring178
symbol->string167
string-set!158
Not so many. This result even includes test cases. symbol->string is not called in many place. So the overhead of O(n) process may not be an issue. (Well, I know this is rubbish because it doesn't show how many it's actually called.)

Hmmmm, should I?

2015-01-08

識別子を識別するために

SRFI-72を確認した結果
  • 識別子の比較は、名前とその識別子の色で行われる
  • 識別子が含む色はリストである(colors)
  • 色はマクロが呼ばれる度に生成される
  • 色は一意のシンボル(eq?でのみ比較される何か)である
  • ソースの式に含まれるシンボルは全て識別子に変換される
    • その際の色は空(nil)
  • 識別子が含む環境は、リネームされるたびに追加されている
  • 束縛は識別子の名前と色をキーとして作られる
  • 全ての束縛には一意の名前が付けられる
    • ライブラリからエクスポートされる際にはそれに対して別名がつく
上記はまぁ前から分かっていたことなので単なる覚書でしかない。本当に知りたいことはリネームのタイミングと識別子の識別方法だったりする。ポータブルなR6RSマクロ展開器であるPsyntaxやこのSRFI-72はどちらもライブラリ機構も提供していて、少なくともSRFI-72はマクロ展開器自体がその機構と密接に関連している。なので一部だけを取り除いて使うということはなかなか難しい。例えば、テンプレート変数が展開されるたびに一意のシンボルになるというのとか。(色付け機能だけを取り除いて実装してみた結果分かったこと。手を動かさないと理解できない程度には頭が悪いので・・・)

とりあえずそれは忘れて現状のリネームの粒度を見直してさらに変数参照の見直しをした結果もう一つわかったこと。おそらく見直し後のリネームの粒度は正しい(syntax-caseのコンパイル時とsyntaxテンプレートの展開時の2回。以前は合計で3~4回やってたorz)。識別子の比較には別の要因がいる。現状識別子が持っている環境を比較をeq?で比較しているのだが、これではまずい場合がでてきている。マクロ展開器を起動した際に環境フレームのみをコピーして一意にしているのだが、これだと同一であるはずのもが非同一になる。これは困る。ここでSRFI-72で行われている色づけが使えそうな気がしないでもない。上記に書いたように、これだけに絞るとまずいので、現状の仕組みの上につける必要がある。(アホみたいな識別子のスロットを排除したいところなのだが、無理っぽいな。)

問題は、どのタイミングで色を変えるかということ。一つはマクロ展開器を起動したタイミングなのだが、そこだけでいいのかが不安。なんとなくもう一息な感じのところまでは来ている気がするので、MPが残っているうちに片付けてしまいたいところではある。走り書き過ぎて自分でも何言ってるのか分からなくなった。

2015-01-07

致命的目な勘違い

随分長いこと勘違いしていたのだが、以下のコードはエラーにならないといけない。
(import (rnrs))

(define-syntax aif
  (lambda (x)
    (syntax-case x ()
      ((_ test then)
       #'(aif test then #f))
      ((k test then else)
       (with-syntax ((it (datum->syntax #'k 'it)))
         #'(let ((it test))
             (if it then else)))))))

(aif (assq 'a '((a . 0))) it)
;; -> error
理由は、一つ目のパターンが展開された際に挿入されるaifは与えられた式のものではないためdatum->syntaxで生成される識別子が期待されるテンプレート識別子から生成されないため。_aifとして、置き換えの際に元の識別子が挿入されるようにすればOKになる。

何が問題かといえば、Sagittariusはこれをエラーにしない。さらにまずいことに僕自身がこの動作を期待してコードを書いている点である。datum->syntaxを多用した記憶はあまりないのだが、CLOS周りとかはかなり処理系の中身べったりで書いているので問題が起きる。また記憶が正しかったら(binary data)辺りもこれ系の動作を期待しているような気がする。

上記のような記憶にあって目に見えてる系のものならまだ救いがあるのだが(それでも影響範囲広いけど)、下記のような間接的に期待しているものがあると困る。
(define-syntax aif1
  (syntax-rules ()
    ((_ test then)
     (aif1 test then #f))
    ((_ test then else)
     (aif test then else))))

(aif1 (assq 'a '((a . 0))) it)
見た目的にはaif1aifの薄いラッパーで単に式をaifに移しているだけなのだが、これはR6RS的には動かない(はず)。が、Sagittariusでは動いてしまう。これ系のコードはdefine-methodで山ほど書いてる気がする。

ここらで一発マクロ周りの見直しをしないといけないな。この辺りを網羅したR6RS準拠なテストケースがほしいところである。PLTのやつはマクロ周りのテストが貧弱すぎて、全パスしてもスタート地点にすら立ってない感じががが・・・

2015-01-04

Environment frames on identifiers

Happy new year! I've kinda missed Japanese holidays around new years day since I needed to work on 2nd January. Some friends even remained me that it's holiday. Shoot!

I've written the article about the bug of datum->syntax. Now I think I've got an idea to resolve without doing O(n^2) identifier rewriting thing during showering. It's always good to let it sit for couple of days (can be weeks or even months).

The problem is that if a renamed identifier is a local variable however variable look up can't find it properly because it's comparing somewhat awkwardly. The reason why it's doing weirdly is more like historical reason (mostly my ignorance of hygienic macro). It might be cleaner if it can refer just comparing environment frame however because of the lack of knowledge, it's now a huge spaghetti even I don't understand why it's like that. Currently identifiers can hold one set of compile time environment frames. The structure of env frame is like this:
(type . ((var val) ...))
type indicates if this is a local variable frame or a pattern variable frame. To look up proper variables from this, it required (or not) somewhat very complicated pile of shit. It basically tries to find proper frames of given identifiers. However because macro expander doesn't rename all identifiers, some frames are the same in identifiers that should be different variables.

The idea came up during showering is making identifiers can contain multiple sets of env frames. The frames should be used from the latest to oldest and macro expander should always rename with prepended env frames. This seems identifier can hold proper environment where it's defined no matter how many it's got renamed. The issues I can see are:
  • Cache file explosion
  • Memory consumption
The first one should not be big deal but I may face this since I've already got huge cache file issue. The second one is sort of inevitable if we rename identifiers each macro expansion.

I'm not totally sure if this works or not yet but sounds like a plan. Need to consider a bit more before start doing this.

2014-12-31

Reviewing 2014

I usually write this things in Japanese but I've heard couple of times that I'm writing cryptogram language so just decided to write in common language, in this case English (well writing in Dutch is still too hard for me...)

Describing 2014 in one word, then it would be change. It's not taken from what the US president said. I think I started taking challenges at some point, probably in March or April, then the changes started happen.

[Private]
I don't write a lot in this topic but just some for my memo.
  • Things are moving forward (not sure if it's good way or not, yet).
  • I've had my shoulder dislocated. It was my very first time in lifetime (ouch!)
  • Leaving current job.
  • Went to Japan twice a year. (Congrats my friend, be happy!)
    • I need to send pics and videos. Oh gosh, totally forgot about it...
  • Went to Washington D.C.
  • Became level 8 Schemer. (See Scheme section)
[Scheme]
I've joined LISP Library 365 to introduce SRFIs.I wrote only 3 times a month so there was no way to write introduction for all SRFIs (in the end it ended up to SRFI-42 except the last one). Not sure if there is a person thought that's useful though...

I've submitted a paper for Scheme Workshop 2014 and accepted in October. So I went to Washington D.C. to make the presentation. I struggled writing the paper but it worth it. (thought I'm not sure if I want to do it again because I'm not good at writing...) Now, I'm a level 8 Schemer :) (although, I still think call/cc is difficult and avoid to use...)

I've made R6RS portable library json-tools and R7RS portable PostgreSQL binding. I thought json-tools was made last year (2013) but it was this year. At some point, time doesn't fly. Unfortunately, they are not needed by anybody (even including me by now but I can't predict the future). Writing portable libraries actually doesn't make my day but sometimes it's good to do it to see how much Scheme can do. Some people say it's only for educational purpose which I totally disagree. It just doesn't have enough of useful portable libraries.

I could release Sagittarius monthly this year (except December, I was a bit too busy). As always, I can't remember how it was in the beginning of the year. I'm not yet satisfied it so it will evolve next year. These are the things I want:
  • Better performance
    • It's not slow but not fast enough for me
  • Debugging utilities
    • I want to stop doing print debug
  • More libraries
    • It even doesn't have a library handling cookies, geez
  • R7RS-large support
    • Currently all R7RS-large libraries are supported
It's all basic things but no priority nor promise. Unfortunately, Sagittarius is not a popular Scheme implementation so I hardly get any feedback. So it's hard to see what's missing for other users. Above items are just what I want and may not for what users want. Plus, I often change my mind :)

In these couple of years, it feels one year is forever long. This is probably because I'm doing a lot of things. I wish 2015 will also be forever long year.

2014-12-29

datum->syntaxに潜む罠

マクロ関連のバグの話(もう何度目だろう・・・)

R6RSにはdatum->syntaxという手続きがある。あるデータ(シンボル、リスト何でも可)を構文オブジェクトに変換するというものである。基本的な考え方は非常に簡単で、第一引数で受け取った構文情報を第二引数で受け取った値に付与して返すと思えばよい。これを使うことでスコープを捻じ曲げることが可能になる。

さて、本題はここから。端的なバグは以下のコード:
(import (rnrs))

(define-syntax let-it
  (lambda (x)
    (define (bind-it k binding)
      (syntax-case binding ()
        ((var . val) 
         (let ((name (syntax->datum #'var)))
           #`(#,(datum->syntax k name) val)))
        (_ (error 'let-it "invalid form"))))
    (syntax-case x ()
      ((k ((var . val) rest ...) body ...)
       (with-syntax (((var1 val1) (bind-it #'k #'(var . val))))
         #'(let ((var1 val1))
            (let-it (rest ...) body ...))))
      ((_ () body ...)
       #'(begin body ...)))))

(let-it ((name . 'name)) name)
まぁ、特に何もない単にlet*を使いにくくしただけのコードなのだが、Sagittariusではこれがエラーになる。バグは敢えてdatum->syntaxで変換している箇所にある。一言で言えば、kの構文情報では変数の参照が出来ないというものである。実はこのケースのみだけで言えば直すのは簡単なのだが、let-itが局所マクロで定義された際等がうまくいかない。

自分の頭を整理するために多少問題を詳しく書くことにする。このケースでは最初のnamelet-itが使用された際の構文情報を持つが、二つ目のnameとはeq?での比較において別の識別子となる(ちなみにdatum->syntaxを使わなかった場合においてはマクロ展開器は同一オブジェクトにする)。この場合に環境の参照が同一の環境を持つ識別子を同一識別子と見なさないのでエラーとなる。なお、この挙動は歴史的理由(主に僕の無知)によるところが多い・・・

ここで、同一環境を含む識別子を同一オブジェクトとした場合に起きる問題を見る。マクロ展開器は以下の場合において識別子の書き換えを行わない:
  • 識別子がパターン変数の場合
  • 識別子がテンプレート変数の場合
  • 識別子が既に局所的に束縛されている場合
上記二つは特に問題にならないのだが、3つ目が以下のコードにおいて問題になる:
(let ()
  (define-syntax let/scope
    (lambda(x)
      (syntax-case x ()
        ((k scope-name body ...)
         #'(let-syntax
               ((scope-name
                 (lambda(x)
                   (syntax-case x ()
                     ((_ b (... ...))
                      #`(begin
                          #,@(datum->syntax #'k
                                (syntax->datum #'(b (... ...))))))))))
             body ...)))))

  (let ((xxx 1))
    (let/scope d1
      (let ((xxx 2))
        (let/scope d2
          (let ((xxx 3))
            (list (d1 xxx) ;; *1
                  (d2 xxx)
                  xxx      ;; *2
                  ))))))
)
同一環境を持つ識別子を同一識別子とみなすと、上記の印をつけた変数が両方とも3
を返す。マクロ展開器が識別子の書き換えを行わないため、全てのxxxが同一環境を持つからである。
これだけ原因がはっきりしているのだからマクロ展開器が展開するごとに識別子を生成しなおせばいいような気がしないでもないのだが、上記の歴史的理由により環境を参照するコードが自分でも理解不能な複雑怪奇なことになっているためなかなか手が出せないでいる。ここは一発腹を決めるしかないか。

追記:
上記のletで束縛されるxxxは最初のもの以外は全て同一の環境を持つ識別子に変換される。っで、(d1 xxx)は正しく最初のxxxのみをもつ、つまり変換された識別子と同一の環境をもつ、識別子に変換されるので環境の頭にある3が束縛されたxxxにヒットする。

問題はどうこれを解決するかなんだけど、ぱっと思いつく解決方法としては、束縛が発生するたびに識別子の書き換えを行い適切な環境に変更してやるというものだろうか。それをやることのデメリットとしては:
  • 式一つコンパイルするのにO(n^2)のコストがかかる
  • コンパイラが持つ構文全てをいじる必要がある
あたりだろうか。最初のはライブラリになっていればキャッシュが効くので初回のみと割り切れなくもないのだが、二つ目のが辛い。バグを埋め込まない自信がないという話ではあるのだが、コンパイラはかなりの数(10以上)の束縛構文を知っているので全て書き換える必要がある。ものぐさな僕には辛い話である。マクロ展開器の方でやれないか考えてみたのだが、それ自体は束縛構文が何かということを知らないのでどの識別子を書き換える必要があるのかが分からないという問題がある。とりあえず直せる部分だけ直して寝かせる方針かなぁ、いつもどおり・・・

2014-12-20

SRFI-117の紹介

(LISP Library 365参加エントリ)

今回は最新のドラフトSRFI-117を紹介します。今年一年SRFIの紹介をしてきましたが、今回が最終回になります。そこで現在SRFIのMLで議論されている最新のSRFIを紹介してみたいと思います。

SRFI-117はR7RS-largeにも提案されているSRFIです。このSRFIではリストを用いたキューを定義します。もともとはQueueという名前をそのまま使っていたのですが、議論の中でAPIの説明が実装に踏み込みすぎているという指摘から最近名前をリストキューに変更しました。

まだ最終ではないのでAPIは変わるかもしれませんが、以下のように使うことが可能です。
(import (srfi 117))

(define q (make-list-queue '(1 2 3)))
;; -> queue

(list-queue-front q)
;; -> 1

(list-queue-remove-front! q)
;; -> 1
;; queue will contain only 2 and 3 after this
実装が見えるといったのは、このSRFIではAPIの説明ほぼ全てにオーダーが指定されています。例えば、list-queue-remove-front!はO(1)で終了しなければならず、またlist-queue-remove-backはO(n)で終了する必要があります。

議論の中で話題になったのはコンストラクタAPIで、make-list-queue(元はmake-queue-from-list)がO(1)を指定しかつ与えられたリストが共有されなければならないというもので、これだと処理系が提供するキューがこのSRFIをサポートできないというものです。これにより、キューという一般的な名前からリストキューというより実装を表して名前に変更になりました。もしかしたら将来のSRFIで下請けのデータ構造に依存しないキューのインターフェース的なものが出てくるかもしれません。

ここでSRFIのプロセスとR7RS-largeへの提案のプロセスを簡単に説明します。R7RS-largeはSRFI上で議論されたものがscheme-report.orgのML上で決を採られます。有効票のうち半数以上が賛成であればR7RS-largeに取り入れられます。流れとしては
  1. SRFIに提案する
  2. scheme-report.orgのMLに上記のSRFIをR7RS-largeに提案すると宣言する
  3. SRFIのML上で議論する
  4. 最終SRFIになる
  5. scheme-report.orgで決を採る
というものになります。現状R7RS-largeに提案されたSRFIは111、112、113、114、115、116で、111と112が正式に採用されています。(残りは決を取っていないはずですが、ひょっとしたら見落としているかもしれません。)これらのSRFIはSagittariusでサポートされているので(113、114及び116
は0.6.0以降)興味があれば試してみると面白いかもしれません。

今回はドラフトSRFI-117を紹介しました。

2014-12-13

SRFI-42の紹介

(LISP Library 365参加エントリ)

SRFI-42は先行内包(訳:Scheme 翻訳規約)を定めたSRFIです。CLのloopのScheme版と思えばいいかと思います。このSRFIができることはかなり多く全てを紹介するのは難しいので触りだけみてみましょう。
(import (srfi :42))

(list-ec (: i 5) i)
;; -> (0 1 2 3 4)

(list-ec (: n 2) (: m 3) (cons n m))
;; -> ((0 . 0) (0 . 1) (0 . 2) (1 . 0) (1 . 1) (1 . 2))

(list-ec (:parallel (: n 3) (: m 3)) (cons n m))
;; -> ((0 . 0) (1 . 1) (2 . 2))
こんな感じで任意個数要素を持つリストを作ることが可能です。list-ec等のマクロは最後の式が評価結果として帰り(do-ecを除く)、それ以前の式で量子を指定します。量子はデフォルトでは入れ子になるので、同時に行う場合には:parallelで囲う必要があります。

SRFIで定義されている名前がSchemeの型から始まる場合は(例:list, vector)は最後の式が返した値の要素で満たされたものが返ります。戻り値が必要ない場合はdo-ecを使います。
(do-ec (: i 5) (print i))
;; prints: 
;; 0 
;; 1
;; 2
;; 3
;; 4
;; -> unspecified value
C等にあるwhileのようなことも以下のようにできます。
(string-ec (:while (: i 10) (< i 10)) #\a)
;; -> "aaaaaaaaaa"
:whileは最初の式で値を生成し、二つ目の式で終了条件を指定します。whileというよりはforに近いかもしれません。

これ以外の機能やジェネレータの拡張などScheme版loopと呼ぶにふさわしくいろいろ盛りだくさんなSRFIです。(正直なところかなり限られた機能しか使っていないのでよく分かっていないというのが・・・求む詳細な解説)

今回はSRFI-42を紹介しました。

2014-12-05

SRFI-41の紹介

(LISP Library 365参加エントリ)

SRFI-41はストリームを扱いSRFIです。 元々はSRFI-40があってそれが廃止になり、初のR6RS用SRFIとして決定されたという経緯があるみたいです。MLからは時系列が今一把握できないのでどういう風に遷移したのかは単なる推測です。どうでもいいのですが、SRFI-40は2004年8月22日に最終になり、SRFI-41は2007年10月21日に最初のドラフトが出ているのですが、後続のSRFI-42が2003年2月20日に最初のドラフトが出ていて、どういう経緯で番号をねじ込んだのかとかが気になってたりします。当時を知っている方がいらっしゃれば是非うかがいたいところです。

ストリーム自体はよく知られた概念かと思いますので、詳しい説明は省くことにします。このSRFIではストリームをリストとみなして扱えるようなAPIを提供しています。使い方は以下。
(import (rnrs) (srfi :41))

(define strm123 
  (stream-cons 1 
    (stream-cons 2 
      (stream-cons 3 stream-nil))))
#|
;; above can be written like this as well.
(stream 1 2 3)
|#
;; -> stream

(stream-car strm123)
;; -> 1

(stream-car (stream-cdr strm123))
;; -> 2

(stream-map (lambda (v) (* v v)) strm123)
;; -> stream

(stream-car (stream-map (lambda (v) (* v v)) strm123))
;; -> 1

(stream-car (stream-cdr (stream-map (lambda (v) (* v v)) strm123)))
;; -> 4
正直この例だと特に恩恵はありません。むしろ、いろいろ面倒なだけです。

例えばOCamlではファイルの読み込みを行うストリームがあります。このSRFIでも似たようなことが可能です。こんな感じ(SRFI本文から拝借)。
(define-stream (file->stream filename)
 (let ((p (open-input-file filename)))
    (stream-let loop ((c (read-char p)))
      (if (eof-object? c)
          (begin (close-input-port p)
                 stream-null)
          (stream-cons c
            (loop (read-char p)))))))

(define file-stream (file->stream "test.scm"))

(stream-car file-stream)
;; -> the first character of the file.
ファイルサイズが大きいと最後まで読み込んだ後にメモリの使用量が大変なことになるという難点があったりしますが(しかも束縛されているとGCもされないという二重苦)、必要になるまで読み込みは行わずまた、読み込んだ文字は常に再利用可能というメリットがあります。また、このSRFIはport->streamというAPIも用意していて、ポート位置の指定が不可能なポート等には便利に使えそうです(ただし文字ポートにしか使えないので、バイナリがいる場合は自作する必要があります)。

参照実装ではストリームは伝統的なthunkで表現されていますが、処理系によってはもう少し賢く実装しているかもしれません(見たことはないですが・・・)。

今回はSRFI-41を紹介しました。

2014-12-01

R7RSポータブルライブラリを書く際の落とし穴

この記事はLisp Advent Calendar 2014の2日目として投稿されました。

R7RSでは処理系毎の差異を吸収可能な構文cond-expandが採用されポータブルなコードが書きやすくなった。では実際のところどれくらい書きやすくなったかという話は寡聞にして聞かないので、ある程度実用的なライブラリを書いて検証してみた。結論から先に書くと、R6RS時代とそこまで変わっていないか、多少不利というのが僕個人の感想である。その理由を一つずつ見ていくことにしよう。

【ライブラリ拡張子】
可搬性の高いライブラリを書くのであれば、外せないポイントの一つである。R7RSでは既定されていない部分であるため、最大公約数を選ぶしかない。知る限りではSagittariusとGaucheは拡張可能である。参照実装であるChibi Schemeが.sldを採用したのでそれに追従する処理系が多い(例:Foment)。再度R7RSでは既定されていないので、処理系依存になる。例えばpicrinは.sldをサポートしていないし、しばらくサポートされなさそうである。これも踏まえてポータブルに書くとなると、実装とライブラリ定義は完全に切り離す必要がある(Chibiは常にこの方式を採用している)。しかしなが、それでは実装者の負担が大きくなるので線引きをする必要はある。現状であれば.sldを採用するのが妥当なところであろう。

余談ではあるのだが、Gaucheでライブラリ拡張子を追加するのは-eオプションを使う必要がある。具体的には-e '(set! *load-suffixes* (cons ".sld" *load-suffixes*))'のようなものが必要になる。append!でもいいのだが、そうすると.scmの方が優先順位が高くなるので嵌ることがある。(嵌った)

【サポートされてるSRFI】
R7RSの範囲だけでもある程度のことはできるのだが、SRFIくらいは許容範囲に入れないとある程度の範囲が狭い。例えばマルチスレッドやソケット等はSRFIを使わないと完全に処理系依存になる。
しかし、これがポータブルなライブラリを書く際の落とし穴になる。 例えば僕が書いたライブラリは以下のSRFIを要求する:
  • SRFI-33(withdrawn)/SRFI-60もしくは(rnrs)
  • SRFI-106
  • SRFI-19(サポートされていれば)
この中に文字列を扱うSRFI-13がないのには理由がある。Chibiがサポートしていないからである。(ちなみにFomentもサポートしていない。) 参照実装から持ってくるという方法もあるといえばあるのだが、ロードパスの問題も出てくる。例えばFomentはSRFI-1もサポートしていないがChibiはしているので、サポートしていないSRFIだけを入れるというのは困難である。特に組み込みでサポートしている場合は参照実装に置き換えると性能が落ちる可能性が出てくる。

ここでは問題としてChibiを指しているが、SagittariusにもあってSRFI-60をサポートしていないのである。理由は面倒だからの1点なのだが、流石にちょっと無視できなくなってきたかもしれない。自分で自分の足を打ち抜いてる感がすごいので*1・・・

余談だが、ChibiはSRFI-106をサポートしていない。なので処理系依存のコードが貼り付けてある。

【R6RSにあってR7RSにない手続き】
R7RSはR6RSで定義された手続きの大部分を提供しない。 特にバイトベクタ周りの手続きがごっそり抜けている。例えばbytevector-u32-refとかである。単に互換手続きをScheme側で実装してやればいいだけなのでそこまで問題にならないが、これがbytevector-ieee-double-refとかだと骨が折れること間違いなしだろう。(今回は16ビット整数と32ビット整数だけだったのでそこまででもなかったが。)

R6RSに限った話ではないが、処理系によってはライブラリもしくは組み込みで提供されている手続き等があり、それらは性能を出す上で重要になってくるかもしれない。例えば上記のバイトベクタ周りの手続きはSchemeで実装した場合複数回のメモリ割付が必要とされる可能性があるが(bytevector-u64-ref等)、処理系が組み込みでサポートしていた場合にはメモリ割付は1回に抑えられるかもしれない。タイトなループで呼ばれる際には無視できない要素になる可能性がある。

【ポータブルなライブラリを書くにあたって】
ではどうするか?というのはライブラリを書く上で重要になるだろう。残念ながら、これといった指標のようなものは今のところ僕個人の中にはない。そして、残念ながらR7RSポータブルなライブラリの絶対数も少ないこと等、既存のものから学ぶという方法もとりづらい。今後の参考になるよう今回書いたライブラリから学んだ点を列挙する。
  1. R7RS外の機能の分離
  2. サポートする処理系の具体的イメージ
  3. 習熟度の低い処理系の性能はあきらめる
#1はサポートされていないSRFIの救済を含む。ライブラリの要件に必要なSRFIを列挙すればいいのだが、多くの処理系で使えるようにするにはそれすらも最小限に抑えた方がよい。例えば今回の例ではSRFI-13があるが、必要だった部分は非常に小さかったのでライブラリ側で実装し依存度を減らした。

#2は対象とする処理系をある程度列挙することである。今回のライブラリではスタートポイントとしてSagittarius、GaucheそしてChibiを選択した。それぞれの処理系に癖があり、細かい点で嵌ったものもある。例えばGaucheのソケットポートはバッファを確保するのでコマンドを任意のタイミングでサーバに送る際にはバッファをフラッシュする必要があった。(他にもwith-exception-handlerがSEGVるとかあるが、それはバグを踏み抜いただけということで。) 複数の処理系で走らせることができれば処理系が許容する未定義動作をある程度意識して回避することが可能である。R7RSでは未定義動作の範囲が広く、また処理系の拡張をかなり許しているため、ポータブルなコードを書く際にはこれを踏まないようにするのが鉄則になるだろう。(今回の動作はSRFI-106なので、自分で足を打ち抜いたのではあるが・・・)

#3は性能を出すポイントというのは処理系ごとに違うので習熟度が低い処理系であれば、ポータブルに書くことを優先すべきである。今回は重たい処理(MD5ハッシュやバイナリ変換)に関してSagittariusでのみ処理系が用意している(バイナリ変換はR6RS由来だが)手続きを用いた。GaucheにもMD5ハッシュはあるが、R7RS+SRFIの範囲で書かれているものを流用することにした*2。当然だが、サポートする全ての処理系に依存するコードで書いたとしても可能な限りポータブルなコードは残さなければならない。仮にR7RSやSRFIで既定されていないものであっても、既定の動作としてエラーを投げるものを組み込んでおくだけでライブラリの一部が使えたり、後のサポートを容易にすることが可能である。

上記のポイントに加えて、ある機能を処理系依存で切り分ける際に必ず一つはR7RS+SRFIの範囲に動くようにした。それぞれの処理系の癖やバグを回避する際に必ず一つはポータブルなパスを通るようにすることで、可能な限りポータブルに出来たと思う。(スペックだけを見るのであれば、Fomentでも何の変更もなく動くはずである。 )

【結論】
R7RSに限ったことではないが、ポータブルなライブラリを書くことは非常に大変である。以前にR6RSポータブルなライブラリを書いた際にも同様な感想を持ったが、R7RSは決定からの時間が浅いからか、カバーする範囲が狭いからか、処理系ごとの癖が強いからなのか分からないがR6RSのときよりもライブラリ本体ではない部分のコードを書く量が多かった気がする。R6RSポータブルなライブラリはJSONを扱うものなのでその差かもしれないが(サポートした処理系全てがかなりの数のSRFIをサポートしていたというのも大きな要因かもしれない)。しかしながら、ある程度の制限はあるもののポータブルなライブラリを書く手段が言語レベルで既定されているというのはやはり大きな利点であると思われる。

長々と書いたが一言でまとめれば、もっとR7RSなSchemeを使おうということになる。もちろんR6RSでも構わない。

*1: 入れた。次のリリースからは使えるようになる。
*2: 正直なところ、GaucheやChibiをタイトに使うことはほとんどないので、Sagittariusで性能が出ればいいというのもある。他の処理系で性能がいる場合はPull Reqを送っていただけるとありがたい。