Tail recursion to while iteration in 2 easy steps

[Terry Reedy]

On 10/2/2013 9:24 PM, Steven D'Aprano wrote:
> On Wed, 02 Oct 2013 18:17:06 -0400, Terry Reedy wrote:
>
>> 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.
>
> The first sentence of this is correct. The next two don't quite make
> sense to me, since I don't understand what you mean by "constant" in this
> context. I *think* you might be referring to the LOAD_CONST byte-code,
> which in Python 3.3 understands tuples like (1, 2, 3), but not lists. So
> a literal (1, 2, 3) gets created at compile-time with a single LOAD_CONST
> call:

Answered in another response.

> py> from dis import dis
> py> dis(compile("x = (1, 2, 3)", '', 'exec'))
>    1           0 LOAD_CONST               4 ((1, 2, 3))
>                3 STORE_NAME               0 (x)
>                6 LOAD_CONST               3 (None)
>                9 RETURN_VALUE
>
>
> while a literal [1, 2, 3] does not:
>
>
> py> dis(compile("x = [1, 2, 3]", '', 'exec'))
>    1           0 LOAD_CONST               0 (1)
>                3 LOAD_CONST               1 (2)
>                6 LOAD_CONST               2 (3)
>                9 BUILD_LIST               3
>               12 STORE_NAME               0 (x)
>               15 LOAD_CONST               3 (None)
>               18 RETURN_VALUE
>
>
> But I don't think this is a necessary language limitation. Both (1, 2, 3)
> and [1, 2, 3] are known at compile time: the first cannot be anything
> other than a tuple of three ints, and the second a list of three ints.

Given introspectable code objects, the list must be built as runtime 
from the three ints to guarantee that.

> seems to me that an implementation might provide a single byte-code to
> build list literals, perhaps even LOAD_CONST itself.

There are list displays, but not list literals. The distinction is 
important. The BUILD_LIST byte code is used above.

LOAD_CONST                     4 (1,2,3)
BUILD_LIST_FROM_TUPLE_CONSTANT

would be possible for the special case but hardly worthwhile.

 > The byte-codes used by the Python VM are not part of the language 
definition,

which is why I specified CPython as the context, with 'current' as the 
default.

> and are subject to change without warning.
>
> And in fact, if we go all the way back to Python 1.5, even tuple literals
> weren't handled by a single byte-code, they were assembled at runtime
> like lists still are:
>
> [steve at ando ~]$ python1.5
> Python 1.5.2 (#1, Aug 27 2012, 09:09:18)  [GCC 4.1.2 20080704 (Red Hat
> 4.1.2-52)] on linux2
> Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
>>>> from dis import dis
>>>> dis(compile("x = (1, 2, 3)", '', 'exec'))
>            0 SET_LINENO          0
>
>            3 SET_LINENO          1
>            6 LOAD_CONST          0 (1)
>            9 LOAD_CONST          1 (2)
>           12 LOAD_CONST          2 (3)
>           15 BUILD_TUPLE         3
>           18 STORE_NAME          0 (x)
>           21 LOAD_CONST          3 (None)
>           24 RETURN_VALUE

Extending pre-complilation to tuples with nested constant tuples is even 
more recent. I 3.3.2, we have

 >>> f.__code__.co_consts
(None, 1, 2, 3, (1, 2, 3))
 >>> def f(): return ((1,2,3), (4,5))

 >>> f.__code__.co_consts
(None, 1, 2, 3, 4, 5, (1, 2, 3), (4, 5), ((1, 2, 3), (4, 5)))

but I am sure if you go back you can find versions that lack the last item.

--
The language is as conservative about mandating optimizations as the 
implementation is about doing them. I consider making None, False, True 
be un-rebindable keynames to be an optimization. This is not even for 
the other singletons Ellipsis and NotImplemented. I cannot think of too 
much else. Tuple constant optimization is not mandated. It would be as 
out of character for the language to require tail-recursion optimization 
as for CPython to do it.

-- 
Terry Jan Reedy