Names, Scopes, and Bindings Oh My!

Binding

  • A binding is an association between two things, such as a name and the thing it names.
  • Binding time is the time at which a binding is created, or more generally, any implementation decision is made. Here are the different possible binding times:
    • Language design time (e.g., control-flow constructs), language implementation time (e.g., number of bits of precision for fundamental types), program writing time, compile time, link time (e.g., a name in one module that refers to an object in another module linked by a compiler), load time, and run time.

Object lifetime and storage management

Distinguish between names and objects to which they refer

Lifetime and Scope

  • Lifetime of a name-to-object binding is the period of time from its creation to destruction
  • garbage is what you get if an object outlives its binding
  • dangling reference is what you get if a binding outlives its object
  • The scope of a binding is the region of the program in which the binding is active

Storage allocation

  • static: an object is given an address that is maintained throughout program execution
  • stack: memory for objs allocated in last-in, first-out order, with subroutine calls and returns
  • heap: blocks can be allocated and deallocated at arbitrary times

Typically use stack allocation for local variables, parameters of procedures, temporaries. Benefits are ability to reuse space, allows for recursive routines. Languages that don’t support recursion, such as older Fortran, can statically allocate local variables because only one invocation of a subroutine can ever be active at a time.

Stack allocation

Typical, uses stack and frame pointers. The stack pointer register points to the first unused location on the stack (or the last used location on some machines) and the frame pointer register points to a known location within the frame of the current subroutine.

Heap-based allocation

Chunk of memory that OS has to allocate and deallocate. Have to deal with internal and external fragmentation (OS topic! Remember this? (Kind of…)) If you allocate big chunks of memory (larger than required to hold a given object), when you deallocate you won’t externally fragment, but you will have internal fragmentation (wasted memory). External fragmentation occurs when the blocks that have been assigned to active objects are scattered through the heap in such a way that unused space is composed of multiple blocks, but no one piece may be large enough to satisfy some future request.

Various methods exist to implement heap allocation. Most use some combination of linked-lists for unused blocks of different sizes to balance finding the best fit in a short amount of time. As fragmentation is unavoidable, there are compaction schemes for reconfiguring the block layout.

Deallocation

When deallocation is not explicit, there is garbage collection upon exiting scope.

Explicit deallocation has simpler compiler implementation and better execution speed. But subject to dangling references and memory leaks due to programmer error.

Implicit deallocation simplifies the programming task. No dangling references with garbage collection. Fewer memory leaks but may still occur if the programmer keeps references to unneeded objects. Garbage collection is getting better.

Scope

The scope of a binding is the part of the program (textually) in which the binding is active. More precisely, a program section of maximal size in which no bindings change (or at least in which no re-declarations are permitted)

  • elaboration is the process by which declarations become active (when control enters a scope)
  • referencing environment is the set of active bindings (at a given point in the programs execution) determined by static and/or dynamic scope rules
  • binding rules - when a reference to a subroutine S is stored, passed as a parameter, etc. These determine which referencing environment used when S is executed. The two principal options are deep binding, in which the choice is made when the reference is first created, and shallow binding, in which the choice is made when the reference is finally used.

Static vs. Dynamic scoping

  • Statically scoped (lexically scoped) - scope determined by lexical structure. All bindings for identifiers can be resolved by examining the program. Typically choose the most recent active binding made at compile time. Used by most compiled languages.
  • Dynamically scoped - scope determined at runtime and depends on flow of execution
  • Global and local variabes are examples of static scopes