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