Вложенная функция

В компьютерном программировании ( вложенная функция или вложенная процедура или подпрограмма ) — это именованная функция , которая определена внутри другого включающего блока и имеет лексическую область действия внутри включающего блока, то есть ее можно вызвать только по имени внутри тела включающего блока. и может использовать идентификаторы , объявленные во внешних блоках , включая внешние функции. Включающий блок обычно, но не всегда, представляет собой другую функцию.

Поддержка языков программирования для вложенных функций различается. Что касается языков структурированного программирования , то он поддерживается в некоторых устаревших языках, таких как ALGOL , Simula 67 и Pascal , а также в широко используемом JavaScript . Обычно он поддерживается в динамических и функциональных языках. Однако он не поддерживается в некоторых широко используемых языках, включая стандартные C и C++ .

Другие технологии программирования предоставляют аналогичные преимущества. Например, лямбда-функция также позволяет определять функцию внутри функции (а также где-либо еще) и позволяет аналогично скрывать и инкапсулировать данные. Примечательно, что лямбда-функция не имеет имени (анонимна), поэтому не может быть вызвана по имени и не имеет аспекта видимости.

Атрибуты [ править ]

Областью действия вложенной функции является блок, который ее содержит, будь то функциональный блок или блок внутри тела функции. Он не виден (не может быть вызван по имени) за пределами содержащего его блока.

Вложенная функция может использовать идентификаторы (т. е. имена функций, переменных, типов, классов), объявленные в любом включающем блоке, за исключением случаев, когда они маскируются внутренними объявлениями с теми же именами.

Вложенная функция может быть объявлена внутри вложенной функции рекурсивно, чтобы сформировать глубоко вложенную структуру. Глубоко вложенная функция может обращаться к идентификаторам, объявленным во всех включающих ее блоках, включая включающие функции.

Вложенные функции могут в определенных ситуациях привести к созданию замыкания . Если вложенная функция может избежать охватывающей функции, например, если функции являются объектами первого класса , а вложенная функция передается другой функции или возвращается из объемлющей функции, то создается замыкание, и вызовы этой функции могут получить доступ к среду исходной функции. Кадр немедленно включающей функции должен оставаться активным до тех пор, пока не умрет последнее ссылающееся замыкание, и поэтому нелокальные автоматические переменные, на которые ссылаются замыкания, не могут быть выделены в стеке в языках, которые позволяют замыканию сохраняться после времени жизни включающего блока. Это известно как проблема funarg и является основной причиной того, почему вложенные функции не были реализованы в некоторых более простых языках, поскольку это значительно усложняет генерацию и анализ кода, особенно когда функции вложены на разные уровни, разделяя разные части своей среды.

Значение [ править ]

Технология вложенных функций позволяет программисту писать исходный код , который включает в себя такие полезные функции, как сокрытие информации , инкапсуляция и декомпозиция . Программист может разделить задачу на подзадачи, которые имеют смысл только в контексте задачи, так что функции подзадачи скрыты от вызывающих сторон, которые не предназначены для их использования.

Область видимости блока позволяет функциям совместно использовать состояние включающих блоков (включая включающие функции) без передачи параметров или использования глобальных переменных . ^[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 
   в 
     f   3   +   f   4 
   закончится  ;

В Хаскеле :

e   ::   Float   ->   Float 
 e   x   =   f   3   +   f   4   где   f   y   =   x   +   y

В ПЛ/И :

e: процедура (x) возвращает (float);
   объявить x плавающим;
   f: процедура(y) возвращает(float);
     объявить y плавающим;
     вернуть х + у
     конец;
   вернуть f(3.0) + f)4.0);
   конец;

В Питоне :

def   e  (  x  :   float  )   ->   float  : 
   def   f  (  y  :   float  )   ->   float  : 
     return   x   +   y 
   return   f  (  3.0  )   +   f  (  4.0  )

В ГНУ С ^[3] – который расширяет стандарт C вложенными функциями:

float   E  (  float   x  ) 
 { 
     float   F  (  float   y  ) 
     { 
         return   x   +   y  ; 
      } 
     вернуть   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  ]; 
              предметы  [  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 синтаксиса лямбда-выражений , который является альтернативной технологией, которая также позволяет скрывать функцию внутри функции:

template  <  typename   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  ); 
	  } 
 }

Языки [ править ]

Известные языки, поддерживающие вложенные функции, включают:

Языки на основе ALGOL , такие как ALGOL 68 , Simula , Pascal , Modula-2 , Modula-3 , Oberon , PL/I , Seed7 и Ada.
Современные версии Lisp (с лексической областью действия), такие как Scheme и Common Lisp.
ECMAScript ( JavaScript и ActionScript )
Дарт ^[5]
Котлин (локальные функции ^[6])
Ржавчина
Scala (вложенные функции ^[7])
Различная степень поддержки языков сценариев, таких как Ruby , Python , Lua , PHP и Perl.
GCC поддерживает вложенные функции в C как расширение языка. ^[8]
C# , начиная с C# 7.0
Язык D — родственный язык C со вложенными функциями.
Фортран , начиная с Фортран-90 , поддерживает один уровень вложенных ( CONTAINed ) подпрограмм и функций.
МАТЛАБ (полная поддержка)
Вольфрам Язык

