2

Under static scoping, by its definition, how can we determine the scope of a variable inside a recursive function?

For example, in a pseudo-language,

int i=1;

function myfun(){
  if (i > 4){
    printf("%d\n", i);
  } else {
    ++i;  
    myfun();
  }
}

myfun();

i changes in each call to myfun

According to static scoping, it seems to me that it should print out 1 for i. But if I remember correctly in C, which is statically scoped, it will print out 5.

If it prints out 5, then what is the difference between dynamic scoping and static scoping for a variable inside a recursively defined function?

Thanks.

  • 1
    It would of course never print 1, regardless the scope of i. If i would be local you would get a stack overflow. – Martin Maat Sep 26 '16 at 19:12
3

Scoping tells us which i is being referred to when a line of code does so.

However, in your example, there is only one i, and it is in the global scope. Since there is no local i declaration (neither as a parameter, nor an automatic variable), uses of i within the function must be referring to the global i.


Static scoping tells us which i, however, (recursive) activation is an orthogonal concept.

If you had a local variable i in scope, then the binding of uses of i would go that local variable.

And when recursion is used, the function is activated multiple times, and each activation gets its own i. Each use of i refers to the local variable in the current activation of the function no matter the recursive depth.

Activation is an inherent property of languages that provide recursion, and any currently executing function knows its specific activation.


C doesn't support closures, so the conversation ends there for C.

However, in Javascript for example, you can have nested functions, and nested functions can access variables of the outer enclosing parents. Static scoping here tells us once again which scope defines the variable used by an use of that name in some line of code.

However, even when the static scoping says that a variable binds to an outer enclosing context, if that outer enclosing context is recursively activated, there will be multiple copies of those variables and the appropriate one is chosen by following first the activation context, and then applying static scoping.

Note that in Javascript, a closure can be activated multiple times without recursion (because a closure can outlive the original function invocation and return), though the same applies. First, the activation context is used before applying static scoping to that context.

In Javascript, due to nested functions, there is also a notion nested activations for the various scopes, so the notion of activations is a bit more complicated that in C as, for example, we can have different depths of recursion for inner nested functions than for the outer nested functions. Still, the activations that create the variables of various scopes are understood during execution, and those provide the contexts for the application of static scoping.


To your comments below:

does static scoping only determine which declaration in the code that a name refers to, but not determine anything about execution, while activations are about execution of the code?

(1) Yes. Though note that execution is constrained to follow the static scoping as follows: given a function and a nested function, if the outer function scope has a variable i from the static scope perspective, there will be some activation that corresponds to that static scope that introduced that i available when the inner scope runs (also with its own activation), otherwise the inner scope could not have been activated itself. So, the static scope can be mapped to the activation, and vice versa, and we can say that the static scope at least tells us something about the pattern of activations.

2). does dynamic scoping determine the same thing as static scoping does? So is it correct that dynamic scoping doesn't determine anything related to execution of the code, so dynamic scoping and activations are also orthogonal concepts to each other? But the way that dynamic scoping uses for the determination depend on execution of the code?

(2) Dynamic scoping, depending on language, looks up the variables by the current activation stack (from most nested outward) rather than by the static scope. Thus, there are inherent runtime implications, which is to say, it is much harder to optimize since lookup depends on the runtime call chain.

(Dynamic scoping is just plain confusing, if you ask me, though I'm sure some programming problems lend themselves to that nicely.)

In any case, if an (inner) function declares its own local i, that i is going to be the one, whether statically scoped or dynamically scoped, and regardless of recursion.

The difference comes into play when the i isn't declared locally, so what gets found as a "non-local" reference to i is the difference. In a dynamically scoped system, the nearest i on the activation stack would bind to the use. This means that at runtime the activation stack is searched for an i. It probably doesn't have to do string matching to find an i (though that is one possibility), but there has to be a bunch of machinery around declaring local variables for binding re: dynamic scoping (which is not exactly so necessary with static scoping).

(Whereas with static scoping, the trick is in having the activations available, given those, you "know" from compile time where i is within its outer scope, as you know statically what the exact function of that outer scope is. In statically scoped system, a use of i would refer to the i that corresponded to the activation of that outer scope that also activated the currently running inner scope, so the outer scope and the inner scope are in some sense well connected. By contrast, with dynamic scoping, completely different outer activations might hold the i of interest depending on the call chain.)

A directly recursive function that didn't declare a local i, would not find an i in itself or any recursive activation of itself, so would find i in some outer activation (but it could be any number of different possible functions that has an i).

If the recursive function participated in mutual recursion where one (or more) of the other functions did declare an i, that most recently activated one would supply any non-local usage of i. Whew! I have never programed that way so I otherwise don't have my head wrapped around how that would be useful. (And as a compiler writer, I see significant performance challenges for dynamic scoping, though have never written a compiler for a dynamically scoped language.)

|improve this answer|||||
  • Thanks. 1). Just to make sure that I understand you correctly, does static scoping only determines which declaration in the code that a name refers to, but not determine anything about execution, while activations are about execution of the code? 2). does dynamic scoping determine the same thing as static scoping does? So is it correct that dynamic scoping doesn't determine anything related to execution of the code, so dynamic scoping and activations are also orthogonal concepts to each other? But the way that dynamic scoping uses for the determination depend on execution of the code? – Tim Sep 26 '16 at 17:36
  • added to 2) wikipedia says Strictly speaking[b] and in practice for most programming languages, "part of a program" refers to "portion of the source code (area of text)", and is known as lexical scope. In some languages, however, "part of a program" refers to "portion of run time (time period during execution)", and is known as dynamic scope. That seems to me that dynamic scoping and activations aren't orthogonal to each other, and dynamic scoping determines the time point for the matching declaration of a given name. – Tim Sep 26 '16 at 17:44
  • @Tim, Answered with edits, see above. – Erik Eidt Sep 26 '16 at 18:58
  • Thanks. What books do you recommend for general programming language concepts e.g. those in the questions that I asked recently? Is it correct that books on implementation of programming languages such as compilers don't explain the language concepts much? – Tim Sep 26 '16 at 19:21
  • Here "when recursion is used, the function is activated multiple times, and each activation gets its own i. Each use of i refers to the local variable in the current activation of the function no matter the recursive depth. Activation is an inherent property of languages that provide recursion, and any currently executing function knows its specific activation." In an earlier post programmers.stackexchange.com/q/331885/699, where a function is defined inside another, why doesn't the quote apply, so that there is no need to consider deep binding, and only shallow binding will apply? – Tim Sep 27 '16 at 2:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.