Binding Issues

last updated 9/17/15

 


Identifiers

Identifiers are a basic "naming" abstraction in every programming language. Identifiers are not restricted to "variables".  There numerous attributes associated with each identifier.
Attributes  
The properties of an identifier. Below are various attributes of identifiers that may be used. 
Classification  
Identifiers are used in a number of contexts or represent instances of some component of the language (usually static)
e.g., variable, constant, type, procedure, function, field name, label
Type
A variety of distinctions: e.g. data type, size, # of fields (record), # of parameters (procedure), array dimensions and index types (usually static)
Location  

assigned memory address (usually static)

Value  
initial or current (usually dynamic)

 

We keep all of this information in the Symbol Table (the next phase of the compiler project).

In some cases code might need to be generated to track any dynamic values. Of course the value is always the result of code execution.

 

 


Binding

Binding is the association or connection of an attribute to the identifier, and typically we are interested in when the attribute becomes associated to the identifier.

Static binding: occurs typically at compile time, or linking time.
That is, the binding is set once, prior to, or sometimes at the beginning of, execution and remains fixed.

Dynamic binding: occurs at execution time, the attribute value potentially can change.

 

identifiers Algol* based constants Algol* based variables FORTRAN variables LISP pointers Java objects (reference vars)
type static static static dynamic static
location static dynamic static dynamic dynamic
value static dynamic dynamic dynamic dynamic
  *The family of stack based languages includes C/C++, PL/I, Pascal, Modula, etc.

Lifetime is the range of time that an identifier is bound to an attribute. 

 

 


Blocks

A block is defined as "A unit of code typically beginning with a declaration section followed by imperative section of code. The declared variables are local to the block."

Subroutines/procedures/functions/methods are in themselves a block. For some languages, these are the only blocks.

Pascal and FORTRAN  blocks are limited to the MAIN program and procedure (SUBROUTINE) or function (FUNCTION) blocks 
C/C++ and Java defines blocks as anything inside { } which covers methods
Algol and PL/I  define blocks inside BEGIN... END 
(PL/I has a DO ... END that is the same as Pascal's BEGIN ... END and are only statement groups)
C example of localized declaration in a block
for (i=0; i<n-1; i++) /*bubblesort*/
   for (j=0; j<n-(i+1); j++)
    if(a[j] > a[j+1]) { //subtly defined block
int t = a[j];         a[j] = a[j+1];         a[j+1] = t; } /* t is undefined here*/
 

 

 


Declarations

implicit declarations- mere use of the variable (identifier) declares its existence
e.g. variables beginning with letters I-N in FORTRAN are integers; BASIC

explicit declaration - programmer must define the identifier in a declaration section

global - identifier is known throughout all blocks or known at least outside the block

local - identifier is known only within the block in which it was declared

With nested blocks, the association of global or local status is less clear. Thus there can be levels of "local-ness" (my term).

 

 

 

 


Runtime Environments

In block structured languages

Upon entering a block (function call or local block), local variables are allocated on a stack.
Upon exit, this local variable space is popped off the stack.

The Activation Record (or Frame) holds the local variables, along with parameters, machine context and pointers to the previous activation record and the one defining the next outer definition level.
Some activation records on the stack may not be "active".

The lifetime or extent of a variable is its duration of allocation on the stack.

In languages supporting dynamic allocation

Often overlap with BSLs

E.g. new(), dispose() in Pascal and malloc() and free() in C

The memory allocation's extent is the time between new() and dispose().

What is the extent of a dynamically allocated object in Java?

The allocation is found in the heap.

int *p = NULL; 
int *q; 
p = (int *)malloc(sizeof(int)); 
q = p;
Note examples of counting procedure calls.

 

 


Semantics of Variables

r-value = value stored in the variable (the value on the right hand side of an assignment statement)

l-value = address of the variable (only variables are allowed on the l.h.s of an assignment operator)

To get the r-value you must dereference the l-value. Most languages dereference automatically based on context. C allows programmer full control of dereferencing.

& suppresses normal dereferencing in C

int n;
int *p;
int *q;
p = &n;
q = p;

Latter statement is "assignment by sharing" or "shallow copying". Often done in LISP. It is faster to "assign" the value of a variable to another by making the receiving variable just point to the value. Object reference variables in OOPL typically do the same.  Deep copying would be used to override assignment by sharing or shallow copying.

q is an alias of p. Changes to what p points to also changes what q points to.

Problem: Dangling Reference

A dangling reference is a situation that a pointer variable points to an address that no longer is valid or was reassigned by the system to some other purpose.

p=malloc(sizeof(int));
q = p;
free(p); /*p is NULLed, but q is not*/

Garbage Collection

Recovery of heap space. Garbage collection is accomplished by a system process to discover memory in the heap area that is no longer pointed to by any variables. Any such space is returned to the system for further allocation.

Some languages have automatic garbage collection (BASIC string space, LISP, Java); others require the programmer to track the space to be freed (C,Pascal, Ada)

Explicit memory freeing:

 

 


Semantics of Constants

The identifier has no location (in theory), just a value attribute. Static binding.

A constant is symbolic.

Manifest constant is one that can be replaced directly in code (even in embedded in the instructions). Pascal's constants are such. Ada constants defined in routines may vary from call to call which are called dynamic constants.

Java's use of final is a form of dynamic constants.