2012年を振り返って

今年はなんだかいろいろ激変した感じがある年ではあるが、プライベートなことを振り返ると気分がへこむのでとりあえずはSagittarius周りのことだけで。

【達成したこと】

• R6RSマクロ展開器が標準により準拠した
• R7RS対応がほぼ終わった
• 月1リリースの継続

あまり目標を立ててないので、自分の中で達成したというのはないなぁ。自分がほしい機能をいっぱい詰め込んだ「俺々処理系」度がえらく進んだ感があるが(リーダの置き換えとか)。


【来年やりたいこと】

• ドキュメント
• ライブラリの充実
• 使い勝手が悪い(と個人的に思っている)部分の改善

ドキュメントは書いてないというのもあるのだが、1個の巨大なファイルになっているのが気になってきたのでその辺も直したい。
ライブラリは仕事で使う分でも足りないなぁと思う部分が出てきたので(主にバイナリいじるようなの)その辺を充実させていきたい。industriaのpackみたいなのがあると汎用的に使えるか？
使い勝手は、僕個人の感想なのだが、使い捨てのスクリプトを書く際にいちいちimportを書くのがさすがに面倒だなぁと思ってきたので、その辺を何とかしたい。
処理系本体に大きな変更を加える気は今のところないのだが、0.5.0か0.6.0あたりでビルド時のオプションで自前のGCを選択できるようにしたいと思っている。ただ、そこまで個人的にやれるかというのはかなり疑問なのであくまで「やりたい」程度ではあるが。

基本的に「必要ドリブン」(泥縄とも言う)開発スタイルなので、来年やりたいことというのは、現状で改善したいことでしかなく、下手をすれば1月中に終わるというものだったりもするのだが。

何はともあれ、来年もよろしくお願いいたします。

TLVパーサがほしい

最近仕事でAPDUをいじる必要があるのだが(正確には眺めてるだけなんだけど・・・)、中に入ってるデータとかSIMが返すデータとかがTLV形式であることが多い。っで、TLV自体は別に何か特別な仕様というわけでもないのでこのパーサがあってもいいかなぁと思っていたりする。

問題は、現在既にあるASN.1パーサは基本的にはTLVパーサの上にASN.1のオブジェクトを被せるという形になっている点だろう。TLVだけに特化したのを別に作るのは馬鹿らしいのでこれを分離する方向にしたい。ということでちょっと実装方針を考えることにする。

現状のASN.1パーサはDERとBERに特化した形になっているので不定長のバイト列を処理することができるのだが、TLV形式だけならこれは不要になる。っが、これを外すことは当然だができない。また、DER、BERだとタグ部分が1バイトを超えることがあるが、他の形式だとたいてい1バイトである。(この辺ちょっと自信ない。現状の実装が一般的な気もする。)

となると、タグを読む、長さを読む、値を読む手続きとそれらから得られたデータから最終的なオブジェクトを構築する手続きを渡して、TLVパーサを作るような形にするといいだろうか？ でも、そこまでやるなら分離する必要ないよな？オブジェクトの構築だけを外出しにすると、今度は不定長データの処理に困るし、どうしようかな。

Enbug

かなり大きめなバグを0.4.0で埋め込んだみたいである。問題になるのは以下のコード。

