[Python-ideas] FW: Idea: Compressing the stack on the fly

[M.-A. Lemburg]

On 12.09.2013 09:03, Joshua Landau wrote:
> On 12 September 2013 07:59, M.-A. Lemburg <mal at egenix.com> wrote:
>> On 12.09.2013 06:29, Joshua Landau wrote:
>>> Does anyone actually write recursive Python code where the recursion
>>> in a significant bottleneck? The only such code I can think of is
>>> either for a tree, in which case stack depth is irrelevant, or bad
>>> code.
>>
>> Any kind of backtracking algorithm will need recursion or a separate
>> stack data structure to keep track of the various decisions made
>> up to a certain point on the path.
>>
>> The C stack is rather limited in size, so a recursive parser can
>> easily blow up if it uses the C stack alone for managing
>> backtracking.
> 
> What sort of algorithm would backtrack that many times? I doubt a
> parser would and I can't think of anything worse ATM.

Oh, that's easy. It just depends on the given data set that you're
working on and how often you have to branch when working on it.

http://en.wikipedia.org/wiki/Backtracking lists a few problems.

Here's a regular expression example that would blow the stack,
if the re module were still using it (it was fixed in 2003 to
no longer do):

    re.match('(.*a|.*b|x)+', 'x' * 100000)

The expression still uses exponential time, though.

With Python 2.3, you see the stack limit error:

Python 2.3.5 (#1, Aug 24 2011, 15:52:42)
[GCC 4.5.0 20100604 [gcc-4_5-branch revision 160292]] on linux2
Type "help", "copyright", "credits" or "license" for more information.

>>> import re
>>> re.match('(.*a|.*b|x)+', 'x' * 100000)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "/usr/local/python-2.3-ucs2/lib/python2.3/sre.py", line 132, in match
    return _compile(pattern, flags).match(string)
RuntimeError: maximum recursion limit exceeded

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Sep 12 2013)
>>> Python Projects, Consulting and Support ...   http://www.egenix.com/
>>> mxODBC.Zope/Plone.Database.Adapter ...       http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________
2013-09-11: Released eGenix PyRun 1.3.0 ...       http://egenix.com/go49
2013-09-04: Released eGenix pyOpenSSL 0.13.2 ...  http://egenix.com/go48
2013-09-20: PyCon UK 2013, Coventry, UK ...                 8 days to go

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/