учебники, программирование, основы, введение в,

 

Управление подпрограммами

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

  • сегмент кода, содержащий выполняемый код и константы;
  • сегмент данных, называемый также записью активации, содержащей локальные переменные и параметры.

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

  • CIP-указатель (current instruction pointer) является указателем текущей команды сегмента кода;
  • CEP-указатель (current environment pointer) является указателем текущей записи активации. CEP-указатель иногда также называется указателем текущей среды, так как определяет среду всех объектов данных, используемых подпрограммой.

При выполнении программы интерпретатор выбирает команду по CIP-указателю, увеличивает значение этого указателя и выполняет выбранную команду. Если при выполнении команды был выполнен безусловный переход или вызов подпрограммы, то значение CIP-указателя опять изменяется. Значение переменной, используемой в подпрограмме, определяется по CEP-указателю, идентифицирующему конкретную запись активации.
Последовательный вызов подпрограмм
Запись активации для главной программы создается или перед началом выполнения программы или в процессе трансляции одновременно с формированием сегмента кода.
Перед переходом на подпрограмму текущие значения CIP- и CEP-указателей сохраняются. Выполнение программы начинается с присваивания CEP-указателю адреса записи активации, а CIP-указателю - ссылки на первую команду сегмента кода главной программы. При каждом вызове подпрограммы создается новая запись активации этой подпрограммы, и значение CEP-указателя устанавливается на эту запись активации, а значение CIP-указателя - на первую команду фрагмента кода подпрограммы.
При возврате из подпрограммы восстанавливаются сохраненные значения CIP- и CEP-указателей и удаляется запись активации.
Место сохранения значений CIP-указателя и CEP-указателя иногда называют точкой возврата. Точка возврата представляет собой системный объект, сохраняемый, как правило, в записи активации.
При последовательном вызове подпрограммы (реализуемом иногда как копирование подпрограммы) в процессе выполнения может создаваться множество записей активации подпрограммы, но в каждый отдельный момент времени хранится и используется только одна запись активации, т.е. перед созданием новой записи активации прежняя запись активации должна быть удалена.
Иногда в реализациях для достижения наибольшего быстродействия жертвуют некоторым количеством требуемой памяти: место под запись активации выделяется статически при компиляции (в фрагменте кода) и при каждом вызове происходит только повторная инициализация записи активации. В этом случае никакая подпрограмма не может одновременно иметь более одной записи активации, что значительно сужает возможности программиста. Такая модель выполнения присуща большинству трансляторов языка FORTRAN.
Для аппаратной реализации вызова подпрограммы с заранее фиксированной записью активации достаточно только CIP-указателя, сохраняемого командой перехода с возвратом.
Если место для записи активации должно выделяться динамически, то это, как правило, реализуется с помощью стека.
Стек создается в свободной области памяти. При вызове подпрограммы созданная запись активации помещается в стек. При этом значение указателя стека увеличивается с учетом размера выделяемого пространства. При удалении записи активации значение указателя стека уменьшается с учетом освобождаемого пространства. Выделение и освобождение памяти в стеке происходит с одного конца и фиксируется указателем стека.
Такая реализация позволяет создавать для одной подпрограммы несколько записей активации, которые будут последовательно заноситься в стек.
На представлена организация памяти, используемая при выполнении программы на языке С.
Вся память программы делится на статическую, определяемую при трансляции, и динамическую, содержание которой формируется в процессе выполнения. Стек располагается в динамической области памяти.
Также в динамической области памяти располагается куча, пространство которой используется под динамически создаваемые объекты.

http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gifРекурсивный вызов подпрограмм

Применение стека для хранения записей активации позволяет реализовывать не только последовательный вызов подпрограмм, но и рекурсивный вызов.
Рекурсивным вызовом подпрограммы называется вызов подпрограммы из самой себя. При n вызовах подпрограммы A в стек будет последовательно добавлено n записей активации этой подпрограммы. Последний вызов подпрограммы A будет завершен первым, и его запись активации будет первой удалена из стека.
Примером использования рекурсии может служить программа вычисления факториала n! =(n*(n-1)!), 0!=1.
Пример подпрограммы на языке С:
int factoria(int n)
{ if (n) return n* factoria(n-1);
else return 1;
}
В некоторых случаях без применения рекурсии задачу решить практически невозможно. Хорошо известен пример программирования алгоритма ханойских башен. Условия задачи состоят в следующем: есть три башни, первая башня состоит из колец, диаметр которых увеличивается сверху вниз. Задача заключается в программировании алгоритма, обеспечивающего перемещение колец с первой башни на вторую по одному с возможным использованием вспомогательной третьей башни таким образом, чтобы все кольца оказались на второй башне и их диаметр увеличивается сверху вниз. Алгоритм решения этой задачи посредством рекурсии состоит в предположении, что эта задача решена для n-1 кольца. Тогда, если при n=1 решение задачи очевидно, то есть решение и для n колец.
Пример подпрограммы на языке С++, реализующей алгоритм ханойских башен:

#include "stdafx.h"
#include <iostream>
void tower_3(int n, int m, int k);
int main(int argc, _TCHAR* argv[])
{      
tower_3 (3,1,3);
return 0;
}

void tower_3(int n, int m, int k){
/* n - число перемещаемых колец
m - башня, с которой выполняется
перемещение
k - башня, на которую выполняется
перемещение                  */

if (n==1) {
//Последнее очевидное перемещение
return ;}

tower_3(n-1,m,6-m-k);
/* 6-m-k определяет номер вспомогательной
башни, m - номер башни, с которой
выполняется перемещение */

std::cout<<" from "<< m << " to "<< k <<
" n= "<<n-1<<std::endl;
tower_3(n-1,6-m-k,k);
/* 6-m-k- номер башни, с которой
выполняется перемещение */
}
На приведен пример выполнения алгоритма ханойских башен для трех колец (n указывает количество перекладываемых колец).
Одним из первых языков программирования, допускавших рекурсию, являлся ALGOL 60. Раньше принципы реализации записей активации трансляторами языка FORTRAN не позволяли применять рекурсию, но последняя версия компилятора языка FORTRAN 90 это допускает.
Подпрограммы A и B называются взаимно рекурсивными, если подпрограмма A вызывает B, а подпрограмма B вызывает A.
Языки программирования, для которых традиционно используются однопроходные компиляторы, для реализации взаимной рекурсии должны вводить предварительное определение подпрограммы. Это объясняется тем, что при взаимно рекурсивном вызове подпрограмм A и B, в момент вызова B из A подпрограмма B должна быть уже определена, а в момент вызова A из B подпрограмма A должна быть определена. Такой механизм используется в языках Pascal и Ada.
Язык Pascal не требует указания сигнатуры функции или процедуры в том случае, если ее определение расположено в коде программы до ее вызова. В противном случае используется предварительное определение, указываемое ключевым словом forward.
На приведен код модуля на языке Pascal (созданного в среде Delphi), иллюстрирующий предварительное объявление функции A.
Следует отметить, что компиляция программ, удовлетворяющих стандарту языка программирования, различными трансляторами может создавать различный выполнимый код. При этом очень часто компиляторы несколько "расширяют" диапазон возможностей, предоставляемых стандартом языка программирования. Такая ситуация будет приводить к ограничению использования "расширенного" синтаксиса программы с другими компиляторами.
http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gif

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика