Tail recursion to while iteration in 2 easy steps

[Charles Hixson]

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