Имеет ли лексический охват динамический аспект?

Question

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

Вот очень простой пример, когда одна функция имеет два замыкания с разными значениями для a.

def elvis(a): 
    def f(s): 
    return a + ' for the ' + s 
    return f 

f1 = elvis('one') 
f2 = elvis('two') 
print f1('money'), f2('show') 

У меня нет никаких проблем с идеей, что, когда мы читаем код для функции f, когда мы видим a, оно не определенно в f, поэтому мы выскочим функцию ограждающей и найти один там , и это относится к a в f. Расположение в исходном коде достаточно, чтобы сообщить мне, что f получает значение для a из охватывающей области.

Но, как описано here, при вызове функции его локальный фрейм расширяет свою родительскую среду. Таким образом, просмотр окружения во время выполнения не является проблемой. Но я не уверен в том, что статический анализатор всегда может выработать , к которому относится закрытие во время компиляции, прежде чем код будет запущен. В приведенном выше примере очевидно, что у elvis есть два закрытия, и их легко отслеживать, но в других случаях это будет не так просто. Интуитивно я нервничаю, что попытка статического анализа может столкнуться с проблемой остановки вообще.

Точно так же лексическая область видимости имеет динамический аспект, где местоположение в исходном коде говорит нам о том, что область охвата задействована, но не обязательно, к какому закрытию относится? Или это проблема решена в компиляторах, и все ссылки в рамках функций на их закрытие действительно могут быть детализированы подробно статически?

Или ответ зависит от языка программирования - в этом случае лексическая область обзора не такая сильная, как я думал?

[EDIT @comments:

С точки зрения моего примера я могу переформулировать мой вопрос: Я прочитал требования, как «Лексическая разрешение может быть определено во время компиляции,» еще задавался вопросом, как ссылки на значения a в f1 и f2 можно было бы разработать статически/во время компиляции (в общем).

Решение состоит в том, что лексическое охват не требует так много. Л.С. может сообщить нам, во время компиляции, что что-то под названием a будет определяться всякий раз, когда я нахожусь в f (и это, очевидно, может быть выработано статически, это определение лексической области), но определяющее значение значение (или закрытие которого активно): 1) за пределами LS концепция, 2) выполняется во время выполнения (не статически), поэтому в некотором смысле динамична, но, конечно же, 3) использует правило, отличное от динамического охвата.

Сообщение о выводе, цитируемое @PatrickMaupin, гласит: «Некоторая динамическая работа еще должна быть выполнена». ]

Answer 1

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

def foo(x): 
    y = 1 
    z = 2 
    def bar(a): 
     return (x, y, a) 
    return bar 

окр захвата решение выглядит:

1. foo вводится и местный кадр построен, который содержит x , y, z, bar фамилии. Название x связан с параметром, имя y и z на 1 и 2, название bar к закрытию
2. закрытие назначается bar фактически захватывает весь родительский кадр так, когда он назвал это может поиск имя a в его собственный локальный кадр и может искать x и y вместо этого в захваченном родительском кадре.

При таком подходе (т.е. не подход, используемый Python) переменная z будет оставаться в живых до тех пор, пока крышка остается в живых, даже если он не ссылается закрытия.

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

1. во время компиляции кода анализируется и закрытие назначается bar обнаруживается захватывая имена x и y из текущей области.
2. эти две переменные поэтому классифицируются как «ячейки», и они выделяются отдельно от локального фрейма. Замыкание хранит адрес этих переменных, и каждый доступ к ним требует двойной косвенности (ячейка является указателем на то, где значение фактически сохранено)

Для этого требуется заплатить немного дополнительного времени, когда создается замыкание, потому что каждая отдельная захваченная ячейка должна быть скопирована внутри объекта замыкания (вместо простого копирования указателя на родительский кадр) но имеет то преимущество, что не захватывает весь кадр, так что, например, z не останется в живых после возвращения foo, только x и y будет.

Это то, что делает Python ... в основном во время компиляции, когда выполняется замыкание (или именованная функция или lambda), выполняется подкомпиляция. Во время компиляции, когда есть поиск, который разрешает родительскую функцию, переменная помечена как ячейка.

