Static (Lexical) vs Dynamic Scoping – Programming Languages and Compilers

All programming languages allow names to be associated with values by means of definitions, and a name is said to be in the ‘scope’ of its definition. When a name is mentioned in a program, its dentition (if any) must be known, in order for its ‘invocation’ to make sense. However, most languages allow names to be redefined in a program; the rules for determining to which definition a name refers, are called the scoping rules.

There are two principal scoping methods: static and dynamic. This essay will firstly explain these two concepts, comparing their similarities and differences. The uses of the two methods will be discussed, illustrating these with code from actual programming languages. Finally the essay will conclude with a critical summary of the advantages and disadvantages of static and dynamic scoping for present day programming problems.

Binding Variables in Programming Languages

Programming languages provide mechanisms that allow access to variables stored in memory through the use of bindings. Bindings exist between a variable name (such as Pi) and a value stored at a location in memory (such as 3.14), illustrated in Figure 1.

Many computer programs allow the use of nested expressions, blocks and loops; when variable names are reused or redefined, the language uses binding mechanisms to manage when these bindings are activated and deactivated [1].

The region or context in which a variable is active can be defined as its scope. Dynamic and Static scoping are two entirely different language paradigms for defining what bindings are active in a referencing environment. The first of these, Dynamic Scoping, maintains a binding between the most recently used name and its variable [2]. Whereas Static, or Lexical, Scoping is where the binding is determined by entirely by the block of code that the name is called in [2,3]. An example contrasting the two methods is shown in Figure 2 – Sum of squares program in C (Adapted).

//Sum of Squares - Computes sum(i^2)
int sumofsquares(int n) 
{ 
    int i = 1; int ret = 0; //A value to hold the return variable 
    while(i>=n) 
    { 
        int n = i*i; // Creates a new binding to a variable named n 
        ret += n; // Adds n to the return value         
        i+=1; 
    } 
    return ret; 
}

void main() 
{ 
    int value = 5; 
    int result = sumofsquares(value);
    printf(“%i”,result); 
} 

Figure 2

On a call to the function sumofsquares(5), the name n will be bound to a variable containing the argument’s value. On the first iteration of the while loop, the value of i*i is bound to a new variable which redefines n. The value has not been overwritten – the old value of 5 still exists in memory, only the name’s binding is altered in this block.

After the first iteration of the while loop, the program checks whether the value of i is less than or equal to n. If the variables are statically scoped, the binding of n–>5 will be re-instantiated as, lexically, the binding of n–>1 is out of scope.

