Re: Will guile support R7RS terminating equal? in the presence of cycle?
On 9 September 2012 13:41, Mark H Weaver m...@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
Re: Will guile support R7RS terminating equal? in the presence of cycle?
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 alexsh...@gmail.com wrote: On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe stefan.ita...@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?
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?
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 m...@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
Re: Will guile support R7RS terminating equal? in the presence of cycle?
On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe stefan.ita...@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?
On 09/08/2012 09:35 PM, Alex Shinn wrote: On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe stefan.ita...@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?
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 l...@gnu.org: Hi, Stefan Israelsson Tampe stefan.ita...@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?
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 l...@gnu.org wrote: Hi, Stefan Israelsson Tampe stefan.ita...@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’. cycle.scm Description: Binary data
Re: Will guile support R7RS terminating equal? in the presence of cycle?
Hi, Stefan Israelsson Tampe stefan.ita...@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?
David A. Wheeler dwhee...@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?
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?
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);
ccx
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 dwhee...@dwheeler.comwrote:
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?
Hi, Stefan Israelsson Tampe stefan.ita...@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’.
