Opened 10 years ago

Closed 10 years ago

#10788 closed defect (fixed)

Maximum recursion depth exceeded in the computation of return words

Reported by: slabbe Owned by: slabbe
Priority: major Milestone: sage-4.7
Component: combinatorics Keywords:
Cc: jleroy Merged in: sage-4.7.alpha2
Authors: Sébastien Labbé Reviewers: Julien Leroy
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

---------- 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

Attachments (1)

trac_10788_return_words-sl.patch (10.4 KB) - added by slabbe 10 years ago.
Applies over sage-4.6.1

Download all attachments as: .zip

Change History (8)

comment:1 follow-up: Changed 10 years ago by slabbe

  • Cc jleroy added
  • Status changed from new to needs_review

This should fix the problem. Needs review.

comment:2 in reply to: ↑ 1 ; follow-up: Changed 10 years ago by 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?
  1. 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

comment:3 in reply to: ↑ 2 Changed 10 years ago by 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.

  1. 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.

Changed 10 years ago by slabbe

Applies over sage-4.6.1

comment:4 follow-up: Changed 10 years ago by slabbe

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

comment:5 in reply to: ↑ 4 Changed 10 years ago by jleroy

  • Status changed from needs_review to positive_review

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!

comment:6 Changed 10 years ago by jdemeyer

  • Authors set to Sébastien Labbé
  • Milestone changed from sage-4.6.2 to sage-4.7
  • Reviewers set to Julien Leroy

comment:7 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.