Programming Languages CSCI 4430 & CSCI 6969
Names, Scopes, and Binding
Read: Scott, Chapter 3.1, 3.2 and 3.3.1, 3.3.2 and 3.3.6
1
1
Programming Languages CSCI 4430, A. Milanova
2
Lecture Outline
Notion of binding time
Object lifetime and storage management
An aside: Stack Smashing 101
Scoping
Static scoping
Dynamic scoping
Programming Languages CSCI 4430, A. Milanova
3
Scoping
In most languages the same variable name can be used to denote different memory locations
Scoping rules: map variable to location
Scope: region of program text where a declaration is visible
Most languages use static scoping
Mapping from variables to locations is made at compile time
Block-structured programming languages
Nested subroutines (Pascal, ML, Scheme, etc.)
Nested blocks (C, C++ { … })
Programming Languages CSCI 4430, A. Milanova
4
Static Scoping in Block Structured Programming Languages
Also known as lexical scoping
Block structure and nesting of blocks gives rise to the closest nested scope rule
There are local variable declaration within a block
A block inherits variable declarations from enclosing blocks
Local declarations take precedence over inherited ones
Hole in scope of inherited declaration
In other words, inherited declaration is hidden
Lookup for non-local variables proceeds from inner to outer enclosing blocks
4
5
Example – Block Structured PL
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
Nested block structure
allows locally defined
variables and subroutines
main.a, main.b, P.c
main.a,main.b,S.c,S.d
R.a, main.b, main.c
main.P, P.S, main.R
main.P, P.S, S.R
S.R,P.S,main.P
main.R, main.P
5
P.c is an example of hole in scope for main.c.
Visibility of procedures is the same as visibility of variables –
nested procedures are only knowable by the procedures that
Would be able to access them if they were declared variable.
Programming Languages CSCI 4430, A. Milanova
6
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)
7
Example with Frames
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*/
main
—
—
a
b
c
at /*1*/
fp – currently
active frame
sp
top
at /*2*/, main calls
main.P
8
Example
main
—
—
a
b
c
main.P
c
fp
sp
top
at /*3*/
dynamic link
(control link; called-by chain)
static link
(access link; static environment)
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*/
8
Within procedure P, uses of a are main.a,
uses of b are main..b and uses of c are P.c
9
Example
main
—
—
a
b
c
main.P
c
main.R
a
fp
sp
at /*5*/
at /*4*/,
P calls main.R
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*/
9
within procedure r.main, accesses to a are to r.main.a,
to b are to main.b and to c are main.c
10
Example
at /*6*/ main.R exits
sp fp
fp old fp
in main.R’s frame
main
—
—
a
b
c
main.P
c
fp
sp
top
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*/
11
Example
at /*7*/,
P calls P.S;
at /*8*/:
main
—
—
a
b
c
main.P
c
P.S
c
d
fp
sp
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*/
11
in s, references to c and d are local; to a, b, are to main’s variables
12
Example
main
a
b
c
main.P
c
P.S
c
d
S.R
fp
sp
at /*9*/ S calls
in S.R; at /*10*/
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*/
13
Example
main
a
b
c
main.P
c
P.S
c
d
fp
sp
/*11*/ pop S.R’s frame
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*/
14
Example
main
a
b
c
main.P
c
fp
sp
/*12*/pop S’s frame
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*/
15
Example
main
a
b
c
sp
fp
/*13*/ pop P’s frame
/*14*/ pop main’s frame
so that sp fp
at /*13*/
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*/
Static Link vs. Dynamic Link
Static link for a frame of subroutine P points to the most recent frame of P’s lexically enclosing subroutine
Bookkeeping required to maintain the static link
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
To find non-local variables, follow static chain
Dynamic link points to the caller frame, this is essentially old fp stored on frame
Programming Languages CSCI 4430, A. Milanova
16
Not always guaranteed lexically enclosing subroutine still on stack!!!
16
Programming Languages CSCI 4430, A. Milanova
17
Observations
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
Used to implement static scoping using a display
Dynamic link may point to a different subroutine’s frame, depending on where the subroutine is called from
An Important Note!
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
When subroutines (functions) are third-class values, it is guaranteed the static reference environment is on the stack
I.e., a subroutine cannot outlive its reference environment
Programming Languages CSCI 4430, A. Milanova
18
An Important Note!
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
We will return to scoping later during our discussion of functional programming languages
Programming Languages CSCI 4430, A. Milanova
19
Programming Languages CSCI 4430, A. Milanova
20
Dynamic Scoping
Allows for local variable declaration
Inherits non-local variables from subroutines that are live when current subroutine is invoked
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
(old) Lisp, APL, Snobol, Perl
21
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()
end main
Which a is modified at /*1*/
under dynamic scoping?
Z.a or W.a or both?
22
Example
main calls Z,
Z calls Y,
Y sets Z.a to 0.
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()
end main
23
Example
main calls W,
W calls Y,
Y sets W.a to 0.
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()
end main
24
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
Static vs. Dynamic Scoping
main
—
—
a
b
c
main.P
c
main.R
a
Static Scoping:
a bound to R.a,
b to main.b,
c to main.c
Dynamic Scoping:
a bound to R.a,
b to main.b,
c to P.c
24
Dynamic Scoping
Dynamic scoping is considered a bad idea. Why?
More on static and dynamic scoping to come!
Programming Languages CSCI 4430, A. Milanova
25
The End
Programming Languages CSCI 4430, A. Milanova
26
/docProps/thumbnail.jpeg