Функциональные языки [ править ]

В большинстве языков функционального программирования , таких как Scheme, вложенные функции являются распространенным способом реализации алгоритмов с циклами в них. Создается простая ( хвостовая ) рекурсивная внутренняя функция, которая ведет себя как основной цикл алгоритма, в то время как внешняя функция выполняет действия при запуске, которые необходимо выполнить только один раз. В более сложных случаях в качестве внутренних функций можно создать ряд взаимно рекурсивных функций.

Альтернативы [ править ]

Для достижения тех же результатов программирования, что и при использовании вложенных функций, можно использовать различные альтернативные методы.

Модульность [ править ]

Распространенной альтернативой является использование технологии модульности языка. Некоторые функции доступны для использования вне модуля, а некоторые видны только внутри модуля.

В C это можно реализовать, объявив функции и переменные как статические , чтобы скрыть их от кода вне файла. ^[9]Это позволяет скрывать, инкапсулировать и декомпозировать данные, но на другом уровне детализации , чем при использовании вложенных функций. Эта модульность не поддерживает более одного уровня вложенности.

В объектно-ориентированных языках класс обычно предоставляет область, в которой функции и состояние могут быть скрыты от потребителей класса, но доступны внутри класса. Некоторые языки допускают вложенность классов.

Параметры [ править ]

Чтобы реализовать сокрытие данных, функции могут передавать общие данные в качестве параметров, но это увеличивает сложность вызовов функций. ^[1]

В C это обычно реализуется путем передачи указателя на структуру, содержащую общие данные. ^[9]

Лямбда [ править ]

В PHP и других языках лямбда альтернативой является . Функция определяется в операторе кода, а не объявляется с использованием обычного синтаксиса функции. У него нет имени, но его можно вызвать через ссылку на функцию . Такие функции могут быть определены внутри функции, а также в других областях видимости. Чтобы использовать локальные переменные в анонимной функции, используйте замыкание .

Альтернативы по языкам [ править ]

Следующие языки предоставляют функции, аналогичные вложенным функциям:

C++ — классы позволяют аналогично скрывать и инкапсулировать данные; определение класса внутри класса обеспечивает аналогичную структуру (см. Объект функции в C++ ).

C++11 и более поздние версии — через лямбда-выражения (см. пример быстрой сортировки выше). ^[10]

Eiffel – явно запрещает вложение подпрограмм, чтобы язык был простым; допускает использование специальной переменной Result для обозначения результата функции (возвращающей значение).

C# и Visual Basic – через лямбда-выражения

Java – начиная с Java 8, через лямбда-выражения. ^[11], а в более старых версиях — через анонимный класс , содержащий единственный метод

Реализация [ править ]

Реализация вложенных функций может быть более сложной, чем может показаться, поскольку ссылка на вложенную функцию, которая ссылается на нелокальные переменные, создает замыкание . По этой причине вложенные функции не поддерживаются в некоторых языках, таких как C, C++ или Java, поскольку это усложняет реализацию компиляторов. ^[9]^[12]Однако некоторые компиляторы поддерживают их как расширение, специфичное для компилятора. Хорошо известным примером этого является реализация C GNU C , которая использует общий код с компиляторами таких языков, как Pascal, Ada и Modula.

Доступ к нелокальным объектам [ править ]

Существует несколько способов реализации вложенных процедур в языке с лексической областью, но классический способ заключается в следующем:

Любой нелокальный объект X доступен через ссылки доступа в кадрах активации в стеке машины. Вызывающий C помогает вызываемой процедуре P, передавая прямую ссылку на последнюю активацию непосредственной лексической инкапсуляции P (P) перед самим вызовом. Затем P может быстро найти нужную активацию для определенного X, следуя фиксированному количеству (P.глубина – X.глубина) ссылок (обычно небольшого количества).

Вызывающая сторона создает эту прямую ссылку, (сама по себе), следуя C.глубина – P.глубина + 1 более старые ссылки, ведущие к последней активации (P), а затем временно соединяя их прямой ссылкой на эту активацию; ссылка позже исчезает вместе с P, при этом более старые ссылки под ней могут снова использоваться.

Обратите внимание, что P виден для C и поэтому может быть вызван им, если (P) = C / (C) / ((C)) / и т. д.

Этот оригинальный метод быстрее, чем может показаться, но, тем не менее, его часто оптимизируют в практических современных компиляторах (с использованием дисплеев или подобных методов).

