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がいろいろまとまっているので参照するとよいだろう。