Operational Semantics of Block-Structured Languages: Variables

Robert D. Cameron
January 30, 2002

Four Semantic Attributes of Variables

In general, the semantics of variables in programming languages is often described in terms of four attributes.

Type. A description of the set of permissible values for a variable.
Scope. The region of program text over which a variable is known.
Location. A location in memory associated with the variable.
Value. Typically, an indirect attribute of a variable; the value stored in the memory location associated with a variable.

Static versus Dynamic Binding

Binding is the process of associating an attribute with an entity, either during language processing (e.g., compilation) or during program execution. In general, attributes whose values are fixed during compilation are called statically bound, whereas attributes whose values are determined at run-time are called dynamically bound.

Different choices for attribute binding give rise to a spectrum of semantic possibilities in programming languages.

Attribute Static Dynamic

Type

Attribute	Static	Dynamic
Type	Statically typed languages fix the type associated with each variable at compile time. This permits compile-time type checking, which catches many programming errors before execution. Static typing with dynamic subtyping is common. In this case, the dynamic type of a variable may change during program execution, but only within a set of possible types specified by a statically bound supertype. Pascal, Modula, Ada, Java, C++ are statically typed languages. Dynamic subtyping in Ada is used for range types, generic array instantiation and so on. Object-oriented languages often fix a superclass as a static type, while allowing the subclass to vary dynamically.	Dynamically typed languages allow the programmer to freely assign objects of any type to a variable, even if the variable previously held a value of a different type. All values must be tagged with run-time type codes so that the type of a variable may be determined. Dynamically typed languages may still be strongly typed, as long as run-time type checking eliminates the possibility of applying an operation to a value of an unexpected type. Historically, dynamic typing has been associated with interpreter-oriented languages such as Lisp, APL and SNOBOL; modern scripting languages such as Perl, Javascript and PHP are also dynamically typed.
Scope	Static or lexical scoping means that the scope of a variable declaration is a particular region of program text. A local variable of a subprogram will only be visible to that subprogram and others that are nested within it, (nested block-structure languages). Under static scoping, there is a unique declaration that applies to any particular use of a variable.	Dynamic scoping means that the scope of a variable declaration within one procedure extends to any other procedure that is called. That is, suppose that procedure A has a local variable x. Then whenever A calls any other procedure, x is implicitly available to that procedure. From the perspective of a called procedure, dynamic scoping affects the interpretation of nonlocal variables. If procedure B accesses a nonlocal variable x, then that variable may refer to the variable x within A, if B was just called by A. But when B is called by a some other procedure C that also defines a local variable x, then it is the x within C that is accessed by B. Dynamic scope binding was first used in interpreter-oriented programming languages such as Lisp and APL, because it is easy to implement and provides some programming conveniences. Dynamic scoping is still found in scripting languages such as Perl (`my` variables).
Location	The process of assigning and reserving memory locations for variables is known as allocation. Early programming languages used static allocation for all variables. Two problems result. First, subprogram variables maintain their values between calls, meaning that the value of a variable set during one call may be inadvertently accessed during the next call. This is history sensitivity. Second, static allocation means that it is not possible to have different outstanding activations of a procedure using different sets of local variables and parameters. Recursive procedures are precluded as are concurrent processes that share code. Although most languages have abandoned static allocation as a general policy, some have retained the possibility of explicitly declaring static allocation for local variables (Algol `own` variables and C `static` variables).	Dynamic allocation is the norm for modern programming languages. However, two principal variations exist. Stack-based allocation with nested block structure. Variables are automatically allocated when blocks are entered and deallocated when blocks are exited. Heap-based allocation. Pointer variables for dynamic data structures are allocated from a managed region of memory called the heap. Allocation and deallocation may be explicitly under programmer control, as in the Pascal and C families of languages. Alternatively, constructors may provide for automatic allocation when objects are created and garbage collection may provide for automatic deallocation when variables are no longer accessible.
Value	Symbolic constants may be considered as variables whose value is statically bound. A finer-grained breakdown of static binding time is possible. Constants may be bound at language-definition time, such as the predefined constant `true` in Pascal. Constants may be bound at language-implementation time, such as a constant `maxint` that denotes the maximum integer value supported by a particular implementation. Programmer-defined constants are typically bound at compile time. In some cases, however, a language may support the notion of a "constant" whose value is set dynamically on block entry, but remains static through its lifetime.	Dynamic value binding is of course the norm for variables. Typically, a variable may be assigned a value multiple times. In functional programming languages, the value of a variable is set when it is created and retains its value throughout its lifetime.

