Проблема Funarg: реализация функций первого класса и управление стеком
Funarg problem
Проблема funarg в программировании: трудности реализации функций как объектов первого класса при использовании стековой памяти. Решения: замыкания, запрет ссылок.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В информатике проблема funarg (проблема аргумента функции) относится к сложности реализации функций первого класса (функций как объектов первого класса) в реализациях языков программирования с использованием стековой аллокации памяти для функций. Эта сложность возникает только в том случае, если тело вложенной функции ссылается непосредственно (то есть, не через передачу аргументов) на идентификаторы, определенные в области видимости, где функция определена, но не в области видимости вызова функции. Стандартным решением является либо запрет таких ссылок, либо создание замыканий. Существует два немного различающихся варианта проблемы funarg. Проблема funarg, направленная вверх, возникает при возврате (или иной передаче "вверх") функции из вызова функции. Проблема funarg, направленная вниз, возникает при передаче функции в качестве параметра другому вызову функции.
In computer science, the funarg problem (function argument problem) refers to the difficulty in implementing first class functions (functions as first class objects) in programming language implementations so as to use stack based memory allocation of the functions. The difficulty only arises if the body of a nested function refers directly (i. e., not by argument passing) to identifiers defined in the environment in which the function is defined, but not in the environment of the function call. A standard resolution is either to forbid such references or to create closures. There are two subtly different versions of the funarg problem. The upwards funarg problem arises from returning (or otherwise transmitting "upwards") a function from a function call. The downwards funarg problem arises from passing a function as a parameter to another function call.
Вверх по лестнице
Когда одна функция вызывает другую во время выполнения типичной программы, локальное состояние вызывающей функции (включая параметры и локальные переменные) должно быть сохранено, чтобы выполнение продолжилось после возврата вызванной функции. В большинстве компилируемых программ это локальное состояние хранится в стеке вызовов в структуре данных, называемой стековой рамкой или записью активации. Эта стековая рамка помещается в стек (выделяется) перед вызовом другой функции и извлекается из стека (деаллоцируется), когда вызванная функция возвращается в функцию, которая её вызвала. Проблема «funarg вверх» возникает, когда вызывающая функция обращается к состоянию вызванной функции после её возврата. Следовательно, стековая рамка, содержащая переменные состояния вызванной функции, не должна быть деаллоцирована при возврате функции, что нарушает парадигму вызова функций на основе стека. Одно из решений проблемы «funarg вверх» заключается в том, чтобы выделять все записи активации из кучи, а не из стека, и полагаться на сборку мусора или подсчёт ссылок для их деаллокации, когда они больше не нужны. Исторически управление записями активации в куче считалось менее эффективным, чем в стеке (хотя это частично опровергается), и предполагало значительную сложность реализации. Большинство функций в типичных программах (в меньшей степени в программах на функциональных языках программирования) не создают «funarg вверх», что усиливает опасения по поводу потенциальных накладных расходов, связанных с их реализацией. Кроме того, этот подход затруднителен в языках, которые не поддерживают сборку мусора. Некоторые компиляторы, ориентированные на эффективность, используют гибридный подход, при котором записи активации для функции выделяются из стека, если компилятор может определить с помощью статического анализа программы, что функция не создаёт «funarg вверх». В противном случае записи активации выделяются из кучи. Другое решение — просто скопировать значения переменных в замыкание в момент его создания. Это приведёт к другому поведению в случае изменяемых переменных, поскольку состояние больше не будет общим для замыканий. Но если известно, что переменные являются константами, то этот подход будет эквивалентным. Языки ML используют этот подход, поскольку переменные в этих языках связаны со значениями, то есть переменные нельзя изменить. Java также использует этот подход в отношении анонимных классов (и лямбда-выражений с Java 8), поскольку он позволяет ссылаться только на переменные в окружающей области видимости, которые являются фактически финальными (то есть константами). Некоторые языки позволяют программисту явно выбирать между двумя вариантами поведения. Анонимные функции PHP 5.3 требуют указания переменных, которые следует включить в замыкание, с помощью ключевого слова `use`; если переменная указана по ссылке, то включается ссылка на исходную переменную; в противном случае передаётся значение. В анонимных функциях Apple Blocks захваченные локальные переменные по умолчанию захватываются по значению; если требуется общий доступ к состоянию между замыканиями или между замыканием и внешней областью видимости, переменная должна быть объявлена с модификатором `block`, в этом случае эта переменная выделяется в куче.
When one function calls another during a typical program's execution, the local state of the caller (including parameters and local variables) must be preserved in order for execution to proceed after the callee returns. In most compiled programs, this local state is stored on the call stack in a data structure called a stack frame or activation record. This stack frame is pushed, or allocated, as prelude to calling another function, and is popped, or deallocated, when the other function returns to the function that did the call. The upwards funarg problem arises when the calling function refers to the called/exited function's state after that function has returned. Therefore, the stack frame containing the called function's state variables must not be deallocated when the function returns, violating the stack based function call paradigm. One solution to the upwards funarg problem is to simply allocate all activation records from the heap instead of the stack and rely on some form of garbage collection or reference counting to deallocate them when they are no longer needed. Managing activation records on the heap has historically been perceived to be less efficient than on the stack (although this is partially contradicted) and has been perceived to impose significant implementation complexity. Most functions in typical programs (less so for programs in functional programming languages) do not create upwards funargs, adding to concerns about potential overhead associated with their implementation. Furthermore, this approach is genuinely difficult in languages that do not support garbage collection. Some efficiency minded compilers employ a hybrid approach in which the activation records for a function are allocated from the stack if the compiler is able to deduce, through static program analysis, that the function creates no upwards funargs. Otherwise, the activation records are allocated from the heap. Another solution is to simply copy the value of the variables into the closure at the time the closure is created. This will cause a different behavior in the case of mutable variables, because the state will no longer be shared between closures. But if it is known that the variables are constant, then this approach will be equivalent. The ML languages take this approach, since variables in those languages are bound to values—i. e. variables cannot be changed. Java also takes this approach with respect to anonymous classes (and lambdas since Java 8), in that it only allows one to refer to variables in the enclosing scope that are effectively final (i. e. constant). Some languages allow the programmer to explicitly choose between the two behaviors. PHP 5.3's anonymous functions require one to specify which variables to include in the closure using the use clause; if the variable is listed by reference, it includes a reference to the original variable; otherwise, it passes the value. In Apple's Blocks anonymous functions, captured local variables are by default captured by value; if one wants to share the state between closures or between the closure and the outside scope, the variable must be declared with the block modifier, in which case that variable is allocated on the heap.
Проблема с посадкой вниз
Нисходящий funarg может также относиться к состоянию функции, когда она фактически не выполняется. Однако, поскольку по определению существование нисходящего funarg подразумевается выполнением функции, которая его создает, стек-фрейм для этой функции обычно все еще может храниться в стеке. Тем не менее, наличие нисходящих funarg подразумевает древовидную структуру замыканий и стековых фреймов, что может затруднить понимание состояния программы как для человека, так и для машины. Проблема нисходящих funarg усложняет эффективную компиляцию хвостовых вызовов и кода, написанного в стиле передачи продолжений. В этих особых случаях программист (как правило) предполагает, что функция должна выполняться с ограниченным использованием стека, поэтому более "быстрое" поведение может оказаться нежелательным.
A downwards funarg may also refer to a function's state when that function is not actually executing. However, because, by definition, the existence of a downwards funarg is contained in the execution of the function that creates it, the stack frame for the function can usually still be stored on the stack. Nonetheless, the existence of downwards funargs implies a tree structure of closures and stack frames that can complicate human and machine reasoning about the program state. The downwards funarg problem complicates the efficient compilation of tail calls and code written in continuation passing style. In these special cases, the intent of the programmer is (usually) that the function run in limited stack space, so the "faster" behavior may actually be undesirable.
Практические последствия
Исторически проблема обратного funarg оказалась более сложной. Например, язык программирования Pascal позволяет передавать функции в качестве аргументов, но не возвращать их в качестве результатов; таким образом, реализации Pascal требуется решать проблему funarg вниз, но не вверх. Языки программирования Modula 2 и Oberon (потомки Pascal) позволяют использовать функции как в качестве параметров, так и в качестве возвращаемых значений, но присваиваемая функция не может быть вложенной. Язык программирования C исторически избегает основной сложности проблемы funarg, не допуская вложенных определений функций; поскольку окружение каждой функции одинаково и содержит только статические глобальные переменные и функции, указатель на код функции полностью определяет функцию. Компания Apple предложила и реализовала синтаксис замыканий для C, который решает проблему обратного funarg, динамически перемещая замыкания из стека в кучу по мере необходимости. Язык программирования Java решает эту проблему, требуя, чтобы контекст, используемый вложенными функциями в анонимных внутренних и локальных классах, был объявлен final, а контекст, используемый лямбда-выражениями, был эффективно final. В C# и D есть лямбды (замыкания), которые инкапсулируют указатель функции и связанные переменные. В функциональных языках функции являются значениями первого класса и могут передаваться где угодно. Таким образом, реализации Scheme или Standard ML должны решать как проблему обратного, так и проблему прямого funarg. Обычно это достигается путем представления значений функций как замыканий, выделенных в куче, как описано ранее. Компилятор OCaml использует гибридный метод (основанный на статическом анализе программы) для максимизации эффективности.
Historically, the upwards funarg problem has proven to be more difficult. For example, the Pascal programming language allows functions to be passed as arguments but not returned as results; thus implementations of Pascal are required to address the downwards funarg problem but not the upwards one. The Modula 2 and Oberon programming languages (descendants of Pascal) allow functions both as parameters and return values, but the assigned function may not be a nested function. The C programming language historically avoids the main difficulty of the funarg problem by not allowing function definitions to be nested; because the environment of every function is the same, containing just the statically allocated global variables and functions, a pointer to a function's code describes the function completely. Apple has proposed and implemented a closure syntax for C that solves the upwards funarg problem by dynamically moving closures from the stack to the heap as necessary. The Java programming language deals with it by requiring that context used by nested functions in anonymous inner and local classes be declared final, and context used by lambda expressions be effectively final. C# and D have lambdas (closures) that encapsulate a function pointer and related variables. In functional languages, functions are first class values that can be passed anywhere. Thus, implementations of Scheme or Standard ML must address both the upwards and downwards funarg problems. This is usually accomplished by representing function values as heap allocated closures, as previously described. The OCaml compiler employs a hybrid technique (based on static program analysis) to maximize efficiency.