Tail recursion to while iteration in 2 easy steps

[Steven D'Aprano]

It's like this: there *should* be one-to-one mappings between the
various high-level constructs to the machine code, varying only between
different chips (that is the purpose of the compiler after all), yet for
some operations, in languages like scheme, well... I cannot say what
happens... hence my challenge.


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.

In practice, only if you use the exact same source code, the exact same
compiler, the exact same version of that compiler, with the exact same
compiler options, and the exact same version of the language and all its
libraries, then and only then will you will get the same machine code.
And even that is not guaranteed.

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:

http://en.wikipedia.org/wiki/Category:Sorting_algorithms

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.

We can use Python to discuss this, since Python includes a compiler. It
generates byte code, which just means machine code for a virtual machine
instead of a hardware machine, but the principle is the same. Python even
has a disassembler, for taking those raw byte codes and turning them into
human-readable pseudo-assembly for the Python Virtual Machine.

Here is some "machine code" corresponding to the high-level instructions:

x = 23
y = 42
z = x + y
del x, y


py> code = compile('x = 23; y = 42; z = x + y; del x, y', '', 'exec')
py> code.co_code
'd\x00\x00Z\x00\x00d\x01\x00Z\x01\x00e\x00\x00e\x01\x00\x17Z\x02\x00[\x00
\x00[\x01\x00d\x02\x00S'


Translated into "assembly":

py> from dis import dis
py> dis(code)
1 0 LOAD_CONST 0 (23)
3 STORE_NAME 0 (x)
6 LOAD_CONST 1 (42)
9 STORE_NAME 1 (y)
12 LOAD_NAME 0 (x)
15 LOAD_NAME 1 (y)
18 BINARY_ADD
19 STORE_NAME 2 (z)
22 DELETE_NAME 0 (x)
25 DELETE_NAME 1 (y)
28 LOAD_CONST 2 (None)
31 RETURN_VALUE


You should be able to see that there are all sorts of changes that the
compiler could have made, which would have lead to different "machine
code" but with the exact same behaviour. This particular compiler emits
code for x=23; y=42 in the order that they were given, but that's not
actually required in this case. The compiler might have reversed the
order, generating something like:

0 LOAD_CONST 1 (42)
3 STORE_NAME 1 (y)
6 LOAD_CONST 0 (23)
9 STORE_NAME 0 (x)

or even:

0 LOAD_CONST 1 (42)
3 LOAD_CONST 0 (23)
6 STORE_NAME 1 (y)
9 STORE_NAME 0 (x)

without changing the behaviour of the code. Or it might have even
optimized the entire thing to:

0 LOAD_CONST 0 (65)
3 STORE_NAME 0 (z)


since x and y are temporary variables and a smart compiler could perform
the computation at compile time and throw them away. (Nitpicks about
"what if x and y already existed?" aside.) CPython even does this sort of
optimization, although in a more limited fashion:

py> dis(compile('x = 23 + 42', '', 'exec'))
1 0 LOAD_CONST 3 (65)
3 STORE_NAME 0 (x)
6 LOAD_CONST 2 (None)
9 RETURN_VALUE

This is called keyhole optimization. It's not beyond possibility for a
smarter compiler to look beyond the keyhole and make optimizations based
on the whole program.

So you can see that there is no one-to-one correspondence from high-level
source code to low-level machine code, even for a single machine. The
same is even more true for languages such as C, Fortran, Pascal, Lisp,
Scheme, Haskell, Java, etc. where people have spent years or decades
working on compiler technology. Compilers differ in the quality and
efficiency of the machine code they emit and the choices they make about
translating source code to machine code.

That's all. Everything
else is magic. Do you know that the Warren Abstraction Engine used to
power the predicate logic in Prolog into machien code for a VonNeumann
machine is so complex, no one has understood it

That's nonsense. In your next post, you even supply a link to a book
describing how the WAM works with detailed step-by-step instructions for
writing your own. For those reading, here it is:

www.cvc.uab.es/shared/teach/a25002/wambook.pdf


Prolog is not some dark black magic that nobody understands. There are
multiple implementations of Prolog-like logic languages for Python:

http://pyke.sourceforge.net/
https://github.com/logpy/logpy
https://github.com/enriquepablo/nl/
http://code.google.com/p/fuxi/
https://sites.google.com/site/pydatalog/

to say nothing of similar, more advanced languages like Mercury. Just
because *you personally* don't understand something, don't think that
nobody else does.

 

[Piet van Oostrum]

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]

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.

 

[rusi]

Now, one can easily argue that I've gone too far to say "no one has
understood it" (obviously), so it's very little tongue-in-cheek, but
really, when one tries to pretend that one model of computation can be
substituted for another (arguing *for* the Church-Turing thesis), they
are getting into troubling territory (it is only a thesis,
remember)....

The CT thesis is scientific and provable in one sense and vague/philosophical in another.
The Science: Turing computability and lambda-computability are equivalent.
The proofs just consist of writing interpreters for one in terms of the other.

The philosophy: *ALL* computational models are turing equivalent (and therefore lambda-equivalent) or weaker.
The Idea (note not proof) is that for equivalence one can write pair-interpreters like above. For the 'weaker' case, (eg DFA and TMs) one proves that TMs can interpret DFAs and disproves the possibility of the other direction..

This must remain an idea (aka thesis) and not a proof because one cannot conceive of all possible computational models.
It is hard science however for all the models that anyone has so far come up with.

Now there are caveats to this which I wont go into for now.

As for:

I challenge you to get down to the machine code in scheme and formally
describe how it's doing both.

I can only say how ironic it sounds to someone who is familiar with the history of our field:
Turing was not a computer scientist (the term did not exist then) but a mathematician. And his major contribution was to create a form of argument somuch more rigorous than what erstwhile mathematicians were used to that hewas justified in calling that math as a machine.

The irony is that today's generation assumes that 'some-machine' implies its something like 'Intel-machine'.
To get out of this confusion ask yourself: Is it finite or infinite?
If the TM were finite it would be a DFA
If the Intel-machine (and like) were infinite they would need to exist in adifferent universe.

And so when you understand that TMs are just a kind of mathematical rewritesystem (as is λ calculus as are context free grammars as is school arithmetic etc etc) you will not find the equivalence so surprising

 

[Mark Janssen]

But even putting that aside, even if somebody wrote such a description,

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.

 

[Mark Janssen]

Yeah, and this is where two models of computation have been conflated,

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.

 

[Ravi Sahni]

I can only say how ironic it sounds to someone who is familiar with the history of our field:
Turing was not a computer scientist (the term did not exist then) but a mathematician. And his major contribution was to create a form of argument so much more rigorous than what erstwhile mathematicians were used to that he was justified in calling that math as a machine.

The irony is that today's generation assumes that 'some-machine' implies its something like 'Intel-machine'.
To get out of this confusion ask yourself: Is it finite or infinite?
If the TM were finite it would be a DFA
If the Intel-machine (and like) were infinite they would need to exist ina different universe.

With due respect Sir, you saying that Turing machine not a machine?
Very confusion Sir!!!

 

[Mark Janssen]

The CT thesis is scientific and provable in one sense and vague/philosophical in another.
The Science: Turing computability and lambda-computability are equivalent..
The proofs just consist of writing interpreters for one in terms of the other.

Ah, good, a fellow theoretician. Now it's nice that you use language
that makes it seem quite clear, but understand that there's a hidden,
subconscious, *cultural* encoding to your *statement*. The use of the
term "equivalent", for example. Equivalent for the programmer, or for
the machine? (etc., et cetera), and further: "writing interpreters
for one in terms of the other", but again, this will change depending
on your pragmatic requirements. To the theorist, you've accomplished
something, but then that is a self-serving kind of accomplishment. To
the programmer, operating under different requirements, you haven't
accomplished anything. I don't have an infinite stack to implement
lambda calculus, but I can treat my computer's memory as a TM and
*practically* infinite and only rarely hit against the limits of
physicality. This is just being "respectful"... ;^)

