newbie: comparing mutually recursive lists 
Author Message
 newbie: comparing mutually recursive lists

If I create a pair of mutually recursive lists like

        a,b=[],[]
        a.append(b)
        b.append(a)

and try to compare them I get a segmentation fault.  I'm using the
version of python that comes with Debian 2.1 (Python 1.5.1 (#1, Dec 17
1998, 20:58:15)  [GCC 2.7.2.3] on linux2 ).  Does anyone know if this
problem has been fixed?  Failing that, can anyone suggest a workaround?

-andy

/**

 Andrew Hutcheson
 31 Coburn Rd.
 Weston MA 02493

 781.891.8046

+++ Divide By Cucumber Error. Please Reinstall Universe And Reboot +++
        -- (Terry Pratchett, Hogfather)

**/



Sun, 17 Mar 2002 03:00:00 GMT  
 newbie: comparing mutually recursive lists


Quote:
>If I create a pair of mutually recursive lists like

>    a,b=[],[]
>    a.append(b)
>    b.append(a)

>and try to compare them I get a segmentation fault.  I'm using the
>version of Python that comes with Debian 2.1 (Python 1.5.1 (#1, Dec 17
>1998, 20:58:15)  [GCC 2.7.2.3] on linux2 ).  Does anyone know if this
>problem has been fixed?  Failing that, can anyone suggest a workaround?

FYI, I get it on 1.5.2 on Solaris 2.5.1.
--

Androgynous poly {*filter*} vanilla {*filter*} het    <*>       http://www.*-*-*.com/
Hugs and backrubs -- I break Rule 6  (if you want to know, do some research)



Sun, 17 Mar 2002 03:00:00 GMT  
 newbie: comparing mutually recursive lists
[Andrew Hutcheson]

Quote:
> If I create a pair of mutually recursive lists like

>    a,b=[],[]
>    a.append(b)
>    b.append(a)

> and try to compare them I get a segmentation fault.

It's caused by a C stack overflow (unbounded recursion in the interpreter).

Quote:
> I'm using the version of Python that comes with Debian 2.1 (Python 1.5.1
> (#1, Dec 17 1998, 20:58:15)  [GCC 2.7.2.3] on linux2 ).

All versions of Python suffer this.

Quote:
> Does anyone know if this problem has been fixed?

Yes:  no <wink>.

Quote:
> Failing that, can anyone suggest a workaround?

The easiest is-- honest --not to compare lists with cycles.  Note that
mutual recursion isn't necessary to provoke this; e.g.,

    a = []
    b = []
    a.append(a)
    b.append(b)

is just as bad.

Your other choice is to implement your own list comparison, that detects and
keeps track of cycles; see Lib/copy.py for the kind of machinery that's
needed.  This is expensive all the time, which is why the interpreter
doesn't do it.  If it's ever fixed in the language, it's more likely that
this kind of comparison will be declared illegal, and the implementation
will catch it with a much cheaper recursion counter (raising an exception if
the comparison recursion gets "too deep").  This wasn't done before because,
until recently, it was impossible for a comparison operator to raise an
exception (due to obscurities of the implementation).

if-real-lists-had-cycles-i'd-never-stop-shopping-ly y'rs  - tim



Sun, 17 Mar 2002 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Mutually recursive functions in FORTH

2. mutually recursive words

3. example of mutually recursive functions

4. Mutually Recursive Types [was pkg parts, etc.]

5. Readable mutually recursive data structures?

6. Mutually recursive nested functions -- are easy

7. How to make a mutually recursive macro and function

8. NEWBIE QUESTIION: Comparing Lists in Python

9. SML newbie question: recursive type/datatype combination

10. newbie Haskell question : non-recursive iteration?

11. Newbie - Recursive calls in class objects...

12. recursive function that returns true/false (newbie stuff)

 

 
Powered by phpBB® Forum Software