Names, Scopes, and Bindings

Prev: Programming Language Syntax Next: Semantic Analysis

3.1-3.2 Check Your Understanding

What is binding time?
Explain the distinction between decisions that are bound statically and those that are bound dynamically.
What is the advantage of binding things as early as possible? What is the advantage of delaying bindings?
Explain the distinction between the lifetime of a name-to-object binding and its visibility.
What determines whether an object is allocated statically, on the stack, or in the heap?
List the objects and information commonly found in a stack frame.
What is a frame pointer? What is it used for?
What is a calling sequence?
What are internal and external fragmentation?
What is garbage collection?
What is a dangling reference?

3.3 Check Your Understanding

What do we mean by the scope of a name-to-object binding?
Describe the difference between static and dynamic scoping.
What is elaboration?
What is a referencing environment?
Explain the closest nested scope rule.
What is the purpose of a scope resolution operator?
What is a static chain? What is it used for?
What are forward references? Why are they prohibited or restricted in many programming languages?
Explain the difference between a declaration and a definition. Why is the distinction important?

3.4-3.5 Check Your Understanding

Explain the importance of information hiding.
What is an opaque export?
Why might it be useful to distinguish between the header and the body of a module?
What does it mean for a scope to be closed?
Explain the distinction between “modules as managers” and “modules as types.”
How do classes differ from modules?
Why might it be useful to have modules and classes in the same language?
Why does the use of dynamic scoping imply the need for run-time type checking?
Explain the purpose of a compiler’s symbol table.
What are aliases? Why are they considered a problem in language design and implementation?
Explain the value of the restrict qualifier in C.
What is overloading? How does it differ from coercion and polymorphism?
What are type classes in Haskell? What purpose do they serve?

3.6-3.7 Check Your Understanding

Describe the difference between deep and shallow binding of referencing environments.
Why are binding rules particularly important for languages with dynamic scoping?
What are first-class subroutines? What languages support them?
What is a subroutine closure? What is it used for? How is it implemented?
What is an object closure? How is it related to a subroutine closure?
Describe how the delegates of C# extend and unify both subroutine and object closures.
Explain the distinction between limited and unlimited extent of objects in a local scope.
What is a lambda expression? How does the support for lambda expressions in functional languages compare to that of C# or Ruby? To that of C++ or Java?
What are macros? What was the motivation for including them in C? What problems may they cause?

3.10 Exercises

3.1

Indicate the binding time, when the language is designed, when the program is linked, when the program begins execution, etc., for each of the following decisions in your favorite programming language and implementation. Explain any answers you think are open to interpretation.

The number of built-in functions, math, type queries, etc.
The variable declaration that corresponds to a particular variable reference, use.
The maximum length allowed for a constant, literal, character string.
The referencing environment for a subroutine that is passed as a parameter.
The address of a particular library routine.
The total amount of space occupied by program code and data.

3.2

In Fortran 77, local variables were typically allocated statically. In Algol and its descendants, e.g. Ada and C, they are typically allocated in the stack. In Lisp they are typically allocated at least partially in the heap. What accounts for these differences? Give an example of a program in Ada or C that would not work correctly if local variables were allocated statically. Give an example of a program in Scheme or Common Lisp that would not work correctly if local variables were allocated on the stack.

3.3

Give two examples in which it might make sense to delay the binding of an implementation decision, even though sufficient information exists to bind it early.

3.4

Give three concrete examples drawn from programming languages with which you are familiar in which a variable is live but not in scope.

3.5

Consider the following pseudocode:

1. procedure main()
2.     a : integer := 1
3.     b : integer := 2
 
4.     procedure middle()
5.         b : integer := a
 
6.         procedure inner()
7.             print a, b
8.             a : integer := 3
 
9.         -- body of middle
10.            inner()
11.            print a, b
 
12.    -- body of main
13.        middle()
14.        print a, b

Suppose this was code for a language with the declaration-order rules of C, but with nested subroutines, that is, names must be declared before use, and the scope of a name extends from its declaration through the end of the block. At each print statement, indicate which declarations of a and b are in the referencing environment. What does the program print, or will the compiler identify static semantic errors? Repeat the exercise for the declaration-order rules of C#, names must be declared before use, but the scope of a name is the entire block in which it is declared, and of Modula-3, names can be declared in any order, and their scope is the entire block in which they are declared.

3.6

Consider the following pseudocode, assuming nested subroutines and static scope:

procedure main()
    g : integer
 
    procedure B(a : integer)
        x : integer
 
        procedure A(n : integer)
            g := n
 
        procedure R(m : integer)
            write integer(x)
            x /:= 2 -- integer division
            if x > 1
                R(m + 1)
            else
                A(m)
 
        -- body of B
        x := a * a
        R(1)
 
    -- body of main
    B(3)
    write integer(g)

