Tail recursion to while iteration in 2 easy steps

[Steven D'Aprano]

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