Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: Tail recursion to while iteration in 2 easy steps
Date: Wed, 02 Oct 2013 18:17:06 -0400
References: <mailman.571.1380663065.18130.python-list@python.org> <87had0axxy.fsf@dpt-info.u-strasbg.fr>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.0
In-Reply-To: <87had0axxy.fsf@dpt-info.u-strasbg.fr>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.654.1380752253.18130.python-list@python.org>
Lines: 43
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:55384

On 10/2/2013 4:17 AM, Alain Ketterlin wrote:
> Terry Reedy <tjreedy@udel.edu> writes:
>
>> Part of the reason that Python does not do tail call optimization is
>> that turning tail recursion into while iteration is almost trivial,
>> once you know the secret of the two easy steps. Here it is.
>>
>> Assume that you have already done the work of turning a body recursive
>> ('not tail recursive') form like
>>
>> def fact(n): return 1 if n <= 1 else n * fact(n-1)

As I said in response to randomxxx, even this 0th step (recursion to 
recursion transformation) requires assumptions or carefully reasoning 
about the properties of the operations.

>> into a tail recursion like
> [...]
>
> How do know that either "<=" or "*" didn't rebind the name "fact" to
> something else? I think that's the main reason why python cannot apply
> any procedural optimization (even things like inlining are impossible,
> or possible only under very conservative assumption, that make it
> worthless).
>
> -- Alain.
>
> P/S: don't take me wrong; your explanation is excellent (and very useful
> to python programmers). What I say is that it relies on assumptions that
> do not apply to python.

Program transformations (usually intended to be optimizations), whether 
automatic or manual, are infamous for being buggy in not always being 
correct because of hidden assumptions that are not always true.

CPython core developers have be very conservative about what 
tranformations they put into the compiler. (1,2,3) can always be 
compiled as a constant, and so it is. [1,2,3] might or might not be a 
constant, depending on the context, and no attempt is made to analyze that.

-- 
Terry Jan Reedy