「Lisp型」NoSQL DBMS Briqs ドキュメント

Briqsとは

技術的にはkey-value storeだが、LispのCons Cellにあたるものをvalueに持てるようにすることで、木構造やグラフ構造などのデータ構造を実現しようとしているNoSQL DBMSです。また、クエリ言語の構文にはLispのS式を用いています。

作成の背景

• データ構造の柔軟性をできるだけ担保したい
• ただしRDBMSの持つデータ間のリレーション操作(JOIN)の柔軟さもできるだけ残したい
• 上記条件を満たしつつも、できるだけデータ走査を速く行いたい
• クエリを書く際の制限をなるべく少なくしたい

といった目標から、LispのS式の持つ性質と、グラフデータベースの内部構造を参考にして作成しました。

課題・懸念点

1. 各データにO(1)でアクセスできる反面、そのデータ構造ゆえに現在は追記のみしかできない
2. メモリ・ディスク容量の使い方が富豪的
3. REPLじゃなくてREP（実行して結果を表示して終了する）
4. エラー処理は皆無（構文エラーでも何にもしてくれません）

1に関して、結果論ですが、追記型なりのデータ容量節約法を実装していきたいです（VACUUM的機能）。
2は将来最適化することで改善していけると考えています。
3はそのうち作りたいです。
4は適当にエラーチェックしていてコードが汚くなって一度消してしまいました。良い方法を考え中です。

というか、全体的にまだオモチャの域を出ていませんけど。

名前の由来

レゴブロックが好きなのですが、そのブロックを英語でbrickと呼ぶことからです。その他にもレゴ用語をいくつか使っています。なお、クエリ言語には語呂合わせでStiqと名付けました。

クエリ言語Stiq

Briqsを特徴付けているのが、このStiqというDSLです。LispのS式を構文に用いています。これにより、データの構造をそのままS式として書き下せるため、データが扱いやすくなっています。

ソースコードはこちら

チュートリアル

briqとbucket

Briqsで扱うデータは全てbriqという単位です。
また、これらのbriqは、それぞれbucketという入れ物に入れていきます。

バケツを用意する

以下のように書いたテキストファイル（仮にbeatles.iqとします）を新規作成します。

beatles.iq

(bucket "beatles")

./briqs beatles.iq

とファイル名を渡してbriqsを実行すると、

("beatles")

と表示されます。
これで無事にbucketを初期化することができました。

ちなみに、今のところこの表示結果に関してはあんまり関係ありません。
bucketで渡した引数がそのまま返ってきているだけです。

bucketの中の様子を図示すると、以下のようになります。

コの字型のbucketの中に、一つだけ入っている箱のようなものがbriqです。
bucketを初期化すると、まず必ずこの図の状態、つまり一つだけbriqが入っている状態になります。
このbriqはCell型であり、先述の通り、そして見た目通り、Lispのコンスセルのようなものです。
左側をL、右側をGと呼びます。現在、このbriqのLにもGにも0が入っています。
briqの左側にも0が書いてありますが、これはこのbriqを特定するためのIDのようなものだと思ってください。

つまりまとめると、
beatlesというbucketの中には、ID:0のbriqが一つだけ入っていて、そのLにもGにも0が入っている
という状態で、これがbucketの初期状態です。

さてこれで、briqを入れるためのバケツが用意できました。

バケツにbriqを放り込んでみる

次に、このバケツに新しいbriqを追加してみましょう。
さっきのテキストファイルに一行追加します。

beatles.iq

(bucket "beatles")
(save "Please Please Me" "beatles")

save関数は引数を二つ取って、
一つ目の引数は保存する対象のbriq、二つ目の引数は保存先のbucketの名前を文字列で指定します。

これを実行すると

("beatles" "Please Please Me")

と表示されます。

最初の"beatles"は一行目の実行結果で、"Please Please Me"が二行目の実行結果です。
save関数は、保存したbriqをそのまま戻り値として返します。
Stiqでは現在、トップレベルだと、各S式の評価結果が順番にリストで返ってくる仕様になっているので、
こういう結果になっています。
現在のbucketの状態は以下のように変化しています。

