Syntax highlighter

2012-12-31

2012年を振り返って

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

【達成したこと】
  • R6RSマクロ展開器が標準により準拠した
  • R7RS対応がほぼ終わった
  • 月1リリースの継続
あまり目標を立ててないので、自分の中で達成したというのはないなぁ。自分がほしい機能をいっぱい詰め込んだ「俺々処理系」度がえらく進んだ感があるが(リーダの置き換えとか)。


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

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

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

2012-12-18

TLVパーサがほしい

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

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

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

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

2012-12-15

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

2012-12-14

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モードでは動きません。

2012-12-12

パターン変数

リリース直前にバグに気づいた。もちろんマクロ周り・・・
問題となるのは以下のようなコード。
(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対応と称して出してしまおうか・・・(悪魔の囁き

2012-12-10

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をフルサポートしている処理系ということになる。今週末リリースする予定(あくまで予定)。

2012-12-09

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).

2012-12-08

最後の砦

マクロの書き換えを始めて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週間でマクロ展開の実装は所詮環境の参照と識別子のリネームだけなんだと痛感させられた。ただ、それが異様に面倒なだけで・・・

2012-12-05

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 ...

2012-12-02

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も最初のドラフトの段階では追従するということを回答していました。参照

2012-12-01

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式全部トラバースして、丸コピーしないといけなくなるから。まぁ、現状も似たようなことやってるし、考えるだけ無駄か。

2012-11-30

続 マクロ戦争再び

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

現状の問題としては、同一の環境でリネームされた識別子(本来はシンボル)が同名にならないというものだ。これは本質的に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)シンボルにリネーム
方針は固まったので、後は実装か・・・

2012-11-27

マクロ戦争再び

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

ほぼピュア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で動くって保障されてるのかな?されてるよなぁ・・・

2012-11-22

キャッシュを考える

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

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

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

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

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

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

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

2012-11-18

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

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

ま、何はともあれ写真。僕の気力が続く限り撮った。加工するのが面倒だったからファイルが巨大だw
Utrecht Central。いつきても代わり映えはしない。そしてトラブルが多いというイメージの駅。(実際帰りはLeidenへの直通がなかった・・・orz)

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

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

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

森の中を進む。

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

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

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

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

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

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

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

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

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

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

ありがたや~w

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

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

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

2012-11-16

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からの変更で、後方互換性はありません。

2012-11-15

ブレインストーミング

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

