В компьютерном программировании вложенная функция (или вложенная процедура или подпрограмма ) — это функция , которая определена внутри другой функции, включающей функции . Из-за простых правил рекурсивной области видимости вложенная функция сама по себе невидима за пределами своей непосредственно включающей функции, но может видеть (обращаться) ко всем локальным объектам (данным, функциям, типам и т. д.) своей непосредственно включающей функции, а также любой функции. (s), который, в свою очередь, включает в себя эту функцию. Вложенность теоретически возможна на неограниченную глубину, хотя в практических программах обычно используются лишь несколько уровней.
Вложенные функции используются во многих подходах к структурному программированию , включая ранние, такие как ALGOL , Simula 67 и Pascal , а также во многих современных динамических и функциональных языках . Однако они традиционно не поддерживаются в (изначально простом) семействе языков C.
Вложенные функции предполагают область действия функции или область действия блока . Область действия вложенной функции находится внутри включающей функции, т. е. внутри одного из составляющих блоков этой функции, а это означает, что она невидима вне этого блока, а также вне включающей функции. Вложенная функция может обращаться к другим локальным функциям, переменным, константам, типам, классам и т. д., находящимся в той же области или в любой охватывающей области, без явной передачи параметров, что значительно упрощает передачу данных во вложенную функцию и из нее. Обычно это разрешено как для чтения, так и для записи.
Вложенные функции могут в определенных ситуациях (и языках) приводить к созданию замыкания . Если вложенная функция может избежать охватывающей функции, например, если функции являются объектами первого класса , а вложенная функция передается другой функции или возвращается из объемлющей функции, то создается замыкание, и вызовы этой функции могут получить доступ к среду исходной функции. Кадр немедленно включающей функции должен продолжать существовать до тех пор, пока не умрет последнее ссылающееся замыкание, и поэтому нелокальные автоматические переменные, на которые ссылаются замыкания, не могут быть выделены в стеке . Это известно как проблема funarg и является основной причиной того, почему вложенные функции не были реализованы в некоторых более простых языках, поскольку это значительно усложняет генерацию и анализ кода, особенно когда функции вложены на разные уровни, разделяя разные части своей среды.
Пример использования синтаксиса Pascal (с ALGOL , Modula 2 , Oberon , Ada и т. д. подобными):
функция E ( x : действительная ) : действительная ; функция F ( y : действительная ) : действительная ; начало F := x + y конец ; начало E := F ( 3 ) + F ( 4 ) конец ; Функция Fвложена в E. Обратите внимание, что Eпараметр 's xтакже виден внутри F(как Fчасть E), тогда как оба xи yневидимы снаружи Eи Fсоответственно.
Аналогично в стандартном ML :
fun e ( x : real ) = пусть fun f y = x + y в f 3 + f 4 закончится ;Один из способов написать тот же пример в синтаксисе Haskell :
e :: Float -> Float e x = f 3 + f 4 где f y = x + y Тот же пример в синтаксисе GNU C [1] (C расширен вложенными функциями):
float E ( float x ) { float F ( float y ) { return x + y ; } вернуть 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 ]; предметы [ p ] = предметы [ q ]; предметы [ q ] = tmp ; } Int Partition () { Int Pivot = элементы [ первый ], индекс = первый ; поменять местами ( индекс , последний ); for ( int i = first ; i < last ; i ++ ) , if ( items [ i ] < Pivot ) swap ( index ++ , i ); поменять местами ( индекс , последний ); индекс возврата ; } если ( первый < последний ) { int PivotIndex = раздел (); быстрая сортировка ( первый , PivotIndex - 1 ); быстрая сортировка ( pivotIndex + 1 , последний ); } } QuickSort ( 0 , размер — 1 ); } Другим примером является следующая реализация быстрой сортировки на основе разделов Хоара с использованием синтаксиса лямбда-выражений C++11 :
шаблон < имя типа RandomAccessIterator > auto Sort ( RandomAccessIterator Begin , RandomAccessIterator End ) -> void { auto Partition = [ & ]() { // Схема разделения Хоара auto & Pivot = * Begin ; авто ForwardCursor = Начало ; автоматический BackwardCursor = End - 1 ; авто PartitionPositionFound = ложь ; auto LocatePartitionPosition = [ & ]() { while ( * ForwardCursor < Pivot ) ++ ForwardCursor ; while ( Pivot < * BackwardCursor ) -- BackwardCursor ; если ( ForwardCursor >= BackwardCursor ) PartitionPositionFound = true ; иначе Обмен ( * ForwardCursor , * BackwardCursor ); }; //Тривиальная вспомогательная функция auto MoveOnAndTryAgain = [ & ]() { ++ ForwardCursor ; -- НазадКурсор ; }; //Краткое описание фактического процесса разделения while ( true ) { LocatePartitionPosition (); if ( PartitionPositionFound ) возвращает BackwardCursor + 1 ; иначе MoveOnAndTryAgain (); } }; //Краткое описание алгоритма быстрой сортировки if ( Begin < End - 1 ) { auto PartitionPosition = Partition (); Сортировка ( Начало , Позиция Раздела ); Сортировка ( PartitionPosition , End ); } } Определения лексически вложенных функций представляют собой форму сокрытия информации и полезны для разделения процедурных задач на подзадачи, которые имеют смысл только локально. Это позволяет избежать загромождения других частей программы функциями и переменными, не связанными с этими частями.
Обычно они используются как вспомогательные функции или как рекурсивные функции внутри другой функции (как в примере быстрой сортировки выше). Это имеет структурное преимущество, заключающееся в организации кода, позволяет избежать загрязнения области видимости, а также позволяет функциям легко обмениваться состоянием. [3] Поскольку вложенная функция может обращаться к локальным переменным включающей функции, совместное использование состояния возможно без передачи параметров во вложенную функцию или использования глобальной переменной , что упрощает код.
В языках с вложенными функциями функции обычно могут также содержать локальные константы и типы (в дополнение к локальным переменным , параметрам и функциям), инкапсулированные и скрытые таким же вложенным способом на любом уровне глубины. Это может еще больше расширить возможности структурирования кода.
Вложенные функции также можно использовать для неструктурированного потока управления , используя оператор return для общего неструктурированного потока управления. Это можно использовать для более детального управления, чем это возможно с другими встроенными функциями языка – например, оно может позволить досрочное завершение цикла for, если он breakнедоступен, или досрочное завершение вложенного цикла for, если несколько -уровень breakили исключения недоступны.
Поскольку в большинстве языков функции являются допустимыми типами возврата, можно создать вложенную функцию, которая обращается к набору параметров из внешней функции, то есть замыканию , и сделать эту функцию возвращаемым значением внешней функции. Таким образом, можно вернуть функцию, настроенную на выполнение определенной задачи, с небольшим количеством дополнительных параметров или вообще без них, что может значительно повысить производительность. [4]
Основная альтернатива вложенным функциям в языках, в которых они не поддерживаются, — это размещение всех соответствующих функций и переменных в отдельном модуле (файле) и публичное предоставление только функции- обертки верхнего уровня . В C это обычно делается с помощью статических функций для инкапсуляции и статических переменных для связи. [5] Это обеспечивает инкапсуляцию и совместное использование состояния, но не логическую организацию, обеспечиваемую лексической вложенностью функций, и достигается за счет наличия отдельного файла. Это также невозможно более чем на одном уровне.
Другая альтернатива — разделить состояние между функциями через параметры функции, чаще всего передавая ссылки в качестве аргументов, чтобы избежать затрат на копирование. В C это обычно реализуется указателем на структуру, содержащую контекст. [5] Это значительно увеличивает сложность вызовов функций. [3]
В PHP и других языках анонимная функция является единственной альтернативой: вложенная функция объявляется не как обычная функция, а по ссылке, как локальная переменная. Чтобы использовать локальные переменные в анонимной функции, используйте замыкание .
Хорошо известные языки, поддерживающие лексически вложенные функции, включают:
В большинстве языков функционального программирования , таких как Scheme, вложенные функции являются распространенным способом реализации алгоритмов с циклами в них. Создается простая ( хвостовая ) рекурсивная внутренняя функция, которая ведет себя как основной цикл алгоритма, в то время как внешняя функция выполняет действия запуска, которые необходимо выполнить только один раз. В более сложных случаях в качестве внутренних функций можно создать ряд взаимно рекурсивных функций.
Некоторые языки не имеют простой синтаксической и семантической поддержки для реализации вложенных функций. Тем не менее, для некоторых из них идею вложенных функций можно с некоторой степенью сложности смоделировать за счет использования других языковых конструкций. Следующие языки могут аппроксимировать вложенные функции с помощью соответствующих стратегий:
Реализация вложенных функций может быть более сложной, чем может показаться, поскольку ссылка на вложенную функцию, которая ссылается на нелокальные переменные, создает замыкание . По этой причине вложенные функции не поддерживаются в некоторых языках, таких как C, C++ или Java, поскольку это усложняет реализацию компиляторов. [5] [12] Однако некоторые компиляторы поддерживают их как специальное расширение компилятора. Хорошо известным примером этого является реализация C GNU C , которая использует общий код с компиляторами таких языков, как Pascal, Ada и Modula.
Существует несколько способов реализации вложенных процедур в языке с лексической областью, но классический способ заключается в следующем:
Этот оригинальный метод быстрее, чем может показаться, но, тем не менее, его часто оптимизируют в практических современных компиляторах (с использованием дисплеев или подобных методов).
Другой способ реализации вложенных функций, который используется некоторыми компиляторами, — это преобразование («поднятие») вложенных функций в невложенные функции (где дополнительные скрытые параметры заменяют ссылки доступа) с использованием процесса, известного как лямбда-подъем , на промежуточном этапе. в компиляции.
Чтобы локальные функции с нелокальными переменными с лексической областью передавались в качестве результатов, код среды выполнения языка также должен неявно передавать среду (данные), которую функция видит внутри своей инкапсулирующей функции, чтобы она была доступна даже при текущей активации включающей функции. функция больше не существует. [13] Это означает, что среда должна храниться в другой области памяти, отличной от (впоследствии освобожденных частей) хронологически основанного стека выполнения, что, в свою очередь, подразумевает своего рода свободное динамическое распределение памяти . Поэтому многие старые языки на основе Алгола (или его диалекты) не позволяют передавать локальные функции, которые обращаются к нелокальным значениям, в качестве возвращаемых значений или вообще не позволяют функциям в качестве возвращаемых значений, хотя передача таких функций в качестве аргументов все еще возможна.
Реализация вложенных функций в GCC приводит к потере стеков , которые не выполняются (стеки NX). Эта реализация вызывает вложенные функции с помощью инструкции перехода , помещаемой в машинный стек во время выполнения. Для этого необходимо, чтобы стек был исполняемым. Таким образом, стеки без выполнения и вложенные функции в GCC являются взаимоисключающими. Если при разработке программы используется вложенная функция, то стек NX автоматически теряется, если только не вызывается GCC с возможностью оповещения об этом условии. Программное обеспечение, разработанное с использованием жизненного цикла безопасной разработки, часто не позволяет использовать вложенные функции в этом конкретном компиляторе из-за потери стеков NX. [14]‑Wtrampoline