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.

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が局所マクロで定義された際等がうまくいかない。

自分の頭を整理するために多少問題を詳しく書くことにする。このケースでは最初のnameはlet-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以上)の束縛構文を知っているので全て書き換える必要がある。ものぐさな僕には辛い話である。マクロ展開器の方でやれないか考えてみたのだが、それ自体は束縛構文が何かということを知らないのでどの識別子を書き換える必要があるのかが分からないという問題がある。とりあえず直せる部分だけ直して寝かせる方針かなぁ、いつもどおり・・・

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を紹介しました。

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を紹介しました。

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を紹介しました。

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等)、処理系が組み込みでサポートしていた場合にはメモリ割付は１回に抑えられるかもしれない。タイトなループで呼ばれる際には無視できない要素になる可能性がある。

【ポータブルなライブラリを書くにあたって】
ではどうするか？というのはライブラリを書く上で重要になるだろう。残念ながら、これといった指標のようなものは今のところ僕個人の中にはない。そして、残念ながら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を送っていただけるとありがたい。