Binding time

by Carl Burch, Hendrix College, September 2012

Binding time by Carl Burch is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.
Based on a work at www.cburch.com/books/bind/.

1. Name
2. Scope
3. Types
4. Memory location
5. Values
5.1. Constants
5.2. Generics

System designers often have a choice of when the system should make decisions about how to treat a feature; such a decision is called a binding. Usually, this boils down to making the decision at compile-time based solely on the program text (a static binding) or at run-time based on values computed by the program (a dynamic binding). Technically, we could refine these down to more categories.

at programming time (when the programmer writes the code)
at compile time
at link time (when the compiler assembles the executable file)
at load time (when the operating system starts the program)
at execution time (while the program is running)

The distinction between compile-time, link-time, and load-time is a relatively fine line, however, and we'll think of them all as compile-time decisions.

As an extremely simple example where binding time makes a difference, we could talk about when a value is bound to a subprogram parameter. In the line “puts("bindme");”, the value sent to puts is bound at programming time, when the programmer commits to sending the string bindme to the puts function. As you already know, imperative languages include a feature called a variable that allow this binding to occur at execution time. This allows programs to work with data given by the user, for example.

scanf("%d", &input_num);

printf("%d", input_num);

The compiler cannot determine the value sent to printf at compile-time, and so the binding will be deferred to run-time.

Binding-time decisions come up most often in relation to variables. Variables have several properties:

name
scope (area within the program where it can be used)
type
memory location
value

All of these properties could be determined at compile-time or run-time.

1. Name

The variable name is a relatively static property, but the concept of references or pointers allow other names to refer to the same variable. Having multiple names reference the same variable is called aliasing. Not all languages have aliasing; the original BASIC, for example, has nothing resembling it. In such languages, the name of a variable is fixed, and the only way you can refer to the variable is by using this name.

FORTRAN has something akin to aliasing through its call-by-reference parameters, illustrated by this program that uses and then defines a subroutine named INC.

K = 5

      CALL INC(K)

      WRITE (10, 30) K

30    FORMAT (I5)

      END



      SUBROUTINE INC(I)

      I = I + 1

      END

This program declares a variable named K, then passes it into INC as I. With FORTRAN, I and K are aliases, both referencing the same memory location. So an update to I in INC is updating the same memory location that K references; when the program displays K, a 6 will appear. (By contrast, a straightforward translation of this into C, Java, or Python would not work, since in these languages K would be copied into a different I variable, and later updates to I would have no influence on the K's value. So a basic translation to Java or Python would result in an output of 5.)

Though not a typical design choice, some modern languages also use reference parameters. Many, like C++ and C#, default to value parameters like C, Java, and Python, but give the programmer the option to have reference parameters instead. For instance, we could translate inc into C++ as follows.

void inc(int &i) {

    i = i + 1;

}

Although references give more flexibility to the programmer, there are two major reasons for a language designer to shy away from them. The first is that aliasing makes a program more difficult to read: When a variable can have multiple names, it is more difficult to track how the variable is being used.

The other problem with aliasing is that it prohibits some forms of optimization. Consider the following C++ function.

void sum_array(int &total, int *data, int n) {

    int i;



    total = 0;

    for (i = 0; i < n; i++) {

        total += data[i];

    }

}

A compiler would very much prefer to keep total in register so that accesses to it in each iteration don't involve memory references; the compiler would then put the register contents back into total only after the function completes. This strategy would allow the function to execute much faster. But with total as a reference parameter, one possibility is that total could be a reference to an entry in the parameter array.

sum_array(scores[99], scores, 100);

In this case, sum_array would be different based on whether the compiler places total into a register; if it is kept in memory, then each change to total would modify the array entry scores[99], but if it is in a register, the changes would not affect it. Since optimizations should never affect the behavior of a program (except to make it faster), aliasing prevents the compiler from performing this basic optimization. (This example used reference parameters, but similar problems apply for any aliasing situation.)

2. Scope

A more subtle situation in which binding time makes a difference is in a variable's scope. Scope refers to how a variable's use within a program is bound to a particular variable.

What do you suppose the following Python program displays?

def x():

    print(i)   # x uses i



def y():

    i = 3      # y defines i

    x()



i = 4          # outer program defines i

y()

First, a subtlety of Python: This little program has two variables named i, one defined by the outer program and another defined by the y function. So when y assigns i to be 3, it is changing its own i's value, and the outer program's i is still at its old value of 4.

One possible output is “4”. After all, the when x uses i, the version of i in y is “invisible” to it, since it is nested in a sibling function. If you said this, you were using static scoping, more commonly called lexical scoping.

Some people, however, might reasonably predict “3,” under the reasoning that when x refers to i in line 6, it should refer to the most recently created variable named i, which in this case would be y's version, which holds 3. (The outer program's i variable would have been created earlier, just before entering y.) This is called dynamic scoping.

