静态(词法)范围与动态范围(伪代码) [英] Static (Lexical) Scoping vs Dynamic Scoping (Pseudocode)
问题描述
程序A(){x、y、z:整数；程序B(){y:整数；y=0;x=z+1;z=y+2;}程序 C(){z:整数；程序 D(){x:整数；x = z + 1;y = x + 1;调用 B();}z = 5;调用 D();}x = 10;y = 11;z = 12;调用 C();打印 x、y、z；}据我所知，这个程序在使用静态范围运行时的结果是:x=13, y=7, and z=2.
但是，当它使用动态范围运行时，结果是:x=10、y=7 和 z=12.
这些结果是我们教授给我们的.然而，我终生无法理解他是如何达到这些结果的.有人可能会遍历伪代码并在两种不同类型的范围内解释它们的值吗?
使用静态(词法)范围，程序源代码的结构决定了您所引用的变量.使用动态范围，程序堆栈的运行时状态决定了您所指的变量.这可能是一个非常陌生的概念，因为基本上今天广泛使用的每种编程语言(可能除了 emacs lisp)都使用词法范围，这对于人类和分析工具来说都更容易推理.
考虑这个简单得多的示例程序(用您的伪代码语法编写):
program a() {x:整数；//下面讨论中的x1"x = 1;过程 b() {x = 2;//<-- 我们写入哪个x"?}过程 c() {x:整数；//下面讨论中的x2"b();}C();打印 x;}程序和编译器将这两个变量都称为 x，但我将它们标记为 x1 和 x2 以简化下面的讨论.>
使用词法范围，我们在编译时根据程序源代码的静态词法结构确定我们所指的是哪个 x.当定义 b时，x在作用域中的最内层定义是x1，因此有问题的写入解析为x1，这就是 x = 2 写入的地方，所以我们在运行这个程序时打印 2.
使用动态范围，我们有一堆在运行时跟踪的变量定义——因此我们写入哪个 x 取决于范围内的确切内容，并且在运行时动态定义了.开始运行 a 推送 x =>;x1 入栈，调用 c 压入 x =>;x2 到栈中，然后当我们到达 b 时，栈顶是 x =>x2，所以我们写入x2.这使得 x1 保持不变，因此我们在程序末尾打印 1.
此外，考虑这个略有不同的程序:
program a() {x:整数；//下面讨论中的x1"x = 1;过程 b() {x = 2;//<-- 我们写入哪个x"?}过程 c() {x:整数；//下面讨论中的x2"b();}C();b();}注意b被调用了两次——第一次通过c，第二次直接调用.对于词法范围，上面的解释没有改变，我们两次都写入 x1 .但是，对于动态范围，它取决于 x 在运行时的绑定方式.我们第一次调用 b 时，我们写入 x2 如上所述 - 但第二次，我们写入 x1，因为这就是在堆栈的顶部！(x => x2 在 c 返回时弹出.)
所以，这是您教授的代码，注释了哪个确切变量用于哪个写有词法范围.在程序末尾打印的写入用 * 标记:
程序A(){x、y、z:整数；//x1, y1, z1程序B(){y:整数；//y2y=0;//y2 = 0x=z+1;//x1 = z1 + 1 = 12 + 1 = 13*z=y+2;//z1 = y2 + 2 = 0 + 2 = 2*}程序 C(){z:整数；//z2程序 D(){x:整数；//x2x = z + 1;//x2 = z2 + 1 = 5 + 1 = 6y = x + 1;//y1 = x2 + 1 = 6 + 1 = 7*调用 B();}z = 5;//z2 = 5调用 D();}x = 10;//x1 = 10y = 11;//y1 = 11z = 12;//z1 = 12调用 C();打印 x、y、z；//x1, y1, z1}这里是动态范围.请注意，唯一的更改位于 B 和 * 标记的位置:
程序A(){x、y、z:整数；//x1, y1, z1程序B(){y:整数；//y2y=0;//y2 = 0x=z+1;//x2 = z2 + 1 = 5 + 1 = 6z=y+2;//z2 = y2 + 2 = 0 + 2 = 2}程序 C(){z:整数；//z2程序 D(){x:整数；//x2x = z + 1;//x2 = z2 + 1 = 5 + 1 = 6y = x + 1;//y1 = x2 + 1 = 6 + 1 = 7*调用 B();}z = 5;//z2 = 5调用 D();}x = 10;//x1 = 10*y = 11;//y1 = 11z = 12;//z1 = 12*调用 C();打印 x、y、z；}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?
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;
}
这篇关于静态(词法)范围与动态范围(伪代码)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
