Syntax highlighter

2015-12-14

Or, and-let* and tail position

It's about I was stupid enough not to think where actually tail position is.

Let's see the following expression:
(or (returns-false)
    (returns-true))
The first returns-false wouldn't be tail position unless implementation does some magic. It's easy to explain why not only it's explicitly written in R7RS. If you write or with macro, the it'd look like this:
(define-syntax or
  (syntax-rules ()
    ((_ expr) expr)
    ((_ expr expr* ...)
     (let ((t expr)) ;; this is why it's not tail position
       (if t t (or expr* ...))))))
I'm not that stupid just in case you'd think like that.

Now, there's a SRFI which defines and-let*. Using this, you can write nested and and let very simply like this:
(and-let* ((a (returns-something))
           ( (symbol? a) )
           (b (returns-other-thing))
           ( (string? b) ))
  (do-something a b))
#|
would be expanded like this:
(let ((a (returns-something)))
  (and a
       (symbol? a)
       (let ((b (returns-other-thing)))
         (and b
              (string? b)
              (do-something a b))))) ;; this is tail position
|#
You'd probably know what I want to say. Yes, combination like this made me lost...
(or (and-let* (...) body ...)
    (other))
For some reason, I was thinking the last expression in the body would be tail position. Well, doesn't it look like it? And my defence, might make me look more stupid, is that the place where it happened was rather deeply nested (at least for me) and kinda long process. So I couldn't see or in a glance.

Although, it wouldn't hurt that much if you aren't doing recursion. You know what? Yes, I did... on the compiler. If you make a huge expression with internal define, then stack overflow happened because of this mistake. It can happen when the internal define is more than 100 or so (if not, it just consume large stack). Who would write more than 100 internal define? Me, of course.

Don't get me wrong, I don't write by hand (well, rarely maybe) but with macro. Recently, I'm writing SQL parser with (packrat) library and the packrat-parser macro converts the BNF looks like definition into bunch of internal define expressions. If you have never seen how BNF of SQL looks like, then just look this. Even though, it's not completed yet however the parser definition is already close to 2000 LoC. Haven't counted the number of internal definition but at least more than 100. If there's such numbers of internal definition, then stack overflow would happen.

When I fix this problem on compiler, I would expect that it'd also improve the performance. Because of the occupation of the stack area, it'd have impacted some GC performance. The result was not that much. The simple benchmark (just loading sitelib/text/sql/parser.scm) showed 300ms improvement from 7700ms. Well, it's more like an error range.

Anyway, this improvement, at least, save my sanity a bit.

2015-12-13

S式SQL その3

なんとなく必要そうな部分が動くようになってきた。SQL 2003のBNFをほぼそのままSchemeにした形なので無駄に冗長かつ、こんなのいつ使うんだ?的な構文までサポートされている。ほとんどyak shavingに近いような感じで時間だけ取られ、モチベーションを保つのが大変だった。おかげで役に立たなさそうなSQLの構文的な知識が増えた気もする。まぁ、すぐに忘れるだろうけど。

とりあえず、こんな感じで使える。
(import (rnrs) (text sql))

(define sql "select * from t")

(sql->ssql (open-string-input-port sql))
;; -> (select * (from t))
これくらいだとCLにあるSQL扱うのとそんなに変わらない形式のS式なのだが(あれらは基本マクロなので、こんな風に取り出せないけど)、いくらか直感的ではない感じのものがある。例えば以下:
(import (rnrs) (text sql))

(define sql "select * from t inner join a using (id)")

(sql->ssql (open-string-input-port sql))
;; -> (select * (from (t (inner-join a (using id)))))
SxQLだと上記のは
(select :* (from :t) (inner-join :a :on (:= :t.id a.id))) 
見たいな風に書ける(はず、README.markdownから推測しただけなので自信ない)。これは理由があって、FROM句の中にJOIN句を入れた方がSQLのBNF的には楽にパースできたのと、こんなのも有効なSQLだったから:
select * 
from t inner join a using (id)
   , b /* who the heck would write like this? */
SxQL的な記法だと上記が書けないなぁと思ったので、涙を飲んだ。この辺は用途の違いなんだけど、既存のS式SQLはS式からSQLを出力できればよいというものであるのに対して、僕のは既存のSQLをS式に変換するという用途が必要だったから。理由はS式SQLにあるのでそっち参照。単に全てをS式のみで終わらせられる世界の住人ではないというだけだが。INSERT節のVALUES句もそんな感じで直感的ではないものになってる。

パーサがSELECT、INSERT、UPDATEとDELETEをサポートした段階でS式SQLからSQL文字列を取り出すようなのも作った。こっちはかなり簡単で、パターンマッチとマクロを駆使してひたすらゴリゴリ書くだけ。大変なのはSQLに定義されてるほぼ全ての演算子を書かないといけない点。まだ全部は終わってないけど、必要な分からやれるのでそんなに大変でもない。(逆に漏れが出る可能性がパーサより高い・・・)


いくつか宣伝できそうなところ

これが宣伝になるとも思えないけど、パースしたS式SQLはかなり冗長になっているので多少の簡素化を行うようにしている。
  • 識別子の連結
  • Unicode文字列のデコード
  • likesimilar toESCAPE演算子
最初のはパースしただけの状態だとa.b.c(~ a b c)となるので、これをa.b.cというシンボルにする。これはUnicodeやdelimited識別子もいい感じに扱ってくれる。ただ、書き出す際に大文字小文字の情報を失うので、delimitedな識別子はちょっと考える必要があるかもしれない。
二つ目のはU&で始まる識別子もしくは文字列に含まれるUnicodeエスケープをいい感じに文字にするもの。現状surrogate pairとかは全く考慮しない(integer->charするだけな)ので際どい系の文字は危ないかもしれないが。
三つ目のはあんまり使われることがなさそうなESCAPE演算子の除去。

もう少し何かできそうな気がするけど、思いつかなかったのでこれだけ。

ここまでできたので後は使いながら調整していく感じになりそう。0.7.0辺りでドキュメント化できたら嬉しいが、もう少し後になる気がしないでもない。

2015-12-02

syntax-rulesで中級以上のマクロを書く手引き

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

R7RS-smallでは低レベル健全マクロが定義されなかったため SchemerはR5RSから続くsyntax-rulesを使ってマクロを書くことを強いられることになった。syntax-rulesはよくできた健全マクロシステムではあるが、書き方を知らなければ複雑なマクロを書くことができない。ここでは中級程度のマクロを書くために必要な手法を紹介することとする。特に要求するレベルというものを設けることはしないが、想定する読者はここ(秘伝のタレマクロができるまで)に書かれているレベルのマクロは書けるがそれ以上のことがしたい方としている。

紹介する手法

どの程度を中級とするかというのは個人個人で違うだろうが、ここでは以下の手法を用いたマクロを中級とすることとする。
  • 識別子比較
  • CPSマクロ
上記二つを解説した後、この二つを組み合わせたマクロでできることを紹介する。

識別子比較

syntax-rulesを用いたマクロに於ける識別子の比較とは、その識別子に束縛されているものの比較と言い換えることができる。これはR7RSの4.3.2 パターン言語にあるマッチングルール第3項に定義されている。
P is a literal identifier and E is an identifier with the same binding;
(訳)Pがリテラル識別子かつEが同一束縛を持つ識別子である
R7RS 4.3.2 Pattern Language
ここでいうリテラル識別子とはsyntax-rulesに渡す第一引数(ユーザーellipsisを使用する場合は第二引数)のことである。これらの識別子はマクロ展開時に同一の束縛を指す識別子と比較した際にマッチしなければならない。ここで注意したいのは、未束縛の識別子同士の比較は単なる名前の比較になるが、束縛が同一である場合は別名でもマッチするという点である。例えばcondにおける補助構文elseを考えてみる。R7RSでは以下のように書いても正しく動くことが要求されている。
(import (rename (scheme base) (else scheme:else)))