However, if the application uses dynamic scoping, the value of n–> 1 will remain active within the reference environment as this was the last assignment to the variable. In implementation of the application, the while loop will run for ever as the test (i In both dynamic and statically scoped languages, every time a function or block is called, its activation record is pushed onto a call sequence stack [5]. The key difference between these records is the links between the record and its parent: a static link to the function’s lexical parent’s activation record is generated in statically scoped programming languages and a dynamic link to the activation record of the calling function is created in dynamically scoped languages.

Static Scoping

Because active bindings are statically linked to a block’s lexical ancestor’s bindings this scoping method is probably the most intuitive binding mechanism and is featured in most modern and class oriented languages such as Java, C++ and C# [3].

For each lexical block that is entered in code, ancestral bindings are imported or mapped – there are two principal methods for this: static chaining and the display method [5].

Static chaining links a parent’s activation record (and bindings) to the newly entered block of code. Ancestral bindings are effectively imported as pointers to the parents’ binding in a similar manner to a linked list [2]. The display method maintains a table of pointers to the binding’s source activation record rather than lexical parent and operates in constant time – an asymptotic performance improvement for a program which may have many nested procedures. A diagram highlighting the differences between these two methods is shown below:

Using static scoping, the scope of a variable will always be active within the lexical (textural) block of code [6] (such as function or loop) and its children – but never available to the parents of the block. The behaviour of bindings in static scoping is solely defined solely by the structure of the program and not on the order of execution, which allows the bindings can be determined at compile time by examining the code.

The lack of dependence on previously executed code gives statically scoped code an intuitive and predictable nature. Expressions made in languages that use static scoping can more easily be made referentially transparent [5] – blocks of code can be replaced with the value that they return without changing the behaviour of a program [7].

Dynamic Scoping

In languages with dynamic scope, bindings are dependent on the order of which subroutines are called at execution. Because the sequence and flow of control cannot always be predicted in advance, bindings made in dynamically scoped programs cannot be type-checked by the compiler [1]. This is normally deferred until runtime which can make poorly written programs liable to runtime errors or incorrect computational results as highlighted in the explanation of the code in Figure 2.

Dynamic scope can be implemented using either a deep access or shallow access method. In deep access, a stack of all variables is held in memory [3]. For each variable call by name, the chosen binding is the first binding with the correct name closest to the top of the stack (example shown in Figure 5 where n has two stack entries). Shallow access maintains a hash table to a stack for each variable name [6] – access time is now near constant. Although access times can be reduced in deep nesting operations using the shallow access method, there is a more substantial memory overhead for managing these stacks.

Summary

When used properly, neither dynamic nor static scoping should alter the correctness of a program. Both paradigms discussed in this report support O(1) lookups for nested bindings [5,6] meaning that performance could be considered comparable for both methods. The greatest differences between dynamic and static scoping mechanisms are the bindings that are available in the reference environment. In any Turing-complete language, the scoping mechanism cannot limit the computability of a result so it can’t be said that either method is computationally more powerful than the other. However, the fact that functions can be made referentially transparent – internalising local variables [8] – gives static scoping more practical expressivity for the programmer.

Many popular languages (such as Ruby and Perl) allow use of dynamic scoping; however, these languages are not entirely dynamically scoped – variables can exist in dynamic scope through the use of the “local” keyword [9]. Although dynamic scoping has the benefits of the reduced communication overheads between nested calls, some programmers still perceive dynamic scoping to be a nuisance as referential transparency is hard to maintain and getting the “correct” answer from code is often sequence specific. The misunderstanding of dynamic scoping’s behaviour may cause undesirable side effects unknown to the developers – because dynamic scoping is inherently unsafe and cannot be checked until runtime, dynamically scoped languages should be avoided.

Bibliography

[1] Alan Burns Alan Wood. (2012, October) POPL Module Page. [Online]. http://www-module.cs.york.ac.uk/popl/Resources/Lectures/Notes/CurrentYear/

[2] Eric Tanter, “Beyond Static and Dynamic Scope,” in DLS ’09 Proceedings of the 5th symposium on Dynamic languages, New York, 2009, pp. 3-14

[3] Michael Scott, “Programming Language Pragmatics,” in Programming Language Pragmatics, Nate McFadden, Ed. San Francisco, United States of America: Morgan Kaufmann Publishers, 2006, ch. 3, pp. 103-159.

[4] Various. Wikipedia – Scope Code Sample. [Online]. http://en.wikipedia.org/wiki/Scope_(computer_science)

[5] Amruth Kumar Eric Fernandes, “A Tutor on Subprogram Implementation,” Journal of Computing Sciences in Colleges, pp. 36-46, May 2005.

[6] Henry G Baker, “Shallow Binding in Lisp 1.5,” Communications of the ACM, p. 566, July 1978.

[7] Peter Sestoft Harald Soendergaard, “Referential Transparency, Definiteness and Unfoldability,” ACTA INFORMATICA, vol. 27, no. 6, pp. 505-517, January 1990.

[8] Gerald Jay Sussman and Julie Sussman Harold Abelson, “Structure and Interpretation of Computer Science, Second Edition,” in Structure and Interpretation of Computer Science. Cambridge, MA, United States of America: MIT Press, 1996, p. 30.

[9] Larry Wall, “The PERL Programming Language,” NetLabs, 2007.

 

Next post: