Name, Scope and Binding (2)

In Text: Chapter 5

N. Meng, F. Poursardar
 Variable
• A program variable is an abstraction of a memory cell
or a collection of cells
• It has several attributes
– Name: A mnemonic character string
– Address
– Type

2
 Variable Attributes (continued)
• Storage Bindings
– Allocation
o Getting a memory cell from a pool of available memory to bind to
a variable
– Deallocation
o Putting a memory cell that has been unbound from a variable back
into the pool
• Lifetime
– The lifetime of a variable is the time during which it is
bound to a particular memory cell

3
 Object Lifetime and Storage Management
• Key events: creation of objects, creation of bindings, references to
variables (which use bindings), (temporary) deactivation of bindings,
reactivation of bindings, destruction of bindings, and destruction of
objects.

• Binding lifetime: the period of time from creation to destruction of

a name-to-object binding.
• Object lifetime: the time between the creation and destruction of
an objects is the object’s lifetime:
– If object outlives binding it's garbage.
– If binding outlives object it's a dangling reference.

• Scope: the textual region of the program in which the binding is

active; we sometimes use the word scope as a noun all by itself,
without an indirect object.
 Lifetime
• If an object’s memory binding outlives its access
binding, we get garbage
• If an object’s access binding outlives its memory
binding, we get a dangling reference

• Variable lifetime begins at allocation, and ends at

deallocation either by the program or garbage
collector

5
 Categories of Variables by Lifetimes

• Static
• Stack-dynamic
• Explicit heap-dynamic
• Implicit heap-dynamic
 Storage Allocation Mechanisms
• Static: objects are given an absolute address that is
retained throughout the program’s execution.
• Stack: objects are allocated and deallocated in last-in,
first-out order, usually in conjunction with subroutine
calls and returns.
• Heap: objects may be allocated and deallocated at
arbitrary times. They require a more general (and
expensive) storage management algorithm.
 Static Allocation
• Static memory allocation is the allocation of memory
at compile time before the associated program is
executed
• When the program is loaded into memory, static
variables are stored in the data segment of the
program’s address space
• The lifetime of static variables exists throughout
program execution
– E.g., static int a;

8
 Static Allocation
• Advantage
– Efficiency

• Disadvantage
– Reduce flexibility
– No support for recursive subprograms
– No memory sharing among variables

9
Stack-Based Allocation for Subroutines
 Stack-based Allocation
• The location of local variables and parameters can be
defined as negative offsets relative to the base of the
frame (fp), or positive offsets relative to sp
• The displacement addressing mechanism allows such
addition to be specified implicitly as part of an ordinary
load or store instruction
• Variable lifetime exists through the declared method

11
 Heap-based Allocation
• Heap
– A region of storage in which subblocks can be allocated
and deallocated at arbitrary time
– Its organization is highly disorganized because of the
unpredictability of its use
• Heap space management
– Different strategies achieve different trade-offs between
speed and space

12
 Heap-based Allocation
• Explicit heap-dynamic variables are nameless
(abstract) memory cells that are allocated and
deallocated by explicit run-time instructions written by
the programmer.
• An example (C++):
int *intnode; // Create a pointer
intnode = new int; // Create the heap-dynamic variable
...
delete intnode; // Deallocate the heap-dynamic variable
// to which intnode points

• Usage: to construct dynamic structures,

– such as linked lists and trees, that need to grow and/or shrink
during execution

13
 Heap-based Allocation
• Implicit heap-dynamic variables are bound to heap
storage only when they are assigned values.
• All their attributes are bound every time they are assigned.
• Example (JavaScript):
highs = [74, 84, 86, 90, 71];
• Advantage of such variables is that they have the highest
degree of flexibility, allowing highly generic code to be written.
• One disadvantage of implicit heap-dynamic variables is the
run-time overhead of maintaining all the dynamic attributes,
which could include array subscript types and ranges, among
others

14
 Garbage Collection
• Allocation of heap-based objects: triggered by some specific operation in a
program (e.g., object instantiation).

• Deallocation: explicit in some languages (e.g., C++), implicit in others (e.g.,

Java).

• Garbage collection mechanism identifies and reclaims unreachable objects

(implicitly deallocated).

• Explicit deallocation benefits: simplicity and execution speed provided that

