Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #55239 > unrolled thread

Tail recursion to while iteration in 2 easy steps

Back to article view | Back to comp.lang.python

Contents

  Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-01 17:30 -0400
    Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-01 22:16 -0700
      Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:23 +0200
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-02 06:29 -0700
      Re: Tail recursion to while iteration in 2 easy steps Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-03 22:57 +0530
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-04 03:52 -0700
    Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:17 +0200
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 11:59 -0700
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 14:05 -0700
        Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-04 11:49 +0200
          Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 10:51 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 18:32 -0400
            Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-07 19:15 +0200
              Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-07 19:57 +0200
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:56 +0200
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 12:49 +0300
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-07 16:42 -0400
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:19 -0400
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:41 +0200
              Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-07 22:39 +0100
              Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 18:03 -0400
              Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 15:47 -0700
                Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-07 23:50 +0000
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:24 -0700
                    Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 20:17 -0700
                      Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 10:46 +0530
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 22:44 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-10-08 07:43 +0100
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:31 +0530
                            Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-08 06:33 -0700
                        Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve@pearwood.info> - 2013-10-08 07:50 +0000
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:16 +0530
                            Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 13:11 +0000
                              Re: Formal-ity and the Church-Turing thesis Robert Day <robertkday@gmail.com> - 2013-10-08 14:25 +0100
                              Re: Formal-ity and the Church-Turing thesis Chris Angelico <rosuav@gmail.com> - 2013-10-09 08:36 +1100
                      Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 22:19 -0700
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 23:01 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-08 10:39 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:16 -0700
                    Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 02:36 +0000
                      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:27 -0700
                        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve@pearwood.info> - 2013-10-08 09:22 +0000
                          Re: Tail recursion to while iteration in 2 easy steps Charles Hixson <charleshixsn@earthlink.net> - 2013-10-09 15:45 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:46 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:25 +0300
                  Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:18 +0200
                Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:45 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:34 -0700
      Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 18:17 -0400
        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 01:24 +0000
          Re: Tail recursion to while iteration in 2 easy steps Dave Angel <davea@davea.name> - 2013-10-03 01:39 +0000
          Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-03 02:46 +0100
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 02:34 +0000
              Re: Tail recursion to while iteration in 2 easy steps Chris Angelico <rosuav@gmail.com> - 2013-10-03 14:14 +1000
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:16 -0400
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-03 15:04 -0400
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 22:41 -0400
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 01:30 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 23:06 -0400
          Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:14 -0400
          Literal syntax for frozenset, frozendict (was: Tail recursion to while iteration in 2 easy steps) Ben Finney <ben+python@benfinney.id.au> - 2013-10-04 10:18 +1000
          Re: Literal syntax for frozenset, frozendict Ethan Furman <ethan@stoneleaf.us> - 2013-10-03 18:31 -0700
      Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-03 14:52 +0000
        Re: Tail recursion to while iteration in 2 easy steps Neil Cerutti <neilc@norwich.edu> - 2013-10-03 16:03 +0000
          Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 10:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:41 -0600
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:46 -0600
              Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 11:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-04 14:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 17:14 -0400
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-05 09:39 +0200
            Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:27 -0400
              Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:43 +0200

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#56344

>>> But even putting that aside, even if somebody wrote such a description,
>>> it would be reductionism gone mad. What possible light on the problem
>>> would be shined by a long, long list of machine code operations, even
>>> if written using assembly mnemonics?
>>
>> Only that you've got a consistent, stable (and therefore, formalizable)
>> translation from your language to the machine.
>
> You are mistaken to think that there is a single, one-to-one, mapping
> between high-level code and machine code.

It's not mistaken.  Given a stable and formalized language definition,
there should only be continued optimization of the lexical and
procedural constructs into better machine code. In the case of an
"interpreted" language like Python (which I'll define as a language
which includes a layer of indirection between the user and the
machine, encouraging the nice benefits of interactivity), such
optimization isn't really apropos, because it's not the purpose of
python to be optimal to the machine as much as "optimal to the
programmer".  In any case, while such optimization can continue over
time, they generally create new compiler releases to indicate such
changes.  The one-to-one mapping is held by the compiler.