一つbriqが増えています。これは文字列型のbriqです。中にはさっき保存した文字列が入っています。
IDは自動的に振られて、ID:1になっています。文字列なので、LとかGとかはありません。

ただ、もう一カ所変化している部分があります。ID:0のGが0->1に変化しています。
実はこの「ID:0のG」はbucketの中でも特殊で、「現在のbucket内の最後のbriqのID」が入ることになっています。
従って、briqを追加するとこの部分が1->2->3...と増加していきます。

バケツからbriqを取り出してみる

さて、さらにbriqを追加した後、そのbriqを取り出してみましょう。
以下を実行します。

beatles.iq

(bucket "beatles")
(save "Please Please Me" "beatles")
(save "With The Beatles" "beatles")

結果はもう書きませんが、図示はしておきます。

briqがまた一つ増えて、ID:0のGが1->2に変化しています。

ここからbriqを取り出すには、load関数を使います。

beatles.iq

(bucket "beatles")
(save "Please Please Me" "beatles")
(save "With The Beatles" "beatles")
(load 1 "beatles")

load関数もsaveと同じく引数は二つで、最初の引数がbriqのID、次の引数はsaveと同じでbucket名です。

("beatles" "Please Please Me" "With The Beatles" "Please Please Me")

結果はやはり4行分で4つ出ますが、最後の値がload関数の結果です。
正しく"Please Please Me"が返されていますね。

バケツに入っているbriqを順番に取り出したい

さて、更にbriqを追加していき、その一覧を呼び出すにはどうしたらよいでしょうか。

先ほどのテキストファイルには更に追記していて、以下のようになっています。

beatles.iq

(bucket "beatles")
(save "Please Please Me" "beatles")
(save "With The Beatles" "beatles")
(save "Beatles For Sale" "beatles")
(save "Help!" "beatles")
(save "Rubber Soul" "beatles")
(save "Revolver" "beatles")
(save "White Album" "beatles")
(save "Yellow Submarine" "beatles")
(save "Abbey Road" "beatles")
(save "Let It Be" "beatles")

これらの値を列挙したい場合、
「ループを使ってID:1から順番にloadしていけば良いのでは」と思われるかもしれません。
最後の"Let It Be"のIDは、「ID:0のG」に保存されているので、ループの最後のindexも分かりますし。

しかし、（少なくとも現在）Stiqにループ構文はありません。
また、そのような使い方は、実はそもそも、このStiqではあまりお勧めしていない方法です。
説明が簡単になるので、今まではこのような形でデータを保存してきましたが、
保存したデータを後で列挙するために、違う方法を使ってデータを保存しようと思います。

バケツにCell型のbriqもデータと一緒に放り込む

今度は別のテキストファイル（save_beatles.iqとします）を作ります。

save_beatles.iq

(bucket "beatles")
(: album1 (save "Please Please Me" "beatles"))
(save (~ album1) "beatles")

新しいシンボルが二つ登場しています。

:は関数ではなくて特殊形式ですが、schemeのdefineのようなものです。
2行目は、album1がsaveの戻り値を表すことになります。
ここでは戻り値は、既に保存された"Please Please Me"です。

3行目の~は関数で、Cell型Briqを作るものですが、要するにconsです。

save_beatles.iq

(~ album1)

と書くと、Cell型Briqを作り、Lにalbum1が入ります。Gは指定されていないと見なし、値は0です。
結局それはalbum1のみを要素に持つリストを表すことになります。
つまり3行目全体では、その結果のリスト（の先頭のCell型Briq）を保存している、ということになります。
保存後のbucketの状態を図示してみましょう。

Cell型briqも合わせて、2つのbriqが追加されています。
Lには1、Gには0が入っていますが、これがsave_beatles.iqの3行目でできたものです。
このLの1は、「ID:1へのリンク」という意味です。ですから、ポインタのようなものです。
Briqsでは、このような「他のIDへのリンクを表す数値」のことを、デノータ(denoter)と呼びます。
メモリ上のポインタと似ていますが、区別したい場面が出てくるので、新しい名前を付けることにしました。
デノータをポインタのように考え、先ほどの図に矢印をつけてみます。

