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

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

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

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

Атрибуты

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

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

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

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

Ценить

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

Область видимости блока позволяет функциям совместно использовать состояние включающих блоков (включая включающие функции) без передачи параметров или использования глобальных переменных . ^[1]

Использование

Помощник

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

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

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

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

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

Примеры

Простой пример

Простой пример на Паскале:

function E(x: real): real;
    function F(y: real): real;
    begin
        F := x + y
    end;
begin
    E := F(3) + F(4)
end;

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

Аналогично в стандартном ML :

fun e (x : real) =
  let
    fun f y = x+y
  in
    f 3 + f 4
  end;

В Хаскеле :

e :: Float -> Float
e x = f 3 + f 4 where f y = x + y

В ПЛ/И :

e: procedure(x) returns(float);
  declare x float;
  f: procedure(y) returns(float);
    declare y float;
    return x + y
    end;
  return f(3.0) + f)4.0);
  end;

В Питоне :

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;
    }
    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;
        }

        if (first < last) {
            int pivotIndex = partition();
            quickSort(first, pivotIndex - 1);
            quickSort(pivotIndex + 1, last);
        }
    }
    quickSort(0, size - 1);
}

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

template<typename RandomAccessIterator>
auto Sort(RandomAccessIterator Begin, RandomAccessIterator End)->void {
	auto Partition = [&]() {
		//Hoare partition scheme
		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);
		};
		//Trivial helper function
		auto MoveOnAndTryAgain = [&]() {
			++ForwardCursor;
			--BackwardCursor;
		};
		//Brief outline of the actual partition process
		while (true) {
			LocatePartitionPosition();
			if (PartitionPositionFound)
				return BackwardCursor + 1;
			else
				MoveOnAndTryAgain();
		}
	};
	//Brief outline of the quicksort algorithm
	if (Begin < End - 1) {
		auto PartitionPosition = Partition();
		Sort(Begin, PartitionPosition);
		Sort(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]

См. также

Ссылки

^ Jump up to: ^а ^б Яркий 2004 год .
^ Функции высшего порядка и лямбды — язык программирования Kotlin
^ Ротвелл, Тревис Дж. (2011). Справочное руководство GNU C. Фонд свободного программного обеспечения, Inc. 63.
^ Re: Вложенные функции. Почему? , баавгай , 14 января 2012 г.
^ «Экскурсия по языку дартс» .
^ «Функции | Котлин» .
^ «Вложенные методы» .
^ «Вложенные функции – использование коллекции компиляторов GNU (GCC)» . Проект ГНУ . Проверено 6 января 2007 г.
^ Jump up to: ^а ^б ^с Вопрос 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] Jump up to: ^а ^б Яркий 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] Jump up to: ^а ^б ^с Вопрос 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]