Одно небольшое раздражение заключается в том, что при взятии параметра (например, в примере foo) также необходимо выполнить дополнительную операцию копирования в прологе, чтобы преобразовать переданное значение в ячейку. Это в Python не отображается в байт-коде, но выполняется непосредственно механизмом вызова.

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

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

Чтобы увидеть, как это работает в Python вы можете использовать dis модуль для проверки сгенерированного байткода:

>>> dis.dis(foo) 
    2   0 LOAD_CONST    1 (1) 
       3 STORE_DEREF    1 (y) 

    3   6 LOAD_CONST    2 (2) 
       9 STORE_FAST    1 (z) 

    4   12 LOAD_CLOSURE    0 (x) 
      15 LOAD_CLOSURE    1 (y) 
      18 BUILD_TUPLE    2 
      21 LOAD_CONST    3 (<code object bar at 0x7f6ff6582270, file "<stdin>", line 4>) 
      24 LOAD_CONST    4 ('foo.<locals>.bar') 
      27 MAKE_CLOSURE    0 
      30 STORE_FAST    2 (bar) 

    6   33 LOAD_FAST    2 (bar) 
      36 RETURN_VALUE 
>>> 

, как вы можете видеть, сгенерированный код хранит 1 в y с STORE_DEREF (операциями, записывающих на ячейка, таким образом, используя двойную косвенность) и вместо этого хранит 2 в z с использованием STORE_FAST (z не было записано и является локальным в текущем кадре). Когда начинается код foo, x уже завернут в ячейку машиной вызова.

bar просто локальная переменный, так STORE_FAST используется для записи в него, но построить закрытие x и y должны быть скопированы по отдельности (они помещаются в кортеж перед вызовом MAKE_CLOSURE опкода).

Код для самого закрытия виден с:

>>> dis.dis(foo(12)) 
    5   0 LOAD_DEREF    0 (x) 
       3 LOAD_DEREF    1 (y) 
       6 LOAD_FAST    0 (a) 
       9 BUILD_TUPLE    3 
      12 RETURN_VALUE 

и вы можете увидеть, что внутри возвращаемое закрытие x и y доступны с LOAD_DEREF. Независимо от того, сколько уровней «вверх» в иерархии вложенных функций определяется переменной, это действительно просто двойная обратная связь, потому что цена выплачивается при построении закрытия. Замкнутые переменные лишь немного медленнее для доступа (по постоянному коэффициенту) по отношению к местным жителям ... никакая «цепочка цепей» не должна пересекаться во время выполнения.

Компиляторы, которые являются еще более сложными, такими как SBCL (оптимизирующий компилятор для Common Lisp, генерирующего собственный код), также выполняют «анализ побега», чтобы определить, может ли замыкание действительно выжить в закрывающей функции. Если этого не происходит (например, если bar используется только внутри foo и не сохраняется или не возвращается), ячейки могут быть выделены в стеке вместо кучи, уменьшая количество времени выполнения «consing» (выделение объектов в куче которые требуют утилизации мусора).

Это различие находится в литературе, известной как «нисходящая/направленная вверх»; то есть, если захваченные переменные видны только на нижних уровнях (то есть в закрытии или в более глубоких замыканиях, созданных внутри крышки) или также на верхних уровнях (то есть, если мой вызывающий абонент сможет получить доступ к моим захваченным местным жителям).

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

Answer 2

Решена проблема ... в любом случае. Python использует чисто лексическое охват, а замыкание определяется статически. Другие языки допускают динамическое масштабирование - и закрытие определяется во время выполнения, поиск его пути вверх по стеку вызовов во время выполнения вместо стека анализа.

Достаточно ли этого объяснения?

Answer 3

В Python переменная определяется как локальная, если она когда-либо назначена (отображается в LHS присвоения) и явно не объявлена ​​глобальным или нелокальным.

Таким образом, можно обрабатывать лексическую схему лексической цепи, чтобы статически определить, какой идентификатор будет найден в этой функции. Однако необходимо выполнить некоторую динамическую работу, поскольку вы можете произвольно вложить функции, поэтому, если функция A включает функцию B, которая включает в себя функцию C, то для функции C для доступа к переменной из функции A вы должны найти правильный кадр для A. (То же самое для закрытия.)