Implementing dynamic scope

  • Association List - uses a stack at runtime. Linear search to find bindings.
  • Hash table - fast lookup but scope entry and exit are more complex

Binding of referencing environment

What if we create a reference to a subroutine?

  • The one active when reference was created? AKA deep binding
  • The one active when subroutine is invoked? AKA shallow binding

Most languages with static scoping use deep binding.

Definitions

A closure is a reference to a subroutine together with a representation of the binding environment. This is necessary with deep binding. With an association list (dynamic scoping), a closure can be represented by a top-of-stack (beginning of A-list) pointer. New bindings created within the subroutine are pushed using a temporary pointer. Implementation with a central reference table is more complicated.

Static scoping and shallow binding aren’t mixed in programming languages, as the combination doesn’t make much sense. For static scoping and deep binding (e.g., Python), a closure for a subroutine saves a pointer to the subroutine’s code together with the static link that the subroutine would use if it were called immediately.

A first class object can be passed as a parameter, returned, and assigned to a variable (e.g., simple types, functions in functional languages). A second class object can be passed but not returned or assigned. Third class objects can’t be passed, returned, or assigned.

See Scott pg. 156 for the Scheme example on why the desire to maintain stack-based allocation is the reason that most imperative languages do not have first class subroutines. For functional programming languages that allow local objects to have unlimited extent (i.e., their lifetimes continue indefinitely), the local objects can only be reclaimed when the garbage collection system is able to prove that they will never be used again.