Tail recursion to while iteration in 2 easy steps
Terry Reedy
tjreedy at udel.edu
Wed Oct 2 23:06:37 EDT 2013
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
More information about the Python-list
mailing list