What is the advantage of lexical addressing in Chapter 5 of SICP?

Question

I am reading SICP now and don't really understand the necessity of lexical addressing described in 5.5.6 Lexical addressing of SICP.

Since it says "Because our language is lexically scoped, the run-time environment for any expression will have a structure that parallels the lexical structure of the program in which the expression appears", I think it costs same to search a variable in run-time environment as to search in compile environment. Why do we bother to implement a compile environment? I think the compile environment will have the same structure that parallels the lexical structure of the program and this is same as run-time environment, isn't it?

Answer 1

Lexical addressing is useful for speeding up variable lookup. Without lexical addressing, looking up for a variable entails traversing the current environment's frame, or its enclosing environment's frame and so on, all at runtime - because we don't know where the variable was bound, if at all. This is mentioned in the book:

Our compiler, as we have implemented it so far, generates code that uses the lookup-variable-value operation of the evaluator machine. This searches for a variable by comparing it with each variable that is currently bound, working frame by frame outward through the run-time environment. This search can be expensive if the frames are deeply nested or if there are many variables.

By contrast, the procedure for lexical addressing lookup knows exactly where to find a variable at compile time, reducing considerably the time required to find a variable:

lexical-address-lookup takes as arguments an environment and a lexical address that consists of two numbers: a frame number, which specifies how many frames to pass over, and a displacement number, which specifies how many variables to pass over in that frame. Lexical-address-lookup will produce the value of the variable stored at that lexical address relative to the current environment. If we add the lexical-address-lookup operation to our machine, we can make the compiler generate code that references variables using this operation, rather than lookup-variable-value.