Information Technology Reference
In-Depth Information
But if we don't do any renamings, i.e. if we perform so called dynamic scoping
and binding of identifiers, we would arrive at a semantics of Algol60-programs
which is different from Algol60's static scope semantics defined in the report.
Every dynamic scope formal execution tree is regular [Old81b], whereas static
scope formal execution trees may be irregular [Lan74, Old81b]. Consequence:
Algol60 with dynamic scope semantics has a correct and relatively complete
Hoare-like proof calculus, whereas there does not exist any such calculus for the
full static scope Algol60-language [Lan73b,Cla79,LaO80]. In case of static scop-
ing we have such calculi only for certain sublanguages, e.g. of those programs
with regular formal execution trees [Old81a, Old81b], especially of those pro-
grams sucing the so called formal “most recent”-property [Kan74], or of those
programs with finite procedure types (Pascal-like) if the latter have only simple
sideeffects [Old84, Lan85, CGH83, Hun90].
C [KeR78] and Ada [Ich80] do not support procedure nesting. From a software
engineering viewpoint, though, nesting (with static scoping) is a key technique
for information hiding: It reduces the number of global dependencies and helps to
encapsulate and to handle implementation decisions more abstractly. It is well-
known that object oriented programs can be simulated by imperative languages.
Late binding can either be implemented by generic procedures, which perform a
runtime dispatch on the type of message receiver objects [Goe93], or by procedure
variables (formal procedures) as part of the receiver's class object [Bla03]. Thus
Algol-like programs are suciently expressive to support simulation of object
oriented programs.
Note that, in the present essay, we are interested in the opposite direction of
simulation.
2.2
On Reasons Why Proper Understanding of Formal
Algol60-Procedures and Their Static Scope Semantics Has
Been so Intricate
After a discussion of Bauer, Dijkstra, Paul and Samelson in Copenhagen in 1959,
Dijkstra [Dij60] extended operator and number cellar (Operator- und Zahlkeller)
of Bauer and Samelson [SaB59] towards a runtime stack with procedure activa-
tion records (procedure stack frames) as information units which contain
•
local and auxiliary variables,
•
intermediate results,
•
local parameters (arguments),
•
return address,
•
dynamic pointer
DV
to the frame of the most recently called and not yet
completed procedure,
•
static pointer
SV
to a certain frame of the statically (lexicographically) en-
closing procedure in order to have access to global parameters.
The latter three entries form the so called procedure link of a frame (An-
schlussteil in [SaB59]). The special parameter “Beginn freier Speicher” in [SaB59]
Search WWH ::
Custom Search