Names, Scopes, Binding and Routines

Chapter 3
Names, Scopes and Bindings -- Fall 21

Simple Python code example
More complex Python code example
Perl Example 14_39

Binding Time:

binding: association between two things

name and object
object and attributes

binding time

Most important concept.
What are the different times?

coarse
fine

referencing environment

complete set of bindings in effect at a given point in a program.

Object Lifetime and Storage Management

storage allocation corresponds to the object's lifetime

Possible categories

static objects

memory created by load time
lifetime throughout the program's execution

stack-dynamic objects

memory allocated at runtime
lifetime - LiFo

heap-dynamic objects

memory allocated at runtime
lifetime - arbitrary

explicit -- user must create storage
implicit -- declaring the variable creates storage

Static allocation

l-values statically determined (i.e. by load time)

languages with only static allocation have no recursion

Fortran

int i = 1, j = 2, k = 3;
void alpha() {

int i = 4, x = 5; ...
i += k + x;
...
}; void beta() {

int k = 6;
...
i = j + k;
alpha();
...
}; void main() { ...
beta();
... }

Snapshot of Simplesim executing C2 program

Stack allocation

Automatic variable

Deallocation memory when the variable exits the scope

Memory usage is predictable

LIFO stack

Allows recursion

Activation records (AR), also called frames

Addition field in AR allow each call to a routine to have it's own local data

In order to support mutual recursion the definition and declaration must be able to be separated

    int n;
    int fact(void) {
       int loc;
       if (n>1) {
         loc = n--;
         return loc * fact();
       } else {

         return 1;
       }
    }

    int main(void) {
      read(n);
      if (n>0)
        fact();
      else
        print("input error");
      return 0;
    }

A dynamic link (control link) is a reference (points) to the activation record of the calling routine.

Environment pointer (ep) (also called the frame pointer) is the register which points to the current environment (i.e activation record (local data)) Implementation dependent where in the AR the current the ep points to., we will point to the return address field.

Stack ptr is the register which points to the next free space on the stack (data memory).

Instruction ptr is the register which the address of the instruction currently be executed (in this snapshot) The instruction address is in code memory and not shown.

In reality there is more information in the AR. i.e. temp variables

fact.c real c code

fact.s assembly code for Intel machines produces using

gcc -S -ansi fact.c

DJGPP QuickAsm Programming Guide is an excellent reference.
80386 Dependent Features
Intel Architecture Software Developer�s Manual
DDD - Data Display Debugger - Table of Contents

factsun.s assembly code for bingsuns

Constants

A constant is a language entity that has a fixed value for the duration of it existence.

literals -- representation of values
compile time constant (translation time constants)
static constant (load time constant)
manifest constant (a name for a literal)
elaboration time constants

Ada allows constants to be evaluated during elaboration.

procedure Swap ( x,y: in out INTEGER) is

temp: constant INTEGER := x;

begin

x := y;

y := temp;

end Swap;

Java Constants

