Lecture_18_NamingBindingStorage
Naming, Binding, and
Storage
CSCI 3136: Principles of Programming Languages
Agenda
• Announcements
• Assignment 7 is out and due July 5.
• Test 2 in class time on July 5.
• Lectures are being recorded
• Readings: Read Chapter 3
• Lecture Contents
• Motivation
• Naming and Binding
• Reference Environments and Scope
• Binding Times
• Object and Binding Lifetimes
• Storage Allocation
2021-06-28 8:38 AM 2
Keywords
Naming
• Name
• Mnemonic
Binding
• Association
Binding Times
• Early Binding
• Late Binding
• Compile time
• Link time
• Load time
• Run time
Scope
• Reference Environments
• Scope of a binding
Binding Lifetime
• Dangling pointers / references
• Memory leaks
Storage
• Allocation
• Deallocation
• Static memory
• Heap
• Dynamic allocation
• Stack
Stack-based allocation
• Subroutines / functions /
procedures / methods
• Caller
• Callee
• Stack frame
• Arguments
• Return address
• Return value
• Local variables
• Temporary variables
• Registers
• Stack pointer
• Base pointer
2021-06-28 8:38 AM 3
End of this Part
CSCI 3136
2021-06-28 8:46 AM 4
Motivation
CSCI 3136
2021-06-28 8:46 AM 5
Motivation
• Programs manipulate data through execution of
code
• Both data and code needs to be identified when
used in the program
• We use names (symbols) to identify the data or
code
• How we link the symbols to the code or data affects
what we can do!
• Question: Fundamentally, is there a difference
between code and data?
2021-06-28 8:38 AM 6
Naming and Binding
• A Name is a (mnemonic) string representing code or
data:
• x, sin, foo, prog1, null? are names
• 42, 3.14, “test”, false, are literals, not names
• +, !=, << . . . are operators and may be names if they are not
built-in
• A Binding is an association between a name and code
or data:
• Name and value (for constants)
• Name and memory location (for variables)
• Name and function
• Name and label (for gotos)
• Names and bindings are stored in a symbol table at
compile time
2021-06-28 8:38 AM 7
Referencing Environment and Scope
• A Referencing Environment is a complete set of
active bindings at a point in a program
• The Scope of a Binding is
• the region(s) of a program or
• time interval(s) in the programs execution
during which the binding is active
• A Scope is a maximal region of the program where
no bindings are destroyed
e.g., body of a procedure
• When do bindings occur?
int foo(int a, int b) {
// Inside the braces is
// the scope of foo
}
2021-06-28 8:38 AM 8
End of this Part
CSCI 3136
2021-06-28 8:38 AM 9
When are Bindings
Created?
CSCI 3136
2021-06-28 8:38 AM 10
Binding Times
• Compile time
• Link time
• Load time
• Run time
2021-06-28 8:38 AM 11
foo.o
Compile-Time Binding
Bindings are encoded in machine code
• Literals are stored in the object file
final static String hello = “Hello, World!\n”;
• Static data
static int [] ThirdYearCore = {3101, 3110, 3120, 3130, 3136, 3171};
• Local (static/private) functions
private int helper( … ) {
...
}
• Gotos / labels
• Switch statements
switch(c) {
case “YES: ...
case “NO”: ...
case “MAYBE”: ...
}
DATA
“Hello, World!\n”
3101, 3110, 3120, 3130,
3136, 3171
CODE
for(…) {
...
goto error
...
}
...
error:
…
2021-06-28 8:38 AM 12
ahchoo.exe
Link-Time Binding
Bindings are initiated by compiler but finalized by linker
• Function calls between separately compiled modules
int qux(…) {
...
bar(...)
...
}
• Global variables
int errno
foo.o
DATA
“Hello, World!\n”
3101, 3110, 3120,
3130, 3136, 3171
CODE
qux:
… call bar
moo.o
DATA
errno: 0
CODE
bar:
…
zoo.o
DATA
PI: 3.141…
CODE
2021-06-28 8:38 AM 13
Boo.dylib
Load-Time Binding
Bindings are finalized when program is loaded
• Static data locations are fixed (if not done by linker)
• Calls to dynamic libraries
• Loading of required classes (Java)
ahchoo.exe
foo.o
DATA
“Hello, World!\n”
3101, 3110, 3120,
3130, 3136, 3171
CODE
qux:
… call bar
moo.o
DATA
errno: 0
CODE
bar:
…
zoo.o
DATA
PI:
3.141…
CODE
Stack
Heap
Data
Code
Data
Code
Loaded Program
2021-06-28 8:40 AM 14
Run-Time Binding
Bindings become active during execution
• Set variables
a = 42;
• Local and temporary variables created on
the stack
int foo(…) {
Object b;
...
}
• Dynamic memory allocation on the heap
(assign references to variables)
b = new Object()
Stack
Heap
Data
Code
a: 42
b
2021-06-28 8:40 AM 15
Early vs Late Binding
• When a name is bound affects the program!
• Early binding : (compile/link/load time)
• Faster code
• Typical in compiled languages
Example
• Functions in C
• Late binding : (run time)
• Greater flexibility
• Typical in interpreted languages
Example:
• Lambda expressions in Scheme, Java, Python, etc
2021-06-28 8:40 AM 16
End of this Part
CSCI 3136
2021-06-28 8:40 AM 17
Object and Binding
Lifetimes
CSCI 3136
2021-06-28 8:40 AM 18
Object and Binding Lifetimes
• Object lifetime : lifetime of code or data
• Binding lifetime lifetime of association between
name and object
2021-06-28 8:40 AM 19
Object Lifetimes
Lifetime of code or data
• Period between creation and destruction of object
Examples:
• Time between allocation (malloc) to deallocation (free) of a piece of
memory
a = malloc(…);
...
free(a);
• Time between start/end of a function call (all local variables)
int foo(…) {
int a;
int b;
int c;
...
}
2021-06-28 8:40 AM 20
Binding Lifetimes
Lifetime of association between name and object
• Period between the creation and destruction of name
to object binding
Examples:
• Assignment to re-assignment of a pointer to memory
a = new Object();
…
a = null;
• Assignment to re-assignment of a function pointer
func = &func_a;
…
func = &func_b;
2021-06-28 8:40 AM 21
Object Lifetimes vs Binding Lifetimes
• Key Idea: Lifetime of bindings typically match lifetime of
objects except in the case of aliases
• Two common mistakes
• Dangling reference : no object for a binding
E.g., a pointer refers to an object that has already been deleted
m = malloc(…);
…
free(m);
// m no longer points to valid memory
• Memory leak : no binding for an object (preventing the object
from being deallocated)
m = malloc(…);
m = NULL;
// memory allocated by malloc no longer accessible
2021-06-28 8:40 AM 22
multiple bindings
to same object
End of this Part
CSCI 3136
2021-06-28 8:40 AM 23
Storage Allocation
CSCI 3136
2021-06-28 8:40 AM 24
Storage Allocation
• Idea: An object’s life-time depends on where it
resides
• Options for Storage:
• Static memory (Data)
• Heap
• Stack
Stack
Heap
Data (Static)
Code
2021-06-28 8:40 AM 25
Static Objects
• Stored at a fixed absolute address
• Lifetime is the whole program execution
• Examples:
• Global variables
• Static variables local to subroutines that retain their value
between invocations
• Constant literals (strings)
• Tables for run-time support: debugging, type checking, etc.
• Space for subroutines, including local variables in languages
that do not support recursion (e.g., early versions of
FORTRAN)
• Allocated at compile/link/load time.
Stack
Heap
Code
Data (Static)
2021-06-28 8:40 AM 26
Objects on the Heap
• Stored on heap
• Created and destroyed at arbitrary times
• Explicitly by programmer
E.g., malloc(), new, free()
• Implicitly by garbage collector
• Examples:
• Objects (Java)
• Dynamically sized memory
• Large objects
Code
Data (Static)
Stack
Heap
2021-06-28 8:40 AM 27
Heap-Based Allocation
• The heap is a region of memory from which
objects can be dynamically allocated
• The heap can grow as memory demands of a
program grow.
• Each program has a heap (memory) manager
• Part of the program’s runtime environment
• Program’s make requests to the heap
manager to allocate and deallocate memory
• In C: malloc() / realloc() / free()
• In C++: new / delete operators
• In Java: new operator
Code
Data (Static)
Stack
Heap
Heap Manager
2021-06-28 8:40 AM 28
Heap-Based De-allocation
Deallocation can take two forms:
• Explicit deallocation by programmer
• Used in Pascal, C, C++
• Efficient
• May lead to bugs that are difficult to find:
• Dangling pointers/references from deallocating too soon
• Memory leaks from not deallocating
• Automatic deallocation by garbage collector
• Used in Java, functional, and logic programming languages
• Can add significant runtime overhead
• Safer
2021-06-28 8:40 AM 29
Objects on the Stack
• Stored on stack in connection with a subroutine /
method / function call
• Lifetime from invocation to return from subroutine
• Allocation is automatic with each call
• Examples:
• All local variables
• Arguments to a function
• Return address
• Temporary values
Heap
Code
Data (Static)
Stack
2021-06-28 8:40 AM 30
End of this Part
CSCI 3136
2021-06-28 8:40 AM 31
Stack-based Allocation
CSCI 3136
2021-06-28 8:40 AM 32
Stack Based Allocation
• Idea: When a subroutine (function) is
called, a stack frame is pushed on the
stack
• Stack Frame contains:
• Arguments passed to the subroutine
• Space for the return value (optional)
• Return address of caller
• Local variables
• Temporary (hidden) variables
• Registers that must be saved across calls
Arg n
…
Arg 2
Arg 1
Return Value
Return Addr
Local var 1
Local var m
Local var 2
…
Saved reg t
Base Pointer
…
Temp var 2
Temp var r
Tem var 1
…
Saved reg 2
Saved reg 1
…
…
…
…
…
…
…
Stack
2021-06-28 8:40 AM 33
Before the Call
Caller
• Pushes arguments on the stack
• Pushes a dummy return value
(optional)
• Executes call instruction
call foo
• Pushes return address on stack
• Jumps to subroutine (callee)
Arg n
…
Arg 2
Arg 1
Return Value
Return Addr
…
…
…
…
…
…
…
Stack
2021-06-28 8:40 AM 34
During the Call
Callee
• Saves base pointer
• Allocates local variables
• Allocates temporary variables
• Saves registers
• Performs body of subroutine
• Restores registers
• Destroys local and temp variables
• Returns
ret
• Pops return address off stack
• Jumps to return address
Arg n
…
Arg 2
Arg 1
Return Value
Return Addr
Local var 1
Local var m
Local var 2
…
Saved reg t
Base Pointer
…
Temp var 2
Temp var r
Temp var 1
…
Saved reg 2
Saved reg 1
…
…
…
…
…
…
…
Stack
2021-06-28 8:40 AM 35
After the Call
Caller
• Pops arguments off the stack
Arg n
…
Arg 2
Arg 1
…
…
…
…
…
…
…
Stack
Return Value
2021-06-28 8:40 AM 36
Stack Management
0xDEADBEEF
3.14
42
Return Addr
Local var 1
Local var m
Local var 2
…
Saved reg t
Base Pointer
…
Temp var 2
Temp var r
Temp var 1
…
Saved reg 2
Saved reg 1
…
…
…
…
…
…
…
• The stack is managed through two
pointers (kept in registers)
• Stack pointer points to the top of the
stack
• Frame (base) pointer points to the
current stack frame
Note: One of the registers typically saved
on the stack is the previous frame pointer
• Example:
call foo(42, 3.14, "Hello")
BP
SP
2021-06-28 8:40 AM 37mov SP, BP; BP = SP
A Linked List of Stack Frames
…
…
…
…
…
…
…
• The stack frames are all linked, from
the current function being executed
all the way back to main()
• Stack frames contain
• Return address of each function
• Arguments passed
• Local variables
• A debugger can easily access all this
information and allow you to debug
your program!
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
BP
2021-06-28 8:40 AM 38