Вложенная функция
В программировании, вложенная функция (или вложенная процедура или подпрограмма) — функция, которая определена внутри другой внешней функции. Благодаря простым рекурсивным правилам области видимости, вложенная функция не видима снаружи своей непосредственной внешней функции, но может видеть (иметь доступ) ко всем локальным объектам (данным, функциям, типам, и т.д.) своей прямой внешней функции, а также ко всем функциям, которые в свою очередь, находятся внутри этой внешней функции. Вкладывание функций (nesting) теоретически возможно на неограниченную глубину, хотя только несколько уровней обычно используется в повседневных программах.
Вложенные функции используются во множестве подходов к структурному программированию, включая ранние языки, такие как ALGOL, Simula и Pascal, а также во множестве современных динамических и функциональных языков программирования. Несмотря на это, они обычно не поддерживаются в (изначально простых) языках семейства С.
Эффекты[править | править код]
Вложенные функции предполагают наличие области видимости функции или блочной видимости. Областью видимости вложенной функции является содержимое внешней функции, или точнее содержимое одного из составляющих блоков этой функции, что означает, что она не видна снаружи этого блока, а также снаружи внешней функции. Вложенная функция может иметь доступ к другим локальным функциям, переменным, константам, типам, классам, и т.д., которые находятся в той же области видимости, или в любой внешней области видимости, без явной передачи параметров, что сильно упрощает передачу данных в и из вложенной функции. В обычных случаях, как для чтения, так и для записи.
В определенных ситуациях (и языках) вложенные функции могут вести к созданию замыкания. Если существует возможность для вложенной функции выйти из внешней функции, например если вложенная функция является объектом первого класса и она передается другой функции или возвращается из внешней функции, то в таких случаях создается замыкание и вызовы этой функции могут получить доступ к среде изначальной функции. Фрейм непосредственной внешней функции должен оставаться живым до тех пор, пока не умрет последнее ссылающееся замыкание и нелокальные автоматические переменные, ссылки на которые имеются в замыкании не могут таким образом выделить стек. Эта ситуация известна как проблема фунарга и является ключевой причиной того, почему вложенные функции не были реализованы в некоторых более простых языках, так как это значимо усложняет генерацию кода и его анализ, особенно в случаях, когда функции вложены в различные уровни, разделяя различные части своих окружений.
Примеры[править | править код]
Пример, с использованием синтаксиса языка Pascal (Алгол, Модула-2, Оберон, Ада и прочих похожих):
function E(x: real): real;
function F(y: real): real;
begin
F := x + y
end;
begin
E := F(3) + F(4)
end;
Функция F вложена в функцию E. Заметим, что параметр x функции E видим также в функции F (так как функция F является частью функции E), в то время как оба параметра x и y невидимы снаружи функции E и функции F соответственно.
Похожий пример в Standard ML:
fun e (x : real) =
let
fun f y = x+y
in
f 3 + f 4
end;
Один из способов реализации этого примера с использованием синтаксиса языка программирования Haskell:
e :: Float -> Float
e x = f 3 + f 4 where f y = x + y
Этот же пример с использованием синтаксиса GNU C[1] (C расширенный с использованием вложенных функций):
float E(float x)
{
float F(float y)
{
return x + y;
}
return F(3) + F(4);
}
Быстрая сортировка[править | править код]
Более практический пример — это реализация быстрой сортировки:[2]
void sort(int *items, int size) {
void quickSort(int first, int last) {
void swap(int p, int q) {
int tmp = items[p];
items[p] = items[q];
items[q] = tmp;
}
int partition() {
int pivot = items[first], index = first;
swap(index, last);
for (int i = first; i < last; i++)
if (items[i] < pivot)
swap(index++, i);
swap(index, last);
return index;
}
if (first < last) {
int pivotIndex = partition();
quickSort(first, pivotIndex - 1);
quickSort(pivotIndex + 1, last);
}
}
quickSort(0, size - 1);
}
Другой пример, это следующая реализация Быстрой сортировки Хоара с использованием синтаксиса лямбда выражений на C++11:
template<typename RandomAccessIterator>
auto Sort(RandomAccessIterator Begin, RandomAccessIterator End)->void {
auto Partition = [&]() {
//Hoare partition scheme
auto &Pivot = *Begin;
auto ForwardCursor = Begin;
auto BackwardCursor = End - 1;
auto PartitionPositionFound = false;
auto LocatePartitionPosition = [&]() {
while (*ForwardCursor < Pivot)
++ForwardCursor;
while (Pivot < *BackwardCursor)
--BackwardCursor;
if (ForwardCursor >= BackwardCursor)
PartitionPositionFound = true;
else
Swap(*ForwardCursor, *BackwardCursor);
};
//Trivial helper function
auto MoveOnAndTryAgain = [&]() {
++ForwardCursor;
--BackwardCursor;
};
//Brief outline of the actual partition process
while (true) {
LocatePartitionPosition();
if (PartitionPositionFound)
return BackwardCursor + 1;
else
MoveOnAndTryAgain();
}
};
//Brief outline of the quicksort algorithm
if (Begin < End - 1) {
auto PartitionPosition = Partition();
Sort(Begin, PartitionPosition);
Sort(PartitionPosition, End);
}
}
Назначение[править | править код]
Лексически определения вложенных функций являются формой сокрытия и полезны для разделения процедурных задач на подзадачи, когда они имеют только локальное значение. Это помогает избежать засорения других частей программы функциями и переменными, которые не имеют отношения к этим частям.
Обычно вложенные функции используются как вспомогательные функции или как рекурсивные функции внутри других функций (как в примере быстрой сортировки выше). Это полезно для структурной организации кода, избегания загрязнения области видимости, а также позволяет функциям легко делиться своим состоянием.[3] Так как вложенная функция имеет доступ к локальным переменным внешней функции, совместное использование состояния возможное без передачи параметров во вложенную функцию или использования глобальных переменных упрощает код.
В языках со вложенными функциями, функции могут в общих случаях также содержать локальные константы, и типы данных (в дополнение к локальным переменным, параметрам и функциям), инкапсуплированным и спрятанным в той же манере с любым уровнем вложенности. Это позволяет еще более обогатить структурированные возможности организации кода.
Другие виды использования[править | править код]
Порядок выполнения[править | править код]
Вложенные функции могут быть также использованы для неструктурированного порядка выполнения, с использованием оператора возврата для общего неструктурированного порядка выполнения. Это может быть использовано для более детального контроля, чем это возможно с другими встроенными свойствами языка - например, это может помочь раннему завершению цикла если оператор break не доступен, или раннему завершению вложенного цикла, если не доступен оператор break для нескольких уровней вложенности или не доступны исключения.
Функции высшего порядка[править | править код]
Так как в большинстве языков функции являются корректным возвращаемым типом, то возможно создать вложенную функцию, которая имеет доступ к набору параметров из внешней функции и использовать такую функцию в качестве возвращаемого значения внешней функции. Таким образом возможно вернуть функцию, предназначенную для выполнения определенной задачи без параметров или с небольшим набором параметров переданными в неё, что может значительно увеличить производительность.[4]
Альтернативы[править | править код]
Главной альтернативой вложенным функциям в языках программирования, в которых отсутствует их поддержка является перенос всех релевантных функций и переменных в отдельный модуль (файл) и предоставление доступа только к функции-обёртке верхнего уровня. В языке программирования С в общих случаях это будет сделано с использованием статических функций для инкапсуляции и статических переменных для связи.[5] Это помогает в инкапсуляции и совместном использовании состояния, хотя отсутствует логическая организация кода, которая возможна с лексическим вложением функций, и происходит за счет создания дополнительного файла. Также невозможно создать вложенность больше одного уровня.
Другая альтернатива совместного использования состояния между функциями возможна с использованием параметров функции, в большинстве случаев передавая ссылки в качестве аргументов, для избежания затрат на копирование. В общих случаях в С это реализовано с использованием указателя на структуру, содержащую контекст.[5] Это значительно усложняет вызовы функции.[3]
В PHP и других языках анонимная функция является единственной альтернативой: вложенная функция объявляется не как обычная функция, а как ссылка на локальную переменную. Для использования локальных переменных в анонимных функциях, используется замыкание.
Языки программирования[править | править код]
Хорошо известные языки программирования лексически поддерживающие вложенные функции включают:
- Основанные на Алгол языки такие как Алгол 68, Симула, Паскаль, Модула-2, Модула-3, Оберон, Seed7 и Ада
- Современные версии языка программирования Lisp (с лексической областью видимости) такие как Scheme, и Common Lisp
- ECMAScript (JavaScript и ActionScript)
- Dart[6]
- Kotlin (локальные функции[7])
- Scala (вложенные функции[8])
- Различные уровни поддержки в скриптовых языках, таких как Ruby, Python, Lua, PHP и Perl
- GCC поддерживает вложенные функции в С, как расширение языка.[9]
- C#, начиная с C# 7.0
- Язык D, относящийся к C язык с вложенными функциями.
- Фортран, начиная с Fortran-90, поддерживает одиночный уровень вложенных подпрограмм и функций.
- MATLAB (полная поддержка)
- Wolfram
Функциональные языки[править | править код]
В большинстве языков функционального программирования, таких как Scheme, вложенные функции с циклами являются обычным способом реализации алгоритмов. Простая (хвостовая) рекурсивная внутренняя функция создается и используется в качестве главного цикла алгоритма, в то время, когда внешняя функция выполняет действия, связанные с запуском, которые должны быть выполнены только однажды. В большинстве сложных случаев, ряд взаимно рекурсивных функций может быть создан в качестве внутренних функций.
Некоторые языки без прямой поддержки[править | править код]
Определенные языки не имеют прямой синтаксической и семантической поддержки для реализации вложенных функций. Несмотря на это, для некоторых из них аналогия вложенных функций может быть смоделирована с некоторой степенью сложности с использованием других языковых конструкций. Следующие языки могут реализовать аналог вложенных функций с помощью соответствующих стратегий:
- C++
- перед версией C++11: позволяет определить классы внутри классов, предоставляя возможность использования методов класса способом похожим на вложенные функции для одного уровня (смотри Функциональный объект в C++).
- начиная с версии C++11: используя лямбда выражения, например, быстрая сортировка, показанная выше.[10]
- Eiffel явно не позволяет использование вложенных функций, для того чтобы сохранить простоту языка, а также использует соглашение об использовании специальной переменной, Result, для обозначения результата функции, возвращающей значение.
- Visual Basic, с использованием анонимных методов или лямбда выражений.
- Java с использованием лямбда выражений[11] (смотри Анонимные функции в Java) (начиная с Java 8) или с использованием обходного пути, который состоит в использовании анонимного класса, содержащего единственный метод. Может быть также использован именованный класс объявленный локально в методе.
Реализация[править | править код]
Реализация вложенных функций может потребовать больше внимания, чем это кажется, так как ссылка на внутреннюю функцию, которая ссылается на нелокальную переменную создает замыкание. По этой причине вложенные функции не поддерживаются в некоторых языках программирования таких как C, C++ или Java, так как это создает сложности для компиляторов при компиляции подобных программ.[5][12] Несмотря на это, некоторые компиляторы поддерживают их в виде специального расширения компилятора. Хорошо известный пример — это реализация GNU C языка программирования C.
См. также[править | править код]
Примечания[править | править код]
- ↑ Rothwell, Trevis J. The GNU C Reference Manual. — Free Software Foundation, Inc, 2011. — P. 63.
- ↑ Re: Nesting functions- Why? Архивная копия от 21 марта 2016 на Wayback Machine, baavgai Архивная копия от 8 февраля 2022 на Wayback Machine, 14 January 2012
- ↑ 1 2 Bright, 2004.
- ↑ Higher-Order Functions and Lambdas - Kotlin Programming Language. Дата обращения: 10 февраля 2023. Архивировано 8 февраля 2023 года.
- ↑ 1 2 3 "Question 20.24: Why doesn't C have nested functions? Архивная копия от 7 октября 2011 на Wayback Machine, comp.lang.c FAQ
- ↑ A tour of the Dart language. Дата обращения: 10 февраля 2023. Архивировано 14 января 2020 года.
- ↑ Functions | Kotlin. Дата обращения: 10 февраля 2023. Архивировано 10 февраля 2023 года.
- ↑ Nested Methods. Дата обращения: 10 февраля 2023. Архивировано 10 февраля 2023 года.
- ↑ Nested Functions – Using the GNU Compiler Collection (GCC). GNU Project. Дата обращения: 6 января 2007. Архивировано 11 декабря 2006 года.
- ↑ Nested function - Rosetta Code. Дата обращения: 10 февраля 2023. Архивировано 10 февраля 2023 года.
- ↑ Nested function - Rosetta Code. Дата обращения: 10 февраля 2023. Архивировано 10 февраля 2023 года.
- ↑ answer by Dave Vandervies, Aug 28 '09 at 17:45, to "Why are nested functions not supported by the C standard? Архивная копия от 10 февраля 2023 на Wayback Machine"
Литература[править | править код]
- Walter Bright. Nested Functions (англ.) (2004).
Ссылки[править | править код]
- comp.lang.c FAQ: Nested Functions
- "6.4 Nested procedure and functions". FreePascal documentation.