Проблема Funarg - Funarg problem

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

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

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

Задача вверх funarg

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

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

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

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

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

Пример

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

составить f g = λx → f (g x)

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

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

Задача с направлением вниз

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

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

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

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

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

Смотрите также

внешняя ссылка

[1] Функция FUNCTION в LISP или почему проблему FUNARG следует называть проблемой среды, Джоэл Мозес, в: Бюллетень ACM SIGSAM 17 (июль 1970 г.), стр. 13-27.

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

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

[1]

[2]

[3]