(For the purposes of discussion, if I make a word in CamelCase, I am
referring to a page on the WikiWikiWeb with the same name:
http://c2.com/cgi/wiki?WikiWikiWeb.)

The philosophy: *ALL* computational models are turing equivalent (and therefore lambda-equivalent) or weaker.
The Idea (note not proof) is that for equivalence one can write pair-interpreters like above. For the 'weaker' case, (eg DFA and TMs) one proves that TMs can interpret DFAs and disproves the possibility of the other direction.

This must remain an idea (aka thesis) and not a proof because one cannot conceive of all possible computational models.

Why not? I can "conceive" of all possible integer numbers even if I
never "pictured" them. Is there not an inductive way to conceive of
and define computation? I mean, I observe that the field seems to
define several ModelsOfComputation. Intuitively I see two primary
domains

It is hard science however for all the models that anyone has so far comeup with.

And what of "interactive computation"?

As for:


I can only say how ironic it sounds to someone who is familiar with the history of our field:
Turing was not a computer scientist (the term did not exist then) but a mathematician. And his major contribution was to create a form of argument so much more rigorous than what erstwhile mathematicians were used to that he was justified in calling that math as a machine.

Hmm, I'm wondering if my use of the word "formally" is confusing you.
In mathematics, this word has a subtly differing meaning, I think,
than in computer science. Turing was "justified in calling that math
as a machine" because he was using a definition (the translation table
+ finite dictionary) such that it remained perfectly deterministic.

