Will guile support R7RS terminating "equal?" in the presence of cycle?

Will guile support R7RS terminating "equal?" in the presence of cycle?

[David A. Wheeler]

I'd really like for there to be a common spec for Scheme with libraries, etc., and my hope is that R7RS will be that spec.

*However*, the current R7RS draft for "equal?" requires termination even in the presence of cycles, as well as impose other requirements on "write" and "display" in the presence of cycles.  Will guile support such changes?  I worry that these new requirements on "equal?" will have such a high overhead that people won't do it.  But perhaps those fear are misplaced.

Thanks.

--- David A. Wheeler

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Ludovic Courtès]

Hi,

"David A. Wheeler" <dwheeler@dwheeler.com> skribis:

> *However*, the current R7RS draft for "equal?" requires termination
> even in the presence of cycles, as well as impose other requirements
> on "write" and "display" in the presence of cycles.  Will guile
> support such changes?  I worry that these new requirements on "equal?"
> will have such a high overhead that people won't do it.  But perhaps
> those fear are misplaced.

Are you talking about termination in the case of circular lists, or for
arbitrary data structures?

The former is easy and reasonably cheap, but the latter may require more
work, indeed.

Thanks,
Ludo’.

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Ian Price]

"David A. Wheeler" <dwheeler@dwheeler.com> writes:

> I'd really like for there to be a common spec for Scheme with libraries, etc., and my hope is that R7RS will be that spec.

Call me a cynic, but if r6rs couldn't do that, then I don't see how r7rs
could be given that it actively avoids many important portability
questions. But we all can dream...

-- 
Ian Price -- shift-reset.com

"Programming is like pinball. The reward for doing it well is
the opportunity to do it again" - from "The Wizardy Compiled"

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[David A. Wheeler]

I said:
> > I'd really like for there to be a common spec for Scheme with libraries, etc., and my hope is that R7RS will be that spec.

Ian Price:
> Call me a cynic, but if r6rs couldn't do that, then I don't see how r7rs
> could be given that it actively avoids many important portability questions.

Well, the cynics are often right :-).  But I think R7RS is intentionally much more conservative and R5RS-like.  In particular, it's *supposed* to be easy for an R5RS implementation to move to R7RS.  If it's easier to adopt, it's more likely to be adopted.

Scheme is rediculously non-portable due to its lack of a *standard* library system.  If a standard for *that* could be widely adopted, many other portability problems would be drastically reduced.

> But we all can dream...

Indeed!

--- David A. Wheeler

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 1800 bytes --]

The cycle detection for a tree would probably look something like,

SCM scm_equal_cons(SCM x, SCM y, SCM slow, int move)
{
  SCM res;
  if(scm_is_pair? (x) && scm_is_pair (y))
    {
      if(scm_is_eq (x, slow)) cycle_detection_hit();

      if(move)
        if(scm_is_pair? (SCM_CAR (slow)))
          slow = scm_cons(SCM_CAAR (slow),
                          scm_cons(SCM_CDAR (slow), SCM_CDR (slow)));
        else
          slow = SCM_CDR (slow);
      ccccccccccccccx
      res = scm_equal_cons (SCM_CAR(x), SCM_CAR(y), slow, !move);

      if(scm_is_false (res)) return SCM_BOOL_T;

      res = scm_equal_cons (SCM_CDR (x), SCM_CDR (y), slow, !move);
    }
}

Although it probably works there will be a lot of consing being done
slowing the algorithm, as said.
So I take back what I said earlier with tree cycle code added equal will be
slower.

/Stefan

On Sun, Sep 2, 2012 at 5:17 PM, David A. Wheeler <dwheeler@dwheeler.com>wrote:

> I said:
> > > I'd really like for there to be a common spec for Scheme with
> libraries, etc., and my hope is that R7RS will be that spec.
>
> Ian Price:
> > Call me a cynic, but if r6rs couldn't do that, then I don't see how r7rs
> > could be given that it actively avoids many important portability
> questions.
>
> Well, the cynics are often right :-).  But I think R7RS is intentionally
> much more conservative and R5RS-like.  In particular, it's *supposed* to be
> easy for an R5RS implementation to move to R7RS.  If it's easier to adopt,
> it's more likely to be adopted.
>
> Scheme is rediculously non-portable due to its lack of a *standard*
> library system.  If a standard for *that* could be widely adopted, many
> other portability problems would be drastically reduced.
>
> > But we all can dream...
>
> Indeed!
>
> --- David A. Wheeler
>
>

