В компьютерном программировании , A вложенная функция (или вложенная процедура или подпрограмма ) представляет собой функцию , которая определена внутри другой функции, в функции включения . Из-за простых рекурсивных правил области видимости вложенная функция сама невидима за пределами своей непосредственно включающей функции, но может видеть (получать доступ) все локальные объекты (данные, функции, типы и т. Д.) Своей немедленно включающей функции, а также любой функции. (s), который, в свою очередь, включает эту функцию. Вложенность теоретически возможна до неограниченной глубины, хотя в практических программах обычно используется только несколько уровней.
Вложенные функции используются во многих подходах к структурированному программированию , включая ранние, такие как ALGOL , Simula 67 и Pascal , а также во многих современных динамических языках и функциональных языках . Однако они традиционно не поддерживаются в (изначально простом) семействе языков C.
Эффекты
Вложенные функции предполагают область действия или область действия блока . Объем вложенной функции находится внутри функции-оболочки, то есть внутри одного из составляющих блоков этой функции, что означает, что она невидима вне этого блока, а также вне функции-оболочки. Вложенная функция может обращаться к другим локальным функциям, переменным, константам, типам, классам и т. Д., Которые находятся в той же области или в любой охватывающей области, без явной передачи параметров, что значительно упрощает передачу данных во вложенную функцию и из нее. Обычно это разрешено как для чтения, так и для записи.
Вложенные функции могут в определенных ситуациях (и в некоторых языках) приводить к закрытию . Если вложенная функция может выйти из включающей функции, например, если функции являются объектами первого класса, а вложенная функция передается другой функции или возвращается из включающей функции, то создается закрытие, и вызовы этой функции могут получить доступ окружение исходной функции. Фрейм немедленно включающей функции должен оставаться активным до тех пор, пока не умрет последнее ссылающееся замыкание, и поэтому нелокальные автоматические переменные, на которые ссылаются замыкания, не могут быть выделены в стеке . Это известно как проблема funarg и является ключевой причиной того, почему вложенные функции не были реализованы в некоторых более простых языках, поскольку это значительно усложняет генерацию и анализ кода, особенно когда функции вложены на разных уровнях, разделяя разные части своей среды.
Примеры
Пример с использованием синтаксиса Паскаля (с аналогичными ALGOL , Modula 2 , Oberon , Ada и т. Д.):
функция E ( x : real ) : real ; функция F ( y : действительный ) : действительный ; начало F : = x + y конец ; начало E : = F ( 3 ) + F ( 4 ) конец ;
Функция F
вложена в E
. Обратите внимание, что E
параметр 's x
также виден в 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, где 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 = элементы [ первый ], индекс = первый ; своп ( индекс , последний ); for ( int i = first ; i < last ; i ++ ) if ( items [ i ] < pivot ) swap ( index ++ , i ); своп ( индекс , последний ); индекс возврата ; } если ( первый < последний ) { 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 ; если ( ForwardCursor > = BackwardCursor ) PartitionPositionFound = true ; иначе Swap ( * ForwardCursor , * BackwardCursor ); }; // Простая вспомогательная функция auto MoveOnAndTryAgain = [ & ] () { ++ ForwardCursor ; - BackwardCursor ; }; // Краткое описание фактического процесса разбиения while ( true ) { LocatePartitionPosition (); если ( PartitionPositionFound ) return BackwardCursor + 1 ; иначе MoveOnAndTryAgain (); } }; // Краткое описание алгоритма быстрой сортировки if ( Begin < End - 1 ) { auto PartitionPosition = Partition (); Сортировка ( Начало , Позиция раздела ); Сортировка ( Позиция раздела , Конец ); } }
Цель
Лексически вложенные определения функций являются формой сокрытия информации и полезны для разделения процедурных задач на подзадачи, которые имеют смысл только локально. Это позволяет избежать загромождения других частей программы функциями и переменными, не связанными с этими частями.
Обычно они используются как вспомогательные функции или как рекурсивные функции внутри другой функции (как в приведенном выше примере быстрой сортировки). Это имеет структурное преимущество в виде организации кода, позволяет избежать загрязнения области, а также позволяет функциям легко обмениваться состоянием. [3] Поскольку вложенная функция может обращаться к локальным переменным включающей функции, совместное использование состояния возможно без передачи параметров вложенной функции или использования глобальной переменной , что упрощает код.
В языках с вложенными функциями функции обычно могут также содержать локальные константы и типы (в дополнение к локальным переменным , параметрам и функциям), инкапсулированные и скрытые таким же вложенным образом на любом уровне глубины. Это может дополнительно расширить возможности структурирования кода.
Другое использование
Поток управления
Вложенные функции также могут использоваться для неструктурированного потока управления , используя оператор return для общего неструктурированного потока управления. Это можно использовать для более детального управления, чем это возможно с другими встроенными функциями языка - например, он может разрешить досрочное завершение цикла for, если break
он недоступен, или раннее завершение вложенного цикла for, если несколько -уровень break
или исключения недоступны.
Функции высшего порядка
Поскольку в большинстве языков функции являются допустимыми возвращаемыми типами, можно создать вложенную функцию, которая получает доступ к набору параметров из внешней функции, и эта функция должна быть значением, возвращаемым внешней функцией. Таким образом, можно вернуть функцию, которая настроена на выполнение определенной задачи, с небольшими дополнительными параметрами или без них, что может значительно повысить производительность. [4]
Альтернативы
Основной альтернативой вложенным функциям в языках, которые не поддерживают их, является размещение всех соответствующих функций и переменных в отдельном модуле (файле) и публичное раскрытие только функции оболочки верхнего уровня . В C это обычно делается с помощью статических функций для инкапсуляции и статических переменных для связи. [5] Это обеспечивает инкапсуляцию и совместное использование состояния, хотя и не логическую организацию, обеспечиваемую лексическим вложением функций, и достигается за счет наличия отдельного файла. Это также невозможно более чем на одном уровне.
Другой альтернативой является разделение состояния между функциями через параметры функции, чаще всего с передачей ссылок в качестве аргументов, чтобы избежать затрат на копирование. В C это обычно реализуется указателем на структуру, содержащую контекст. [5] Это значительно увеличивает сложность вызовов функций. [3]
В PHP и других языках анонимная функция является единственной альтернативой: вложенная функция объявляется не как обычная функция, а по ссылке, как локальная переменная. Чтобы использовать локальные переменные в анонимной функции, используйте замыкание .
Языки
Хорошо известные языки, поддерживающие лексически вложенные функции, включают:
- Алгол основанных языков , такие как АЛГОЛ 68 , Симула , Pascal , Modula-2 , Modula-3 , Оберон , Seed7 и Ada
- Современные версии Lisp (с лексической областью видимости), такие как Scheme и Common Lisp
- ECMAScript ( JavaScript и ActionScript )
- Scala (полная поддержка)
- Различные степени поддержки языков сценариев, таких как Ruby , Python , Lua , PHP и Perl.
- GCC поддерживает вложенные функции в C как расширение языка. [6]
- C # , начиная с C # 7.0
- Язык D , связанный с C язык с вложенными функциями.
- Fortran , начиная с Fortran-90 , поддерживает один уровень вложенных ( CONTAINED ) подпрограмм и функций.
- MATLAB (полная поддержка)
- Язык Wolfram Language
- Пешка с YSI
Функциональные языки
В большинстве языков функционального программирования , таких как Scheme, вложенные функции являются обычным способом реализации алгоритмов с циклами в них. Создается простая ( хвостовая ) рекурсивная внутренняя функция, которая ведет себя как основной цикл алгоритма, в то время как внешняя функция выполняет действия при запуске, которые необходимо выполнить только один раз. В более сложных случаях несколько взаимно рекурсивных функций могут быть созданы как внутренние функции.
Некоторые языки без прямой поддержки
Некоторые языки не имеют прямой синтаксической и семантической поддержки для реализации вложенных функций. Тем не менее, для некоторых из них идея вложенных функций может быть смоделирована с некоторой степенью сложности за счет использования других языковых конструкций. Следующие языки могут аппроксимировать вложенные функции с помощью соответствующих стратегий:
- C ++
- до C ++ 11: позволяет определять классы внутри классов, обеспечивая возможность использования методов класса аналогично вложенным функциям на одном уровне (см. Объект функции в C ++ ).
- начиная с C ++ 11: с использованием лямбда-выражений в качестве примера быстрой сортировки выше. [7]
- Eiffel явно запрещает вложение подпрограмм. Это сделано для упрощения языка, а также позволяет использовать специальную переменную Result для обозначения результата функции (возвращающей значение).
- Visual Basic с использованием анонимных методов или лямбда-выражений.
- Java , используя лямбда-выражения [8] (см. Анонимные функции в Java ) (начиная с Java 8) или обходной путь, который заключается в анонимном классе, содержащем единственный метод. Также может использоваться именованный класс, объявленный локальным для метода.
Выполнение
Реализация вложенных функций может быть более сложной, чем может показаться, поскольку ссылка на вложенную функцию, которая ссылается на нелокальные переменные, создает замыкание . По этой причине вложенные функции не поддерживаются на некоторых языках, таких как C, C ++ или Java, поскольку это затрудняет реализацию компиляторов. [5] [9] Однако некоторые компиляторы поддерживают их как специфические расширения компилятора. Хорошо известным примером этого является реализация C для GNU C, в которой код используется совместно с компиляторами таких языков, как Pascal, Ada и Modula.
Доступ к нелокальным объектам
Есть несколько способов реализовать вложенные процедуры на языке с лексической областью видимости, но классический способ выглядит следующим образом:
- Любой нелокальный объект X доступен через ссылки доступа в кадрах активации в машинном стеке. Вызывающий C помогает вызываемой процедуре P, вставляя прямую ссылку на последнюю активацию непосредственной лексической инкапсуляции P (P) до самого вызова. Затем P может быстро найти правильную активацию для определенного X, следуя фиксированному количеству (P.depth - X.depth) ссылок (обычно небольшое количество).
- Вызывающий создает эту прямую ссылку (сам), следуя старым ссылкам C.depth - P.depth + 1, ведущим к последней активации (P), а затем временно соединяется с ними с прямой ссылкой на эту активацию; позднее ссылка исчезает вместе с буквой P, в результате чего старые ссылки под ней могут снова использоваться.
- Обратите внимание, что P виден для C и, следовательно, может вызываться им, если (P) = C / (C) / ((C)) / и т. Д.
Этот оригинальный метод быстрее, чем может показаться, но, тем не менее, он часто оптимизируется в практических современных компиляторах (с использованием дисплеев или аналогичных методов).
Другой способ реализации вложенных функций, который используется некоторыми компиляторами, - это преобразование («подъем») вложенных функций в не вложенные функции (где дополнительные, скрытые параметры заменяют ссылки доступа) с использованием процесса, известного как лямбда-лифтинг, на промежуточном этапе. в сборнике.
Функции как значения
Чтобы локальные функции с нелокальными переменными с лексической областью видимости передавались в качестве результатов, код среды выполнения языка также должен неявно передавать среду (данные), которые функция видит внутри своей инкапсулирующей функции, чтобы она была доступна также при текущей активации включающей функция больше не существует. [10] Это означает, что окружающая среда должна храниться в другой области памяти, чем (впоследствии восстановленные части) стека выполнения, основанного на хронологическом порядке, что, в свою очередь, подразумевает некое свободное динамическое распределение памяти . Поэтому многие старые языки на основе Algol (или их диалекты) не позволяют передавать локальные функции, которые обращаются к нелокальным значениям, в качестве возвращаемых значений или вообще не разрешают функции в качестве возвращаемых значений, хотя передача таких функций в качестве аргументов все еще возможна.
Неисполняемые стеки
По крайней мере, одна реализация вложенных функций вызывает потерю стека невыполнения (стек NX) . Реализация вложенной функции GCC вызывает вложенные функции с помощью инструкции перехода, помещаемой в машинный стек во время выполнения. Для этого требуется, чтобы стек был исполняемым.
В GCC стеки выполнения и вложенные функции не исключают друг друга. Если вложенная функция используется при разработке программы, стек NX автоматически теряется. GCC предлагает предупреждение -Wtrampoline для предупреждения об этом состоянии.
Программное обеспечение, спроектированное с использованием безопасного жизненного цикла разработки, часто не позволяет использовать вложенные функции в этом конкретном компиляторе (GCC) из-за потери стеков NX. [11]
Смотрите также
- Стек вызовов
- Закрытие (информатика)
- Внутренний класс
- Вложенность (вычисления)
Заметки
Рекомендации
- ^ Rothwell, Тревис J. (2011). GNU C Справочное руководство . Free Software Foundation, Inc. стр. 63.
- ^ Re: Функции вложенности - Почему? , баавгай , 14 января 2012 г.
- ^ а б Яркий 2004 .
- ^ Функции высшего порядка и лямбды - язык программирования Kotlin
- ^ a b c " Вопрос 20.24: Почему в C нет вложенных функций?, comp.lang.c FAQ
- ^ «Вложенные функции - Использование коллекции компиляторов GNU (GCC)» . Проект GNU . Проверено 6 января 2007 . CS1 maint: обескураженный параметр ( ссылка )
- ^ http://www.rosettacode.org/wiki/Nested_function#C.2B.2B
- ^ http://www.rosettacode.org/wiki/Nested_function#Java
- ^ ответ Дэйва Вандервиса, 28 августа 2009 г. в 17:45, на вопрос « Почему вложенные функции не поддерживаются стандартом C? »
- ^ Такое сочетание кода функции и его окружения иногда называют закрытием .
- ^ Уолтон, Джеффри. «Укрепление инструментальной цепочки на основе C» . Открытый проект безопасности веб-приложений (OWASP) . Проверено 28 февраля 2017 года .
- Брайт, Уолтер (1 мая 2004 г.). «Вложенные функции» . Доктора Добба .
Внешние ссылки
- comp.lang.c FAQ: Вложенные функции
- «6.4 Вложенные процедуры и функции» . Документация FreePascal.