Such determinism *defines* the machine, otherwise you might as well
get rid of the notion of computer *science*.  All else is error, akin
to cosmic rays or magic.  Unless the source code changes, all else
remaining equal, the machine code is supposed to be the same, no
matter how many times it is compiled.

>[Only if you use the exact source, compiler, switches, etc]] will the output be the same.
> And even that is not guaranteed.

Oh, and what would cause such non-determinism?

> Take, for example, the single high-level operation:
>
> sort(alist)
>
> What machine code will be executed? Obviously that will depend on the
> sort algorithm used. There are *dozens*. Here are just a few:

Well, since you didn't specify your programming language, you're then
merely stating an English construct.  As such, there can be no single
mapping from English into the machine, which is why there are so many
different languages and experiments that map your [English] concepts
into source code.

> Now sorting is pretty high level, but the same principle applies to even
> simple operations like "multiply two numbers". There are often multiple
> algorithms for performing the operation, and even a single algorithm can
> often be implemented in slightly different ways. Expecting all compilers
> to generate the same machine code is simply naive.

You are both over-simplifying and complexifying things at once.  Pick one.

-- 
MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#56376

On Mon, 07 Oct 2013 20:27:13 -0700, Mark Janssen wrote:

>>>> But even putting that aside, even if somebody wrote such a
>>>> description, it would be reductionism gone mad. What possible light
>>>> on the problem would be shined by a long, long list of machine code
>>>> operations, even if written using assembly mnemonics?
>>>
>>> Only that you've got a consistent, stable (and therefore,
>>> formalizable) translation from your language to the machine.
>>
>> You are mistaken to think that there is a single, one-to-one, mapping
>> between high-level code and machine code.
> 
> It's not mistaken.

I'm afraid it is. Reality trumps your theory. gcc, clang, Microsoft 
Visual Studio, and all the many, many other C compilers do not generate 
identical machine code even when targeting the same hardware. This is a 
fact. It's not even the case that there is One True Way to implement a 
particular program on a given hardware device and compilers merely are 
buggy for doing something else. There are often different ways to 
implement it which are equally good, the only difference being personal 
preference.


> Given a stable and formalized language definition,
> there should only be continued optimization of the lexical and
> procedural constructs into better machine code.

Better than what? "Continued" optimization? When you say "lexical and 
procedural constructs", do you mean "source code"?


> In the case of an
> "interpreted" language like Python (which I'll define as a language
> which includes a layer of indirection between the user and the machine,

Irrelevant. In the case of Python, there is a machine. The fact that it 
is a VM rather than a physical machine is irrelevant. A machine is a 
machine -- we could be talking about a Lisp Machine, a Forth Machine, a 
x86 processor, an Motorola 68000, an Atom processor, one of those old 
Russian mainframes that used three-state trits instead of two-state bits, 
or even Babbage's Analytical Engine. 

Besides, most modern CPUs don't execute machine code directly, they run 
the machine code in a virtual machine implemented in hardware. So the 
difference between Python and x86 machine code is just a matter of degree.



> encouraging the nice benefits of interactivity), such optimization isn't
> really apropos, because it's not the purpose of python to be optimal to
> the machine as much as "optimal to the programmer".  In any case, while
> such optimization can continue over time, they generally create new
> compiler releases to indicate such changes.  The one-to-one mapping is
> held by the compiler.
> 
> Such determinism *defines* the machine, otherwise you might as well get
> rid of the notion of computer *science*.  All else is error, akin to
> cosmic rays or magic.  Unless the source code changes, all else
> remaining equal, the machine code is supposed to be the same, no matter
> how many times it is compiled.

That is akin to saying that there is *only one* way to measure the speed 
of light (say), standing in exactly the same place, using exactly the 
same equipment, using precisely the same measurement techniques, and that 
if we allow alternative methods for measuring the speed of light, physics 
is no longer a science.