[-- Attachment #2: Type: text/html, Size: 2322 bytes --]

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Ludovic Courtès]

Hi,

Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:

> The cycle detection for a tree would probably look something like,

Tortoise-and-hare would have to be applied to arbitrary data structures, AIUI.

Ludo’.

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 911 bytes --]

No

I wanted to say that you create a linearisation of the search and apply
tourtouse hare on that. One can make that linearisation fast for list
traversals but expensive for deep trees. To note here is that if we had one
bit to spare for every cons representation we could do use that bit to mark
conses as been touched and abort the ordinary equal if we find a mark. For
x86-64 we have one such bit available which is cool. My sugestion is to
implemen those two versions and we well then not see a performans
degradation unless on 32bit platforms with treelike structures

Stefan
Den 3 sep 2012 00:08 skrev "Ludovic Courtès" <ludo@gnu.org>:
>
> Hi,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:
>
> > The cycle detection for a tree would probably look something like,
>
> Tortoise-and-hare would have to be applied to arbitrary data structures,
AIUI.
>
> Ludo’.
>
>

[-- Attachment #2: Type: text/html, Size: 1126 bytes --]

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Stefan Israelsson Tampe]

[-- Attachment #1.1: Type: text/plain, Size: 442 bytes --]

I actually implemented an algorithm to handle infinite trees that we could
use if we like.

Enjoy!




On Mon, Sep 3, 2012 at 12:07 AM, Ludovic Courtès <ludo@gnu.org> wrote:

> Hi,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:
>
> > The cycle detection for a tree would probably look something like,
>
> Tortoise-and-hare would have to be applied to arbitrary data structures,
> AIUI.
>
> Ludo’.
>
>
>

[-- Attachment #1.2: Type: text/html, Size: 786 bytes --]

[-- Attachment #2: cycle.scm --]
[-- Type: application/octet-stream, Size: 2661 bytes --]

(use-modules (ice-9 match))
(use-modules (srfi srfi-1))

(define (cycle-equal? x y)
  (define touch-x-car (make-hash-table))
  (define touch-x-cdr (make-hash-table))
  (define touch-y-car (make-hash-table))
  (define touch-y-cdr (make-hash-table))

  (define (marks-1 touch-1 touch-2 x)
    (match x
      (((and xx (_ . _)) . l)
       (let ((mark (hashq-ref touch-1 xx)))
         (if mark
             (begin
               (hashq-set! touch-1 xx '())
               (marks-2 touch-1 touch-2 x))
             (begin
               (hashq-set! touch-1 xx #t)
               (marks-1 touch-1 touch-2 xx)
               (marks-2 touch-1 touch-2 x)))))
      (_ (marks-2 touch-1 touch-2 x))))

  (define (marks-2 touch-1 touch-2 x)
    (match x
      ((_ . (and xx (_ . _)))
       (let ((mark (hashq-ref touch-2 xx)))
         (if mark
             (hashq-set! touch-2 xx '())
             (begin
               (hashq-set! touch-2 xx #t)
               (marks-1 touch-1 touch-2 xx)))))
      (_ 'ok)))

  (define-syntax-rule (reshape touch)
    (let ((new (make-hash-table)))
      (hash-for-each
       (lambda (k v)
         (if (null? v) (hashq-set! new k (make-hash-table))))
       touch)
      (set! touch new)))

  (define (tr y touch x)
    (let ((xx (hashq-ref touch x)))
      (and xx (if (hashq-ref xx y)
                  #t
                  (begin
                    (hashq-set! xx y #t)
                    #f)))))


  (define (c-equal-1 x y)
    (match x
      (((and xx (_ . _)) . _)
       (match y
         (((and yy (_ . _)) . _)
          (let ((mark-x (tr yy touch-x-car xx))
                (mark-y (tr xx touch-y-car yy)))
            (if (or mark-x mark-y)
                (c-equal-2 x y)
                (and
                 (c-equal-1 xx yy)
                 (c-equal-2 x  y)))))
         (_ #f)))

      ((xx . _)
       (match y
         ((yy . _)
          (and
           (equal? xx yy)
           (c-equal-2 x y)))
         (_ #f)))

      (_ (equal? x y))))
                    
  (define (c-equal-2 x y)
    (match x
      ((_ . (and xx (_ . _)))
       (match y
         ((_ . (and yy (_ . _)))
          (let ((mark-x (tr yy touch-x-cdr xx))
                (mark-y (tr xx touch-y-cdr yy)))
            (if (or mark-x mark-y)
                #t
                (c-equal-1 xx yy))))
         (_ #f)))
      
      ((_ . x)
       (match y
         ((_ . y)
          (equal? x y))
         (_ #f)))

      (_ (equal? x y))))

  (marks-1 touch-x-car touch-x-cdr x)
  (marks-1 touch-y-car touch-y-cdr y)
    
  (reshape touch-x-car)
  (reshape touch-x-cdr)
  (reshape touch-y-car)
  (reshape touch-y-cdr)

  (c-equal-1 x y))

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Ludovic Courtès]

Hi,

Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:

>   (define (c-equal-1 x y)
>     (match x
>       (((and xx (_ . _)) . _)

[...]

>       ((xx . _)

[...]

>       (_ (equal? x y))))

Doesn’t this mean that ‘cycle-equal?’ falls back to ‘equal?’ for
non-pairs?

Ludo’.

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 601 bytes --]

Yes, so it is no real replacement. For that we need yo hamdle vectors ,
structs etc. Eg cycles is only allowed in the pair part.

If we wan't this for the general case, please ask!

/stefan
Den 3 sep 2012 23:12 skrev "Ludovic Courtès" <ludo@gnu.org>:

> Hi,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:
>
> >   (define (c-equal-1 x y)
> >     (match x
> >       (((and xx (_ . _)) . _)
>
> [...]
>
> >       ((xx . _)
>
> [...]
>
> >       (_ (equal? x y))))
>
> Doesn’t this mean that ‘cycle-equal?’ falls back to ‘equal?’ for
> non-pairs?
>
> Ludo’.
>

[-- Attachment #2: Type: text/html, Size: 951 bytes --]

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Mark H Weaver]

On 09/03/2012 09:55 AM, Stefan Israelsson Tampe wrote:
> To note here is that if we had
> one bit to spare for every cons representation we could do use that bit
> to mark conses as been touched and abort the ordinary equal if we find a
> mark. For x86-64 we have one such bit available which is cool.

This trick of mutating bits in the conses fails badly in case of 
multiple threads, therefore we cannot use it.

     Mark

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 746 bytes --]

You are right! That will only work for one thread!

Remain to see how much the overhed there is to linearize the search and
use tourtoues - hare, should be much less overhead then using a map to
mark the objects though!

/Stefan

On Sat, Sep 8, 2012 at 6:56 PM, Mark H Weaver <mhw@netris.org> wrote:

> On 09/03/2012 09:55 AM, Stefan Israelsson Tampe wrote:
>
>> To note here is that if we had
>> one bit to spare for every cons representation we could do use that bit
>> to mark conses as been touched and abort the ordinary equal if we find a
>> mark. For x86-64 we have one such bit available which is cool.
>>
>
> This trick of mutating bits in the conses fails badly in case of multiple
> threads, therefore we cannot use it.
>
>     Mark
>

[-- Attachment #2: Type: text/html, Size: 1201 bytes --]

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Alex Shinn]

On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe
<stefan.itampe@gmail.com> wrote:
> You are right! That will only work for one thread!
>
> Remain to see how much the overhed there is to linearize the search and
> use tourtoues - hare, should be much less overhead then using a map to
> mark the objects though!

See http://srfi.schemers.org/srfi-85/srfi-85.html
for a common implementation approach.

The basic idea there is just to run equal? normally,
but keep a counter of how many objects have been
compared.  If the count gets too high, there is a
decent chance you have a cycle, and only then do
you switch to a more expensive approach.

You could of course use a modified hare and tortoise
with the same goal of just detecting when a cycle
has occurred and switching algorithms.  You only
need to do this on one of the data structures, since
if either is non-cyclic equal? will terminate naturally.
This would be slightly more overhead than a counter,
and probably require heap allocation to keep the
search path in memory, but it removes the need to
choose a good limit.  Small cycles will still be detected
right away, and very long straight lists won't switch
to the expensive algorithm.

I think trying to use two hares and two tortoises
to compare directly without a fallback algorithm
would be very harey.

-- 
Alex

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Mark H Weaver]

On 09/08/2012 09:35 PM, Alex Shinn wrote:
> On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe
> <stefan.itampe@gmail.com>  wrote:
>> You are right! That will only work for one thread!
>>
>> Remain to see how much the overhed there is to linearize the search and
>> use tourtoues - hare, should be much less overhead then using a map to
>> mark the objects though!
>
> See http://srfi.schemers.org/srfi-85/srfi-85.html
> for a common implementation approach.
>
> The basic idea there is just to run equal? normally,
> but keep a counter of how many objects have been
> compared.  If the count gets too high, there is a
> decent chance you have a cycle, and only then do
> you switch to a more expensive approach.
>
> You could of course use a modified hare and tortoise
> with the same goal of just detecting when a cycle
> has occurred and switching algorithms.  You only
> need to do this on one of the data structures, since
> if either is non-cyclic equal? will terminate naturally.
> This would be slightly more overhead than a counter,
> and probably require heap allocation to keep the
> search path in memory, but it removes the need to
> choose a good limit.  Small cycles will still be detected
> right away, and very long straight lists won't switch
> to the expensive algorithm.

Another option is to use the method described in "Efficient 
Nondestructive Equality Checking for Trees and Graphs" by Adams and Dybvig.

http://www.cs.indiana.edu/~dyb/pubs/equal.pdf

     Mark

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 2259 bytes --]

There is another interesting option that uses a hash to mark objects.

Keep a counter and for each new object check the counter, if it's 0
then check to see if the object have been visited before else register it!
then initiate the counter with (random N) elements.

If N equals 10 in guile scheme, then equal-with-cycle-detection is about
twice as slow
as an ordinary equal? on two equal?  1000 times long list.

The drawback is that for cyclic structures you get a positive probability
to wait for
a very long time but typically the expected waiting time should be less then
(N / 2) ** 2  = 25 in my test case. By increasing the N you will cause less
overhead
on the normal behavior but increase the cost for structures with cycles.

Anything unsound with this approach?

/Stefan


On Sun, Sep 9, 2012 at 3:35 AM, Alex Shinn <alexshinn@gmail.com> wrote:

> On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe
> <stefan.itampe@gmail.com> wrote:
> > You are right! That will only work for one thread!
> >
> > Remain to see how much the overhed there is to linearize the search and
> > use tourtoues - hare, should be much less overhead then using a map to
> > mark the objects though!
>
> See http://srfi.schemers.org/srfi-85/srfi-85.html
> for a common implementation approach.
>
> The basic idea there is just to run equal? normally,
> but keep a counter of how many objects have been
> compared.  If the count gets too high, there is a
> decent chance you have a cycle, and only then do
> you switch to a more expensive approach.
>
> You could of course use a modified hare and tortoise
> with the same goal of just detecting when a cycle
> has occurred and switching algorithms.  You only
> need to do this on one of the data structures, since
> if either is non-cyclic equal? will terminate naturally.
> This would be slightly more overhead than a counter,
> and probably require heap allocation to keep the
> search path in memory, but it removes the need to
> choose a good limit.  Small cycles will still be detected
> right away, and very long straight lists won't switch
> to the expensive algorithm.
>
> I think trying to use two hares and two tortoises
> to compare directly without a fallback algorithm
> would be very harey.
>
> --
> Alex
>

[-- Attachment #2: Type: text/html, Size: 2903 bytes --]

Re: Will guile support R7RS terminating "equal?" in the presence of cycle?

[William ML Leslie]

On 9 September 2012 13:41, Mark H Weaver <mhw@netris.org> wrote:
> Another option is to use the method described in "Efficient Nondestructive
> Equality Checking for Trees and Graphs" by Adams and Dybvig.
>
> http://www.cs.indiana.edu/~dyb/pubs/equal.pdf
>
>     Mark

The 'interleave' algorithm there looks excellent.  One possible
refinement: the 'stack' of items currently being examined is probably
a good hint as to which slots may have cycles, so it could be useful
to reify that stack, at least the portion of it that has not been
checked yet.

-- 
William Leslie