{"id":110925,"date":"2025-03-03T07:00:00","date_gmt":"2025-03-03T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110925"},"modified":"2025-03-03T11:01:10","modified_gmt":"2025-03-03T19:01:10","slug":"20250303-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20250303-00\/?p=110925","title":{"rendered":"Lexically scoped functions accessing parent locals: The display"},"content":{"rendered":"

Some time ago, I discussed how the static chain pointer<\/a> is used to access local variables of lexical parent functions, for languages like Pascal that support it. In a later article, I discussed how the mysterious second parameter to the x86 ENTER<\/code> instruction<\/a> accomplishes the same task, but in a different way.<\/p>\n

There is yet another popular way to implement this feature, known as the display<\/i>, a name that comes from the final paragraph of the paper Recursive Programming<\/i><\/a> by Edsger Dijkstra.\u00b9<\/p>\n

The idea is that you have a reserved array of pointers known as the display, its size equal to the maximum depth of lexically scoped functions. If a function has inner functions, then it stores a pointer to its stack frame in the display at an index corresponding to its depth, where the “depth” of a function is the number of enclosing lexical parent functions. For example, a global function has depth zero since it has no lexical parents. When the function returns it restores the original value to the display slot.<\/p>\n

Let’s walk through this design with our example.<\/p>\n

function Outer(n: integer) : integer;\r\n    var i: integer;\r\n\r\n    procedure Update(j: integer);\r\n    begin\r\n        i := i + j\r\n    end;\r\n\r\n    procedure Inner(m: integer);\r\n\r\n        procedure MoreInner;\r\n        begin\r\n            Update(m)\r\n        end;\r\n\r\n    (* Inner body begins here *)\r\n    begin\r\n        MoreInner\r\n    end;\r\n\r\n(* Outer body begins here *)\r\nbegin\r\n    i := 0;\r\n    Inner(n);\r\n    Outer := i\r\nend;\r\n<\/pre>\n
The function Outer<\/code> is not lexically enclosed in any other function, so its depth is zero. Its lexical children are then assigned a depth depending on how many frames they are away from that starting point.<\/p>\n
\u00a0<\/div>\n\n\n\n\n\n\n\n
Outer<\/td>\n <\/td>\n <\/td>\n <\/td>\nDepth 0<\/td>\n<\/tr>\n
\u2193<\/td>\n\u2198<\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
Update<\/td>\n <\/td>\nInner<\/td>\n <\/td>\nDepth 1<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\nMoreInner<\/td>\n <\/td>\nDepth 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Let’s walk through a call to Outer<\/code>.<\/p>\n
Initially, the display looks like this:<\/p>\n\n\n\n\n\n
0<\/td>\nmystery0<\/td>\n<\/tr>\n
1<\/td>\nmystery1<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The Outer<\/code> function saves the value in display slot zero (mystery0<\/code>) and replaces it with a pointer to its stack frame.<\/p>\n\n\n\n\n\n
0<\/td>\nOuter<\/tt> frame \u2190<\/td>\n<\/tr>\n
1<\/td>\nmystery1<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
When Outer<\/code> calls Inner<\/code>, the Inner<\/code> procedure saves the value in display slot one (mystery1<\/code>) and replaces it with a pointer to the Inner<\/code> stack frame.<\/p>\n\n\n\n\n\n
0<\/td>\nOuter<\/tt> frame<\/td>\n<\/tr>\n
1<\/td>\nInner<\/tt> frame \u2190<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Next, Inner<\/code> calls MoreInner<\/code>. This time, MoreInner<\/code> has no inner functions of its own, so it doesn’t have to do anything with the display.<\/p>\n
Now things get interesting. How does MoreInner<\/code> load the value of m<\/code>? Well, m<\/code> is a parameter in Inner<\/code>‘s stack frame, and Inner<\/code> is at depth one, so MoreInner<\/code> reads the pointer at index 1 in the display pointers and uses it to read m<\/code> from the Inner<\/code> stack frame.<\/p>\n
Okay, now we have a call to Update<\/code>, which is at depth one, so it saves the value in display slot one (which is a pointer to Inner<\/code>‘s frame) and replaces it with a pointer to Update<\/code>‘s frame.<\/p>\n\n\n\n\n\n
0<\/td>\nOuter<\/tt> frame<\/td>\n<\/tr>\n
1<\/td>\nUpdate<\/tt> frame \u2190<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
To find the i<\/code> variable in Outer<\/code>‘s frame, Update<\/code> realizes that Outer<\/code> is a depth zero function, so it looks for the pointer in display slot zero (which is a pointer to Outer<\/code>‘s frame) to locate the i<\/code> variable and add j<\/code> to it.<\/p>\n
Now that the work is done, Update<\/code> restores the saved value to display slot one (Inner<\/code> frame) and returns to MoreInner<\/code>.<\/p>\n\n\n\n\n\n
0<\/td>\nOuter<\/tt> frame<\/td>\n<\/tr>\n
1<\/td>\nInner<\/tt> frame \u2190<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
If MoreInner<\/code> had more work to do, it could use display slots 0 and 1 to access the variables of Outer<\/code> and Inner<\/code>. But it doesn’t. So it just returns.<\/p>\n\n\n\n\n\n
0<\/td>\nOuter<\/tt> frame<\/td>\n<\/tr>\n
1<\/td>\nInner<\/tt> frame<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Similarly Inner<\/code> is finished and restores its saved value to display slot 1 before returning.<\/p>\n\n\n\n\n\n
0<\/td>\nOuter<\/tt> frame<\/td>\n<\/tr>\n
1<\/td>\nmystery1 \u2190<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Finally, Outer<\/code> fetches the value from its i<\/code> variable (which Update<\/code> conveniently updated) and uses it as the return value. Before returning, it restores display slot zero.<\/p>\n\n\n\n\n\n
0<\/td>\nmystery0 \u2190<\/td>\n<\/tr>\n
1<\/td>\nmystery1<\/td>\n<\/tr>\n
2<\/td>\nmystery2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Notice that whenever a depth N<\/var> function is active, only the first N+1<\/var> display slots are meaningful.<\/p>\n
Originally, the display was a global variable with a fixed number of slots, which caps the depth of lexically nested functions.\u00b3 Accessing a variable from an outer frame requires only one added indirection (through the display). It does cost a load from a global variable, which depending on your processor architecture might be easy (if your processor supports absolute addressing or instruction pointer-relative addressing with a large enough reach), or annoying (if you have to calculate the address separately).<\/p>\n
Making the display global precludes multi-threaded operations. Most implementations have the function at depth zero allocate the display in its own frame, then have all inner functions receive the address of that display as a hidden parameter.<\/p>\n
\u00b9 Reading that document has a similar feeling to reading centuries-old scientific documents.\u00b2 The terminology and style of writing is so different that you spend a good amount of mental effort translating the text into modern terminology: “The program for subroutine A<\/i> can only be executed correctly if the current value of the parameter pointer is at the disposal of the arithmetic unit, in other words, the parameter pointer can be regarded as one of the aspects of the state of the arithmetic unit, and it must therefore be recorded amongst the link data.” Translation into modern language: “The frame pointer must be kept in a CPU register and stored in the stack frame.”<\/p>\n
\u00b2 For example, here’s  Proposition IV. Theorem IV<\/a> from Isaac Newton’s Principia<\/i>: “The centripetal forces of bodies, which by equoble motions describe different circles, tend to the centres of the same circles; and are one to the other, as the squares of the arcs described in equal times applied to the radii applied the circles.” In modern terms, this is saying that centripetal acceleration is toward the center of the circle and is proportional to s<\/var>\u00b2\/r<\/var>, where s<\/var> is the distance travelled over a fixed period of time, and r<\/var> is the radius.<\/p>\n
And that’s one of the easy ones! Corollary 6 reads, “If the periodic times are in the sesquiplicate ratio of the radii, and therefore the velocities reciprocally in the subduplicate ratio of the radii; the centripetal forces will be in the duplicate ratio of the radii inversely: and the contrary.” Good luck with that.<\/p>\n
\u00b3 If each module provides its own display, then you can have each module’s display be exactly the size of the deepest lexical nesting in that module.<\/p>\n
\n