さて、思い出してみると当初の目的は、「保存したデータを後で列挙できるようにする」ということでした。
結論から言うと、Briqsでは、デノータを辿っていくことによってそれを実現します。
また、ID:0は特殊なbriqであり、bucketを初期化しても必ず存在するため、全てのデータの起点として使えます。
ID:0のGは既に使ってしまっていますが、Lは0のまま、未使用です。ここを使いましょう。
つまり、以下のようにID:0のLを2に変更できれば、ID:0からデノータを辿って"Please Please Me"に辿り着けるわけです。

そのためのコードを追加すると、以下のようになります。

save_beatles.iq

(bucket "beatles")
(: album1 (save "Please Please Me" "beatles"))
(: cell1 (save (~ album1)))
(: ent (load 0 "beatles")) ;0行目を呼出
(save (setl ent cell1) "beatles") ;0行目のLにcell1をセットして保存

4~5行目で、ID:0のLの更新を行っています。
ちなみにStiq上で;はコメントの開始を表します。行末までがその範囲です。
setl関数は引数を二つ取り、一つ目の引数のLに二つ目の引数をリンクします。
同様の動きをする、setg関数もあります。

それでは今度はせっかくつなげたbriqを呼び出してみましょう。
load_beatles.iqという新しいファイルに

load_beatles.iq

(L (load 0 "beatles"))

と入力して実行します。
L関数はこれまで出てきたLから推測できると思いますが、引数のBriqのL側にあるBriqを返します。
要するに、lispのcarです。G関数も同様で、こちらはもちろんlispのcdrに当たります。
実行結果が以下のようになっていれば、無事デノータを辿ってデータが呼び出せたことになります。

(("Please Please Me"))

Cellをつなげてバケツの中にリストを作ろう

前節の通り、Briqsの肝は「Cell型briqを使ってデータ構造を作っていく」ことであり、
また、「デノータを辿っていくことでデータを走査していく」ことでもあります。
ここまでで出てきた道具立てで、根本的にはその準備は整ったことになります。

というわけで、ここからは少しずつ実用的な内容に近付けていこうと思います。
まずはデータを追加して、それらを列挙できるように、前節のbucketに更にbriqを追加しましょう。
さきほどのソースコードを再掲します。

beatles.iq

(bucket "beatles")
(save "Please Please Me" "beatles")
(save "With The Beatles" "beatles")
(save "Beatles For Sale" "beatles")
(save "Help!" "beatles")
(save "Rubber Soul" "beatles")
(save "Revolver" "beatles")
(save "White Album" "beatles")
(save "Yellow Submarine" "beatles")
(save "Abbey Road" "beatles")
(save "Let It Be" "beatles")

これを、Cell型briqを使う形に書き直してみます。

save_beatles.iq

(bucket "beatles")
(: album1 (save "Please Please Me" "beatles"))
(: cell1 (save (~ album1) "beatles"))
(: ent (load 0 "beatles")) ;0行目を呼出
(save (setl ent cell1) "beatles") ;0行目のLにcell1をセット

(: album2 (save "With The Beatles" "beatles"))
(: cell2 (save (~ album2) "beatles"))
(save (setg cell1 cell2) "beatles") ;cell1のGにcell2をセット

(: album3 (save "Beatles For Sale" "beatles"))
(: cell3 (save (~ album3) "beatles"))
(save (setg cell2 cell3) "beatles") ;cell2のGにcell3をセット

(: album4 (save "Help!" "beatles"))
(: cell4 (save (~ album4) "beatles"))
(save (setg cell3 cell4) "beatles") ;cell3のGにcell4をセット

(: album5 (save "Rubber Soul" "beatles"))
(: cell5 (save (~ album5) "beatles"))
(save (setg cell4 cell5) "beatles") ;cell4のGにcell5をセット

(: album6 (save "Revolver" "beatles"))
(: cell6 (save (~ album6) "beatles"))
(save (setg cell5 cell6) "beatles") ;cell5のGにcell6をセット

(: album7 (save "White Album" "beatles"))
(: cell7 (save (~ album7) "beatles"))
(save (setg cell6 cell7) "beatles") ;cell6のGにcell7をセット

