Что такое функции/закрытие/Lambdas, с точки зрения структуры данных?

Question

На днях я поговорил о некоторых подробных деталях языков программирования, и одна тема, которая была поднята, - это то, что функция (или закрытие/лямбда/и т. Д.) Фактически «есть» с точки зрения структуры данных. Чтобы быть ясным, я не спрашиваю, какие функции делают или как они используются, а скорее как они представлены в коде «за кулисами».

Когда функция «вызывается», что происходит при выполнении кода? Является ли функция структурой или объектом какого-либо типа, который передается с использованием идентификатора? Является ли функция, даже представленная структурой данных вообще? Значит ли это значительно отличается от языка к языку, или же функции, как правило, представлены таким же образом в скомпилированном/интерпретируемом коде? Я всегда считал, что функции - это всего лишь наборы операций, которые влияют на данные, и что они не существуют в какой-либо форме структуры/объекта, но затем я начал задаваться вопросом, потому что есть много случаев, когда функции рассматриваются как переменные/параметры и могут быть использованы способом, очень похожим на структуры или объекты, например, с закрытием.

Пример в Swift:

let closure = {(firstInt: Int, secondInt: Int) -> Bool in 
    return firstInt > secondInt 
} 

Как такое поведение работает (в Swift или любом языке, который поддерживает закрытие)? Что хранится в постоянной «закрытия»? Когда я вызываю .map (function, iterable) в Python, что «отправляется» на этот вызов для представления функции? Я надеюсь, что этот вопрос не кажется слишком широким, но я подумал, что было бы интересно и, возможно, полезно узнать, как строятся и работают функции. Большинство людей, с которыми я столкнулся, похоже, сосредоточены только на деталях того, как переменные/структуры/объекты и т. Д. работают, не обращая внимания (или, по крайней мере, не столько) на внутреннюю работу функций.

Answer 1

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

Функция значения

В JavaScript функция является только объектом, который может быть заданными свойствами, как и любой другой объект:

var someObj = {}; 
someObj.someProperty = "hey, I have a property now"; 

var someFunc = function(a, b) { return a > b; }; 
someFunc.someProperty = "hey, I have a property now, too"; 

Таким образом, все, что вы можете сделать, чтобы объект, вы можете сделать к функции. Однако объекты функции имеют внутреннее свойство (условное свойство, доступное для механизма выполнения JavaScript, но не доступное для кода JavaScript), называемое [[Code]], а другое внутреннее свойство - [[FormalParameters]]. spec defines these как:

[[Code]] - The ECMAScript код функции.

[[FormalParameters]] - Возможно пустой список, содержащий идентификатор Строки формы FormalParameterList.

Так что, если ваш язык не поддерживает закрытие, что на самом деле все, что вам нужно: список имен параметров и некоторый код для выполнения (здесь, «код» является то, что ваш язык обычно используется, чтобы выразить работоспособный код за пределами функций: скомпилированные двоичные, интерпретируемые команды или промежуточный байт-код). Достаточно легко обрабатывать эти свойства примерно так же, как ваш язык уже относится к нормальным свойствам. Всякий раз, когда вы вызываете someFunc(val1, val2), вы запускаете содержимое свойства [[Code]] после подачи значений для формальных параметров a и b.

Если ваш язык требует ввода возвращаемых значений, это, вероятно, третье свойство, проверенное в момент, когда вы пытаетесь сделать return что-то. Кроме того, на вашем языке могут потребоваться типизированные формальные параметры, в случае wihch рассмотрите список формальных параметров список из {string, type} кортежей.

Затворы

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

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

в JavaScript функции могут видеть все переменные, определенные в функциях, которые их содержат:

function foo() { 
    var qux = 5; 
    function bar() { return qux; } 
    return bar; 
} 

var returnedBar = foo(); 
returnedBar(); 

Здесь bar находится внутри foo, поэтому, когда bar работает, это может выглядеть «вверх» цепочки областей видимости, чтобы увидеть переменную qux из foo.

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

function foo(quxVal) { 
    var qux = quxVal; 
    function bar() { return qux; } 
    return bar; 
} 

var returnedBar1 = foo(1); 
returnedBar1(); 

var returnedBar2 = foo(2); 
returnedBar2(); 

Здесь returnedBar1 и returnedBar2 имеет один и тот же функциональный код, но их лексических сред различны, потому что они имеют разный «родитель» foo вызовов с отличается окружающая среда записи.

Структуры данных Закрытие

В JavaScript область видимости функции на основе. В файле environment record в JavaScript отслеживается, какие переменные содержатся в каждой области, и сопоставляет имена идентификаторов этим переменным. Запись таблица среды может выглядеть следующим образом:

Name Variable 
---- -------- 
foo  [value of this var is whatever is in address 0x34F6A2 right now] 
bar  [value of this var is whatever is in address 0x34F6A6 right now] 

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

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

Это, как мы можем смотреть «вверх» в «родительские» функции, как мы делаем, когда bar смотрит на foo своей стоимости qux.Мы пересекаем цепочку областей видимости, которая является связанным списком структур лексической среды, направленным вверх в более высокие области. Каждая лексическая среда имеет запись об окружающей среде (сопоставление имен идентификаторов переменных для переменных) и указывает на его родительскую лексическую среду.

Когда мы вызываем foo(1) выше, он создает новую лексическую запись среды как часть запуска функции. Эта лексическая среда foo(1) имеет запись об окружающей среде, которая содержит запись для переменной qux внутри foo. Затем, когда мы вызываем bar, это создает другую лексическую среду, которая указывает на родительскую лексическую среду foo(1). (Функция bar имеет внутреннее свойство [[Scope]], которое используется во время вызова функции, чтобы сообщить новой лексической среде, каков ее родитель.) Когда мы вызываем returnedBar1, двигатель ищет переменную qux в записи среды bar; то, когда это не удается, двигатель смотрит на родительскую лексическую среду, чтобы найти qux, объявленный в foo.

Когда мы называем foo(2), мы создаем совершенно новую лексическую среду, а затем мы называем bar создать новую лексическую среду, которая является дочерней лексической средой foo(2). Когда мы звоним returnedBar2, мы распространяем совершенно другую цепочку на foo(2).

С практической точки зрения структуры данных, каждая функция имеет [[Scope]] свойство, установить во время определения, который указывает, какие лексико среда, функция должна использовать в качестве родителя для своего собственного лексического окружения всякий раз, когда работает функция. Запись среды («содержание» лексической среды) может быть представлена ​​как сопоставление имен переменных с переменными (где «переменная» представляет собой структуру с указателем на любое значение, которое в настоящее время представляет переменная).

Заключения

В заключении, вот практические свойства необходимы закрывающий:

• код (своего рода работоспособного кода) - используется для запуска функции
• Список параметров (список имен строк и, необязательно, типы) - используется для идентификации аргументов функции при ее вызове
• Тип возвращаемого (типа) - используется для проверки возвращаемого значения функции
• лексического объект сферы (лексическая среда) - когда функция вызываются, лексическое окружение, созданное во время вызова функции использует этот лексический объект окружающей среды в качестве родителя

лексическая среда состоит из двух частей:

• запись Environment (отображение имен переменных к переменным) - используется, чтобы найти переменную, связанную с (например, нам нужна переменная с именем «qux» - где мы можем установить/получить ее значение в памяти?)
• Родитель лексическая среда (лексический объект среды) - Родитель лексическая среда, используемая в качестве части связанного списка, чтобы переменные внешний вид окна до цепочки областей видимости