Binding

Section 3.1

Names

  • A mnemonic character string used to represent something else
  • Can refer to variables, constants, types, functions, etc
  • Allow programmers to abstract complexity (e.g. memory addresses)

Abstraction

  • Hiding details to create clearer interfaces

Control Abstractions

  • Hide complex executable code
  • Functions, subroutines, and certain macros are examples

Data Abstractions

  • Hide data representation details behind simpler operations
  • Examples are classes and structs

Binding Time

  • A binding is an association between two things
  • Binding time refers to the point when the association is created

Possible Binding Times

  • Language design time
  • Program writing time
  • Compile time
  • Link time
  • Run time

Performance

  • As a general rule, making decisions earlier will make final programs more efficient
  • Earlier binding times generally improve efficiency

Run Time

  • Bindings are not finalized by the time the program begins running
  • Bindings may be altered at runtime

Static and Dynamic Binding

  • Static - any binding determined before runtime
  • Dynamic - any binding determined during runtime

Object Lifetime and Storage

Section 3.2

Key Events

  • Creation and destruction of objects
  • Creation and destruction of bindings
  • Deactivation and reactivation of bindings

Lifetime

  • The period between creation and destruction
  • Object lifetime and binding lifetime may or may not coincide

References

  • Values passed by reference typically have a longer lifetime than their binding
  • Dangling references can occur when a reference outlives the object it points to

Storage Allocation Mechanisms

  • Static - Absolute addresses and exist throughout execution
  • Stack - Allocated and deallocated in LIFO order with matching function calls
  • Heap - Allocated and deallocated at arbitrary times

Static Allocation

  • Global variables
  • Machine code
  • Variables declared static
  • Can be used for local variables in certain languages (e.g. early Fortran without recursion)

Stack Allocation

  • Must be used for local variables to support recursion
  • Function instances get their own stack frame for local variables and other data
#include <stdio.h>

int factorial(int n) {
  if (n == 1) return 1;

  return n * factorial(n - 1);
}

int main(void) {
  for (int i = 1; i < 11; i++) {
    printf("%d! = %d\n", i, factorial(i));
  }
}

Calling Sequence

  • Prolog - Executed initially to prepare the stack
  • Epilog - Executed to put state back as it was before the call

Accessing Stack Variables

  • Addresses are not known at compile time
  • A frame pointer is created to point to the current stack frame
  • Local variable references are offsets to this pointer
Upward-growing call stack

Heap Allocation

  • Required for dynamically allocated data structures
    • Linked data structures (linked lists, trees, graphs, etc)
    • Objects of arbitrary size (documents, images, etc)
  • Heap management is a complex topic

Language Differences

  • Allocation is typically explicit
  • Deallocation is explicit in some language (C,Rust,etc)
  • Some languages specify that deallocation should happen automatically at runtime using garbage collection

Garbage Collection

  • Automatically cleans up objects in memory when they are no longer needed
  • Prevents many common classes of memory bugs
  • Will have some runtime performance cost

Issues Mitigated by Garbage Collection

  • Use after free (dangling references box example)
  • Memory leaks
  • Hard to debug as the problem does not trigger an exception at the root cause, but causes problems later

Heap Allocation in C

  • malloc returns a pointer to allocated heap memory
  • free frees the memory

Example

char* ptr;

// Allocate 100 bytes
ptr = (char*) malloc(100 * sizeof(char));

// Do some things using the memory
// ...

// Free the memory
free(ptr);