Binding and Scoping
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
Notion of Binding Time
n Binding time (Scott): the time an answer becomes associated to an open question
Programming Languages CSCI 4430, A. Milanova 3
Notion of Binding Time
n Static
n Before program execution
n Dynamic
n During program executes
Programming Languages CSCI 4430, A. Milanova 4
Examples of Binding Time Decisions
n Binding time (Scott): the time an answer becomes associated to an open question
n Binding a variable name to a memory location n Static or dynamic
n Determined by scoping rules
n Binding a variable/expression to a type n Static or dynamic
n Binding a call to a target subroutine
n Static (as it is in C, mostly) or dynamic (virtual calls in
Java, C++)
5
Example: Binding Variables to Locations
n Map a variable to a location
n Map variable at use to a location
n Map subroutine at use to target subroutine
n Determined by scoping rules n Static scoping
n Binding before execution n Dynamic scoping
n Binding during execution n More on scoping later…
int x,y;
void foo(int x)
{
y = x;
int y = 0;
if (y) {
int y; y = 1;
} }
Programming Languages CSCI 4430, A. Milanova 6
General View of Dynamic Binding
n Dynamic binding
n What are the advantages of dynamic binding? n Disadvantages?
n An example: Cost of dynamic binding of call to target method in OO languages
Programming Languages CSCI 4430, A. Milanova 7
Example: Cost of Dynamic Dispatch in C++
n Source: Driesen and Hölzle, OOPSLA’96
a
0
a
c
f
g
5
1
2
6
A
BC
A
B
D
E
a
c
f
3
1
2
a
e
b
d
0
4
7
8
acf
a
e
a
e
0
4
D
EC
ag
bd
Virtual function tables (VFTs)
Capital characters denote classes, lowercase characters message selectors, and numbers method addresses
load [object_reg+#VFTOffset],table_reg
load [table_reg+#selectorOffset],method_reg call method_reg
Programming Languages CSCI 4430, A. Milanova Extra instructions: cost extra 8
Other Choices Related to Binding Time
n Pointers: introduce “heap variables”
n Good for flexibility – allows dynamic structures
n Bad for efficiency – direct cost: accessed indirectly; indirect cost: compiler unable to perform optimizations
n Most PLs support pointers
n Issues of management of heap memory n Explicit allocation and deallocation
n Implicit deallocation (garbage collection)
n PL design choices – many subtle variations n No pointers (FORTRAN 77)
n Explicit pointers (C++ and C)
n Implicit pointers (Java)
9
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 10
Storage Allocation Mechanisms
n Static storage – an object is given absolute address, which is the same throughout execution
n What is an example of static data?
n Stack storage – stack objects are allocated on a
run-time stack at subroutine call and deallocated
at return
n Needs a stack management algorithm n What is an example of stack data?
n Heap storage – long-lived objects are allocated and deallocated at arbitrary times during execution
n Needs the most complex storage management algorithm
Programming Languages CSCI 4430, A. Milanova 11
Combined View
• Static storage: .text (program code), .rodata, .data, etc.
• Stack contains one stack frame per executing subroutine
• Stack grows from higher towards lower memory addresses
• Heap contains objects allocated and not yet de-allocated
• Heap grows from lower towards higher memory addresses
Memory graph courtesy of RPISEC/MBE class.
Runtime Memory
12
.text
.rodata
.data
[heap]
libraries
(libc…)
[stack]
Examples of Static Data
n Program code
n Global variables
n Tables of type data (e.g., inheritance structure)
n Dispatch tables (VFTs) and other tables n Other
Programming Languages CSCI 4430, A. Milanova 13
Examples of Stack Data
n What data is stored on the stack?
n Local variables, including parameters
n Compiler-generated temporaries (i.e., for expression evaluation)
n Bookkeeping (stack management) information
n Return address
Programming Languages CSCI 4430, A. Milanova 14
Run-time Stack
n Stack contains frames of all subroutines that have been entered and not yet exited from
n Frame contains all information necessary to update stack when subroutine is exited
n Stack management uses two pointers: fp (frame pointer) and sp (stack pointer)
n fp points to a location at the start of current frame n In higher memory (but lower on picture)
n sp points to the next available location on stack (or the last used location on some machines)
n In lower memory (but higher up on picture)
n fp and sp define the beginning and the end of the frame
15
Run-time Stack
Programming Languages CSCI 4430, A. Milanova 16
Run-time Stack Management
n Addresses for local variables are encoded as sp + offset
n But may also have fp – offset n Idea:
n When subroutine is entered, its frame is placed on the stack. sp and fp are updated accordingly
n All local variable accesses refer to this frame
n When subroutine is exited, its frame is removed from
the stack and sp and fp are updated accordingly
Programming Languages CSCI 4430, A. Milanova 17
Frame Details
n Arguments to called routines
n Local variables, including parameters
n Temporaries
n Miscellaneous bookkeeping information n Saved address of start of caller’s frame (old fp) n Saved state (register values of caller), other
n Return address
Programming Languages CSCI 4430, A. Milanova 18
Frame Example
void foo(double rate, double initial) {
double position; …
position = initial + rate*60.0; …
return;
}
Assume bar calls foo. Frame for foo:
sp ->
Locals
Temporaries
Misc bookkeeping info
Return address in code of caller
position initial rate
tmp
… old fp
return address
fp ->
19