>>[Only if you use the exact source, compiler, switches, etc]] will the
>>output be the same.
>> And even that is not guaranteed.
> 
> Oh, and what would cause such non-determinism?

The compiler-writer, of course. A compiler is software, and is written by 
a person, who can program it to do anything the writer wants. If the 
writer wants the compiler to be non-deterministic, it can be.

Some viruses use a similar technique to try to avoid virus scanners. They 
encrypt the payload, which is functionally equivalent to randomizing it 
(except it can be reversed if you have the key) so as to defeat virus 
scanners.

A more whimsical example: perhaps a mischievous compiler writer included 
something like this in her compiler:


when compiling integer multiplication, INT * INT:
  if today is Tuesday:
    emit machine code that does multiplication using repeated addition
  otherwise:
    emit machine code that does multiplication using ADD and SHIFT


Both implementations of multiplication are perfectly valid. There may be 
a performance difference, or there may not be. Since no sensible 
programming language is going to specify the *detailed* machine code 
implementation of its high-level operations, such a mischievous compiler 
would still be valid.


>> Take, for example, the single high-level operation:
>>
>> sort(alist)
>>
>> What machine code will be executed? Obviously that will depend on the
>> sort algorithm used. There are *dozens*. Here are just a few:
> 
> Well, since you didn't specify your programming language, you're then
> merely stating an English construct.

What difference does it make? But if it will make you feel better, I'm 
specifying Hypertalk. You've probably never heard of it, but regardless, 
it exists, and it has a sort command, and the high-level language does 
not specify which of many sort algorithms is to be used.



> As such, there can be no single
> mapping from English into the machine, which is why there are so many
> different languages and experiments that map your [English] concepts
> into source code.

And there is no single mapping from <INSERT **ANY** HIGH-LEVEL 
PROGRAMMING LANGUAGE HERE> source code to machine code either.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#56520

