В информатике проблема фунаргов ( проблема аргумента функции) относится к трудности реализации функций первого класса ( функций как объектов первого класса ) в реализациях языков программирования, чтобы использовать стековое распределение памяти для функций.
Трудность возникает только в том случае, если тело вложенной функции ссылается напрямую (т. е. не путем передачи аргументов) на идентификаторы, определенные в среде, в которой определена функция, но не в среде вызова функции. [1] Стандартное решение — либо запретить такие ссылки, либо создать замыкания . [2]
Существуют две тонко различающиеся версии проблемы фунаргов. Проблема фунаргов вверх возникает при возврате (или иной передаче «вверх») функции из вызова функции. Проблема фунаргов вниз возникает при передаче функции в качестве параметра другому вызову функции.
Когда одна функция вызывает другую во время выполнения типичной программы, локальное состояние вызывающей стороны (включая параметры и локальные переменные ) должно быть сохранено для продолжения выполнения после возврата вызываемой стороны. В большинстве скомпилированных программ это локальное состояние хранится в стеке вызовов в структуре данных, называемой стековым кадром или записью активации . Этот стековый кадр помещается в стек или выделяется в качестве прелюдии к вызову другой функции и извлекается или освобождается, когда другая функция возвращается к функции, выполнившей вызов. Проблема восходящих фунаргов возникает, когда вызывающая функция ссылается на состояние вызванной/выведенной функции после возврата этой функции. Следовательно, стековый кадр, содержащий переменные состояния вызываемой функции, не должен освобождаться при возврате функции, что нарушает парадигму вызова функций на основе стека .
Одним из решений проблемы upstream funarg является простое выделение всех записей активации из кучи вместо стека и использование некоторой формы сборки мусора или подсчета ссылок для их освобождения, когда они больше не нужны. Управление записями активации в куче исторически считалось менее эффективным, чем в стеке (хотя это частично противоречит [3] ), и считалось, что оно значительно усложняет реализацию. Большинство функций в типичных программах (в меньшей степени для программ на функциональных языках программирования ) не создают upstream funargs, что усиливает опасения относительно потенциальных накладных расходов, связанных с их реализацией. Более того, этот подход действительно сложен в языках, которые не поддерживают сборку мусора.
Некоторые ориентированные на эффективность компиляторы используют гибридный подход, в котором записи активации для функции выделяются из стека, если компилятор может сделать вывод посредством статического анализа программы , что функция не создает восходящих фунаргов. В противном случае записи активации выделяются из кучи.
Другое решение — просто скопировать значение переменных в замыкание во время создания замыкания. Это вызовет другое поведение в случае изменяемых переменных, поскольку состояние больше не будет разделяться между замыканиями. Но если известно, что переменные являются константами, то этот подход будет эквивалентен. Языки ML используют этот подход, поскольку переменные в этих языках привязаны к значениям, т. е. переменные не могут быть изменены. Java также использует этот подход в отношении анонимных классов (и лямбда-выражений, начиная с Java 8), поскольку он позволяет ссылаться только на переменные в охватывающей области видимости, которые являются фактически final(т. е. константами).
Некоторые языки позволяют программисту явно выбирать между двумя вариантами поведения. Анонимные функции PHP 5.3 требуют указать, какие переменные следует включить в замыкание с помощью use ()предложения; если переменная указана по ссылке, она включает ссылку на исходную переменную; в противном случае она передает значение. В анонимных функциях Apple Blocks захваченные локальные переменные по умолчанию захватываются по значению; если требуется разделить состояние между замыканиями или между замыканием и внешней областью видимости, переменная должна быть объявлена с __blockмодификатором, и в этом случае эта переменная выделяется в куче.
Следующий псевдокод , подобный Haskell, определяет композицию функций :
составим f g = λx → f ( g x ) λ— оператор для построения новой функции, которая в этом случае имеет один аргумент, x, и возвращает результат первого применения gк x, а затем применения fк тому. Эта λ-функция переносит функции fи g(или указатели на них) как внутреннее состояние.
Проблема в этом случае возникает, если функция compose выделяет переменные параметров fи gв стеке. При composeвозврате кадр стека, содержащий fи, gотбрасывается. Когда внутренняя функция λxпытается получить доступ к g, она получит доступ к отброшенной области памяти.
Downwards funarg может также ссылаться на состояние функции, когда эта функция фактически не выполняется. Однако, поскольку, по определению, существование downwards funarg содержится в выполнении функции, которая его создает, стековый фрейм для функции обычно все еще может храниться в стеке. Тем не менее, существование downwards funargs подразумевает древовидную структуру замыканий и стековых фреймов, которые могут усложнить человеческие и машинные рассуждения о состоянии программы.
Проблема нисходящего фунарга усложняет эффективную компиляцию хвостовых вызовов и кода, написанного в стиле продолжения-передачи . В этих особых случаях намерение программиста (обычно) заключается в том, чтобы функция выполнялась в ограниченном пространстве стека, поэтому «более быстрое» поведение может быть на самом деле нежелательным. [ необходимо разъяснение ]
Исторически проблема восходящих фунаргов оказалась более сложной. Например, язык программирования Pascal позволяет передавать функции как аргументы, но не возвращать их как результаты; таким образом, реализации Pascal должны решать проблему нисходящих фунаргов, но не нисходящую. Языки программирования Modula-2 и Oberon (потомки Pascal) допускают функции как в качестве параметров, так и возвращаемых значений, но назначенная функция не может быть вложенной функцией. Язык программирования C исторически избегает основной трудности проблемы фунаргов, не допуская вложенности определений функций; поскольку окружение каждой функции одинаково и содержит только статически выделенные глобальные переменные и функции, указатель на код функции полностью описывает функцию. Apple предложила и реализовала синтаксис замыканий для C , который решает проблему восходящих фунаргов путем динамического перемещения замыканий из стека в кучу по мере необходимости. [ необходима цитата ] Язык программирования Java решает эту проблему, требуя, чтобы контекст, используемый вложенными функциями в анонимных внутренних и локальных классах, был объявлен final, а контекст, используемый лямбда-выражениями , был фактически final. В C# и D есть лямбда-выражения (замыкания), которые инкапсулируют указатель на функцию и связанные переменные.
В функциональных языках функции являются первоклассными значениями, которые могут передаваться куда угодно. Таким образом, реализации Scheme или Standard ML должны решать как проблемы с фунаргами вверх, так и проблемы с фунаргами вниз. Обычно это достигается путем представления значений функций в виде замыканий, выделенных в куче , как описано ранее. Компилятор OCaml использует гибридную технику (основанную на статическом анализе программ ) для максимизации эффективности. [ необходима цитата ]