Let's start 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