Gauche:循環リストの読み書き

循環や共有構造を持つS式

循環や共有構造を持つS式の表現は、srfi-38で決められている。この表記はCommon Lispから取ったもので、たとえば次の2つの式：

(let ((x (list a))) (set-cdr! x x) x)
(let ((x (cons 'a 'b))) (cons x x))

によって作られる構造は、それぞれ次のように記される。

#0=(a . #0#)
(#0=(a . b) . #0#)

#n= でもってオブジェクトにラベルをつけ、 #n# で参照する

Gaucheは、version 0.7.1現在、write* による表示のみサポートしているが、読み込みはサポートしていない。近いうちにサポートしたいので、ここで色々考えてみる。

問題点 - srfi-10 vs srfi-38

循環リストの読み込みは、使えるデータ型が決まっていれば難しくない。しかしGaucheの場合、srfi-10によってユーザ定義のデータ型が外部表現を持つことができる。例えばpersonというクラスをユーザが定義して、

  #,(person "Shiro" 'programmer)

のような表記を読むと、該当するpersonクラスのインスタンスが返ってくるようにすることができる。

ここで、もしこのようなユーザ定義型のスロットに循環構造が現れたらどうなるだろうか。

  #0=#,(person "Shiro" #0#)

#0#のラベルは #,(person ...) が読まれた結果のインスタンスを参照しなければならないが、#,(person ...) を読んだリーダはpersonのコンストラクタに #0#が指すオブジェクトを渡さなければならない。

本質的な問題は、srfi-38表記はオブジェクトが2パスで構築されることを要求しているところにある

考えられる解決策：

とりあえず、ユーザ定義構造体で循環が現れる場合はサポートしない(エラーとする)
srfi-10を拡張し、2パスで構築するプロトコルをサポートする：上記のような未確定の参照が読まれた場合、コンストラクタにまず仮のオブジェクトを渡し、参照が確定した時点でもう一度別のメソッドを呼んでアップデートをかける。

複数回のwrite/ssで共有構造を書き出す

共有構造を持つ複数のグラフをwrite/ssを別々に呼び出して出力すると、read/ssでそれを読み込んでも、同じグラフを得ることはできず、共有構造だった部分が別々のコピーになってしまいます。共有構造がmutableだったり同一性が重要だったりする場合、これは問題になります。

Pythonにおけるオブジェクトのシリアル化機能(pickle/unpickle)では、別々のdump呼び出しでも参照を維持することができます(IBM DeveloperWorksの記事)。これをGaucheでも実現したいのですがどのようにすればよいでしょうか?

SRFI-38のread/ss, write/ssに頼ることはできないので、今のところとりあえず次の方針でシリアル化するということを考えています。

オブジェクトをリストにシリアル化する手続きを自前で用意する
その手続きで状態オブジェクトを持ち回る
状態オブジェクトに、すでに書き出したオブジェクトの参照を記録しておいて、すでに書き出したオブジェクトが与えられた場合はそのIDを書き出す。まだ書き出していないオブジェクトなら、オブジェクトにID(整数)を振って、それを記録しておく。

読み込み時にも状態を持ちまわって、もしオブジェクトそのものではなくIDが与えられた場合には、読み込み済みのオブジェクトを返すという処理をします。

概念的には次のような出力をして、それを適切に読み込むということになります(実際には#n=, #n#という記法を使うことはできず、もっと冗長な記法を使うのですが)。

 > (define str "abc")
 > (define ctx (make-write/ss*-context))
 > (write/ss* str ctx)
 #0="abc"
 > (write/ss* str ctx)
 #0#

実用上は上のように自分でformat, read/ss, write/ssと別のメソッド一セットを用意する方法でなんとかなりそうですが、本質的には既存機能のスーパーセットとしてうまく扱うことができるような気がしてどうも落ち着きません。SRFI-10/38を拡張する際はこの点を考慮してもらえると幸いです。どういう方法がいいのかわかりませんけど。

なお、上記の機能を必要としている理由は、PrevaylerをGaucheで実装しようとしているからです(→実装しはじめました(Gauche:ObjectPrevalence ))。Prevaylerは、オブジェクト永続化の手法の一つで、永続化できるオブジェクトに対する変更を永続化可能なトランザクションオブジェクト継由でのみ行うことにして、そのトランザクションをログに保存しておくことで、同じオブジェクト構造をあとで再現できるようにするという手法なのですが、トランザクションは別々にログにwriteされるため、そのwrite呼び出しをまたいで共有構造を再現することが必要になるのです。

(write呼び出しをまたぐ状態オブジェクトは一度書き出したオブジェクトをすべて覚えておく必要があり、それによってオブジェクトがGCされないということを防ぐために、weak hashも必要になる気がします。が、それはまた別の話ですね。) (2005/06/29 03:42:30 PDT)

Shiro: 内部的には状態オブジェクトを作って持ち回っているので、それをSchemeレベルから使えるようにAPIをちょっと変えるのがいいですかね。ただ、現在のwrite/ssにはCommon Lispの *print-readably* に相当するものがないため、読み込み不可能なオブジェクトがダンプされてしまったことをreadするまで検出できません。真面目にwrite/ssで永続化を考えるなら、そのへんも考慮する必要があるでしょう。 Kahuaのオブジェクトデータベースkahua.persistence では自前のシリアライザを使っています。srfi-10構文を使えばreadはシステムのものを使えるかも。writeは自分でトラバースしなくちゃならないですが。

状態オブジェクトをSchemeレベルから使えるようになると助かります。それ以外に、出力方法などについても少し変える必要があると思います。
- 既存のwrite/ssではグラフのノードを全部訪れてから出力パスに進んでいますが、write/ssをまたいで共有構造を出力する場合、ノードを事前にすべて訪れることはできません。従ってどのノードが共有構造なのかを出力時にすべて知ることはできません(でなければ、ある種の明示的なクローズ操作を用意して、クローズ時にいままでの出力をすべて書き出すということになりますが、それでは自分で要素をリストにまとめて一度にwrite/ssを呼ぶのと大して違いがありません)。変更ログをその都度書き出す目的などには順次書き出していけるという性質が必須です。
- 出力先ポートは途中で変更されることがあるかもしれません。変更ログ出力ファイルが切り替わるといった場合がありえます。
- #,(...)の中に共有構造が含まれる場合を扱う非公式APIがすでに存在しているようですが、あのAPIでよいかどうかを考えないといけないですね。
- 現在のwrite-objectメソッドのAPIが1パス目と2パス目を区別しないゆえの問題も、これをまじめに考えるならなんとかしないといけないかもです。
やりたいことはKahuaのオブジェクトデータベースと似ています。kahua.persistenceを使うことも考えてみたのですが、シリアライズ可能なオブジェクトが既知のプリミティブなオブジェクトに限られていることと、グラフ構造が再現される(同じオブジェクト群が手に入る)か分からなかったので、Prevaylerを移植しようと考えました。kahua.persisitenceでは無限リストのシリアライズで無限ループに入るようですが、標準のwrite/ssで出力できるようになればそういう考慮をしなくて済むという利点もあると思います。

(2005/07/02 10:04:05 PDT): Gaucheのreaderとwriterに手を加えて状態オブジェクトを持ちまわれるようにしてしまいました。Schemeレベルで生成された状態オブジェクトが渡された場合、write/ssはすべてのオブジェクトに#n=タグを付加し、同一性を保ってread/writeできます。Gauche自身のread/writeを使えるメリットは大きいので、この上にPrevalence Layerを作ろうと考えてますが、非標準なものの上にコードを書いていくのは後々困るかもしれないので、Shiroさんの意見を伺いたいです。これに類する機能をGaucheが採用することはありますか？なければやっぱりアプリケーションレベルでシリアライズすることにしますけど。しばらく使ってみてから訊いてみたほうがよいでしょうか？

Shiro: コードを見ることはできますか。当方の考えている他の変更と整合するようでしたら、Gauche本体に取り込んでしまってもいいかと思います。