1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.