Что такое свободные и связанные переменные?

Question

Я программировал долгое время (на самом деле слишком долго), но я действительно изо всех сил пытаюсь понять термины "Свободные переменные" и "Связанные переменные".

Большинство "объяснений", которые я нашел в Интернете, начинаются с обсуждения таких тем, как лямбда-исчисление и формальная логика или аксиоматическая семантика. что заставляет меня хотеть достать мой револьвер.

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

Answer 1

Свободная переменная - это переменная, используемая в некоторой функции, значение которой зависит от контекста, в котором функция вызывается, вызывается или используется. Например, в математических терминах, z является свободной переменной, потому что не ограничен никаким параметром. x является ограниченной переменной:

f(x) = x * z

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

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

Свободная переменная в некотором роде похожа на соглашение " передача по имени " некоторых древних языков программирования.

Допустим, у вас есть функция f это просто печатает некоторую переменную:

def f():
    print(X)

Это Питон. В то время как X не является локальной переменной, ее значение соответствует соглашению Python: она ищет вверх по цепочке блоков, где определена функция, пока не достигнет модуля верхнего уровня.

Так как в Python значение X определяется контекстом объявления функции, мы говорим, что X является ограниченной переменной.

Гипотетически, если X были свободной переменной, это должно вывести 10:

X = 2

def f():
    print(X)

def g():
    # X is a local variable to g, shadowing the global X
    X = 10
    f()

В Python этот код печатает 2, потому что оба X переменные ограничены. Местный X переменная на g ограничен как локальная переменная, а f ограничен глобальным X,

Реализация

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

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

Answer 2

Является ли переменная свободной или связанной, относительна; это зависит от фрагмента кода, который вы просматриваете.

В этом фрагменте х связан:

function(x) {return x + x;};

И здесь x происходит бесплатно:

return x + x;

Другими словами, свобода является свойством контекста. Вы не говорите "x является свободной переменной" или "x является связанной переменной", но вместо этого определяете контекст, о котором говорите: "x свободен в выражении E". По этой причине одна и та же переменная x может быть либо свободной, либо связанной, в зависимости от того, о каком фрагменте кода вы говорите. Если фрагмент содержит сайт привязки переменной (например, он указан в аргументах функции), то он связан, если нет, то он свободен.

Где различие между свободным и связанным важно с точки зрения реализации, когда вы реализуете, как работает подстановка переменных (например, что происходит, когда вы применяете аргументы к функции.) Рассмотрите этапы оценки:

(function(x) {return x + x;})(3);
=> 3 + 3
=> 6

Это работает нормально, потому что x свободен в теле функции. Однако, если x был связан в теле функции, наша оценка должна быть осторожной:

(function(x) {return (function(x){return x * 2;})(x + x);})(3);
=> (function(x){return x * 2;})(3 + 3); // careful to leave this x alone for now!
=> (function(x){return x * 2;})(6);
=> 6 * 2
=> 12

Если бы наша реализация не проверяла наличие вхождений, она могла бы заменить ограничение x для 3 и дал нам неправильный ответ:

(function(x) {return (function(x){return x * 2;})(x + x);})(3);
=> (function(x){return 3 * 2;})(3 + 3); // Bad! We substituted for a bound x!
=> (function(x){return 3 * 2;})(6);
=> 3 * 2
=> 6

Также следует уточнить, что free vs. bound является свойством синтаксиса (то есть самого кода), а не свойством того, как код оценивается во время выполнения. vz0 говорит о динамически изменяемых переменных, которые в некоторой степени связаны со свободными переменными, но не синонимичны с ними. Как правильно описывает vz0, область динамических переменных - это языковая функция, которая позволяет оценивать выражения, содержащие свободные переменные, просматривая стек вызовов во время выполнения, чтобы найти значение переменной с таким же именем. Однако все же имеет смысл говорить о свободных вхождениях переменных в языках, которые не допускают динамическую область видимости: вы просто получите ошибку (например, "x не определен"), если попытаетесь оценить такое выражение в этих языки.

И я не могу с собой поделать: я надеюсь, что однажды ты найдешь в своем сердце, чтобы убрать свои револьверы, когда люди упоминают лямбда-исчисление! Лямбда-исчисление является хорошим инструментом для размышлений о переменных и привязках, потому что это чрезвычайно минимальный язык программирования, который поддерживает переменные и подстановку и ничего больше. Реальные языки программирования содержат много другого мусора (например, динамической области видимости), который скрывает суть.