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

Фунарг — сокращение от «функциональный аргумент»; в компьютерных науках, проблема фунарга относится к сложности реализации функций как первоклассных объектов в стеково-ориентированных языках программирования (в широком смысле, включая все языки, в которых передача параметров функциям осуществляется через стек).

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

Различают два варианта проблемы: проблема восходящего фунарга возникает при возврате функции из некоторой функции, проблема нисходящего фунарга — при передаче функции в качестве параметра некоторой функции.

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

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

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

Если объём памяти, занимаемой кадрами объемлющих функций невелик, а данные в этих кадрах не меняются, то кадры объемлющих функций можно передавать, как значения. Эта возможность предопределена для части языков (большинство функциональных языков и Java применительно к методам внутренних анонимных классов). Но и для языков, которые позволяют менять данные объемлющих функций (например, C#), некоторые эффективные компиляторы реализуют гибридный подход, в котором кадр стека функции размещается на стеке вызовов, в случае если компилятору удаётся путём анализа программы вывести, что функция не создаёт восходящих фунаргов, а в ином случае в куче. Размещение кадра стека в куче в общем случае снижает производительность.

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

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

Проблема возникает в программах на языках, позволяющих передавать функции в качестве параметров, например, Pascal и Algol 68.

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