Lexical Scope, Block Structure & the Run-Time Stack

An identifier refers to the declaration in the textually nearest enclosing block — determined at compile time, regardless of where the procedure is called from:

18.1 Static scoping

An identifier refers to the declaration in the textually nearest enclosing block — determined at compile time, regardless of where the procedure is called from:

(Early LISP used dynamic scoping and would print 2; ALGOL 60's static scoping became the norm for nearly all later languages.)

'begin'
    'integer' x;
    'procedure' show; outinteger(1, x);     'comment' refers to the OUTER x;
    x := 1;
    'begin'
        'integer' x;
        x := 2;
        show                                'comment' prints 1, not 2;
    'end'
'end'

18.2 Activation records

Each block or procedure activation gets an activation record (stack frame) containing:

Local variables and dynamic arrays (with array descriptors / dope vectors holding bounds).

Parameters (values, or thunk pairs for by-name parameters).

Dynamic link: pointer to the caller's frame (for returning).

Static link: pointer to the frame of the lexically enclosing block (for non-local access).

18.3 Static links vs displays

To access a variable declared d levels out, code can follow d static links. Dijkstra ("Recursive Programming", 1960) proposed the display: an array D[0..maxlevel] where D[i] points to the most recent frame at lexical level i, giving constant-time access to any visible variable. Burroughs hardware implemented display registers directly.

Lexical levels:            Run-time stack (growing down):
level 0: program block     [ program block frame ]      <- D[0]
level 1:   procedure a     [ a, k = 10 ]
level 2:     procedure b   [ b ]  static link -> a(k=10)
                           [ a, k = 9 ]                  <- D[1]
                           [ b ]  static link -> a(k=9)  <- D[2]

18.4 goto out of procedures

A goto to a label in an enclosing block must unwind the stack: discard frames until reaching the frame of the block containing the label. This is the ancestor of exception propagation (longjmp in C, throw in C++/Java).

18.5 Procedure parameters carry environments

When a procedure is passed as a parameter, the receiver needs both its code and its environment (static link) — a closure. ALGOL 60 only passes procedures *downwards* (as parameters, never returned or assigned), so the environment is always still on the stack: no heap allocation is needed. This "downward funarg" restriction keeps ALGOL 60 stack-based; languages with first-class functions need heap-allocated closures.

18.6 Block structure benefits

Variables live exactly as long as needed (memory reuse).

Names can be reused safely in different blocks.

Information hiding: helper procedures nested inside the procedure that uses them.

Dynamic arrays sized at block entry.