This is a choice of binding time: With lexical scoping, the decision of to which i to use refers is committed at compile time, whereas with dynamic scoping, this decision is deferred to execution time.

In fact, Python uses lexical scoping, like basically all popular languages today. The most important reason for this is that it allows for subprograms to be understood independently of each other. With dynamic scoping, the fact that x's body uses an externally declared variable called i is crucial to understanding the function's behavior. Secondarily, dynamic scoping tends to be slower than lexical scoping, since it requires a run-time search for the variable of the given name. An additional reason to prefer lexical scoping is that there are no strong reasons to prefer dynamic scoping.

A few languages have used dynamic scoping, including APL, PostScript, and the original version of Lisp. In Lisp, the choice was accidental: The first Lisp interpreter, which was among the first language systems designed, was designed without consideration of the issue, and it just happened that dynamic scoping was more convenient in that interpreter. After experience with the resulting bugs, subsequent Lisp implementations used lexical scoping, and designers of languages since then have been careful to address the issue properly.

3. Types

The binding of types to variables is more controversial. Some programming languages allow programmers to omit the types; the system determines them as the program runs. This is called dynamic typing, and it is the strategy used by Python and JavaScript. C and Java, by contrast, use static typing.

With dynamic typing, a programmer need not mention types at all. For example, below is a Python function that adds together all elements of a list.

def sum_list(nums):

    total = nums[0]

    for n in nums[1:]:

        total += n

    return y

Nothing here constrains the types of the parameter nums. We clearly intend a list of several numbers to be passed into the function. But we could legitimately call sum_list(5): The interpreter will merrily enter the function with nums being 5 and commence executing the code, though it will run into a problem once the code requests nums[0] in the first step; only then will it complain that subscripts can't be applied to an integer. Of course, it wouldn't complain about this if we pass sum_list a list; but if it were a list of dictionaries, the interpreter would complain once it reaches “total += n”.

Things get interesting when we hand sum_list a list of strings like sum_list(["4", "5"]), since Python supports addition on strings (where it catenates them). Given several strings, the function still adds the elements together, and it ends up returning a string like "45". This is obviously not the behavior planned by the programmer who named the parameter nums, but the Python interpreter allows this function to work both for summing numbers and for catenating strings (and for adding together any other types supporting the addition operation).

Dynamic typing has two major advantages. One is that it frees the programmer from the work of associating types with variables. Second, dynamic typing has the advantage of being more flexible — as arguably demonstrated by the sum_list function, which works for a variety of types. Despite these two advantages, many languages choose static typing for a combination of two reasons.

It is nearly impossible to compile a dynamically typed language so that it will run efficiently, since run-time type checking incurs a significant overhead.
Compile-time type verification often leads to error detection by the compiler. Such compiler-detected bugs are preferable to run-time bugs because they occur earlier in the development process and because they do not rely on testing cases to verify their presence.

While static typing is most common in languages intended to be compiled to machine code, dynamic typing is relatively common in languages intended for interpreters. This is because most interpreted languages are intended for small-scale programs in which efficiency is not an issue. Examples of dynamically typed languages include Python, Smalltalk, and Lisp.

Among statically typed languages, the most common way for associating types with variables is to require the programmer to declare their type explicitly. But there are two significant alternatives that free the programmer from declaring types for variables. In the older approach, called implicit declaration, a compiler assumes that any undeclared variable has a type based on the variable name. FORTRAN used this technique: In it, variables beginning with the letters I through N are assumed to be integers, while others are floating-point numbers. A similar version of this technique appears in Perl (though Perl is actually dynamically typed): In Perl, variables representing a single value begin with a dollar sign $, array variables begin with an at sign @, and hash (dictionary) variables begin wtih a percent sign %. Many programmers feel that implicitly declared variables are a poor feature; misspelled variable names easily lead to bugs. (FORTRAN developers today regularly declare their variables before using them.)

A more recent approach is type inference, in which the compiler attempts to infer a variable's type from the surrounding context. In the sum_list function, for example, a type-inferring compiler might notice that nums must be an list since it is subscripted using an integer. (Typically, if the compiler could not infer the types of all variables, it refuses to compile the program, telling the user to resolve some types explicitly.) Type inference is a complicated process for the compiler to perform, but it has the advantage of saving the programmer the effort of writing the types of variables. Haskell is an example of such a language.

4. Memory location

Classically in modern languages, we assign a memory location on the stack to each local variable of a subprogram when the subprogram is entered, and all local variables of a subprogram are removed from the stack when the subprogram exits. Thus, the stack not only tracks the current subprograms we are in the midst of executing, but it also tracks the values of variables for each of these subprograms. This is called stack allocation.