the programmer can correctly identify the end of an object’s lifetime.

• Implicit deallocation (automatic garbage collection) benefits: eliminates

manual allocation errors such as dangling reference and memory leak.
 Garbage Collection Algorithms
• Reference Counting
– Keep a count of how many times you are referencing a
resource (e.g., an object in memory), and reclaim the space
when the count is zero
– It cannot handle cyclic structures
– It causes very high overhead to maintain counters

16
 Garbage Collection Algorithms
• Mark-Sweep
– Periodically marks all live objects transitively, and sweeps
over all memory and disposes of garbage
– Entire heap has to be iterated over
– Many long-lived objects are iterated over and over again,
which is time-consuming

17
 Garbage Collection Algorithms
• Mark-Compact
– Mark live objects, and move all live objects into free space
to make live space compact
– It takes even longer time than mark-sweep due to object
movement

18
 Garbage Collection Algorithms
• Copying
– It uses two memory spaces, and each time only uses one
space to allocate memory, when the space is used up, copy
all live objects to the other space
– Each time only half space is used

19
 Space Concern
• Fragmentation
– The phenomenon in which storage space is used inefficiently
– E.g., although in total 6K memory is available, there is not a
4K contiguous block available, which can cause allocation to
fail

20
 Space Concern
• Internal fragmentation
– Allocates a block that is larger than required to hold a given
object
– E.g., Since memory can be provided in chunks divisible by 4, 8,
or 16, when a program requests 23 bytes, it will actually gets 32
(2^8) bytes
• External fragmentation
– Free memory is separated into small blocks, and the ability to
meet allocation requests degrades over time

21
 Declaration Order
• C99, C++, Java, and C# allow variable declarations to
appear anywhere a statement can appear
– In C99, C++, and Java, the scope of all local variables is
from the declaration to the end of the block

22
 Declaration Order