(: album8 (save "Yellow Submarine" "beatles"))
(: cell8 (save (~ album8) "beatles"))
(save (setg cell7 cell8) "beatles") ;cell7のGにcell8をセット

(: album9 (save "Abbey Road" "beatles"))
(: cell9 (save (~ album9) "beatles"))
(save (setg cell8 cell9) "beatles") ;cell8のGにcell9をセット

(: album10 (save "Let It Be" "beatles"))
(: cell10 (save (~ album10) "beatles"))
(save (setg cell9 cell10) "beatles") ;cell9のGにcell10をセット

これで再度（こちらのソースコードは変わっていません）、

load_beatles.iq

(L (load 0 "beatles"))

を実行すると、今度は

(("Please Please Me" "With The Beatles" "Beatles For Sale" "Help!" "Rubber Soul" "Revolver" "White Album" "Yellow Submarine" "Abbey Road" "Let It Be"))

という風に、登録した10個の文字列が順番に表示されます。うまくいきました。
しかしながら、ちょっとソースコードとしては冗長です。
結果を変えないように注意しながら、書き直していくことにします。

まず、bucket名である"beatles"が繰り返されていますので、これを:を使ってまとめましょう。

save_beatles.iq

(: bc "beatles")
(bucket bc)
(: album1 (save "Please Please Me" bc))
(: cell1 (save (~ album1) bc))
(: ent (load 0 bc)) ;0行目を呼出
(save (setl ent cell1) bc) ;0行目のLにcell1をセット

(: album2 (save "With The Beatles" bc))
(: cell2 (save (~ album2) bc))
(save (setg cell1 cell2) bc) ;cell1のLにcell2をセット

(: album3 (save "Beatles For Sale" bc))
(: cell3 (save (~ album3) bc))
(save (setg cell2 cell3) bc) ;cell2のLにcell3をセット

(: album4 (save "Help!" bc))
(: cell4 (save (~ album4) bc))
(save (setg cell3 cell4) bc) ;cell3のLにcell4をセット

(: album5 (save "Rubber Soul" bc))
(: cell5 (save (~ album5) bc))
(save (setg cell4 cell5) bc) ;cell4のLにcell5をセット

(: album6 (save "Revolver" bc))
(: cell6 (save (~ album6) bc))
(save (setg cell5 cell6) bc) ;cell5のLにcell6をセット

(: album7 (save "White Album" bc))
(: cell7 (save (~ album7) bc))
(save (setg cell6 cell7) bc) ;cell6のLにcell7をセット

(: album8 (save "Yellow Submarine" bc))
(: cell8 (save (~ album8) bc))
(save (setg cell7 cell8) bc) ;cell7のLにcell8をセット

(: album9 (save "Abbey Road" bc))
(: cell9 (save (~ album9) bc))
(save (setg cell8 cell9) bc) ;cell8のLにcell9をセット

(: album10 (save "Let It Be" bc))
(: cell10 (save (~ album10) bc))
(save (setg cell9 cell10) bc) ;cell9のLにcell10をセット

これでbucket名を切り換える変更などがやりやすくなりました。
でもやはり、長いです。特に2~9個目は、ほとんど同じコードを単純に繰り返しています。
少なくとも、

save_beatles.iq

(: album (save アルバム名 bc))
(: cell (save (~ album) bc))

の部分は、結局アルバム名を要素に持つリストを作る、ということなので、まとめたいところです。
さて、ここでそのために^特殊形式が出てきます。これは無名関数を作ります。お察しの通り、lambdaのことです。
書式は以下です。

(^ (引数) 本体)

この^を:に渡して、関数に名前を付けましょう。
以下は、アルバム名を渡すと、それを要素に持つリストを返す関数です。

save_beatles.iq

(: album-cell (^ (album-name) 
    (: album (save album-name bc))
    (save (~ album) bc)))

というわけで、album-cellという、album-nameを引数に持ち、それをリストにくるんで返す関数を作りました。
^特殊形式内は、最後に評価された値が全体の戻り値になりますので、
最後はsaveされたリストが返ってくるわけです。

これを使うとソースコードは以下のようになります。

save_beatles.iq