It does not have to be this way, though. In fact, prior to 1960, most programming languages determined the memory location for variables statically, while compiling the program. FORTRAN was among these. Static allocation, as this is called, involves allocating a fixed memory location for every local variable in every subprogram. This incurs some significant memory cost for large programs, in which only a few subprograms are in progress at any given point. Stack allocation allows only those few subprograms' variables to exist in memory, but static allocation has all memory for all subprograms allocated. This is a significant disadvantage of static allocation. Just as significant is the fact that recursion in a language using static allocation is highly inconvenient, since all recursive calls share the same memory location for data. FORTRAN 77, in fact, doesn't allow recursion, though more recent FORTRAN versions do, and even compilers meant for FORTRAN 77 often support it anyway.

Static allocation is rare, and most popular languages today are based on the concept of stack allocation. Several modern languages, though, have chosen to depart from it. The reason is that many modern languages allow a function to create and return a subfunction that accesses variables local to its parent function. Consider, for example, this simple example in Python.

def addc(x):

    def addsub(y):

        return x + y

    return addsub



add5 = addc(5)

add8 = addc(8)

When we call addc(5), the variable x is created with the value 5, but we're not done with x once addc completes: The function returned by addc (and stored in add5) still exists, and we can call add5(13), which would then access addc's x with its old value of 5. We can't store x on the stack, because its value would be lost as soon as addc completes. Similarly, we can't store x statically, because its value would be overwritten on the second invocation of addc. The only reasonably solution is to store the value on the heap.

Having a function as a value with some associated space for the values of its variables is called a closure. Closures are most common as illustrated here, where a function (addc) generates and returns another function (addsub) that references the variables of the first function. More traditional languages tend not to support closures, but they have grown more popular in recent years — JavaScript, Python, and Haskell are three prominent languages where they are used heavily.

Because closures have grown more popular very recently, other languages are trying to add similar features. An early version of Java added an approximation, in which a class can be created in the context of a method.

public static void main(String[] args) {

    int count = 0;   // does not compile unless 'count' is 'final'

    JButton disp = new JButton("Display");

    disp.addActionListener(new ActionListener() {

        public void actionPerformed(ActionEvent e) {

            System.out.println(count);

        }

    });

    JFrame frame = new JFrame();

    frame.getContentPane().add(disp);

    frame.setVisible(true);

}

However, because Java's developers wanted to avoid closures, they required that any method variables used within the inner class must be declared final; that way, the created object can safely copy into itself the current value of any variables that it needs to reference from the ouside method, and main's count variable can be deallocated once main returns (though the ActionListener will still remember that count was given a final value of 0). If they allowed count to be non-final, then we'd need to create a closure.

Plans for the next version of Java include anonymous functions, but it will still retain the requirement that variables used in the anonymous function can't change after the variable is created. (The variable need not be declared final, but the compiler will silently add final to the declaration and refuse to compile if the code changes the variable after its initialization.) This is somewhat restrictive, but it addresses a common point of confusion: When you have a closure, is the current value of the variable saved, or is a reference to the variable changed? More explicitly, for the following Python program, what do you expect to be displayed?

def getfunc():

    x = 3

    def printfunc():

        print(x)

    x = 4

    return printfunc



printer = getfunc()

printer()

When printer is invoked on the last line, we enter printfunc and access x. Do you expect it to display 3, the value of x at the time printfunc is created? Or do you expect it to display 4, the most recent value of x? As it happens, Python will display 4, but a programmer might reasonably expect the function to capture the value of the variable at the time it is created, displaying 3. Java's approach is to simply forbid such programs since the programmer might be expecting either one.

5. Values

For a variable to be useful, it would seem, its value property would have to be bound during run-time; otherwise, what's the point? Nonetheless, there are two important features that permit a variable value to be bound at compile-time: constants and generics

5.1. Constants

Most programming languages provide some mechanism for binding a value to a variable at compile-time, called a constant. In Java, this is done through static final variables. Constants are read-only variables; in the program body, their values cannot be changed.

Constants have two advantages: They enhance readability (the name typically is more meaningful that the number it represents) without injuring the immutable nature of the value, and they allow the compiler to replace the references to the value with the value itself, thus saving memory references within the program. Since constants are a simple feature to include, most languages have some support for the feature. (The only real drawback is that it increases the complexity of the language slightly.)

5.2. Generics

Another, rarer feature related to compile-time variable value bindings is the generic. A generic item is an entity, such as a subprogram or a class, whose behavior depends on compile-time parameters given elsewhere in the program.

C++

