Maximum recursion depth exceeded in the computation of return words

[slabbe]

---------- Forwarded message ----------  
From: Julien Leroy
Date: 2011/1/19
To: Sébastien Labbé 

Voici quelques exemples des comportements bizarres que j'ai pu observer.

A bientôt,
Julien

sage: TM = words.ThueMorseWord('01')[:1000]
sage: TM
word: 0110100110010110100101100110100110010110...
sage: TM.return_words(Word('0'))
set([word: 0, word: 01, word: 011])


sage: TM = words.ThueMorseWord('01')[:10000]
sage: TM
word: 0110100110010110100101100110100110010110...
sage: TM.return_words(Word('0'))
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded while calling a Python object




sage: f = WordMorphism('a->ab,b->ba')
sage: tm = f.fixed_point('a')[:1000]
sage: tm
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: tm.return_words(Word('a'))
set([word: a, word: ab, word: abb])


sage: tm = f.fixed_point('a')[:10000]
sage: tm
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: tm.return_words(Word('a'))
Traceback (most recent call last):
...
IndexError: string index out of range

[slabbe]

This should fix the problem. Needs review.

[jleroy]

Replying to slabbe:

This should fix the problem. Needs review.

Hi Seb,

All test passed and it seems to fix the problem, indeed. However I have a few questions that probably come from the fact that I still don't know much about sage development.

1. In most of the things that you added or modified in that patch, the functions do not contain any tests. Is there any reason for that?

2. You added some "@cached_method". If I remember well, the cached_method means that what follows does not appear in the list of functions given by the "tab completion", doesn't it? However, those functions (for instance the "good_suffix_table" at line 816) do appear in that list. Am I wrong about the cached_method?

Julien

[slabbe]

1. In most of the things that you added or modified in that patch, the functions do not contain any tests. Is there any reason for that?

That's because tests were already there. In many cases, I just changed the code and kept the documentation and doctests as is.

That being said, it is true that I didn't add any tests for the problem mentionned in this ticket. I am going to add one right now and re-upload the patch.

2. You added some "@cached_method". If I remember well, the cached_method means that what follows does not appear in the list of functions given by the "tab completion", doesn't it? However, those functions (for instance the "good_suffix_table" at line 816) do appear in that list. Am I wrong about the cached_method?

Cached method do and should appear in the tab completion list. A cached method means that it remembers its result instead of computing it everytime. En français, on parle de mémoization:

 http://fr.wikipedia.org/wiki/M%C3%A9moization

In our case, the good_suffix_table is consulted everytime we search for a factor. So for searching the return words of a factor, it might be a good speedup to cache (mémoiser) the good suffix table.

[slabbe]

Applies over sage-4.6.1

[slabbe]

I just refreshed the patch. Needs review! If you have any question Julien, just ask me!

[jleroy]

Replying to slabbe:

I just refreshed the patch. Needs review! If you have any question Julien, just ask me!

Great! All test passed and the problem is fixed. Nice job and thank you for your explicatiosn!