NAMES, SCOPES AND BINDING A REVIEW OF THE CONCEPTS
Name Binding and Binding Time
Name binding is the associa1on of objects (data and/or code) with names (iden1fiers)
Shape S = new Shape();
The binding of a program element to a par1cular property is the choice of the property from a set of possible proper1es
binding and binding 1mes are the proper1es of program elements that are determined by the defini1on of the language or its implementa1on
The 1me during program formula1on or processing when this choice is made is the binding +me
There are many classes of bindings in programming languages as well as many different binding 1mes
Binding Time
Binding 1mes:
Run 1me (execu1on 1me):
On entry to a subprogram or block
Binding of formal to actual parameters
Binding of formal parameters to storage loca1ons
At arbitrary points during execu1on
binding of variables to values
Dynamic binding
Binding Time
Compile 1me (Sta1c Time)
Declara1ons (programmer ac1on)
Variable names
variable types
program statement structure
Compiler ac1on
Rela1ve loca1on of data objects
Linker ac1ons
Rela1ve loca1on of different object modules
Binding Time
Binding Time
Binding Time
o The sum operator (+)
At compila1on 1me (depending on the type of the operands because of overloading)
o If x is declared integer + means one thing o if x is declared real means something else o + can also be overloaded by the programmer.
o Example (C++): it is possible to specify that + operates on strings:
string operator +(string& a, string& b) { return a.append(b);
}
Binding Time
Shape s= new Shape();
s.getArea();
// The compiler can resolve this method call statically.
Binding Time
public void MakeSomeFoo(object a) { // Things happen...
((Shape) a).getArea();
// You won't know if this works until runtime!}
Binding Time: discussion
• Many of the most important and subtle differences between programming languages involve differences in binding 1me
• The trade off is between sta1c analysis, efficient execu1on and flexibility
• The language comes with a type system. The compiler assigns a type expression to parts of the source program. The compiler checks that the type usage in the program conforms to the type system for the language.
• When efficiency is a considera1on (Fortran, C) languages are designed so that as many bindings as possible are performed during transla1on
• Where flexibility is the prime determiner, bindings are delayed un1l execu1on 1me so that they may be made data dependent
Dynamic Dispatch
" Dynamic dispatch allows the code executed when a message is sent to an object (o.m(x)) to be determined by run-‐1me values.
" interface Shape { ... void draw() { ... } }
class Circle extends Shape { ... void draw() { ... } } class Square extends Shape { ... void draw() { ... } } ...
Shape s = ...; //could be a circle a square, or something else.
s.draw();
" Invoking s.draw() could run the code for any of the methods shown in the program (or for any other class that extends Shape).
" Java, all methods (except for sta1c methods) are dispatched dynamically. In
" C++, only virtual members are dispatched dynamically.
" Note that dynamic dispatch is not the same as overloading, which is usually resolved using the sta1c types of the arguments to the func1on being called.
Objects life1me
Creation of an object
Destruction of an object Creation of a binding
Destruction of a binding Dangling reference
if these two times are interchanged
Program execution time Object lifetime Binding lifetime
Dangling References
Int * p = new int;
Int * q = new int;
// things happen on p and q delete p;
//Other things happens Use(q)
Dangling references
#include<stdio.h>
int *call();
void main(){
int*ptr;
ptr=call();
fflush(stdin);
printf("%d",*ptr);
}
int * call(){
int x=25;
++x;
return &x;
}
Storage Management
Programming languages provide three storage alloca1on mechanisms
o Sta1c
Absolute address retained troughout program’s execu1on
o Stack
Dynamic alloca1on with calls&returns
o Heap
Allocated and de-‐allocated at arbitrary 1me
Sta1c Alloca1on
Global variables
Constants
o manifest, declared (parameter variables in Fortran) or iden1fied by the compiler
Variables iden1fied as const in C can be a func1on of non constants and therefore cannot be sta1cally allocated
Constant tables generated by the compiler for debugging and other purposes
Sta1c Alloca1on
In the absence of recursion, all variables can be sta1cally allocated
Also, can be sta1cally allocated:
o Arguments and return values (or their addresses).
Alloca1on can be in processor registers rather than in memory
o Temporaries
o Bookkeeping informa1on
return address
saved registers
debugging informa1on
Sta1c Alloca1on
Stack-‐based Alloca1on
Needed when language permits recursion
Useful in languages without recursion because it can save space
Each subrou1ne invoca1on creates a frame or ac1va1on record
o arguments
o return address
o local variables
o temporaries
o bookkeeping informa1on
Stack maintained by
o calling sequence
o prologue
o epilogue
Stack-‐based Alloca1on (Cont.)
Una funzione ricorsiva
int Func ( /* in */ int a, /* in */ int b ) {
int result;
if ( b == 0 ) // base case result = 0;
else if ( b > 0 ) // first general case result = a + Func ( a , b -‐ 1 ) ) ;
return result;
}
23
Run-‐Time Stack Ac1va1on Records
x = Func(5, 2);// original call at instruction 100
24
FCTVAL ? result ? b 2 a 5 Return Address 100
original call at instruction 100 pushes on this record for Func(5,2)
Run-‐Time Stack Ac1va1on Records
x = Func(5, 2);// original call at instruction 100
25
FCTVAL ? result ? b 1 a 5 Return Address 50 FCTVAL ?
result 5+Func(5,1) = ? b 2
a 5 Return Address 100
record for Func(5,2) call in Func(5,2) code at instruction 50 pushes on this record for Func(5,1)
Run-‐Time Stack Ac1va1on Records
x = Func(5, 2);// original call at instruction 100
26
FCTVAL ? result ? b 0 a 5 Return Address 50 FCTVAL ?
result 5+Func(5,0) = ? b 1
a 5 Return Address 50 FCTVAL ?
result 5+Func(5,1) = ? b 2
a 5 Return Address 100
record for Func(5,2) record for Func(5,1) call in Func(5,1) code at instruction 50 pushes on this record for Func(5,0)
Run-‐Time Stack Ac1va1on Records
x = Func(5, 2);// original call at instruction 100
27
FCTVAL 0
result 0
b 0
a 5
Return Address 50
FCTVAL ? result 5+Func(5,0) = ? b 1
a 5
Return Address 50
FCTVAL ? result 5+Func(5,1) = ? b 2
a 5
Return Address 100
record for Func(5,0) is popped first with its FCTVAL record for Func(5,2) record for Func(5,1)
Run-‐Time Stack Ac1va1on Records
x = Func(5, 2);// original call at instruction 10028 record for Func(5,2) record for Func(5,1) is popped next with its FCTVAL FCTVAL 5
result 5+Func(5,0) = 5+ 0 b 1
a 5
Return Address 50
FCTVAL ? result 5+Func(5,1) = ? b 2
a 5
Return Address 100
Run-‐Time Stack Ac1va1on Records
x = Func(5, 2);// original call at instruction 100
29
FCTVAL 10
result 5+Func(5,1) = 5+5 b 2
a 5 Return Address 100
record for Func(5,2) is popped last with its FCTVAL
Heap-‐based Alloca1on
Region of storage in which blocks of memory can be allocated and de-‐allocated at arbitrary 1mes
Because they are not allocated in the stack, the life1me of objects allocated in the heap is not confined to the subrou1ne where they are created
o They can be assigned to parameters (or to components of objects accessed via pointers by parameters)
o They can be returned as value of the subrou1ne/func1on/
method
Find the errors in this code
Heap-‐based Alloca1on
Several strategies to manage space in the heap
Fragmenta1on
o Internal fragmenta+on when space allocated is larger than needed
o External fragmenta+on when allocated blocks are scahered through the heap. Total space available might be more than requested, but no block has the needed size
Heap-‐based Alloca1on
One approach to maintain the free memory space is to use a free list
Two strategies to find a block for a give request
o First fit: use first block in the list large enough to sa1sfy the request
o Best fit: search the list to find the smallest block that sa1sfy the request
The free list could be organized as an array of free lists where each list in the array contain blocks of the same size
Cells and Liveness
" Cell = data item in the heap
o Cells are “pointed to” by pointers held in registers, stack, global/sta1c memory, or in other heap cells
" Roots: registers, stack loca1ons, global/sta1c variables
" A cell is live if its address is held in a root or held by another live cell in the heap
slide 35
Garbage
" Garbage is a block of heap memory that cannot be accessed by the program
o An allocated block of heap memory does not have a reference to it (cell is no longer “live”)
" Garbage collec1on (GC) -‐ automa1c management of dynamically allocated storage
o Reclaim unused heap blocks for later use by program
slide 36
Example of Garbage
class node { int value;
node next;
}
node p, q;
p = new node();
q = new node();
q = p;
delete p;
slide 37
The Perfect Garbage Collector
" No visible impact on program execu1on
" Works with any program and its data structures
o For example, handles cyclic data structures
" Collects garbage (and only garbage) cells quickly
o Incremental; can meet real-‐1me constraints
" Has excellent spa1al locality of reference
o No excessive paging, no nega1ve cache effects
" Manages the heap efficiently
o Always sa1sfies an alloca1on request and does not fragment
slide 38
Reference Coun1ng: Example
1 root
set
Heap space
2
1 1
1
1 2 1
slide 39
Reference Coun1ng: Cycles
1 root
set
Heap space
1
1 1
1
1 2 1
Memory leak
slide 40
root set
Heap space
Mark-‐Sweep Example (1)
slide 41
root set
Heap space
Mark-‐Sweep Example (2)
slide 42
root set
Heap space
Mark-‐Sweep Example (3)
slide 43
root set
Heap space
Mark-‐Sweep Example (4)
Reset mark bit of marked cells
Free unmarked cells
slide 44
Genera1onal Garbage Collec1on
" Observa1on: most cells that die, die young
o Nested scopes are entered and exited more
frequently, so temporary objects in a nested scope are born and die close together in 1me
" Divide the heap into genera1ons, and GC the younger cells more frequently
o Amor1ze the cost across genera1ons
slide 45
Young
Old root
set A
B
C D
E
F
G
Example with Immediate “Aging” (1)
slide 46
Young
Old root
set
A
B
D
E
F
G
C
Example with Immediate “Aging” (2)
slide 47
Youngest
Oldest To-space
From-space From-space
To-space root
set . . .
Middle generation(s)
Genera1ons with Semi-‐Spaces
SCOPE
Variable
A variable is a loca+on (AKA reference) that can be associated with a value.
Obtaining the value associated with a variable is called dereferencing, and crea1ng or changing the associa1on is called assignment.
Seman1cs of
Programming Languages
Formal Model Graphical
x y z 3.14
“abc”
s fun
Names Env
123 43.21
Store x
y z x s
fun “abc”
Scope and extent
Typed Variables
In sta1cally-‐typed languages, a variable also has a type, meaning that only values of a given type can be stored in it
In dynamically-‐typed languages, values, not variables, have types
Scope rules
The region of the program in which a binding is ac1ve is its scope
Most languages today are lexically scoped
Some languages (e.g. Perl) have both lexical and dynamic scoping
Sta1c Scope -‐ Nested Subrou1nes
In most languages any constant, type, variables or subrou1nes declared within a subrou1ne are not visible outside the subrou1ne
Closest nested scope rule:
a name is known in the scope in which it is declared unless it is hidden by another declara1on of the same name
Sta1c Scope -‐ Nested Subrou1nes (2)
procedure P1(A1: T1);
var X: real;
…
procedure P2(A2: T2);
…
procedure P3(A3: T3);
… begin
… (*body of P3 *) end;
… begin
… (* body of P2 *) end;
…
procedure P4(A4: T4);
…
function F1(A5: T5) : T6;
var X: integer;
… begin
… (* body of F1 *) end;
… begin
… (* body of P4 *) end;
… begin
… (* body of P1 *)
end;
Sta1c Scope -‐ Nested Subrou1nes (3)
To find the frames of surrounding scopes where the desired data is a sta1c link could be used
func1on A() { int I;
func1on B() { int J;
func1on C() { int K;
K=I+J; B(); } C(); } // body of B.
B(); } // body of A.
A calls B calls C calls B calls C.
Sta1c Scope -‐ Nested Subrou1nes (4)
Sta1c Scope -‐ Nested Subrou1nes (5)
ARB4
ARB1 ARB2 ARB3 { /* B1 */!
{ /* B2 */!
{ /* B3 */!
{ /* B4 */!
}!
}!
}!
}!
class Outer { final int x;
class Inner { //int x;
void foo() { x; } }
void bar() { Inner i = new Inner();
int x;
i.foo();
} }
GNU MIPS
gcc MIPS
gcc x386
sp fp
arg1 arg2 ...
argn
return addr old fp local m local m-1
...
local 1
Example
Example: invoca1on
Example
int baz(int x, int y) {
char buf[256];
{
int z = y + 1;
x += z;
}
return x + y;
}
Modules
Modulariza1on depends on informa1on hiding
Func1ons and subrou1nes can be used to hide informa1on. However, this is not flexible enough.
One reason is that persistent data is usually needed to create abstrac1on. This can be addressed in some cases using sta1cally allocated values
Sta1c Scope -‐ Modules (Cont.)
Sta1c Scope -‐ Modules (Cont.)
But modulariza1on oten requires a variety of opera1ons on persistent data.
Sta1c Scope -‐ Modules (Cont.)
Objects inside a module are visible to each other
Objects inside can be hidden explicitly (using a keyword like private) or implicitly (objects are only visible outside if they are exported)
In some language objects outside need to be imported to be visible within the module
Sta1c Scope -‐ Modules Modula-‐2 examples
VAR a,b: CARDINAL;!
MODULE M;!
!IMPORT a; EXPORT w,x;!
!VAR u,v,w; CARDINAL;!
!MODULE N;!
! !IMPORT u; EXPORT x,y;!
! !VAR x,y,z: CARDINAL;!
! !(* x,u,y,z visible here *)!
!END N;!
!(* a,u,v,w,x,y visible here *)!
END M;!
(* a,b,w,x visible here *)!
Modules as types
Dynamic scope
In early Lisp systems variables were bound dynamically rather than sta1cally
In a language with dynamic binding, free
variables in a procedure get their values from the environment in which the procedure is called rather than the environment in which the procedure is defined
Symbol Tables
Symbol tables are used to keep track of scope and binding informa1on about names.
The symbol table is searched every 1me a name is encountered in the source text
Changes occur when a new name or new informa1on about a name is discovered
The abstract syntax tree will contain pointers to the symbol table rather than the actual names used for objects in the source text
Symbol Tables (Cont.)
Each symbol table entry contains
o the symbol name
o its category (scalar variable, array, constant, type, procedure, field name, parameter, etc.)
o scope number
o type (a pointer to another symbol table entry)
o and addi1onal, category specific fields (e.g. rank and shape for arrays)
To keep symbol table records uniform, it may be convenient for some of the informa1on about a name to be kept outside the table entry, with only a pointer to this informa1on stored in the entry
Symbol Tables (Cont.)
The symbol table may contain the keywords at the beginning if the lexical scanner searches the symbol table for each name
Alterna1vely, the lexical scanner can iden1fy keywords using a separate table or by crea1ng a separate final state for each keyword
Symbol Tables (Cont.)
One of the important issues is handling sta1c scope
A simple solu1on is to create a symbol table for each scope and ahach it to the node in the abstract
syntax tree corresponding to the scope
An alter na1ve is to use a addi+onal data structure to keep track of the scope. This structure would resemble a stack:
A C A
B additional
0 2
scope_marker
4 top
2 LL
symbol table
Symbol Tables (Cont.)
A hash table can be added to the previous data structure to accelerate the search.
Elements with the same name are linked from top to bohom.
Search start at the entry of the hash table and proceeds through the linked list un1l the end of the list is reached (old_id) or un1l the link list refers to an element below scope_marker(LL - 1) (new_id)
Symbol Tables (Cont.)
Symbol Tables
Symbol Tables (Cont.)
Associa1on Lists and Central Reference
Tables
The binding of referencing environments
ARP1 ARB1 ARB2 ARB3 ARP2 ARP3 P1()!
{ REAL X!
{ /* B1 */!
{ /* B2 */!
{ /* B3 */!
P2(P3)!
}!
! P3()!
! {!
!x!
! } ! }!
P2(PX)!
{ ! PX()!
}!
}!
}!
PX
