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
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,
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.
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 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
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
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
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
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’.
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
l...@gnu.org (Ludovic Courtès) writes:
Hi Stefan!
stefan.ita...@gmail.com stefan.ita...@gmail.com skribis:
1 I don't think the current equal? Will need to change, but
Another one that under rnr7 will be coded and used with the
Symbol equal? In that module. Hence no problems.
Yes, of
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
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)))
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’.
on circular lists and
Also there is probably enough reference information to code this in due time.
Cheers!
Stefan
Skickat från min HTC
- Reply message -
Från: l...@gnu.org (Ludovic Courtès
Till: guile-devel@gnu.org
Rubrik: Will guile support R7RS terminating equal? in the presence of cycle
Hi Stefan!
stefan.ita...@gmail.com stefan.ita...@gmail.com skribis:
1 I don't think the current equal? Will need to change, but
Another one that under rnr7 will be coded and used with the
Symbol equal? In that module. Hence no problems.
Yes, of course.
2 The guile hackers are able enough
Typed Guile? Did I miss something? :-)
https://gitorious.org/typed-guile
It's a type system implemented using guile-log!
By the way, I do not think the overhead is that dramatic. I guess that
guile's equal would be any slower with this feature added. you typically
does a circularity check via
Stefan Israelsson Tampe stefan.ita...@gmail.com skribis:
https://gitorious.org/typed-guile
It's a type system implemented using guile-log!
Woow, this is crazy. I wish we could converge eventually...
Ludo’.
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
19 matches
Mail list logo
