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?

Dielectric

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.

Griselgriselda

Thank you very much! Think got the point. Save run time searching cost by using the information namely, lexical address that can be acquired at compile time. – Dielectric

@Dielectric you're welcome! Please don't forget to accept the answer to your questions that you consider to be correct, by clicking on the check mark to its left. – Snorter

Assuming a linked-list based environment, If I'm getting it right, the optimization is to navigate an exactly known number of nodes of the list, versus navigating each node of the list checking one-by-one to see if you found the binding, aren't both of these O(n)? (even though in practice the lexical addressing should be faster). The advantage would seem more significative if there was an O(1) way of reading the environment address... – Pryer