What does deep binding mean for static scope?

Question

When I self-study "Programming Languages: Principles and Paradigms, by Maurizio Gabbrielli, Simone Martini", I have a question: what does deep binding mean for static scope?

1. I learned the concepts of deep and shallow bindings for functional parameters from the following part in the book

   The general case, the one we want to analyse, is that of a language with functional parameters, nested environments and the ability to define functions at every nesting level. Let us consider the example shown in Fig. 7.13. The name x is defined more than once, so it is necessary to establish which is the (nonlocal) environment in which f will be evaluated. Concerning this question, the reader will not be surprised if we observe that there are two possibilities for selecting the nonlocal environment to use when executing a function f invoked using a formal parameter h:

   • Use the environment that is active at the time when the link between h and f is created (which happens on line 11). We say, in this case, that the language uses a deep binding policy.

   • Use the environment that is active when the call of f using h occurs (which happens on line 7). In this case, we say that the language uses a shallow binding policy.

   {int x = 1;
    int f(int y){
        return x+y;
    }
    void g (int h(int b)){
        int x = 2;
        return h(3) + x;
    }
    ...
    {int x = 4;
     int z = g(f);
    }
   }
   

   Fig. 7.13 Functional parameters

   All common languages that use static scope also use deep binding (because the choice of a shallow policy appears contradictory at the methodological level). The matter is not as clear for languages with dynamic scope, among which there are languages with deep as well as shallow binding. Returning to the example of Fig. 7.13, the different scope and binding policies yield the following behaviours:

   • Under static scope and deep binding, the call h(3) returns 4 (and g returns 6). The x in the body of f when it is called using h is the one in the outermost block;

   • Under dynamic scope and deep binding, the call h(3) returns 7 (and g returns 9). The x in the body of f when it is called using h is the one local to the block in which the call g(f) occurs;

   • Under dynamic scope and shallow binding, the call h(3) returns 5 (and g returns 7). The x in the body of f at the moment of its call through h is the one

   The above example 7.13 makes me think that the concepts of deep binding and shallow binding only apply to dynamic scope but not to static scope.

   But it also says "All common languages that use static scope also use deep binding", so I have the question: what does deep binding mean to static scope?

2. Later in the book, it seems to address my question in the following quote

   Binding policy and static scope

   We have already observed how all languages with static scope use deep binding. At first sight it could rather seem that deep or shallow binding make no difference in the case of static scope. After all, the nonlocal environment of a function is determined from the (static) position of its declaration and not by the way in which it is invoked. In the case in Fig. 7.13, it is the scope (and not binding) rule that establishes that every invocation of f (whether direct, using its name, or indirect, using a formal parameter) is evaluated in the outermost nonlocal environment.

   In general, however, it is not like this. The reason for this is that there can be many activation records for the same function simultaneously present on the stack (this clearly happens when we have recursive or mutually recursive functions). If a procedure is passed out from one of these activations, it is possible to create a situation in which the scope rules alone are not enough to determine which nonlocal environment to use in invoking the functional parameter. As an example, we will discuss the code in Fig. 7.15, which, as usual, we assume was written in a pseudo- language with static scope.

   {void foo (int f(), int x){
       int fie(){
           return x;
       }
       int z;
       if (x==0) z=f();
       else foo(fie,0);
    }
    int g(){
        return 1;
    }
    foo(g,1);
   }
   

   Fig. 7.15 The binding policy is necessary for determining the environment

   The heart of the problem is the (nonlocal) reference to x inside fie. The scope rules tell us that such an x refers to the formal parameter to foo (which, as it happens, is the only x declared in the program). But when fie is called (using the formal f), there are two active instances of foo (and therefore two instances of its local environment). A first activation from the call foo(g,1), in which x is associated (to a location which contains) the value 1, and a second one from the (recursive) call foo(fie, 0), in which x is associated with the value 0. It is inside this second activation that the call to fie through f is made. The scope rules say nothing about which of the instances of x should be used in the body of f. It is at this point that the binding policy intervenes. Using deep binding, the environment is established when the association between fie and f is created, that is when x is associated with the value 1. The variable z will therefore be assigned the value 1.

   In the case of shallow binding (which, let us repeat, is not used with static scope), the environment would be determined at the time f is invoked and z would be assigned the value 0.

   In example 7.15 of recursion, it seems to me that the book tries to explain how deep binding works for static scope. But to me, it actually explains how deep binding works for dynamic scope instead of static scope. So how does the example explain how deep binding works for static scope?

Thanks.

Answer 1

Admittedly, the parts dedicated to binding policies in the Programming Languages: Principles and Paradigms book could be more detailed. I'll try to convey some additional and contextual information, and answer directly to your questions along the way.

Scope policies and binding policies

As described around chapter 9, scope policies and binding policies are effectively two separate, yet related, mechanisms for binding names to objects. I assume the notions of static scope and dynamic scope are already known, so I will delve directly into binding policies.

There are two binding policies

• Deep binding
• Shallow binding

and they are another level of variability beyond scoping rules; that is, once you've fixed the type of scoping rule (either static or dynamic) there could still be some uncertainty around the decision of which objects to assign to a given name.

Static scope

For static scope, the only situation[1] I know of where this ambiguity could arise is that of a nested function definition, as in the following example

function f(function g (int), int y) {
    function h (x) {
        return x + y;
    }

    if (y == 0) {
        return g(1);
    } else {
        return f(h, 0);
    }
}

int y = 4;
function k (x) {
    return x * y;
}

{
    print(f(k, 1));
}

In this example, the occurrence of y in h() belongs to the non-local environment, and since we are using static scope that y must be the one declared as a formal parameter of f(). However, f() is also a recursive function, and multiple occurrences of variable y could coexist at the same time. Which "instantiation" of variable y should we refer to in the body of h() then? The static scope rule is not enough to answer to this question.

The above example 7.13 makes me think that the concepts of deep binding and shallow binding only apply to dynamic scope but not to static scope.

No, deep binding and shallow binding can also mean a difference when applied to static scope. If you fix a static scope discipline then

• A deep binding rule means binding at the time when the formal function parameter is assigned to an actual function
• A shallow binding rule means binding at the time the function is called via the formal function parameter

To make this easier to understand, consider my former example.

Deep binding

If we use static scope and deep binding, then

• k() reference to y refers to the global y, initially set to 4. This binding remains the same even if k() is used as an actual function parameter, because static scope has greater "precedence" over any binding policy
• When f() is invoked, g() is initially set to k(). However, in the recursive call to f(h, 0), it is later set to the internally defined h() function. Since we are using deep binding, h()'s y will be the one set to 1

Shallow binding

If we use static scope and shallow binding, then

• k() reference to y is the same as in the point before
• When f() is invoked, g() is initially set to k(). However, in the recursive call to f(h, 0), it is later set to the internally defined h() function. Since we are using shallow binding, h()'s y will be the one found at the needed moment, which in our case is the one set to 0

So my last few words should have given an answer to

But it also says "All common languages that use static scope also use deep binding", so I have the question: what does deep binding mean to static scope?

Although I did not make an intentional effort, I might also have answered to

So how does the example explain how deep binding works for static scope?

If I didn't, feel free to report it in the comments.

Dynamic scope

I will not detail the impact of the two binding policies in the context of dynamic scope, since this was not called for in the question body. However, if I see this answer to raise enough interest, I may expand it to also include this point.

[1] I had the luck to ask to Maurizio Gabrielli himself, who was my professor, and he too could not find another occasion where this ambiguity could take place.