Examples (C#)
{int x;
. . .
{int x; //illegal
. . .
}
. . .
}
void fun() {
. . .
for (int count = 0; count < 10;
count++){
. . .
}
. . .
}
23
 Declaration Order (continued)
– In C#, the scope of any variable declared in a block is the
whole block, regardless of the position of the declaration
in the block
o However, a variable still must be declared before it can be used
– In C++, Java, and C#, variables can be declared in for
statements
o The scope of such variables is restricted to the for construct

24
 Scope
• The scope of a variable is the range of statements over
which its declaration is visible
• A variable is visible in a statement if it can be referenced
in that statement
• The nonlocal variables of a program unit or block are
those that are visible but not declared in the unit
• Global versus nonlocal

• Two types of scope

– Static/lexical scope
– Dynamic scope

25
 Scope Rules
• Scope: a program section of maximal size in which no
bindings change, or at least no re-declarations are
permitted.
• In most languages with subroutines, we open a new
scope on subroutine entry:
– Create bindings for new local variables.
– Deactivate bindings for global variables that are re-declared
(these variable are said to have a “hole” in their scope).
– Make references to variables.
• On subroutine exit destroy bindings for local variables
and reactivate bindings for global variables that were
deactivated.
26
 Static Scope
• The scope of a variable can be statically determined,
that is, prior to execution
• Two categories of static-scoped languages
– Languages allowing nested subprograms: Ada, JavaScript,
Python, and PHP
– Languages which does not allow subprograms: C, C++, Java

27
 Static Scope
• To connect a name reference to a variable, you must
find the appropriate declaration
• Search process
1. search the declaration locally
2. If not found, search the next-larger enclosing unit (static
parent or ancestors)
3. Loop over step 2 until a declaration is found or an
undeclared variable error is detected

28
 An Example (Ada)
1. procedure Big is
2. X : Integer;
3. procedure Sub1 is
4. X: Integer; • Which declaration does X
5. begin -- of Sub1
6. …
in line 10 refer to?
7. end; -- of Sub1
8. procedure Sub2 is
9. begin -- of Sub2
10. …X…
11. end;-- of Sub2
12. begin -- of Big
13. …
14. end; -- of Big
29
 Variable Hiding
• Variables can be hidden from a unit by having a
“closer” variable with the same name
– “Closer” means more immediate enclosing scope
– C++ and Ada allow access to the “hidden” variables (using
fully qualified names)
o scope.name
• Blocks can be used to create new static scopes inside
subprograms

30
 Dynamic Scope
• Dynamic scoping is based on the calling sequence of
subprograms, not on their spatial relationship to each
other
• Dynamic scope can be determined only at runtime
• Always used in interpreted languages, which does not
have type checking at compile time

31
 An Example
program foo; What value is printed?
var x: integer;
procedure f; Evaluate with static
begin scoping:
print(x);
x=1
end f;
procedure g;
var x: integer; Evaluate with dynamic
begin scoping:
x := 2;
x=2
f;
end g;
begin
x := 1;
g;
end foo.
32
 Static vs. Dynamic Scoping
Static scoping Dynamic scoping
Advantages 1. Readability Some extra
2. Locality of convenience (minimal
reasoning parameter passing)
3. Less runtime
overhead
Disadvantages Less flexibility 1. Loss of readability
2. Unpredictable
behavior
3. More runtime
overhead
33
 Another Example
void printheader() {
What is the static scope of
…
} sum?
void compute() {
What is the lifetime of sum?
int sum;
…
printheader();
}

34
 Referencing Environment
• At any given point in a program’s execution, the set
of active bindings is called the current referencing
environment.
• The referencing environment is principally
determined by static or dynamic scope rules.
• Sometimes it may depend on deep and shallow
binding related to the passing of parameters to
subroutines.

35
 Referencing environments in static-
scoped languages

• The variables declared in the local scope plus the

collection of all variables of its ancestor scopes that are
visible, excluding variables in nonlocal scopes that are
hidden by declarations in nearer procedures

36
An Example
1. procedure Example is
2. A, B : Integer; What are the referencing
3. … -------------------------1 environments of the
4. procedure Sub1 is
indicated program points?
5. X,Y: Integer;
6. begin -- of Sub1 Point RE
7. … ----------------2 1. A and B of Example
8. end; -- of Sub1 2. A and B of Example, X and
9. procedure Sub2 is Y of Sub1
10. X: Integer; 3.
11. begin -- of Sub2 4.
12. … ----------------3
13. end; -- of Sub2
14. begin -- of Example
15. … -----------------------4
16. end; -- of Example 37
Referencing environments in dynamic-
scoped languages
• A subprogram is active if its execution has begun
but has not yet terminated
• The referencing environments of a statement in a
dynamically scoped language is the locally declared
variables, plus the variables of all other subprograms
that are currently active
– Some variables in active previous subprograms can be
hidden by variables with the same names in recent ones

38
 An Example
1. void sub1() {
2. int a, b; What are the referencing
3. … ------------------------1
environments of the
4. } /* end of sub1 */
5. void sub2() {
indicated program points?
6. int b, c;
7. … -------------------2
8. sub1();
9. } /* end of sub2 */
10.void main() {
11. int c, d;
12. … ----------------3
13. sub2();
14.} /* end of main */
39
 The meaning of names within a scope
• Within a scope,
– Two or more names that refer to the same object at the
same program point are called aliases
o E.g., int a =3; int* p = &a, q = &a;
– A name that can refer to more than one object at a given
point is considered overloaded
o E.g., print_num(){…}, print_num(int n){…}
o E.g., complex + complex, complex + float

40
 Named Constants
• A named constant is a variable that is bound to a
value only once
• Advantages: readability and modifiability
• Used to parameterize programs
• The binding of values to named constants can be
either static (called manifest constants) or dynamic

41
 Parameterize a Program
void example() {
void example() { final int len = 100;
int[] intList = new int[100]; int[] intList = new int[len];
String[] strList = new String[100]; String[] strList = new String[len];
. . . . . .
for (index = 0; index < 100; for (index = 0; index < len;
index++) { index++) {
. . . . . .
} }
. . . . . .
for (index = 0; index < 100; for (index = 0; index < len;
index++) { index++) {
. . . . . .
} }
. . . . . .
average = sum / 100; average = sum / len;
. . . . . .
} }

Using a named constant as a program

parameter 42
 Named Constants (continued)
• Languages:
– C++ and Java: allow dynamic binding of values to named
variables
o final int result = 2 * width + 1; (Java)
– C# has two kinds, readonly and const
o the values of const named constants are bound at compile time
o the values of readonly named constants are dynamically bound

43