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

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

Здесь я опубликую упражнение, чтобы проверить, правильно ли я нашел решение:

учитывая следующую программу, написанную в псевдокоде:

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: я пытаюсь выполнять некоторые упражнения, подобные этим, если вы знаете, где я могу найти такие проблемы (желательно с решениями), пожалуйста, дайте ссылку, спасибо!

Ответы на вопрос(3)

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

В «лексической области видимости» конечное значение u не равно 180 или 119, что является неправильным ответом.

Правильный ответи = 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";

Результати = 97

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

Мелкая привязка приносит замечательныйO (1) улучшенная производительность по сравнению с предыдущей реализацией!

Мелкая привязка совершенствует прежний механизм, присваивая каждой переменной свою собственную «ячейку», сохраняя значение переменной внутри ячейки.

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

Пожалуйста, смотрите код ниже для тривиальной реализации 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";

Как вы увидите, результат все ещеи = 97

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

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

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

 Joshua Taylor17 дек. 2015 г., 19:00
«поверхностное связывание дает те же результаты, что и глубокое связывание, но работает быстрее, так как поиск привязки никогда не требуется». В большинстве случаев результаты совпадают, но не тогда, когда вы начинаете передавать функции. Например, см.stackoverflow.com/questions/34051146/shallow-and-deep-binding .
Решение Вопроса

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

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

Правильный.

б) используя динамический охват и глубокое связывание? 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, Это очевидно грязно и подвержено ошибкам, но это также действительно помогает вам понять, что происходит, поэтому в образовательных целях я думаю, что оно того стоит!

 ruakh12 февр. 2013 г., 06:20
@JustinGingyMcDonald: Всегда пожалуйста!
 Justin McDonald12 февр. 2013 г., 05:43
молодец спасибо!

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

Окружающая среда будет отражать это:[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, Потрясающие!

Что касается динамической области видимости: он просто гарантирует, что закрытие пропускает динамические символы, тем самым избегая захвата и превращения в динамический.

Затем поместите присваивание динамического в верхней части кода. Если dynamic совпадает с именем параметра, он маскируется значением параметра, переданным в.

Предположим, у меня была динамическая переменнаяz, Когда я позвонилadd(8), z был бы установлен в8 независимо от того, что я хотел. Вероятно, поэтому динамические переменные имеют более длинные имена.

Ходят слухи, что динамические переменные полезны для таких вещей, как возврат, с использованием конструкций let Lisp.

 Pops18 нояб. 2011 г., 17:40
(Запоздало) добро пожаловать в Stack Overflow, Терри! Спасибо за подробный ответ. В будущем, пожалуйста, проверьте справку по форматированию, встроенную в редактор; вы, вероятно, хотели выделить примеры кода, но в итоге весь ответ превратили в большой блок кода, потому что редактор недостаточно умен, чтобы понимать разницу между текстом и кодом.

Ваш ответ на вопрос