[racket] Confusion with circular structs

From: Nicholas Labich (labichn at gmail.com)
Date: Fri Jul 26 17:47:26 EDT 2013

> It looks to me like you can't specify rational sets with shared
I didn't expect to be able to, but I found it interesting that I didn't hit
an error; it just returned a value I didn't expect. Any idea why direct
mutation isn't working?

> Does OCAML allow rational sets?
I do not know, I only mentioned OCaml to point out that equality on cyclic
data doesn't always do what you want/hope it to.


On Fri, Jul 26, 2013 at 3:38 PM, Matthias Felleisen <matthias at ccs.neu.edu>wrote:

>
> It looks to me like you can't specify rational sets with shared:
>
> % racket
> Welcome to Racket v5.90.0.3.
> > (struct vertex (v s p) #:transparent #:mutable)
> > (define-values (x y z)
>     (shared ([v0 (vertex 0 (list) succs0)]
>      [v1 (vertex 1 preds1 (list))]
>      [v2 (vertex 2 preds2 succs2)]
>      [succs0 (list v1 v2)]
>      [preds1 (list v0)]
>      [preds2 (list v0 v2)]
>      [succs2 (list v2)])
>       (values v0 v1 v2)))
> > x
> #0=(vertex 0 '() (list (vertex 1 '(#0#) '()) #1=(vertex 2 '(#0# #1#)
> '(#1#))))
> > y
> #0=(vertex
>     1
>     (list #1=(vertex 0 '() (list #0# #2=(vertex 2 '(#1# #2#) '(#2#)))))
>     '())
> > (set-vertex-s! x (vertex-s y))
> > x
> #0=(vertex
>     0
>     #1='(#0#)
>     (list (vertex 1 #1# '()) #2=(vertex 2 '(#0# #2#) '(#2#))))
>
>
>
> Does OCAML allow rational sets? -- Matthias
>
>
>
>
>
>
>
>
> On Jul 26, 2013, at 5:25 PM, Nicholas Labich wrote:
>
> I'm running into what I find to be surprising behavior with circular
> structures (vertices of a simple graph).
>
> Graphically (see code below to reproduce):
> 0 --> 1 ;; no problem
> 2-+      ;; also no problem
>  ^-+
>
> But when I try to add an edge between 0 and 2, I hit an infinite loop at
> line 88 of racket/set.rkt (in 5.3.3) or line 447 of
> racket/private/set-types.rkt (in the latest 5.90.0.2), both of which are
> the hash-proc for set's gen:equal+hash.
>
> Is this the expected behavior (after all, OCaml makes no guarantee of
> termination for (=) on circular data)? I'm surprised that the self-edge on
> 2 doesn't result in the same. I've also tried to reproduce the same using
> `shared', but I'm assuming I still misunderstand its functionality because
> the result is not quite what I expect it to be.
>
> Any insight would be much appreciated.
>
> Nick
>
> Welcome to Racket v5.90.0.2.
> > (struct vertex (value preds succs) #:mutable #:transparent)
> > (define v0 (vertex 0 (set) (set)))
> > (define v1 (vertex 1 (set) (set)))
> > (set-vertex-succs! v0 (set v1))
> > (set-vertex-preds! v1 (set v0)) ;; 0 --> 1
> > (equal? v0 (set-first (vertex-preds v1)))
> #t
> > (define v2 (vertex 2 (set) (set)))
> > (set-vertex-preds! v2 (set v2)) ;; 2--+
> > (set-vertex-succs! v2 (set v2)) ;; ^--+
> > v2
> #0=(vertex 2 (set #0#) (set #0#))
> ;; try to add the already existing set
> > (set-vertex-succs! v0 (set-add (vertex-succs v0) v2)) ;; loops and loops
>   C-c C-c^Cuser break
>   context...:
>  .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc
>  .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc
>  .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc
>  .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc...
> ;; try to make a new set instead
> > (set-vertex-succs! v0 (set v1 v2))
>   C-c C-c^Cuser break
>   context...:
>   .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc
>   .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc
>   .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc
>   .../racket/collects/racket/private/set-types.rkt:447:3: hash-proc...
>
> > (shared ([v0 (vertex 0 (set) succs0)]
>            [v1 (vertex 1 preds1 (set))]
>            [v2 (vertex 2 preds2 succs2)]
>            [succs0 (set v1 v2)]
>            [preds1 (set v0)]
>            [preds2 (set v0 v2)]
>            [succs2 (set v2)])
>     (values v0 v1 v2))
> (vertex 0 (set) (set #0=(vertex 2 (set #0#) (set #0#))))
> (vertex 1 (set (vertex 0 (set) (set #0=(vertex 2 (set #0#) (set #0#)))))
> (set))
> #0=(vertex 2 (set #0#) (set #0#))
> ;; I must be using `shared' incorrectly...
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130726/78d8655e/attachment-0001.html>

Posted on the users mailing list.