Dynamic list for frame pointers and static list of nested activation frames

Question

I am going through the book Compiler Construction by Niklaus Wirth. The following is what I feel to be stated summarily by his lesson on procedure calls:

1. The compilation of a procedure call is the allocation of a block of stack memory. It starts with the base address which is stored in the frame pointer and the local variables are allocated addresses with respect to it with negative offsets.

2. For every procedure the block of stack memory is termed as its stack frame or the activation frame and a DYNAMIC LIST is maintained of the base pointers of the stack frame

Then an illustration of an situation is made where nested procedure calls are made with the following code snippet:

PROCEDURE P; P 0
  VAR x: INTEGER; x 1
  PROCEDURE Q; Q 1
  VAR y: INTEGER; y 2
    PROCEDURE R; R 2
    VAR z: INTEGER; z 3
    BEGIN x := y + z
    END R;
  BEGIN R
  END Q ;
  PROCEDURE S; S 1
  BEGIN Q
  END S;
BEGIN Q; S
END P;

Now it is said that assuming that access of the local variables of R by traversing the dynamic list, it is possible that call to R can be made through the sequence P → S → Q → R. As such a second list of activation records is necessary, denoting the nestedness of the procedures.

Why is it necessary to have a static list of the activation frames of the procedures and the procedures nested in them?

At the end of a procedure, we can restore the value of the frame pointer by taking the previous value in the dynamic list and the return address would be restored from the register where it was saved. I don't see why a static list linking the activation frames of the nested procedure is required.

It has been suggested that the following question :

Static scope and dynamic scope

might be having the answer to my question and the questions are co-duplicate to each other but I would beg to differ as :

The suggested question is more about evaluation strategy of a function , more focused on the implementation of argument passing to functions , however my question can be said to be about "returning the control to the calling procedure" or "linking of nested procedures ". My question basically asks the reasons for which Wirth considers maintaining of one static list as a necessity . The following is the link to With's book and my question is centered around the topic "addressing of variables" in pages 72 and 73 .

ON WHY I SAID THAT MY QUESTION IS MORE ABOUT "returning the control to the calling procedure"

I know Wirth starts up the topic with the problem of accessing the variables of an internal procedure or nested procedure but since the dynamic list of frame pointers is maintained to restore the registers from activation frames on return of control to the calling procedure that is why I said that my question is more about the "returning the control to the calling procedure".

Answer 1

The two links can point to different frame. Consider this variation:

PROCEDURE P;
  VAR x: INTEGER;
  PROCEDURE S;
  BEGIN X := 42
  END S;
  PROCEDURE Q;
  VAR y: INTEGER;
    PROCEDURE R;
    VAR z: INTEGER;
    BEGIN S
    END R;
  BEGIN R
  END Q ;
BEGIN Q
END P;

when calling S in R, it will set the static link pointing to R so that S can return to R and the dynamic link pointing to P so that S can access the correct X.

Answer 2

First, Wirth said about "dynamic" list, while you switch between "static" and "dynamic" through your question. I bet you need to replace it with "dynamic" in each place.

Now what the data structures you need. First, on the call you create activation record for each procedure storing its local variables. On the return from a procedure, you drop the current activation record and return to the last one, so simple stack can efficiently manage that.

But you also need an access to variables from earlier activation records. Now, it's the problem. F.e. stack may contain P->Q->R activation records on one occasion (code path) and Q->P->R on another one. So, you don't have fixed stack offsets for variables in higher-level procedures, unlike variables in the current one.

Now, there are various ways to find these offsets. But speaking from pure theoretical standpoint, you manage the calling sequence and finds latest invocation of procedure P in the sequence. So, this is the dynamic list containing (pointers to) activation records in the current stack. You scan the list looking for the last frame corresponding to P and once you found one, you can address current state of variables local to P. The list may contain other, earlier P invocations, but the current execution context has no access to their variables.

The calling sequence contains just the current list of activation records in the stack, right in the order they are placed in the stack. I.e. it's the same list you manage to be able to return into caller procedure. It just has one more duty - searching for variables from higher-level procedures.