Dynamic Links:
The description of dynamic links in chapter
10 is
incorrect, and in conflict with what is said about the whole subprogram invocation
process.
Here are relevant excerpts from the book.
" The dynamic link is a pointer to the top of
the activation record instance of the caller. In static-scoped languages, this link is used in the destruction of the
current activation record instance when the procedure completes its execution. The stack top is set to the
value of the old dynamic link. The dynamic link is required, because in some cases there are other allocations from
the stack by a subprogram beyond its activation record.
For example, temporaries needed by the machine language
version of the program may be allocated there. So, although the size of the activation record may be
known, the size cannot simply be subtracted from the stack top pointer to remove the activation record".
(p. 444)
" One more thing is required to control the execution
of a subprogram, the EP. Initially, the EP points at the base, or first address of the activation record instance of the
main program. Subsequently, the run-time system must ensure that it always points at the base of the activation record instance of the currently executing program unit. When a subprogram is
called, the current EP is saved in the new activation record
instance along with the other execution status information. The EP is then set to point to the base of the new activation record
instance. Upon return from the subprogram, the EP is restored from the
activation record instance of the subprogram that has completed its
execution.
Note that the EP currently being used is not stored in
the runtime stack. Only saved versions are stored in the activation record
instances. Because such saved versions are stored with the
other execution status information, the stored EP's are not shown in the
figures of the runtime stack". (p.445)
"The collection of dynamic links present
in the stack at a given time is called the dynamic chain,
or call chain" (p. 447)
"The dynamic chain links together all subprogram
activation record instances in the reverse order in which they were
activated. Therefore, the dynamic chain is exactly what is
needed to reference nonlocal variables in a dynamic-scoped language.
This method is called deep access, because access may
require searches deep in the stack" (p. 461)
Now:
-
The way it is described here, there is no need for the "dynamic link", since the previous stack top is just the location one
below the current EP value. Hence, in order to "destroy" the current activation record, just set the stack top to the location one below
the current EP value.
-
More importantly, "the size cannot simply be subtracted from the stack top pointer to remove the activation record" means that the real size of each activation record is not known in advance, and we cannot just follow the "dynamic chain" in order to implement dynamic scoping. (remember, all offsets are from the beginning of the activation record instance, not the top!)
-
There is nothing mysterious about the "other execution status information": it is the "return address to the calling subprogram", and the static link, both of which are
already shown in the activation records.
THE SOLUTION T
he handling of the EP is described correctly, but there is a missing link! The "dynamic link" in the topmost activation record instance should be just the
saved EP of the calling subprogram, not the old stack top pointer. That way everything falls into place, dynamic chain can now be traced, and the previous stack top is not saved unnecessarily.
Horn Clauses:
In page 690, it is said that "Horn clauses with empty left
sides, which are often used to state facts, are called headless Horn Clauses.
For example, father(bob,jake)"
We can call "Horn clauses with empty left sides" whatever
we like, but they are certainly not used to state facts! In fact a "headless
Horn Clause" is the negation of a query consisting of a conjunction of atoms.
Facts are Horn clauses without the body!