While the procedural language Ada introduced the concept of generics, C++ first adapted the idea to object-oriented languages: In C++, you can define a template, which is a parameterized class. Below is an example illustrating a C++ template.

1  #include <stdio.h>



 2  template<class item_type>

 3  class List {

 4  public:

 5      List() { head = NULL; }



 6      int contains(item_type value) {

 7          for(Node *n = head; n != NULL; n = n->next) {

 8              if(n->value == value) return 1;

 9          }

10          return 0;

11      }



12      void add(item_type value) {

13          head = new Node(value, head);

14      }



15  private:

16      struct Node {

17          item_type value;

18          Node *next;

19          Node(item_type val, Node *n) { value = val; next = n; }

20      };

21      Node *head;

22  };



23  int main() {

24      List<int> a;

25      printf("%d\n", a.contains(23));

26      a.add(23);

27      printf("%d\n", a.contains(23));

28      return 0;

29  }

In line 2, we declare a template class, in this case with a single parameter, a type named item_type. Within the class definition, we can refer to this type, as in lines 6, 12, and 19. When we use the template class, we must specify the value of its parameter, as in line 24.

Java

C++ templates, though useful, proved to introduce many complexities to the language, and even today different C++ compilers treat templates differently. In Java, designers wanted to preserve simplicity, and so they chose to omit the feature. But the feature is so useful that the designers finally introduced it in Fall 2004, in version 1.5, after several years of work trying to figure out how best to incorporate it. The class below illustrates Java's generics facility.

1 public class List<ItemType> {

  2     private static class Node<ItemType> {

  3         ItemType value;

  4         Node<ItemType> next;

  5         Node(ItemType val, Node<ItemType> n) { value = val; next = n; }

  6     }



  7     private Node<ItemType> head;



  8     public List() { head = null; }



  9     public boolean contains(ItemType value) {

 10         for(Node<ItemType> n = head; n != null; n = n.next) {

 11             if(n.value.equals(value)) return true;

 12         }

 13         return false;

 14     }



 15     public void add(ItemType value) {

 16         head = new Node<ItemType>(value, head);

 17     }



 18     public static void main(String[] args) {

 19         List<Integer> a = new List<Integer>();

 20         System.out.println(a.contains(new Integer(23)));

 21         a.add(new Integer(23));

 22         System.out.println(a.contains(new Integer(23)));

 23     }

 24 }

It looks quite similar to C++ templates, but under the hood the languages use dramatically different approaches. With C++, when a program uses a template, the compiler uses the template to automatically generate code for that class and compiles this generated code into the executable. Thus if a program uses a template with 10 different type parameters, then the executable will incorporate 10 copies of the template into the executable. With Java, the generic facility exists primarily to facilitate type-checking: The executable code includes only the class compiled to deal with Objects, and after verifying that there are no potential typing problems, the compiler will insert the appropriate casts into the code using the generic.

This has an important implication: The only type parameters can be subclasses of the Object class. This is generally not a problem, unless you want to deal with one of Java's eight primitive types, such as int. In this case, we did, and so we were forced to use Java's Integer class in lines 19–22; this class's objects simply wrap around a int value. (In fact, Java 1.5 also includes a “autoboxing” feature, where it will automatically convert an int value into an Integer object where necessary. We could use this to simplify lines 20–22.)

ML and Haskell

ML and Haskell have another interesting variation on templates, called the polymorphic function. Recall that these languages use type inference. The following Haskell function is to find whether the parameter value occurs in the parameter list.

contains value []     = False

contains value (x:xs) | x == value = True

                      | otherwise  = contains value xs

A Haskell compiler will look at this and notice it can't really determine much about value: We compare it to a list element (x), though, which means that the type of each list element must match up with the value's type. Based on this, it will conclude that value has some type α, and list must be a list of values of the same type α. Moreover, α must be a type that supports equality testing (so the function can't work with value being a function, for example, since Haskell doesn't support testing for function equality). We can use this same function for a variety of values.

contains [23, 25, 26] 24                   -- returns false

contains ["hello", "i'm", "carl"] "carl"   -- returns true

Conclusion

Note that generics are largely beside the point in many dynamically typed languages: The primary purpose of generics is to be able to write code that applies to a variety of types, and this is already possible for most dynamically typed languages. Indeed, dynamically typed languages are typically interpreted, and the distinction between compile-time and run-time is less important for interpreters.

For statically typed languages, though, generics (or templates) are a useful feature for a language to include: Using generics, we can write code that can apply in a larger variety of situations. Note that this is an advantage of dynamic typing also. Generics, however, allow the language to give this advantage while maintaining the static typing that allow compile-time type checking and efficient program execution. The primary reason generics have not been more widespread is their complexity, which increases the learning curve and the difficulty of implementing systems for such languages.