具有深/浅绑定的动态/静态范围（练习）

Question

我正在研究具有深/浅绑定的动态/静态作用域，并手动运行代码，以了解这些不同的作用域/绑定实际上是如何工作的。我阅读了理论并用谷歌搜索了一些示例练习，我发现的练习非常简单（例如 这个对于动态作用域非常有帮助）但是我很难理解静态作用域是如何工作的。

在这里，我发布了一个练习，以检查我是否获得了正确的解决方案：

考虑以下用伪代码编写的程序：

int u = 42; 
int v = 69;
int w = 17;
proc add( z:int )
  u := v + u + z
proc bar( fun:proc )
  int u := w;
  fun(v)
proc foo( x:int, w:int )
  int v := x;
  bar(add)
main
  foo(u,13)
  print(u)
end;

打印到屏幕上的内容是什么

使用静态作用域 a) ？答案=180

b) 使用动态作用域和深度绑定？答案= 69（u的总和= 126，但它是foo的本地v，对吗？）

c）使用动态作用域和浅绑定？答案= 69（u = 101的总和，但它是foo的本地v，对吧？）

PS：我正在尝试练习做一些这样的练习，如果你知道我在哪里可以找到这些类型的问题（最好有解决方案），请给出链接，谢谢！

Answer 1

您对词法（静态）范围的回答是正确的。您对动态范围的回答是错误的，但如果我正确地阅读了您的解释，那是因为您在 u 和 v 之间感到困惑，而不是因为对深度和浅层绑定的工作原理。 （我假设您的 u/v 混淆只是偶然的，而不是由于对 foo< 的调用中的值与引用的奇怪混淆/代码>。）

a) 使用静态作用域？答案=180

正确。

b) 使用动态作用域和深度绑定？ answer=69（u 的总和 = 126，但它是 foo 的本地 v，对吧？）

您的括号解释是正确的，但您的答案是错误的：u 确实设置为 126 ，并且 foo 确实本地化了 v，但由于 main 打印 u，而不是 v ，答案是126。

c) 使用动态作用域和浅绑定？ answer=69（u 的总和 = 101，但它是 foo 的本地 v，对吗？）

