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

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

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

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

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

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

  1. #0=(a . #0#)
  2. (#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パスで構築されることを 要求しているところにある

考えられる解決策:

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

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

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

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

読み込み時にも状態を持ちまわって、もしオブジェクトそのものではなく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)


Last modified : 2012/02/07 08:03:48 UTC