В компьютерном программировании технология , называемая функцией , подпрограммой , процедурой , методом , процедурой или подпрограммой , представляет собой последовательность инструкций, которая имеет четко определенное поведение и может быть вызвана в компьютерной программе для демонстрации этого поведения.
Технология и название, используемые для нее, несколько различаются в зависимости от контекста (например, языка программирования ). Но есть концепция, общая для всех контекстов и названий. Общий термин «вызываемая единица» обычно не используется, но подразумевает более общую концепцию без последствий других, более часто используемых терминов. [1] Если не указано иное, эти термины используются в этой статье как взаимозаменяемые, причем функция часто означает то же самое, что и вызываемый unit .
Технология предоставляет мощный инструмент программирования. [2] Основная цель — обеспечить разбиение большой и/или сложной проблемы на фрагменты с относительно низкой когнитивной нагрузкой и присвоение значимого имени (если оно не анонимно). [3] Разумное применение может снизить затраты на разработку и поддержку программного обеспечения, одновременно повышая его качество и надежность. [4]
Эта технология присутствует на нескольких уровнях абстракции в среде программирования. Например, программист может написать функцию в исходном коде , который скомпилируется в машинный код, реализующий аналогичную семантику . В исходном коде есть вызываемая единица, а в машинном коде — связанная с ней единица, но это разные виды вызываемых единиц — с разными значениями и функциями.
Возможности функциональной технологии различаются в зависимости от контекста. В этом разделе описаны различные возможности, которые функции имеют в некоторых контекстах.
Функция может быть вызвана (вызвана) много раз и часто из многих других функций во время выполнения программы. Обычно выполнение программы продолжается со следующей инструкции после инструкции вызова, когда вызываемая функция возвращает управление.
Функция может быть написана так, чтобы ожидать параметры , которые функция объявляет как формальные параметры . Вызывающий объект передает фактические параметры , или аргументы , для сопоставления. Различные языки программирования предоставляют разные соглашения для передачи аргументов; см. ниже.
Функция может иметь побочный эффект , например изменение переданных или глобальных данных, чтение или запись на периферийное устройство , доступ к файлу , остановку программы или компьютера или временную приостановку выполнения программы. Широкое использование функций с побочными эффектами характерно для императивных языков программирования.
Функция может возвращать другое значение при каждом вызове, даже если ей переданы одни и те же аргументы или они отсутствуют. Одним из примеров является генератор псевдослучайных чисел , доступный на многих языках, который возвращает псевдослучайное число при каждом вызове.
Функцию можно написать так, чтобы она рекурсивно вызывала сама себя в одном или нескольких местах для выполнения своей задачи. Этот метод позволяет напрямую реализовать функции, определенные с помощью математической индукции и рекурсивных алгоритмов «разделяй и властвуй» .
Функция, предназначенная для вычисления логического значения (например, для ответа на вопрос «да» или «нет»), иногда называется предикатом . В языках логического программирования часто [ неопределенно ] все функции называются предикатами, поскольку именно они в первую очередь [ неопределенно ] определяют успех или неудачу. [ нужна цитата ]
Функция, которая не возвращает никакого значения или возвращает нулевое значение, иногда называется процедурой . Процедуры обычно изменяют свои аргументы или глобальное состояние и являются основной частью процедурного программирования .
В некоторых контекстах подпрограмма — это функция, которая не возвращает значение.
Чисто математическая функция возвращает значение , которое полностью определяется входными параметрами и не выполняет никаких других действий (побочных эффектов) и не изменяет какие-либо входные параметры. Например, вычисление логарифма числа или определителя матрицы .
В некоторых языках синтаксис функции, возвращающей значение, в основном такой же, как и синтаксис функции, которая этого не делает. Часто разница заключается в том, содержит ли тело функции оператор возврата со значением. В некоторых языках функция может возвращать значение с оператором значения или без него в зависимости от потока управления.
Функции могут быть определены внутри программы или отдельно в библиотеке , которая может использоваться несколькими программами.
Большинство языков программирования предоставляют возможности для определения и вызова функций, включая синтаксис для доступа к таким функциям, в том числе:
Некоторые языки, такие как Pascal , Fortran , Ada и многие диалекты BASIC , используют другое имя для вызываемой единицы, которая возвращает значение (функция или подпрограмма), а не для той, которая этого не делает (подпрограмма или процедура) . Другие языки, такие как C , C++ , C# и Lisp , используют только одно имя для вызываемой единицы — функции. В языках семейства C это ключевое слово используется voidдля обозначения отсутствия возвращаемого значения.
В строго функциональных языках программирования , таких как Haskell , функция не может иметь побочных эффектов , то есть она не может изменять состояние программы. Функции всегда возвращают один и тот же результат для одного и того же ввода. Такие языки обычно поддерживают только функции, которые возвращают значение, поскольку в функции нет значения, которое не имеет ни возвращаемого значения, ни побочного эффекта.
Если объявлено, что он возвращает значение, вызов можно внедрить в выражение , чтобы использовать возвращаемое значение. Например, вызываемая единица измерения квадратного корня может называться как y = sqrt(x).
Вызываемая единица, которая не возвращает значение, называется автономным оператором , например print("hello"). Этот синтаксис также можно использовать для вызываемого модуля, который возвращает значение, но возвращаемое значение будет игнорироваться.
В некоторых языках требуется ключевое слово для вызовов, которые не принимают возвращаемое значение, например CALL print("hello").
Компилятор преобразует операторы вызова и возврата в машинные инструкции в соответствии с четко определенным соглашением о вызовах . Для кода, скомпилированного тем же или совместимым компилятором, функции можно компилировать отдельно от программ, которые их вызывают. Последовательности инструкций, соответствующие операторам вызова и возврата, называются прологом и эпилогом процедуры .
Встроенная функция , или встроенная функция , или встроенная функция — это функция, для которой компилятор генерирует код во время компиляции или предоставляет его способом, отличным от других функций. [5] Встроенную функцию не нужно определять так же, как другие функции, поскольку она встроена в язык программирования. [6]
Преимущества разбиения программы на функции включают в себя:
По сравнению с использованием встроенного кода, вызов функции требует некоторых вычислительных затрат в механизме вызова. [ нужна цитата ]
Функция обычно требует стандартного служебного кода – как при входе в функцию, так и при выходе из нее ( пролог и эпилог функции – обычно с сохранением как минимум регистров общего назначения и адреса возврата).
Функциональная технология была первоначально задумана Джоном Мочли и Кэтлин Антонелли во время их работы над ENIAC [ 7] и записана на Гарвардском симпозиуме в январе 1947 года по теме «Подготовка задач для машин типа EDVAC ». [8] Морису Уилксу , Дэвиду Уиллеру и Стэнли Гиллу обычно приписывают формальное изобретение этой концепции, которую они назвали закрытой подпрограммой , [9] [10] в отличие от открытой подпрограммы или макроса . [11] Однако Алан Тьюринг обсуждал подпрограммы в статье 1945 года о предложениях по проектированию NPL ACE , доходя до того, что изобрел концепцию стека адресов возврата . [12]
Идея подпрограммы возникла после того, как вычислительные машины уже существовали некоторое время. Инструкции арифметических действий и условного перехода были запланированы заранее и изменились относительно мало, но специальные инструкции, используемые для вызовов процедур, сильно изменились за прошедшие годы. Самые ранние компьютеры и микропроцессоры, такие как Manchester Baby и RCA 1802 , не имели ни одной инструкции вызова подпрограммы. Подпрограммы можно было реализовать, но для этого требовалось, чтобы программисты использовали последовательность вызовов — серию инструкций — на каждом месте вызова .
Подпрограммы были реализованы в Z4 Конрада Цузе в 1945 году.
В 1945 году Алан М. Тьюринг использовал термины «похоронить» и «вытащить из погребения» как средство вызова подпрограмм и возврата из них. [13] [14]
В январе 1947 года Джон Мочли представил общие заметки на «Симпозиуме крупномасштабных цифровых вычислительных машин», организованном совместно Гарвардским университетом и Управлением артиллерийских вооружений ВМС США. Здесь он обсуждает последовательную и параллельную работу, предполагая
...конструкция машины не должна быть сложной. Поскольку все логические характеристики, необходимые для этой процедуры, доступны, можно разработать инструкцию кодирования для размещения подпрограмм в памяти в местах, известных машине, и таким образом, чтобы их можно было легко вызвать в использование.
Другими словами, можно обозначить подпрограмму A как деление, подпрограмму B как комплексное умножение и подпрограмму C как вычисление стандартной ошибки последовательности чисел и так далее по списку подпрограмм, необходимых для конкретной задачи. ... Все эти подпрограммы потом будут храниться в машине, и останется только сделать краткую ссылку на них по номеру, как они указаны в кодировке. [8]
Кей МакНалти тесно сотрудничала с Джоном Мочли в команде ENIAC и разработала идею подпрограмм для компьютера ENIAC , который она программировала во время Второй мировой войны. [15] Она и другие программисты ENIAC использовали подпрограммы для расчета траекторий ракет. [15]
Гольдстайн и фон Нейман написали статью от 16 августа 1948 года, в которой обсуждается использование подпрограмм. [16]
Некоторые очень ранние компьютеры и микропроцессоры, такие как IBM 1620 , Intel 4004 и Intel 8008 , а также микроконтроллеры PIC , имеют вызов подпрограммы с одной командой, который использует выделенный аппаратный стек для хранения адресов возврата — такое оборудование поддерживает только несколько уровней. вложенности подпрограмм, но может поддерживать рекурсивные подпрограммы. Машины до середины 1960-х годов, такие как UNIVAC I , PDP-1 и IBM 1130 , обычно используют соглашение о вызовах , при котором счетчик команд сохраняется в первой ячейке памяти вызываемой подпрограммы. Это допускает произвольно глубокие уровни вложенности подпрограмм, но не поддерживает рекурсивные подпрограммы. В IBM System/360 была инструкция вызова подпрограммы, которая помещала сохраненное значение счетчика команд в регистр общего назначения; это можно использовать для поддержки произвольно глубокой вложенности подпрограмм и рекурсивных подпрограмм. PDP -11 (1970 г.) - один из первых компьютеров с инструкцией вызова подпрограммы перемещения стека; эта функция также поддерживает как произвольно глубокую вложенность подпрограмм, так и рекурсивные подпрограммы. [17]
В самых ранних ассемблерах поддержка подпрограмм была ограничена. Подпрограммы не были явно отделены друг от друга или от основной программы, и действительно, исходный код подпрограммы мог перемежаться с кодом других подпрограмм. Некоторые ассемблеры предлагают предопределенные макросы для генерации последовательностей вызова и возврата. К 1960-м годам ассемблеры обычно имели гораздо более сложную поддержку как встроенных, так и отдельно собираемых подпрограмм, которые можно было связывать вместе.
Одним из первых языков программирования, поддерживающих написанные пользователем подпрограммы и функции, был FORTRAN II . Компилятор IBM FORTRAN II был выпущен в 1958 году. АЛГОЛ 58 и другие ранние языки программирования также поддерживали процедурное программирование.
Даже при таком громоздком подходе подпрограммы оказались очень полезными. Они позволили использовать один и тот же код во многих разных программах. Память была очень дефицитным ресурсом на ранних компьютерах, а подпрограммы позволяли значительно экономить размер программ.
Многие ранние компьютеры загружали инструкции программы в память с перфоленты . Затем каждая подпрограмма может быть представлена отдельным куском ленты, загруженным или смонтированным до или после основной программы (или «основной линии» [18] ); и одна и та же лента с подпрограммами может затем использоваться многими разными программами. Похожий подход использовался в компьютерах, загружавших программные инструкции с перфокарт . Название « библиотека подпрограмм» первоначально означало библиотеку в буквальном смысле, в которой хранились индексированные коллекции лент или колод карт для коллективного использования.
Чтобы устранить необходимость в самомодифицирующемся коде , разработчики компьютеров в конечном итоге предоставили инструкцию косвенного перехода , операнд которой, вместо того, чтобы быть самим адресом возврата , был местоположением переменной или регистра процессора, содержащего адрес возврата.
На этих компьютерах вместо изменения возврата функции вызывающая программа сохраняла адрес возврата в переменной, чтобы после завершения функции она выполняла косвенный переход, который направлял выполнение в место, заданное предопределенной переменной.
Еще одним достижением стала инструкция перехода к подпрограмме , которая сочетала сохранение адреса возврата с вызывающим переходом, тем самым значительно минимизируя накладные расходы .
В IBM System/360 , например, инструкции ветвления BAL или BALR, предназначенные для вызова процедур, сохраняли адрес возврата в регистре процессора, указанном в инструкции, по соглашению, регистре 14. Для возврата подпрограмме нужно было только выполнить инструкция косвенного ветвления (BR) через этот регистр. Если подпрограмме нужен этот регистр для какой-то другой цели (например, для вызова другой подпрограммы), она сохранит содержимое регистра в отдельной области памяти или в стеке регистров .
В таких системах, как HP 2100 , инструкция JSB выполняла аналогичную задачу, за исключением того, что адрес возврата сохранялся в ячейке памяти, которая была целью ветвления. Выполнение процедуры фактически начнется со следующей ячейки памяти. На языке ассемблера HP 2100 можно было бы написать, например
...JSB MYSUB (вызывает подпрограмму MYSUB.)BB ... (Вернусь сюда после завершения MYSUB.)для вызова подпрограммы MYSUB из основной программы. Подпрограмма будет закодирована как
MYSUB NOP (Хранилище обратного адреса MYSUB.)АА... (Начало тела MYSUB.)...JMP MYSUB,I (возврат в вызывающую программу.)Инструкция JSB поместила адрес инструкции NEXT (а именно, BB) в ячейку, указанную в качестве ее операнда (а именно, MYSUB), а затем после этого разветвилась к ячейке NEXT (а именно, AA = MYSUB + 1). Затем подпрограмма может вернуться в основную программу, выполнив непрямой переход JMP MYSUB, I, который перейдет к ячейке, хранящейся в ячейке MYSUB.
Компиляторы для Фортрана и других языков могут легко использовать эти инструкции, если они доступны. Этот подход поддерживал несколько уровней вызовов; однако, поскольку адресу возврата, параметрам и возвращаемым значениям подпрограммы были назначены фиксированные ячейки памяти, рекурсивные вызовы не допускались.
Кстати, аналогичный метод использовался Lotus 1-2-3 в начале 1980-х годов для обнаружения зависимостей пересчета в электронной таблице. А именно, в каждой ячейке было зарезервировано место для хранения обратного адреса. Поскольку циклические ссылки не допускаются для естественного порядка пересчета, это позволяет обход дерева без резервирования места для стека в памяти, что было очень ограничено на небольших компьютерах, таких как IBM PC .
Большинство современных реализаций вызова функции используют стек вызовов , особый случай структуры данных стека , для реализации вызовов функций и возвратов. Каждый вызов процедуры создает новую запись, называемую кадром стека , наверху стека; когда процедура завершает работу, ее кадр стека удаляется из стека, и его пространство может использоваться для вызовов других процедур. Каждый кадр стека содержит личные данные соответствующего вызова, которые обычно включают параметры процедуры и внутренние переменные, а также адрес возврата.
Последовательность вызовов может быть реализована с помощью последовательности обычных инструкций (подход, который до сих пор используется в архитектурах вычислений с сокращенным набором команд (RISC) и очень длинным командным словом (VLIW)), но многие традиционные машины, разработанные с конца 1960-х годов, включают специальные инструкции для эта цель.
Стек вызовов обычно реализуется как непрерывная область памяти. Это произвольный выбор конструкции, является ли нижняя часть стека самым низким или самым высоким адресом в этой области, так что стек может расти в памяти вперед или назад; однако многие архитектуры выбрали последнее. [ нужна цитата ]
В некоторых проектах, особенно в некоторых реализациях Форта , использовались два отдельных стека: один в основном для управляющей информации (например, адреса возврата и счетчики циклов), а другой — для данных. Первый представлял собой стек вызовов или работал как стек вызовов и был доступен программисту лишь косвенно через другие языковые конструкции, тогда как второй был доступен более напрямую.
Когда впервые были представлены вызовы процедур на основе стека, важной мотивацией была экономия драгоценной памяти. [ нужна цитация ] При такой схеме компилятору не нужно резервировать отдельное пространство в памяти для личных данных (параметров, адреса возврата и локальных переменных) каждой процедуры. В любой момент стек содержит только частные данные активных в данный момент вызовов (а именно тех, которые были вызваны, но еще не вернулись). Из-за того, как программы обычно собирались из библиотек, нередко можно было найти программы, включающие в себя тысячи функций, из которых в любой момент времени активны лишь несколько. [ нужна цитация ] Для таких программ механизм стека вызовов может сэкономить значительные объемы памяти. Действительно, механизм стека вызовов можно рассматривать как самый ранний и простой метод автоматического управления памятью .
Однако еще одним преимуществом метода стека вызовов является то, что он допускает рекурсивные вызовы функций , поскольку каждый вложенный вызов одной и той же процедуры получает отдельный экземпляр ее личных данных.
В многопоточной среде обычно имеется более одного стека. [19] Среда, которая полностью поддерживает сопрограммы или отложенные вычисления, может использовать структуры данных, отличные от стеков, для хранения записей активации.
Одним из недостатков механизма стека вызовов является увеличение стоимости вызова процедуры и ее соответствующего возврата. [ необходимы пояснения ] Дополнительные затраты включают в себя увеличение и уменьшение указателя стека (а в некоторых архитектурах проверку на переполнение стека ) и доступ к локальным переменным и параметрам по адресам, относящимся к кадру, а не по абсолютным адресам. Затраты могут быть реализованы в увеличении времени выполнения или увеличении сложности процессора, или в том и другом.
Эти накладные расходы наиболее очевидны и нежелательны в конечных процедурах или конечных функциях , которые возвращаются без выполнения каких-либо вызовов процедур. [20] [21] [22] Чтобы уменьшить эти накладные расходы, многие современные компиляторы пытаются отложить использование стека вызовов до тех пор, пока он действительно не понадобится. [ нужна цитация ] Например, вызов процедуры P может сохранять адрес возврата и параметры вызываемой процедуры в определенных регистрах процессора и передавать управление телу процедуры простым переходом. Если процедура P возвращается без каких-либо других вызовов, стек вызовов вообще не используется. Если P необходимо вызвать другую процедуру Q , он будет использовать стек вызовов для сохранения содержимого любых регистров (например, адреса возврата), которые понадобятся после возврата Q.
В C все вызываемые модули называются функциями.
В C++ вызываемая единица называется функцией-членом или методом , если она связана с классом , или свободной функцией [23] , если нет.
Определение функции начинается с имени типа значения, которое она возвращает, или voidс указания того, что она не возвращает значение.
void doSomething () { /* некоторый код */ } Эта функция не возвращает значение и всегда называется автономной, напримерdoSomething()
int GiveMeFive () { возвращение 5 ; } Эта функция возвращает целочисленное значение 5. Вызов может быть автономным или в виде выражения типаy = x + giveMeFive()
void addTwo ( int * pi ) { * pi += 2 ; } Эта функция имеет побочный эффект — изменяет значение, передаваемое по адресу, на входное значение плюс 2. Ее можно вызывать для переменной, vнапример addTwo(&v), когда амперсанд (&) сообщает компилятору передать адрес переменной. Если перед вызовом v равно 5, после вызова оно будет равно 7.
void addTwo ( int & я ) { я += 2 ; } Для этой функции требуется C++ — она не будет компилироваться как C. Она ведет себя так же, как предыдущий пример, но передает фактический параметр по ссылке, а не передает его адрес. Такой вызов addTwo(v)не включает амперсанд, поскольку компилятор обрабатывает передачу по ссылке без синтаксиса в вызове.
Ранние варианты BASIC требуют, чтобы каждая строка имела уникальный номер, не обеспечивали разделения вызываемого кода, не имели механизма передачи аргументов или возврата значения, а все переменные были глобальными. Он предоставляет команду GOSUB, где sub означает подпрограмму или подпрограмму . Управление переходит к указанному номеру строки, а затем при возврате переходит к следующей строке.
10 REM A BASIC PROGRAM 20 GOSUB 100 30 GOTO 20 100 ВВОД « ДАЙТЕ МНЕ НОМЕР » ; N 110 ПЕЧАТЬ « КВАДРАТНЫЙ КОРЕНЬ » ; _ _ Н ; 120 ПЕЧАТЬ « Есть » ; SQRT ( Н ) 130 ВОЗВРАТ Этот код неоднократно просит пользователя ввести число и сообщает квадратный корень из значения. Строки 100-130 являются вызываемыми.
Sub SayHello TextWindow . WriteLine ( «Привет!» ) End Sub Ключевое Subслово обозначает начало определения подпрограммы, за которым следует идентификатор имени. Последующие строки представляют собой тело, которое заканчивается ключевым EndSubсловом. Его можно назвать так SayHello().[24]
В Visual Basic 6 (не .NET) термин процедура используется для обозначения концепции подпрограммы. В коде Subиспользуется для возврата значения и Functionдля возврата значения. При использовании в контексте класса процедура является методом.
Каждый параметр имеет тип , который, если не указан, по умолчанию имеет значение вариант .
Поддерживаются следующие соглашения о передаче параметров:
ByVal) — передает копию фактического параметра, которая не позволяет процедуре изменить его.ByRef) – передает ссылку на фактический параметр, что позволяет процедуре изменять значение фактического параметра.Если не указан параметр by-ref, аргумент передается по параметру val. Поэтому by-val редко указывается явно.
Для простого типа, такого как число, эти соглашения относительно ясны. Передача by-ref позволяет процедуре изменять переданную переменную, тогда как передача by-val этого не делает. Для объекта семантика более сложна, поскольку объект всегда рассматривается как ссылка. Передача объекта по значению означает передачу ссылки по значению. Вызванная процедура может изменять состояние объекта с помощью своих методов, но не может изменять ссылку на объект фактического параметра.
Sub DoSomething () 'Здесь некоторый код End Sub Не возвращает значение и его следует называть автономным, напримерDoSomething
Функция GiveMeFive () как целое число GiveMeFive = 5 Конечная функция Это возвращает значение 5, и вызов может быть частью выражения, напримерy = x + GiveMeFive()
Sub AddTwo ( ByRef intValue as Integer ) intValue = intValue + 2 End Sub Это имеет побочный эффект — изменяет переменную, передаваемую по ссылке, и ее можно вызывать для переменной vтипа AddTwo(v). Если перед вызовом v равно 5, после вызова оно будет равно 7.
В PL/I вызываемой процедуре может быть передан дескриптор , предоставляющий информацию об аргументе, например длину строки и границы массива. Это позволяет сделать процедуру более общей и устраняет необходимость передачи такой информации программисту. По умолчанию PL/I передает аргументы по ссылке. (Тривиальная) функция изменения знака каждого элемента двумерного массива может выглядеть так:
Change_sign: процедура (массив); объявить массив(*,*) с плавающей запятой; массив = -массив;конец изменения_знака;
Это можно вызвать с различными массивами следующим образом:
/* первый массив ограничен от -5 до +10 и от 3 до 9 */объявить массив1 (-5:10, 3:9)float;/* второй массив ограничен значениями от 1 до 16 и от 1 до 16 */объявить массив2 (16,16) с плавающей запятой;вызов Change_sign(массив1);вызовите Change_sign(массив2);
В Python ключевое слово defобозначает начало определения функции. Операторы функции (тело) следуют в одной строке или с отступом в последующих строках. [25] Следующая функция возвращает текст приветствия, включающий имя, переданное вызывающим абонентом.
def format_greeting ( имя ): вернуть «Добро пожаловать» + имя def Say_hello_martin (): печать ( format_greeting ( «Мартин» ))При вызове say_hello_martin()на консоль пишет «Добро пожаловать, Мартин».
Подпрограмма может счесть полезным использовать определенный объем рабочего пространства; то есть память , используемая во время выполнения этой подпрограммы для хранения промежуточных результатов. Переменные, хранящиеся в этом рабочем пространстве, называются локальными переменными , а рабочее пространство называется записью активации . Запись активации обычно имеет обратный адрес , который сообщает, куда передать управление обратно после завершения подпрограммы.
Подпрограмма может иметь любое количество и характер точек вызова. Если рекурсия поддерживается, подпрограмма может даже вызвать саму себя, что приведет к приостановке ее выполнения на время выполнения другого вложенного выполнения той же подпрограммы. Рекурсия — полезный способ упростить некоторые сложные алгоритмы и решить сложные проблемы. Рекурсивные языки обычно предоставляют новую копию локальных переменных при каждом вызове. Если программист желает, чтобы значения локальных переменных оставались неизменными между вызовами, их можно объявить статическими на некоторых языках или можно использовать глобальные значения или общие области. Вот пример рекурсивной функции на C/C++ для поиска чисел Фибоначчи :
int Fib ( int n ) { if ( n <= 1 ) { return n ; } вернуть Фиб ( n - 1 ) + Фиб ( n - 2 ); } Ранние языки, такие как Фортран, изначально не поддерживали рекурсию, поскольку переменные и расположение адреса возврата выделялись статически. [26] Ранние компьютерные наборы команд затрудняли хранение адресов возврата и переменных в стеке. Машины с индексными регистрами или регистрами общего назначения , например, серии CDC 6000 , PDP-6 , GE 635 , System/360 , серии UNIVAC 1100 , могут использовать один из этих регистров в качестве указателя стека .
Современные языки после ALGOL , такие как PL/I и C, почти всегда используют стек, обычно поддерживаемый большинством современных компьютерных наборов команд, для обеспечения новой записи активации для каждого выполнения подпрограммы. Таким образом, вложенное выполнение может свободно изменять свои локальные переменные, не беспокоясь о влиянии на другие приостановленные выполнения. По мере накопления вложенных вызовов формируется структура стека вызовов , состоящая из одной записи активации для каждой приостановленной подпрограммы. Фактически, эта структура стека практически повсеместно распространена, поэтому записи активации обычно называются кадрами стека .
Некоторые языки, такие как Pascal , PL/I и Ada , также поддерживают вложенные функции , которые можно вызывать только в пределах внешней (родительской) функции. Внутренние функции имеют доступ к локальным переменным внешней функции, которая их вызвала. Это достигается за счет хранения дополнительной контекстной информации в записи активации, также называемой отображением .
Если подпрограмма может быть выполнена правильно, даже когда другое выполнение той же подпрограммы уже выполняется, такая подпрограмма называется реентерабельной . Рекурсивная подпрограмма должна быть реентерабельной. Реентерабельные подпрограммы также полезны в многопоточных ситуациях, поскольку несколько потоков могут вызывать одну и ту же подпрограмму, не опасаясь вмешательства друг друга. В системе обработки транзакций IBM CICS квазиреентерабельность была несколько менее строгим, но аналогичным требованием для прикладных программ, совместно используемых многими потоками.
В строго типизированных языках иногда желательно иметь несколько функций с одинаковым именем, но работающих с разными типами данных или с разными профилями параметров. Например, можно определить функцию извлечения квадратного корня для работы с вещественными числами, комплексными значениями или матрицами. Алгоритм, который будет использоваться в каждом случае, различен, и возвращаемый результат может быть разным. Написав три отдельные функции с одинаковым именем, программисту не нужно запоминать разные имена для каждого типа данных. Кроме того, если для вещественных чисел можно определить подтип, чтобы разделить положительные и отрицательные действительные числа, для действительных чисел можно написать две функции: одну для возврата вещественного числа, когда параметр положителен, а другую для возврата комплексного значения, когда параметр равен отрицательный.
В объектно-ориентированном программировании , когда ряд функций с одинаковым именем может принимать разные профили параметров или параметры разных типов, каждая из функций называется перегруженной .
Вот пример перегрузки функции в C++ , демонстрирующий реализацию двух функций с одинаковым именем (Area), но разными параметрами:
#include <iostream> двойная площадь ( двойной ч , двойной ш ) { возвращение ч * ш ; } /* Первая функция Area предназначена для определения площади прямоугольника, * поэтому она принимает в качестве параметров два числа: высоту и ширину. */ двойная площадь ( double r ) { return r * r * 3,14 ; } /* Вторая функция Area предназначена для определения площади круга, * поэтому она принимает в качестве параметра только одно число — радиус. */ int main () { двойной прямоугольник_область = Площадь ( 3 , 4 ); // Это вызывает первую функцию Area, поскольку предоставлены два параметра. двойной круг_площадь = Площадь ( 5 ); // Это вызывает вторую функцию Area, поскольку предоставляется только один параметр. std :: cout << "Площадь прямоугольника равна" << right_area << std :: endl ; std :: cout << "Площадь круга равна " << Circle_area << std :: endl ; } Другой пример: функция может создать объект , который будет принимать указания, и отслеживать его путь к этим точкам на экране. Конструктору можно передать множество параметров (цвет трассировки, начальные координаты x и y, скорость трассировки). Если программист хотел, чтобы конструктор мог принимать только параметр цвета, он мог бы вызвать другой конструктор, который принимает только цвет, который, в свою очередь, вызывает конструктор со всеми параметрами, передавая набор значений по умолчанию для всех остальных параметров ( X и Y обычно располагаются по центру экрана или в начале координат, а для скорости устанавливается другое значение по выбору кодировщика).
PL/I имеет GENERICатрибут для определения общего имени для набора ссылок на записи, вызываемых с различными типами аргументов. Пример:
ОБЪЯВИТЬ имя_гена GENERIC( имя КОГДА(ФИКСИРОВАННЫЙ ДВОИЧНЫЙ), пламя КОГДА(FLOAT), путь ИНАЧЕ );
Для каждой записи можно указать несколько определений аргументов. Вызов «gen_name» приведет к вызову «name», когда аргумент FIXED BINARY, «flame», когда FLOAT и т. д. Если аргумент не соответствует ни одному из вариантов, будет вызван «pathname».
Замыкание — это подпрограмма со значениями некоторых ее переменных, полученными из среды, в которой она была создана . Замыкания были примечательной особенностью языка программирования Лисп, представленного Джоном Маккарти . В зависимости от реализации замыкания могут служить механизмом побочных эффектов.
Было разработано большое количество соглашений по кодированию функций. Что касается именования, многие разработчики приняли подход, согласно которому имя функции должно быть глаголом, когда она выполняет определенную задачу, прилагательным , когда она выполняет какой-либо запрос, и существительным , когда она используется для замены переменных.
Некоторые программисты предлагают, чтобы функция выполняла только одну задачу, а если функция выполняет более одной задачи, ее следует разделить на несколько функций. Они утверждают, что функции являются ключевыми компонентами обслуживания кода , и их роли в программе должны оставаться разными.
Сторонники модульного программирования (модуляризации кода) выступают за то, чтобы каждая функция имела минимальную зависимость от других частей кода. Например, сторонники этой точки зрения обычно считают использование глобальных переменных неразумным, поскольку оно усиливает тесную связь между функцией и этими глобальными переменными. Если такое связывание не является необходимым, они советуют провести рефакторинг функций, чтобы они принимали переданные параметры . Однако увеличение количества параметров, передаваемых функциям, может повлиять на читаемость кода.
Помимо основного или обычного эффекта, подпрограмме может потребоваться информировать вызывающую программу об исключительных условиях, которые могли возникнуть во время ее выполнения. В некоторых языках и стандартах программирования это часто делается с помощью кода возврата — целочисленного значения, помещаемого подпрограммой в какое-то стандартное место, которое кодирует нормальные и исключительные условия.
В IBM System/360 , где от подпрограммы ожидался код возврата, возвращаемое значение часто проектировалось так, чтобы оно было кратно 4, чтобы его можно было использовать в качестве прямого индекса таблицы перехода в таблицу перехода, часто расположенную сразу после вызвать инструкцию, чтобы избежать дополнительных условных проверок, что еще больше повышает эффективность. На языке ассемблера System/360 можно было бы написать, например:
BAL 14, SUBRTN01 перейти к подпрограмме, сохраняющей адрес возврата в R14. B TABLE(15) использует возвращаемое значение в регистре 15 для индексации таблицы ветвей,* переход на соответствующую ветку инстр.ТАБЛИЦА Б. Код возврата ОК =00 ХОРОШО } B BAD код возврата =04 Неверный ввод } Таблица ответвлений B Код возврата ОШИБКА =08 Непредвиденное состояние }При вызове функции возникают значительные накладные расходы во время выполнения, включая передачу аргументов, переход к подпрограмме и обратный переход к вызывающей программе. Накладные расходы часто включают сохранение и восстановление определенных регистров процессора, выделение и освобождение памяти для кадров вызова и т. д. [ необходим пример ] В некоторых языках каждый вызов функции также подразумевает автоматическое тестирование кода возврата функции или обработку исключений , которые она может вызвать. . Значительным источником накладных расходов в объектно-ориентированных языках является интенсивно используемая динамическая диспетчеризация вызовов методов.
Существуют некоторые, казалось бы, очевидные оптимизации вызовов процедур, которые нельзя применять, если процедуры могут иметь побочные эффекты. Например, в выражении (f(x)-1)/(f(x)+1)функцию fнеобходимо вызвать дважды, поскольку два вызова могут возвращать разные результаты. Более того, в тех немногих языках, которые определяют порядок вычисления операндов оператора деления, значение xдолжно быть получено снова перед вторым вызовом, поскольку первый вызов мог его изменить. Определить, может ли подпрограмма иметь побочный эффект, очень сложно (действительно, неразрешимо в силу теоремы Райса ). Таким образом, хотя подобные оптимизации безопасны в чисто функциональных языках программирования, компиляторам типичного императивного программирования обычно приходится предполагать худшее.
Метод, используемый для устранения этих накладных расходов, - это встроенное расширение или встраивание тела подпрограммы в каждый сайт вызова (вместо ветвления к функции и обратно). Это не только позволяет избежать накладных расходов на вызов, но также позволяет компилятору более эффективно оптимизировать тело процедуры , принимая во внимание контекст и аргументы при этом вызове . Вставленное тело может быть оптимизировано компилятором. Однако встраивание обычно увеличивает размер кода, если только программа не содержит только один вызов функции.
Мы могли бы предоставить нашему сборщику копии исходного кода для всех наших полезных подпрограмм, а затем, предоставляя ему основную программу для сборки, сказать ему, какие подпрограммы будут вызываться в основной [...]