Re: PCODE Interpereters 101

sda@rt66.com (Scott Amspoker) writes:
> One interesting aspect of P-code is the manner in which it handled the
> lexical nesting of procedures. Rather than use a "display" (an array
> of frame pointers each corresponding to a lexical level), each stack
> frame contained both a "static link" and a "dynamic link" to previous
> stack frames. The dynamic link was identical to the typical C method
> of pushing the old frame pointer when creating a new frame (i.e. it
> pointed back to the previous stack frame). The static link pointed
> back to the previous stack frame for the next outer procedure
> lexically containing the current procedure.


Right; this was a popular implementation for a lot of Pascal systems,
not only P-code. I don't think it was original with Pascal, either.


> I always felt that P-code's static links weren't a very efficient way
> to handle the problem. The PUSH and POP instructions (LOAD/SAVE,
> whatever) contained the lexical level of the variable as well as its
> offset within its stack frame. For "global" variables and variables
> in the current frame, it was reasonably efficient. However, for
> variables somewhere in between, the engine had to follow the static
> links the necessary number of steps to locate the desired frame.


It's been about twenty years since I looked at this carefully, but the
tradeoff you have to make here is the frequency of nonlocal variable
references vs. the frequency of procedure calls. Static links are
cheaper to update at procedure call & return than a "display" array
is; moreover they can be optimized away entirely for outermost-level
procedures. A display array allows cheaper access to more-than-one-
level-out nested local variables, but it offers no advantage for local
variables, global variables, or one-level-out nested locals.


Now maybe the programming styles I'm used to are hopelessly
troglodyte, but I've seen darn few programs other than
recursive-descent compilers that even *have* two-level-nested
procedures, much less programs in which such procedures' access to
their grandparents' locals are so frequent as to be worth improving at
the cost of a slowdown in all procedure calls.


I think the only reason display-style implementations were ever
popular at all is that Wirth's Pascal book described doing it that
way; for most practical purposes static link is superior.


regards, tom lane

Return to the comp.compilers page.
Search the comp.compilers archives again.