Information Technology Reference
In-Depth Information
is exactly the administrative quantity “stack pointer” in [Dij60] which always
points to the first free place in the memory reserved for the stack.
2
The notion static pointer is due to Algol60's new language feature, namely the
block (nesting) concept. Dijkstra formulated a statement in [Dij60] to determine
the static pointer
SV
:
“
SV
points to the
most recent
, not yet completed, activation of the first block
that lexicographically encloses the block of the subroutine called in.”
In [KaL74, Kan74] this statement is called the
“most recent”-property
of an
Algol-program. But: Is this property really a logical consequence constituted by
Algol60's static scope copy rule semantics for all programs?
McGowan [McG72] contradicts this consequence and speaks of Dijkstra's
“most recent”-error
. In [GHL67] there is a first example
π
1
of an Algol60-
program which does not meet the
“most recent”
-property. Nevertheless, Dijk-
stra's claim has been around for a long time. E.g. in the topic on compiler
construction [WiM92] we find the following statement together with a so called
proof of assurance (Sicherstellungsbeweis) which is obviously incorrect:
“(Invariant ISV) In every stack frame provided for the incarnation of a proce-
dure
p
the static pointer
SV
is pointing to the stack frame of the
most recent
, still
living incarnation of that program unit which is directly enclosing
p
” (translated
from German).
The program example
π
1
in [GHL67], page 108/109, which does not satisfy
the “most recent”-property has the following substructure:
proc P(F, G)
{
proc Q(R, S)
{
...
}
end Q
...
F(Q, F)
...
}
end P
...
P(P, P)
...
The
“most recent”
-error shows up already in that linear subtree inside the for-
mal execution tree which is generated by this substructure. In the following
we show a simplified example
π
2
[Goe05] (compare the simplified examples
in [KaL74, Kan74])
{
proc q(r,s)
{
print(g)
}
f(q,false)
}
p(p,true)
proc p(f,g)
2
Already in [Sam57] K. Samelson discribes how to execute closed parameterized sub-
routines by help of the fixed variable “Anfang (=Beginn) freier Speicher” where
repeatedly called subroutines are to be provided with parameters, return informa-
tions and auxiliary storage places before earlier calls have been completely executed.
Search WWH ::
Custom Search