以下のコードを考える。
(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つ目のポートに持たせるのは無駄以外のなんでもないような気がするので、やるならオンデマンドだろうか。

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

2012-11-14

この発想はなかった

Chibi-SchemeのIssue 149にあった面白い発想のdefineをsyntax-caseで実装してみた。
(import (rnrs))
#|
;; ※1
;; 投稿した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をいっぱい書いている。でも、これ使えばそのわずらわしさから開放される!というわけだ。

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

2012-11-11

R7RS対応

ドラフト7の範囲の実装が大体終わった。Chibi SchemeのR7RSテストケースもほぼ通るようになっている。(通らないのは、R6RSと競合する部分とFlonumの精度が決め打ちになっている部分と、R7RS上では不明瞭に見えてかつ僕がChibiの挙動の方がおかしいと思う部分)

他の人が仕様書に対して書いたテストというのは意外と自分ではチェックしない部分の挙動があったりしてバグ潰しに役立つということが分かった。実際、Chibiのテストケースを通るようにした際に6個くらいバグをつぶした。中にはSEGVを起こすようなのもあって、普段使わない、書かない系のコードというのの中にこそバグが含まれているというのがよく分かった。

現状でR7RS準拠度はevalが環境を破壊的に変更するのと(問題だとすら思っていない)、R6RSなのでbinary、textualポートの区切りがはっきりしている点を除けば全て準拠していると思う。Chibiですら対応していないinclude-library-declarationsも入っているw

今週末にリリース予定の0.3.8からR7RSドラフト7に対応しているという宣伝。

未束縛エクスポートのチェック

R6RS及びR7RSではexport句に未束縛なシンボルを書くとエラーになるとある。しかし、Sagittariusでは実装上の手抜きでチェックをしていない(やれば実はできるんだけど、コンパイル時間の増大を防ぎたいとか、メモリ使用率を減らしたいとか、まぁいろいろ言い訳をつけてやってない)。

っで、近頃(昨日)R7RSのドラフト7が出て、結構な数の手続きが追加または削除になったのがあり、実際に手続き及びマクロが定義されているかのチェックを目視とかテストケース書いてたらやってられないなぁと思ったのでこんなスクリプトを書いた。
(import (rnrs) (util file)
        (sagittarius vm) (match)
        (srfi :26) (srfi :64))
;; この部分を適当に変える。
;; R7RSだけ調べたいなら"./sitelib/scheme/*"とか
(define files (glob "./lib/**/*"))

(test-begin "bound check")
(define (check-exports file)
  (define (do-check name exports)
    (guard (e (#t 
               (when (message-condition? e)
                 (print (condition-message e)))
               (print "failed to find library: " name)))
      (let ((lib (find-library name #f)))
        (define (check orig export)
          (unless (keyword? export)
            (test-assert (format "~a:~a" name orig)
                         (let ((gloc (find-binding lib export #f)))
                           (and gloc (gloc-bound? gloc))))))
        (for-each
         (lambda (export)
           (match export
             (('rename renames ...)
              (for-each (lambda (rename)
                          (check rename (car rename))) renames))
             (_ (check export export))))
         exports))))
  (guard (e (#t (print "failed to read: " file)))
    (when (file-regular? file)
      (let ((expr (file->sexp-list file)))
        (match expr
          ((('library name ('export exports ...) rest ...))
           (do-check name exports))
          (_ #f)))
      )))
  

(for-each (cut check-exports <>) files)

(test-end)
やっていることは至極単純で、見つけたファイルを読み取って、中からlibraryで始まるS式見つけて、ライブラリ見つけて、exportしているものが存在するか調べる。それだけ。
なぜか、||なシンボルを読まなかったり、キーワードをキーワードとして読み取らなかったりと、変な挙動があるけど、それなりに便利。 既存のライブラリで未束縛なエクスポートを含んでいたのものさえ発見できたし・・・orz

2012-11-10

R7RSの7thドラフト

ようやく出た。正直、出る出る詐欺じゃないかと心配していたw

Ballotの結果なんかは追っているので、もしR7RSで検索してたどり着いたのであればそちらを見ていただきたい。
Sagittariusは6thドラフトに追従していないので5thドラフトから変更となるが、まぁ問題はないだろう。7thドラフトは個人的に割りとインパクトが大きくて、ライブラリの修正だけではなく、コンパイラもいじらないといけない。以下に自分用のメモも兼ねて修正ポイントを記載する。

【コンパイラ】
include-library-declarations
define-library構文に追加になった。include先のライブラリのexport句のみを対象に持ってくる。単なる便利構文。正直、いるかこれ?と思っている。
【ライブラリ】
(scheme base)
いろいろな手続きが削除、移動になった。
(scheme cxr)
cxxr以上の手続きが(scheme base)から取り除かれてこっちに移動。
(scheme char normalization)
Unicodeサポートが必須じゃなくなったので削除。
(scheme division)
たしか6thドラフトの段階で消えてた気がする。
(scheme r5rs)
R5RSコンパチライブラリ。(7thからだったかな?記憶あいまい)
(scheme lazy)
delay-forceが追加になった。
ライブラリの修正は、面倒なだけで特にインパクトは小さいんだけど、コンパイラは面倒だ。まぁ、そこまで面倒でもないんだけど。include-library-declarationsは個人的に非常に醜いと思うのでできれば入れたくないが、たぶんファイルに残るだろうなぁ。

【文字と文字列】
勘違いしていたことと、やはり納得がいかないので一応。
7thドラフトで文字列がサポートしなければならない範囲が明確に定義された。処理系は最低でも「NULLを除いたASCII文字の文字列」のサポートしなければならない。 まぁ、ここまではいいだろう。ただ、「文字列を文字の集合」として捉えた際に現状のドラフトでは不整合がでる。なぜか?問題はこの一文;
All Scheme implementations must support at least the ASCII character repertoire: that is, Unicode characters U+0000 through U+007F.
 7thドラフトでは明確に文字がサポートしなければならない範囲にNULLが含まれているが、文字列ではNULLを省いていいよって言ってるのだ。まぁ、文字列 != 文字の集合なら何の問題もないけど。R7RSに明確に文字列は文字の並び(sequenceってどう訳すの?)と書いてあるね。

2012-11-08

curly-infix (SRFI-105)

I have merged my SRFI-105 implementation on Github to Sagittarius itself. So it can be used from version 0.3.8.
I haven't follow all the discussions nor read all specification (WTF?!), so I'm not sure if the following code is too much #\{ and #\} or it's supposed to be like this;
;; Sagittarius need this line
#!read-macro=curly-infix
;; For portability with other implementations.
#!curly-infix

(import (rnrs))

(define (fact n)
  (if {n = 0}
      1
      ;; Here, it seems too much. If I could write
      ;; fact(n - 1), it seems way better. But my
      ;; implementation (mostly taken from reference
      ;; implementation) doesn't allow me.
      {n * fact({n - 1})}))

{print fact(5)} ;; -> 120
As far as I understood, inside of #\( must be treated the same as usual Scheme way. So if I want to pass calculated argument(s) with infix style, then I need to wrap with extra pair of #\{ and #\}. If I'm not understanding correctly, please let me know :-)

Some part such as {n = 0} might be easier to understand for people who are not so familier with polish notation. However for people who already wrote a lot of Lisp programme, this might make them confused (or maybe not?).

Anyway, providing choices to users is a good thing, I believe.

2012-11-03

SQLiteをODBCで使う

せっかくODBCをサポートしてるんだし(WindowsとCygwinだけだが)、SQLiteでも使ってみるかと思いちょっといじってみた。目的としてはdbi-preparedでバイトベクタとポートを受け付けるようにしたかっただけなのだが・・・

結論を言うと、SQLiteでは(というか、SQLite ODBC Driverでは)BLOBを扱うのが無理。正確には巨大なBLOBを扱うのが不可能くさい。

なぜか?SQLGetDataがここに書かれている動作をしない。(おそらく)呼び出すたびに先頭からデータを取ってくる。もしくは、一度の呼び出しで全部取得できてしまったら二度目の呼び出しでまた全部データを取ってくるため。なので、以下のコードが無限ループに陥った。
(import (rnrs) (dbi))

(define conn (dbi-connect "dbi:odbc:server=SG"))
(define sql "insert into test (id, data) values (?, ?)")

(let ((query (dbi-prepare conn sql 1 "ok")))
  (dbi-execute! query))
(define sql "select * from test")
(let ((query (dbi-prepare conn sql)))
  (print (dbi-execute! query))
  (print (dbi-columns query))
  (let loop ((col (dbi-fetch! query)))
    (when col
      (vector-for-each (lambda (v)
                         (if (binary-port? v)
                             (let loop ((bv (get-bytevector-n v 20)))
                               (unless (eof-object? bv)
                                  (print bv)
                                  (loop (get-bytevector-n v 20))))
                             (display v))) col)
      (newline)
      (loop (dbi-fetch! query)))))
(dbi-close conn)
dataカラムはblobになっている。問題になった、get-bytevector-nの部分。ポートになっているが、中身はSQLGetDataを呼び出して必要なだけ取り出すというもの。ただ、ポートの部分は普通のファイルと共通になっているので(昨日そうした)、まずバッファに溜め込もうとする。問題は、SQLGetDataが常に先頭からデータを読み出すので、EOFが返ることがないこと。

これが、get-bytevector-allだと予定通りに動くのだが、今度はデータが空のblobが半端なくでかいサイズを要求するのでメモリが足りないといわれる。データ空なのに・・・

SQLiteを仕事で使うことはないので、割とどうでもいいのではあるが、解決するため(結局できなかった)に2時間は無駄にしたのでせっかくだしと思い書いた。

2012-10-31

should of and whilst

最近イングランド在住のJKとチャットをしている。普通ならありえるはずもないことなので、ネットとは恐ろしいものだ。

それはさておき、会話の中で結構見慣れない単語、表現が出てきたりする。さすがはネイティブ、いろんな表現を知っているなぁと思い勉強させてもらっている。その中で出てきたので、「should of」というのかあった。こんな感じで使われている。
I should of been there.
こんなのがあったかは覚えがないが、要するにhaveの代わりにofを使っているのだ。方言かな?と思いググッて見た。(Google便利だよGoogle)
っで、最初に得られた結果が以下
This is one of those errors typically made by a person more familiar with the spoken than the written form of English. A sentence like “I would have gone if anyone had given me free tickets” is normally spoken in a slurred way so that the two words “would have” are not distinctly separated, but blended together into what is properly rendered “would’ve.” Seeing that “V” tips you off right away that “would’ve” is a contraction of “would have.” But many people hear “would of” and that’s how they write it. Wrong.
COULD OF, SHOULD OF, WOULD OF より
単なる間違いらしい。日本語の「ら」抜き言葉とか「全然~ない」みたいなものか(多少違うか)。口語表現をそのまま文語(まで堅苦しくはないか)に持ってきたもののようだ。

ついでに、よく見る単語で「whilst」というのがある。こんな感じで使われていた。
Whilst I'm lying on the sofa.
意味は「while」だと推測可能ではあるのだが、なんだこれ?ということでGoogle先生に尋ねる。っで以下がヒット。
Both while and whilst are ancient, though while is older. There’s no difference in meaning between them. For reasons that aren’t clear, whilst has survived in British English but has died out in the US. However, in Britain it is considered to be a more formal and literary word than its counterpart. I have a small weakness for it, for which I’ve been gently teased in the past.
World Wide Words: While versus whilst より
意味に違いはないけど、アメリカでは死語で、イギリスでは形式ばった表現らしい。 多分使うことはないけど、いろいろ面白い。

2012-10-24

SchemeでClojure風構文

お昼ごはんを食べながら適当に書いてみた。Clojureの構文はちょっと見ただけなので違うかもしれない。
((import (rnrs))

(define-syntax fn
  (lambda (x)
    (define (parse-args args acc)
      (define (finish opt)
        (if (null? acc)
            opt
            (append (reverse acc) opt)))
      (syntax-case args (&)
        (() (finish '()))
        ((& rest) (finish #'rest))
        ((a . d)
         (parse-args #'d (cons #'a acc)))))

    (define (parse-body body acc)
      (syntax-case body ()
        (() (reverse acc))
        (((#(args ...) exprs ...) . rest)
         (with-syntax ((formals (parse-args #'(args ...) '())))
           (parse-body #'rest 
                       (cons #'(formals exprs ...) acc))))))
    (syntax-case x ()
      ((_ #(args ...) exprs ...)
       #'(fn dummy #(args ...) exprs ...))
      ((_ name #(args ...) exprs ...)
       (identifier? #'name)
       #'(fn name (#(args ...) exprs ...)))
      ((_ (#(args ...) exprs ...) ...)
       #'(fn dummy (#(args ...) exprs ...) ...))
      ((_ name (#(args ...) exprs ...) ...)
       (identifier? #'name)
       (with-syntax ((((formals body ...) rest ...)
                      (parse-body #'((#(args ...) exprs ...) ...) '())))
         #'(letrec ((name (case-lambda 
                           (formals body ...)
                           rest ...)))
             name))))))

(define-syntax def
  (syntax-rules ()
    ((_ name expr) (define name expr))))

(define-syntax defn
  (syntax-rules ()
    ((_ name #(args ...) body ...)
     (defn name (#(args ...) body ...)))
    ((_ name (#(args ...) body ...) ...)
     (define name
       (fn name (#(args ...) body ...) ...)))))

(defn print #(& args) (for-each display args) (newline))

(defn t1 #(a b) (print a b))
(t1 1 2)

(defn t2 
  (#(x) (print x))
  (#(x y) (print x y)))

(t2 1)
(t2 1 2)
(t2 2 1)

(def mult
  (fn this
      (#() 1)
      (#(x) x)
      (#(x y) (* x y))
      (#(x y & more) (apply this (this x y) more))))

(print (mult 1 2 3 4 5))
Clojureでは[]がベクタになるけど、Schemeでは#()にしないといけないのでむしろうっとおしい感じがする。

動作確認はいつものR6RS処理系でやった。

なんでこんなものを書いたかと言えば、パターンマッチ部分でベクタにもマッチできるよなぁと思ったから。本当にただそれだけ。

2012-10-23

Should NULL be allow to be in string?

R7RS working group likes discussion, I guess.

The most recent topic is about string containing #\x0 (or #\null).
poll: invalid item #315 from 5th ballot
The #315 is about the following code won't raise any error.
(string-set! s i #\null)
For me, it seems totally fine. But for them, or even Unicode world, it's not fine. Really?

Well, either way the above expression on Sagittarius will be totally fine for any time. So, I don't have any intension to change current behaviour.

The reason I'm writing this article is I found a curious experience in the topic. How does the following code work on R6RS implementations? Original was about Chicken and Gambit.
(import (rnrs))
(define file (string #\a #\x0 #\b))
(when (file-exists? file) (delete-file file))

(let ((o (open-file-output-port file)))
  (put-bytevector o (string->utf8 "hello"))
  (close-port o))
The file is definitely invalid file path.

The results are like this;
ImplementationResult
ChezMade 'a' file
LarcenyMade 'a' file
MoshMade 'a' file
RacketRaised an error
SagittariusMade 'a' file
YpsilonMade 'a' file
I can't say which way should implementations behave.

2012-10-19

Sagittarius 0.3.7リリース

Sagittarius Scheme 0.3.7がリリースされました。ダウンロード

今回のリリースから、リーダの置き換えが可能になります。詳しくはドキュメントを参照してください。

修正された不具合
  • append!がリテラルリストを破壊的に変更可能だった不具合が修正されました
  • (cond-features)がmutable listを返す不具合が修正されました。
  • vector-reverse!がリテラルベクタを破壊的に変更する不具合が修正されました
  • 組込みリーダを意図的に呼び出した際に、Schemeオブジェクト以外の不正なオブジェクトが返される不具合が修正されました
  •  file-symbolic-link?手続きがシンボリックリンクに対して#tを返さない不具合が修正されました
  • with-libraryマクロがキャッシュファイルを壊す可能性がある不具合が修正されました
  • delete-directoryがWindows環境でいかなるフォルダも削除できない不具合が修正されました
新たに追加された機能
  • リーダの置き換え機能が追加されました
  • create-directory*, delete-directory*,  copy-directory及びbuid-path*手続きが(util file)ライブラリに追加されました
  • socket-recv及びsocket-sendのflags引数がオプショナルになりました。ドラフトSRFI-106への追従です。
新たに追加されたライブラリ
  • SRFI-49がサポートされました。#!reader=srfi/:49の宣言をつけることでリーダが置き換えられます。
改善点
  •  values手続きが第一級オブジェクトを返さなくなりました。また、32個までの引数ならVMはメモリの割り当てをしません。
  • Windows環境での安定性が向上しました
非互換な変更
  • (rsa pkcs :5)で定義されているderive-key&ivメソッドが2つの多値を返す必要があるように変更されました

2012-10-17

ファイルの末尾に追加したい

ふと、R6RSの範囲でシェルで言う「>>」みたいなことができるのかなぁ?ということが気になった。

R6RSの範囲でファイルの末尾位置を取得する方法な無い(はずな)ので、outputポートのみを使うという方法は不可能である。となれば、input/outputポートを使用して、ポートを開いた直後に全部読み取ればポートの位置が末尾になるはず。ということで、こんなスクリプトで実験。
(import (rnrs))
(define out-file "out.txt")

(unless (file-exists? out-file)
  (call-with-output-file out-file
    (lambda (p) (put-string p "hello\n"))))

(let ((in/out (open-file-input/output-port
               out-file (file-options no-fail no-truncate))))
  (display (utf8->string (get-bytevector-all in/out)))
  (put-bytevector in/out (string->utf8 "hello\n"))
  (close-port in/out)) ;; これを忘れていた
#|
期待される出力結果。
1. 
 hello
2.
 hello
 hello

so on
|#
予定通りなら、期待される出力結果になって、末尾に追加されていることになる。とりあえず、Ypsilon、Mosh、Sagittarius、Chez、LarcenyとRacketで試してみた。

予定通りに動いた処理系:Sagittarius、Chez、Racket
全て上書き(helloを常に一個だけ出力)した処理系:Ypsilon、Mosh、Larceny

ふむ、ちょっとR6RSを読み返す必要があるらしい(またかよ・・・)。ということで、セクション8を読み返す。っで、面白いことに気づいた。以下面白い文章
(get-bytevector-all binary-input-port)    procedure 
Attempts to read all bytes until the next end of file, blocking as necessary. If one or more bytes are read, get-bytevector-all returns a bytevector containing all bytes up to the next end of file. Otherwise, get-bytevector-all returns the end-of-file object. The operation may block indefinitely waiting to see if more bytes will become available, even if some bytes are already available.
何が面白いか、どこにもポートポジションを更新すると書いてない\(^O^)/
他のget-bytevector関連は更新すると書いてあるのになぁ・・・ということで、スクリプトのget-bytevector-allの部分をget-bytevector-nに変更して512バイト読み取るようにした。
しかし、結果は変わらず。う~ん、これってYpsilonとMoshのバグなのか、R6RS的には未定義なのかどっちなんだろう?でも、input/outputポートってこういう用途に使うんじゃないのか?

上記の検証は嘘であることが発覚した。単にポートの閉じ忘れで、ポートを閉じないと、Ypsilon、MoshとLarcenyでは溜め込んだバッファをflushしないだけだった。逆にいうと、Chez、RacketとSagittariusではその辺に寛容でプログラム終了時(だと思う、SagittariusではGC時)にポートのflushを行っているというだけだろう。
恥ずかしい検証をしたけど、自分への戒めとして残しておくことにしよう・・・

2012-10-15

Portは閉じられるべきか?

デバッグをしている最中に「随分dynamic-winderがあるなぁ」ということに気づいた。スクリプトを眺めると、特にdynamic-windもguardも使われていない。あるのは、call-with-output-bytevector-portのみ。

そういえば、この辺の手続きはなぜかdynamic-windを使ってportを閉じているなぁと言うことを思い出し、R6RSではどう規定されてたっけと仕様書を眺める。あれ?何も書いてない。 call-with-portでは明示的にportは閉じられないと書いてあるが、勝手に作られる、しかも中身をR6RSの範囲では取り出しようがないものは手を抜かれたのだろうか?

じゃあ、別に閉じる必要ないよね。とは言っても、他の処理系の挙動と一応整合性を取っておきたい、ということで簡易テスト。
(import (rnrs))
(define p #f)

(guard (e (else (put-bytevector p #vu8(1 2))))
  (call-with-bytevector-output-port
   (lambda (port)
     (set! p port)
     (error 'ghehe "gehehe"))))
こんなの書いて、エラー投げなかったら閉じてない、投げたら閉じてるという感じで。

【結果】
閉じてる処理系:Ypsilon
閉じてない処理系:Chez、Racket(plt-r6rs)、Larceny、Mosh

閉じない方がメジャーな振る舞いっぽいし、call-with-portとの一貫性も取れるので閉じない方向で。

Monad on Scheme

Twitterでちらほら動的型付けでMonadなんてのが賑わっていたので、追随してみた。
CLで書かれていたのをScheme (Sagittarius)に書き直しただけなので非常に簡単ではあったが・・・
こんな感じ。
(import (rnrs) (clos user))

;; From following URLs
;; http://d.hatena.ne.jp/wasabiz/20121014/1350174261
;; http://basking-cat.blogspot.jp/2012/10/clojurestate.html
(define-syntax perform
  (syntax-rules ()
    ((_ ((name value)) expr ...)
     (fmap value (lambda (name) expr ...)))
    ((_ ((name value) . rest) expr ...)
     (bind value (lambda (name) (perform rest expr ...))))))

(define-generic bind)
(define-generic fmap)

;; List Monad
(define-method bind ((m <list>) f) (apply append (map f m)))
(define-method fmap ((m <list>) f) (map f m))

;; State Monad
(import (sagittarius object) (match))
(define-class <state> () ((run :init-keyword :run :reader state-run)))
(define (run-state m v) ((state-run m) v))
(define (eval-state m v) (car (run-state m v)))
(define (exec-state m v) (cadr (run-state m v)))

(define (make-state f) (make <state> :run f))

(define (get-state) (make-state (lambda (s) (list s s))))
(define (put-state) (make-state (lambda (_) (list '() x))))

(define-method bind ((m <state>) f)
  (make-state (lambda (s)
                (match (run-state m s)
                  ((a ss)
                   (run-state (f a) ss))))))

(define-method fmap ((m <state>) f)
  (make-state (lambda (s)
                (match (run-state m s)
                  ((a ss)
                   (list (f a) ss))))))

;; cursor
(define-class <cursor> ()
  ((x :init-keyword :x)
   (y :init-keyword :y)))
(define-method write-object ((c <cursor>) p)
  (format p "#<cursor (x ~a) (y ~a)>" (~ c 'x) (~ c 'y)))
(define (make-cursor x y) (make <cursor> :x x :y y))
(define (right n)
  (make-state (lambda (cursor)
                (let ((x (+ (~ cursor 'x) n)))
                  (list x (make-cursor x (~ cursor 'y)))))))
(define (down n)
  (make-state (lambda (cursor)
                (let ((y (+ (~ cursor 'y) n)))
                  (list y (make-cursor (~ cursor 'x) y))))))

(define (square n)
  (perform ((x (right n))
            (s (down x)))
    s))

(let* ((c (make-cursor 0 0))
       (es (exec-state (square 10) c)))
  (print c)
  (print es))

;; seqM and mapM
;; from https://gist.github.com/3889104
(define (seqM ms)
  (define (rec ms)
    (match ms
      ((m . ms)
       (if (null? ms)
           (fmap m (lambda (x) (cons x '())))
           (bind m (lambda (x) (fmap (rec ms) (lambda (y) (cons x y)))))))
      (_ '())))
  (if (null? ms)
      '()
      (rec ms)))

(define (mapM f ms) (seqM (map f ms)))

(define-class <maybe> () ((x :init-keyword :x :reader maybe-x)))
(define-method write-object ((m <maybe>) p)
  (format p "#<maybe ~s>" (maybe-x m)))
(define (make-maybe x) (make <maybe> :x x))
(define-method bind ((m <maybe>) f)
  (match (maybe-x m)
    ((:just . x) (f x))
    (:nothing (make-maybe :nothing))))

(define-method fmap ((m <maybe>) f)
  (make-maybe (match (maybe-x m)
                ((:just . x) (cons :just (f x)))
                (:nothing :nothing))))

;; Test
(define (buz xs)
  (define (bar x)
    (if (negative? x)
        (make-maybe :nothing)
        (make-maybe (cons :just (sqrt x)))))
  (mapM bar xs))

(print (buz '(1 4 9)))
(print (buz '(1 -4 9)))
Gaucheなら多分あまり手を入れなくても動くはず。TinyCLOSを持ってる処理系はキーワードの処理だけ何とかすれば、多少手を入れればいけるはず。
問題は、僕はMonadをよく分かっていないし、そのありがたみを享受したこともないので、こで何がうれしいのかいまいち分からない。Haskelやれってことか?

2012-10-11

低レベルのソケットAPI

将来的なことを考えると低レベルのソケットAPIがあった方がいい気がしてきたのでちょっとメモ。(僕自身がソケットプログラミングに明るくないので、間違いがある可能性が大いにあります)

現在主流になっているソケットAPIはBSDスタイルだと思う。というか、他を知らない。恐らく、このAPIの本質はUNIXの「全てはファイルである」だと思う。なのでソケット自体がファイルディスクリプタだし、わざわざrecv/sendとか使わなくても、read/writeで読めたりする。

Wikipediaを見ると、オリジナルのAPI自体は7つしかない。どの段階で物事が簡単じゃなくなったのか分からないけど(多分IPv6だと思う)、 現在ではいろいろ解決しなければいけないものがありそう。とりあえずのメモとして、どれくらい自分がサポートしたいかを考えることにする。

思いつくままに箇条書き
  • Wikipediaの7つのAPIの内、gethostbynameとgethostbyaddrを除く5つはサポート
  • ソケットのみノンブロッキングI/Oをサポート
  • select相当のAPI
    • fdsetがいるけど、どうするべ?
  • addrinfoは便利そうなのでうまいこと扱えるように
  • Unix domain socketはサポートしない
    • Windowsで提供できない(ことはないけど、面倒な)のでカット
  • JavaみたいにServerSocketとClientSocketを分けた方がいいかな?
  • IPアドレスの扱いはどうする?
う~ん、これさらに実装時には疑問が増えそうだなぁ。CLのusocketみたいに可能な限り隠蔽してしまった方がスマートだろうか?usocketが低レベルかと言われると、よく分からないけど・・・

2012-10-10

Socket in other words SRFI-106

I'm currently working on SRFI-106 which I proposed (wow, sounds like i'm doing something cool, haha).

Now, I'm wondering if it's possible to make extensible APIs for future socket changes. The trigger to think is this message;
However, an API that is designed so that implementations can extend it to support things like Unix domain sockets, etc. without changing the basic design of the API might be better.
From SRFI-106 mailing list
 I super agree with it. But is it possible? To make this simple, let me target only Unix domain socket.

As far as I understand, Unix domain socket means file system socket like /tmp/socket1.s or something like this (, isn't it?). To create this, create a socket FD passing AF_UNIX (or AF_LOCAL) flag to socket(2), set filesystem path string to struct sockaddr_un's sun_path member, then call bind(2) with socket FD and sockaddr_un set before. This is UNIX (or POSIX) way to create local socket.
Now, let's see how it goes with Windows. Well, unfortunately Windows doesn't have this type of socket. If you want to do sort of the same thing, you need to do either creating a local address socket or using PIPE. Creating a local address socket would be portable way but occupies a port. Using pipe provides the same thing as UNIX but code won't be portable.

Yes, implementation can wrap those ugly part with beautifully abstracted API (if i can...). Or if AF_UNIX equivalent flag is passed on Windows environment, implementation can just raise an error.
Well, then here comes my next question. Is it basic? I might stick too much with this word. But I would rather make small world than bigger and lower layer world with this SRFI. Flexisibility is important. I believe simplicity is also important. I think I'm too lazy to introduce a lot of features such as addrinfo data type or other procedures. And it might be from my ignorance of socket programming.

Sort of brain storming. I'm still thinking if there is a nicer way to keep both flexibility and simplicity as much as possible.

2012-10-06

中置記法

CourseraのScalaコースでScalaで中置記法が書けるということを知った。
こんな感じ
class Foo(x: Int) {
  val v = x
  def +(y: Foo) = new Foo(v + y.v)
  def less(y: Foo) = v < y.v
}

new Foo(1) + new Foo(2)
C++の演算子のオーバーロードに似ているけど、イメージとしては単に関数定義。Scalaは割りと自由にシンボルが定義できる。Schemer好みともいえる。のだが、多分演算子だけを特別視したくなかったんだろうなぁと思うのが、以下の記法。
new Foo(1) less new Foo(2)
SRFI-105でも感じた「うわぁ・・・」感漂う何か。何故かはいまいち分からないけど、どうも読みにくいと感じる。僕の主観だと思うんだけど、これが読みにくいと思うのはあまりにも自然言語に近いからだと思う。僕はあまり国語が得意ではなかったところに起因があるのかもしれないが・・・

それに加えて、中置き記法は評価の優先順位が問題になってくる。まぁ、常識人なら()で囲って優先順位を明確にするだろうけど、なんでそんなことを人間が考えなくてはいけないんだろう?と思ってしまう程度にはLisp脳になっているのかもしれない。(いや、単にものぐさなだけだろう)

コンパイルしてしまえばJavaからでも使えるし、REPLもあって開発効率は高そうなイメージなんだけど、じゃあ仕事で使いたいか?といわれると今のところ微妙な感じ。(でも、Scalaでやるよ~って言われたら喜んで飛びつきそうなくらいにはJavaに飽きている・・・)

2012-10-05

必要ドリブン

泥縄とも言うのだが・・・(しかも、絶対的に必要というわけでもない・・・)

SOAPリクエストを投げる必要が出てきた。まぁ、ぶっちゃけSoapUI使っておけよという話になるのだが、いろいろなことを自動化するのにGUIを使うのは都合が悪い。1ヵ月後の自分が楽できるように今のうちに仕込んでおくのが怠け者の鑑というものだろう。

ということでSOAP的な何かができるライブラリを作った。タイトルはあんまり関係なく、どちらかというとどんな風に設計したのかという覚書。

実はSOAPを扱うライブラリはほしいなぁとずっと思っていて(まぁ、仕事で使うからなのだが)、3ヶ月くらいどうしようかなぁともやもやしていた。理由はJavaとかC++とか見たいにWSDLからクラスを自動生成してとかってやるのがかったるいとずっと思っていたから。そもそもScheme(というかLisp系言語)はS式というこの上なくXMLと親和性の高いデータ構造を息をするように扱うことができる。じゃあ、他の言語が必要とするXML→マッピング→オブジェクトなんていらんじゃん、と思っていたからだ。

もやもやすること3ヶ月、とりあえず動くものが欲しい(というか要る)と思い、適当に使いやすいと思うものを作ってみた。ポイントとしたのは、
  • オブジェクトマッピングみたいなことはしない
  • そこそこ柔軟に書ける
  • リクエストを送ってレスポンスを返す
出来上がったのが、これ

自分で使った感想としては、まぁ悪くないんだけど、一々手書きでタグの定義を書くのは面倒だなぁとは思った。なので、改善点としては、WSDL解析してdefine-soap-type定義を自動で作ることかなぁ。

2012-10-04

職業プログラマ

ふとこんな記事を見つけた。

[徒然]そろそろ潮時? - Kazzzの日記
何時からだろうか、職業プログラマとして生業を全うしたいと思いながら仕事をしていたのだが、今の職場ではもうそれを許してはくれなさそうだ。 許してくれないというよりは正確には「認めて貰えない」と言った方が良いだろうか。
プログラマのコストと会社の利益について書かれていた。僕が日本でかつプログラマとして働いた期間は2年と短い(オランダでのプログラマ歴の方が長くなってしまった)のだが、その短い期間でも同様の不満というか「それおかしくね?」という疑問を持った記憶がある。

なぜ、単価はPG < SE < PMなの?
PMは顧客と交渉するから(これ営業の仕事ちゃう?)?人的リソースとスケジュールの管理をするから?
SEは仕様書を書くから?見積もりだすから?(これも営業の仕事ちゃう?)
でもものを作るのはPGだよね?安い労働力に見合った品質で十分ということなのだろうか?年功序列で給料が決まるなら、年功序列でPG->SE->PMでいいと思うけど、本人の能力に対しての対価として給料が決まるなら、原価が安い=品質が落ちるに繋がる気がするんだけど、違うのかな?

その昔、営業が1億で取ってきたけどSEが見積もったら赤字になる案件で、営業は高評価、SEは遂行できなかったから低評価というようなのを見たことがある(実際体験もした、金額は違うけど)。これって、無能な営業が安請け合いをして結果的に営業の責任で会社に損害を出したんだけど、全部SEに擦り付けられてるよね?っで、そのSEの下でものを必死になって作ったPGはさらに納期が守れなかったって非難される・・・おかしくないかなぁ?

優秀なプログラマは希少価値が高いと思うのだが、どうも十把一絡げ的に扱われている気がしてならない。僕も職業プログラマとして生涯現役でありたいと願う身なので、この手の話はいつもやりきれない思いが付きまとう。(自分が優秀どうかは知らんが・・・)

幸い、現在の職場は、PM、TM(テクニカルマネージャ)、PGと分かれていてそれなりに分業が出来てるし、PGだから給料が安いということもない(と思う。他人の給料知らん)。

2012-10-02

絶対に明文化されないライブラリのメモ

Sagittariusには開発者が既存の機能のバグをビルドすることなくテストするライブラリがあったりする。(実際はライブラリという形式を取っているだけで、そういう機能があるのだが)。
この機能は僕が(主にマクロ展開器の)バグ取りように使うだけという位置づけにしてあるものの、普通にライブラリとして提供されている。ドキュメント化は絶対されないし、するつもりもない。っが、遊びとして使う分には面白い機能なので、興味がある人は触ってもいいかなぁと思いメモ。(と将来の自分への備忘録)

ライブラリは(現状では)(sagittarius aspect)という名前で提供されていて、このライブラリは(Again現状では)point-cutというマクロを提供している。名前付けは正直微妙だなぁと思っているので、将来のバージョンでは変更になるかもしれない。まぁ、でも使用頻度はそうないしこのままかもしれない。
使い方は以下のようになる。
(import (sagittarius aspect))
(point-cut
  (core syntax-case)
  expand-syntax
  (lambda (vars template ranks id-lexname lexname-check-list p1env)
     (let ((r (proceed)))
        (print r)
        r)))
マクロがproceedという手続きを提供するので、単に結果を覗きたいだけならこんな感じで書ける。結果が意にそぐわないものであれば変更も出来る。また、オリジナルの処理をせずに(proceedを呼ばずに)自分で再実装しても構わない。
気をつける点は、そのライブラリで定義された手続き自体を変更するということ。この変更がどこかのライブラリの挙動を変更するのである。例としては、
(library (foo)
    (export bar)
    (import (rnrs))
  (define (bar) 'bar))

(library (hoge)
    (export fuga)
    (import (rnrs) (foo))
  (define (fuga) (display (bar)) (newline) 'fuga))

(import (hoge))
(fuga)     ; prints bar and returns fuga

(import (sagittarius aspect))
(point-cut (foo) bar (lambda () 'gehehe))
(fuga)     ; prints gehehe and returns fuga
上記の例では、手続きfugaは一切変更されていないが、依存するライブラリ(foo)内で定義された手続きbarが変更されているので、fugaに影響が起きている。モジュールシステムそのものを破壊する禁じ手ではあるのだが、使い方によっては便利に使えるので入れてある(自分用)。

そういえば、似たような機能で明文化されているのはwith-libraryマクロだろう。あっちはオリジナルを実行して値を覗くということは出来ないが。

2012-10-01

R7RS 7th mini ballot result

I can't believe it's October. The time flies like an arrow, indeed (T_T)

Super postponed ballot result has been revealed. How long did they postpone? 3 weeks? I remember they said it's a small one so only a week. Liar!

Anyway, let me check what is the impact of it. I remember they were discussing how expt should behave.

#121
Now R7RS requires to signal error with the expression (expt 0 z) when z is negative. I believe this is incompatible change since I haven't seen any implementation raises error with this case. (Ypsilon, Sagittarius, Mosh, Gauche and Chibi(?!)). I agree with that the specification should not allow implementations to choose either unspecified value or error but hmm, is this nicer than R6RS?

#472
For me it's trivial, because I don't have intention to change current implementation of cond-expand, include and include-ci. But I think it's better if I can write like this;
(import (scheme base))
(cond-expand
  (sagittarius (import (srfi :1)))
  (else (import (srfi 1))))
;; bla bla
Does the result allow us to this? I actually couldn't understand properly:P

#473
I'm really disappointed with this decision. I think R6RS's toplevel restriction was too strict and it's better to be able to write import clause everywhere for small scripts. But they decided only beginning. It might be much better because now we can write the code above officially but hmm... No, we can't write the above code on toplevel according to the result. If we want to write the compatibility layer, we need to write it in a library then import it. Shit!!

#405
They have decided to keep compatibility with R6RS. (force 2) can raise error.

Only 4 items! But they needed 3 weeks?! I wish draft 7 will be released in this week...

BTW, why did I write this in English?

2012-09-26

多値を考える

ずっと放置していた問題の一つ。

最近2chのLisp Schemeスレッドで多値が話題に上がっていて、せっかくだし便乗して考えることにした。(意味不明)

Sagittariusでは多値は第1級オブジェクトになっていて、valuesを呼ぶたびにメモリのアロケーションが走る。これは実は実装の手抜きで、
(apply values (iota 10000 1))
のようなコードをとりあえず走らせるための妥協の産物となっている。ちなみに、Gauche 0.9.3とMosh0.2.7ではこのコードはエラーになる。多分Gaucheは0.9.4辺りできっと直されるだろう(希望的観測)

valuesに期待したいことの一つとして、「これ使っておけば処理系はconsicingしない」というのがある(と思う)。そういう意味ではSagittariusはプログラマの期待を裏切っているわけだ。

自分自身、せっかくvalues使うんだしという感もあるので、現状の上限なしを維持しつつある程度は期待を裏切らない実装にしたい。案としては以下のようになるだろう。
  • ある程度割り付けておいて、あふれた分は都度割付
  • 必要になったら割付してそのバッファを再利用。足りなかったら再度割り付け(Racket方式)
一つ目と二つ目のどこに違いがあるのか?というレベルだが、実装レベルでは多少違うはず。一つ目は上限超えた際に常にメモリ割付が発生するが、そもそもvaluesに(こちらが考えた)上限を超える値は渡されないだろうという楽観的な実装になる。二つ目はユーザは常にこちらの想像を超えるものだが、それを見越してある程度の性能を出しておきたいという悲観的実装になる。
正直、一長一短ではあると思うが、二つ目の実装で困りそうなのが、上記の例みたいなことをされた際に10000個のバッファを常に保持する羽目になることだろう。多分、どこかの段階でGCされるような仕組みにしておかないと、不必要なバッファがメモリを食いつぶすなんて事になる。

さて、どうしたものかな。

2012-09-22

括弧ゴルフ再び

リードマクロを実装したときに書いたネタ再び。(書いたよね?)
ちなみに、元ネタはこちら
本当にLispはカッコが多い? - 八発白中 
今回はSRFI-49という最強の武器(w を持ったのでこんな風に書ける(0.3.7)
#!reader=srfi/:49
import
  srfi :1

define
  fact x
  if
    = x 0
    1
    * x
      fact
        - x 1

define
  printer i
  print i " ! = "
    fact i

define
  main args
  for-each
    printer
    iota
      if
        null? args
        1
        string->number
          cadr args
      1
Readerの切り替えに#!を使うので括弧0を実現可能!!!wwww
SRFI-49をサポートしている処理系(今のところSagittariusだけっぽい) ならSchemeで括弧ゴルフに勝利することができる。
なんだか、行き着くところまで来てしまったか感がする。

2012-09-21

ユーザー定義のReader

こんな意見をいただいた。
これはいい!ということで、こっちにしてみた。

多少そのままではまずいので、定義を以下のように変更。
#!reader=srfi/:49
これで、今回ならSRFI-49を読み込むようになる。見ればすぐ分かると思うけど、(srfi :49)がsrfi/:49と変更されている。多少以上に醜いのはこの際目をつぶらないといけない。「.」とかだとライブラリ名が含んでいる可能性があるので「絶対含めることが出来ない文字」にする必要があったのだ。これならファイルシステムがエラー出すので、「実用上ありえない」が少なくとも保障される(少なくともWindowsとUNIX系OSなら)。

それに伴って一つ前の使用例を修正。この形式ならリーダマクロもいけるよなぁ、ポータビリティのために追加しようかな。

SRFI-49をまじめに検討してみる

きっかけはこの一言
ないのか?ならば最初の処理系になってみようではないか!おぉぉ、燃え上がれ俺の小宇宙!

と、ここまで意気込むのはいいんだけど、このSRFI先頭にマークがあるわけではないし、105のように{}で囲まれているわけでもないのでreader(日本語で書くとleaderと混同しそう)そのものを置き換える必要がある。
確かに、参照実装のGuileではオリジナルのreadをこれように上書きしていたが、Sagittariusではファイルから起動する際はCで書かれたread相当の関数を直接読んでいるので上書きしても嬉しい結果にはならない。むしろ悲しくなる。
また、この面白SRFIを適用したした結果他のファイルに影響があっても嫌だ。となると、リードマクロと同様、適用したファイルのみに働くことが絶対条件かつなんらか既存のreaderを置き換える仕組みが必要になる。

実は腹案が既にあって(朝起きてシャワー浴びてたら思いついた)、ライブラリ自体に一つだけreaderを持たせることを許せば、持っていない場合はデフォルトで持ってる場合はユーザ定義という形で振り分けができそう。多少のオーバヘッドがかかるが、これを入れれば単に面白SRFIのサポートのみではなく、Cで書いたと思ったのにSchemeで実行されているでござる!ということが可能になるかもしれない。(結局ネタだな)
暇なので(これがいけない、ネタがあると飛びついてしまう)、この方針でとりあえず実装してみることにする。

2012-09-14

Sagittarius 0.3.6 リリース

今回のリリースはメンテナンスリリースです。
ダウンロード: Sagittarius Scheme

修正された不具合
  • SOBER-128がpseudo-random手続きで初期化不可能だった不具合が修正されました。
  • read-delimited-listがcustom textual portに対してCレベルのアサーションで落ちる不具合が修正されました。
  • リードテーブルが#!r7rs及び#!compatibleでリセットされない不具合が修正されました。
  • import句のprefix が正しく動作しない不具合が修正されました。
  • (syntax bar)が正しいライブラリを参照していない不具合が修正されました。
新しく追加された機能
  • mod-expt及びmod-inverseがCでより高速に書き直されました。
  • syntax-case及びsyntax-rules(R6RS版)がシンボルのリネームを行うようになりました。
  • path-for-each、path-map、delete-directory*及びcreate-directory*が(util file)ライブラリに追加されました。
  • copy-file手続きが追加されました。この手続きはOSの機能を使ってファイルをコピーするので、高速に動作することが期待できます。
  • list->stringがオプショナル引数startとendを取るようになりました。
  • read-random-bytes!手続きが(math random)に追加されました。
新たに追加されたライブラリ
  • SRFI-86、SRFI-31、SRFI-29及びSRFI-43がサポートされました。
改善された機能
  • split-at手続きが末尾再帰になるように書き直されました。
  • condがSRFI-61スタイルをサポートするようになりました。
互換性のない変更
  • カスタムハッシュのread-randomスロットの名前及びセットされるべき手続きが取る引数が変更になりました。詳しくはドキュメントを参照してください。

2012-09-12

マクロ戦争ひとまず終結

マクロの不具合に出会うたびに戦争だといっているだけ。それくらいR6RSのマクロ周りは複雑怪奇だと僕は思っている。

一つ前と二つ前の記事でマクロ周りの不具合が(まだまだたくさん)残っていることを書いたが、黒魔術的な処方を用いて直すことに成功したのでちょっと備忘録。

何が問題だったか?
2つの問題があって、1つはマクロを生成するマクロが生成した識別子の問題。もう一つはリネームの問題。

識別子の問題
問題点は2つ前の記事に書いたので、どう解決したかだけ。問題になるのはsyntax-caseのテンプレート部分のみだったので、どこにも束縛されていない識別子のライブラリを展開されているライブラリに置き換えるようにした。記事のコードで言えばdummyがあたかも(test-lib)内で定義されるかのように振舞うよう変更した。(本来はそうあるべきだった)。
ただ、これだけのことでも一筋縄ではいかず、結局コンパイラに手を入れたりと結構な量の修正が入った。問題だったのは、ライブラリ内で展開されるマクロがそのライブラリで定義された値を知っている必要があって、Sagittariusではその情報はコンパイラのみが知ることができるもの (マクロ展開器は構文について一切知らない)なので。これを入れたので、恐らくやろうと思えば未定義の値の参照を検出したり、未定義なexportを検出したり出来るはず。(まだやらない)

リネームの問題
これは本当に苦労した。一つ前の記事で書いた動作の修正になる。これについてはあほみたいな黒魔術を使って直した感があるが、そのうちリファクタリングしてやるという意思表示のためにどう直したかという恥をさらす。
Sagittariusにはgensymがあるのだけど、それを少し拡張して、与えられたシンボルに戻すことが出来るreversible-gensymという手続きを導入した。なぜこんなものが必要だったかと言えば、syntax-rulesやsyntax-caseにあるリテラル(キーワード?)の処理に必要だったから。単純にリネームしただけではこれらのキーワードが比較不可能なシンボルに変換されてしまうが、それはマッチする際に比較できずパターンエラーになる。なので、マッチする際にリテラルを強引に元に戻すという荒業を使っている。スマートな解決策がほしいところだが、僕の頭ではいい案が出なかった。

 問題になるかもしれない変更点
 リネーム問題の解決するに伴い、「それどうよ?」的な変更が入っている。それは、syntax-rulesもしくはsyntax-caseで定義されたリテラルが暗黙の内にマクロとして定義される。まぁ、大きな問題としては、unboundだと思って&assertionを期待していると&syntaxが飛んでくるようになった程度か?

とりあえず、0.3.6でマクロ周りが多少改善されるはず。小宇宙が少し高まっただろうか?

2012-09-11

syntax-rules

マクロ周りは非常に奥が深くて僕では溺れてしまうという話。
昨日の記事を書いた後(しばらくは冪剰余やってたけど)気づいた。そういえば、Sagittariusではsyntax-rulesを使ってdummyみたいなことは出来ないと。
ということで、テスト。
;;(import (rnrs))
;;(import (scheme))
(define-syntax test
  (syntax-rules ()
    ((_ var val)
     (begin
       (define dummy val)
       (define (var) dummy)))))

(test a 'a)
(test b 'b)
(display (a)) (newline)
(display (b)) (newline)
最初のコメントは処理系に応じて入れたり消したり。試した処理系。
  • R5RS Gauche、Racket(plt-r5rs)
  • R6RS Ypsilon、Mosh、Petite Chez Scheme、Sagittarius(R6RS?)
  • R7RS Chibi-Scheme(一応そう謳ってるし)
とりあえず、ほしい結果は多分以下。
#| R6RS的にはこうだよね?
a
b
|#
#| 字面的にはこうでもよさげ?(2)
b
b
|#
dummyというシンボルを使いまわしているように見えるので、(2)でもいいような気がしないでもない。(R6RSまじめに読んでない、R5RSは目を通したことすらない気がする・・・)
結論を言えば、Racket、Ypsilon、Mosh、Petite Chez Schemeは最初の結果、残り(Gauche、Chibi及びSagittarius)は2番目になった。

分かっていたんだけどね、こうなるって(Sagittariusの話)。そして、これは現状のつくりを維持するなら正直直しようがない。原因は2番目の結果になった処理系は、dummyを参照することができるということ。Sagittariusは確定なんだけど、恐らく残りの2つもマクロ展開時にシンタックスの情報を持っていない。なので、dummyとdefineの区別がつけられず、シンボルのrename(もしくはunintern)を行えない。

単純な話、上記の例で言えば、2つのdummyは同じrenameされたシンボルに変換できる。そうすると、トップレベルではdummyというシンボルは何かしらにrenameされているので見えないが、varが束縛(捕捉?)したdummyは同一のものにrenameされているのでそこからは見える。

これ多分、明示的にマクロ展開のフェーズを持たないと無理じゃないかな?もしくは、マクロ展開器がもっといろいろ知っている必要がある。あぁ、でもそれくらいならいけるかな?

結局、テンプレートをre-writeする際に、それがグローバルに束縛されているならそのままで、そうじゃないものならrenameとかすればいいかも。(でも、やるなら0.3.7以降だな。0.3.6はリリースが近いから無理だ)

これって、R5RSとR6RSで明確に定義されている非互換な動作なのだろうか?

2012-09-10

マクロ、マクロ、マクロ

Sagittariusを試してもらえているというのは非常にありがたいし、嬉しいことである。それがたとえ動かない動作であっても(T_T)

動かない動作は以下のサイトより
衝突回避と暗黙のimport - 主題のない日記 

id:SaitoAtsushさん(こう書くのがHatena流だっけ?)は僕が絶対書かないタイプのマクロをガンガン書かれて、しかもそのテストにSagittariusも使ってくださっていてなんともありがたい。
ただ、まともに動いたことがない感じがするのがとても心苦しかったりもするだけれど・・・(R6RS名乗るの無理になってきたか・・・?)

さて、今回の不具合はパッと見、恐らく現状のマクロ展開の仕組みを使っていると直すのがかなり厳しい気がする。問題なのは、define-settable内で定義される識別子(ここではset-dummy!)は自身の定義されているライブラリの参照としてオリジナルのライブラリ(settable-variable)を持つ(はず)。そうすると、(test-lib)内で定義されているにも関わらず、参照を解決する際にオリジナルを見に行く。っで、unbound variableが投げられて悲しい思いをする。というのがパッと見た感じのエラーの原因と思う。
(あれ?でもこんな感じのマクロはdefine-record-typeとかでも普通に使われているはずだから、そんなはずないよなぁ?)

見た感じ、このマクロは結構コーナーエッジっぽいみたいで、意図どおりに動く処理系はRacketとYpsilonのみっぽい。実際手元のnmoshで試したらエラー投げた。
ちょっとpriority低めでIssue上げとくか・・・

冪剰余

まだ実装中なんだけど、必要な部分は出来て動いたのでちょっとベンチマークを取ってみた。
(import (rnrs) (crypto) (math) (time))
(time (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4)))
自宅のX60で2048bitの鍵を作るのは自殺行為なので1024bitで。っで、以下が結果。
$ sash test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  4.265625 real    4.188000 user    0.078000 sys

$ ./build/sash.exe -Llib -Lsitelib -Lext/crypto test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  0.953125 real    0.890000 user    0.046000 sys
下が開発版。4倍程度高速になっているのが分かる。これくらい高速なら実用に耐えるだろうか?まだJavaと比較すると2倍から3倍遅いが・・・(比較する対象が間違っているのかもしれないと思い始めてもいる。)

Javaの実装に習って、Miller Rabinテストの試行回数を1024bit以上の時は2回にしてメルセンヌ数をチェックする処理を試したんだけど、結果が返ってこなかった。多分ヤコビシンボルを探すのが遅いのだろう。さすがにそこまでC側で実装するべきか悩むところだ。(Lucus Lehmer法自体がBignumを直接操作しないと遅いのかもしれない。まぁ、後の課題にする。)

mod-exptの動作としては、まだ対称の数(x ^ e mod mのx)が偶数の場合の処理が未テストかつ多分動きがおかしいはず。テストを書きつつ動作を検証していかないと。

Open Monumentendag@Haarlem

I actually didn't know what open monumentendag was. But I went there.

This was meetup stuff and originally it was Utrecht however organiser had just heard that most of the monuments were closed on Saturday so he changed it to Haarlem. Well, I've never been to Haarlem before (even though I've been living here for 3 and half years already!) so there was no reason not to go;)

 Central square? I don't know the place name. The sun glasses guy was the organiser.

 Inside of the city hall (if I following the explanation correctly...)

 They have a huge draw.

 Inside of the church which was on the first photo. Male choir was there. They were pretty good.

Should be a pipe organ. But I also saw a much smaller one, so this might not be the one.

Yes, as you already know I'm not a good photographer, so the photos are that's it.

Then we went through the city and into some museums. It was quit interesting to me. The city itself was totally different from other cities such as Leiden, Amsterdam or the Hague. (I don't know much about Rotterdam even though I work there:P)

2012-09-09

冪剰余実装中

単にメモリ割り当てを減らしただけでは鍵対生成に対して実用的なパフォーマンスが得られないことが分かったので(2048bitで5秒からかかる)、どこが遅いかを調査した。結果、素数テストを行っている手続きで使用されている冪剰余の計算が遅いことが判明。x^e mod mを計算する際のx, e, m全ての数が2048bitあった際に20秒かかるという脅威の遅さだった。(3GHz Core i7)

Javaは2048bitの鍵対生成でも同マシンで1秒以下の時間で作ってくる。篩とかあるけど、何より素数チェック、その中で使われている冪剰余が高速なのだと仮定して実装をチェック。素数チェックはTwitterでも呟いたけど、Miller Rabinテストが1024bitを超えると試行回数が2回で、その代わりメルセンヌ数のチェックが入っていた。冪剰余についてはColin PlumbのBignumライブラリを元にした高速な実装になっている。

現状Sagittariusでは冪剰余を求める際に単純なバイナリ法を使っている。普通に
(mod (expt x e) m)
とするよりは遥かに高速なのだが、数値がBignumになってくると計算の度にメモリ割り当てが入りあまり嬉しくない。(eは1bitずつ右シフトされるので、2048bitあると、32bit環境では単純計算で2000回以上の割り当てがexponent部分だけで発生する)。
上記の実装(とりあえずはJavaの)ではメモリ割り当てがかなり削られている。正確には数えていないが、最大でも20回行かない程度に抑えられそうである。

ならばやらないわけには行くまいと、とりあえずJavaから実装を移植したら嵌った。

問題になったのはJavaのBigIntegerは内部で持っているintの配列のオーダーがSagittariusとは逆順になっているのだ。理由は知らないんだけど、きっとその方が効率がいい場面が多いのだろう。もしくはPrimitiveな配列でさえサイズを取ることができるからなのかもしれない。なので、単純にJavaから実装を持ってくるのは失敗に終わった。

恐らく中で何をやっているのか理解してやれば逆順に対応するのも難しくはないのだろうが、高速なモントゴメリ法の実装自体に興味があるわけではないので、可能な限りその労力は避けたい(ものぐさ)。ということでオリジナルの実装を当たってみることにした。←いまここ

2012-09-05

マクロ展開時のライブラリ

以下のツイートを発見。
動かないのは許せない(というか、バグだし)ので、原因を探る。元コードはきっとこれだろう。
文字列補間 - 主題のない日記 
とりあえず、走らせる。&assertionか。なんとなく既に嫌な予感がしている。 いろいろ省略して原因箇所:
(datum->syntax #'string-interpolate 'x->string)
これ。全体というよりも、#'string-interpolateの部分のみ。

何故か?これ多分マクロ展開器の根幹の問題で、(syntax foo)という構文は定義されたライブラリ内ではなくimportされた先のライブラリで解決される。つまり、識別子が所属するライブラリがおかしいのである。なので、datum->syntax手続きが、#'string-interpolateからx->stringを作る際に本来ならば定義されたライブラリの情報を付加しないといけないんだけど、importしたライブラリの情報を付加する。結果、unbound variableといって怒られる。

とりあえず、一時的なしのぎとしてx->stringもexportしてしまうのが最も簡単な解決方法であろう。0.3.6以降のどこかで頑張って直そう。ちょっと(かなり?)大き目のバグが2つになった。燃える(φΛφ)

やはりいろいろな人に検証してもらうのは非常にありがたい。僕一人では恐らく未来永劫気づかなかったバグだ。

相手の言いたいことを想像する

こっそり転職活動をしていて、ふと思ったこと。ちなみに、行間を読むのではなく、もっと物理的な話。

こっちでは(僕があんまり熱心に転職活動をしていないからなのか)、エージェントが電話もしくはメールを送ってきて求職条件にマッチしたら先に進めるという、どちらかといえば受動的な感じでことが進む。もちろん、自分から応募した場合は向こうの条件に職歴等がマッチした場合のみ先に進む。この辺はどこでも一緒だろう。

さて、現在僕は1件面接が予定されていて今日の午後にそれに行く予定である。っが、それは別の話。今回はその面接をアレンジしたエージェントの話である。

よく、「オランダ人では話しかけた言語で会話を進められる」といわれるくらい言語能力が高いと信じられている。まぁ、ヨーロッパ内の言語なら概ねそうと言えるが、もちろん例外もいる。件のエージェントはどちらかと言えばその例外に当てはまる方のタイプで、ちょっと英語能力が怪しい。そうすると、たまに「何が言いたいのかいまいち分からない表現」というのが出てきて、多分これかなぁと想像することがある。正直なところこれが結構きつい。

何故きついか?普通に日本語を勉強している外国人と会話する際のことを思い浮かべればいいだろう。途切れ途切れで話すとか、言い回しがなんだかわけの分からないものだったりとか、そんな感じ。そうすると、多分こういいたいのかな?と推測をするわけだ。問題は、母語であればその推測が大抵当たるし、そんなに大変じゃないんだけど、第二外国語以降の言語だと習熟度に応じて難易度が変動する。僕の英語はリーズナブル(なんて訳すといいんだろう?)レベルだと思っていて、その手のことをするのは結構しんどいのである。特に、つっかえつっかえだと1秒前に言われた言葉が頭から抜けるのだ。

理解できなかった部分はどうするのか?聞きなおしても同じことが起きるので、「とりあえず最後にメール送ってくれるように聞いてみるか」となって理解を放棄する傾向にある。水は低い方に流れるのだ。あまり、相手の言いたいことを想像しない。よくない傾向である。

ちなみに、この現象は人ごみの中で電話をとったときとか、バスの中、電車の中でも起きる。雑音の中から向こう側の声を拾えないのである。(取りこぼすといった方がいいか?)。これは単純に言語能力の問題なのでヒアリング能力を上げるしかないのだが。

こういう細かい部分ってどうやって鍛えればいいのだろう?なにかいい方法があれば是非教えて欲しいです。

2012-09-04

メモリ使用量

Sagittariusは割りと富豪的にメモリを喰う傾向にある。理由はいたって単純で、いろんなところで利便性のため冗長な情報を持たせているからである。

っが、それでは困ることが出てきた。テストを走らせるとかなりのメモリを消費し、Cygwin上でメモリ不足で落ちることがあるのである。地道に不要なオブジェクトをGCフレンドリにしたりして、50MB程度使用量を削ったのだが、焼け石に水感が拭えない。結局後100とかテストファイルが増えれば元の木阿弥な気がするからだ。

実は何が冗長な情報を持っているかは分かっている。ライブラリだ。どこかで書いたがSagittariusではライブラリもオブジェクトでその中にいくつかのメタ情報を持たせてある。importやexportの情報だ。 この二つは必須なので削りようがないのだが、もう一つ、そして恐らく大量にメモリを消費している情報で、親ライブラリ情報がある。これは何をしているのかと言えば、どのライブラリから何がimportされたかという情報である。たとえば以下のコード;
(library (lib1) (export v1) (import (rnrs)) (define v1 1))
(library (lib2) (export v1 v2) (import (rnrs) (lib1)) (define v2 2))
(lib2)は(rnrs)と(lib1)を親ライブラリとして持ち、(lib1)からv1を(rnrs)からは全てのシンボルをimportしているという感じである。

これが、かなり冗長(無駄ともいう)情報を持っていて、たとえば、(rnrs)は親に(rnrs base)とか持っていて、(lib2)はそれが何をexportしているという情報を全て持っている。なんでそんな冗長にしてあるかと言えば、ライブラリから値を引っ張り出してくる際に、その方が楽だからなのだが、はっきり言えば無駄である。実際、import情報だけあれば、全て解決するものであるのだからだ。

このライブラリの実装は複雑怪奇になっていて、正直自分でも必要がなければ構いたくないレベルになっている。(キャッシュもそうだが・・・)。っが今回必要が出てきてしまったので、頑張ってリファクタリングすることにする。とりあえず、意思表示だけ。

RSA key generation

I wasn't satisfied with the performance of RSA key pair generation at all since Sagittarius supported cryptographic operations. So I've done a lot of performance tuning such as bytevector->integer, integer->bytevector procedures. These changes, however, did not make that much difference even it's been improved 100 times faster than previous implementation.

Why? Actually I knew why. The prime number generation was really slow. It reads random number each time and checks if the number is prime or not with Millar Rabin test. In this prime number generation procedure, bytevector->integer is used so I thought if I improve the performance it would be changed dramatically. I've bet on the wrong horse, unfortunately.

Then I let it be for long time (I guess 3 month or so?) and I've got an idea today. The random number generation creates fresh bytevector each time, what if I modified it to read destructively. So I have introduced read-random-bytes! procedure and modified random-prime to use it. Now it's benchmark time. I used following code which generates 1024 bits RSA key pair.
(import (crypto) (math) (time))
(generate-key-pair RSA :prng (pseudo-random RC4))
To make sure the key generation procedure uses the same random generator, I specified :PRNG keyword. The result is below;
% sash test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  1.7565269470214844 real    1.826000 user    0.047000 sys

% ./build/sash.exe -Llib -Lsitelib -Dbuild -L./ext/crypto -Lext/time test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  0.769230 real    0.749000 user    0.031000 sys
Yes! It's improved as twice fast as before. The problem is, however, this change, more specificaly read-random-bytes!, introduced imcompatiblity of 0.3.5. Well, the change only affects custom pseudo random generator and I guess it's used by only me. So just wrote note on the document.

2012-09-02

続 exportされた変数

一つ前の記事で、実行時エラーにしていたがえいやっとコンパイル時エラーにすることにした。

Sagittariusではライブラリも(実は)First class object(訳語忘れた)で、普通のR6RS処理系がするようなライブラリをrenameしてごにょごにょということは(いい悪いは別にして)行わない。 マクロ展開フェーズというものもなく、全てコンパイル時に解決している。これは、マクロ展開器とコンパイラで定義が被るのが嫌だったので。似たようなコードがそこかしこに出てくるのが我慢ならなかった。

本題に戻る。なので、ライブラリが別であれば、識別子は被っても問題ない。lookup(訳語知らない)時にimportされているものを調べて合致したものを返しているだけなので。なので再定義されても、参照される先が変わるだけ。正直特に必要性を感じていなかったし、今では面倒になっただけかも感があるのだが、規格に準拠するのもポータブルなコードを書くのには欠かせない部分だろうと重い腰を上げた感じ。

どう実装したか?
実は非常に簡単で、グローバルに値を定義できる構文と値を変更できる構文ってSchemeでは合計で3つしかない(よね?)。つまり、define、define-syntaxとset!の3つ。前2つは定義された値が同じライブラリ外で既に定義されていればエラーを投げる。set!は先に局所変数を探して、違ったら大域変数なので、その際にチェック。
問題だったのは、bootコードを生成するSchemeコードが再定義を前提で書かれていること。全部ライブラリ形式に書き換えてすっきりさせるというのもありだったのだが、面倒だったのでとりあえず再定義可能なモードを急遽入れて対応。ごにょごにょ黒魔法的な何かを使うよりはいいだろうと思う。そのうち書き直そう。

ちょっとした課題?
正直デフォルトで書き換え不可はあまりに面倒だなぁと思っているので、R6RSもしくはR7RSモードの際だけにするかもしれない。テストケースをコンバートしている際に思った。どうも僕はゆるい開発スタイルの方が好きらしい。

Shiroさんのコメントで何故R6RSが再定義を許さないかというのが非常に面白かった。既存の名前空間(モジュールシステム?)を実装していない処理系でもライブラリが持てるような考慮なんだろうか?psyntaxとか他の展開器(Andre van Tonderのしか知らないけど)ではlibraryも展開するようになってるし。

2012-09-01

exportされた変数

一つ前の記事に言及していた記事の著者さんからコメントが付いてた。っで、自分の書いたコメントに疑問が(ぉぃ
set!で変更可能となると、「取り扱い注意」のラベルが必要かもしれませんが。
よく考えてみると、Sagittariusでは以下のようなことができる。
(library (test)
    (export variable)
    (import (rnrs))
  (define variable 1))

(import (test))
(set! variable 2)
(print variable)
#|
;; Output
2
|#
これはR6RS的にはエラーにならないとまずい。記憶が正しかったら、R7RS的にもエラーだったはず。
Sagittariusではデフォルト(というか、現状だと必ず)「取り扱い注意」のラベルが要ることになる。直すかなぁ。変更できた方が便利だろうかと思ったんだけど、変更されない方が便利だよなぁ。

でも、Ypsilonでも#!r6rsをつけないとエラーにならないなぁ。 どうしよう?

2012-08-30

パラメタ

Schemeのparameterはわざわざ評価してやらないと値が取れないから使うのが面倒だ、と常々思っていたのだが、
識別子マクロとパラメタによる大域変数エミュレート
にそれを解消するマクロが紹介されていた。確かに、ぱっと見よさげだなぁと思ったのだが、これってSRFI-39が提供するparameterizeマクロと相性最悪じゃね?と思ってちょっと実験してみた。
(import (rnrs) (srfi :39))
(define-syntax define-identifier-parameter
  (syntax-rules ()
    ((_ var val)
     (begin
       (define t (make-parameter val))
       (define-syntax var
         (make-variable-transformer
          (lambda(x)
            (syntax-case x (set!)
              ((set! _ a) #'(t a))
              (_ #'(t))))))))))
(define-identifier-parameter *variable* 1)
(display *variable*) (newline)
(parameterize ((*variable* 2)) (display *variable*) (newline))
(display *variable*) (newline)
検証はいつもどおり、Sagittarius、YpsilonにMosh。
っで結果:
Sagittarius
Ypsilon
1を3回出力。(parameterizeされてない)
Mosh
&assertion: (1)は関数じゃないと怒られた
ふむ、パラメタはparameterizeと一緒に使われること(というか、僕は常にそれを想定)が多いと思うので、これだと、値が変更できるライブラリ変数という位置づけでしか使えないということだろうか?
面白いけど、使いどころが限定されそうだ。