Другой способ реализации вложенных функций, который используется некоторыми компиляторами, — это преобразование («поднятие») вложенных функций в невложенные функции (где дополнительные скрытые параметры заменяют ссылки доступа) с использованием процесса, известного как лямбда-подъем, на промежуточном этапе. в компиляции.

Функции как значения [ править ]

Чтобы локальные функции с с лексической областью нелокальными переменными передавались в качестве результатов, код среды выполнения языка также должен неявно передавать среду (данные), которую функция видит внутри своей инкапсулирующей функции, чтобы она была доступна даже при текущей активации включающей функции. функция больше не существует. ^[13]Это означает, что среда должна храниться в другой области памяти, отличной от (впоследствии освобождаемых частей) стека выполнения, основанного на хронологии, что, в свою очередь, подразумевает своего рода свободное динамическое распределение памяти . Поэтому многие старые языки на основе Алгола (или его диалекты) не позволяют передавать локальные функции, которые обращаются к нелокальным значениям, в качестве возвращаемых значений или вообще не позволяют функциям в качестве возвращаемых значений, хотя передача таких функций в качестве аргументов все еще может быть возможной.

Стеки без выполнения [ править ]

Реализация вложенных функций в GCC приводит к потере , которые не выполняются стеков (стеки NX). Эта реализация вызывает вложенные функции с помощью инструкции перехода , помещаемой в машинный стек во время выполнения. Для этого необходимо, чтобы стек был исполняемым. Таким образом, стеки без выполнения и вложенные функции в GCC являются взаимоисключающими. Если при разработке программы используется вложенная функция, то стек NX незаметно теряется, если только GCC не вызывается с ‑Wtrampolineвозможность оповещения о состоянии. Программное обеспечение, разработанное с использованием жизненного цикла безопасной разработки, часто не позволяет использовать вложенные функции в этом конкретном компиляторе из-за потери стеков NX. ^[14]

См. также [ править ]

Ссылки [ править ]

^ Перейти обратно: ^а ^б Яркий 2004 год .
^ Функции высшего порядка и лямбды — язык программирования Kotlin
^ Ротвелл, Тревис Дж. (2011). Справочное руководство GNU C. Фонд свободного программного обеспечения, Inc. 63.
^ Re: Вложенные функции. Почему? , баавгай , 14 января 2012 г.
^ «Экскурсия по языку дартс» .
^ «Функции | Котлин» .
^ «Вложенные методы» .
^ «Вложенные функции – использование коллекции компиляторов GNU (GCC)» . Проект ГНУ . Проверено 6 января 2007 г.
^ Перейти обратно: ^а ^б ^с Вопрос 20.24: Почему в C нет вложенных функций? , comp.lang.c FAQ
^ «Вложенная функция — Rosetta Code» .
^ «Вложенная функция — Rosetta Code» .
^ ответ Дэйва Вандервиса, 28 авг. 2009, в 17:45, на вопрос « Почему вложенные функции не поддерживаются стандартом C? »
^ Такое сочетание кода функции и ее окружения иногда называют замыканием .
^ Уолтон, Джеффри. «Усиление защиты инструментальной цепочки на основе C» . Открытый проект безопасности веб-приложений (OWASP) . Проверено 28 февраля 2017 г.

Брайт, Уолтер (1 мая 2004 г.). «Вложенные функции» . Доктор Добб .

Внешние ссылки [ править ]

comp.lang.c FAQ: Вложенные функции
«6.4 Вложенные процедуры и функции» . Документация FreePascal.

[FOOTNOTEBright2004-1] Перейти обратно: ^а ^б Яркий 2004 год .

[Higher-Order_Functions_and_Lambdas_–_Kotlin_Programming_Language-2] Функции высшего порядка и лямбды — язык программирования Kotlin

[3] Ротвелл, Тревис Дж. (2011). Справочное руководство GNU C. Фонд свободного программного обеспечения, Inc. 63.

[4] Re: Вложенные функции. Почему? , баавгай , 14 января 2012 г.

[5] «Экскурсия по языку дартс» .

[6] «Функции | Котлин» .

[7] «Вложенные методы» .

[8] «Вложенные функции – использование коллекции компиляторов GNU (GCC)» . Проект ГНУ . Проверено 6 января 2007 г.

[cfaq-9] Перейти обратно: ^а ^б ^с Вопрос 20.24: Почему в C нет вложенных функций? , comp.lang.c FAQ

[10] «Вложенная функция — Rosetta Code» .

[11] «Вложенная функция — Rosetta Code» .

[12] ответ Дэйва Вандервиса, 28 авг. 2009, в 17:45, на вопрос « Почему вложенные функции не поддерживаются стандартом C? »

[13] Такое сочетание кода функции и ее окружения иногда называют замыканием .

[14] Уолтон, Джеффри. «Усиление защиты инструментальной цепочки на основе C» . Открытый проект безопасности веб-приложений (OWASP) . Проверено 28 февраля 2017 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]