2

I'm taking a comparative programming languages course and have learned the bare basics of variable scopes with respect to stack frames -- e.g. static and dynamic links, offsets, etc. as in the image at the bottom of this page for example.

In our texts (two: Understanding Programming Languages by Ben-Ari and Concepts of Programming Languages by Sebesta, plus my own copy of Programming Language Pragmatics by Scott) there is discussion of namespaces but no explanation that I saw of namespaces in relation to the stack frame.

How do namespaces affect the process of variable lookup in the stack?

Is it correct to say that when an activation record is instantiated onto the stack and linked that the fully-qualified name (namespace.variableName) is added, and not just the name as said in our texts? If not then I don't see how the same identifier from two namespaces in the current scope can be disambiguated.

2

You are talking about access to in-scope local variables, because of the example you're referring to, and because you're speaking of activations, which is where local variables live.

There is no such thing that I know of regarding namespace qualified access to local variables.

Local variables are scoped to the containing method but basically don't participate in namespaces -- there is no way to use a namespace qualified expression to reach a (method's) local variable in the languages I know.


Local variables are in methods; methods are in classes.

Classes are in either (other) classes or namespaces, and namespaces are either root, or in other namespaces.

We can build an expression starting from a namespace to reach/identify a class. And we can extend such an expression to reach/identify a (static) method, but we cannot further extend such an expression to reach a local variable in that method.

Local variables can only be reached if they are in scope, and then they are referenced by simple name only. The associated namespace is understood by the context of the method (being compiled), though basically has no bearing on locating local variables, which is done by scoping instead of namespaces.

  • I should have clarified, I wasn't talking specifically about variables only but about symbols/identifiers in general. Variables were just intended as an example. So for example, if we have a variable V or function F in some namespace N we can reference it as N.V or N.F from elsewhere, assuming we don't import that namespace. How does the runtime environment know where to look for N.V or N.F ? That's really what I'm trying to ask. I may have used the stack incorrectly in my question. Thanks. – Dave Dec 4 '16 at 20:24
  • Ok. Your original question is referencing activations, in which resolution is about choose between multiple copies (due the call chain) of (lexically the same) local variable(s) . Namespace expressions pretty much only reference static variables and static methods, of which there are only ever one copy, and they don't live on the activation stack. This means that the resolution is different from the other kind of resolution. If you have a follow on question on how that works, I would encourage you to post new question to the website for that and we'll happily take our best shot! – Erik Eidt Dec 4 '16 at 23:06
2

Stack frames are used to store local variables (variables declared within a function). In many languages, it is not meaningful to talk of the “fully qualified name” of a local variable.

In contrast, namespaces, packages, or modules are used to organize global symbols. These symbols might refer to top-level functions or global variables or to concepts that are not represented directly in memory. Accesses to these symbols are therefore not compiled as memory reads relative to the stack pointer.

It's also important to note that stack frames do not contain the name of the symbols they are containing. If a stack frame “stores a variable x”, this just means it reserves memory at a compile-time known stack pointer offset for the value of that variable. Since all accesses are done through the offset and not the name, the name is unknown at run time (unless you compile with debugging symbols activated).

With nested functions, we might want to refer to symbols of an enclosing function, e.g.

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

Here, inside g() the x symbol refers to the outside scope. This can be done with static links: There is a pointer from g()'s stack frame to f()'s stack frame. In pseudo-C, y would be compiled as stack_frame->y, but x as stack_frame->enclosing_scope->x.

The difficult part with nested functions is not traversing the scope chain, but making sure all accessible scopes live as long as each reference to a nested function. If a reference to a nested function can leave the enclosing function, this necessarily implies garbage collection.

If the enclosing scope has a variable of the same name as an inner scope, the inner scope shadows the outer variable:

function f(x) {
  return function g(x) { return x; } // x always refers to g()'s x
}

In most languages, f()'s x variable is completely inaccessible from g(). Exceptions to the rule:

  • Python's nonlocal is similar, but actually just aliases an outer variable into the nested scope. It does not allow to disambiguate between inner and shadowed variables.

  • Perl6's OUTER pseudo-namespace allows us to access shadowed variables:

    my $x = 5;
    {
       my $x = 6;
       say $x;          #=> 6
       say $OUTER::x    #=> 5
    }
    

    The OUTER namespace is not a physical, global namespace, but rather a way to augment the variable lookup process.

  • Excellent thanks. I may have munged my question since it was late last night. My question more broadly is how does the runtime environment know where to find a namespace-qualified variable/function/symbol? With the stack we can follow the calls through the static and dynamic links, but if they are not in the stack (which I would have presumed, at the first stack frame for global scope, so that may be wrong) then where are they maintained? On the heap, even if primitive values? If so the runtime still has to be able to know the address, so how is that address stored and found? – Dave Dec 4 '16 at 20:29
  • Also Sebesta specifically says that in dynamic-scoped languages the variable name must be stored in the stack as well, because they cannot determine the offset at compile time. But after some research it looks like those languages seem to be pretty rare so maybe not worth considering that issue at all then. Thanks. – Dave Dec 4 '16 at 20:41
  • @Dave Where global variables etc. are stored depends on the format of the binary. In general, the binary includes a data segment, whereas machine code lives in the text segment. The data segment is distinct from the heap and the stack: as this memory is allocated at compile time, the running program doesn't need to allocate or free this memory. References inside an object file can be resolved at assembly time, whereas references between files are resolved by the linker. Unfortunately I haven't the slightest idea how C-style linking actually works. – amon Dec 4 '16 at 20:48
  • @Dave dynamic scoping is used mostly in interpreters, as it is far easier to implement than lexical scoping (examples: some Lisp dialects, Shells, Perl, many template languages, …). Here, scopes are usually implemented as (a linked list of) hash tables instead of stack frames, with the variable name being the hash table key. – amon Dec 4 '16 at 20:51
1

How do namespaces affect the process of variable lookup in the stack?

They don't, at least not in C#.

In C#, namespaces are a source-code convenience; they disappear entirely when you compile. In essence, all references are fully qualified at compile-time. So namespaces have no effect on variable lookup in the stack whatsoever.

Your mileage may vary in other languages.

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.