(a) What does this program print?
(b) Show the frames on the stack when A has just been called. For each frame, show the static and dynamic links.
(c) Explain how A finds g.

3.7

As part of the development team at MumbleTech.com, Janet has written a list manipulation library for C that contains, among other things, the code in Figure 3.16.

typedef struct list_node {
    void* data;
    struct list_node* next;
} list_node;
 
list_node* insert(void* d, list_node* L) {
    list_node* t = (list_node*) malloc(sizeof(list_node));
    t->data = d;
    t->next = L;
    return t;
}
 
list_node* reverse(list_node* L) {
    list_node* rtn = 0;
    while (L) {
        rtn = insert(L->data, rtn);
        L = L->next;
    }
    return rtn;
}
 
void delete_list(list_node* L) {
    while (L) {
        list_node* t = L;
        L = L->next;
        free(t->data);
        free(t);
    }
}

(a) Accustomed to Java, new team member Brad includes the following code in the main loop of his program:

list_node* L = 0;
while (more_widgets()) {
    L = insert(next_widget(), L);
}
L = reverse(L);

Sadly, after running for a while, Brad’s program always runs out of memory and crashes. Explain what’s going wrong.

(b) After Janet patiently explains the problem to him, Brad gives it another try:

list_node* L = 0;
while (more_widgets()) {
    L = insert(next_widget(), L);
}
list_node* T = reverse(L);
delete_list(L);
L = T;

This seems to solve the insufficient memory problem, but where the program used to produce correct results, before running out of memory, now its output is strangely corrupted, and Brad goes back to Janet for advice. What will she tell him this time?

3.8

Rewrite Figures 3.6 and 3.7 in C. You will need to use separate compilation for name hiding.

3.9

Consider the following fragment of code in C:

{
    int a, b, c;
    ...
    {
        int d, e;
        ...
        {
            int f;
            ...
        }
        ...
    }
    ...
    {
        int g, h, i;
        ...
    }
    ...
}

(a) Assume that each integer variable occupies four bytes. How much total space is required for the variables in this code?
(b) Describe an algorithm that a compiler could use to assign stack frame offsets to the variables of arbitrary nested blocks, in a way that minimizes the total space required.

3.10

Consider the design of a Fortran 77 compiler that uses static allocation for the local variables of subroutines. Expanding on the solution to the previous question, describe an algorithm to minimize the total space required for these variables. You may find it helpful to construct a call graph data structure in which each node represents a subroutine, and each directed arc indicates that the subroutine at the tail may sometimes call the subroutine at the head.

3.11

Consider the following pseudocode:

procedure P(A, B : real)
    X : real
 
    procedure Q(B, C : real)
        Y : real
        ...
 
    procedure R(A, C : real)
        Z : real
        ...    -- (*)
    ...

Assuming static scope, what is the referencing environment at the location marked by (*)?

3.12

Write a simple program in Scheme that displays three different behaviors, depending on whether we use let, let*, or letrec to declare a given set of names. Hint: to make good use of letrec, you will probably want your names to be functions, lambda expressions.

3.13

Consider the following program in Scheme:

(define A
  (lambda()
    (let* ((x 2)
            (C (lambda (P)
                 (let ((x 4))
                   (P))))
            (D (lambda ()
                 x))
            (B (lambda ()
                 (let ((x 3))
                   (C D)))))
      (B))))

What does this program print? What would it print if Scheme used dynamic scoping and shallow binding? Dynamic scoping and deep binding? Explain your answers.

3.14

Consider the following pseudocode:

x : integer -- global
 
procedure set_x(n : integer)
    x := n
 
procedure print_x()
    write integer(x)
 
procedure first()
    set_x(1)
    print_x()
 
procedure second()
    x : integer
    set_x(2)
    print_x()
 
set_x(0)
first()
print_x()
second()
print_x()

What does this program print if the language uses static scoping? What does it print with dynamic scoping? Why?

3.15

The principal argument in favor of dynamic scoping is that it facilitates the customization of subroutines. Suppose, for example, that we have a library routine print_integer that is capable of printing its argument in any of several bases, decimal, binary, hexadecimal, etc. Suppose further that we want the routine to use decimal notation most of the time, and to use other bases only in a few special cases: we do not want to have to specify a base explicitly on each individual call. We can achieve this result with dynamic scoping by having print_integer obtain its base from a nonlocal variable print_base. We can establish the default behavior by declaring a variable print_base and setting its value to 10 in a scope encountered early in execution. Then, any time we want to change the base temporarily, we can write:

begin -- nested block
    print_base : integer := 16 -- use hexadecimal
    print_integer(n)