u 的总和实际上是 97 (42+13+42 code>），但由于 bar 本地化了 u，所以答案是 42。 （您的括号解释对此是错误的 - 您似乎在解释语句 int u := w 时使用了全局变量 w，即 17 在 bar 的定义中，但该语句实际上引用了 foo 的局部变量 w，它的第二个参数是13 但这实际上并不影响答案。 v。）

---

对于词法作用域，通过将伪代码翻译成具有词法作用域的语言来检查您的答案非常容易。同样具有浅绑定的动态作用域。 （事实上​​，如果您使用 Perl，您几乎可以同时测试这两种方式，因为它支持这两种方式；只需使用 my 作为词法范围，然后执行查找和替换将其更改为 <但是，即使您使用 JavaScript 作为词法作用域，使用 Bash 作为动态作用域，测试两者也应该很快。）

具有深度绑定的动态作用域要棘手得多，因为很少有广泛的应用。 - 部署的语言支持它。如果您使用 Perl，则可以通过使用从变量名映射到标量引用的哈希（关联数组）并将此哈希从一个函数传递到另一个函数来手动实现它。在伪代码声明局部变量的任何地方，您都将现有的标量引用保存在 Perl 词法变量中，然后将新的映射放入哈希中；在函数结束时，您恢复原始标量引用。为了支持绑定，您可以创建一个包装函数来创建哈希的副本，并将该传递给其包装函数。这是使用该方法在 Perl 中动态范围、深度绑定的程序实现：

#!/usr/bin/perl -w

use warnings;
use strict;

# Create a new scalar, initialize it to the specified value,
# and return a reference to it:
sub new_scalar($)
  { return \(shift); }

# Bind the specified procedure to the specified environment:
sub bind_proc(\%$)
{
  my $V = { %{+shift} };
  my $f = shift;
  return sub { $f->($V, @_); };
}

my $V = {};

$V->{u} = new_scalar 42; # int u := 42
$V->{v} = new_scalar 69; # int v := 69
$V->{w} = new_scalar 17; # int w := 17

sub add(\%$)
{
  my $V = shift;
  my $z = $V->{z};                     # save existing z
  $V->{z} = new_scalar shift;          # create & initialize new z
  ${$V->{u}} = ${$V->{v}} + ${$V->{u}} + ${$V->{z}};
  $V->{z} = $z;                        # restore old z
}

sub bar(\%$)
{
  my $V = shift;
  my $fun = shift;
  my $u = $V->{u};                     # save existing u
  $V->{u} = new_scalar ${$V->{w}};     # create & initialize new u
  $fun->(${$V->{v}});
  $V->{u} = $u;                        # restore old u
}

sub foo(\%$)
{
  my $V = shift;
  my $x = $V->{x};                     # save existing x
  $V->{x} = new_scalar shift;          # create & initialize new x
  my $w = $V->{w};                     # save existing w
  $V->{w} = new_scalar shift;          # create & initialize new w
  my $v = $V->{v};                     # save existing v
  $V->{v} = new_scalar ${$V->{x}};     # create & initialize new v
  bar %$V, bind_proc %$V, \&add;
  $V->{v} = $v;                        # restore old v
  $V->{w} = $w;                        # restore old w
  $V->{x} = $x;                        # restore old x
}

foo %$V, ${$V->{u}}, 13;
print "${$V->{u}}\n";

__END__

实际上它打印了 126。这显然很混乱且容易出错，但它也确实可以帮助您了解正在发生的事情，因此出于教育目的，我认为这是值得的！

Answer 2

简单绑定和深度绑定是 Lisp 解释器对伪代码的看法。作用域只是指针算术。如果没有自由变量，动态作用域和静态作用域是相同的。

静态作用域依赖于指向内存的指针。空旷的环境没有任何价值联想的象征；用“结束”一词表示。每次解释器读取一个赋值时，它都会为符号和值之间的关联腾出空间。

环境指针更新为指向最后构建的关联。

env = End  
env = [u,42] -> End
env = [v,69] -> [u,42] -> End
env = [w,17] -> [v,69] -> [u,42] -> End    

让我将此环境内存位置记录为AAA。在我的 Lisp 解释器中，当遇到一个过程时，我们将环境指针放在口袋里。

env = [add,[closure,(lambda(z)(setq u (+ v u z)),*AAA*]]->[w,17]->[v,69]->[u,42]->End.

这几乎就是调用过程 add 之前的全部内容。有趣的是，如果 add 从未被调用，那么您只会花费一个指针。

假设程序调用add(8)。好吧，让我们滚吧。环境 AAA 已设为当前环境。环境是->[w,17]->[v,69]->[u,42]->End。

add的过程参数被添加到环境的前面。环境变为[z,8]->[w,17]->[v,69]->[u,42]->End。

现在add的过程体被执行。自由变量v的值为69。自由变量u的值为42。 z 的值为 8。

u := v + u + z

u 将被赋值为 69 + 42 + 8，变为 119。

环境将反映这一点：[z,8]->[w,17]->[v,69]->[u,119]->End。

假设过程add 已完成其任务。现在环境已恢复到以前的值。

env = [add,[closure,(lambda(z)(setq u (+ v u z)),*AAA*]]->[w,17]->[v,69]->[u,119]->End.

请注意过程 add 如何产生更改自由变量 u 值的副作用。惊人的！

关于动态作用域：它只是确保闭包忽略动态符号，从而避免被捕获并变得动态。

然后将动态赋值放在代码顶部。如果动态与参数名称相同，它将被传入的参数值屏蔽。

假设我有一个名为 z 的动态变量。当我调用 add(8) 时，无论我想要什么，z 都会被设置为 8。这可能就是动态变量名称更长的原因。

有传言说动态变量对于回溯、使用 let Lisp 构造等事情很有用。

Answer 3

静态绑定，也称为词法作用域，指的是大多数现代语言中的作用域机制。

在“词法范围”中，u 的最终值既不是 180 也不是 119，这是错误的答案。

正确答案是u=101。

请参阅下面的标准 Perl 代码以了解原因。

use strict;
use warnings;

my $u = 42;
my $v = 69;
my $w = 17;

sub add {
    my $z = shift;
    $u = $v + $u + $z;
}

sub bar {
    my $fun = shift;
    $u = $w;
    $fun->($v);
}

sub foo {
    my ($x, $w) = @_;
    $v = $x;
    bar( \&add );
}

foo($u,13);
print "u: $u\n";

关于浅层绑定与深度绑定，这两种机制都可以追溯到以前的LISP时代。

这两种机制都是为了实现动态绑定（相对于词法作用域绑定），因此它们产生相同的结果！

浅层绑定和深层绑定之间的区别不在于语义（它们是相同的），而是在于动态绑定的实现。

使用深度绑定，变量绑定在堆栈中设置为“varname => varvalue”对。

• 通过从上到下遍历堆栈来检索给定变量的值，直到找到给定变量的绑定。
• 更新变量包括在堆栈中查找绑定并更新关联值。
• 在进入子例程时，每个实际参数的新绑定被推入堆栈，可能隐藏旧的绑定，因此无法再通过上述检索机制访问（在第一个检索到的绑定处停止）。
• 离开子例程时，这些参数的绑定只是从绑定堆栈中弹出，从而重新启用对以前的绑定的访问。

请参阅下面的代码，了解深度绑定动态作用域的 Perl 实现。

use strict;
use warnings;
use utf8;

##
# Dynamic-scope deep-binding implementation
my @stack = ();

sub bindv {
    my ($varname, $varval);

    unshift @stack, [ $varname => $varval ]
        while ($varname, $varval) = splice @_, 0, 2;

    return $varval;
}

sub unbindv {
    my $n = shift || 1;
    shift @stack while $n-- > 0;
}

sub getv {
    my $varname = shift;

    for (my $i=0; $i < @stack; $i++) {
        return $stack[$i][1]
            if $varname eq $stack[$i][0];
    }

    return undef;
}

sub setv {
    my ($varname, $varval) = @_;

    for (my $i=0; $i < @stack; $i++) {
        return $stack[$i][1] = $varval
            if $varname eq $stack[$i][0];
    }
    return bindv($varname, $varval);
}

##
# EXERCICE
bindv(  u => 42,
        v => 69,
        w => 17,
);

sub add {
    bindv(z => shift);

     setv(u => getv('v')
               + getv('u')
               + getv('z')
    );

    unbindv();
}

sub bar {
    bindv(fun => shift);

     setv(u   => getv('w'));
    getv('fun')->(getv('v'));

    unbindv();
}

sub foo {
    bindv(x => shift,
          w => shift,
    );

     setv(v => getv('x'));
    bar( \&add );

    unbindv(2);
}

foo( getv('u'), 13);
print "u: ", getv('u'), "\n";

结果是 u=97

然而，这种对绑定堆栈的不断遍历是昂贵的：0(n) 复杂性！

浅绑定与之前的实现相比，带来了美妙的O(1)增强性能！

浅绑定通过为每个变量分配自己的“单元格”来改进前一种机制，并将变量的值存储在单元格内。

• 给定变量的值只是从变量的
  单元格（使用变量名称的哈希表，我们实现了
  0(1) 访问变量值的复杂性！）
• 更新变量的值只是将值存储到
  变量的单元格。
• 创建新绑定（输入 subs）通过推送旧值来工作
  将变量（先前的绑定）放入堆栈，并存储
  值单元格中的新本地值。
• 通过弹出旧值来消除绑定（留下 subs）
  从堆栈中移出到变量的值单元格中。

请参阅下面的代码，了解浅绑定动态作用域的简单 Perl 实现。

use strict;
use warnings;

our $u = 42;
our $v = 69;
our $w = 17;
our $z;
our $fun;
our $x;

sub add {
    local $z = shift;
    $u = $v + $u + $z;
}

sub bar {
    local $fun = shift;
    $u = $w;
    $fun->($v);
}

sub foo {
    local $x = shift;
    local $w = shift;
    $v = $x;
    bar( \&add );
}

foo($u,13);
print "u: $u\n";

正如您将看到的，结果仍然是u=97

作为结论，请记住两件事：

• 浅绑定产生与深度绑定相同的结果< /em>，但运行速度更快，因为永远不需要搜索绑定。

• 问题不在于浅层绑定与深层绑定与
  静态绑定但是词法作用域与动态作用域（通过深度或浅层绑定实现）。