On 10/08/2013 02:22 AM, Steven D'Aprano wrote:
> On Mon, 07 Oct 2013 20:27:13 -0700, Mark Janssen wrote:
>
>>>>> But even putting that aside, even if somebody wrote such a
>>>>> description, it would be reductionism gone mad. What possible light
>>>>> on the problem would be shined by a long, long list of machine code
>>>>> operations, even if written using assembly mnemonics?
>>>> Only that you've got a consistent, stable (and therefore,
>>>> formalizable) translation from your language to the machine.
>>> You are mistaken to think that there is a single, one-to-one, mapping
>>> between high-level code and machine code.
>> It's not mistaken.
> I'm afraid it is. Reality trumps your theory. gcc, clang, Microsoft
> Visual Studio, and all the many, many other C compilers do not generate
> identical machine code even when targeting the same hardware. This is a
> fact. It's not even the case that there is One True Way to implement a
> particular program on a given hardware device and compilers merely are
> buggy for doing something else. There are often different ways to
> implement it which are equally good, the only difference being personal
> preference.
>
>
>> Given a stable and formalized language definition,
>> there should only be continued optimization of the lexical and
>> procedural constructs into better machine code.
> Better than what? "Continued" optimization? When you say "lexical and
> procedural constructs", do you mean "source code"?
>
>
>> In the case of an
>> "interpreted" language like Python (which I'll define as a language
>> which includes a layer of indirection between the user and the machine,
> Irrelevant. In the case of Python, there is a machine. The fact that it
> is a VM rather than a physical machine is irrelevant. A machine is a
> machine -- we could be talking about a Lisp Machine, a Forth Machine, a
> x86 processor, an Motorola 68000, an Atom processor, one of those old
> Russian mainframes that used three-state trits instead of two-state bits,
> or even Babbage's Analytical Engine.
>
> Besides, most modern CPUs don't execute machine code directly, they run
> the machine code in a virtual machine implemented in hardware. So the
> difference between Python and x86 machine code is just a matter of degree.
>
>
>
>> encouraging the nice benefits of interactivity), such optimization isn't
>> really apropos, because it's not the purpose of python to be optimal to
>> the machine as much as "optimal to the programmer".  In any case, while
>> such optimization can continue over time, they generally create new
>> compiler releases to indicate such changes.  The one-to-one mapping is
>> held by the compiler.
>>
>> Such determinism *defines* the machine, otherwise you might as well get
>> rid of the notion of computer *science*.  All else is error, akin to
>> cosmic rays or magic.  Unless the source code changes, all else
>> remaining equal, the machine code is supposed to be the same, no matter
>> how many times it is compiled.
> That is akin to saying that there is *only one* way to measure the speed
> of light (say), standing in exactly the same place, using exactly the
> same equipment, using precisely the same measurement techniques, and that
> if we allow alternative methods for measuring the speed of light, physics
> is no longer a science.
>
>
>>> [Only if you use the exact source, compiler, switches, etc]] will the
>>> output be the same.
>>> And even that is not guaranteed.
>> Oh, and what would cause such non-determinism?
> The compiler-writer, of course. A compiler is software, and is written by
> a person, who can program it to do anything the writer wants. If the
> writer wants the compiler to be non-deterministic, it can be.
>
> Some viruses use a similar technique to try to avoid virus scanners. They
> encrypt the payload, which is functionally equivalent to randomizing it
> (except it can be reversed if you have the key) so as to defeat virus
> scanners.
>
> A more whimsical example: perhaps a mischievous compiler writer included
> something like this in her compiler:
>
>
> when compiling integer multiplication, INT * INT:
>    if today is Tuesday:
>      emit machine code that does multiplication using repeated addition
>    otherwise:
>      emit machine code that does multiplication using ADD and SHIFT
>
>
> Both implementations of multiplication are perfectly valid. There may be
> a performance difference, or there may not be. Since no sensible
> programming language is going to specify the *detailed* machine code
> implementation of its high-level operations, such a mischievous compiler
> would still be valid.
>
>
>>> Take, for example, the single high-level operation:
>>>
>>> sort(alist)
>>>
>>> What machine code will be executed? Obviously that will depend on the
>>> sort algorithm used. There are *dozens*. Here are just a few:
>> Well, since you didn't specify your programming language, you're then
>> merely stating an English construct.
> What difference does it make? But if it will make you feel better, I'm
> specifying Hypertalk. You've probably never heard of it, but regardless,
> it exists, and it has a sort command, and the high-level language does
> not specify which of many sort algorithms is to be used.
>
>
>
>> As such, there can be no single
>> mapping from English into the machine, which is why there are so many
>> different languages and experiments that map your [English] concepts
>> into source code.
> And there is no single mapping from <INSERT **ANY** HIGH-LEVEL
> PROGRAMMING LANGUAGE HERE> source code to machine code either.
I would assert that Python is not inherently a virtual machine 
language.  Originally, IIRC, it was believed that LISP couldn't be 
compiled.  Also, you could implement that virtual machine as a hardware 
machine.  (Also, of course, on modern hardware assembly language is run 
on a virtual machine, implemented by an underneath microcode layer.)

You can reasonably say that an implementation of Python is done in terms 
of a virtual machine.  (Usually I don't bother about this kind of 
nit-pick, but in this discussion it seems apropos.)

-- 
Charles Hixson

[toc] | [prev] | [next] | [standalone]

#56342

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:

> Far more useful would be a high-level description of Scheme's programming 
> model. If names can be rebound on the fly, how does Scheme even tell 
> whether something is a recursive call or not?

Maybe it doesn't have to tell. If you do tail call optimization there is no need to do tail recursion optimization.
-- 
Piet van Oostrum <piet@vanoostrum.org>
WWW: http://pietvanoostrum.com/
PGP key: [8DAE142BE17999C4]

[toc] | [prev] | [next] | [standalone]

#56362

Steven D'Aprano writes:

> Far more useful would be a high-level description of Scheme's
> programming model. If names can be rebound on the fly, how does
> Scheme even tell whether something is a recursive call or not?
> 
> def foo(arg):
>     do stuff here
>     foo(arg-1)  # how does Scheme know that this is the same foo?

In general, it doesn't know. It just calls whatever function is bound
to foo. It does know that the call is in a tail position.

If the compiler has access to all code that can possibly change the
value of foo, it can know simply by proving that there is no such
assignment statement in the code. This can happen if the compiler is
told to assume that it has the whole program. It often happens in a
local scope. Module systems create such local scopes for unexported
variables, and even for exported variables by forbidding assignments
outside.

(I'm not sure if your question was rhetorical or if you were looking
for this information.)

[toc] | [prev] | [next] | [standalone]

#56374

Op 08-10-13 01:50, Steven D'Aprano schreef:
> On Mon, 07 Oct 2013 15:47:26 -0700, Mark Janssen wrote:
> 
>> I challenge you to get
>> down to the machine code in scheme and formally describe how it's doing
>> both.
> 
> For which machine?
> 
> Or are you assuming that there's only one machine code that runs on all 
> computing devices?
> 
> 
> Frankly, asking somebody to *formally* describe a machine code 
> implementation strikes me as confused. Normally formal descriptions are 
> given in terms of abstract operations, often high level operations, 
> sometimes *very* high level, and rarely in terms of low-level "flip this 
> bit, copy this byte" machine code operations. I'm not sure how one would 
> be expected to generate a formal description of a machine code 
> implementation.
> 
> But even putting that aside, even if somebody wrote such a description, 
> it would be reductionism gone mad. What possible light on the problem 
> would be shined by a long, long list of machine code operations, even if 
> written using assembly mnemonics?
> 
> Far more useful would be a high-level description of Scheme's programming 
> model. If names can be rebound on the fly, how does Scheme even tell 
> whether something is a recursive call or not?
> 
> def foo(arg):
>     do stuff here
>     foo(arg-1)  # how does Scheme know that this is the same foo?

It doesn't and it doesn't need to. tail call optimisation is not
limited to recursive functions. All tail calls can be optimised,
recurisive call and others.

-- 
Antoon Pardon

[toc] | [prev] | [next] | [standalone]

#56341

Mark Janssen <dreamingforward@gmail.com> writes:

> Yeah, and this is where two models of computation have been conflated,
> creating magical effects, confusing everybody.  I challenge you to get
> down to the machine code in scheme and formally describe how it's
> doing both.

Which two models of computation are you talking about? And what magica; effects? AFAIK there is no magic in computer science, although every sufficiently advanced ...
-- 
Piet van Oostrum <piet@vanoostrum.org>
WWW: http://pietvanoostrum.com/
PGP key: [8DAE142BE17999C4]

[toc] | [prev] | [next] | [standalone]

#56345

>> Yeah, and this is where two models of computation have been conflated,
>> creating magical effects, confusing everybody.  I challenge you to get
>> down to the machine code in scheme and formally describe how it's
>> doing both.
>
> Which two models of computation are you talking about? And what magica; effects?