(define else #f)

(cond (else 'ng)
      (scheme:else 'ok))
;; -> ok

(cond (scheme:else 'ng)
      (else 'ng))
;; syntax error
R6RSにはfree-identifier=?と呼ばれる識別子同士が同一の束縛を指すかどうかを調べる手続きがあるが、この性質を使うとR7RS-smallでも同様の機能を持つマクロを書くことができる。例えば以下のように:
(import (scheme base))

(define-syntax free-identifier=??
  (syntax-rules ()
    ((_ a b)
     (let-syntax ((foo (syntax-rules (a)
                         ((_ a) #t)
                         ((_ _) #f))))
       (foo b)))))

(free-identifier=?? a a)
;; -> #t

(free-identifier=?? a b)
;; -> #f
R7RS-smallでは識別子を直接扱うこと、ここでは手続き等の引数にするという意味、はできないのでマクロで書いてやる必要がある点に注意されたい。このようにリテラルに比較したい識別子を与え、それにマッチするかどうかをチェックすることで識別子の比較が可能である。ちなみに、fooという名前に特に意味はない。単にこのマクロ内で使われていない識別子を取っているに過ぎない。意味がないことに意味があるともいえるのかも知れないが、哲学的になるので深くは掘り下げないことにする。

ここで識別子の比較は束縛の比較と書いたがそれが端的に現れている例を提示しよう。
(import (scheme base) (rename (only (scheme base) car) (car scheme:car)))

;; definition of free-identifier=??

(free-identifier=?? car scheme:car)
;; -> #t
上記のスクリプトに於いてcarscheme:carも同一の手続きを指すのでfree-identifier=??#tを返す。

注意:このケースではライブラリのインポートがたかだか一回であることが保障されているはずだが、この解釈は多少自信がない部分がある。解釈が揺れていることに関してはこちらの記事を参照されたい:
Defined or undefined?(英語)
R7RSのライブラリに関する疑問


識別子の比較で注意したいのは一時変数として生成された同名のテンプレート変数の比較は常に真になるということだろう。
(import (scheme base))

(define-syntax foo
  (syntax-rules ()
    ((_ a b)
     (let-syntax ((bar (syntax-rules (a)
                         ((_ a) #t)
                         ((_ _) #f))))
       (bar b)))
    ((_ t* ...)
     (foo t t* ...))))
(foo)
;; -> #t
一時識別子を、マクロ展開器がテンプレート変数をリネームするという性質を用いて、生成するというのはしばしば用いられるテクニックなのだが、これで生成された識別子は同一ではないが同一の束縛を持つ(ここでは未束縛)同名の識別子になるため、syntax-rulesのリテラルと必ずマッチする。こういったケースの識別子を比較した場合はR6RSで定義されているbound-identifier=?を使用する以外にはなく、R7RS-smallの範囲では行えないはずである。(少なくとも筆者が知る限りでは。)

CPSマクロ

CPSマクロとはCPS(Continuation Passing Style)で書かれたマクロのことである。この名称が一般的かどうかというのはここでは議論しないこととする。

Schemeに於いてマクロは必ず式の先頭から評価される。手続きでは引数が評価された後に手続き自体が評価されるが、マクロにおいてはこれが逆になる。これは、あるマクロの展開結果を別のマクロで使いたい場合に手続きのように書くことができない、ということを意味する。例えば以下:
(define-syntax foo
  (syntax-rules ()
    ((_ (a b)) 'ok)))

(define-syntax bar
  (syntax-rules ()
    ((_) (a b))))

(foo (bar))
;; -> syntax error
これは多少例が極端すぎるかもしれないが、いくつかのマクロを組み合わせたい場合というのは少なからずある。その際にあるマクロを展開結果を意図して別のマクロの引数に渡すというミスはままある(体験談)。これを解決する唯一の方法がCPSマクロである。

CPSという名が示すとおり、CPSマクロは次に展開されるマクロをマクロの引数として渡してやる。上記の例であれば、foobarが先に展開されることを期待しているので、以下のようにbarfooを渡すように書き換える。
(define-syntax foo
  (syntax-rules ()
    ((_ (a b)) 'ok)))

(define-syntax bar
  (syntax-rules ()
    ((_ k) (k (a b)))))

(bar foo)
;; -> ok
次に展開するマクロが期待する式をあらかじめ知っておく必要があることと、それに合わせて式を展開する必要がある以外は何も難しいことはない。

組み合わせる

これら二つのテクニック、特に識別子の比較、は単体ではあまり意味を持たせて使うことはないが組み合わせるととても強力なマクロを書くことができる。ここでは極単純だがある程度汎用性のある例を紹介しよう。

マクロは、とりあえずベクタのことは忘れるとして、言ってしまえばリスト操作である。リスト操作といえばassq、ということでassqのマクロ版を作ってみる(強引)。

注意:このネタは既に書いてるので、これを読んだ方には退屈かもしれない。新しいネタを考えてると期日に間に合わなさそうだったので焼き増しである。正直スマン

assocなので、取り出した式を使えるようにしたい。そのためにはCPSマクロを使う必要がある。そうすると一番上の定義は以下のようになるだろう。
(define-syntax massq
  (syntax-rules ()
    ((_ k id alist)
     ...)))
kは次に展開されるマクロの識別子である。後はassqと一緒だ。次にidalistの中にあるかを調べる必要がある。idは識別子であることを期待するので、syntax-rulesのリテラルを使って以下のように書ける。
(letrec-syntax ((foo (syntax-rules (id)
                       ((_ ((id . d) rest ...)) (k (id . d))
                       ((_ ((a . d) rest ...))  (foo (rest ...))))))
  (foo alist))
後はこれを組み合わせてやればよい。
(define-syntax massq
  (syntax-rules ()
    ((_ k id (alist ...))
     (letrec-syntax ((foo (syntax-rules (id)
                            ((_ ((id . d) rest (... ...))) (k (id . d))
                            ((_ ((a . d) rest (... ...)))  (foo (rest (... ...)))))))
       (foo alist)))))
実はこのマクロには少なくとも一つ問題がある。多くの場合では問題にならないことの方が多いのだが、このマクロは入力式をそのまま返さない。具体的にはidがリネームされてしまうのである。これを回避するためには、マッチさせる式と出力する式を分ける必要がある。こんな感じでalistを2回渡してやるだけなので難しい話ではない。
(define-syntax massq
  (syntax-rules ()
    ((_ k id alist)
     (letrec-syntax ((foo (syntax-rules (id)
                            ((_ ((id . d1) rest (... ...)) 
                                ((a . d2) rest2 (... ...)))
                             (k (a . d2)))
                            ((_ ((a1 . d1) rest (... ...))
                                ((a2 . d2) rest2 (... ...)))
                             (foo (rest (... ...)) (rest2 (... ...)))))))
       (foo alist alist)))))
kに渡しているのがaというのが肝である。これによって入力式の識別子が展開された式で使用されることを保障している。ここまでやる必要のあるマクロを書く機会は少ないかも知れないが、識別子のリネームによる予期しない動作を回避するための一つの方法として覚えておいても損はないだろう。

まとめ

中級以上のマクロを書くために必要になる手法を紹介した。識別子の比較を用いればsyntax-rulesのリテラルに依存しないマクロキーワードを作ることができ、CPSマクロを用いればマクロの展開結果を受け取るマクロを作ることができる。どちらも複雑なマクロを書く際の強力なツールとなる。

なおこの記事はこれらの手法を使って複雑怪奇なマクロを書くことを推奨するものではないが、言語を拡張するレベルのマクロを書く際には必要になる(かもしれない)ものではある。更なるマクロの深淵を覗きたい方はOleg氏のLow- and high-level macro programming in Schemeがいろいろまとまっているので参照するとよいだろう。

2015-11-30

S式SQL その2

ちょっと書き始めたらいきなり壁にぶち当たったのでSQL恐ろしい子という感じである。

SQLにはqualified identifierというものがある。何かといえば「.」で繋げられたあれである。例えば以下のSQLをS式にするとする:
select f.bar from foo f;
特に何も考えなければ以下のようになるだろう。
(select (f.bar) (from (as foo f)))
asをつけるかどうかは決めてない(SQL的には要らない子でもS式的にはあった方がいいような)。大抵の場合はこれで問題ないんだけど、SQLにはdelimited identifierというものがある。例えばこんなにも合法なSQL:
select f."bar" from foo f;
SchemeにはR7RSから「||」が入ったんだからdelimited identifierもそれでいいじゃん?と思わなくもない。S式からSQL文字列にした際にどうするとか考えなければだけど。

ここまではまだ序の口で、少なくともSQL2003からはユニコードが使えて、以下のようなのも合法:
select f.U&"\0062ar" from foo f;
大分怪しくなってきた。さらにエスケープ文字の変更も可能なので、以下のも合法:
select f.U&"$0062ar" uescape '$' from foo f;
誰が書くんだこんなのというレベルだが、テーブルやカラム名にASCII以外を使っているとありえるのかもしれない。さらに、U&"$0062ar" uescape '$'はunicode delimited identifierというトークンなので、単なる識別子として処理される。つまり、末尾である必要がなく、以下も合法:
select U&"$0066" uescape '$'.U&"$0062ar" uescape '$' from foo f;
涙出そう。ここまで行くと全てを捨ててシンボルでというわけにはいかないので、SQLの読み込みで作られるqualified identifierはリストにすることにした。こんな感じ:
(select ((@ (unicode (! "$0066") uescape "$") (unicode (! "$0062ar") uescape "$"))) 
 (from (as foo f)))
果てしなく冗長な気がする。連結を表すのに「@」を使うか悩み中。「.」が使えるといいんだけど、「|」でエスケープしたくない。ただ、「@」は別のところで使いたい場面が出てきそうな上に、今一連結(もしくは参照)というイメージが湧かない。「->」はSQLのキーワードの一つなのでできれば使いたくない。「=>」だと紛らわしいかなぁ?

パーサー自体はゴリゴリとBNFを書いていくだけなので作業量は多いけどそこまで大変ではない(大変だけど)。必要な部分だけ書いて後は必要に応じてということができそう。やはり問題になるのはこういう細かい表記の部分だろう。一度使い始めると変更できない(したくない)部分になるので可能な限り違和感のないものにしたいところである。

追記:qualified indentifierをスロットアクセスと考えれば「~」を使うのはありかもしれないなぁ。後は連結に何を割り当てるか考えないとなぁ。

2015-11-27

S式SQL

ちょっと本格的に欲しくなってきたのでメモ兼考えをまとめる。

ことの発端は仕事でテーブルの変更を加えた際に200件を超えるINSERT文を修正しなければいけない可能性が出たこと。可能性で終わった(偶然僕は休みだったので)のだが、今後こういったケースが出ないとは限らない。というかDBを弄る必要がある以上起きる。毎回手作業で貴重な人生を浪費するのも馬鹿らしいので、プログラムにやらせてしまいたい。テキスト処理でやるには荷が重過ぎるのでAST(リストだけど)を操作したい。とここまでが動機。

SQLのBNFはここにあるのを使うとして(SQL2003と多少古いが問題ないだろう)、まずはどういう形にするかをまとめておきたい。これがまとまってないから頓挫してるリポジトリもあったりするし・・・

SQLをS式にするというのはいくつか既にあって、たとえばCL-SQLとかSxQLとかS-SQLとか、大体似てるんだけどちょっとずつ違う感じのS式を使用してる。例で挙げたのは全てCLなのでキーワードをSQLのキーワード、select等、に割り当ててるのもあるのだが、Schemeということでそれは避ける方向にする。キーワードでもいいんだけどリーダーのモードで読み込みが変わっちゃうので依存しないようにしたい。

いろいろ悩んだ結果こんな感じで割り付けることにする
  • 予約語:シンボル
  • テーブル名、カラム名(識別子):シンボル
  • 文字列:文字列
  • 数値:数値
  • ステートメント:リスト
  • 式:前置リスト
  • 関数呼び出し:前置リスト(式ではないもの)
いたって普通。単純なのはこんな感じに:
(select ((count *)) (from foo) (where (and (< 1 id) (< id 10)))
;; = select count(*) from foo where (1 < id and id < 10); 
他の文は適宜考えることにする。IS NOT NULLみたいなのはどうしようかなぁと悩み中。多分(not (null? ...))みたいにする。

パーサは軽く書いたけどずっと大変なんだよなぁ。BNFがあるのでpackratを使ってゴリゴリ書いていくつもりではあるが。とりあえず全く必要なさそうなEmbedded SQLとかはばっさり切ってしまって問題ないだろう。後は適当に何とかするしかないかなぁ。

割とすぐ欲しいけど時間がかかりそうだ。頑張ろう・・・

2015-11-19

R7RSのライブラリに関する疑問

R7RSを実装する際に、ライブラリ周りはR6RSを使いまわしにできたのであまりその仕様について深く考察したことがなかったのだが、最近ちょっと考えることがあり疑問というか不明瞭な点がいくつかあることに気付いた。具体的にはライブラリは複数回読み込まれる可能性があるというこの仕様が不明瞭な点を作っている。仕様から用意に読み取れる点から、ちょっと突っ込んだ(ら直ぐに不明瞭になる)点をだらだらと書いてみようと思う。

明示的に書いてある点

ライブラリAは複数のプログラム、ライブラリから読み込まれた際には読み込みが複数回に渡ることがある。
これは非常に簡単で、以下のようなものになる。
(define-library (A)
  (export inc!)
  (import (scheme base) (scheme write))
  (begin 
    (define inc! 
      (let ((count 0)) 
        (lambda () 
          (set! count (+ count 1))
          count)))
   )
)

(define-library (B)
  (export count-B)
  (import (scheme base) (A))
  (begin (define count-B (inc!)))
)

(define-library (C)
  (export count-C)
  (import (scheme base) (A))
  (begin (define count-C (inc!)))
)

(import (B) (C))

count-B
;; -> 1

count-C
;; -> 1 or 2
ライブラリBがインポートされるのが先と仮定すると、count-Cの値は未定義である。これはライブラリAが複数回評価される可能性があるからであり、これは明示的に書いてある。

書いてない点

いっぱいあるんだけど、とりあえず以下。
(import (scheme eval))

;; library (A) is the same as above
(eval '(inc!) (environment '(A)))
;; -> 1

(eval '(inc!) (environment '(A)))
;; -> ???
これ微妙に書いてない気がする。これは多分、2を返すのが正しい(はず)。根拠としては§5.6.1の最後にあるこれ:
Regardless of the number of times that a library is loaded, each program or library that imports bindings from a library must do so from a single loading of that library, regardless of the number of import declarations in which it appears. That is, (import (only (foo) a)) followed by (import (only (foo) b)) has the same effect as (import (only (foo) a b)).
environmentの引数はimport specである必要があるので、無理やり読めば上記に該当するような気がする。ついでに、プログラムの定義が一つ以上のimport句と式と定義されてる、かつライブラリが複数回読まれる可能性は、読み込みが複数のプログラムもしくはライブラリからなので。

気にしてるのはこれ
(import (scheme base) (prefix (scheme base) scheme:))
一つのプログラム内だから一回のみかなぁとは思うんだけど、微妙に読み取り辛い気がする。

これはどうなるんだろう?
;; a.scm
(import (A))
(inc!)

;; other file
(import (scheme load))
(load "a.scm")
(load "a.scm")
loadは同一の環境で評価するけど、二つのプログラムになるから、両方とも1を返してもいいのかな?それとも、loadで読み込まれたファイルは呼び出し元と同じプログラムということになるのだろうか?

まぁ、こんなことを考えているんだけど、実際の処理系で複数回ライブラリを評価するのは見たことがないので「完全処理系依存フリー」とかいうことをしなければ気にすることはないのではあるが。

2015-11-15

Defined or undefined?

R7RS doesn't mandate implementations to load a library only once, unlike R6RS. I believe, the reason why is that letting implementators to have variety of options such as without creating/storing library definition anywhere but each time it'd be evaluated. Understandable, just rather inefficient to me. Also it defines the behaviour of multiple import clauses of the same library.

Now, I've got a question. What should happen if there are 2 the same libraries import in the same import clause and one (or more) of the identifier(s) is(are) renamed like this?
(import (scheme base) (rename (only (scheme base) car) (car kar)))

;; are car and kar required to be the same binding?
Honestly, I couldn't read if it's required to be the same in such case from R7RS. Though my guess is the followings:
  • The last paragraph of section 5.6.1 only specifies the case of 2 import clauses importing the same libraries
  • This type of import can't be merged into one import in sense of R7RS import definition (or can it be?)
  • Thus this can be multiple import of the same library.
  • The third last paragraph of section 5.6.1 suggesting the possibility of multiple load when there's multiple import of the same library (can be interpreted as multiple evaluation of library).
The point that I'm not totally sure is that the paragraph which suggest the possibility of multiple load says that this would happen when the library is imported more than one program or library. This would also be interpreted if a library imported twice in the same script or library, then it should only be loaded once. If this interpretation is correct, then above car and kar must be the same bindings. Otherwise, can be different.

Why this matters? Generally, it doesn't. Just wondering if the last case of this Gist is required to print #t by R7RS.

I've also posted this question to comp.lang.scheme: this

2015-11-10

Explicit Renamingが解るかもしれない解説

R7RS-largeではExplicit Renaming(以下ER)が入ると噂されている。まだSRFIすら出ていないのでいつになるのか全く不明ではあるのだが、それがどのように動くかを理解しておけば近い将来(と信じたい)ERが入った際に慌てふためくこともないだろう。といってもsyntax-caseより遥かに簡単なので身構える必要もないのではあるが。

簡単な使い方

まずは簡単な使い方を見てみよう。例としてletをERで書いてみることにする。名前付letは考えないことにするのでマクロの名前はmy-letとしよう。また、簡便にするため既存のletを使うことにする。
(import (scheme base))
;; import er-macro-transformer
(cond-expand
  (gauche (import (gauche base)))
  (sagittarius (import (sagittarius)))
  (chibi (import (chibi)))
  (else (error "sorry")))

(define-syntax my-let
  (er-macro-transformer
    (lambda (form rename compare)
      ;; form = (let bindings body ...)
      ;; bindings = ((var val) ...)
      (let ((bindings (cadr form))
            (body (cddr form)))
 `((,(rename 'lambda) ,(map car bindings) ,@body)
   ,@(map cadr bindings))))))
ER展開器は3つの引数を取る手続きを受取りマクロ展開器を返す。それぞれ入力式、リネーム手続、比較手続の3つである。ERで最も重要なのは二つめのリネーム手続で、この手続きによってマクロの健全性を保証することができる。上記の例ではマクロ内でlambdaをリネームすることによって、以下のような場合でも正く動作することを保証することができる。
(let ((lambda 'boo))
  (my-let ((a 1) (b 2)) (+ a b)))
;; -> 3
ERでは健全性、入力式のチェック等は全てユーザに委ねられる。syntax-caseと異りデフォルト(リネーム手続きを呼ばない単なる式変形)では非健全である。

どうやって動いてるの?

ERの動作原理は実に単純である。リネーム手続きはシンボルをマクロ定義時の環境から見える識別子にして返す。例えば上記の例ではmy-letが定義された際に見える識別子というのは(scheme base)からエクスポートされているものになる。これはlambdaを含むのでリネーム手続きにシンボルlambdaを渡すと(scheme base)からエクスポートされているlambdaを指す識別子を返してくる。
;; very naive/simple image

;; environment when my-let is bound
;; ((exporting-name . actual-binding-name) ...)
'((lambda . |lambda@(scheme base)|)
  ... ;; so on
  )

;; very naive implementation of rename procedure
(define (rename s)
  ;; (macro-environment) returns the above environment
  (cond ((assq s (macro-environment)) => cdr)
        (else
   ;; convert to identifier which is bound in macro-environment
   #;(implementation-dependent-procedure s)
   )))
ここではリネーム手続きはシンボルのみを受け取ると仮定しているが、処理系によってはフォームを受け取ることも可能である。特に仕様が決っていないので処理系独自に拡張されているが、ERをサポートしている多くの処理系ではフォームを受け取ることが可能である。

追記:
リネーム手続きに同名のシンボル又は識別子を渡すと常に同一の識別子が返って来る。同一のオブジェクト(eq?で比較した際に#t)ではない可能性に注意してほしい。R6RSの語彙を借ればbound-identifier=?#tを返す識別子である。
(define-syntax foo
  (er-macro-transformer
    (lambda (form rename compare)
      (list (rename 'a) (rename 'a)))))
(foo)
;; -> list of the same identifiers in sense of bound-identifier=?

(let () (foo))
;; -> list of the same identifiers as above macro expansion
;;    because input of rename is always 'a
「Hygienic Macros Through Explicit Renaming」によればリネーム手続きの呼出毎にeqv?#tを返す識別子が新に作られるが、多くのR7RS処理系(Gauche、Chibi、Sagittarius)では同一のオブジェクトを返すようになっている。もちろんそれに依存したコードを書くと後で痛い目にあうかもしれない。

比較手続き

ERが受け取る3つ目の手続きは比較用手続きは渡された2つの入力式が同一であるかを比較する。ここでいう同一とは、同一の束縛を指す。言葉で説明するよりも例を見た方が早いので先ずは例を見てみよう。
(define-syntax bar (syntax-rules ()))
(define-syntax foo
  (er-macro-transformer
    (lambda (form rename compare)
      (define (print . args) (for-each display args) (newline))
      (print (compare (cadr form) (rename 'bar))))))

(foo bar)
;; -> #t

(foo foo)
;; -> #f

(let ((bar 1))
  (foo bar))
;; -> #f
barは束縛されている必要はないのだが(なければ未束縛として比較される)、ここでは話を簡単にするために敢えて束縛を作っている。fooは一つ目のフォームとリネームされたbarが同一の束縛を指すかをチェックするだけのマクロである。 
一つ目の(foo bar)では与えられたbarは大域に束縛されたbarと同一の束縛を指すので#tが返る。これは以下のようにした際に参照される束縛と同一のものと考えれば自明である。
bar
;; -> syntax error
二つ目の(foo foo)barではないので#fが返る。
三つ目の(foo bar)は引数barがマクロ展開時に見える束縛と異る為に、この場合は局所変数barが見える、#fを返す。
R6RSの語彙を借て説明すれば、比較手続きはfree-identifier=?とほぼ同義である。(処理系の拡張によってフォームを受け取れる可能性があるため「ほぼ」としている。)
比較手続きを用いることでcondelseなどの補助構文の導入が可能になる。

まとめ

非常に簡潔にだがERの使い方及び動作モデルの説明をした。syntax-caseでもそうだが、ERも付き詰めればマクロ定義時と展開時の識別子が何を指すのかというところに落ち着き、ERではこれを非常に明示的に記述することができる。

参照

William D Clinger - Hygienic Macros Through Explicit Renaming
https://groups.csail.mit.edu/mac/ftpdir/users/cph/macros/exrename.ps.gz

2015-10-24

er-macro-transformer on top of syntax-case

There are numbers of low level hygienic macros in Scheme world. The most famous ones are probably the followings:
  • explicit renaming
  • syntax-case
  • syntactic closure
Of course there are more (e.g. ir, reverse syntactic) but if you discuss low level hygienic macros, then above would usual be the ones.

R6RS has syntax-case and rumour says R7RS would have explicit renaming. According to this article, if implementations have one of them, then the rest can be implemented atop it. I'm wondering is it really true? Very lame conclusion is true. Because Sagittarius uses kind of syntactic closure and implements both explicit renaming and syntax-case. Now, can it be done in a portable way?

So I've wrote this. It seems this can work most of R6RS implementations except Racket. Though I haven't tested on Larceny, Guile and Vicare yet, they are using either Psyntax or van Tonder expander such as Mosh and IronScheme (Psyntax) or NMosh (van Tonder). So should work.

The basic idea of the implementation is very simple. rename procedure is a simple wrapper of datum->syntax. compare is free-identifier=?. Then wrap the returning form with datum->syntax*.

The initial revision of the Gist used mere datum->syntax. This wasn't good enough because the procedure should only accept datum not syntax object. The error was raised by Psyntax implementations and Racket. Then I've been suggested to walk thought the returning form.

I first thought this won't work because traversing and constructing a new form would return a list not a syntax object. However I was just didn't consider thoroughly. If I use syntax-case and quasisyntax (with-syntax could also be), then I can construct syntax object containing syntax object renamed by er-macro-transformer. So I've rewrite the code. Then most of the R6RS implementation seem working. Even Racket seems working if the macro is very simple like the one on the comment.

Now, my question is 'Is this R6RS portable?'. R6RS standard libraries 12.2 says:
The distinction between the terms “syntax object” and “wrapped syntax object” is important. For example, when invoked by the expander, a transformer (section 12.3) must accept a wrapped syntax object but may return any syntax object, including an unwrapped syntax object.
So transformer *MAY* return unwrapped syntax object. Though what I'm doing is returning wrapped syntax object so should be fine. What I couldn't read is whether or not a syntax object can contain syntax object(s) inserted by other transformer. If this is required feature, then this might be a bug of Racket. Otherwise this is not portable.

I hope it's a bug of Racket, then you (not me) can write an explicit renaming SRFI with sample implementation.

For convenience, embedded source.

2015-10-18

カスタムポートとソケットとバッファポート

「と」で繋げるとなんとなくアニメとかのタイトルっぽい感じがするなぁ。

Sagittariusは0.6.9でポート周りにかなりバグを混入した(弄った)のだが、頭を悩ませるバグが顕在化した。それが表題のポートである。どこで使われているかといえばTLSである。

何が問題か?いくつかの問題が合わさってるのではあるんだが、一つはget-bytevector-nとカスタムポートの相性。カスタムポートは要求されたバイト(文字数)を返す必要はないので、例えば1バイトずつ返して呼び出し元に判断させるということができる。例えば以下のようなの
(import (rnrs))

(let* ([pos 0]
       [p (make-custom-binary-input-port
           "custom in"
           (lambda (bv start count)
             (if (= pos 16)
                 0
                 (begin
                   (set! pos (+ 1 pos))
                   (bytevector-u8-set! bv start pos)
                   1)))
           (lambda () pos)
           (lambda (p) (set! pos p))
           (lambda () 'ok))])
  (get-bytevector-n p 3))
;;-> #vu8(1 2 3)
R6RSテストスイーツからの抜粋なのだが、read!手続きは1バイトずつ処理しget-bytevector-nが最終的に何を返すか決定するという形である。カスタムポートが扱うのが有限のデータなら特に問題ないのだが、ソケットのようにいつEOFがくるか分からないものだと割と困るのである。例えばread!の部分がrecvを使っていたとして、あるソケットは要求の半分のデータを受信したする。そうするとget-bytevector-nは残りの半分を取得するためにもう一回read!を呼び、処理はブロックされる。

不定長のデータを扱うのにget-bytevector-nなんて使うなという話なのだが、本当の問題は別のところにある。0.6.9からバッファポートを導入したのだが、こいつとカスタムポートの相性が悪い。何が悪いかと言えば、バッファを埋めるのにget-bytevector-n相当のことがされているのである。カスタムポートを実装したときに、あまり何も考えずにポート側でバイト数を数えるようにしてしまったので複数回の呼び出しが起きるという話なのではある。

解決方法は多分2つくらいあって、
  1. バッファを埋める処理を別枠にする
  2. 現状ポート側でやってることをget-bytevector-nに移す
1.はそこそこadhocな感じがして嫌だなぁ。2.は(99.99%ないけど)別のところに影響が出る可能性がある(もしくは考慮漏れによるバグの混入)。でも2かなぁ、どう考えても。それでとりあえずはバッファの問題は解決するし。

2015-10-15

CPSマクロ

assocをマクロで書いたらどうなるか、ということを考えた。これくらいならそんなに難しい話ではなく、以下のように書けるだろう。
(import (scheme base) (scheme write))

(define-syntax assocm
  (syntax-rules ()
    ((_ key (alist ...))
     (letrec-syntax ((foo (syntax-rules (key)
                            ((_ (key . e) res (... ...)) (key . e))
                            ((_ (a . d) res (... ...)) (foo res (... ...))))))
       (foo alist ...)))))

;; a bit of trick to avoid unbound variable
(define (c d) (list 'c d))
(define d 1)

(assocm c ((a b) (b d) (c d) (d d)))
;; -> (c 1)
取り出せるのであれば、その中身も欲しい。つまり、carcdrだ。これも同じ要領でやればこんな感じで書けるだろう。
(define-syntax cdrm
  (syntax-rules ()
    ((_ (a . d)) d)))

(cdrm (c . d))
;; -> 1
だが、これら二つのマクロはこんな感じでは組み合わせられない。
(cdrm (assocm c ((a b) (b d) (c d) (d d))))
;; -> error
これはcdrmassocmより先に展開されるからである。あるマクロの展開結果を別のマクロで使いたい状況というのはしばしばある。そういうときにはCPSでマクロを書く。最初のassocmをCPSで書いてみよう。
(define-syntax assocm/cps
  (syntax-rules ()
    ((_ k key (alist ...))
     (letrec-syntax ((foo (syntax-rules (key)
                            ((_ (key . e) res (... ...)) (k (key . e)))
                            ((_ (a . d) res (... ...)) (foo res (... ...))))))
       (foo alist ...)))))

(assocm/cps cdrm c ((a . b) (b . d) (c . d) (d . d)))
;; -> 1
このassocm/cpsは最初の引数に次に展開するマクロを受け取ることで、マクロの展開が終わった際に展開結果(この場合は(key . e))を引数kに渡すことを可能としている。要するに単なるCPSであるがこの状態では割と致命的な欠点がある。それは複数のマクロを組み合わせることができないということである。

例えば上記の例でcadrmはどう書くだろうか?普通に考えれば、carmを定義したのち、cdrmを組み合わせて書きたいところであろう。(もちろんゴリゴリ書いてもいいんだけど。) そう(compose f g)みたいなことがしたわけである。
;; I want to write like this!
(assocm/cps (composem cdrm/cps carm) c ((a . b) (b . d) (c . d) (d . d)))
こうなると、単にマクロを受け取って結果を渡すだけではなく、次のマクロが複合マクロかどうかを判別して上手いことやってくれる何かがほしい。こんな感じだろう。
(define-syntax composem (syntax-rules ()))

;; assume k is CPS macro
(define-syntax extract/cps
  ;; it's a bit awkward to have own name in literals
  ;; but this saves me a lot
  (syntax-rules (composem extract/cps)
    ((_ (composem k) args ...) (k args ...))
    ((_ (composem k ...) args ...)
     (extract/cps "flatten" () (k ...) (args ...)))
    ;; flatten nested composem
    ((_ "flatten" (cps ...) ((composem k ...) k* ...) args)
     (extract/cps "flatten" (cps ... k ...) (k* ...) args))
    ((_ "flatten" (cps ...) (k k* ...) args)
     (extract/cps "flatten" (cps ... k) (k* ...) args))
    ((_ "flatten" (cps ...) () (args ...))
     (extract/cps (extract/cps cps ...) args ...))
    ;; extract/cps keyword
    ((_ (extract/cps (composem k)) args ...) (k args ...))
    ((_ (extract/cps (composem k k* ...)) args ...)
     (k (extract/cps (composem k* ...)) args ...))

    ((_ (extract/cps k) args ...) (k args ...))
    ((_ (extract/cps k k* ...) args ...)
     (k (extract/cps (composem k* ...)) args ...))
    ;; short cut
    ((_ k args ...) (k args ...))))
多少無理やり感があるので(extract/cpsリテラルとか)もう少し綺麗にならないかと思ったりはするのだが、まぁとりあえずこんな感じでいいだろう。これを使って上記のassocm/cpsは以下のように書き換える。
(define-syntax assocm/cps
  (syntax-rules ()
    ((_ k key (alist ...))
     (letrec-syntax ((foo (syntax-rules (key)
                            ((_ (key . e) res (... ...)) 
                             (extract/cps k (key . e)))
                            ((_ (a . d) res (... ...)) (foo res (... ...))))))
       (foo alist ...)))))
さらにcarm/cpscdrm/cpsをこんな感じで定義して、最後のkvaluesmとして定義しよう。CPSマクロの最後に展開されるマクロはCPSではないことに注意しよう。
(define-syntax cdrm/cps
  (syntax-rules ()
    ((_ k (a . d)) (extract/cps k d))))

(define-syntax carm/cps
  (syntax-rules ()
    ((_ k (a . d)) (extract/cps k a))))

(define-syntax valuesm
  (syntax-rules ()
    ((_ args) args)
    ;; this isn't really values...
    ((_ args ...) (args ...))))
こうするとassocmから見つかった値のcadr部分をとるマクロは以下のように書ける。
(assocm/cps (composem cdrm/cps carm/cps valuesm) c ((a b) (b d) (c d) (d d)))
;; -> 1
ちなみに、このコードGaucheでは(まだ)動かないので(すぐ直されると思うけど)、実際に動かしてみたい場合はSagittarius、Chibi、Larcenyのいずれかを使うといいだろう。

ちなみに、この手のコードは3日もすると自分でも理解不能になる危険を孕んでいるので使用する際は十分に留意した方がいいだろう。こういったマクロはだいたOleg氏がまとめているので、メタプログラミングの深淵を覗きたい方はそちらを参照されたい。この辺とか。

2015-10-12

Small Scheme or large Scheme?

2 topics about the size of Scheme were posted on c.l.s. One was rather branch of other topic:How many R6RS users and how much code out there?. And the other is indirectly suggesting it: Question about vote of RnRS (the poster mentioned about the change between R5RS and R6RS as drastic change so seems it's about the size.) Even though all what I wanted to say is already said by Taylan on the first topic I've mentioned, I want to write something about the size so bare with me :)

The point of this topic for me is the definition of small or large. The poster said it is useful enough for educational purpose. I agree with it. If I need to add a bit of my opinion about this, I would say the languages which has proper design for the topic of the class are useful enough for educational purpose as long as students don't use convenient libraries. Java is fine for OOP, C++ is fine for OOP and meta programming, Mathematica is excellent for math, etc. So they can also be programming languages for educational purpose, right? Now are they small?

The answer for me is no. Especially if you see C++'s specification, it's more than gigantic even human beings couldn't understand, IMHO (are there people who understand all the spec?). I wouldn't say it's one of beautifully designed language, but it's powerful enough to cover other purposes including professional use . Then, should Scheme be this much huge to make all programmer happy?

My answer is again no. It's too complicated, it's piling up features on top of other features on top of other, lemme quit. One of the reason why C++ is piling up those features, I believe, is that it doesn't have enough abstraction to make language self growing. Most of programming language don't have this type of feature such as defining new syntax. Or if they have it, it'd be rather complicated to use, either deliberately or accidentally. If it's deliberately, then the designer of the language doesn't want users to use it casually. If it's accidentally, then it's not considered well but made rather adhoc. The first decision is understandable, sometimes those things are not really needed and don't want users to summon daemons from their nose.

Now what's the definition of small in Scheme specification? In my opinion, there is no need to pile up features but it can grow by itself. Let me elaborate what it means.  Currently there're on going discussion about hashtable on SRFI. This might be a good example to do it. Is hashtable required by small language as Scheme? Well, my answer from bottom of my heart is yes but rational answer is no. Why no? It can be implemented by vector and record. Now one of the SRFIs also mentioning weak hashtable. This is rather interesting. Implementing this data structure can not be done neither in range of R6RS nor R7RS. So this seems required, right? Wait a sec, there's a draft SRFI about ephemeron. If you use this, then you can implement weak hashtable using vector, record and ephemeron. So the absolute requirement to have is this one. Hurrah, the language spec is kept small enough!

IMO, this is a bit too extreme. Each time users need to make own utility libraries for those common data structure is ridiculous. Then here comes R7RS-large process. The purpose, in my understanding, of this process is that keeping core language absolutely minimum and put a collection of those commonly used things in its specification. So implementations may or may not support all of them. Oops, again, what's absolutely minimum?

Unfortunately, I don't have generic answer for this and, I believe, neither most of Schemers do. The only thing I do have now is that it's not enought to be perfect language which can solve all problems in this world. Concurrency, networking, weak data, etc. These are not in the specification (maybe yet) but absolutely needed. If there's something lacking, then language specification should grow even if it's got bigger.

The world of computer is growing like speed of light. Problems to be solved are zillion. Too small wouldn't solve. We need small enough.

2015-10-09

bound or free identifier

I've just fixed the bug of incorrect usage of free-identifier=? during macro expansion. As my memo and maybe good to share what I've learnt.

Firstly, have a look at this piece of code:
(import (rnrs))

(define-syntax foo
  (lambda (x)
    (syntax-case x ()
      ((_ (t1 t2))
       ;; what should be print?
       (begin (display (free-identifier=? #'t1 #'t2)) (newline)
              (display (bound-identifier=? #'t1 #'t2)) (newline))
       #''ok)
      ((_ (t* ...) a b ...)
       #'(foo (t* ... t) b ...))
      ((_ a ...)
       #'(foo () a ...)))))
(foo 1 2)
If you can immediately see what's printed, then you can skip the next paragraph :)

The difference between bound-identifier=? and free-identifier=? is that the first one only sees where the given 2 identifiers were  created and the second one sees the actual bindings are the same or not. In the above example, identifier ts are created in different places, more precisely different macro expansion process. If you expand the macro manually, then it would look like this:
(foo 1 2)
;; -> (foo () 1 2))
;; -> (foo (t) 2)) ;; <- where the first t is created 
;; -> (foo (t t))  ;; <- the second one is created here in the different macro expansion
;; 'ok
If 2 identifiers whose names are same are created in different macro expansion, then comparing bound-identifier=? should return #f.free-identifier=?, on the other hand, should return #t because those identifiers are not bound to anything thus they have the same binding (unbound variable) and also have the same name (t). (This is what I understood the behaviour of those 2 procedures. Correct me, if I'm wrong.)

Now the bug was related to this difference. The detail is here. In the description, it says free-identifier=? returns #t against pattern variables t but this is correct behaviour. What I did wrong was using free-identifier=? to compare pattern variables during expanding template variables. Moreover, compiler for syntax-case renamed pattern variables which must be preserved so that expander can use bound-identifier=? to compare pattern variables.

If I know what's wrong, then fixing it is not a big problem. Just adding extra check for pattern variable and use bound-identifier=?. Done! I hope this would be the last article related to macro bug... (feeling won't though)

2015-10-08

マクロバグ

何回目だろうこのネタ。もういい加減尽きたと信じたかったが、そうもいかないらしい。

バグの報告は以下のツイート
突き詰めていくと、テンプレート変数を割り当てていく部分で使用しているfree-identifier=?がこの条件だと全ての一時パターン変数に対して#tを返すということが分かった。adhocに直すならこういう場合の比較に対しては#fを返すようにすればいいのだが、コードを眺めていてふと思った、「こいつらbound-identifier=?で比較しないとまずくね?」と。

単純にこの二つの手続きを置き換えるだけなら何の問題もなく、こんな記事も書いてはいないのだが、そうは問屋が卸してくれなかった。問題になるのは、with-syntax等でラップされた式の中で束縛されたテンプレートを返すようにした場合である。例えばこんなの:
(syntax-case x ()
  ((_ (k ...))
   (with-syntax (((e ...) (gen)))
     #'(lambda (x) (syntax-case x (k...) e ...)))))
具体的にはsyntax-rulesがこんな感じの定義なんだけど、パターン変数がそのままマクロによって生成されるsyntax-caseで使われているのがまずい。現状の実装ではマクロの展開が走ると問答無用で識別子がリネームされてしまうので、パターンのkとテンプレートのkが別の識別子として束縛されてしまう(つまりbound-identifier=?#fを返す)。

あれ、待てよ。パターン変数として束縛された識別子はマクロ環境で束縛されているので、リネームの際にそれを避けるようにすれば無用なリネームが発生しないことになるな。その方向でいくか。やはり問題は一度書き出すとなんとなく解決策がでてくるものだな。まだ解決してないけど。

2015-10-07

Timezone related bugs

Since Sagittarius 0.6.7, it has timezone object. The rationale behind this is pretty simple. Before it used localtime and some other C APIs to get proper local timezone offset. I wasn't unhappy until I needed to handle other timezone offsets. I don't remember exact situation but related to time conversion. Unfortunately, on POSIX there is no way to treat timezone as objects (as far as I could research), so I've decided to implement own timezone handling.

Timezone is related to physical location. Of course, you can change your computer's setting to deceive yourself. I wasn't one of those people and that bit me. I've faced 2 timezone related bugs. Both could only happen in particular places, Japan and country where no summer time. Let me share the bug story. Starting from the first one.

There is IANA TZ database and I'm using it to find proper timezone offset. If you build Sagittarius from repository, then the pre-build process, not cmake but dist.sh, downloads TZ database and compiles it to S-expression. It's not too bad. The only bad thing is that it can't handle any rules not written in the TZ database, such as Japan.

Asia/Tokyo timezone has rather weird rules. According to the TZ database, Japan had summer time between 1948-1951. On the comment, it clearly says this is used only on US military base, for your information, so officially Japan didn't have it, though. Funny thing is that this rule, named Japan, is associated to Asia/Tokyo timezone and it's active now (2015 current). Additionally, the rule doesn't have definition of after 1951. So what should happen? Maybe I didn't read all the comment or how the rules defined properly so I missed something. Anyway, the previous behaviour of handling this situation was signaling an error. Which, of course, caused problem. The biggest one was Sagittarius couldn't be built in Japan.

Thanks to the comment on this blog, I could notice there was such a problem. Other than that, this would stay until I'd decide to go back to Japan. The fix was rather simple, instead of signaling an error, it simply returns default timezone offset without considering old timezone offset. I think that's good enough. (NB: the timezone object would consider the when, means if you ask timezone offset of before 1835 in the Netherlands, then it would return GMT+0:19:32. No need for this? just for fun.)

The second one was rather stupid mistake. Again it was in Japan. I've found a tweet that said time-utc->date didn't consider timezone offset but just return UTC. I saw this when I fixed the first bug so I thought it might be related. Well, kinda but not quite. This bug happened only on Windows (including Cygwin) running on a timezone without summer time (Japan for example).

The reproducing was one easy step. Change system timezone to 'Osaka, Sapporo, Tokyo' then get local timezone. Aha, it returned UTC. But why? Well, very simple. To get local timezone name on Windows (and Cygwin), Sagittarius uses GetTimeZoneInformation and check the return code. If the return code was not TIME_ZONE_ID_UNKNOWN then it returns standard timezone name, otherwise UTC. Hey, MSDN says if the timezone doesn't have summer time then this return code would be returned! That's why if it's in Japan, it returned always UTC. Careless (or stupid) mistake.

Even though I'm using CI services for Linux, Windows and OS X, this type of physical location related bugs are really hard to find. (Not even sure if I can change system timezone per build on the services) I've just seen importance of feedback in a fresh light.

08 Oct 2015
typo fix. the light wasn't from jewel meat...

2015-09-29

暗号ライブラリ (別題:実用Scheme)

Schemeは黒板言語だと言われたりするのだが(概ね認める部分もあるが)、プログラミング言語は実用されないことにはコミュニティも広がらないだろうということで、完全R7RSのみで暗号ライブラリを作っていたりする。ちなみにR6RS処理系用はindustriaがあるので、そっちを使った方がよいと思われる。

ライブラリの名前はAeolus(アイオロス)。まぁ、そういうことです。基本的にはSagittariusで実装されてる(crypto)ライブラリに似せた感じのAPIにしてある。使い方は大体こんな感じ。
(import (scheme base)
        (aeolus cipher)
        (aeolus cipher aes)
        (aeolus modes ecb))

;; 128bit key
(define key (string->utf8 "1234567890123456"))
(define cipher (make-cipher AES key mode-ecb))

;; 16 octet block
(cipher-encrypt cipher (string->utf8 "It's top secret!"))
;; -> #vu8(230 1 210 64 10 131 72 18 222 112 210 129 170 236 243 42)
パディングとかはまだ実装してないので、自前でデータをブロック長にする必要があったりする。

以下はここにあるR7RS準拠の処理系での動作チェック。部分準拠のものは試してない。

完動(全テストパス)
  • Sagittarius 0.6.8
  • Gauche 0.9.5 (HEAD)
  • Larceny 0.98 (ただしパラメタのテストはtest-errorの実装がおかしいので動かない)
  • Chibi Scheme (23ac772e3a)
テスト失敗
  • Chibi Scheme 0.7.3 (AESのテストがこける。SRFI-33っぽい、使わないようにしたらテスト通った)
動かん
  • Foment (複数のバグを踏んだ)
  • Picrin (パスの通し方が分からん)
  • Kawa (同上)
未検証
  • Husk (Haskellいれるのだるい)
PicrinとKawaはなんとか試してみたいのだが、いかんせんライブラリパスの通し方が分からんので手が出せない。誰かテストしてくれないかな(チラ その他リストには載ってないけど動いたとかの報告があると嬉しいなぁ(チラ

とりあえずDES、Triple DESとAESをサポート(というか、当面はこれだけの予定。Blowfishとか欲しい人いる?) 以下は当面のTODO
  • パディング(パラメタにするか明示的にユーザにやらせるか悩み中)
  • ハッシュ(MD5、SHA-1、SHA-256、SHA-512等)
  • MAC(HMAC、CMAC辺り)
  • RSA
  • PKI(X.509証明書とか。ここまでやるとほぼSagittariusの焼き増しに・・・)
 これくらいあるとTLSとかSSHとか実装できそう。

なんでこんなの作ったのか?


上の方に書いたのと被るけど、○○がないからSchemeは使わない(使えない)と言われるのが嫌だったから。仕様内だとソケットやスレッドがないのでいろいろ厳しいんだけど、そこに依存しないピュアSchemeなライブラリを書いていけばそのうち人が増えるのではないかと。黒板言語と呼ばれる理由の一つに実用的なライブラリが圧倒的に足りないというのがあると思うので、そこを何とかしていけばいつかきっととか。以前書いたPostgreSQLバインディングもそんな気持ちからというのはある。(Scheme使ってPostgreSQL使ってるっていう人の方は少ない気がするので、ちとニッチ過ぎたというのはあるが・・・)

まぁ、後は仕事で暗号関係を使わなくなってきたので、忘れないようにというのもある。誰にも聞かれないと思うけど、一応動機。

2015年9月30日追記
Chibiのバグが直されたので完動に追加。仕事が速い。

2015-09-24

process-wait with timeout argument

Recently, I'm writing own CI task on my local machine. (it doesn't mean I quit others when it's completed but just for fun.) Then, I've noticed that it might be convenient to have timeout argument on process-wait instead of using timer to poll every 500 ms (or whatever). So I've implemented it, now you can use like this:
(import (rnrs) (sagittarius process))

(let ((p (call "sh" "sleep_forever.sh")))
  ;; wait for 5 seconds. can also be time object.
  (unless (process-wait p :timeout 5))
    ;; it returns #f if timed out. so kill it
    (process-kill p)))
Now, I don't have to make timer to check. Very convenient :)

TL;DR


From here is the description of underlying implementation. This is not something you may be interested in but simply for my memo (and hope that somebody would indicate better solusion).

Sagittarius supports both Windows and POSIX environment. On Windows, the story was very simple, I just needed to call WaitForSingleObject with process handle and timeout millisecond. Hurray done!. I like this abstraction that API can handle almost any kind of handle. (Most of the time it's a headache to support Windows but sometimes it's easier than POSIX.)

On POSIX, on the other hand, it doesn't have timedwaitpid or something like that. I've asked the teacher, Google, what would be the solution. The first hit was this: Waitpid equivalent with timeout?. Its best answer doesn't seem the best answer since entire process would be affected. Plus, it would always wait for specified timeout amount of time which is not something I want. The most useful pointed one looks nice if POSIX has a portable way to get standard output file descriptor from pid. Though, there seems a way to do it using ptrace(2). (See reptyr(1) and  its source). I haven't looked into its detail but, in my understanding, it opens given pid process with ptrace(2) and calls dup(2) on that process (ptrace_remote_syscall does this black magic I think). It'd be nice to have it if I can do this all platforms Sagittarius supports. However not an easy task to do it without having real environments (e.g. OS X is only on Travis CI).

Go easy


What I wanted to do is waitpid with timeout. So I just need to have a watch dog which alerts either timeout is happened or the target process is finished. Well, the easiest one I could think of was thread with pthread_cond_timedwait(2).

The idea is pretty much simple. It goes the following steps:
  1. Create a thread with the thread entry which calls waitpid
  2. Call pthread_cond_timedwait.
    1. If this return ETIMEDOUT, then send signal to the thread and return #f
    2. Otherwise return the return code.
Done! What an easy solution! (There was a stupid mistake. I didn't know pthread_join can't be called with detached thread. Though, interestingly, it worked on FreeBSD, why?)


Issue


Well, if I can say this is a perfect solution, I'd be super happy but of cource this has an issue (for now only one I'm facing!). Because of the limitation of waitpid (2), the pid can be waited must be created by the parent process means Sagittarius script. Thus processes created by pid->process can't be passed (well this is not only for timeout argument but entire procedure issue, though). If this happens, then ECHILD is raised (see waitpid(2)).

I haven't got any problem with it but if would, then I need a better solution (maybe set PPID to running process? but how?). But for now, I'm happy enough and I believe there's very few situation which users want to wait non child processes.

Again, this isn't an issue on Windows. I don't care good or not but I like it.

2015-09-22

SMTPクライアント

何かが失敗したときにメールを飛ばせると便利かなぁと思い書いた。こんな感じでメールが飛ばせる(サンプルはドキュメントから)。

(import (rnrs) (rfc client))

;; creates SMTP mail object
(define mail 
  (smtp:mail
   (smtp:from "Your name" "your-address@example.com")
   (smtp:subject "Subject")
   "Message"
   (smtp:to "recipient@example.com")))

;; creates an SMTP connection
(define smtp-conn (make-smtp-connection "your.smtp.server.com" "587"))

;; connect to the server
(smtp-connect! smtp-conn) ;; returns SMTP connection

;; Authenticate if required.
(when (smtp-authentication-required? smtp-conn)
  ;; NOTE: only AUTH PLAIN is supported for now
  (cond ((memq 'PLAIN (smtp-connection-authentication-methods smtp-conn))
         (smtp-authenticate! smtp-conn (smtp-plain-authentication
                                        "username"
                                        "password")))
        (else (smtp-disconnect! smtp-conn)
              (error #f "authentication method not supported" 
                     (smtp-connection-authentication-methods smtp-conn)))))

;; Send it
(smtp-send! smtp-conn mail) ;; returns SMTP connection

;; Clean up
(smtp-disconnect! smtp-conn)
メールを作る部分は利便性を高めるためにマクロを用意してて、これの嬉しい点としては、記述力が高いこともあるけど、以下のようにメールをテンプレートとして外部ファイルに書き出しておいて、readevalで手軽に作成することができることもある。
(define mail
  (eval (call-with-input-file "mail.scm" read)
        (environment '(rnrs) '(rfc smtp))))
今のところは考えてないけど、メールのソース(MIMEテキスト)からメールをパース・生成するというのがあってもいいかもしれない。(その前に認証をもう少しなんとかしないとという感じではあるのだが。PLAINだけとかいくらなんでもねぇ・・・)

 一応RFC5321に書いてあるコマンドは全部実装してあるが、拡張とかは全然だし、エラー処理とかもまだ大分甘いので使って直していくという感じ。

2015-09-11

call/ccで嵌った話

call/ccというよりはguardなんだけど。

エラー処理をしたいとか、エラーが起きても処理を継続したいという場合はままある。そういったときに使えるのはguardであることもまぁ周知の事実だと思う。これから提示する例も常識的に理解されているものかもしれない。

まずは以下の例を見てもらいたい。
(import (rnrs))
;; (import (scheme base) (scheme write))
;; (define mod modulo)

(define count 100000)

(define (run)
  (let loop ((i 0))
    (if (= i count)
        i
        (guard (e (else (loop (+ i 1))))
          (when (zero? (mod i 5))
            (error 'who "dummy"))
          (loop (+ i 1))))))

(display (run)) (newline)
(flush-output-port (current-output-port))
これをみて、「あぁ、これはまずいわ」と一目で分かったら以下を読む必要はないです。

これがまずいプログラムだということは既に書いているのでいいとして、何がまずいか。問題になるのはguard内で外側のloopを呼んでいること。一見すると問題ないように見えるのだが、多くの処理系でguardの実装にcall/ccを使用しているのが問題になる。実装例:SRFI-34
参照実装を展開して簡潔に書くと以下のようになる。
(define (run)
  (let loop ((i 0))
    (if (= i count)
        i
        ((call/cc (lambda (k)
                    (let-values ((args (loop (+ i 1))))
                      (k (lambda () (apply values args))))))))))
はい、末尾再帰じゃないですね。なのでスタックがあふれます・・・orz

実際のところとして、R6RS的には末尾再帰になることを要求しているので上記はスタックがあふれるとまずいのだが、(嘘ついた。<cond>を<body>と空目した。)これが問題なく動いたのは確認した中ではChezとRacketだけ。(GuileとVicareは試してない。) もちろん、この2つはスタックを拡張して動かしてるだけかもしれないけど・・・ちなみにR7RSは末尾再帰であることを要求していないので、上記は動かなくても問題ない。

この挙動で嵌ったの実は2回目で、3度目があると嫌だなぁと思ったので適当に書き記しておく。 しかし、どうやったら末尾再帰なguardが実装できるんだろう?参照実装では無理だよなぁ?

追記:
直した。https://bitbucket.org/ktakashi/sagittarius-scheme/commits/7bab13c1e83820eda28fc7878b14209fe1b87df3?at=default

追記の追記:
Shiroさんとのやり取りで上記の修正が正しいのか不安になってきた。っが、問題になるケースが思い浮ばない+スタック消費しないのでこのままで行くことにする。

Problem of hop on hop off projects

Hop on hop off projects is the term I made. This means you join a project in short term, then join other project in short term, like hop on hop off tour buses. (I just don't know any word describes such a style of driving project, drifting?)

I'm currently working with kind of scrum environment. Why kinda? It's because sprint period is rather longer than usual (4-5 weeks) and no standup meeting. The same part is that each sprint I get new task(s). By now, the tasks I've got assigned were not really related so each time I need to look into something I don't know (of course product specific thing). Thus hop on hop off projects.

It might be only me but if I don't have long term commitment of a project, then I lose interest and start writing crappy code. This is because I start thinking that "I would move to next something I don't know anyway why should I write maintanable code?". Probably, I don't feel any responsibility to the code I'll never see in future. (Plus, the current code base is really pile of shit, I don't want to swin into that. Too risky...)

What happen if I'm such a state? For example:
  • Start using copy&paste instead of extracting common use-case somewhere usable place.
  • Using magic number/string as everybody is doing.
  • No tests (well, I don't think there's a culture writing a test in this company...)
These are happening right now. Of cource I know I'm not doing right but risk is too high if I touch/refactor something without tests. I do what I suppose to do but I'm not those highly motivated people so I don't much care as long as I don't see it anymore.

The funny thing about this is that my company is actually developing one product however they don't assign to the same project (so far) or don't have long term assignment. Each task must be done at most a month. I understand that's the basic idea of scrum. But by now, I can only see the greate failure, such as:
  • Wrongly abstracted classes
  • No tests
  • Copy&pasted code
  • Only few people know the structure of code/architecture
  • No refactoring (of cource, there's no efficient tests!)
  • etc.
I'm such a lazy person so I'd write as maintanable as possible if I need to maintain the code. But if I don't have to, this laziness seems to take into horribly.
Or maybe I'm considered as one of useless developers so they don't want me to do anything but piling crap. That's fine by me, as long as they pay my salary.

2015-09-09

ハッシュテーブルSRFIs

ハッシュテーブルに関するSRFIが2つ提出された。一つはJohn Cowanの「SRFI-124: Intermediate hash tables」でこれは既存のSRFI-69の互換性を保ちつつ拡張するというもの。もう一つはTaylan Ulrich Bayırlı/Kammerの「SRFI-126: R6RS-based hashtables」でこれは名前からも分かるようにR6RSで標準化されたハッシュテーブルを拡張するもの。SRFI-126はweakハッシュテーブルを要求しているのでこちらを実装すればもう片方は実装可能という感じである。(bimapをどうするかとかはあるが、Schemeで実装してしまえばいいわけだし、気にしないことにする。所詮別の型だし。)

これだけなら特にネタにもならないのだが、現状SRFI-126はweakハッシュテーブルと通常のハッシュテーブルの操作を同一の手続きで行えることを要求している。インターフェースの統一という感じだし、実用を考えればわざわざ「weak-hashtable-ref」とか書かずに「hashtable-ref」でアクセスできた方が楽というのはあるだろう。問題はどうこれを実現するかということだ。普通に全ての手続きでハッシュテーブルのタイプを場合分けしてもいいんだけど、泥臭い上に拡張性が低い。別のハッシュテーブルが追加されるという可能性は低いといえば低いが、ないわけでもないだろう(concurrentハッシュテーブルとか)。とすると、もう少しマシな方法を考える必要がある。

現状Sagittariusはハッシュテーブルとweakハッシュテーブルは完全に別の型としているのだが、これを以下のようにするとなんとなく拡張性が高くなりそうな雰囲気がある(あくまで雰囲気)。
          +-----------+
          | hashtable |
          +-----+-----+
                |
      +----------+-----------+
      |                      |   
+-----+------------+ +-------+--------+
| normal hashtable | | weak hashtable |
+------------------+ +----------------+
まぁ、普通というか、ひねりも何にもなくインターフェースと実装を分けるだけという。実際にはこれにmutableとimmutableのクラスを追加してやろうかなぁとも考えている。こうしておけば後で意味不明なハッシュテーブルが現れてもそれなりに問題なく動くことが期待できそうだ。

このSRFIは出てきてまだ数日なので上記の変更を入れるかを決めるのは時期尚早な気がする。ただ、この変更自体はやってもいいかなぁとも思えるのでどうしようかなぁというところ。

2015-08-28

OS X support and Travis CI

Travis CI doesn't support Bitbucket so I didn't use it until now. I knew there's a way to use it, more precisely, there's a service which synchronises Bitbucket's repository to Github (BitSyncHub). But I didn't use it since there are couple of CI service which support Bitbucket (e.g. drone.io). Now, I've heard that Travis CI supports OSX so I wanted to use it. Using BitSyncHub wasn't difficult at all (so if you want to use Travis CI, it might be worth to consider). Enabling multiple OS support requires dropping a line to their support. No problem. Then I've got the environment, yahoo!!

OS X is, I believe, considered POSIX OS in most of the case. So I was hoping that Sagittarius would work without any change. Well, it didn't. When I write OS specific code, I refer POSIX spec to make sure I'm writing portable code. Was I doing right? I think so because the code worked on FreeBSD without any change which is also considered POSIX compliant OS. The pitfalls of OSX were the followings:
  • sem_timedwait is not implemented (linker error)
  • sem_init is not supported (can be compiled but an error)
  • Passing O_TRUNC to shm_open is an error.
Well, not that much things but pretty much annoying. Especially the first one. I've created a patch to make 0.6.7 be compiled so that CI server can build it.

Long time ago, Sagittarius got a pull request which made it work on OSX. The PR also contains a fix for libffi search path. It requires to specify the path explicitly. Which I think fine as long as you have control of the environment. However on CI server, we don't know until when the version is there. So I've written kind of solution to fine libffi in build process. So now, you can simply build like the following:
$ cmake .
$ make
It does kinda ugly thing internally but it's working so I'm happy with it.

Then I've experienced build failure number of times (including stupid mistake), finally got the successfull build.

Now, I can say Sagittarius supports OSX again.

2015-08-17

プログラミングにおける公私

駄文

高校で物理の教師が担任だったときに「数学に疲れたら国語を勉強して気分転換して、一日10時間勉強する」とか言われた記憶がある。勉強すること自体に疲れるのにどうやって別科目をやって気分転換するんだ?と疑問に思ったことがある。あれから15年ちょっとなんとなくあの教師の言っていたことが分かった気がする(遅い)。

僕の職業はプログラマで趣味(の一つ)もプログラミングである。職場で書くコードは大なり小なり制約があり思い通りに書くことはできない。言語の制約だったり(Java辛い)、積みあがった糞を崩したくないという精神的枷であったり、あんまり深く追求したくないという己の弱さだったりとまぁいろいろだ。例えば今の職場は、ユニットテストを書く習慣があんまりないかつテスト自体を書くのが驚くほど辛いので既存のコードを弄るのが怖いという個人的には致命的な枷があり、コードを書くのが辛いのである。(そんな環境を変えるという選択肢もあるかもしれないが、そこまで会社に思い入れはない+現状を変えたくないのに権力を持った人がいるので戦ってまで変える気もない。給料分だけ働きます状態。)

そんな状況でコードを書いているといろいろとストレスがたまる。特に現状を変えないように無理やりAPIに切り出す作業とか個人的に大分辛い。そうすると趣味で書いてるプログラムで思いっきり変更加えてストレスを発散しているのである。まさに「プログラミングでプログラミングの疲れを取る」という傍から見たら意味不明なことをしているわけだ。

プログラミングの一つの醍醐味として、自分の思ったとおりのプログラムを作ることができる(可能性がある)というのがあると思っていて、それは例えばパズルのピースがぴったりはまるような感覚で上手く抽象化できたとか、本来なら1000行くらい書く必要があるものを100行まで圧縮できたとか(マクロ中毒)、形は違えど思い通りになる感覚がいいのである。個人的にはこれが得られないとストレスになるらしく、どうしようもなくコピペが要るとか、あまりに酷いコードだけどテストがないから直せないとか、仕事で書くコードはそういったものが趣味で書くものより多いみたいである。

自分が書くコードがきれいとか上手いこといっているとは思わないし思えないが、それでも思い通りに書き換えることができる(もちろん動作は変えないで)というのはやはりストレスを発散することができるようである。特に不要なコードをばっさり削ったときの爽快感は一度味わうと止められない。趣味のプログラミングで気分転換をするときは何かしらがごそっと変わっている可能性がある。いいか悪いかは言及しないことにする。

取り留めなく終わり。

2015-08-14

Renaming identifier (solution of pandoric macro)

I've found a solution for the bug described on the article: pandoricマクロ. It was a rather simple solution.

There were 2 issues and one was a bug.
  • Making a global variable strips syntax information of the given identifier (bug)
  • Explicit renaming doesn't rename when identifiers are bound
The first one was a very simple bug, on the compiler if define has an identifier for its binding's name, then it shouldn't strip. That's it. Though, this isn't a good solution because if the identifier is bound in other library then the binding would be created not the one creating a binding but the one created the identifier. I think it's not a big deal but rather weird.

To resolve the weirdness, the identifier needs to be renamed. On Sagittarius, identifiers internally contain its identity which is a sort of history when the identifier is renamed. If the identity is #f, then it's a global identifier (means almost the same as raw symbol). Now, as far as I remember, each identifier, which reached to define and contains identity, are renamed means created in macros and it should be safe to change its name to unique symbol which is done by compiler via rename-pending-identifier. So I've added extra check to change the identifier name.

The benefit of this change is not only making R7RS syntax-rules work the same as R6RS one but also make R6RS datum->syntax works more R6RS compliant. More precisely, it resolved this issue. So now this won't work:
(import (rnrs))

(define-syntax define/datum->syntax
  (lambda (x)
    (define (concat n1 n2)
      (string->symbol
       (string-append (symbol->string (syntax->datum n1))
              "-"
              (symbol->string (syntax->datum n2)))))
    (syntax-case x ()
      ((_ name1 name2 var) ;; oops
       (with-syntax ((name (datum->syntax #'k (concat #'name1 #'name2))))
     #'(define name var))))))

(define/datum->syntax n1 n2 'bar)

n1-n2
;; -> error
(though, I've also found a piece of code depending on this bug...)

In my understanding, this type of renaming isn't required on R7RS. So this is a valid R7RS script:
(define-syntax defbar
  (syntax-rules ()
    ((_ name)
     (defbar name t1))
    ((_ name t1)
     (begin
       (define t1 'bar)
       (define (name) t1)))))

(defbar foo)

t1
;; may or may not an error
For example, Chicken Scheme returns bar. (For my preferecne, if identifiers are bound in macros, then it should be renamed as R6RS requires, but I can't do much about it.)

2015-08-10

手抜き力

最近日常的に割りと限界まで自分ができることを詰め込んでいるのではないかということに気づいたのと、それだとまずいなぁと思ったので自戒を込めたポエム。

一生懸命という言葉がある。元々は一所懸命という言葉だったのが、どこかで間違って一生懸命となったらしい(要出展)。僕は人生是すちゃらかをモットーにしているのだが、どうも何かを頼まれたりやろうと思ったりすると加減というものが効かない性分でもあるらしい。頼まれたら確実に不可能でない限り引き受けるだろうし、やると決めたら割ととことんやるので大抵どこかで息切れをする。これらのことが期限付きもしくはゴール付きのことであれば終わりがあるのである程度大丈夫なのだが、無期限もしくは終わりがないものだと問題になる。

例えば100m走を思い浮かべればどんなことかイメージしやすいだろう。100m走であれば、100m全力で走った後は失速しようが血を吐いて倒れようが目的は果たしたのでそれ以上に何かを求められることはない。それがマラソンだったらどうだろうか?100m走って止まってもまだ終わっていない。残り42.095km走らなければならないのだ。

話を一生懸命に戻してみよう。一生を懸命に生きる、すばらしい言葉だと思う。でも人生を80年と考えて常に全力疾走できるだろうか?残念ながら僕のような凡人には無理である。30数年生きたが24時間365日の内5割は手抜きして生きてきたと思う。それがここにきて手抜きの割合が多少減ってきたのである。別に大したことではない。例えば掃除を隅々までやるとか、毎日3食作るとか、そういった日常的なことの積み重ねで手を抜かなくなってきているのである。もちろん趣味の範囲とかもそれなりに拡大しているし、最近だと書類を集めるのに奔走したりとかいろいろある。

単に年を取って体力が衰えただけともいえるかもしれない。しかし、それであればより現状の自分の限界を確かに見極める必要がある。朝起きて、朝食作って掃除して買出ししてジムに行ったら15時くらいなんだけど、もう体力がないとかになってしまうと、何かあったときに全く動けない(割と切実)。

完全に自業自得なこと書いてるんだけど、ここ数週間ちょっといろいろあって上記の何かあった状態になっているのだが、ジムに行くのをキャンセルしても何かあったの何かが帳消しするぐらいに体力を持っていくので一つ一つのタスクを手抜きしないと倒れる状態になってたりする。しかも、この何かは無期限に続く系のものなのでふとこんなことを書いてたりする。若いのは精神年齢のみであるので肉体年齢相応にしないとという自戒。

2015-08-09

pandoricマクロ

SchemeでCLのpandoricマクロを実装したらSagittariusでは動かないというのを捕捉した。コードをGistに貼り付けてもらった。これ。正直見ただけで、「あ、これ動かないやつだ」分かるのが嫌だったが、一応確認してみた。うん、動かないね・・・

一応言い訳をしておくと、R6RS版のsyntax-rulesなら動く。問題になるのはR7RS版のsyntax-rules。何度もブログに書いてるから知ってる人は知ってると思うけど、SagittariusではR7RSで追加された拡張を実現するために、R7RSのsyntax-rulesはChibi Schemeから移植したものを使っている。これは大抵の場合で上手く動くんだけど、上記のような、テンプレート変数で生成した一時変数を別ライブラリで大域に束縛すると動かなくなる。

もう少し短い例だと以下のようなコード:
;; foo.scm
(define-library (foo)
  (export defbar)
  (import (scheme base))
  (begin
    (define-syntax defbar
      (syntax-rules ()
        ((_ name)
         (defbar name t1))
        ((_ name t1)
         (begin
           (define t1 'bar)
           (define (name) t1)))))))

(import (scheme base) (scheme write) (foo))

(defbar boo)

(display (boo)) (newline)
;; -> error
#|
sash -r7 foo.scm
|#
(scheme base)(rnrs)にすると動く(define-libraryは変更する必要はない)。何が問題かといえば、defbar内で細くされたテンプレート変数は、そのマクロが定義されたライブラリを内部で保持する識別子となるため、展開後に参照しようとするとそんなものないと怒られるのである。これは健全性を保持するためにそうなっているのだが、一時変数を大域で束縛するとそれがあだになるのである。

ではどうするかなのだが、一番確実なのはsyntax-caseで実装するというものなのだが、これも実は内部的な問題がある。コンパイラ内でマクロを使っているのだが、このマクロはerで実装されたsyntax-rulesであるということに大分依存している。単純にerの方が作りが単純なので識別子が保持する環境とかをあまり考えなくて済むというだけなのではあるが。さらに、これをやるとR6RSとR7RSで使用する_...を分けなければならなくなるのであまり美味しくない。(理由はsyntax-caseにある)

次にやれそうなのは、syntax-rulesの実装を変えることなのだが、これやってもerで作ったマクロに問題が残ることになるので、近い(遠いかも)将来、erがR7RS-largeに組み込まれた際にいやな感じになる。(のでやらない)

残るは少しadhocになるが、大域に束縛された識別子の定義位置が別ライブラリだった場合に同一の識別子の位置を無理やり束縛されるライブラリに変更するとかになる。ぱっと思いつくパターンでは動くような気がするんだけど、これだけadhocな変更だと大体どこかでほころびが出ることが過去の経験から分かっているのでやるなら思いつく限りのパターンをテストしないとという感じになる。(まぁ、似たようなことをsyntax-caseでやっているので動くとは思うんだけど、どうだろう?)

ちと考える必要があるなぁ・・・

2015-08-06

Safer thread termination (2)

I think I've found a (imperfect) solution to do it.

Goal


The goal is pretty simple. No crash, that's it. Optionally, releasing resource as much as possible. But the resource in this case is not about Scheme world or Sagittarius created, it's OS resource such as allocated stack or so.

The problem


Yes, it's the problem. The problem was sometimes it crashed with 0xC0000005 (access violation, SEGV in POSIX way). The termination process was described in previous article (Safer thread termination) . The cause, in short, was interrupting Eip or Rip may break call stack frame.

As my conclusion, if the Scheme process went into deep inside of C function call, then the program counter is overwritten, the call stack may get broke. So when the process tries to return from RaiseException however there is no place to return or returning invalid address. (This may not be true but seems like it.)

Comparing stack pointer was not enough


In previous article, I've written to do it. It does prevent the error when the thread has already returned from entry point however it didn't resolve returning from deep stack address. So I need to find one more thing.

The issue is breaking call stack. Means, if I can restore it until the thread entry function is called, then the call stack is not broken and can return properly.

jmp_buf?


If I need to restore the stack frame of certain point, then setjmp and longjmp seem the things I need to use, instead of calling RaiseException. So I've put setjmp before calling Scheme world process. Then the thread-terminate! interrupts the process to the C function which calls longjmp.

Not a perfect solution


Unfortunately, this isn't a perfect solution. It works most of the time and, I think, should be good enough (so far I don't get crash in my test case). However, the following code may not work:
(thread-terminate! (thread-start! (make-thread (lambda () #t))))
The problem of this piece of code is that the thread may not be terminated. If the thread couldn't reach the point where setjmp is called, then thread-terminate! would call longjmp without proper jmp_buf. Or the thread wouldn't be terminated if it didn't reach the internal thread entry point. Who writes this crap? Who knows.

This may not be a perfect solution but at least less possibility to get crashed. Thus it's safer than before. So, for now, I'm happy with it.

2015-08-04

Safer thread termination

Terminating a thread is a dangerous operation (AFAIK). So this shouldn't be done in general. However I've wrote the library (util concurrent) which uses thread-terminate! to finish tasks forcibly. As my understanding, as long as you free all resources held by the thread, terminating thread isn't that badly wrong. Well, if this was the conclusion, then I wouldn't write this. It actually works fine on POSIX environments I usually test, including Cygwin, however not working properly on Windows.

Windows has the API which terminates a thread, called TerminateThread. I, however, don't use this because of the following reasons:
  • It may not release all resources
  • There is no way to handle after termination
If the resource aren't released, then it may leak eventually. I don't use Sagittarius on 24/7 service so this might be a trivial issue but you'll never know. So it's better to have as safe as possible.

If you don't use TerminateThread, then there's, afaik, not many choice to do it. The way I've chosen is using CONTEXT. The basic process is the followings:
  1. Suspend the target thread
  2. Check if it's active
  3. Get thread context
  4. Set program counter to the function calls RaiseException
  5. Resume the thread
The thread caller wraps the thread function with _try and _except, so the thrown exception will be caught.

Until here, there seems nothing wrong and works fine. Well no. This works most of the case however at some point you may get a context which contains no call frame of thread caller function. I think this means either thread is almost terminating or it's finished but still active. Then you'd get access violation error.

Now, what can I do? I think I'll try to compare stack pointer. Luckly, Boehm GC has base stack pointer on each thread. So if I can get this and compare with the thread context stack pointer, I might be able to detect if the thread is already finished (or at least returned from the thread function of Sagittarius) or not.

If you know better way, please let me know.

2015-07-27

語学学習

ふとしたことから新しい言語を学ぶことについて議論をしたのだが、そこからなんとなく自分の中の言語感覚が分かったような気がするのでメモ。単なる駄文。

言語間の距離


日本語は欧州で話される言語から見ると最も遠いところにある言語の一つである。(参照: Language Difficulty Ranking - Effective Language Learning) これはどうしようもない事実なので受け入れるしかない。思えば中学で初めて英語に触れたときに、日本語との類似点を見出せずとにかく意味不明なものであった記憶がある。ELT(今はALTか?)で来てたアメリカ人(だったはず)に「英語好きか?」と
聞かれて「パズルみたいだから、好きだ」と答えたのだが、答えられた方は意味が分からないという顔をしていた気がする。それくらい意思疎通の道具ではなく、何かしらクイズみたいなものだったということである。

オランダではオランダ語が話されているというのはある意味当たり前で、6年も住んでいれば多少は喋れる、理解できるようにはなるのだが(もちろんそれなりには勉強しているが)、僕の中のオランダ語は基本的にオランダ語との距離が近い英語をベースにしている。英語とオランダ語の間は割りと一対一の関係に近い。それとは逆に日本語と英語の間には言語間の意味を言語ではなくイメージで捉えるような抽象的な層があるように思われる。これら3つの言語の関係を図にするとこんな感じになる。
  +-----------------+
  |                 |
  |     Dutch       \
  |                 |\
  +-------++--------+ \
          ||           \
          ||            \                     .........
          ||             \               ...........   ......
          ||              \         .....                 ...
          ||               \    .....                       ...
  +-------++--------+       \ ...                             ..             +-----------------+
  |                 +--------..                                  ..----------+                 |
  |    English      +------..      Abstract language layer        ..---------+    Japanese     |
  |                 +------.                                       ..--------+                 |
  +-----------------+      ..                                      .         +-----------------+
                             ..                                   ..
                               ...                          ......
                                   ..         .. ............
                                     ................
線が多い方が密に繋がっているとする。日本語と英語の繋がりは(例外もあるけど)大体言語ではない何かで繋がっている感じ。なので英語で話してるときは日本語で考えることが辛い。逆もまた叱り。逆にオランダ語は抽象空間を経由しないので割りと簡単に英蘭をスイッチできる。言語間の距離が離れている言語を学習する際はこの違いを吸収する層の構築が重要になるのではないかと思っている。

オランダ語話者から見た英語


そこまで具体的に聞いたわけではないのだが、オランダ語を母語とする人からみた英語というのは母語+α(下手するとマイナスα)くらいの感覚のようである。学校で一応文法や英語の文章がどのように構築されているかとかやるらしいのだが、学校でやったら後は忘れても問題ないくらいで細かいことは気にしなくても喋れるようだ。人の頭の中は覗けないので実際のところはどうかは分からないが、おそらくこれくらいの勢いで繋がっているのであろう。
  +-----------------+
  |                 |
  |     Dutch       |
  |                 |
  +----+++++++++----+
       |||||||||
       |||||||||
       |||||||||
       |||||||||
       |||||||||
  +----+++++++++----+
  |                 +
  |    English      +
  |                 +
  +-----------------+
方言とまでは行かないが、かなり近い言語であることは間違いないのでここまでではないにしろ英語を話せるオランダ人の中ではこれくらい近いものではないだろうか。なんともうらやましい限りである。

オランダでは(多分欧州の多くの国では)高校卒業までに少なくとも2ヶ国語を学ぶのだが(オランダでは英語とフランス語かドイツ語)、どちらの言語も日本語に比べればはるかに近い、それこそ限りなく0に近いレベルなので(言いすぎだが)上記の図の近くにもう一つ言語が追加されるレベルのものだろう。

オランダ語話者から見た日本語


実はこれが本題。当然だがオランダ語と日本語にはほとんど類似点はない。文法、発音、動詞の格変化挙げればキリがないが、本当に何一つない。まぁ、これは英語でもいえることではあるが。これくらい何もないと学習するさいの取っ掛かりがないように思える。平面に点が2つあるだけとかそんなレベル近い気がする。(これは憶測だが)それまで言語学習といえば母語と紐付けて考えることができたものが、いきなり手探りになるので近寄りがたい感じになるのではないだろうか?

個人的には一度抽象化の層を構築してしまうとなんとなく他の言語を学習するコストが下がる気がしないでもない。もちろん発音とか聞き取りとかは物理的な問題があるのでそれなりに時間がかかるが、頭の中の切り替えは大体同じようにできる気がしている。

なんでこんなことを思ったかというと、日本語を話したい言ってはいるがこの取っ掛かりのなさに絶望気味になっているという話しを聞いたのだ。僕はこの絶望も20年前に味わっている+義務教育という性質上克服する以外に逃げ場はなかったのでなんとなくなんとかなってしまったという。ひょっとしたら言語の距離というのは一度克服してしまうと後は楽になるのではないのかなぁ、と思ったのであった。オチなし。

2015-07-16

あとらんだむ

時間があるときにまとめてとも言う。

MSVCとスタック

最近AppveyorというWindows用CIサービスでもCIをし始めたのだが(なぜかx64版が0xc0000005で落ちるのだがなぜだろう、起動すらしてない感じに見えるのだが?)、試用期間が終わって無償版に自動移行した際に起きたスタックオーバーフロー例外が起きるようになった。起きている場所は毎回同じ。移行される前は動いていたテストなので不思議な感じがしていたのだが、原因がCPUが1個にされたためにテストケースがシングルスレッドで走ったため発覚したバグだった。

ちょっと前にCPUが1個のときはテストケースをシングルスレッドで走らせた方が速いということを確認したので、ランタイムでCPUの数を確認して適当にディスパッチさせるようにしたのだが、これが原因(もしくは功を奏したの)だった。問題になったのは10万くらいネストしたリストの書き出し。これくらいネストするとC側のスタックが尽きるのでスタックの深さが既定値(メインスレッドで1MB、子スレッドで64KB)を超えたら&i/o-errorを投げるようにしていたのだが、これが上手いこといっていなかった。MSVCは既定では1MBしかスタックを割り当ててくれないので、リンカオプション(具体的には/STACK)で8MBを指定していたのだが、どうもこのオプションでは上手く行かなかったらしい。とりあえずどれが上手く動くのか分からないのでC_FLAGSとCXX_FLAGSに/Fオプションを渡し、さらにCMakeが持っている2つの内部リンカフラグ両方に/STACKオプションを追加した。これで試すと手元の環境ではスタックオーベーフロー例外は起きなくなったのだが、Appveyor上ではまだ起きる。起動時にスタック領域を制限されるのか、Windowsサーバーの仕様なのかは不明だが起きるものは起きる。

どうしたものかと適当にGoogle先生にお伺いを立てたところ以下の記事を発見。

How to trap stack overflow in a Visual C++ application

_try_exceptを使って例外を捕捉したらVirtualFreeとVirtualProtectでスタック領域を元に戻してやるというもの。これいけるんじゃね?と思い早速追加。

https://bitbucket.org/ktakashi/sagittarius-scheme/src/031c6cbaf9c75df5815b7885a2c9ba5c34bb119f/src/writer.c?at=default#cl-1065

インラインアセンブラの部分は適当に変更(そうしないとx64ではコンパイルできない)。なんとなく動いているようである。

これとStackWalk64を使うとスタックトレースが取れそうな気がしないでもないので、組み込んだら原因不明の0xc0000005の発生場所が特定できるかもしれないなぁ。

タイムゾーン

どうもPOSIXやMSVC付属のCRTにあるタイムゾーン関係のAPIは使いにくい。というか、基本的にはタイムゾーンオブジェクトみたいな風にできないようである。別にシステムの時間とかを変更したいわけではなく、単にある地域のGMTオフセット等が知りたいだけなのだが、そういう使い方がやりづらい。Javaだとjava.util.Timezone(Java8からは非推奨になったけど)等があるのでなんとかできるのだろうとちょっと調べてみた。

結果、やれるけど割りと茨の道。Javaは自前のタイムゾーンDBを持っててそこから情報を取得している。Java8からはtzdb.datというファイルに変更されて、更新があってもとユーザがJREの更新を待つ必要がなくなったというのはあるが、OSから取得していないというところは一緒である。

タイムゾーンの情報は現在はIANAが管理していて、データ及びPOSIXの時間関係のソースはパブリックドメインで公開されている。そこに山があると登りたくなるのが登山家であれば、そこに問題があると何とかしたくなるのがプログラマである。別に面白みがあるものではないが、OSが上手いことAPIを提供してくれないのであれば、自前でなんとかせねばあるまいということである。

とりあえずFTPサーバーからデータファイルを落として、そいつらをS式に落とし込む部分までは書いたので後は落とし込んだ情報を元に時間をなんとかするだけなのだが、そこが面倒ともいう。とりあえずは、GMTオフセットと夏時間が取得できればいいのだが、今週末(というか明日)予定 している0.6.6のリリースには当然間に合わない。ただ、tzdb.dat相当のファイルをリポジトリに入れたくない(自動生成されるファイルを入れたくない)ということから、ここまでは今のうちにやっておかないと(0.6.6が提供するAPIのみで書けるようにしておくという意味)間延びするか、ポリシーに反してリポジトリを汚すかの2択になってしまうので。

IANAのデータ、閏秒のデータも入っているから何とかすれば外だしにできそうなのだが、何を血迷ったのかC側に入れてあるのでちょっと辛い気がしないでもない。まぁ、もう少し機能をScheme側に押し出してやればやれなくもないのだが、どうしようかね。


なんかもう一つ書くことがあった気がしたのだが、完全にわすれたようなのでオチもなくお終い。

2015-07-08

Conditions and stack trace

One of the things I don't want to see is stack traces. Whenever I saw this, I'd always be disappointed. There are basically 2 reasons: the first one is it usually means something went wrong, the second one is sometimes it doesn't show where the condition is actually raised. The first one can be considered a bug so I just need to snatch it. The second one is more for implementations issue.

Currently, Sagittarius shows stack trace whenever default exception handler is invoked, means no guard nor with-exception-handler. The stack trace is collected in the default exception handler. This is fine most of the time since I don't use them that much in my script. (well, I don't argue if it's good or not here.) However, sometimes I want a script fail safe or make sure it releases resources or so. Then I saw the fangs. As a simple example, you have the following script:
(guard (e (else (release-all) (raise e)))
  (open-something-and-fail-it)
  (release-all))
Suppose open-something-and-fail-it may raise an error and you want to release all resources after the process. Now, you saw a stack trace, what would you expect to be shown? I would expect where the root cause is raised. Or at least I can see it. However because the stack trace is collected in the default exception handler, you don't see those information at all.

It was okay until I had written a server program which shows a stack trace whenever unhandled exception is raised. If you write this kind of script, then you want to know which one is the actual culprit, server itself or the application program. As long as I'm writing both, it's just a matter of good old days printf debug but this is pain in the ass. If the stack trace shows where this happened, I don't have to do this type of thing in some cases. So I've changed the timing of collecting stack traces.

The basic idea is whenever raise or raise-continuable is called with compound condition, then it appends stack trace object. Only one stack trace object can be appeared in the compound condition. So if the condition is re-raised, then new stack trace object is created and the old one is set to the new one as its cause. It's pretty much similar with Java's exception. Of course, there are bunch of differences.
  1. Java's exception collects stack trace when it's created
  2. java.lang.Throwable's cause property may have root cause while Sagittarius' only takes stack trace object.
  3. The stack trace object is implicitly added, means given condition is copied entirely while Java's exception can be the same.
The item #1 is the biggest one. On Java, if you throw an exception created before the throw syntax, then the stack trace indicates where it's created. This can be very inconvenient like this type of case:
public class Foo {
  private Exception exn = new Exception();
  public void foo() throws Exception {
    throw exn;
  }
}
Don't ask me who would do this but the stack trace would be shown indicates the second line. (I didn't check the Java's spec, so this might depend on the implementation.)

The item #2 is because of implementation of condition. It flattens the given compound conditions if there are. For example, suppose you catch a condition and re-raise it with adding specific condition. The script would be like this:
;; suppose (fail) raises a compound condition
(guard (e (else (raise (condition (make-some-other-condition) e))))
  (fail))
In this case, the compound condition e will be flattened and merged into the new condition object. R6RS doesn't say how the condition procedure construct compound condition so it can decompose it by need.

The item #3 can be an issue. Suppose you want to re-use a condition and compare it by mean of eq? like this:
(let ((c (condition (make-error) (make-who-condition 'who))))
  (guard (e (else (eq? c e)))
    (raise c)))
;; -> #f
The raise procedure implicitly copy the given condition and adds stack trace object, thus the object wouldn't be the same one. I couldn't find anything mentioning this kind of thing on R6RS. So I think it's still R6RS compliant. However this might cause an issue in the future. (Using exception as a returning value or so?)

The reason why Sagittarius choose to collect stack trace  when condition is raised is because of the requirement of condition procedure. It's not so difficult to make condition procedure collect stack trace however this procedure must be able to take arbitrary number of conditions including compound conditions. So there is no way to specify which one is the actual root cause when multiple compound conditions are given. (Nobody do this? who knows!)

I'm kinda doubting that if I made a better choice. Especially item #3. But seeing irrelevant stack traces is much more painful. So I think I can live with this.

2015-07-03

Webアプリケーションサーバっぽい何か

時間というのは取れるときは取れるものである・・・

今更ながらにWebアプリ的な何かを暇を見つけて書いているのだが(世の中GUIでできるものはクリック一つでできた方が楽ですよ的な軟弱な考えに基づいている)、一ファイルに全部詰め込んで書いてるのが辛くなってきたのでいろいろいい感じに扱ってくれるフレームワーク的なのを書いたのでその紹介(と備忘録)。基本的にはPaellaの上(名前的には下だけど)に乗せてある何か。

極々簡単な何か


Githubから落としてきて以下のコマンドでインストール可能。
$ cmake .
$ make install
インストールしたら適当にアプリを作る。まぁ、こんな感じ。
$ plato-recipe.scm -i -a sample simple-app 
simple-appというディレクトリができているはずなのでそこに移動して、以下のようにサーバ起動。
$ sagittarius run.scm 
これだけやると、http://localhost:8080/sampleにアクセスできるはず。OKと表示されていたら上手いこと動いている。

仕組み


30分足らずで書いた何かなので、仕組みも糞もないくらい簡単ななのだが、端的に言えばディレクトリ決め打ちアプリケーションという感じである。上記の例だと以下のようなディレクトリ構造が作成される。
simple-app/
  + lib/
  + apps/
      + sample/
          + handler.scm
  + run.scm
handler.scmがマウントポイントのエントリーポイントになる。詳しくはソース見た方が早いレベル。

欲しげな機能


  • セッション管理の機能とか。現状クッキーを扱うライブラリとかないのでそこから作らないといけないという。
  • 設定ファイル的な何か。JEEでいうweb.xml的のがあるといいかなぁ。
  • マウントポイント別環境。
  • サブパス。今のところ一番sample/fooみたいなことができない。いるかどうかは別だが・・・

ちょっとCygwin上で動かしたらselect (2)の実装の違いにより動かなかったので、現在のHEADが必要。Linuxなら0.6.5でも問題なく動くと思う。

2015-07-02

プロセス間通信とセマフォ

書こうと決めてから1週間近くたってしまった。時間とは取れないものである。

Sagittariusにプロセス間通信用の共有メモリとその排他制御用のセマフォを入れた話。

プロセス間通信なんてソケットでもファイルでも何でもいいんだけど、もう少し軽量なものがあるといいかと思い共有メモリを入れた。っで、一つの資源に対して二つ以上の場所からアクセスがあると排他制御がいるということで、プロセス間で使えるセマフォを入れた。とりあえずこんな感じで使える。
;; process A
(import (rnrs)
        (sagittarius process)
        (sagittarius threads))

;; create a semaphore with initial counter 0
(define sem (make-semaphore "/waiter" 0))

;; opens shared memory. if this is the first process then it'll be created
;; with the size 256.
(define shm (open-shared-memory "/shared-memory" 256 (file-options no-fail)))

;; wait for the other process
(semaphore-wait! sem)

;; something was delivered
(let ((bv (shared-memory->bytevector shm)))
  (print (utf8->string bv 0 5)))

;; close and release
(close-shared-memory shm)
(semaphore-close! sem)
(semaphore-destroy! sem)

;; process B
(import (rnrs)
        (sagittarius process)
        (sagittarius threads))

;; open the semaphore created by the other process
(define sem (open-semaphore "/waiter"))

;; this must specify no-truncate option otherwise it may fail
(define shm (open-shared-memory "/shared-memory" 256 (file-options no-truncate)))

(let ((bv (shared-memory->bytevector shm)))
  ;; put some value
  (bytevector-copy! (string->utf8 "hello") 0 bv 0 5))

;; notify the other process
(semaphore-post! sem)
プロセスAは入力待ちプロセス。プロセスBは共有メモリ/shared-memoryに何か書き込んでセマフォのカウンタを一つ増やす。

正直共有メモリだとシェルから使いにくいのであんまり嬉しくないのが悲しいところ。本当は名前付きパイプも入れたいのだが、POSIXとWindowsでモデルが大分違うので上手いAPIを思いつかないでいる。(作成を考えなければどちらのモデルでも名前付きパイプは単なるファイルと変わらないので扱えなくはないのだが、せっかくなので何かほしいという話。)

なんでこんなのが入ったかといえば、最近仕事で使うツールを自前サーバに載せているのだが、サーバの再起動をリモートREPLからできると楽かなぁと思ったからというのがある。正直どちらもあまり上手く使われていないので今のところそこまでの恩恵がないという話もある・・・

2015-06-25

Platform specific issues

Recently I've faced to stability issues. The followings are the ones I've met:

Well, the one for Windows is kinda known for a while (except Windows Server one). These issues are categorised more or less platform specific issues.

The reason why I'm writing is because I have no idea why it happens and might be able to get some knowledge from comment (my googling ability is not high enought to find the solution). For example, the first one happens only on Arch Linux. The funny thing is that the reported bug didn't happen on my Arch Linux environment but different one mentioned on the comment. And never happened on other environment (e.g. Ubuntu or FreeBSD).

The second one happens only on my Linux CI environment. So I even can't debug. And, again, never happened on other Linux environment. (why?)

If you have any clue, please let me know.

2015-06-07

パラメータとスレッド(2)

前回の続き。

コードとか実装のアイデアというのは寝かせると浮かんでくるものではあるのだが、割と早めに浮かんできたので早速実装してみたという話。

Gaucheの動作はパラメータの初期値をグローバルに持っているから実現されている(それ以外にも手はあるのだが)という話から、とりあえず同様のことをしてみた。SagittariusではパラメータはSchemeで実装されているので実装ライブラリにWeakハッシュテーブルを持たせパラメータが参照される動的環境内に値がなければグローバルのテーブルから引っ張ってくるという実装。実装が簡単な上に効果は抜群で、前回のスクリプトはGaucheと同様の結果を返すようになった。さらに、Weakハッシュテーブルを使っているのでGCが走った際にどこからも参照されていなければ回収されるのでメモリの爆発もない。

この変更によるものではないと思うけど、プッシュしたらdrone.ioのテストがこけた・・・なんだろう?

2015-06-06

パラメータとスレッド

平行処理ライブラリの書き換えをしていてスレッドと動的環境(今回はパラメータ限定)に関連した挙動の違いが気になったのでメモ。

動作の調査としては、スレッドAで作成されたパラメータが親スレッド、スレッドAが生成される前から存在したスレッドB及びスレッドAの処理が終了後に生成されたスレッドCでどのように見えるかというもの。使用したのは以下のコード:
;; (param) library
(define-library (param)
  (export *param*)
  (import (scheme base))
  (begin
    (define *param* (make-parameter 10))))

;; script
(import (scheme base) (scheme load) (scheme write) (scheme eval) (srfi 18))

(define box (make-vector 1))
(define lock (make-mutex))
(define waiter (make-condition-variable))

(define t 
  (thread-start!
   (make-thread
    (lambda ()
      (mutex-unlock! lock waiter)
      ((vector-ref box 0))))))

(define (do-param v)
  (display (current-thread))
  (display (eval '(*param*) (environment '(param))))
  (eval `(*param* ,v) (environment '(param)))
  (display (eval '(*param*) (environment '(param))))
  (newline))

(thread-join! (thread-start! (make-thread
  (lambda () (do-param ":changed")))))

;; main thread
(do-param ":changed-main")

;; other thread?
(thread-join! (thread-start! (make-thread
  (lambda () (do-param ":changed-other")))))

(vector-set! box 0 (lambda () (do-param ":changed-before")))
(condition-variable-broadcast! waiter)
(thread-join! t)
調査はSRFI-18が使えるChibi、Gauche、Sagittariusでのみ。FomentやChickenもcond-expandを使って必要な部分だけ何とかすればいけるんだけど、面倒だったので今回はパス。悲しいことにR6RS処理系はSagittariusを除いてSRFI-18をサポートしてないのでそれらもパス。

結果は以下の通り
Chibi
#<Context -2373536>10:changed
#<Context -2555840>:changed:changed-main
#<Context -2108736>:changed-main:changed-other
#<Context -2412960>:changed-other:changed-before

Gauche
#<thread #f runnable 0x800a2a10>10:changed
#<thread "root" runnable 0x800a2e60>10:changed-main
#<thread #f runnable 0x800a28a0>:changed-main:changed-other
#<thread #f runnable 0x800a2b80>10:changed-before

Sagittarius
#<thread thread-9 runnable 0x80204320>10:changed
#<thread root runnable 0x8014ce10>#f:changed-main
#<thread thread-10 runnable 0x80204190>:changed-main:changed-other
#<thread thread-7 runnable 0x802044b0>#f:changed-before
Chibiは全てのスレッドでパラメータの共有しているっぽく、スレッドセーフではない模様。デフォルトでのビルドなのでビルドオプションによっては何かあるかもしれない。

GaucheはShiroさんから聞いていた通りスレッドをまたいでも初期値が保持される模様。

Sagittariusは別スレッドで作成されたパラメータの初期値は取れない、まぁ分かっていたことだけど。 親スレッドで作成されたものは子スレッドに渡るので必要なら親スレッドで準備すればよい話なのだが、これが面倒になってきたので何とかしたいなぁというのもある。

Shiroさんからの情報によると、Gaucheではパラメータの初期値はグローバルに持っていてごにょごにょやっているっぽい。ただ、局所的に作成されたパラメータはGCされないとのこと。(Weakハッシュテーブルとかでなんとかできないのだろうか?) 一応確認してみた。
(import (scheme base))

(do ((i 0 (+ i 1))) ((= i 100000)) (make-parameter 1))
;;(do ((i 0 (+ i 1))) ((= i 100000)) (cons 1 2))

;; trigger GC
(do ((i 0 (+ i 1))) ((= i 100)) (make-vector 100))
パラメータを作る場合と単なるコンスセルの場合でどれくらいメモリ割り当てが違うか。明示的には書いてないが、-f collect-statsオプションを渡すとGCの状況を教えてくれるのでそれを使用。っで以下が結果。
# parameter
% gosh -r7 -f collect-stats test.scm

;; Statistics (*: main thread only):
;;  GC: 14524416bytes heap, 1334816808bytes allocated
;;  stack overflow*: 0times, 0.00ms total/0.00ms avg

# cons
% gosh -r7 -f collect-stats test.scm

;; Statistics (*: main thread only):
;;  GC: 5943296bytes heap, 11413768bytes allocated
;;  stack overflow*: 0times, 0.00ms total/0.00ms avg
コンスセルとパラメータのサイズの違いは調べてないので分からないけど、GCが起きたと仮定するとパラメータとコンスセルの場合で同じメモリになるはずなので、パラメータは回収されていないようにみえる。

動作的にはGaucheの動作が望ましいので、何か手を加えようかな。ただメモリが爆発するのは嫌なので(これが嫌でシンボルもGC対象にしたわけだし)、どうにもならなさそうなら現状維持の方向で。

2015-06-05

getaddrinfo on Cygwin

I think I found a bug on Cygwin or could already be known issue but it kinda took my half a day so might be good to share.

The problem is related to getaddrinfo as this article's title says. The story starts from that I've re-written the executor on (util concurrent), then for some reason getting the error which says 'Name or service not known' which return code is '8'. This error has never happened before even though I was using the library heavily on my testing (if you see the test runner, it uses this library). So first I thought this was because of the re-writing.

So I've checked the code which raises the error message and reached the procedure get-addrinfo. The procedure is just a thin wrapper of getaddrinfo(7) so I've started been doubting. So I've asked my precious body, Google, why this happens, then I've found this Python issue. Sounds pretty much similar. Could it be? So I've wrote the following script to check if this is related to multi threading but my new library.
(import (rnrs) 
        (srfi :18)
        (sagittarius socket))

(define s 
  (thread-start!
   (make-thread
    (lambda ()
      (define sock (make-server-socket "5000"))
      (print 'up)
      (let loop ()
        (let ((cs (socket-accept sock)))
          (socket-send cs (string->utf8 "hello"))
          (loop)))))))

(thread-yield!)
(thread-sleep! 0.1)

(print 'try)

;; uncomment this would make next thread work.
#;(let ((cs (make-client-socket "localhost" "5000")))
  (print (utf8->string (socket-recv cs 255))))

(define c 
  (thread-start!
   (make-thread
    (lambda ()
      (let ((cs (make-client-socket "localhost" "5000")))
        (print (utf8->string (socket-recv cs 255))))))))

(print (thread-join! c))
#|
up
try
Unhandled exception
  Condition components:
  &uncaught-exception
    reason: #<condition
 #<&i/o>
 #<&who get-addrinfo>
 #<&message Name or service not known>
 #<&irritants ((localhost 5000))>
>
    thread: #<thread thread-4 terminated 0x806c8c80>
stack trace:
  [1] thread-join!
  [2] #f
    src: (thread-join! c)
    "test.scm":31
  [3] load
|#
As the comment mentions, if I create a socket on the main thread (or even the thread which creates the server thread?), it works. On POSIX, it says getaddrinfo is thread safe. See, freeaddrinfo, getaddrinfo - get address information. So I think whatever I do on multi threading environment, it should work as I expect. So it's not my library, case closed.

...
......
.........

NO, IT'S NOT!!!

The problem is that Cygwin is one of my most used environment and I can't give up this type of error. However I have no idea how I can resolve this. I've tried to lock before calling getaddrinfo so that the process itself can be atomic. But the result is the same. Now I need to find a workaround for this crappy thing. *sigh*