В информатике , то проблема funarg (аргумент функции проблемы) относится к трудности в реализации первых функций-класса ( функции как объекты первого класса ) в программировании реализаций языка так, чтобы использование стека на основе выделения памяти функций.
Сложность возникает только в том случае, если тело вложенной функции ссылается непосредственно (то есть не путем передачи аргументов) на идентификаторы, определенные в среде, в которой определена функция, но не в среде вызова функции. [1] Стандартное решение - либо запретить такие ссылки, либо создать закрытие . [2]
Есть две тонко разные версии проблемы funarg. Проблема восходящего потока возникает из-за возврата (или иной передачи «вверх») функции из вызова функции. Проблема нисходящего потока возникает из-за передачи функции в качестве параметра другому вызову функции.
Задача вверх funarg
Когда одна функция вызывает другую во время типичного выполнения программы, локальное состояние вызывающей стороны (включая параметры и локальные переменные ) должно быть сохранено, чтобы выполнение продолжилось после возврата вызываемого объекта. В большинстве скомпилированных программ это локальное состояние хранится в стеке вызовов в структуре данных, называемой кадром стека или записью активации . Этот кадр стека помещается или выделяется, как прелюдия к вызову другой функции, и выталкивается или освобождается, когда другая функция возвращается к функции, которая выполнила вызов. Проблема восходящего потока возникает, когда вызывающая функция обращается к состоянию вызванной / завершенной функции после того, как эта функция вернулась. Следовательно, кадр стека, содержащий переменные состояния вызываемой функции, не должен освобождаться при возврате функции, что нарушает парадигму вызова функций на основе стека .
Одно из решений проблемы восходящего funarg - просто выделить все записи активации из кучи, а не из стека, и полагаться на некоторую форму сборки мусора или подсчета ссылок, чтобы освободить их, когда они больше не нужны. Управление записями активации в куче исторически считалось менее эффективным, чем в стеке (хотя это частично противоречит [3] ), и считалось, что оно значительно усложняет реализацию. Большинство функций в типичных программах (в меньшей степени для программ на функциональных языках программирования ) не создают восходящие аргументы, что усиливает опасения по поводу потенциальных накладных расходов, связанных с их реализацией. Более того, этот подход действительно затруднен для языков, не поддерживающих сборку мусора.
Некоторые компиляторы, ориентированные на эффективность, используют гибридный подход, в котором записи активации для функции выделяются из стека, если компилятор может вывести посредством статического анализа программы , что функция не создает восходящих аргументов. В противном случае записи активации выделяются из кучи.
Другое решение - просто скопировать значение переменных в замыкание в момент создания замыкания. Это вызовет другое поведение в случае изменяемых переменных, потому что состояние больше не будет разделяться между замыканиями. Но если известно, что переменные постоянны, то такой подход будет эквивалентен. В языках ML используется этот подход, поскольку переменные в этих языках привязаны к значениям, т.е. переменные не могут быть изменены. Java также использует этот подход в отношении анонимных классов, поскольку он позволяет ссылаться только на переменные в охватывающей области видимости, которые являются final
(т. Е. Постоянными).
Некоторые языки позволяют программисту явно выбирать между двумя вариантами поведения. Анонимные функции PHP 5.3 требуют указать, какие переменные включать в закрытие, используя use ()
предложение; если переменная указана по ссылке, она включает ссылку на исходную переменную; в противном случае он передает значение. В анонимных функциях Apple Blocks захваченные локальные переменные по умолчанию захватываются по значению; если кто-то хочет разделить состояние между замыканиями или между замыканием и внешней областью, переменная должна быть объявлена с __block
модификатором, и в этом случае эта переменная выделяется в куче.
Пример
Следующий псевдокод, вдохновленный Haskell, определяет композицию функций :
составить fg = λx → f (gx)
λ
- это оператор для создания новой функции, которая в данном случае имеет один аргумент x
, и возвращает результат сначала применения g
к x
, а затем применения f
к нему. Эта функция λ переносит функции f
и g
(или указатели на них) как внутреннее состояние.
Проблема в этом случае существует, если функция компоновки выделяет переменные параметров f
и g
в стеке. При compose
возврате кадр стека, содержащий f
и g
, отбрасывается. Когда внутренняя функция λx
пытается получить доступ g
, она обращается к заброшенной области памяти.
Задача с направлением вниз
Аргумент вниз может также относиться к состоянию функции, когда эта функция на самом деле не выполняется. Однако, поскольку, по определению, существование нисходящего funarg содержится в выполнении функции, которая его создает, кадр стека для функции обычно все еще может быть сохранен в стеке. Тем не менее, существование нисходящих целевых аргументов подразумевает древовидную структуру замыканий и фреймов стека, которая может усложнить рассуждения человека и машины о состоянии программы.
Проблема нисходящего потока усложняет эффективную компиляцию хвостовой рекурсии и кода, написанного в стиле передачи продолжения . В этих особых случаях намерение программиста (обычно) состоит в том, чтобы функция выполнялась в ограниченном пространстве стека, поэтому «более быстрое» поведение может быть нежелательным.
Практические последствия
Исторически сложилось так, что проблема восходящего фунарга оказалась более сложной. Например, язык программирования Паскаль позволяет передавать функции как аргументы, но не возвращать их как результаты; таким образом, реализации Паскаля требуются для решения проблемы направленности вниз, но не вверх. В Modula-2 и Оберон языки программирования (потомки Паскаля) позволяют функцию как в качестве параметров и возвращаемых значений, но назначенная функция не может быть вложенной функцией. Язык программирования C исторически избегает основную трудность задачи funarg, не допуская определения функций , чтобы быть вложенными; поскольку среда каждой функции одинакова, содержит только статически распределенные глобальные переменные и функции, указатель на код функции полностью описывает функцию. Apple предложила и реализовала синтаксис замыкания для C, который решает проблему восходящего потока, динамически перемещая замыкания из стека в кучу по мере необходимости. [ необходимая цитата ] Язык программирования Java имеет дело с этим, требуя, чтобы контекст, используемый вложенными функциями в анонимных внутренних и локальных классах, был объявлен окончательным , а контекст, используемый лямбда-выражениями, был фактически окончательным. В C # и D есть лямбды (замыкания), которые инкапсулируют указатель на функцию и связанные переменные.
В функциональных языках функции являются первоклассными значениями и могут передаваться где угодно. Таким образом, реализации Scheme или SML должны решать как восходящие, так и нисходящие проблемы funarg. Обычно это достигается путем представления значений функции в виде замыканий, выделенных в куче , как описано ранее. OCaml компилятор использует гибридный метод (на основе анализа программ ) , чтобы максимизировать эффективность. [ необходима цитата ]
Смотрите также
- Закрытие (информатика)
- Функциональное программирование
- Лямбда-исчисление
- Тест на мужчину или мальчика
- Привязка имени
- Ссылочная прозрачность
- Область применения (программирование)
- Стек спагетти
Рекомендации
- ^ Функция FUNCTION в LISP или почему проблема FUNARG должна называться проблемой окружающей среды , Джоэл Мозес, MIT Project MAC memo AI-199, MAC-M-428, июнь 1970 г. (15 стр.).
- ^ Предлагаемое решение проблемы FUNARG , по Эрик Сандуолл в: ACM SIGSAM Bulletin 17 (январь 1971), стр 29-42..
- ^ Эндрю В. Аппель , Чжун Шао. Эмпирическое и аналитическое исследование стоимости стека и кучи для языков с замыканиями. Технический отчет Princeton CS TR-450-94 , 1994.
Внешние ссылки
- Йозеф Вайценбаум . «Объяснение проблемы FUNARG» , 1968.
- Иоиль Моисей . «Функция FUNCTION в LISP, или почему проблема FUNARG должна называться проблемой среды» . MIT AI Memo 199, 1970.
- Привязки, процедуры, функции, функциональное программирование и лямбда-исчисление