(: bc "beatles")

;アルバム名をリストでくるんで返す
(: album-cell (^ (album-name)
    (: album (save album-name bc))
    (save (~ album) bc)))

(bucket bc)

(: cell1 (album-cell "Please Please Me"))
(: ent (load 0 bc)) ;0行目を呼出
(save (setl ent cell1) bc) ;0行目のLにcell1をセット

(: cell2 (album-cell "With The Beatles"))
(save (setg cell1 cell2) bc) ;cell1のLにcell2をセット

(: cell3 (album-cell "Beatles For Sale"))
(save (setg cell2 cell3) bc) ;cell2のLにcell3をセット

(: cell4 (album-cell "Help!"))
(save (setg cell3 cell4) bc) ;cell3のLにcell4をセット

(: cell5 (album-cell "Rubber Soul"))
(save (setg cell4 cell5) bc) ;cell4のLにcell5をセット

(: cell6 (album-cell "Revolver"))
(save (setg cell5 cell6) bc) ;cell5のLにcell6をセット

(: cell7 (album-cell "White Album"))
(save (setg cell6 cell7) bc) ;cell6のLにcell7をセット

(: cell8 (album-cell "Yellow Submarine"))
(save (setg cell7 cell8) bc) ;cell7のLにcell8をセット

(: cell9 (album-cell "Abbey Road"))
(save (setg cell8 cell9) bc) ;cell8のLにcell9をセット

(: cell10 (album-cell "Let It Be"))
(save (setg cell9 cell10) bc) ;cell9のLにcell10をセット

少し短くなりました。でも、save関数で始まる各行はそのままです。
そこで共通項を探ってみると、どうやら「一つ前に作ったCellのG」に「今作ったCell」をつなげる、ということのようです。
さきほどのように単純な法則ではないですが、ここも関数化したいですね。
そこでさっきの図解を思い出してみます。
まず、二つのアルバム名を登録した直後の状態です。

これが、もう一つアルバム名を登録すると、以下の状態になります。

「一つ前に作ったCellのG」を取るための方法はいくつかあるかもしれませんが、
図解を見て考えた結果、最も応用が利きそうな方法である「ID:0からデノータを辿り、最後のCellを取得する」という方法を採用しようと思います。

「ID:0からデノータを辿り、最後のCellを取得する」ために、新しい関数を作ります。lastという名前にします。

save_beatles.iq

(: last (^ (cell)
    (? (G cell)
       (last (G cell))
       cell)))

lastはcellという引数を一つ取る関数です。そして新しいシンボル、?が出てきました。これは

(? 条件 式1 式2)

という書式を取る、言わばif文です。条件は真偽で判断され、真ならば式1、偽ならば式2が評価されます。
G関数は、指定したbriqのGにあたるbriqを返します。
last関数の中の条件文は

(G cell)

ですが、結論から言うと、これはリストの終端であるかどうかを判断する部分です。
先ほどの最後の図解で言うと、ID:4のGは6ですが、ID:6のGは0、つまりN(lispで言うnil)です。
nil同様、StiqでもNは偽と扱い、それ以外は真と扱います。
そこから読み取ると、この条件文は
「真の時（リストが後ろにまだ続いている場合）はlast関数を再帰的に呼び出し、
　偽の時（リストがそのCellで終わりの場合）は引数をそのまま返す」
ということになり、
last関数は、「与えられたCellのGのデノータを辿って一番端のCellを返す」という内容だと分かります。

実際にlast関数を使う際には、ID:0の（Gではなく）Lから辿っていくので、

save_beatles.iq

(last (L (load 0 bc)))

とすれば、どれだけ多くの項目が登録されていても、常にID:0から辿った一番端のCellが取得できることになります。
というわけで、このlast関数で元のソースコードを置き換えてみます。

save_beatles.iq

(: bc "beatles")

;アルバム名をリストでくるんで返す
(: album-cell (^ (album-name)
    (: album (save album-name bc))
    (save (~ album) bc)))

;指定されたリストの一番端のCellを取得する
(: last (^ (cell)
    (? (G cell)
       (last (G cell))
       cell)))

