Динамический / Статический прицел с Глубоким / Мелким переплетом (упражнения)

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;

Что печатается на экране

а) используя статическую область видимости? ответ = 180

б) использование динамического объема и глубокого связывания? answer = 69 (сумма для u = 126, но это локальная переменная foo, верно?)

в) использование динамического объема и мелкой привязки? answer = 69 (сумма для u = 101, но это локальная переменная foo, верно?)

PS: я пытаюсь выполнять некоторые упражнения, подобные этим, если вы знаете, где я могу найти такие типы проблем (желательно с решениями), пожалуйста, дайте ссылку, спасибо!

Answer 1

Ваш ответ для лексической (статической) области является правильным. Ваши ответы о динамическом охвате неверны, но если я правильно читаю ваши объяснения, то это из-за того, что вы запутались между u и v, а не из-за реального недопонимания того, как работает глубокая и поверхностная привязка. (Я предполагаю, что ваша u / v путаница была просто случайной, а не из-за странной путаницы между значениями и ссылками в вызове foo.)

а) используя статическую область видимости? ответ = 180

Correct.

б) использование динамического объема и глубокого связывания? answer = 69 (сумма для u = 126, но это локальная переменная foo, верно?)

Ваше объяснение в скобках верно, но ваш ответ неправильный: u действительно установлен на 126, а foo действительно локализует v, но, поскольку main печатает u, а не v ответ 126.

в) использование динамического объема и мелкой привязки? answer = 69 (сумма для u = 101, но это локальная переменная foo, верно?)

Сумма для u на самом деле 97 (42+13+42), но, поскольку bar локализует u, ответ будет 42. (Ваше объяснение в скобках неверно для этого - вы, похоже, использовали глобальную переменную w, равную 17, при интерпретации оператора int u := w в определении bar; но это утверждение фактически относится к Локальная переменная foo w, ее второй параметр, 13. Но это на самом деле не влияет на ответ. Ваш ответ неверен только потому, что main печатает u, а не v.)

---

Что касается лексической области видимости, то довольно легко проверить свои ответы, переведя псевдокод на язык с лексической областью видимости. Аналогично динамический прицел с мелкой привязкой. (На самом деле, если вы используете Perl, вы можете протестировать оба способа почти одновременно, поскольку он поддерживает оба; просто используйте my для лексической области, затем выполните поиск и замену, чтобы изменить его на local для динамической области Но даже если вы используете, скажем, 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

Статическое связывание , также известное как лексическая область действия , относится к механизму определения объема, найденному в большинстве современных языков.

In "лексическийscope ", окончательное значение для вас не равно 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».

• Значение данной переменной извлекается из обхода стека сверху вниз, пока не будет найдена привязка для данной переменной.
• Обновлениепеременная состоит в нахождении привязки в стеке и обновлении связанного значения.
• При вводе подпрограммы новая привязка для каждого фактического параметра помещается в стек, потенциально скрывая более старую привязку, которая, следовательно, больше не являетсядоступный по описанному выше механизму извлечения (который останавливается на 1-й извлеченной привязке).
• При выходе из подпрограммы привязки для этих параметров просто извлекаются из стека привязок, таким образом, вновь предоставляя доступ к прежним привязкам.

Пожалуйста, смотрите код ниже для реализации 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) для доступа к значениям переменной!)
• Обновление значения переменной - это просто сохранение значения в ячейке переменной.
• Создание новогоПривязка (входящие в подпрограммы) работает путем помещения старого значения переменной (предыдущей привязки) в стек и сохранения нового локального значения в ячейке значения.
• Удаление привязки (оставляя подпрограммы) работает путем выталкиваниястарое значение из стека в ячейку значения переменной.

Пожалуйста, смотрите код ниже для тривиальной реализации Perl в shaдинамическая область видимости.

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

В заключение запомните две вещи:

• поверхностное связывание дает те же результаты, что и глубокое связывание , но работает быстрее, поскольку поиск привязки никогда не требуется.

• Проблема не в поверхностном связывании против в глубоком связывании против
  статическом связывании НО лексическом объеме против динамический охват (реализован с глубоким или неглубоким связыванием).

Answer 3

Простое и глубокое связывание - это точки зрения интерпретатора 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.