Проблема Фунарга

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

Трудность возникает только в том случае, если тело вложенной функции напрямую (т. е. не путем передачи аргументов) ссылается на идентификаторы, определенные в среде, в которой определена функция, но не в среде вызова функции. ^[1] Стандартное решение — либо запретить такие ссылки, либо создать замыкания . ^[2]

Существуют две слегка отличающиеся версии проблемы funarg. Проблема восходящего аргумента возникает при возврате (или иной передаче «вверх») функции из вызова функции. Проблема с нисходящим аргументом возникает при передаче функции в качестве параметра при вызове другой функции.

Проблема восходящего фунарга

Когда одна функция вызывает другую во время типичного выполнения программы, локальное состояние вызывающей стороны (включая параметры и локальные переменные ) должно быть сохранено, чтобы выполнение могло продолжиться после возврата вызываемого объекта. В большинстве скомпилированных программ это локальное состояние хранится в стеке вызовов в структуре данных, называемой кадром стека или записью активации . Этот кадр стека помещается или выделяется в качестве прелюдии к вызову другой функции и извлекается или освобождается, когда другая функция возвращается к функции, выполнившей вызов. Проблема восходящего аргумента возникает, когда вызывающая функция ссылается на состояние вызванной/завершенной функции после того, как эта функция вернулась. Следовательно, кадр стека, содержащий переменные состояния вызываемой функции, не должен освобождаться при возвращении функции, что нарушает парадигму вызова функции на основе стека .

Одним из решений проблемы восходящего Funarg является простое выделение всех записей активации из кучи , а не из стека, и использование той или иной формы сборки мусора или подсчета ссылок для их освобождения, когда они больше не нужны. Управление записями активации в куче исторически считалось менее эффективным, чем в стеке (хотя это частично противоречит ^[3]) и было воспринято как существенно усложняющее реализацию. Большинство функций в типичных программах (в меньшей степени это относится к программам на языках функционального программирования ) не создают восходящих аргументов, что усиливает опасения по поводу потенциальных накладных расходов, связанных с их реализацией. Более того, этот подход действительно сложен для языков, которые не поддерживают сборку мусора.

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

Другое решение — просто скопировать значения переменных в замыкание во время его создания. Это приведет к другому поведению в случае изменяемых переменных, поскольку состояние больше не будет разделяться между замыканиями. Но если известно, что переменные постоянны, то этот подход будет эквивалентным. Языки машинного обучения используют этот подход, поскольку переменные в этих языках привязаны к значениям, то есть переменные не могут быть изменены. Java также использует этот подход по отношению к анонимным классам (и лямбда-выражениям, начиная с Java 8), поскольку он позволяет ссылаться только на те переменные во внешней области, которые эффективно final (т.е. постоянный).

Некоторые языки позволяют программисту явно выбирать между двумя вариантами поведения. Анонимные функции PHP 5.3 требуют указать, какие переменные включать в замыкание, используя use () пункт; если переменная указана по ссылке, она включает ссылку на исходную переменную; в противном случае оно передает значение. В анонимных функциях Apple Blocks захватываемые локальные переменные по умолчанию захватываются по значению; если кто-то хочет разделить состояние между замыканиями или между замыканием и внешней областью видимости, переменная должна быть объявлена с помощью __block модификатор, и в этом случае эта переменная выделяется в куче.

Пример

Следующий Haskell в стиле псевдокод определяет композицию функций :

compose f g = λx → f (g x)

λ — оператор построения новой функции, которая в данном случае имеет один аргумент, xи возвращает результат первого применения g к x, затем применяя f к этому. Эта λ-функция несет в себе функции f и g (или указатели на них) как внутреннее состояние.

Проблема в этом случае существует, если функция компоновки выделяет переменные параметров f и g в стеке. Когда compose возвращается, кадр стека, содержащий f и g отбрасывается. Когда внутренняя функция λx попытки получить доступ g, он получит доступ к удаленной области памяти.

Проблема нисходящего фунарга

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

Проблема нисходящего Funarg усложняет эффективную компиляцию хвостовых вызовов и кода, написанного в стиле передачи продолжения . В этих особых случаях намерение программиста (обычно) состоит в том, чтобы функция выполнялась в ограниченном пространстве стека, поэтому «более быстрое» поведение на самом деле может быть нежелательным. ^{[ нужны разъяснения ]}

Практические последствия

Исторически сложилось так, что проблема восходящего фунарга оказалась более сложной. Например, язык программирования Паскаль позволяет передавать функции в качестве аргументов, но не возвращать их в качестве результатов; таким образом, реализации Паскаля необходимы для решения проблемы нисходящего движения, но не восходящего. Языки программирования Modula -2 и Oberon (потомки Pascal) допускают функции как в качестве параметров, так и в качестве возвращаемых значений, но назначенная функция не может быть вложенной функцией. Язык программирования C исторически позволяет избежать основной трудности проблемы funarg, не допуская вложенности определений функций; поскольку среда каждой функции одинакова и содержит только статически выделенные глобальные переменные и функции, указатель на код функции полностью описывает функцию. Apple предложила и реализовала синтаксис замыканий для C , который решает проблему восходящего массива путем динамического перемещения замыканий из стека в кучу по мере необходимости. ^{[ нужна ссылка ]} Язык программирования Java решает эту проблему, требуя, чтобы контекст, используемый вложенными функциями в анонимных внутренних и локальных классах, был объявлен. final, а контекст, используемый лямбда-выражениями, будет фактически окончательным. В C# и D есть лямбды (замыкания), которые инкапсулируют указатель на функцию и связанные переменные.

В функциональных языках функции — это значения первого класса, которые можно передавать куда угодно. Таким образом, реализации Scheme или Standard ML должны решать проблемы как восходящего, так и нисходящего движения. Обычно это достигается путем представления значений функции в виде замыканий, выделенных в куче , как описано ранее. Компилятор OCaml использует гибридный метод (основанный на статическом анализе программы ) для максимизации эффективности. ^{[ нужна ссылка ]}

См. также

Ссылки

^ Функция FUNCTION в LISP, или почему проблему FUNARG следует называть проблемой окружающей среды , Джоэл Мозес, памятка MAC проекта MIT AI-199, MAC-M-428, июнь 1970 г. (15 стр.).
^ Предлагаемое решение проблемы FUNARG , предложенное Эриком Сандеволлом, в: ACM SIGSAM Bulletin 17 (январь 1971 г.), стр. 29–42.
^ Эндрю В. Аппель , Чжун Шао. Эмпирическое и аналитическое исследование стоимости стека и кучи для языков с замыканиями. Технический отчет Princeton CS TR-450-94 , 1994 г.

Внешние ссылки

[1] Функция FUNCTION в LISP, или почему проблему FUNARG следует называть проблемой окружающей среды , Джоэл Мозес, памятка MAC проекта MIT AI-199, MAC-M-428, июнь 1970 г. (15 стр.).

[2] Предлагаемое решение проблемы FUNARG , предложенное Эриком Сандеволлом, в: ACM SIGSAM Bulletin 17 (январь 1971 г.), стр. 29–42.

[3] Эндрю В. Аппель , Чжун Шао. Эмпирическое и аналитическое исследование стоимости стека и кучи для языков с замыканиями. Технический отчет Princeton CS TR-450-94 , 1994 г.

[1]

[2]

[3]