Names, Scopes, and Binding
Read: Scott, Chapter 3.1, 3.2 and 3.3.1, 3.3.2 and 3.3.6
1
Lecture Outline
n Notion of binding time
n Object lifetime and storage management
n An aside: Stack Smashing 101
n Scoping
n Static scoping
n Dynamic scoping
Programming Languages CSCI 4430, A. Milanova 2
Scoping
n In most languages the same variable name can be used to denote different memory locations
n Scoping rules: map variable to location
n Scope: region of program text where a declaration is
visible
n Most languages use static scoping
n Mapping from variables to locations is made at compile time
n Block-structured programming languages
n Nested subroutines (Pascal, ML, Scheme, etc.)
n Nested blocks (C, C++ { … })
Programming Languages CSCI 4430, A. Milanova 3
Static Scoping in Block Structured Programming Languages
n Also known as lexical scoping
n Block structure and nesting of blocks gives rise to
the closest nested scope rule
n There are local variable declaration within a block
n A block inherits variable declarations from enclosing blocks
n Local declarations take precedence over inherited ones
n Hole in scope of inherited declaration
n In other words, inherited declaration is hidden
n Lookup for non-local variables proceeds
from inner to outer enclosing blocks
Programming Languages CSCI 4430, A. Milanova 4
Example – Block Structured PL
main
a, b, c: integer procedure P
c: integer main.a, main.b, P.c main.P, P.S, main.R procedure S
c, d: integer procedure R …
end R
R()
end S
R()
S()
end P procedure R
a: integer
… = a, b, c end R
P()
main.a,main.b,S.c,S.d
S.R,P.S,main.P
main.P, P.S, S.R
Nested block structure allows locally defined variables and subroutines
end main
5
R.a, main.b, main.c
main.R, main.P
main
a, b, c: integer procedure P
c: integer procedure S
c, d: integer procedure R
…
end R
R()
end S
R()
S()
end P procedure R
a: integer
… = a, b, c end R
P()
end main
Rule: a variable is visible
if it is declared in its own block or in a textually surrounding block and it is not ‘hidden’ by a binding in a closer block (i.e., there is no hole in scope)
Programming Languages CSCI 4430, A. Milanova 6
Example with Frames
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
at /*1*/
main —
—
a
b
c
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
top
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
fp – currently active frame
at /*2*/, main calls main.P
sp
7
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
at /*3*/
static link (access link; static environment)
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
fp
sp
main —
—
a
b c
dynamic link (control link; called-by chain)
main.P
c
top
8
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
end S /*12*/
R() /*4*/
S() /*7*/ end P /*13*/
procedure R /*5*/ a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
at /*5*/
main at /*4*/, —
P calls main.R—
a b c
main.P
c
fp
main.R
a
sp
9
at /*6*/ main.R exits sp ¬ fp
fp¬ oldfp
in main.R’s frame
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
fp
sp
main —
—
a
b c
main.P
c
top
10
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
main —
—
a
b c
main.P
c
P.S
c
d
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
at /*7*/,
P calls P.S; fp at /*8*/:
sp
11
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
main
a b c
main.P
c
P.S
c
d
S.R
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
at /*9*/ S calls in S.R; at /*10*/
fp sp
12
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
fp
main
a b c
main.P
c
P.S
c
d
/*11*/ pop S.R’s frame
sp
13
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
fp sp
main
a b c
main.P
c
/*12*/pop S’s frame
14
Example
main
a, b, c: integer /*1*/ procedure P /*3*/
c: integer procedure S /*8*/
c, d: integer procedure R /*10*/ …
end R /*11*/
R() /*9*/
end S /*12*/ R() /*4*/
S() /*7*/
end P /*13*/ procedure R /*5*/
a: integer
… = a, b, c end R /*6*/
P() /*2*/ … end main /*14*/
at /*13*/
fp
main
a b c
sp
/*13*/ pop P’s frame /*14*/ pop main’s frame so that sp ¬ fp
15
Static Link vs. Dynamic Link
n Static link for a frame of subroutine P points to the most recent frame of P’s lexically enclosing subroutine
n Bookkeeping required to maintain the static link
n If subroutine P is enclosed k-levels deep from main, then the length of the static chain that begins at a frame for P, is k
n To find non-local variables, follow static chain
n Dynamic link points to the caller frame, this is
essentially old fp stored on frame
Programming Languages CSCI 4430, A. Milanova 16
Observations
n Static link of a subroutine P points to the frame of the most recent invocation of
subroutine Q, where Q is the lexically enclosing subroutine of P
n Used to implement static scoping using a display
n Dynamic link may point to a different subroutine’s frame, depending on where the subroutine is called from
Programming Languages CSCI 4430, A. Milanova 17
An Important Note!
n For now, we assume languages that do not allow subroutines to be passed as arguments or returned from other subroutines, i.e., subroutines (functions) are third-class values
n When subroutines (functions) are third-class values, it is guaranteed the static reference environment is on the stack
n I.e., a subroutine cannot outlive its reference environment
Programming Languages CSCI 4430, A. Milanova 18
An Important Note!
n Static scoping rules become more involved in languages that allow subroutines to be passed as arguments and returned from other subroutines, i.e., subroutines (functions) are first class values
n We will return to scoping later during our discussion of functional programming languages
Programming Languages CSCI 4430, A. Milanova 19
Dynamic Scoping
n Allows for local variable declaration
n Inherits non-local variables from subroutines that are live when current subroutine is invoked
n Use of variable is resolved to the declaration of that variable in the most recently invoked and not yet terminated frame. I.e., lookup proceeds from closest predecessor on stack to furthest
n (old) Lisp, APL, Snobol, Perl
Programming Languages CSCI 4430, A. Milanova 20
Example
main procedure Z
a: integer
a := 1
Y()
output a end Z
procedure W
a: integer
a := 2
Y()
output a end W
procedure Y
a := 0 /*1*/
end Y
Z()
W()
21
Which a is modified at /*1*/ under dynamic scoping? Z.a or W.a or both?
end main
Example
main procedure Z
a: integer a := 1
Y() output a
end Z procedure W
a: integer a := 2
Y() output a
end W procedure Y
a := 0; /*1*/
end Y
Z()
W()
22
main calls Z,
Z calls Y,
Y sets Z.a to 0.
end main
Example
main procedure Z
a: integer a := 1
Y() output a
end Z procedure W
a: integer a := 2
Y() output a
end W procedure Y
a := 0; /*1*/
end Y
Z()
W()
23
main calls W, W calls Y,
Y sets W.a to 0.
end main
Static vs. Dynamic Scoping
main
a, b, c: integer procedure P
c: integer procedure S
main — —
a
b c
c, d: integer procedure R …
end R
R() end S
R()
S() end P
procedure R
a: integer
… = a, b, c end R
P() end main
24
Static Scoping:
a bound to R.a, b to main.b,
c to main.c
main.P c
main.R a
Dynamic Scoping: a bound to R.a, b to main.b,
c to P.c
Dynamic Scoping
n Dynamic scoping is considered a bad idea. Why?
n More on static and dynamic scoping to come!
Programming Languages CSCI 4430, A. Milanova 25
The End
Programming Languages CSCI 4430, A. Milanova 26