[sawfish] Re: `position' in rep...?

[Eli Barzilay <eli barzilay org>]

9 hours ago, Jeremy Hankins wrote:
> 
> I wrote a version of the position function that would work with
> circular lists, since the other one will start an infinite loop if
> you give it a circular list.

That code is broken, as Timo points out.  See correct version below.


> I've included the function below, but it turns out that infinite
> lists are only semi-supported -- calling length, or even evaluating
> them in sawfish-client, causes an infinite loop.  According to the
> docs (where I should have looked first) only cons, car, cdr, rplaca,
> rplacd, nth, and nthcdr can be used on circular lists.

That's a bad state.  It means that doing some naive experimenting can
easily get your WM to die.  (And dynamic experimenting is one of
sawfish's great advantages.)


> In short: I don't know that it's worth it to fix it elsewhere, even
> if we end up staying with rep, [...]

The repl getting hung up is especially disturbing, and shouldn't be
hard to fix.  Other functions can trip into an infinite loop but at
least they're easier to break.


40 minutes ago, Timo Korvola wrote:
> 
> Many functions do. Basically anything that loops through the
> elements of a list will get stuck.

There's no reason to let them get stuck.  In Racket, as in some other
Scheme implementations, `list?' is implemented correctly and will
return #f when given a cyclic list.  (This is specified in R5RS, which
even gives this example:

 (let ((x (list 'a)))
   (set-cdr! x x)
   (list? x))         ==>  #f

)  In such implementations there's an easy way to deal with cyclic
lists in a way that avoids infinite loops -- for example:

  (define (position item l)
    (unless (list? l) (error "bleh"))
    ... usual code, ignore infinite lists ...)

But of course dealing with potentially infinite lists is not much
harder.


> Your fix does not work either if the list cycles back not to its
> head but some later element.

Right -- checking if you get back to the beginning isn't going to
work.  The common way to deal with infinite lists is the "hare and
tortoise" method: iterate with two pointers, one advancing at twice
the speed of the other.  Here's a working implementation of `position'
using this:

  (define (position item l)
    (let loop ((slow l) (l l) (i 0))
      (cond ((not (consp l)) #f)
            ((equal item (car l)) i)
            (#t (let ((l (cdr l)) (i (1+ i)))
                  (cond ((not (consp l)) #f)
                        ((equal item (car l)) i)
                        ((eq l slow) #f)
                        (#t (loop (cdr slow) (cdr l) (1+ i)))))))))

This follows the common pattern for this method: the usual code is
written twice, and the slow pointer is checked and advanced once per
iteration.  Implementing `length' etc like this is easy, and it would
be nice if cyclic lists won't get basic things like that to crash
sawfish.

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!