Русская Википедия:Вложенная функция

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Эффекты

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

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

Примеры

Пример, с использованием синтаксиса языка Pascal (Алгол, Модула-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. Заметим, что параметр x функции E видим также в функции 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 where 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 = 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); 
} 
}

Назначение

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

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

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

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

Порядок выполнения

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

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

Шаблон:Main Так как в большинстве языков функции являются корректным возвращаемым типом, то возможно создать вложенную функцию, которая имеет доступ к набору параметров из внешней функции и использовать такую функцию в качестве возвращаемого значения внешней функции. Таким образом возможно вернуть функцию, предназначенную для выполнения определенной задачи без параметров или с небольшим набором параметров переданными в неё, что может значительно увеличить производительность.[3]

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

Главной альтернативой вложенным функциям в языках программирования, в которых отсутствует их поддержка является перенос всех релевантных функций и переменных в отдельный модуль (файл) и предоставление доступа только к функции-обёртке верхнего уровня. В языке программирования С в общих случаях это будет сделано с использованием статических функций для инкапсуляции и статических переменных для связи.[4] Это помогает в инкапсуляции и совместном использовании состояния, хотя отсутствует логическая организация кода, которая возможна с лексическим вложением функций, и происходит за счет создания дополнительного файла. Также невозможно создать вложенность больше одного уровня.

Другая альтернатива совместного использования состояния между функциями возможна с использованием параметров функции, в большинстве случаев передавая ссылки в качестве аргументов, для избежания затрат на копирование. В общих случаях в С это реализовано с использованием указателя на структуру, содержащую контекст.[4] Это значительно усложняет вызовы функции.Шаблон:Sfn

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

Языки программирования

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

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

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

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

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

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

Реализация

Шаблон:See also Реализация вложенных функций может потребовать больше внимания, чем это кажется, так как ссылка на внутреннюю функцию, которая ссылается на нелокальную переменную создает замыкание. По этой причине вложенные функции не поддерживаются в некоторых языках программирования таких как C, C++ или Java, так как это создает сложности для компиляторов при компиляции подобных программ.[4][11] Несмотря на это, некоторые компиляторы поддерживают их в виде специального расширения компилятора. Хорошо известный пример — это реализация GNU C языка программирования C.

См. также

Примечания

Шаблон:Reflist Шаблон:Refbegin Шаблон:Refend

Литература

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite book
  2. ↑ Re: Nesting functions- Why? Шаблон:Wayback, baavgai Шаблон:Wayback, 14 January 2012
  3. ↑ Шаблон:Cite web
  4. ↑ 4,0 4,1 4,2 "Question 20.24: Why doesn't C have nested functions? Шаблон:Wayback, comp.lang.c FAQ
  5. ↑ Шаблон:Cite web
  6. ↑ Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite web
  11. ↑ answer by Dave Vandervies, Aug 28 '09 at 17:45, to "Why are nested functions not supported by the C standard? Шаблон:Wayback"
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Вложенная_функция&oldid=9421928