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. 904
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 <PERSON> himself, who was my professor, and he too could not find another occasion where this ambiguity could take place. 603