And here, again, one can easily gets mixed up using the same lexicon
across two different domains: that of math and that of CS. I advise
you to look at the dialog at ConfusedComputerScience.

The irony is that today's generation assumes that 'some-machine' implies its something like 'Intel-machine'.
To get out of this confusion ask yourself: Is it finite or infinite?

But this only gets us out of the confusion for the mathematicians.
For the programmer and perhaps even the computer scientist (the one's
coming from physics), it is something different.

If the TM were finite it would be a DFA

But this is not a useful formalism. Any particular Program implements
a DFA, even as it runs on a TM. The issue of whether than TM is
finite or not can be dismissed because a simple calculation can
usually suffice, or at least establish a range "usefulness" so as not
to "run out of memory".

If the Intel-machine (and like) were infinite they would need to exist ina different universe.

Ha, yeah. Let us dismiss with that.

And so when you understand that TMs are just a kind of mathematical rewrite system (as is ë calculus as are context free grammars as is school arithmetic etc etc) you will not find the equivalence so surprising

It's not that it's surprising, it's that it's *practically* a problem.
The translation between one PL and another which assumes a different
model of computation can get intractible.

Maybe that makes sense....

MarkJ
Tacoma, Washington

 

[rusi]

With due respect Sir, you saying that Turing machine not a machine?
Very confusion Sir!!!

Thanks Ravi for the 'due respect' though it is a bit out of place on a list like this

Thanks even more for the 'very confusion'. I can tell you being a teacher for 25 years that the most terrifying thing is the Dunning Kruger effect -- students who are utterly clueless and dont have a frigging clue about that.

Ive seen PhDs in CS ask questions in compiler-related degree projects that they would not ask if they really understood the halting problem.
[Or were you suggestig that I am the confused? ]

So yes, its a big thing to be confused and to accept that.

To explain at length will be too long and OT (off-topic) for this list.
I'll just give you a link and you tell me what you make of it:
http://sloan.stanford.edu/mousesite/Secondary/Whorfframe2.html
[mainly concentrate on the first section]

 

[rusi]

I don't have an infinite stack to implement
lambda calculus, but...

And then

But this is not a useful formalism. Any particular Program implements
a DFA, even as it runs on a TM. The issue of whether than TM is
finite or not can be dismissed because a simple calculation can
usually suffice, or at least establish a range "usefulness" so as not
to "run out of memory".

Having it both ways aren't you?

 

[Mark Lawrence]

Thanks Ravi for the 'due respect' though it is a bit out of place on a list like this

With due respect Sir I'd like to point out that this appears to have
very little to do (directly) with Python, so to go completely off topic
I'll point out that my nephew is currently working on the film about the
life of said Alan Turing

--
Roses are red,
Violets are blue,
Most poems rhyme,
But this one doesn't.

Mark Lawrence

 

[Jussi Piitulainen]

The entire point of tail call optimization requires not keeping the
intervening stack frames around, in _any_ form, so as to allow
arbitrarily deep recursion without ever having the possibility of a
stack overflow. An implementation which reduced but did not
eliminate the space used per call would not be worthwhile because it
would not enable the recursive functional programming patterns that
mandatory tail call optimization allows.

You could require that an "optimizable tail call" be made explicit.
Actually, I suspect it might be possible to do this now, by abusing
exception handling as a control flow mechanism.

Python code already marks many of the functionally relevant tail calls
with 'return'. It just wants to retain the trace.

Another keyword could be used to indicate that the programmer does not
want a stack frame retained. It's probably too much to suggest 'please
return', but how about 'goto return'?

A tail call is a 'goto that passes arguments', and I think 'goto' is a
keyword already.

(Actually I just wanted to suggest 'please return'. Not seriously.)

 

[Jussi Piitulainen]

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.)

 

