Gauche > Archives > 2013/05/21

2013/05/21 07:31:05 UTCyamasushi
#
recordの等価判定なのですが、chickenではequal?で判定できるのですが、これは処理系に依存する振る舞いなのでしょうか? SRFI 99: ERR5RS Records
http://srfi.schemers.org/srfi-99/srfi-99.html
#
#;2> (define-record-type p make-p #f x y z)
#;3> (equal? (make-p 1 2 3) (make-p 1 2 3))
#t
#;4> (equal? (make-p 1 2 3) (make-p 1 2 4))
#f
#
recordをつかったrelationをつくってみたのですが、そこでちょっと困ったのでした。とりあえず、こんな感じにして回避しました。https://gist.github.com/yamasushi/5617926 rtd-equality-testerなるプロトコルを追加したのでした。
2013/05/21 08:05:17 UTCkaki
#
<record> に object-equal? が欲しいですね
2013/05/21 08:13:21 UTCshiro
#
R6RS recordもERR5RS recordもequal?はeqv?と完全に等価であることを要求してますよね? equal?で中身に再帰してはいけないという話は http://www.r6rs.org/r6rs-editors/2005-August/000830.html にぶら下がってるスレッドを見てください。ここではSchemeはCLと同じく慎重な立場を取り、(1)何が等価かはコンテキスト依存なのでひとつの動作を決め打ちするのは良くない(2)再帰することに決めちゃうとequal?のコストが予想できなくなる、あたりがこの仕様の理由だと思います。もっと欲しいものがはっきりするまでは仕様に入れないから、必要な等価判定を自分で書いてね、っていうスタンス。
#
ただまあGaucheの場合、ジェネリック関数を使って<record>の場合に再帰するmy-equal?を書くのは簡単なんですが、ハッシュテーブルが一般化された等価判定をサポートしてないのでそこで困っちゃいますね。これはなんかうまい方法が思いつくまで保留にしてあるところです。
2013/05/21 08:27:38 UTCyamasushi
#
relationのタプルの表現としてrecordは最適な感じなので、record-relationを実装できる仕掛けがなにかあれば、それはそれで有用な気がします。
2013/05/21 08:31:49 UTCshiro
#
relationのそれに使うだけなら、record.scm改変してrtd-equality-tester書かなくても、単にrecord-equiv?みたいなメソッドを<record>と<pseudo-record>に後付けするんでいけませんかね。あ、<pseudo-record>をexportしてないな。
2013/05/21 08:35:19 UTCkaki
#
深く考えずにレスしてしまっていました.なるほど…. Gauche的には再帰的に equal? する object-equal? メソッドを持つ <record> のサブクラスがあれば便利そう,と思いました.でも gauche.record は単一継承か…
2013/05/21 08:36:36 UTCyamasushi
#
<pseudo-record>のインスタンスというのは、実体がよくわからないのではないでしょうか? <list>かもしれないし<vector>かもしれない。なのでrtdが判定関数を提供しないといけない・・・・と考えたのでした。
2013/05/21 08:38:34 UTCshiro
#
あっそうか。そうですね。<pseudo-record>のインスタンスって実際には作られないんだった。
2013/05/21 08:44:21 UTCshiro
#
んー、でもrecordでもpseudo-recordでも、要は全てのフィールドについてそれぞれequal?を確かめればいいのだから、わざわざ別々に用意しなくてもいいような気がするなあ。
2013/05/21 09:05:31 UTCyamasushi
#
recordの場合にはすべてのフィールドにequal?を確かめるのですけれど、psudo-recordはもっと効率のいいやり方でできるのではないかと考えたのでした。(どうすれば効率がいいのかよくわからないのですが。)
#
(define-method rtd-equality-tester ((rtd <pseudo-record-meta>))
  (let1 size (vector-length (slot-ref rtd'field-specs))
    (^ xy
      ($ equal? $* map (cut subseq <> 0 size) xy)
    ) ) ) のsubseqをしているあたりは改良の余地があるのでしょうね・・・
2013/05/21 09:12:50 UTCyamasushi
#
この方法か、上でご指摘のあったとおり、object-equal?のあるrecordを定義する。その使用は自己責任という流れかなあとか。
#
その場合、pseudo-recordの判定の扱いをどうやるか?ということに。rtd-predicateの実装のように、ゆるやかな扱いをするとなると・・・・
2013/05/21 09:20:14 UTCkaki
#
pseudo-recordの場合は直接 equal? すればいいんじゃないでしょうか.
2013/05/21 09:33:58 UTCshiro
#
>yamasushi はい、効率の良いやり方はありますが、subseq噛ましてるのとクロージャ作ってるのでそのコードならあまり効率は関係ないかと。一番効率良いのはべたにインデックスでループするコードだと思います。
#
>kaki 一応、長いベクタの先頭いくつかの要素をpseudo-recordとみなす、という使い方ができるので、「それ以降は違ってても良い」という立場なら直接equal?は使えなくなります。そういう用途は限定されそうですけど。
2013/05/21 09:38:27 UTCkaki
#
なるほど,そういうのもあるんですね.気が付きませんでした.
2013/05/21 09:39:32 UTCshiro
#
効率言うなら、インデックスでループしてもその中でジェネリックなref使っちゃうと台無しなんで、それなら先に全部のreferencerを作っておいてそれでアクセスかける方が良くて、それならrecordのルーチンと同じになりますね。
2013/05/21 10:27:11 UTCyamasushi
#
u8vectorをまとめてu64vectorで比較するなんてことができたらいいのかしら?とか。
#
アセンブラのブロック比較的なことができればいいのかなあとか考えていたのでした。
2013/05/21 10:31:09 UTCshiro
#
uvector-alias使えばできますが、ある程度以上の大きさでないと終端の中途半端な部分の処理とかのオーバヘッドで帳消しになってしまう可能性が。
#
まあベンチ取ってみないとわかりませんが。(昔々、PS2でできるだけ128bit wordでまとめて処理するコードを書いてベンチ取ってみたけど半端分の処理が足を引っ張ってあんまり嬉しく無かった記憶が。必ず境界ぴったしに収まってるってわかってるデータなら良いんですけど、一般化しようとすると面倒ですな。)
2013/05/21 10:37:30 UTCyamasushi
#
4の倍数限定にしても、それなりに用途はあるのではないでしょうか? [R6RS] R6RS records: record equality
http://www.r6rs.org/r6rs-editors/2005-August/000831.html
では、IPアドレスとかに使うと言うこと(?)を書いていますけど。
2013/05/21 10:45:00 UTCshiro
#
まあ、rtdが出来た時点でサイズはわかるので、その時に4なり8の倍数なら最適化された比較ルーチンを作っとくってことは出来るでしょう。場合分けするぶんコードがごちゃごちゃするので、私なら本当に必要になる時まで作るのを遅延しますが。
2013/05/21 11:03:13 UTC齊藤
#
C の memcmp 関数って大抵はある程度のまとまった単位で処理して最後の半端もうまいことやってくれる実装になってますけど、それに丸投げしたんじゃ駄目なんでしょうか。 Gauche の世界のレコードって C の世界で memcmp で比較できるような形じゃないのかな?
2013/05/21 11:17:19 UTCshiro
#
もはやレコードじゃなくてuvectorの話になってるんですが (一般のレコードは各フィールドに再帰しないとならないのでmemcmpじゃだめ)、「uvectorのここからここまでを比較して」っていうAPIがまだ無いんですね。高速な比較が必要になったことが無かったんで。
2013/05/21 11:21:43 UTCshiro
#
uvector丸ごと比較はどうしてるかと思ったら一要素づつ比較してるなあ。まあ、f(16|32|64)vectorだとどっちにせよmemcmp使えないんだけど (NaNや-0.0が混ざってる可能性があるため)。要するに性能とコードの複雑化とのトレードオフが今はこのへんに落ち着いてるって感じです。どうしても高速に比較したいって要望が出れば何か考えるかも。
2013/05/21 22:00:21 UTCyamasushi
#
recordの等価判定を適切におこなえるようにフィールドの型を限定したようなrecordのサブタイプを定義すればいいということなのかしら?とか考えました。
2013/05/21 23:56:46 UTCshiro
#
拡張方法は色々考えられると思います。ただまあ、recordのサブタイプにしちゃうとERR5RS/R6RSのequal?の要請とどうやって折り合いをつけるかってとこが問題になりますね。