Lecture 9: Properties of Variables; Scope and Lexical Analysis

Declarations and References

Variable names generally occur in programs in two flavors: declarations and references:

• Declarations create a new variable

  Examples:

  • (define x ...)
  • (lambda (x) ...)
  • (let ((x ...)) ...)

  All of these uses of "x" are variable declarations.

• References are when you use a variable name to refer to a hopefully-existing variable.

  Examples: just about any variable name that occurs in something that isn't creating that variable.

  • x
  • (+ x 1)
  • (inc x)

This distinction is important when we want to ask the following question: when a variable reference occurs, what declaration is it referring to?

If a particular variable reference refers to a particular declaration, we say that variable is bound to that declaration.

Static Properties of Variables

Throughout our discussion of languages we will often use the terms static and dynamic to refer to various properties:

• A property is static when it can be determined by looking at the program text.
• A property is dynamic when the program text must be executed to determine the property.

Static properties can be used to detect errors and improve performance at compile time. These definitions will be used throughout the semester and applied to a variety of properties. In general, though, they take a little more work by the interpreter or compiler to implement.

In this section, we will explore some of the static properties that variables can have.

Free and Bound Variables

Here is the BNF that describes the toy language we will use to discuss free and bound variables. It is called the lambda calculus for historical reasons.

   <exp> ::= <symbol>
        | (lambda (<symbol>) <exp>)
        | (<exp> <exp>)   
 

Definitions:

• A variable is bound or occurs bound in an expression if it refers to the formal parameter in the expression.
• A variable is free or occurs free in an expression if it is not bound.
• A variable that is bound by some formal parameter is said to be lexically bound.
• A variable that is not lexically bound must be bound at run time to something such as a system primitive. (Well, there is an exception.) Such variables are said to be globally bound.
• A lambda expression without any free variables (i.e., does not depend on any system primitives or other things defined outside of itself) is called a combinator.

Examples:

• In the following expression, x is bound and y is free.

  ((lambda (x) x) y)
  

• We can capture y by enclosing the above expression in another lambda expression which has y as its formal parameter:

  (lambda (y) ((lambda (x) x) y))
  

• In this expression, z is a parameter, not a variable reference, so it is neither bound nor free. That is z does not occur bound or free. However x is free.

  (lambda (z) x)
  

• The expression:

  (lambda (x) x)
  

  always has the same meaning: its returns its argument unchanged. This function is called the identity function. It does not depend on any free variables and thus its meaning is independent of any run-time concerns.

Scope and Lexical Analysis

Definitions:

• The scope of a variable declaration is the part of the program where that variable declaration is seen.
• If the scope of a variable can be determined at compile time (i.e., statically), the language is said to be statically or lexically scoped.
• If scope regions can be nested inside of each other, the language is block structured. These regions are called blocks.
• If a variable in one block is not visible because it has been redeclared in block nested within that one, we say that that variable creates a hole in the outer scope. We say that the inner variable declaration shadows the outer one.

Examples:

• Consider the following C program:

  {			/* Block 1 */
      int x, y;
  
      x = 4;
      {			/* Block 2 */
          int x, z;
  
          x = 3
          z = x + 1
      }
      y = x + 1
  }
  

  The declaration of x in block 2 shadows the declaration of x in block 1. What is the final value of x in block 1? In block 2? What is the final value of y? Of z?

• Here is a scheme program with a similar structure:

  (lambda (x y)		;; block 1
     (lambda (x z)	;; block 2
         ...
      ))
  

  The lambda calculus is statically scoped. That means that a lambda expression's formal parameter binds all occurrences of that variable in the body of that lambda expression unless an intervening declaration of the same variable occurs.

  Scheme is also statically scoped. Formal parameters of lambda expressions have the same scope as in the lambda calculus. Local variables defined by a let expression has similar scope within the body of that let.

Lexical Addresses

A lexical address of a variable reference gives the depth of the reference from the block in which the variable was declared and the position of the variable in that declaration.

A lexical address has the form (v : d p) where v is the variable name, d is the depth and p is the position. For our purposes, depth and position are zero-based counts.

For example, the lambda calculus expression:

(lambda (x y)
  ((lambda (a)
     (x (a y)))
   x))

can be transformed to show lexical addresses as follows:

(lambda (x y)
  ((lambda (a)
     ((x : 1 0) ((a : 0 0) (y : 1 1))))
   (x : 0 0)))

Please not that this is simply a notation for marking variables with their lexical addresses. Although this looks like code, you can't run it through an interpreter.

So, the first x is at depth 1 and position 0. That means it's one level out from the current block and is at posiition 0 among thouse variables. Similarly, variable a has depth 0 and position 0 (same block, first variable (position 0)). The last y has a lexical address with depth 1 and position 1. That means to go one block out and get the second variable (position 1).

Last updated at 9:54 am on Friday, August 27, 2004.