The problem with this argument is that there are usually other ways to achieve the same effect, without dynamic scoping. Describe at least two for the print_integer example.

3.16

As noted in Section 3.6.3, C# has unusually sophisticated support for first-class subroutines. Among other things, it allows delegates to be instantiated from anonymous nested methods, and gives local variables and parameters unlimited extent when they may be needed by such a delegate. Consider the implications of these features in the following C# program:

using System;
public delegate int UnaryOp(int n);
    // type declaration: UnaryOp is a function from ints to ints
 
public class Foo {
    static int a = 2;
    static UnaryOp b(int c) {
        int d = a + c;
        Console.WriteLine(d);
        return delegate(int n) { return c + n; };
    }
    public static void Main(string[] args) {
        Console.WriteLine(b(3)(4));
    }
}

What does this program print? Which of a, b, c, and d, if any, is likely to be statically allocated? Which could be allocated on the stack? Which would need to be allocated in the heap? Explain.

3.17

If you are familiar with structured exception handling, as provided in Ada, C++, Java, C#, ML, Python, or Ruby, consider how this mechanism relates to the issue of scoping. Conventionally, a raise or throw statement is thought of as referring to an exception, which it passes as a parameter to a handler-finding library routine. In each of the languages mentioned, the exception itself must be declared in some surrounding scope, and is subject to the usual static scope rules. Describe an alternative point of view, in which the raise or throw is actually a reference to a handler, to which it transfers control directly. Assuming this point of view, what are the scope rules for handlers? Are these rules consistent with the rest of the language? Explain.

3.18

Consider the following pseudocode:

x : integer -- global
 
procedure set_x(n : integer)
    x := n
 
procedure print_x()
    write integer(x)
 
procedure foo(S, P : function; n : integer)
    x : integer := 5
    if n in {1, 3}
        set_x(n)
    else
        S(n)
    if n in {1, 2}
        print_x()
    else
        P
 
set_x(0); foo(set_x, print_x, 1); print_x()
set_x(0); foo(set_x, print_x, 2); print_x()
set_x(0); foo(set_x, print_x, 3); print_x()
set_x(0); foo(set_x, print_x, 4); print_x()

Assume that the language uses dynamic scoping. What does the program print if the language uses shallow binding? What does it print with deep binding? Why?

3.19

Consider the following pseudocode:

x : integer := 1
y : integer := 2
 
procedure add()
    x := x + y
 
procedure second(P : procedure)
    x : integer := 2
    P()
 
procedure first
    y : integer := 3
    second(add)
 
first()
write integer(x)

(a) What does this program print if the language uses static scoping?
(b) What does it print if the language uses dynamic scoping with deep binding?
(c) What does it print if the language uses dynamic scoping with shallow binding?

3.20

Consider mathematical operations in a language like C++, which supports both overloading and coercion. In many cases, it may make sense to provide multiple, overloaded versions of a function, one for each numeric type or combination of types. In other cases, we might use a single version, probably defined for double-precision floating point arguments, and rely on coercion to allow that function to be used for other numeric types, e.g. integers. Give an example in which overloading is clearly the preferable approach. Give another in which coercion is almost certainly better.

3.21

In a language that supports operator overloading, build support for rational numbers. Each number should be represented internally as a (numerator, denominator) pair in simplest form, with a positive denominator. Your code should support unary negation and the four standard arithmetic operators. For extra credit, create a conversion routine that accepts two floating-point parameters, a value and an error bound, and returns the simplest, smallest denominator, rational number within the given error bound of the given value.

3.22

In an imperative language with lambda expressions, e.g. C#, Ruby, C++, or Java, write the following higher-level functions. A higher-level function takes other functions as argument and/or returns a function as a result.

compose(g, f) returns a function h such that h(x) == g(f(x)).
map(f, L) given a function f and a list L returns a list M such that the ith element of M is f(e), where e is the ith element of L.
filter(L, P) given a list L and a predicate, Boolean-returning function, P, returns a list containing all and only those elements of L for which P is true.

Ideally, your code should work for any argument or list element type.

3.23

Can you write a macro in standard C that returns the greatest common divisor of a pair of arguments, without calling a subroutine? Why or why not?

3.24-3.31

In More Depth.

Takashi's Notes

Explorer

Names, Scopes, and Bindings

Names, Scopes, and Bindings

3.1-3.2 Check Your Understanding

3.3 Check Your Understanding

3.4-3.5 Check Your Understanding

3.6-3.7 Check Your Understanding

3.10 Exercises

3.1

3.2

3.3

3.4

3.5

3.6

3.7

3.8

3.9

3.10

3.11

3.12

3.13

3.14

3.15

3.16

3.17

3.18

3.19

3.20

3.21

3.22

3.23

3.24-3.31

Graph View

Table of Contents

Backlinks