class ConstantEx {

void myMethod( int n ) {

final int j = n;

System.out.println(j);

// j =15; is not legal

}

static public void main(String [] a) {

ConstantEx ex = new ConstantEx ();

ex.myMethod( 5 );

}

readonly - runtime
const - compile time

HEAP Storage

Heap (not the data structure heap)

Memory management hard

tradeoff speed vs space

space -- internal vs external fragmentation

allocation algorithm (memory management)

describe

Dangling Reference Problem -- object deallocated too soon

Remember dangling (pointer) reference points to deallocated storage.

references

Creations of two Dangling Pointers ----old C

/* ppp is the address of a pointer */
int * dangle ( int ** ppp) {

int p = 5; int m = 21;
*ppp = &p /* dereference ppp to get the pointer whose address was passed. */
return &m; }
main () {

int k = 17;
int *pm, *pk = &k;
pm = dangle(&pk); //both pm and pk point to deallocated memory. }

Fischer&Grodzinsky, The Anatomy of Programming Languages, page 237

This problem can be prevented by good language design --

Why?
Can any garage collection algorithm prevent this problem?

Garbage collection algorithms

Reference counting [Collins 1960]

cycles not reclaimed [Harold-McBeth 1963]

Tracing Algorithms

Mark and Sweep [McCarthy 1960]
Stop and Copy

Scope

Scope is the region of the program which the variable can be referred to by using its simple name (identifier).
What is the difference between the lifetime of an object and the lifetime of a binding of a name to an object?
What is the difference between lifetime of a binding and scope of a binding?
Static scoping (lexical scoping)

Visibility of variable follows the structure of the blocks they are written in
Does not depend on function calls
free variables (not declared locally) are bound statically
scope hole: when the name bound to an object is hidden by a nested declaration of the same name

{ int hide = 1;

{ float hide = 1.0

}

Ada allows a qualifier to access the outer declared variable.

Ada calls this visibility by selections.

Java allows a qualifier to access a hidden instance/class variable

(pre-99) C only allows declarations at the beginning blocks
Algol 68, C++, Java, C-99 allow declarations anywhere
When does a declaration come in scope?

Java, C and C++ vs C# and Pascal
Java example Scope.java
C example scope.c

What is the difference between declaration and definition ?

Python: scope rules in nested functions:

Simple Nested Functions example
Another Nested Function Example

What is the output ?

print outer()
print i, j

Dynamic scoping

free variables are bound dynamically
visibility of variable depends on sequence of function calls
can not determine from written code
APL, Snobol, early versions of LISP, Perl

Perl : local variables in a functions

There are two different ways to create non global variables.

STATIC Scoping

my function creates a variable

sub sub1 {         my $sum = 0;
        ...
   }
whose

scope is the block

lifetime is from the execution of the myfunction to the end of the execution of the block.

Dynamic Scoping

local creates a non-global variable

sub sub1 {
local $dyn = 0;
...

sub2
# after the call to sub2 the value of $dyn = "wow" }
sub sub2 {
# locations of $dyn is dynamic
$dyn = "wow" }

lifetime is the same as a "my" variable

scope is the block in which it is defined as well as any function directly or indirectly from that block.

local is an unfortunate legacy from earlier versions of Perl and should be avoided.

PERL:: Example 14_39

Raku - Perl 6 FYI

Concepts related to Scope

Aliases

What is it?

Overloading vs Coercion vs Polymorphism

Example

Runtime Support of Nested Blocks and Nested Routines

C, C++ support nested blocks but not nested routines

 int f(void) {

              int x,y,w;

          

              while( ...) {

                 int x,z;

                   ...

                 while (...) {

                     int y;

                  ...

          

                 }

                 if (...) {

                    int x, w;

                     ...

                 }

              }

              if (...) {

                 int a,b,c,d;

                  ...

              }

          }

Pascal, Modula 2, Haskell have nested routines but not nested blocks

Ada and Python have both

Simple Nested Functions example
Figures from Text

Nested routines need to be able to find variable declared in the outer routine.

Referencing environment

Classes of values:

"third class" values can only be only be assigned into a variable.

subroutines in Ada 83

"second class" values can be passed as a parameter or assigned into a variable.

most imperative --Pascal
Nested function passed as arguments

"first class" values: can be returned from a routine, passed as a parameter or assigned into a variable.

C#, most scripting languages and ALL functional languages
closure
Functions are first class in Python
Nested functions as returned values

Other issues with passing functions

Issues - What is the referencing environment of the function passed?
Shallow binding vs Deep binding.
Static scoping is combined with deep binding.

Shallow binding does not make sense with static scoping.

def A(I, P):
    def B():
      print(I)

    # body of A
    if I > 1:
       P()
    else:
       A(2, B)

def C():
    pass # do nothing

A(1, C) # main program I is NOT local to "B".
When P is called it is "B"
The question is --
Where is "B" bound to
the "A" where "B" is declared
or
the "A" where "B" is passed to?

Deep binding :
output 1

Shallow binding:
output 2

Example Scott 155

How could this be implemented at run time?
Why isn't this an issue in C?
Deep Binding Code

Activation Records Whose Size Becomes Known at Unit Activation: C5

Ada allows the size of local arrays to be decided during execution.

Elaboration is the process by which declarations become active when encountered in the flow of control. This entails the creation of a binding. It may also entails the allocation of stack space for local objects, and possibly the assignment of initial values.

The activation record is allocated in several steps

storage for statically know data and descriptors of the dynamic arrays is allocated

when the declaration of the array is encounted, dimensions are entered in the descriptor and the size of the array is evaluated

AR is extended in Free space to include space for the array

the pointer in the descriptor is set to this area

Implementing Dynamic Scoping see here

Chapter 3 Names, Scopes and Bindings -- Fall 21