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

[Stefan Israelsson Tampe]

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 <address@hidden> 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