Well, I delineate all computation involving predicates (like lambda
calculus) between those using digital logic (like C).  These realms of
computation are so different, they are akin to mixing the complex
numbers with the real.  Yet hardly anyone points it out (I've
concluded that hardly anyone has ever noticed -- the Church-Turing
thesis has lulled the whole field into a shortcut in thinking which
actually doesn't pan out in practice).

> AFAIK there is no magic in computer science, although every sufficiently advanced ...

Ha!  That's very good.  I'm glad you catch the spirit of my rant.
"Any sufficiently advanced compiler can be substituted with magic to
the neophyte without a change in output."  A mini Liskov substitution.

-- 
MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#55394

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:

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. It 
seems to me that an implementation might provide a single byte-code to 
build list literals, perhaps even LOAD_CONST itself. The byte-codes used 
by the Python VM are not part of the language definition, 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@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




-- 
Steven

[toc] | [prev] | [next] | [standalone]

#55396

On 2/10/2013 21:24, 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:
>
> 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:
>
>

The difference is that a tuple can be reused, so it makes sense for the
comiler to produce it as a const.  (Much like the interning of small
integers)  The list, however, would always have to be copied from the
compile-time object.  So that object itself would be a phantom, used
only as the template with which the list is to be made.


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#55397

On 03/10/2013 02:39, Dave Angel wrote:
> On 2/10/2013 21:24, 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:
>>
>> 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:
>>
>>
>
> The difference is that a tuple can be reused, so it makes sense for the
> comiler to produce it as a const.  (Much like the interning of small
> integers)  The list, however, would always have to be copied from the
> compile-time object.  So that object itself would be a phantom, used
> only as the template with which the list is to be made.
>
The key point here is that the tuple is immutable, including its items.

[toc] | [prev] | [next] | [standalone]

#55399

On Thu, 03 Oct 2013 02:46:53 +0100, MRAB wrote:

> On 03/10/2013 02:39, Dave Angel wrote:
>> On 2/10/2013 21:24, 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:
>>>
>>> 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:
>>>
>>>
>>>
>> The difference is that a tuple can be reused, so it makes sense for the
>> comiler to produce it as a const.  (Much like the interning of small
>> integers)  The list, however, would always have to be copied from the
>> compile-time object.  So that object itself would be a phantom, used
>> only as the template with which the list is to be made.
>>
> The key point here is that the tuple is immutable, including its items.

You are both assuming that LOAD_CONST will re-use the same tuple 
(1, 2, 3) in multiple places. But that's not the case, as a simple test 
will show you:


# Python 3.3

py> def f():
...     a = (1, 2, 3)
...     b = (1, 2, 3)
...     return a is b
...
py> f()  # Are the tuples the same object?
False
py> from dis import dis
py> dis(f)
  2           0 LOAD_CONST               4 ((1, 2, 3))
              3 STORE_FAST               0 (a)

  3           6 LOAD_CONST               5 ((1, 2, 3))
              9 STORE_FAST               1 (b)

  4          12 LOAD_FAST                0 (a)
             15 LOAD_FAST                1 (b)
             18 COMPARE_OP               8 (is)
             21 RETURN_VALUE



So even though both a and b are created by the same LOAD_CONST byte-code, 
the object is not re-used (although it could be!) and two distinct tuples 
are created.

Re-use of objects (caching or interning) is an implementation 
optimization, not a language feature. An implementation might choose to 
cache ints, tuples, strings, floats, or none of them at all. That in no 
way affects whether the LOAD_CONST byte-code is used.

In fact, LOAD_CONST may behave differently inside functions than outside: 
in CPython, functions will cache some literals in the function attribute 
__code__.co_consts, and LOAD_CONST may use that, while outside of a 
function, only small ints and identifier-like strings are cached but very 
little else. Other implementations may do differently -- I'm not sure 
whether __code__ is a public language feature or an implementation 
feature, but what goes into co_consts certainly isn't fixed. IronPython 
2.6 doesn't appear to put anything in co_consts except None.

And of course, *all of this is subject to change*, since it is not 
language semantics but implementation details. If HyperPython8.5 
aggressively caches every tuple it can, while SimplePython1.1 uses 
BUILD_TUPLE rather than LOAD_CONST, both are still perfectly compliant 
Python implementations.

(HyperPython probably will require a huge amount of memory, and 
SimplePython will probably be slow, but those are quality of 
implementation issues.)


Aside: a sufficiently smart optimizing compiler could optimize function f 
above to either 

    LOAD_CONST    (True)
    RETURN_VALUE

or

    LOAD_CONST    (False)
    RETURN_VALUE


and still be a correct Python implementation. Since Python the language 
doesn't specify when, if ever, objects should be cached, it could even 
randomly choose between those two options at compile time, or even at 
runtime, and still be correct.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#55403

On Thu, Oct 3, 2013 at 12:34 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> py> def f():
> ...     a = (1, 2, 3)
> ...     b = (1, 2, 3)
> ...     return a is b
> ...
> py> f()  # Are the tuples the same object?
> False

That just means the compiler doesn't detect reuse of the same tuple.
But compare:

>>> def f():
    return (1,2,3)

>>> f() is f()
True

Every time the function's called, it returns the same tuple (which
obviously can't be done with lists). And of course if that would be
dangerous, it's not done:

>>> def f():
    return (1,[2],3)

>>> f()[1].append("Hello")
>>> f()
(1, [2], 3)
>>> import dis
>>> dis.dis(f)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 BUILD_LIST               1
              9 LOAD_CONST               3 (3)
             12 BUILD_TUPLE              3
             15 RETURN_VALUE

ChrisA

[toc] | [prev] | [next] | [standalone]

#55413

On Wed, Oct 2, 2013, at 22:34, Steven D'Aprano wrote:
> You are both assuming that LOAD_CONST will re-use the same tuple 
> (1, 2, 3) in multiple places. But that's not the case, as a simple test 
> will show you:

>>> def f():
...   return (1, 2, 3)
>>> f() is f()
True

It does, in fact, re-use it when it is _the same LOAD_CONST
instruction_.

[toc] | [prev] | [next] | [standalone]

#55440

On 10/2/2013 10:34 PM, Steven D'Aprano wrote:

> You are both assuming that LOAD_CONST will re-use the same tuple
> (1, 2, 3) in multiple places.

No I did not. To save tuple creation time, a pre-compiled tuple is 
reused when its display expression is re-executed. If I had been 
interested in multiple occurrences of the same display, I would have tested.

 >>> def f():
	a = 1,'a',3333, 'bbb'; x = 1,'a',3333, 'bbb'
	b = 1,'a',3333, 'bbb'
	c = 'a'
	d = 3333 + 3333
	
 >>> f.__code__.co_consts
(None, 1, 'a', 3333, 'bbb', (1, 'a', 3333, 'bbb'), (1, 'a', 3333, 
'bbb'), (1, 'a', 3333, 'bbb'), 6666)

Empirically, ints and strings are checked for prior occurrence in 
co_consts before being added. I suspect None is too, but will not assume.

How is the issue of multiple occurrences of constants relevant to my 
topic statement? Let me quote it, with misspellings corrected.

"CPython core developers have been very conservative about what
transformations they put into the compiler." [misspellings corrected]

Aha! Your example and that above reinforce this statement. Equal tuples 
are not necessarily identical and cannot necessarily be substituted for 
each other in all code.

 >>> (1, 2) == (1.0, 2.0)
True

But replacing (1.0, 2.0) with (1, 2), by only storing the latter, would 
not be valid without some possibly tricky context analysis. The same is 
true for equal numbers, and the optimizer pays attention.

 >>> def g():
	a = 1
	b = 1.0

 >>> g.__code__.co_consts
(None, 1, 1.0)

For numbers, the proper check is relatively easy:

for item in const_list:
   if type(x) is type(item) and x == item:
     break  # identical item already in working list
else:
   const_list.append(x)

Writing a valid recursive function to do the same for tuples, and 
proving its validity to enough other core developers to make it 
accepted, is much harder and hardly seems worthwhile.

It would probably be easier to compare the parsed AST subtrees for the 
displays rather than the objects created from them.

---
 > py> def f():
 > ...     a = (1, 2, 3)
 > ...     b = (1, 2, 3)
[snip]
 > So even though both a and b are created by the same LOAD_CONST 
byte-code,

I am not sure what you mean by 'created'. LOAD_CONST puts the address of 
an object in co_consts on the top of the virtual machine stack.

 > the object is not re-used (although it could be!)

It can be reused, in this case, because the constant displays are 
identical, as defined above.

 > and two distinct tuples are created.

Because it is not easy to make the compiler see that only one is needed.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#55400

On 10/2/2013 9:46 PM, MRAB wrote:
> On 03/10/2013 02:39, Dave Angel wrote:
>> On 2/10/2013 21:24, 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.

To be specific: in

for i in [1,2,3]: print i

it looks like it might be save to pre-compile the list and just use it 
when the code is run. But if the above is in a function object whose 
code object is ever introspected, the list object could be accessed and 
mutated. Letting the compiler know that it can do the optimization is 
one reason to use tuples in situations like the above.

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

I am referring to constant-value objects included in the code object.
 >>> def f(): return (1,2,3)

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

None is present as the default return, even if not needed for a 
particular function. Every literal is also tossed in, whether needed or not.

>>> which in Python 3.3 understands tuples like (1, 2, 3), but not lists.

The byte-code does not understand anything about types. LOAD_CONST n 
simply loads the (n+1)st object in .co_consts onto the top of the stack.

>>> S9 a literal (1, 2, 3) gets created at compile-time with a single
>>> LOAD_CONST call:
>>>
>>> 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:
>>>
>>
>> The difference is that a tuple can be reused, so it makes sense for the
>> comiler to produce it as a const.  (Much like the interning of small
>> integers)  The list, however, would always have to be copied from the
>> compile-time object.  So that object itself would be a phantom, used
>> only as the template with which the list is to be made.
>>
> The key point here is that the tuple is immutable, including its items.

The items of the tuple I gave as an examples are all constant. If they 
were not, the tuple would not be a constant for the purpose of 
compile-time creation.



-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#55448

On Wed, 02 Oct 2013 22:41:00 -0400, Terry Reedy wrote:

> I am referring to constant-value objects included in the code object.
>  >>> def f(): return (1,2,3)
> 
>  >>> f.__code__.co_consts
> (None, 1, 2, 3, (1, 2, 3))

Okay, now that's more clear. I didn't understand what you meant before. 
So long as we understand we're talking about a CPython implementation 
detail.


> None is present as the default return, even if not needed for a
> particular function. Every literal is also tossed in, whether needed or
> not.
> 
>>>> which in Python 3.3 understands tuples like (1, 2, 3), but not lists.
> 
> The byte-code does not understand anything about types. LOAD_CONST n
> simply loads the (n+1)st object in .co_consts onto the top of the stack.

Right, this is more clear to me now.

As I understand it, the contents of code objects are implementation 
details, not required for implementations. For example, IronPython 
provides a co_consts attribute, but it only contains None. Jython doesn't 
provide a co_consts attribute at all. So while it's interesting to 
discuss what CPython does, we should not be fooled into thinking that 
this is guaranteed by every Python.

I can imagine a Python implementation that compiles constants into some 
opaque object like __closure__ or co_code. In that case, it could treat 
the list in "for i in [1, 2, 3]: ..." as a constant too, since there is 
no fear that some other object could reach into the opaque object and 
change it.

Of course, that would likely be a lot of effort for very little benefit. 
The compiler would have to be smart enough to see that the list was never 
modified or returned. Seems like a lot of trouble to go to just to save 
creating a small list.

More likely would be implementations that didn't re-use constants, than 
implementations that aggressively re-used everything possible.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#55401

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

[toc] | [prev] | [next] | [standalone]

#55412

On Wed, Oct 2, 2013, at 21:46, MRAB wrote:
> > The difference is that a tuple can be reused, so it makes sense for the
> > comiler to produce it as a const.  (Much like the interning of small
> > integers)  The list, however, would always have to be copied from the
> > compile-time object.  So that object itself would be a phantom, used
> > only as the template with which the list is to be made.
> >
> The key point here is that the tuple is immutable, including its items.

Hey, while we're on the subject, can we talk about frozen(set|dict)
literals again? I really don't understand why this discussion fizzles
out whenever it's brought up on python-ideas.

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.python

csiph-web