17 Feb
2025
17 Feb
'25
12:08 p.m.
On Mon, 2025-02-17 at 09:13 -0500, Paul Koning wrote:
The display isn't static for nested recursive functions (as in Pascal)
and you want to have "deep binding," not "shallow binding."
The "up link" for a recursive function passed to another recursive
procedure as an actual argument should be the "up link" as of the
moment of invocation of the procedure getting the nested one, not as of
the moment the nested one finally gets invoked by way of the formal
argument during a recursion by the procedure that got it as an actual
argument.
Pennello had some Pascal "compiler breaker" codes that he would use to
test compilers.
After he graduated, he worked for Frank de Remer at MetaWare. They
marketed Pascal compilers for many machines. Tom called it
"overextended Pascal."
I don't know whether the Algol 60 Report or the Algol 68 standard or
the Pascal Report explicitly specified deep binding, but it's more
useful than shallow binding. The Fortran standards explicitly require
deep binding, but not using those words.
When Tom
Pennello was a grad student studying under Frank de Remer
at
ACSC, he collected a big pile of codes in languages that had nested
lexical and dynamic scopes (such as recursive internal functions).
He
found that chasing up-links was much faster than displays. In some
cases, creating and destroying the display took six times longer
than
executing the function. I mentioned this to Malcolm Cohen and me
mumbled something about a "trampoline." I have no idea what that
is.
I'm puzzled by that, since the display is a static data structure and
updating it takes only a few instructions for each call and fewer for
a return.
"Trampolines" are how GCC handles nested
functions, or at least that
is the traditional mechanism. I never really understood them other
than to realize they involve executable code on the stack -- which
means they only work in some machines and some operating systems. I
think there is now a replacement mechanism that avoids this issue but
I don't remember the details. Why GCC didn't adopt displays isn't
clear to me.