;指定した名前のアルバム項目を追加する
(: add-album (^ (album)
    (: c (album-cell album))
    (save (setg (last (L (load 0 bc))) c) bc)))

(bucket bc)

(: cell1 (album-cell "Please Please Me"))
(: ent (load 0 bc)) ;0行目を呼出
(save (setl ent cell1) bc) ;0行目のLにcell1をセット

(add-album "With The Beatles")
(add-album "Beatles For Sale")
(add-album "Help!")
(add-album "Rubber Soul")
(add-album "Revolver")
(add-album "White Album")
(add-album "Yellow Submarine")
(add-album "Abbey Road")
(add-album "Let It Be")

最初の項目だけ特別扱いされてることは変わりませんが、これでかなりすっきりしました。

もっと保存を簡単にしよう

さて、ここまでで行ったのは、「10個の要素を持つリストを保存して、呼び出す」という、それだけのことです。
「10個の要素を持つリストを保存する」コードと、「保存したリストを呼び出す」コードを比較すると、保存する側のコード量がとても多いです。
「リストの中身を保存する」だけでこれだけの手間が掛かるのなら、実用するのは少し苦しい気がします。

しかも、実はStiqの紹介文で、こうも書いています。

Briqsを特徴付けているのが、このStiqというDSLです。LispのS式を構文に用いています。これにより、データの構造をそのままS式として書き下せるため、データが扱いやすくなっています。

「データ構造をそのままS式として書き下せる」のなら、

("Please Please Me" "With The Beatles" "Beatles For Sale" "Help!" "Rubber Soul" "Revolver" "White Album" "Yellow Submarine" "Abbey Road" "Let It Be")

というリストをソースコードに書いて、そのまま保存できるのではないでしょうか。
実は、できます。ごめんなさい。
前回のチュートリアルは言わば「内部のしくみを知ってもらう」ことも目標だったので、あえて手間の掛かる方法を使ってしまっていましたが、今まで使っていなかった関数を使えばできます。

save-recursiveという名前です。これを使うと、最初のコードは以下のようになります。

save_beatles.iq

(: bc "beatles")
(bucket bc)

(: album-list (save-recursive
    (Q ("Please Please Me"
        "With The Beatles"
        "Beatles For Sale"
        "Help!"
        "Rubber Soul"
        "Revolver"
        "White Album"
        "Yellow Submarine"
        "Abbey Road"
        "Let It Be")) bc))

(save (setl (load 0 bc) album-list) bc)

かなりすっきりしました。

Qというシンボルが新しく出てきましたが、これはlispのquoteで、引数のリストを評価せずにそのまま返します。Qを付けないと、評価の決まり上、リストの最初の要素が関数や特殊形式だと見なされてしまうので、それを防ぐために付いています。データとしてのリストが欲しい時に、頻繁に使います。あまりに頻繁に使うので、

(Q a)

と書く代わりに

'a

と書けます。これもlispでおなじみのリードマクロです。これを使うとさきほどのソースコードは

save_beatles.iq

(: bc "beatles")
(bucket bc)

(: album-list (save-recursive
    '("Please Please Me"
      "With The Beatles"
      "Beatles For Sale"
      "Help!"
      "Rubber Soul"
      "Revolver"
      "White Album"
      "Yellow Submarine"
      "Abbey Road"
      "Let It Be") bc))

(save (setl (load 0 bc) album-list) bc)

となり、もう少しだけすっきりしました。

save-recursiveは便利ですが、結局、これまでと同じことを、自動的に行っているだけです。
また上記の方法は、固定のデータを一度に保存する場合にしか使えませんので、
一つ一つ項目を追加していきたいなら、save-recursiveだけでは不足ですし、
最後の行にある通り、ID:0のLデノータからリスト本体へリンクする処理は相変わらず必要です。

その他のこと

ここまでお付き合いいただき、ありがとうございます。
文字列の修正、項目の挿入など他にもまだまだやってみたいことはありますが、
ひとまずここで区切りとさせていただきたいと思います。

次の記事では、属性を複数持つオブジェクト（に似たもの）を作って、
Briqsをもう少し実用的に活用していければと考えています。

それではまた、その時に。
ありがとうございました。