Войти
В компьютерном программировании, вложенная функция (или вложенная процедура или подпрограмма ) - это функция , которая определена внутри другой функции, включающей функцию. Из-за простых рекурсивных правил scope вложенная функция сама невидима за пределами своей немедленно включающей функции, но может видеть (получать доступ) все локальные объекты (данные, функции, типы и т. Д.) Своей немедленно включающей функции а также любой функции (ей), которая, в свою очередь, включает эту функцию. Вложенность теоретически возможна до неограниченной глубины, хотя в практических программах обычно используется только несколько уровней.
Вложенные функции используются во многих подходах к структурному программированию, включая ранние, такие как ALGOL, Simula 67 и Pascal, а также во многих современных динамических языках и функциональных языках. Однако они традиционно не поддерживаются в (изначально простом) семействе языков C.
Вложенные функции предполагают область действия или блок область действия. Объем вложенной функции находится внутри включающей функции, то есть внутри одного из составляющих блоков этой функции, что означает, что она невидима вне этого блока, а также вне включающей функции. Вложенная функция может обращаться к другим локальным функциям, переменным, константам, типам, классам и т. Д., Которые находятся в той же области или в любой охватывающей области без явной передачи параметров, что значительно упрощает передачу данных во вложенную функцию и из нее. Обычно это разрешено как для чтения, так и для записи.
Вложенные функции могут в определенных ситуациях (и на некоторых языках) приводить к созданию замыкания. Если вложенная функция может выйти из включающей функции, например, если функции являются объектами первого класса, а вложенная функция передается другой функции или возвращается из включающей функции, затем создается замыкание, и вызовы этой функции могут получить доступ к среде исходной функции. Фрейм немедленно включающей функции должен оставаться активным до тех пор, пока не исчезнет последнее ссылающееся замыкание, и поэтому нелокальные автоматические переменные, на которые ссылаются замыкания, не могут быть выделены в стек. Это известно как проблема funarg и является ключевой причиной того, почему вложенные функции не были реализованы в некоторых более простых языках, поскольку это значительно усложняет генерацию и анализ кода, особенно когда функции вложены на разные уровни, разделяя разные части их окружение.
Пример с использованием синтаксиса Паскаля (с ALGOL, Modula 2, Oberon, Ada и т. Д. Аналогично):
function E (x: real): real; функция F (y: действительный): действительный; начало F: = x + y конец; начало E: = F (3) + F (4) конец;
Функция Fвложена в E. Обратите внимание, что параметр Exвиден также в F(поскольку Fявляется частью E), а xи yневидимы за пределами Eи Fсоответственно.
Аналогично в Стандартном ML:
fun e (x: real) = let fun f y = x + y in f 3 + f 4 end;
Один из способов написать тот же пример в синтаксисе Haskell :
e :: Float ->Float ex = f 3 + f 4, где fy = x + y
Тот же пример в GNU C синтаксис (C расширен вложенными функциями):
float E (float x) {float F (float y) {return x + y; } return F (3) + F (4); }Более реалистичным примером является реализация quicksort :
void sort (int * items, int size) {void quickSort (int first, int last) {void swap ( int p, int q) {int tmp = элементы [p]; items [p] = items [q]; items [q] = tmp; } int partition () {int pivot = элементы [первый], индекс = первый; своп (индекс, последний); 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 синтаксиса лямбда-выражения :
шаблонаauto Sort (RandomAccessIterator Begin, RandomAccessIterator End) ->void {auto Partition = [] () {// Схема разделения Хоара 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);}; // Простая вспомогательная функция auto MoveOnAndTryAgain = [] () {++ ForwardCursor; --BackwardCursor;}; // Краткое описание фактического процесса разделения while (true) {LocatePartitionPosition (); if (PartitionPositionFound) return BackwardCursor + 1; else MoveOnAndTryAgain ();}}; // Краткое схема алгоритма быстрой сортировки if (Begin < End - 1) { auto PartitionPosition = Partition(); Sort(Begin, PartitionPosition); Sort(PartitionPosition, End); } }
Лексически вложенные определения функций являются формой info Операция скрывает и полезна для разделения процедурных задач на подзадачи, которые имеют смысл только локально. Это позволяет избежать загромождения других частей программы функциями и переменными, не связанными с этими частями.
Они обычно используются как вспомогательные функции или как рекурсивные функции внутри другой функции (как в примере быстрой сортировки выше). Это имеет структурное преимущество, заключающееся в организации кода, предотвращении загрязнения области, а также позволяет функциям легко обмениваться состоянием. Поскольку вложенная функция может обращаться к локальным переменным включающей функции, совместное использование состояния возможно без передачи параметров вложенной функции или использования глобальной переменной, что упрощает код.
В языках с вложенными функциями функции обычно могут также содержать локальные константы и типы (в дополнение к локальным переменным, параметры и функции), инкапсулированные и скрытые одинаково вложенным образом на любом уровне глубины. Это может дополнительно расширить возможности структурирования кода.
Вложенные функции также могут использоваться для неструктурированного потока управления, используя оператор return для общего неструктурированного потока управления. Это можно использовать для более тонкого управления, чем это возможно с другими встроенными функциями языка - например, это может позволить досрочное завершение цикла for, если breakнедоступно, или раннее завершение цикла вложенный для цикла, если многоуровневый разрывили исключения недоступны.
Поскольку в большинстве языков функции являются допустимыми возвращаемыми типами, можно создать вложенную функцию, которая получает доступ к набору параметров из внешней функции, и эта функция должна быть возвращаемое значение внешней функции. Таким образом, можно вернуть функцию, которая настроена на выполнение определенной задачи, с небольшими параметрами или без них, что может значительно повысить производительность.
Основная альтернатива для вложенные функции на языках, которые не поддерживают их, заключается в том, чтобы поместить все соответствующие функции и переменные в отдельный модуль (файл) и публично раскрыть только функцию-оболочку верхнего уровня. В C это обычно делается с помощью статических функций для инкапсуляции и статических переменных для связи. Это обеспечивает инкапсуляцию и совместное использование состояния, хотя и не логическую организацию, обеспечиваемую лексическим вложением функций, и достигается за счет наличия отдельного файла. Это также невозможно более чем на одном уровне.
Другой альтернативой является разделение состояния между функциями через параметры функции, чаще всего с передачей ссылок в качестве аргументов, чтобы избежать затрат на копирование. В C это обычно реализуется указателем на структуру, содержащую контекст. Это значительно увеличивает сложность вызовов функций.
В PHP и других языках анонимная функция является единственной альтернативой: вложенная функция объявляется не как обычная функция, но по ссылке, как локальная переменная. Чтобы использовать локальные переменные в анонимной функции, используйте closure.
Хорошо известные языки, поддерживающие лексически вложенные функции, включают:
В большинстве языков функционального программирования, таких как Scheme, вложенные функции являются обычным способом реализации алгоритмов с циклами в них. Создается простая (tail ) рекурсивная внутренняя функция, которая ведет себя как основной цикл алгоритма, в то время как внешняя функция выполняет действия запуска, которые необходимо выполнить только один раз. В более сложных случаях несколько взаимно рекурсивных функций могут быть созданы как внутренние функции.
Некоторые языки не имеют прямой синтаксической и семантической поддержки для реализации вложенных функций. Тем не менее, для некоторых из них идея вложенных функций может быть смоделирована с некоторой степенью сложности за счет использования других языковых конструкций. Следующие языки могут аппроксимировать вложенные функции с помощью соответствующих стратегий:
Реализация вложенных функций может быть сложнее, чем может показаться, поскольку ссылка на вложенную функцию, которая ссылается на нелокальные переменные, создает закрытие . По этой причине вложенные функции не поддерживаются на некоторых языках, таких как C, C ++ или Java, поскольку это затрудняет реализацию компиляторов. Однако некоторые компиляторы поддерживают их как расширение для конкретного компилятора. Хорошо известным примером этого является реализация C GNU C, которая использует общий код с компиляторами для таких языков, как Pascal, Ada и Modula.
Существует несколько способов реализации вложенных процедур на языке с лексической областью видимости, но классический способ выглядит следующим образом:
Этот оригинальный метод быстрее, чем может показаться, но, тем не менее, он часто оптимизируется в практических современных компиляторах (с использованием отображает или аналогичные методы).
Другой способ реализации вложенных функций, который используется некоторыми компиляторами, - это преобразование («подъем») вложенных функций в не вложенные функции (где дополнительные скрытые параметры заменяют ссылки доступа) с помощью процесса, известного как лямбда-подъем на промежуточном этапе компиляции.
Чтобы локальные функции с лексической областью видимости нелокальными передавались в качестве результатов, код языковой среды выполнения также должен неявно передавать окружение (данные), которое функция видит внутри своей инкапсулирующей функции, так что она становится доступной даже тогда, когда текущая активация включающей функции больше не существует. Это означает, что среда должна быть сохранена в другой области памяти, чем (впоследствии восстановленные части) стека выполнения, основанного на хронологическом порядке, что, в свою очередь, подразумевает некое свободное распределение динамической памяти. Поэтому многие старые языки на основе Algol (или их диалекты) не позволяют передавать локальные функции, которые обращаются к нелокальным значениям, в качестве возвращаемых значений или вообще не разрешают функции в качестве возвращаемых значений, хотя передача таких функций в качестве аргументов все еще возможна.
По крайней мере, одна реализация вложенных функций вызывает потерю стеков без выполнения (стек NX). Реализация вложенной функции GCC вызывает вложенные функции с помощью инструкции перехода , помещаемой в машинный стек во время выполнения. Для этого требуется, чтобы стек был исполняемым.
Никакие стеки выполнения и вложенные функции не являются взаимоисключающими в GCC. Если вложенная функция используется при разработке программы, стек NX автоматически теряется. GCC предлагает предупреждение -Wtrampolineдля оповещения о состоянии.
Программное обеспечение, спроектированное с использованием Жизненного цикла безопасной разработки, часто не позволяет использовать вложенные функции в этом конкретном компиляторе (GCC) из-за потери стеков NX.