(define (foo)
  (define (bar n) (print n))
  (bar 1)
  (let ()
    (define (bar n) (print 'hoge))
    (bar 1)))

何の変哲もないコードだが、0.4.0では「CレベルのASSERTで落ちる」という脅威の振る舞いをしてくれる。

マクロ直しの一環でのEnbugなのだが、正直全く気づかなかった。久しぶりにベンチマークでも取るかとGambitベンチマークを走らせてはじめて発覚。この問題の面白い(いやな)ところは、実行されたインストラクションから見ると問題の箇所はラムダリフティングに見えた点。実はそこではなく、barが2箇所で使われている点にある。

なぜこんなバグを混入することになったかといえば、R6RS及びR7RSではdefine-syntaxが内部defineと同様に書けることに起因する。たとえば以下のコード。

(let ()
  (define even?
    (lambda (x)
      (or (= x 0) (odd? (- x 1)))))
  (define-syntax odd?
    (syntax-rules ()
      ((odd?  x) (not (even? x)))))
  (even? 10))

こんなコードがあった際に、コンパイラはまずマクロのコンパイルをする。その後、内部defineのコンパイルをする。っが、実は一箇所大きめの落とし穴があって、どちらのコンパイルの際でも内部defineの名前を局所変数として登録する。つまり2重登録が発生する。っで、これの解決の方法がまずかった。

2重で登録されているのなら、2つ目に来るものは無視すればいいのだろうと安易に考えたのだが、そのをしたら最初のコードが動かなくなった。ある意味当たり前である。同名がくることは一切考えていなかったのだから。

リリース直後に気づいた不具合の致命的度としては最大級な気がする・・・orz

Sagittarius 0.4.0リリース

Sagittarius Scheme 0.4.0がリリースされました。ダウンロード。
今回のリリースはマイナーバージョンアップリリースです。大きな変更点は以下、

• R6RS準拠度(マクロ周り)の改善
• R7RS small (draft 8)の要求仕様への準拠

修正された不具合

• datum->syntaxが与えられたテンプレート識別子を解決しない不具合が修正されました。
• 深くネストしたリストを出力するとSEGVを起こしていた不具合が修正されました。
• import句でのforキーワードが無視されていた不具合が修正されました。
• ただし、run、expandなどのフェーズ指定句は従来どおり無視されます。
• let-syntax及びletrec-syntaxがR6RSモードでスコープを作っていた不具合が修正されました。
• カスタムコーデックがtranscoded-portで使用できない不具合が修正されました。
• path-map及びpath-for-eachに:all #fを渡した際に処理が終わらない不具合が修正されました。
• bytevector-u64-set!及びbytevector-s64-set!が値を正しくセットしない不具合が修正されました。
• port-eof?がカスタムポートに対して使用できない不具合が修正されました。
• random-integerが与えられたサイズと同じ値を返すことがある不具合が修正されました。
• (eqv? 0.0+0.0i 0.0-0.0i)が#tを返す不具合が修正されました。

改善点

• マクロのR6RS準拠度が大幅に改善されました。
• リーダマクロがファイル単位からポート単位に変更になりました。
• 4096文字を超える文字列の読み取りが可能になりました。
• Debian Linuxがサポートされました。

新たに追加されたライブラリ

• SRFI-25及びSRFI-78が追加されました。
• ただしSRFI-78はcheck-ecがR6RSモードでは動きません。

パターン変数

リリース直前にバグに気づいた。もちろんマクロ周り・・・
問題となるのは以下のようなコード。

(define-syntax loop
  (lambda (x)
    (syntax-case x ()
      [(k e ...)
       (with-syntax
           ([?break (datum->syntax #'k 'break)])
         #'(call-with-current-continuation
            (lambda (?break)
              (let f () e ... (f)))))])))
(let ((n 3) (ls '()))
  (loop
   (if (= n 0) (break ls))
   (set! ls (cons 'a ls))
   (set! n (- n 1))))

R6RSテストスイーツでは?breakの部分はbreakになっている。これがすごく長い間誤解を招いていた。何が問題かといえばコードではなく、(もちろん)実装の方で、現状の実装ではマクロ展開後の式をもう一回総舐めするのだが、その際に上記のbreakを正しいものに置き換える処理をしている。ただ、その際にパターン変数の中身ではなく、パターン変数そのものを見て置き換えるので上記のコードだと?breakが対象になる。

もちろん、よく考えればそれはおかしいと気づくのだが、なぜかずっと現状の実装が正しいと思い込んでいた。っで、R6RSへの準拠度を高めようとマクロの書き直しを終えた後に、いろいろなマクロを試していて気づいたと・・・orz

気づいたからには直さないと気が済まないので現在修正中なのだが、ほぼ全てのテストは通るのに、SRFI-86のテスト1個だけが通らない。他のテストは勘所などが分かったのだが、こいつは長巨大マクロライブラリなので全く分からん。まず間違いなく誤参照をしているのだけど、どこがそれを引き起こしているのかが分からない。

リリースを引き伸ばすか、こいつは次のリリースで直すか悩むところである。R7RSのドラフト8対応と称して出してしまおうか・・・(悪魔の囁き

R7RS 8thドラフト斜め読み

7thドラフトから1ヶ月しか経っていないのにもう8thが出るとは。ちょっと油断していた。

今回のドラフトは7thのtypoと非正確数のeqv?あたりぐらいだろうと思っているので軽く斜め読み。Chibi-Schemeもこれにあわせてか、0.6.1とバグフィックス版を出してきている。

前回からの変更点

• (eqv? 0.0 -0.0)が処理系が負の0.0を識別するなら#fと明示された
• read-bytevector!の引数順が変更になり、それに伴ってオプショナル引数が4つに増えた

これくらいしか見つけられなかった。さすがに斜め読みすぎたか。eqv?の変更はメーリングリストでかなり険悪な状態までいっていたりしてどう落ち着くのか不安ではあったが、R6RSとの整合性が保たれていたのでちょっと安心。でも、未だに(eqv? 0.0 -0.0)が#fでなければならないプログラムを見たことないが、atanとかバリバリ使う人だと問題になるんだろうか？

やべ、こんなに変更点がないとは思っていなかった。書くことがないw

とりあえず、宣伝。
0.3.8でドラフト7に対応したんだけど、Chibiのテストが結構こけてたりしてたんだけど、次のリリースでは全て問題なく通る。それにプラスして、Chibiでは(たぶん、まだ)サポートされていないinclude-library-declarationsもサポートされているので、現状ではR7RS Smallをフルサポートしている処理系ということになる。今週末リリースする予定(あくまで予定)。

Rewrote case-lambda

Sometimes it's good to review what I've done so far. Yes, I've found something not efficient and it can be more efficient. This time it was case-lambda.

The original was SRFI-19 and since R6RS it's a standard macro (or syntax) for Scheme. However neither of implementations is efficient. At least it can be written better in R6RS. The problem of the reference implementation is it creates closures per lambda formals and apply it with given arguments. If the implementation is smart enough, the apply could be inlined however Sagittarius is not so smart (unfortunately).

If the implementation is not smart enough, then programmers need to be smart to let compiler emit efficient codes. So I rewrote it. This is what I think at least better than the references.

;; this is almost only R6RS except reverse!
(define-syntax case-lambda-aux
  (lambda (x)
    (define (construct args formals clause*)
      (define _car #'car)
      (define _cdr #'cdr)
      (define (parse-formals formal args inits)
        (syntax-case formal ()
          (() (reverse! inits))
          ((a . d)
           (with-syntax ((arg `(,_car ,args))
                         (args `(,_cdr ,args)))
             (parse-formals #'d #'args
                            (cons (list #'a #'arg) inits))))
          (v
           (reverse! (cons (list #'v args) inits)))))
      (with-syntax ((((var init) ...) (parse-formals formals args'()))
                    ((clause ...) clause*))
        #'(let ((var init) ...) clause ...)))
    (syntax-case x ()
      ((_ args n)
       #'(assertion-violation #f "unexpected number of arguments" args))
      ((_ args n ((x ...) b ...) more ...)
       (with-syntax ((let-clause (construct #'args #'(x ...) #'(b ...)))
                     (expect-length (length #'(x ...))))
         #'(if (= n expect-length)
               let-clause
               (case-lambda-aux args n more ...))))
      ((_ args n ((x1 x2 ... . r) b ...) more ...)
       (with-syntax ((let-clause (construct #'args #'(x1 x2 ... . r) 
                                            #'(b ...)))
                     (expect-length (length #'(x1 x2 ...))))
         #'(if (>= n expect-length)
               let-clause
               (case-lambda-aux args n more ...))))
      ((_ args n (r b ...) more ...)
       #'(let ((r args)) b ...)))))

(define-syntax case-lambda
  (syntax-rules ()
    ((_ (fmls b1 b2 ...))
     (lambda fmls b1 b2 ...))
    ((_ (fmls b1 b2 ...) ...)
     (lambda args
       (let ((n (length args)))
         (case-lambda-aux args n (fmls b1 b2 ...) ...))))))

The trick is really simple. Just let macro compute the given arguments. Even length is called only once.

With this code, at least on Sagittarius, the compiler emits better code than references (there is no extra closure created).

最後の砦

マクロの書き換えを始めて1週間(以上か？)、大詰めまで来ている気がする。美しくなかった機能をばっさりと切り捨て、マクロ展開器は(個人的に)かなりシンプルになったと思う。既存のテストが全て通るようになり、いよいよ本丸のindustriaを走らせて見たら、以前と同じエラーで落ちる。これは何かを見落としているなと思い、落ちている原因のdo/unrollマクロを眺めることにした。

正直、中で何をしているのか理解するのに時間がかかるくらいでかく複雑(に僕には見える)マクロだが、本質的な原因は以下のマクロが動かないことにあることが分かった。

(import (rnrs))
(define-syntax expand-it
  (lambda (x)
    (define (gen-return var) (with-syntax ((v var)) #'v))
    (syntax-case x ()
      ((_ (v init) expr ...)
       (with-syntax ((r (gen-return #'v)))
         #'(let ((v init))
             (when (= v r)
               expr ...)))))))

(expand-it (v 1) (display 'ok) (newline)) 

Chezで試したが当然動く。正直、何がいけないのかすでに分かっていて、以前あったパターン変数の問題の展開された識別子版である。
入力として与えられてvが二箇所のsyntaxで展開されているためにそれぞれ別の識別子として出力されるのが問題なのである。

それこそ、マクロ展開器との格闘を始めて結構長いと思うが、このパターンは完全に見落としていた。こんなマクロ書いたことないし、見たこともないからである。パターン変数の問題はいくらか書いたし、見たことがあったので何が原因かも分かっていたのだが、これは思いもよらなかった。なんというか、目の前に大穴が空いているのに全く気づかなかった気分である。

パターン変数の際と同様の方法で解決するとするか。

しかし、この1週間でマクロ展開の実装は所詮環境の参照と識別子のリネームだけなんだと痛感させられた。ただ、それが異様に面倒なだけで・・・

expanded internal define

It's aboud the macro expander of Sagittarius Scheme. I'm re-writing it to get better conformity with R6RS. Now I've got a (well not only one) problem and found a bug of current version.

Short description of the bug;

;; Doesn't matter what equal? return.

;; Bug 1
(let ()
  (define-record-type (pare kons pare?)
    (fields (mutable x kar set-kar!)
     (immutable y kdr)))
  (define a (kons (vector 1 2 3) '(a b c)))
  (define b (kons (vector 1 2 3) '(a b c)))
  (equal? a b))
kons ;; -> #<closure kons>
;; this should be &assertion of unbound variable

;; Bug 2
(let ((c #t))
  (define-record-type (pare kons pare?)
    (fields (mutable x kar set-kar!)
     (immutable y kdr)))
  (define a (kons (vector 1 2 3) '(a b c)))
  (define b (kons (vector 1 2 3) '(a b c)))
  (equal? a b))
;; -> &assertion

The first one is obviously wrong, it broke the definition of internal define. The second one is releated to comple time environment lookup. The kons is defined by define-record-type and it must be the same identifier as the one in internal define. But it's not. That's because macro expander re-name it to different identifer.

The simplest solution I have tried was to wrap all given expression first then expand macros. It's simple it worked (mostly) but broke constant literals such as quoted lists or vectors. The problem was not only it but also broke some other codes (mostly related with er-macro-transformer used for generating bootstap code and R7RS). So I've decided not to do this (even though I feel like it's the easier way to do it).

The second solution is modifying the environment lookup process. An identifier can hold some environment without any restriction on current branch and if I can find a better way to look up proper variable from compile time environment, it can be resolved. The problem is I don't know how...

Consider the case of Bug 1. The kons and environment have following frames;

;; kons identifier's frame
((0))
;; when 'a' is being compiled
((0 (kons#user . #(lvar ...)) ...) ;; kons#user is an identifier
 (0)) ;; &lt-- the same environment as the kons identifier

So when a is being compiled, compiler can see the same environment at the very top of the frame chain. But how can we assume kons#user and kons in internal define are the same variables? If the root of the frame are the same, would we be able to assume? Or when it's expanded to internal define, should it be stripped to mere symbol?

Hmm..., I need to think ...

SchemeでReader Macro

この記事はLisp Reader Macro Advent Calendar 2012の記事として書かれました。

3日目はSchemeでリーダマクロを使ってみます。

僕が知る限り、Schemeの仕様にはユーザ定義のリーダマクロはありません。しかし、いくつかの処理系は独自にそれらを定義する方法をもっています。僕が知る限りではRacket、Gambit、Chicken、Sagittarius(拙作)は独自のリードテーブル拡張手続きを持っています。前2つはあるということくらいしか知らないので、ここでは拙作Sagittariusのリーダマクロの簡単な使い方、及びこれが使えると何がうれしいかということを宣伝を兼ねて紹介します。

世界的にはRacketがよく使われている(らしい)のですが、日本でSchemeと言えばGaucheがまず挙げられるのではないでしょうか。しかし、GaucheはR5RS準拠の処理系ということで、R6RSで書かれたライブラリを実行することが不可能です(2012年12月3日現在)。でも、Gaucheの独自拡張されたリーダマクロを使いつつ、R6RSのライブラリも使いたい！そんなこと考えたことありませんか？そこでSagittariusの出番です(宣伝ここまで)。

SRFI-14な文字セットをリード時に読み込むことを考えます(*1)。Gaucheでは以下のように書けます。

#[a-zA-Z] ;; -> 文字セット(#[a-zA-Z]と表示されます)

これはGaucheの独自拡張なので、他のScheme処理系とは互換性がありません。でも便利そうですよね？じゃあ、こう書けるようにしてみましょう！

(library (char-set reader)
    (export :export-reader-macro)
    (import (rnrs) (sagittarius reader)
            (srfi :14))

  (define-dispatch-macro charset-reader #\# #\[
    (lambda (port subc param)
      (let loop ((cs (char-set-copy char-set:empty)))
        (let ((c (get-char port)))
          (if (char=? c #\])
              cs
              (let ((nc (lookahead-char port)))
                (cond ((char=? nc #\-)
                       (get-char port)
                       (let ((c2 (get-char port)))
                         (if (char=? c2 #\])
                             (char-set-adjoin! cs c nc)
                             (loop (ucs-range->char-set!
                                    (char->integer c)
                                    (+ (char->integer c2) 1)
                                    #f
                                    cs)))))
                      (else
                       (loop (char-set-adjoin! cs c))))))))))
)
#!read-macro=char-set/reader
'#[a-zABC] ;; -> #<char-set #\A-#\C #\a-#\z>
#[a-]      ;; -> #<char-set #\--#\- #\a-#\a>

たったこれだけでGauche互換な文字セットリーダが書けます(*2)。
2日目の記事を読まれた方には簡単すぎるかもしれませんが、簡単な解説です。上記のコードは#\#と#\[の組み合わせをリーダマクロとして使用することを宣言しています。(CLでいうset-dispatch-macroと同義。)定義はリファレンスマニュアルを参照していただくとして、問題の中身です。コードを見ればすぐに分かるレベルの単純なものですが、最初に空の文字セットをコピーして読み取った文字、もしくは文字範囲(#\-でつながっている文字)を文字セットに破壊的に追加していき、#\]を読むまで続けます。(ちなみに、EOFまで読んでしまうとchar=?が&assertionを投げます。あまりよくない振る舞いですので、実用する際はeof-object?で検出して適切な例外を投げた方がいいでしょう。)

しかし、最新のリリース(0.3.8)で上記のコードを使うとキャッシュを壊すので以下のように書く必要があります。

(library (char-set-good)
    (export :export-reader-macro)
    (import (rnrs) 
            (sagittarius reader)
            (rename (only (srfi :1) alist-cons) (alist-cons acons))
            (srfi :14))

  (define-dispatch-macro char-set-reader #\# #\[
    (lambda (port subc param)
      (let loop ((ranges '()) (chars '()))
        (let ((c (get-char port)))
          (if (char=? c #\])
              `(char-set-union (string->char-set ,(list->string chars))
                               ,@(map (lambda (range)
                                        `(ucs-range->char-set 
                                          ,(car range) ,(cdr range))) ranges))
              (let ((codepoint (char->integer c))
                    (nc (lookahead-char port)))
                (cond ((char=? nc #\-)
                       (get-char port)
                       (let ((c2 (lookahead-char port)))
                         (cond ((char=? c2 #\])
                                (loop ranges (cons nc chars)))
                               (else
                                (get-char port)
                                (loop (acons codepoint (+ (char->integer c2) 1)
                                             ranges)
                                      chars)))))
                      (else
                       (loop ranges (cons c chars))))))))))
)
#!read-macro=char-set-good
(import (srfi :14))
#[a-zABC]  ;; -> (char-set-union (string->char-set "CBA") (ucs-range->char-set 97 123))
#[a-]      ;; -> #<char-set #\--#\- #\a-#\a>

これは、一部の組込みオブジェクトをキャッシュ機構がうまくキャッシュできないことに起因しています。次期リリースではある程度この問題が解決される予定です(少なくとも文字セットとハッシュテーブルは最新のHEADでは解決されています)。ユーザ定義のオブジェクトに対しては明示的にキャッシュとして書き出し、及び読み込みをするための手続きを定義することが可能です。

リーダマクロは処理系依存な機能な上に、処理系によっては(主にSagittariusですが)制限もあったりと使いどころが難しいものかもしれません。しかし、SRFI-105等のリーダ拡張を必要とするライブラリにScheme側のみで対応できたり、処理系の独自拡張の差異を吸収できたりと便利かつ強力な機能でもあります。

3日目はSchemeでもリーダマクロを使う方法を紹介しました。

*1: Sagittariusでも正規表現の読み込みははC側で実装されているので例として使いにくかったのです。
*2: 実際にはGaucheの文字セット読み取り機能はもっと多機能なのでこれだけだと完全に互換とはいえないですが・・・

R6RSとR7RSのライブラリ比較

この記事はLisp Advent Calendar 2012の3日目の記事として書かれました。

3日目は最近出たR7RSドラフトセミファイナル(とWG1が読んでいる)と、R6RSのライブラリシステムの文法的な違い(意味的なものも多少)を見ていこうと思います。

まずは、R6RSのライブラリのおさらいです。R6RSは制定されてすでに数年(2007年だったっけ？)経っているので、皆さんもうご存知ですよね。なので以下はごく簡単な例；

(library (foo)
   (export bar)
   (import (only (rnrs) define quote))
  (define bar 'bar))
#|
ライブラリ構文の定義
(library <library-name>
   (export <export-spec> ...)
   (import <import-spec> ...)
  <body> ...)
|#

R6RSのライブラリは暗黙もしくは明示的なマクロ展開フェーズを持ちます。これはマクロ内で使われる手続きと、ランタイムで使われる手続きを明示的に分ける必要があったから(らしい)です。(個人的にこのフェーズ分けは考えるのが面倒なので、暗黙的に解決してくれる処理系の方が好きです。好みの問題ですけど。)

次はR7RSのライブラリの例；

(define-library (foo)
  (import (scheme base) (scheme write))
  (begin (define foo 'foo)
         (define (print . args) (for-each display args)(newline)))
  (define (printw . args) (for-each write args)(newline))
  (export foo print)
  (export bar)
  (begin (define bar 'bar))
  (cond-expand
   ((library (srfi 1))
    (import (rename (only (srfi 1) alist-cons) (alist-cons acons))))
   ((library (srfi :1))
    (import (rename (only (srfi :1) alist-cons) (alist-cons acons))))
   (else
    (define (acons a b c) (cons (cons a b) c))))
  (export acons))
#|
ライブラリ構文の定義
(define-library <library-name>
   <library-declaration> ...)
|#

あえて違いを出すように書いてありますが、普通はexportとimport句はまとめると思います。
R7RSではR6RSと違い順番がライブラリ定義の順番及びその個数が規定されていません。なので、上記のコードは既存のR7RS処理系(ChibiとSagittariusしか知らない)で正しく動きます。(規定されていないので処理系依存になるかもしれません。)
R7RSのimport句はR6RSとは異なりforがありません。これはR7RSではマクロの展開フェーズが規定されていないからです。処理系は暗黙的にしかマクロ展開フェーズを持つことができません。(問題になる処理系の方が少ない気はしますが)
一方export句でもrenameのあり方がR6RSとは異なります。R6RSではrename句の中に複数の識別子を定義することができましたが、R7RSでは一つのrenameに対して一つの識別子しか定義することができません。
また、cond-expandはSRFI-0のものとは多少違い、featureとしてlibraryが追加されています。これによってライブラリが存在するかのチェックが可能になり、上記のように無ければ定義、みたいなことが可能(なはず)です。
また、以下の例はR7RSが既存のR5RSで書かれたプログラムをそのまま使用することが可能であるということを強く意識して作られたことを示す例です。

;; bazz.sls (for Sagittarius) or bazz.sld (for Chibi)
(define-library (bazz)
  (export bla)
  (import (scheme base))
  (include "bazz.scm"))

;;--
;; bazz.scm
(define bla 'bla)

ライブラリ内で使用されるinclude、include-ci(case insensitive)はライブラリ上にそのままファイルの内容が展開されるイメージです。処理系によっては以下のように解釈するかもしれませんが、まぁ無視できる程度の差異でしょう(Sagittariusはこのように解釈する)。

(define-library (bazz)
  (export bla)
  (import (scheme base))
  (begin (define bla 'bla)))

事実、Chibi-Schemeのほぼ全てのライブラリはincludeを用いて記述されています。また、今回のドラフトから追加されたinclude-library-delarationsは以下のように使えば処理系ごとの拡張子の違いを簡単に吸収することが可能です。(ただし、現状ではSagittariusのみがこの構文をサポートしている状態です)。

;; boo.sls or boo.sld
(define-library (boo)
   ;; もちろん、この上下にいろいろ書いてもOK
   (include-library-declarations "boo.decl"))

;;--
;; boo.decl
(export bah)
(import (scheme base))
(include "boo.scm")

;;--
;; boo.scm
(define bah 'bah)

include-library-declarationsはinclude、include-ciとほぼ同様の動作をしますが、include先のファイル(この場合はboo.decl)は<library-declarations>で構成されている必要があります。R7RSの議論の中ではこの構文は巨大なexport句を外出しにし共有化するために作られてのですが(*1)、このような使い方もできるのではと思っています。

R7RSはまだドラフトで上記の構文を試せる処理系はまだ少ないですが(2012年12月現在)、多くの処理系製作者がすでに追従するということを表明しています(*2)。個人的にはR7RSの構文の方がR6RSに比べて柔軟かつ処理系の差異も吸収しやすいのではと考えています。

3日目はR6RSとR7RSのライブラリ構文の比較を行いました。

*1: たとえば(srfi :1)と(srfi :1 lists)は同一のexport句を持ちますが、R6RSのライブラリではどちらのライブラリも同一のexport句を記述する必要があります。Sagittariusは:allキーワードがあるので、多少手が抜けたりしますが・・・
*2: Kawaはすでに可能な限り追従するとR7RSのメーリングリスト上で製作者が言っています。Larceny、Gauche、及びChickenも最初のドラフトの段階では追従するということを回答していました。参照

Andre van Tonderの展開器を読む

やっぱりマクロ周りの問題は割りと大きくのしかかってくる感じなので、まじめに戦略を練るために既存の展開器を理解しようかなぁと思い読み始める。

とりあえず以下が理解したこと；

• マクロ展開時にユニークなマークを作成
• colorとなっているもの
• これによってbound-identifier=?を実装している
• 展開フェーズはdefine-syntaxが現れると+1される
• Sagittariusは暗黙に解決する方向をとるので、これは要らない
• syntax-caseのマッチはランタイムに生成される
• パフォーマンス的にはうれしくないよなぁ
• ただ、その分いろいろな情報解析で手を抜けそう
• 式が渡された段階で全てのシンボルが識別子に変換されている
• 重要だけど、リテラルなリストとかどうしようかな・・・
• 環境は全ての束縛を保持する
• 局所変数から大域変数、はたまた構文まで全部
• free-identifier=?の実装には必要
• 僕の考え方は間違ってなかったのかと納得
• パターン変数を識別するものがある

っで、現状のSagittariusの実装とは大きく異なる部分；

• パターンマッチは組み込みである
• コンパイルが2度走る必要がないの多少高速なはず
• テンプレート展開部分も組み込みである
•  Andre van Tonderの方はこいつもマクロごとに生成される
• ラップする式は束縛されている変数のみかつ、コンパイラが行う
• しかも、複数回走る
• 全体を1回だけにした方がいいが、リテラルリストをどうするか

ある意味当たり前なんだけど、マクロ展開の部分だけに目を向けるなら、syntax-caseとsyntaxだけが解決されている。つまり、それ以外のR6RSが提供する低レベルマクロ用何かしらは、すべてこの2つの組み合わせのみで解決できる。
ということは、この2つが完璧に動作さえすれば、他の動作は保障されているわけで、現状いろいろごにょごにょやっている部分がすっきりする可能性が高い。

Andre van Tonderの展開器ではポータビリティのために生成されるGUIDはシンボルなのだが、gensymがある処理系ならばこれはgensymに単純に置き換えることができる(検証もした)。ついでに、GUIDは一時変数とか、ユニークなシンボルの生成以外には使われていない。
ライブラリの関係(だけじゃないかも)で、グローバルもしくはローカルに束縛されたシンボルの実態はGUIDに変換されている。ただ、ルックアップ自体は識別子で行うので、Sagittariusではやる必要はないと思う。

全体を1回だけラップすることで起きえる問題を考えてみる；

• リテラルリストが壊れる
• 完全にリテラルだと分かっているならラップしないということも可能
• quasiquoteが困りそうだがどうする？
• ラップ時にquasiquoteだけ特別視？
• ベクタもリテラルであるよな？
• libraryやdefine-library構文に手を入れる必要がある。
• exportやimportがシンボルを期待しているが、識別子になってしまう
• まぁ、大きな問題ではない

リテラルリストだけなんとかすれば大きく問題はないと思う。ずっと使わずあるだけだったpass0手続きがついに使われるときが来たか。
気になるのは、ただでさえメモリ喰いなのにさらにメモリを喰うようになることか。読んだS式全部トラバースして、丸コピーしないといけなくなるから。まぁ、現状も似たようなことやってるし、考えるだけ無駄か。

続 マクロ戦争再び

すこぶる体調が悪いが頭はそれなりに稼動するので案をベッドの上で考えていたりした。

現状の問題としては、同一の環境でリネームされた識別子(本来はシンボル)が同名にならないというものだ。これは本質的に2つの問題を含んでいることを示唆している。

1. 識別子を用いてシンボルの同一性を取ろうとしていること
1. α変換が不完全である
2. 識別子が本来の意味を越えて使用されているため、複雑なものが複雑怪奇にグレードアップしている
1. 識別子＝構文オブジェクト＝パターン変数＝リネームされたシンボルになっている

では、どうすればいいかということを考えていた。とりあえず1と2の問題の一部を解決するアイデアが以下である。

• 使用されている環境に応じて適切にシンボルのリネームを行う

王道である。実際これくらいしか思いつかなかったともいう。問題になるのは、どの環境をもって同一の環境というかという点である。Sagittariusではマクロ展開時に3つの環境を参照することができる。

1. コンパイル時の環境
2. マクロ束縛時の環境
3. マクロ展開時の環境

自分の中でもなんでこんなに環境が必要なのか実は整理できていないのが問題なのだが、それぞれ全て違う。細かいこと(細かくないが)はとりあえず置いておいて、とりあえず以下のプログラムを考える；

(import (rnrs))
(let ((bv #t)) ;; ※1
  (define-syntax foo
    (lambda (x)
      (syntax-case x ()
        ((_)
         (with-syntax ((set (let ((type #'bytevector-u8-set!))
                              #`(#,type bv 0 1))))
           #'(let ((bv (make-bytevector 1)))
               set
               bv))))))
  
  (let ((bv #f))
    (display (foo))))

まぁ、前回とほぼ同じコードである。違いは、マクロ束縛時環境が何かを捉えている点である。ここで問題になるのは、全てのbvが同一のシンボルになる必要がある点である。そうすると、コンパイル時環境を使うのはまずいことになる。letで束縛されたtypeが入ってくるからだ。そうすると、二つ目のbvと環境が異なるため、生成されるシンボルが異なる。
この状態では、マクロ束縛時と展開時の環境が多少違う。このパターンを考えるとマクロ束縛時の環境を使ってリネームするのが正しい気がする。ただし、リネームされたシンボルは※1と同名になる必要がある。これは、with-syntax>で生成されたものがそれを参照している必要があるからだ。また、最終的に返される構文で束縛されるbvも同様である。それによってシャドウイングされて結果正しい値を返す。
もし、このスクリプトでマクロ展開時の環境を使うと、(まぁ、結果的には問題ないのだが)、二つ目のbvにリネームされることになるのでうれしくない。

なんとなくどうすればいいのか見えてきた。結果として以下のように修正すれば、いいのではないだろうか？

1. コンパイラ側のリネームを(uninterned)シンボルを使うように修正
2. マクロ展開器ではマクロ束縛時の環境を元にシンボルを(uninterned)シンボルにリネーム

方針は固まったので、後は実装か・・・

マクロ戦争再び

正直何度目だ、戦争が勃発するのは・・・

ほぼピュアR6RSで書かれたライブラリでindustriaというものがある。驚嘆するほどでかい上に、Sagittariusのお株の一つである暗号処理がサポートされている。(別にライブラリの宣伝をしたいわけではない)

このライブラリ内で使われているマクロが動かないというバグレポートを受けた。最初はmake-variable-transformerが参照している環境が違うだけかと思ったのだが、実は裏にもう一つ潜んでいた。こっちは非常に厄介な、しかもずっと悩んでいる問題の一つ。端的に問題を顕在化させるコードが以下；

(import (rnrs))
(define-syntax foo
  (lambda (x)
    (syntax-case x ()
      ((_)
       (with-syntax ((set #'(bytevector-u8-ref bv 0)))
  #'(let ((bv (make-bytevector 1)))
      set
      bv))))))

(foo)

with-syntaxで作られた新しいパターン変数(ということにしている)内にあるbvと最終的に返される構文内で使われているbvが同じでなければならないという問題。

これはSagittariusではうまく動かない。なぜかという原因も分かっていて、最初のbvと2回目のbvは使用される環境(正確には違うけど便宜上こう呼ぶ) が違うから。これと類似の問題に、R6RSテストスイーツのbreakがあるが、あれはwith-syntax上ですでにパターン変数として作られているので、なんとか識別する。

これの本質的な問題は、syntax構文が同一環境で呼ばれても同一の識別子を返さないことにある。本来ならば、最初と2回目は同一の環境なので、どちらのbvも同じ名前にリネームされるから最終的な形としては問題なく動くようになる、はずなのだけど、そうは問屋がおろさないので困っている。

解決策としては2つあると思っていて、一つは王道、識別子にリネームされた際の環境、フェーズその他もろもろの情報を付加してやり、identifier=?はそれらをまじめに比較するようにする。二つ目は邪道(というか、スパゲッティ生成法)、マクロ作成時に作られる環境にフィールドを一つ追加して、何が何にリネームされたかということ保持しておき、それを環境が拡張されるても共有する。

正直、どちらの方法もかなり大掛かりな変更が必要になる。やりたくないが、バグとして報告された以上なんとかしないわけにもいくまい・・・

ってか、これってR6RSで動くって保障されてるのかな？されてるよなぁ・・・

キャッシュを考える

ふとQiitaのLisp Reader Macro Advent Calendar 2012のネタを考えているときに思ったこと。

Sagittariusはパフォーマンス(ほぼレスポンスだが)向上のためにライブラリ単位でFASLのようなものを持っている (正確にはライブラリファイル単位だが)。普通にスクリプトを書く分には気にする必要はないのだが、リーダーマクロが絡んでくると多少考える必要が出てくる。たとえば、組み込みの正規表現はリーダーマクロを用いて読み取った場合リテラルオブジェクトとして扱われる。これはその方がパフォーマンスがいいからに他ならない。

ここで、ユーザー定義のオブジェクトを考える(Qiitaに書く予定のネタは文字セットなんだけど)。たとえばCLOSを用いてオブジェクトを作成するが、リーダーマクロでリテラルとしても返せるようにしたとする。そうすると何が起きるか？普通にスクリプトとして使用されるだけなら特に問題はないのだが、ライブラリ内で使用すると話が違ってくる。

現状ではキャッシュ機構はユーザー定義のオブジェクトをキャッシュする方法を暗に知る方法がない。SRFI-4ではユーザー定義のリテラルを返すようにしているが、これは明示的にどうそのオブジェクトをキャッシュするかということをScheme側で制御しているからできるのである。しかし、いちいちそれを書くのが面倒な場合の方が大体多い。

なんとかならないかなぁと思っていたのだが、なんとなく「完全Scheme」で定義されたオブジェクトなら一般的な方法でいけるような気がしてきている。それは、CLOSのオブジェクトは基本スロットの中身さえ保存してしまえば何とでもなるからだ。スロット名と値を保存して、復元時は単にslot-set!でセットしてやる。

ここで、問題になるのは、「キャッシュできない組み込みオブジェクト」だろう。現状でsubrをうまいことキャッシュする方法を思いついていない。また、自由変数を含むクロージャーがスロットに入っていた場合とかも困る。まぁ、あくまでベストエフォートだと言えばいいので、こういったキャッシュ不可能なものが来たら弾いてしまえばいいといえばそうなんだけど。

不安材料の方が多い気もするし、どうしたものか・・・？

Hoge VeluweとKröller Möller美術館

Meetupのイベントで行ってきた。Utrecht以東に行くのは実はこれがはじめて。Adventureはたどり着く前から始まっているのである。（MeetupのグループがAdventureを冠している）

ま、何はともあれ写真。僕の気力が続く限り撮った。加工するのが面倒だったからファイルが巨大だｗ

Utrecht Central。いつきても代わり映えはしない。そしてトラブルが多いというイメージの駅。（実際帰りはLeidenへの直通がなかった・・・orz）

ハイキング開始。きれいな丘だろ？これでもオランダなんだぜ。

もう少し傾斜があれば軽く山登りな気分。

オランダとは思えない風景の一つ。

森の中を進む。

森が終わると今度はサバンナｗ

あたり一面まっ平ら。ま、やっぱりオランダだよね。

微妙にこの風景はSaskatchewanとかManitobaを思い出す。何もない平らな風景。

3時間に及ぶハイキングの後、小さなレストランに到着。あの小屋みたいなのがレストラン。

ここからはKröller Möller美術館の中。これは正確にはその庭。

途中で見つけた何かしら。これの裏に、三段腹をモチーフにした何かがあったけど、写真取り忘れたｗ

木漏れ日が差してる絵って好きなんだよね。 ま、iPhoneのカメラではこの程度が限界だけど。

芸術家の考えることは一般人には理解できないけど、これはひときわ、なんぞこれｗ？だった。

改装中の部屋にあった絵。

本物（だと思う）のゴッホの絵。この美術館はゴッホのコレクションがオランダで2番目に多いらしい。一番はアムステルダムのゴッホ美術館だと思う。

ありがたや～ｗ

自分が写りまくりｗ合わせ鏡があって、どれくらい光が届くんだろうと気になって撮った。

夜の帳が下りようとしている中、正門まで2kmのウォーキング。10分後にはえらい暗くなっていた。

帰り道はUtrechtからLeidenへの電車がなかったので、Den Haag経由で帰る必要があったがまぁ無事に帰宅。3時間＋30分のウォーキングで足が痛いｗ
正直、オランダにこんなところがあるんだ、と感動した一日だった。そして、山っぽいところを歩いているときに、あぁ、やっぱり自分は山の方が好きなんだなぁと実感した。

writeがスタックを食いつぶす

Gaucheのソースツリーを眺めていて、writeがCのスタックを食いつぶすのを直したというようなコミットを見つけた。同じことが起きるよなぁと思いつつ、とりあえずテスト。以下は使用したコード(R7RS形式なのは最後にチェックしたのがChibiだから。当然Sagittariusでも動く)

(import (scheme base) (scheme write))
(define (call-with-string-output-port proc)
  (call-with-port (open-output-string)
    (lambda (p) 
      (proc p)
      (get-output-string p))))

(display
 (let loop ((cnt 0) (ls '()))
   (if (< cnt 1000000)
       (loop (+ cnt 1) (list ls))
       (string-length (call-with-string-output-port
                       (lambda (p) (display ls p))))))) 
(newline)

とりあえず、どのくらいの処理系がこれをSEGVを起こさず処理するのかチェック。以下は結果。

200002を正しく返した処理系

Chez Scheme, Racket (plt-r6rs), Larceny (R6RS)

SEGVもしくは処理が終わらなかった処理系

Sagittarius, Chibi, Mosh, Ypsilon

動く処理系で、ソースを確認できるのはRacketとLarcenyだけなので、とりあえず確認してみた。

Larcenyはなぜ動いているのか正直分からなかった。コードがSchemeで書かれているので、ひょっとしたら最適化でうまいこと動いているのか、Cで書いていない分スタックの消費が少なくなっているのかは不明。

Racketはスタックの底にたどり着いたらlongjmpするという荒業だった。たしかに、ありだよね。

Gaucheは0.9.4は再帰呼び出しをせず、gotoで済ますという方法。ただ、そのためにメモリを結構使用するんじゃないかなぁと思ったり。

Sagittariusは(ユニットテストの)メモリの使用量が半端ないので、可能な限り省エネで行きたいところ。なので、やるならRacket方式か、気合でなにか良い案思いつく必要がある。longjmpのオーバーヘッドってどれくらいなんだろう？

Sagittarius 0.3.8 リリース

Sagittarius Scheme 0.3.8がリリースされました。今回のリリースからR7RSドラフト7がサポートされます。ダウンロード。

修正された不具合

• ローカルマクロをマクロ内で定義した際にSEGVが起きる不具合が修正されました。
• (dbd odbc)を用いて存在しないレコードを更新しようとした際にエラーが投げられる不具合が修正されました。
• get-bytevector-allがソケットポートからデータを全て読み込まない不具合が修正されました。
• binary-port?及びtextual-port?がカスタムポートに対して適切に動作しない不具合が修正されました。
• #n=をリーダが適切に読み込まない不具合が修正されました。
• remainderの第一引数に浮動小数点数を与えるとSEGVが起きる不具合が修正されました。
• (sqrt -1)が非正確数を返す不具合が修正されました。
• (zero? 0.0+0.0i)が#fを返す不具合が修正されました。
• -1iのような形式の複素数が正しくない符号を返す不具合が修正されました。
• ライブラリのバージョンに0が使えない不具合が修正されました。
• ライブラリバージョンリファレンスの形式がエラーを投げる不具合が修正されました。
• appendが引数1つで呼び出された場合に()を返す不具合が修正されました。
• 全ての未束縛exportが束縛された値を持つよう修正されました。

改善点

• (cond ((assq a b) => cdr))の形式をコンパイラが可能であれば組込みインストラクションを使うように改善されました。
• ビルドプロセスが改善されました。
• 多くの依存ライブラリがFIND_PACKAGEを用いて検索されるようになりました。
• libffiが見つからなかった際にLinuxでもバンドルされたlibffiが使用可能になりました。（Ubuntu 32 bitでのみテストされています)
• ODBCライブラリのblob型ポートが作成時に全てのデータを読み取らないように変更されました。

新たに追加された機能

• リーダーマクロの有効範囲がファイル単位からポート単位に変更になりました。
• R7RSドラフト7がサポートされました。
• glob手続きが追加されました。
• sashの-Lオプションが-L'*'形式をサポートするようになりました。これはglobで見つかった全てのディレクトリをロードパスに追加します。

新たに追加されたライブラリ

• SRFI-105が追加されました。#!read-macro=curly-infixで有効になります。#!curly-infixではないことに注意してください。

非互換な変更

• R7RSのライブラリが大幅に変更になりました。これらはドラフト5からの変更で、後方互換性はありません。

ブレインストーミング

考えをまとめるのに紙に書くのが面倒なのと、記録を残しておいた方がいい類のものなのでメモ。

以下のコードを考える。

(read (open-string-input-port "#!fold-case ABC"))
(read (open-string-input-port "ABC")) ;; こいつは何を返すか

恐らく書いている方の期待する結果はABCというシンボルだろう。だが、これは予想に反してabcを返す。(Sagittariusでは#!fold-caseは全部小文字にして返す) 。こんなの書くやついないよ！と思っていたのだが、意外なことに自分がこれではまったのでやはり問題かなと思うようになってきた。

何が問題か？

現状ではSagittariusはファイル単位でリードテーブルの切り替えを行う。っが、上記のようなものだと同一ファイル上でreadが走るのでファイル単位で行うと残念な結果になる。つまり、ファイルではなくポート単位で行う必要があるということになる。

どう直すか？

ポート単位にするというのは結構大掛かりな変更になる。現状の実装では、VMが現在のリードテーブルを保持して、loadが走る際にポートに保存、loadが終わったら保存したテーブルをVMに戻すという割と回りくどいことをしている。
これをポート単位にするにはどうすればいいのか？とりあえず簡単に思いつくのはVMが現在loadしているポートを保存するというもの。loadは必ずファイル単位で行われるので、現在のloadingポートが分かれば何とかなりそうである。となると問題になってくるのは、どの段階でポートにリードテーブルを持たせるかというもの。可能性としてあるのは、

1. ポート作成時。（全てのポートはリードテーブルを持つ）
2. リードテーブルを変更するようなものを検出したとき。（オンデマンド）

上記のようなコードだと、2つ目のポートに持たせるのは無駄以外のなんでもないような気がするので、やるならオンデマンドだろうか。

方針は決まったので実装するか。

この発想はなかった

Chibi-SchemeのIssue 149にあった面白い発想のdefineをsyntax-caseで実装してみた。

(import (rnrs))
#|
;; ※１
;; 投稿した2分後にsyntax-case一回だけでいけることに気づいた。
;; なので、コード直下のぼやきはこのコードに対してのもの。
(define-syntax define-function
  (lambda (x)
    (define (compose expr)
      (let loop ((expr expr))
        (syntax-case expr ()
          (((name . formals) body ...)
           (identifier? #'name)
           #'(define name (lambda formals body ...)))
          (((name&formals . rest) body ...)
           (not (identifier? #'name&formals))
           (loop #'(name&formals (lambda rest body ...)))))))
    (syntax-case x ()
      ((_ exprs ...)
       (compose #'(exprs ...))))))
|#
;; すっきしたバージョン。これなら処理系関係ない。
(define-syntax define-function
  (lambda (x)
    (syntax-case x ()
      ((k (name . formals) body ...)
       (identifier? #'name)
       #'(define name (lambda formals body ...)))
      ((k (name&formals . rest) body ...)
       ;;(not (identifier? #'name&formals)) ;; この行要らない
       #'(define-function name&formals (lambda rest body ...))))))

(define-function ((f x) y) (+ x y))

(print ((f 1) 2))

多少以上に余計な手間をかけているのだが、マクロ周りがR6RS準拠な処理系と違ってSagittariusでは識別子のリネームに制限がある。それは、同一のsyntax構文内でリネームを行わないと識別子が同じにならず、unbound variableエラーを投げるというもの。なので、上記は本来ならquasisyntaxを使ってもう少し分かりやすく書けるのだが（まぁ、どちらが分かりやすいかは人によるが）、Sagittariusで動かすために式を全部一緒に処理してやる必要がある。（※1のコード)

この制限はずっと気づいているし、問題だと思っているのだが、いかんせんスマートな解決方法が思い浮かばないのと、慣れてしまえば別に気にならないので放置してある。0.4.0辺りまでに直したいという思いはあるが、あるだけともいえる・・・（マクロ周りは本当に鬼やぜ）

さて、ようやく本題。上記のマクロがどのように展開されるかというのが個人的には面白いなぁと思ったという話。Chibiのissue見れば答えは載っているのだが、引数の個数にも寄るが、この構文簡易カリー化と取れなくもない。上記の手続きfは以下のように展開される。

(define f (lambda (x) (lambda (y) (+ x y))))

たとえば、SXPathはこんな感じの手続きをころころ作るのだが、実装を見てみると（当然なんだけど）明示的にlambdaをいっぱい書いている。でも、これ使えばそのわずらわしさから開放される！というわけだ。

僕自身、あまりそんな使い方しないんだけど、マクロ使えばこんなこともできちゃう！というちょっとした例。