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

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

Вложенные функции используются во многих подходах к структурное программирование, в том числе ранние, такие как АЛГОЛ, Симула 67 и Паскаль, а также во многих современных динамические языки и функциональные языки. Однако они традиционно не поддерживаются в (изначально простом) семействе языков C.

Эффекты

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

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

Примеры

Пример с использованием синтаксиса Паскаля (с АЛГОЛ, Модула 2, Оберон, Ада и т.п. аналогичные):

функция E(Икс: настоящий): настоящий;    функция F(у: настоящий): настоящий;    начать        F := Икс + у    конец;начать    E := F(3) + F(4)конец;

Функция F вложен в E. Обратите внимание, что Eпараметр Икс виден также в F (так как F является частью E) в то время как оба Икс и у невидимы снаружи E и F соответственно.

Точно так же в Standard ML:

весело е (Икс : настоящий) =  позволять    весело ж у = Икс+у  в    ж 3 + ж 4  конец;

Один из способов написать тот же пример в Haskell синтаксис:

е :: Плавать -> Плаватье Икс = ж 3 + ж 4 где ж у = Икс + у

Тот же пример в GNU C синтаксис[1] (C расширен вложенными функциями):

плавать E(плавать Икс){    плавать F(плавать у)    {        вернуть Икс + у;    }    вернуть F(3) + F(4);}

Быстрая сортировка

Более реалистичным примером является реализация быстрая сортировка:[2]

пустота Сортировать(int *Предметы, int размер) {    пустота quickSort(int первый, int последний) {        пустота своп(int п, int q) {            int tmp = Предметы[п];            Предметы[п] = Предметы[q];            Предметы[q] = tmp;        }                int раздел() {            int поворот = Предметы[первый], показатель = первый;            своп(показатель, последний);            для (int я = первый; я < последний; я++)                если (Предметы[я] < поворот)                    своп(показатель++, я);            своп(показатель, последний);            вернуть показатель;        }        если (первый < последний) {            int pivotIndex = раздел();            quickSort(первый, pivotIndex - 1);            quickSort(pivotIndex + 1, последний);        }    }    quickSort(0, размер - 1);}

Другой пример - следующая реализация Быстрая сортировка на основе разделов Хора с помощью C ++ 11 синтаксис лямбда-выражения:

шаблон<typename RandomAccessIterator>авто Сортировать(RandomAccessIterator Начать, RandomAccessIterator Конец)->пустота {	авто Раздел = [&]() {		// Схема разбиения Хора		авто &Pivot = *Начать;		авто ВпередКурсор = Начать;		авто НазадКурсор = Конец - 1;		авто PartitionPositionFound = ложный;		авто LocatePartitionPosition = [&]() {			в то время как (*ВпередКурсор < Pivot)				++ВпередКурсор;			в то время как (Pivot < *НазадКурсор)				--НазадКурсор;			если (ВпередКурсор >= НазадКурсор)				PartitionPositionFound = правда;			еще				Своп(*ВпередКурсор, *НазадКурсор);		};		// Тривиальная вспомогательная функция		авто MoveOnAndTryAgain = [&]() {			++ВпередКурсор;			--НазадКурсор;		};		// Краткое описание фактического процесса разделения		в то время как (правда) {			LocatePartitionPosition();			если (PartitionPositionFound)				вернуть НазадКурсор + 1;			еще				MoveOnAndTryAgain();		}	};	// Краткое описание алгоритма быстрой сортировки	если (Начать < Конец - 1) {		авто PartitionPosition = Раздел();		Сортировать(Начать, PartitionPosition);		Сортировать(PartitionPosition, Конец);	}}

Цель

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

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

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

Другое использование

Поток управления

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

Функции высшего порядка

Основная статья: Функции высшего порядка

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

Альтернативы

Основная альтернатива вложенным функциям в языках, которые не поддерживают их, - это поместить все соответствующие функции и переменные в отдельный модуль (файл) и предоставить доступ только к верхнему уровню. функция-оболочка публично. В C это обычно делается с помощью статических функций для инкапсуляции и статические переменные для связи.[5] Это обеспечивает инкапсуляцию и совместное использование состояния, хотя и не логическую организацию, обеспечиваемую лексическим вложением функций, и достигается за счет наличия отдельного файла. Это также невозможно более чем на одном уровне.

Другой альтернативой является разделение состояния между функциями через параметры функции, чаще всего с передачей ссылок в качестве аргументов, чтобы избежать затрат на копирование. В C это обычно реализуется указателем на структуру, содержащую контекст.[5] Это значительно увеличивает сложность вызовов функций.[3]

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

Языки

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

Функциональные языки

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

Некоторые языки без прямой поддержки

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

  • C ++
    • до C ++ 11: позволяет определять классы внутри классов, обеспечивая возможность использования методов класса аналогично вложенным функциям в один уровень (см. Функциональный объект в C ++ ).
    • начиная с C ++ 11: с использованием лямбда-выражений в качестве примера быстрой сортировки выше.[7]
  • Эйфель явно запрещает вложение подпрограмм. Это сделано для упрощения языка, а также позволяет соглашаться с использованием специальной переменной, Результат, чтобы обозначить результат функции (возвращающей значение).
  • Visual Basic, используя анонимные методы или лямбда-выражения.
  • Ява, используя лямбда-выражения[8] (увидеть Анонимные функции в Java ) (начиная с Java 8) или с помощью обходного пути, заключающегося в анонимный класс содержащий единственный метод. Также может использоваться именованный класс, объявленный локальным для метода.

Реализация

Смотрите также: Тест на мужчину или мальчика

Реализация вложенных функций может быть более сложной, чем может показаться, поскольку ссылка на вложенную функцию, которая ссылается на нелокальные переменные, создает закрытие. По этой причине вложенные функции не поддерживаются на некоторых языках, таких как C, C ++ или Java, поскольку это затрудняет реализацию компиляторов.[5][9] Однако некоторые компиляторы поддерживают их как расширение для конкретного компилятора. Хорошо известным примером этого является GNU C реализация 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 предлагает -W батут предупреждение, чтобы предупредить о состоянии.

Программное обеспечение, разработанное с использованием Жизненный цикл безопасной разработки часто не разрешают использование вложенных функций в этом конкретном компиляторе (GCC) из-за потери стеков NX.[11]

Смотрите также

Заметки

использованная литература

  1. ^ Ротвелл, Тревис Дж. (2011). Справочное руководство GNU C. Free Software Foundation, Inc. стр. 63.
  2. ^ Re: Функции вложенности - Почему?, баавгай, 14 января 2012 г.
  3. ^ а б Яркий 2004.
  4. ^ Функции высшего порядка и лямбды - язык программирования Котлин
  5. ^ а б c "Вопрос 20.24: Почему в C нет вложенных функций?, comp.lang.c FAQ
  6. ^ «Вложенные функции - Использование коллекции компиляторов GNU (GCC)». Проект GNU. Получено 2007-01-06.
  7. ^ http://www.rosettacode.org/wiki/Nested_function#C.2B.2B
  8. ^ http://www.rosettacode.org/wiki/Nested_function#Java
  9. ^ ответ Дэйв Вандервис, 28 августа 2009 г., 17:45, в "Почему вложенные функции не поддерживаются стандартом C? "
  10. ^ Такое сочетание кода функции и его окружения иногда называют закрытие.
  11. ^ Уолтон, Джеффри. «Укрепление инструментальной цепочки на основе C». Проект безопасности открытых веб-приложений (OWASP). Получено 28 февраля 2017.

внешние ссылки