Statically typed languages fix the type associated with each variable at compile time. This permits compile-time type checking, which catches many programming errors before execution.

Static typing with dynamic subtyping is common. In this case, the dynamic type of a variable may change during program execution, but only within a set of possible types specified by a statically bound supertype.

Pascal, Modula, Ada, Java, C++ are statically typed languages. Dynamic subtyping in Ada is used for range types, generic array instantiation and so on. Object-oriented languages often fix a superclass as a static type, while allowing the subclass to vary dynamically.

Dynamically typed languages allow the programmer to freely assign objects of any type to a variable, even if the variable previously held a value of a different type. All values must be tagged with run-time type codes so that the type of a variable may be determined.

Dynamically typed languages may still be strongly typed, as long as run-time type checking eliminates the possibility of applying an operation to a value of an unexpected type.

Historically, dynamic typing has been associated with interpreter-oriented languages such as Lisp, APL and SNOBOL; modern scripting languages such as Perl, Javascript and PHP are also dynamically typed.

Scope

Static or lexical scoping means that the scope of a variable declaration is a particular region of program text. A local variable of a subprogram will only be visible to that subprogram and others that are nested within it, (nested block-structure languages).

Under static scoping, there is a unique declaration that applies to any particular use of a variable.

Dynamic scoping means that the scope of a variable declaration within one procedure extends to any other procedure that is called. That is, suppose that procedure A has a local variable x. Then whenever A calls any other procedure, x is implicitly available to that procedure.

From the perspective of a called procedure, dynamic scoping affects the interpretation of nonlocal variables. If procedure B accesses a nonlocal variable x, then that variable may refer to the variable x within A, if B was just called by A. But when B is called by a some other procedure C that also defines a local variable x, then it is the x within C that is accessed by B.

Dynamic scope binding was first used in interpreter-oriented programming languages such as Lisp and APL, because it is easy to implement and provides some programming conveniences. Dynamic scoping is still found in scripting languages such as Perl (my variables).

Location

The process of assigning and reserving memory locations for variables is known as allocation. Early programming languages used static allocation for all variables. Two problems result. First, subprogram variables maintain their values between calls, meaning that the value of a variable set during one call may be inadvertently accessed during the next call. This is history sensitivity.

Second, static allocation means that it is not possible to have different outstanding activations of a procedure using different sets of local variables and parameters. Recursive procedures are precluded as are concurrent processes that share code.

Although most languages have abandoned static allocation as a general policy, some have retained the possibility of explicitly declaring static allocation for local variables (Algol own variables and C static variables).

Dynamic allocation is the norm for modern programming languages. However, two principal variations exist.

Stack-based allocation with nested block structure. Variables are automatically allocated when blocks are entered and deallocated when blocks are exited.
Heap-based allocation. Pointer variables for dynamic data structures are allocated from a managed region of memory called the heap. Allocation and deallocation may be explicitly under programmer control, as in the Pascal and C families of languages. Alternatively, constructors may provide for automatic allocation when objects are created and garbage collection may provide for automatic deallocation when variables are no longer accessible.

Value

Symbolic constants may be considered as variables whose value is statically bound. A finer-grained breakdown of static binding time is possible.

Constants may be bound at language-definition time, such as the predefined constant true in Pascal.
Constants may be bound at language-implementation time, such as a constant maxint that denotes the maximum integer value supported by a particular implementation.
Programmer-defined constants are typically bound at compile time. In some cases, however, a language may support the notion of a "constant" whose value is set dynamically on block entry, but remains static through its lifetime.

Dynamic value binding is of course the norm for variables. Typically, a variable may be assigned a value multiple times.

In functional programming languages, the value of a variable is set when it is created and retains its value throughout its lifetime.