Static (Lexical) Scoping vs Dynamic Scoping (Pseudocode)

Question

Program A()
{
    x, y, z: integer;

    procedure B()
    {
        y: integer;
        y=0;
        x=z+1;
        z=y+2;
    }

    procedure C()
    {
        z: integer;

        procedure D()
        {
            x: integer;
            x = z + 1;
            y = x + 1;
            call B();
        }

        z = 5;
        call D();
    }

    x = 10;
    y = 11;
    z = 12;
    call C();
    print x, y, z;
}

From my understanding, the result of this program when run using static scoping is: x=13, y=7, and z=2.

However, when it is run using dynamic scoping, the result is: x=10, y=7, and z=12.

These results are the ones that our professor gave us. However, I cannot understand for the life of me how he has reached these results. Could someone possibly walk through the pseudocode and explain their values in the two different types of scopes?

Solution 1

With static (lexical) scoping, the structure of the program source code determines what variables you are referring to. With dynamic scoping, the runtime state of the program stack determines what variable you are referring to. This is likely a very unfamiliar concept, since basically every programming language in wide use today (except perhaps emacs lisp) uses lexical scoping, which tends to be dramatically easier for both humans and analysis tools to reason about.

Consider this much simpler example program (written in your pseudocode syntax):

program a() {
  x: integer; // "x1" in discussions below
  x = 1;

  procedure b() {
    x = 2; // <-- which "x" do we write to?
  }

  procedure c() {
    x: integer; // "x2" in discussions below
    b();
  }

  c();
  print x;
}

The program and compiler refer to both variables as x, but I have labeled them x1 and x2 to ease discussion below.

With lexical scoping, we determine at compile time which x we are referring to based on the static, lexical structure of the program source code. The innermost definition of x in scope when defining b is x1, and so the write in question resolves to x1, and that's where x = 2 writes, so we print 2 upon running this program.

With dynamic scoping, we have a stack of variable definitions tracked at runtime -- so which x we write to depends on what exactly is in scope and has been defined dynamically at runtime. Beginning to run a pushes x => x1 onto the stack, calling c pushes x => x2 onto the stack, and then when we get to b, the top of the stack is x => x2, and so we write into x2. This leaves x1 untouched, and so we print 1 at the end of the program.

Furthermore, consider this slightly different program:

program a() {
  x: integer; // "x1" in discussions below
  x = 1;

  procedure b() {
    x = 2; // <-- which "x" do we write to?
  }

  procedure c() {
    x: integer; // "x2" in discussions below
    b();
  }

  c();
  b();
}

Note b is called twice -- the first time via c, the second time directly. With lexical scoping, the explanation above isn't changed and we write into x1 both times. However, with dynamic scoping, it depends on how x is bound at runtime. The first time we call b, we write into x2 as explained above -- but the second time, we write into x1, since that's what's on top of the stack! (x => x2 is popped when c returns.)

So, here is your professor's code, annotated with which exact variable is used on which write with lexical scoping. Writes that end up printed at the end of the program are marked with a *:

program A()
{
    x, y, z: integer; // x1, y1, z1

    procedure B()
    {
        y: integer; // y2
        y=0; // y2 = 0
        x=z+1; // x1 = z1 + 1 = 12 + 1 = 13*
        z=y+2; // z1 = y2 + 2 = 0 + 2 = 2*
    }

    procedure C()
    {
        z: integer; // z2

        procedure D()
        {
            x: integer;  // x2
            x = z + 1; // x2 = z2 + 1 = 5 + 1 = 6
            y = x + 1; // y1 = x2 + 1 = 6 + 1 = 7*
            call B();
        }

        z = 5; // z2 = 5
        call D();
    }

    x = 10; // x1 = 10
    y = 11; // y1 = 11
    z = 12; // z1 = 12
    call C();
    print x, y, z; // x1, y1, z1
}

And here it is with dynamic scoping. Note the only changes are in B, and in the location of the * tags:

program A()
{
    x, y, z: integer; // x1, y1, z1

    procedure B()
    {
        y: integer; // y2
        y=0; // y2 = 0
        x=z+1; // x2 = z2 + 1 = 5 + 1 = 6
        z=y+2; // z2 = y2 + 2 = 0 + 2 = 2
    }

    procedure C()
    {
        z: integer; // z2

        procedure D()
        {
            x: integer;  // x2
            x = z + 1; // x2 = z2 + 1 = 5 + 1 = 6
            y = x + 1; // y1 = x2 + 1 = 6 + 1 = 7*
            call B();
        }

        z = 5; // z2 = 5
        call D();
    }

    x = 10; // x1 = 10*
    y = 11; // y1 = 11
    z = 12; // z1 = 12*
    call C();
    print x, y, z;
}

Solution 2

Static scoping and Dynamic scoping are different ways to find a particular variable with a specific unique name in a program written in any language.

Its specifically helpful for interpreter or compiler to decide on where and how to find the variable.

Consider code is like below,

f2(){

   f1(){
   }

   f3(){
    f1()
   }

}

Static:

This is basically textual, first variable is defined or not will be checked in local function(lets name it f1()), if not in the local function f1(), then variable will be searched in function f2() that enclosed this function(by this I mean f1()), ...this continues...until variable is found.

Dynamic:

This is different from static, in the sense, as it is more runtime or dynamic, first variable is defined or not will be checked in local function,if not in the local function f1(),then variable will be searched in function f3() that called this function(by this I mean f1() again), ...this continues...until variable is found.

Solution 3

The crux is that the lexical graph looks like this:

B <- A -> C -> D

whereas the call graph looks like this:

     A -> C -> D -> B

The only difference is what lineage B has. In the lexical picture, B is defined directly in the scope of A (the global scope). In the dynamic picture, the stack at B already has D on top of C and then A.

This difference amounts to how the keywords x and z are resolved in B. Lexically, they are identified with A.x and A.z, but dynamically, they are identified with D.x and (since no D.z exists) with C.z.

def B:
    B.y = 0
    __x = __z + 1
    __z = B.y + 2
def C:
    def D:
        D.x = __z + 1
        __y = D.x + 1
        call B
    C.z = 5
    call D
A.x, A.y, A.z = 10, 11, 12
call C
print A.x, A.y, A.z

Above I've tried to represent your code more clearly. Note that D mutates A.y according to both methods of name resolution, whereas B only mutates A.x and A.z if lexical rather than dynamic scoping is chosen.

Note that while a function is only ever defined once*, it is common to call it from multiple places (and it may even call itself recursively). Thus, while it is fairly trivial to perform lexical scoping using the static code, the dynamic scoping is more complicated because the same keyword (in the same function) may resolve to different variables (from different name spaces) during different calls to that function (requiring you to step through the program and track how the call stack changes during execution).

*(Except in templating languages..)

Comments

[vschum]

This answer should be accepted; it does a great job of explaining the difference between lexical and dynamic scope, especially with the addition of the easier to read example program.

[Dagang]

This is a great answer, very clear explanation of the difference between static scoping and dynamic scoping. I also appreciate the way of using x1, x2 to distinguish different variables. BTW, when I was googling "dynamic scoping", it highlighted this answer, and pointed me here. Cool UX!

[Dagang]

Just wanted to know if the this keyword of JavaScript can also be considered as an example of dynamic scoping? Because this is not bound in a lexical scope.

[Kashif]

Okay I found one mistake. In the dynamic scope, it should be procedure B() { y: integer; // y2 y=0; // y2 = 0 x=z+1; // x2 = z2 + 1 = 5 + 1 = 6 z=y+2; // z2 = y2 + 2 = 0 + 2 = 2 }

[Noober]

One of the best explanation for static and dynamic scope. Learnt a lot. Thanks.

[Lucian]

Your example was of great help!

[doge]

In the first example, if the program is dynamic scoping and I print x instead of calling b() in procedure c, what is the output? Will there be an error?

[Giovanni Lobitos]

This one is really straightforward.