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?

Answer 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;
}