[Steven D'Aprano]

With due respect Sir, you saying that Turing machine not a machine? Very
confusion Sir!!!

The mathematical ideal Turing Machine has an infinitely long tape,
equivalent to infinite memory, and may take an unbounded amount of time
to complete the computation. Since no *actual* physical machine can be
infinitely big, and in practice there are strict limits on how long we
are willing to wait for a computation to complete, in the *literal*
sense, Turing Machines are not *actual* machines. They are a mathematical
abstraction.

But in practice, we can wave our hands and ignore this fact, and consider
only not-quite-Turing Machines with finite amounts of tape, and note that
they are equivalent to physical machines with finite amounts of memory.
One could even build such a finite Turing Machine, although of course it
would be very slow. Or one can simulate it in software.

So in that sense, computers are Turing Machines. Anything a physical
computing device can compute, a Turing Machine could too. The converse is
not true though: a Turing Machine with infinite tape can compute things
where a real physical device would run out of memory, although it might
take longer than anyone is willing to wait.

 

[Alain Ketterlin]

Let's be clear about what optimizations we are talking about. Tail call
optimization, itself, doesn't care _what_ is being called. It can just
as easily mean "erase its own stack frame and replace it with that of
another function" as "reassign the arguments and jump to the top of this
function". Some people have introduced the idea of _further_
optimizations, transforming "near" tail recursion (i.e. return self()+1)
into tail recursion, and _that_ depends on knowing the identity of the
function (though arguably that could be accounted for at the cost of
including dead code for the path that assumes it may have been changed),
but tail call optimization itself does not.

You're right, thanks for the clarification.

-- Alain.

 

[Alain Ketterlin]

Op 07-10-13 19:15, Alain Ketterlin schreef:
[...]

That's fine. My point was: you can't at the same time have full
dynamicity *and* procedural optimizations (like tail call opt).
Everybody should be clear about the trade-off.

Your wrong. Full dynamics is not in contradiction with tail call
optimisation. Scheme has already done it for years. You can rebind
names to other functions in scheme and scheme still has working
tail call optimisatiosn.

See
http://en.wikipedia.org/wiki/Scheme_(programming_language)#Lexical_scope

(first sentence, about variable bindings).

-- Alain.

 

[Antoon Pardon]

Op 08-10-13 01:50, Steven D'Aprano schreef:

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.

 

[Steven D'Aprano]

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.

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.

 

[Antoon Pardon]

Op 07-10-13 23:27, (e-mail address removed) schreef:

The entire point of tail call optimization requires not keeping the
intervening stack frames around, in _any_ form, so as to allow
arbitrarily deep recursion without ever having the possibility of a
stack overflow. An implementation which reduced but did not eliminate
the space used per call would not be worthwhile because it would not
enable the recursive functional programming patterns that mandatory tail
call optimization allows.

So? What about an implementation that would keep its stackframes
normally until it deteced recursion had occured. From then on it
would only keep what it already had plus the four top stackframes
(assuming it are all tail calls for the moment). This would allow
for a stacktrace of the last four calls and essentially doesn't need
any space per call from then on.

 

[Jussi Piitulainen]

Op 07-10-13 19:15, Alain Ketterlin schreef:
[...]

That's fine. My point was: you can't at the same time have full
dynamicity *and* procedural optimizations (like tail call opt).
Everybody should be clear about the trade-off.

Your wrong. Full dynamics is not in contradiction with tail call
optimisation. Scheme has already done it for years. You can rebind
names to other functions in scheme and scheme still has working
tail call optimisatiosn.

See
http://en.wikipedia.org/wiki/Scheme_(programming_language)#Lexical_scope

(first sentence, about variable bindings).

# ... Scheme is lexically scoped: all possible variable bindings in a
# program unit can be analyzed by reading the text of the program unit
# without consideration of the contexts in which it may be called ...

The actual procedure to be called is still not known at compile time,
in general. It can be a parameter. It needn't even be the value of any
explicit variable (needn't be "bound to a name").

def call(f, a):
...
return f(a) # tail call
...

def wev(...):
...
return (fs if c(k) else gs)[k](a) # tail call
...

In the Scheme reports, a variable is said to be bound to a location,
which is lexically apparent to the language processor; the value is
stored in that location, and assignment to the variable means storing
a new value in that location. It works like Python or Java; Python
just has a different way of talking about how it works - binding names
directly to values in a namespace, and rebinding to different values.

However, Scheme processors know that the local variables are not
accessible from anywhere else but the local code, so there are more
opportunities for compile-time analysis. They can optimize many of
those locations away, for example.