В программировании , вложенная функция (или вложенная процедура или подпрограмма ) является именованной функцией , которая определена внутри другого, охватывающего, блока и лексически ограничена внутри охватывающего блока - это означает, что она может быть вызвана только по имени внутри тела охватывающего блока и может использовать идентификаторы, объявленные во внешних блоках , включая внешние функции. Охватывающий блок обычно, но не всегда, является другой функцией.
Поддержка вложенных функций в разных языках программирования различается. Что касается структурированных языков программирования, она поддерживается в некоторых устаревших языках, таких как ALGOL , Simula 67 и Pascal , а также в широко используемом JavaScript . Она обычно поддерживается в динамических и функциональных языках. Однако она не поддерживается в некоторых широко используемых языках, включая стандартные C и C++ .
Другие технологии программирования предоставляют схожие преимущества. Например, лямбда-функция также позволяет определять функцию внутри функции (а также в другом месте) и допускает аналогичное скрытие и инкапсуляцию данных. Примечательно, что лямбда-функция не имеет имени (является анонимной) и, следовательно, не может быть вызвана по имени и не имеет аспекта видимости.
Областью действия вложенной функции является блок, который ее содержит – будь то блок функции или блок внутри тела функции. Она не видна (не может быть вызвана по имени) за пределами ее содержащего блока.
Вложенная функция может использовать идентификаторы (т. е. имена функций, переменных, типов, классов), объявленные в любом охватывающем блоке, за исключением случаев, когда они замаскированы внутренними объявлениями с теми же именами.
Вложенная функция может быть объявлена внутри вложенной функции, рекурсивно, для формирования глубоко вложенной структуры. Глубоко вложенная функция может получить доступ к идентификаторам, объявленным во всех ее охватывающих блоках, включая охватывающие функции.
Вложенные функции могут в определенных ситуациях приводить к созданию замыкания . Если вложенная функция может выйти из охватывающей функции, например, если функции являются объектами первого класса , а вложенная функция передается другой функции или возвращается из охватывающей функции, то создается замыкание, и вызовы этой функции могут получить доступ к среде исходной функции. Фрейм непосредственно охватывающей функции должен продолжать существовать до тех пор, пока не умрет последнее ссылающееся замыкание, и поэтому нелокальные автоматические переменные, на которые ссылаются в замыканиях, не могут быть выделены в стеке в языках, которые позволяют замыканию сохраняться после окончания срока службы охватывающего блока. Это известно как проблема фунаргов и является ключевой причиной, по которой вложенные функции не были реализованы в некоторых более простых языках, поскольку это значительно усложняет генерацию и анализ кода, особенно когда функции вложены в различные уровни, разделяя разные части своего окружения.
Технология вложенных функций позволяет программисту писать исходный код , включающий полезные атрибуты, такие как сокрытие информации , инкапсуляция и декомпозиция . Программист может разделить задачу на подзадачи, которые имеют смысл только в контексте задачи, так что функции подзадач будут скрыты от вызывающих, которые не предназначены для их использования.
Область видимости блока позволяет функциям совместно использовать состояние включающих блоков (включая включающие функции) без передачи параметров или использования глобальных переменных . [1]
Вложенная функция обычно действует как вспомогательная функция или рекурсивная функция (как в примере быстрой сортировки выше).
Вложенные функции могут использоваться для неструктурированного потока управления , используя оператор return для общего неструктурированного потока управления. Это может использоваться для более точного управления, чем это возможно с другими встроенными функциями языка – например, это может позволить досрочное завершение цикла for, если breakнедоступно, или досрочное завершение вложенного цикла for, если многоуровневый breakили исключения недоступны.
В некоторых языках можно создать вложенную функцию, которая обращается к набору параметров из внешней функции, то есть замыкание , и сделать эту функцию возвращаемым значением внешней функции. Таким образом, можно вернуть функцию, которая настроена на выполнение определенной задачи с небольшим количеством или без дополнительных параметров, что может значительно повысить производительность. [2]
Простой пример на Паскале:
функция E ( x : вещественное ) : вещественное ; функция F ( y : вещественное ) : вещественное ; начало F := x + y конец ; начало E := F ( 3 ) + F ( 4 ) конец ; Функция Fвложена в E. Обратите внимание, что Eпараметр xтакже виден в F(так как Fявляется частью E), тогда как xи yневидимы вне Eи Fсоответственно.
Аналогично в стандартном ML :
fun e ( x : real ) = пусть fun f y = x + y in f 3 + f 4 end ;В Хаскелле :
e :: Плавающий -> Плавающий e x = f 3 + f 4 , где f y = x + y В PL/I :
e: процедура(x) возвращает(float); объявить x float; f: процедура(y) возвращает(float); объявить y float; вернуть х + у конец; вернуть f(3.0) + f(4.0); конец;
На языке Python :
def e ( x : float ) -> float : def f ( y : float ) -> float : return x + y return f ( 3.0 ) + f ( 4.0 )В GNU C [3] – который расширяет стандартный C вложенными функциями:
float E ( float x ) { float F ( float y ) { return x + y ; } return F ( 3 ) + F ( 4 ); } Ниже приведена реализация быстрой сортировки : [4]
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 ; } если ( первый < последний ) { int pivotIndex = partition (); quickSort ( первый , pivotIndex - 1 ); quickSort ( pivotIndex + 1 , последний ); } } quickSort ( 0 , размер - 1 ); } Ниже представлена реализация быстрой сортировки на основе разбиения Хоара с использованием синтаксиса лямбда-выражений C++11 , который является альтернативной технологией, также позволяющей скрывать функцию внутри функции:
template < typename RandomAccessIterator > 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 ); } } Известные языки, поддерживающие вложенные функции:
В большинстве функциональных языков программирования , таких как Scheme, вложенные функции являются распространенным способом реализации алгоритмов с циклами в них. Создается простая ( хвостовая ) рекурсивная внутренняя функция, которая ведет себя как основной цикл алгоритма, в то время как внешняя функция выполняет действия запуска, которые необходимо выполнить только один раз. В более сложных случаях ряд взаимно рекурсивных функций могут быть созданы как внутренние функции.
Для достижения аналогичных результатов программирования, как и с помощью вложенных функций, можно использовать различные альтернативные методы.
Распространенной альтернативой является использование модульной технологии языка. Некоторые функции доступны для использования вне модуля, а некоторые видны только внутри модуля.
В C это можно реализовать, объявив функции и переменные статическими , чтобы скрыть их от кода за пределами файла. [10] Это позволяет скрывать данные, инкапсулировать и декомпозировать их, но на другом уровне детализации, чем с вложенными функциями. Эта модульность не поддерживает более одного уровня вложенности.
В объектно-ориентированных языках класс обычно предоставляет область, в которой функции и состояние могут быть скрыты от потребителей класса, но доступны внутри класса. Некоторые языки позволяют вкладывать классы.
Для реализации сокрытия данных функции могут передавать общие данные в качестве параметров, но это увеличивает сложность вызовов функций. [1]
В языке C это обычно реализуется путем передачи указателя на структуру, содержащую общие данные. [10]
В PHP и других языках лямбда является альтернативой. Функция определяется в операторе кода, а не объявляется с помощью обычного синтаксиса функции. У нее нет имени, но ее можно вызвать через ссылку на функцию . Такие функции могут быть определены как внутри функции, так и в других областях. Чтобы использовать локальные переменные в анонимной функции, используйте замыкание .
Следующие языки предоставляют функции, похожие на вложенные функции:
Реализация вложенных функций может быть более сложной, чем может показаться, поскольку ссылка на вложенную функцию, которая ссылается на нелокальные переменные, создает замыкание . По этой причине вложенные функции не поддерживаются в некоторых языках, таких как C, C++ или Java, поскольку это затрудняет реализацию компиляторов. [10] [13] Однако некоторые компиляторы поддерживают их в качестве специфичного для компилятора расширения. Хорошо известным примером этого является реализация C в GNU C , которая разделяет код с компиляторами для таких языков, как Pascal, Ada и Modula.
Существует несколько способов реализации вложенных процедур в языке с лексической областью действия, но классический способ выглядит следующим образом:
Этот оригинальный метод быстрее, чем может показаться, но тем не менее он часто оптимизируется в современных практических компиляторах (используя дисплеи или аналогичные методы).
Другой способ реализации вложенных функций, используемый некоторыми компиляторами, — это преобразование («поднятие») вложенных функций в невложенные функции (где дополнительные скрытые параметры заменяют ссылки доступа) с помощью процесса, известного как лямбда-поднятие, на промежуточном этапе компиляции.
Для того чтобы локальные функции с лексически ограниченными нелокальными переменными передавались как результаты, код времени выполнения языка также должен неявно передавать среду (данные), которые функция видит внутри своей инкапсулирующей функции, чтобы она была достижима и тогда, когда текущая активация охватывающей функции больше не существует. [14] Это означает, что среда должна храниться в другой области памяти, чем (впоследствии восстановленные части) хронологически основанный стек выполнения, что, в свою очередь, подразумевает некое свободное динамическое распределение памяти . Многие старые языки на основе Algol (или их диалекты) поэтому не позволяют передавать локальные функции, которые обращаются к нелокальным переменным, как возвращаемые значения, или вообще не позволяют передавать функции как возвращаемые значения, хотя передача таких функций в качестве аргументов все еще может быть возможна.
Реализация вложенных функций GCC приводит к потере стеков без выполнения (стеков NX). Эта реализация вызывает вложенные функции через инструкцию перехода , помещенную в стек машины во время выполнения. Для этого требуется, чтобы стек был исполняемым. Поэтому стеки без выполнения и вложенные функции являются взаимоисключающими в GCC. Если вложенная функция используется при разработке программы, то стек NX молча теряется, если только GCC не вызывается с опцией оповещения об этом состоянии. Программное обеспечение, разработанное с использованием Secure Development Lifecycle, часто не позволяет использовать вложенные функции в этом конкретном компиляторе из-за потери стеков NX. [15]‑Wtrampoline