Nested Function - Implementation

Implementation

There are several ways to implement nested procedures, but the classic way is as follows:

Any non-local object, X, is reached via access-links in the activation frames on the machine stack. The caller, C, assists the called procedure, P, by pushing a direct link to the latest activation of P's immediate lexical encapsulation, (P), prior to the call itself. P may then quickly find the right activation for a certain X by following a fixed number (P.depth - X.depth) of links (normally a small number).

The caller creates this direct link by (itself) following C.depth - P.depth + 1 older links, leading up to the latest activation of (P), and then temporarily bridging over these with a direct link to that activation; the link later disappears together with P, whereby the older links beneath it may come into use again.

Note that P is visible for, and may therefore be called by, C if (P) = C / (C) / ((C)) / etc.

This original method is faster than it may seem, but it is nevertheless often optimized in practical compilers (using displays or similar techniques).

Another way to implement nested functions that is used by some compilers is to convert ("lift") nested functions into non-nested functions (where extra parameters replace the access links) using a process known as lambda lifting during an intermediate stage in the compilation.