静态(词法)作用域与动态作用域(伪代码) [英] Static (Lexical) Scoping vs Dynamic Scoping (Pseudocode)

问题描述

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

据我了解，使用静态作用域运行该程序的结果是:x = 13，y = 7和z = 2.

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

但是，当使用动态作用域运行该程序时，结果为:x = 10，y = 7和z = 12.

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?

推荐答案

使用静态(词法)作用域，程序源代码的结构确定了您要引用的变量.通过动态作用域，程序堆栈的运行时状态可以确定要引用的变量.这可能是一个非常陌生的概念，因为基本上今天广泛使用的每种编程语言(也许emacs lisp除外)都使用词法作用域，这对于人类和分析工具而言都容易进行推理.

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

程序和编译器将这两个变量都称为x，但为了方便下面的讨论，我将它们标记为x1和x2.

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

使用词法作用域，我们在编译时根据程序源代码的静态词法结构确定要引用的x. 定义 b时，作用域中x的最内层定义为x1，因此所讨论的写入解析为x1，这就是x = 2写入的位置，因此我们打印2运行该程序.

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.

通过动态作用域，我们可以在运行时跟踪变量定义的堆栈-因此我们要写入的x取决于范围内的确切范围，并且是在运行时动态定义的.开始运行a将x => x1压入堆栈，调用c将x => x2压入堆栈，然后当我们到达b时，堆栈的顶部是x => x2，所以我们写进入x2.这使x1保持不变，因此我们在程序末尾打印1.

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();
}

注意b被调用两次-第一次通过c，第二次直接.使用词法作用域时，上面的解释没有改变，我们都写了x1.但是，使用动态作用域时，它取决于在运行时如何绑定x.第一次调用b时，如上所述，我们写入了x2；但是第二次，我们写入了x1，因为这就是堆栈的顶部！ (c返回时会弹出x => x2.)

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
}

这里是动态作用域.请注意，仅更改位于B和*标记的位置:

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

这篇关于静态(词法)作用域与动态作用域(伪代码)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！