Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 106
Текст из файла (страница 106)
Каждая новая процедура требует добавления к стеку нового блока памяти, содержащего локальные переменные для этой процедуры; выход из этой прог! едуры сопровождается изъятием этого блока из стека. В данной главе мы займемся изучением атой модели. Тем не менее необходим более развитый динамический механизм управления памятью. В языках С (с помощью функции па11ос), С++, Дача и Рааса! (при помощи функции пеи) н неяв1<о в таких языках, как МЕ и 11БР программа может произвольным образом отводить в памяти место для новых объектов данных. Во всех таких случаях нужно использовать кучу, которая динамически выделяет в произвольном порядке блоки памяти и освобождает их по требованию.
Организацию кучи мы обсудим более подробно в главе 10. 9.1. Управление последовательностью подпрограмм Каким образом одна подпрограмма вызывает другую и затем позволяет вернуться из вызванной подпрограммы в исходную? Простая структура, состоящая из операторов са11 и гетогп, является общей почти для всех языков программирования и представляет обычный стандартный механизм для достижения указанной цели. Простой вызов и возвратив подпрограммы.
В программировании мы привыкли рассматривать программы как некие иерархические структуры. Программа состоит из единственной главной программы, которая во время выполнения может вызывать различные подпрограммы, а те, в свою очередь, могут вызывать подпод- 9.1. Управление последовательностью подпрограмм 385 программы и так далее до любого уровня глубины вложенности. Предполагается, что каждая подпрограмма в какой-то момент прекращает свое выполнение и возвращает управление той программе, которая ее вызвала. Во время выполнения подпрограммы выполнение вызывающей подпрограммы временно приостанавливается. Когда выполнение полпрограммы завершается, выполнение вызывающей программы возобновляется с той точки, которая непосредственно следует за точкой вызова подпрограммы. Такая структура управления часто объясняется правилом копирования: выполнение оператора сэ11, вызывающего подпрограмму, имеет тот же аффект, что и замена этого оператора на копию тела вызываемой подпрограммы (с соответствующими подстановками для параметров и разрешением возможных конфликтов, связанных с совпадением идентификаторов) перед выполнением программы.
С этой точки зрения подпрограмму можно рассматривать как структуру управления, которая позволяет избежать копирования большого количества идентичных или почти идентичных операторов, встречающихся в нескольких местах программы. Прежде чем рассматривать реализацию простой структуры вызова-возврата, используемой для представления подпрограмм на основе правияа копирования, следует обсудить вкратце некоторые неявные предположения, присутствующие в таком представлении, отказ от которых позволяет прийти к более общим структурам управления подпрограммами.
1. Подпрограммы не могут быть рекурсивными. Программа называется прямо рекурсивной, если в ней содержится обращение к самой себе (то есть подпрограмма В содержит оператор са11 В); косвенно рекурсивная подпрограмма содержит обращение к подпрограмме, которая, в свою очередь, вызывает первую подпрограмму или инициирует цепь вызовов подпрограмм, которая в конце концов возвращает к исходной подпрограмме. В случае, когда вызываемая подпрограмма является простой нерекурсивлой подпрограммой, мы можем применить правило копирования во время трансляции, заменив вызовы этой подпрограммы на копии ее тела, и, таким образом, полностью исключить необходимость использования этой отдельной подпрограммы (в принципе, но не на практике). Но если подпрограмма является прямо рекурсивной, то это невозможно даже в принципе, поскольку подстановка вместо оператора вызова тела подпрограммы будет, очевидно, бесконечной.
Каждая подстановка, удаляющая оператор вызова, вводит новый вызов той же самой подпрограммы, для которого необходима новая подстановка и т, д, Косвенная рекурсия, возможно, позволит удалить неко- 1 тор гяе подпрограммы, но в конце концов должна привести к тому, что другие подпрограммы станут прямо рекурсивными. Тем не менее многие алгоритмы являются рекурсивными и, естественно, приводят к структурам рекурсивных подпрограмм, 2. Требуется явное обращение к подпрограмме с помощью оператора сэ11. Для того чтобы можно было применить правило копирования, каждая точка вызова подпрограммы должна быть явным образом указана в транслируемой программе. Для подпрограммы, используемой в качестве обработчика исключений, может и не существовать явный оператор вызова. 386 Глава 9.
Управление подпрограммами 3. Подпрограммьс должны полностью выполняться при каждан вьсзовв. В правиле копирования неявно предполагается, что подпрограмма выполняется с самого начала и до своего логического конца каждый раз, когда она вызывается. Если она вызывается во второй раз, то ее выполнение начинается заново и опять выполняется до своего логического конца вплоть до возвращения управления в вызывающую программу. Подпрограмма, которая используется как сопрограмма, продолжает выполнение с точки ее последнего завершения всякий раз, когда оиа вызывается. 4.
Нв свдленная передача управления в точку вызова. Явный оператор вызова подпрограммы сзН указывает, что управление должно быть передано непосредственно этой подпрограмме в точке вызова, и, таким образом, копирование тела подпрограммы в вызывающую программу имеет тот же самый аффект. Для вьаова подпрограмм по графику выполнение подпрограммы может быть отложено до некоторого более позднего момента времени. 5. Единая последовательность выполнения. В любой точке во время выполнения иерархии подпрограмм только одна подпрограмма имеет управление.
Выполнение продолжается в одной последовательности от вызывающей программы к вызываемой подпрограмме и назад к вызывающей программе, Если в какой-либо точке мы остановим выполнение, мы всегда сможем определить, которая подпрограмма в данный момент выполняется (то есть имеет управление), а также указать множество других подпрограмм, выполнение которых временно было приостановлено (вызывающая программа, вызывающая ее программа и т, д.), и оставшиеся, которые или никогда не вызывались, или полностью были выполнены. Подпрограммы, используемые как задачи, могут выполняться одновременно, так что несколько подпрограмм могут выполняться в одно и то же время. Из тех языков, которые мы обсуждаем в данной книге, только ЕОКТКЛс с непосредственно основан на представлении подпрограмм с помощью правила копирования.
В других языках используются более гибкие структуры управления. 9.1.1. Простые подпрограммы вызов-возврат Заметим, что в данной главе мы уделяем особое внимание структурам управления последовательностью действий (то есть механизмам передачи управления от одних программ и полпрограмм другим). С каждой из этих структур тесно связаны вопросы управления данными: передача параметров, глобальные и локальные переменные и т. д, Эти темы отдельно обсуждаются в следующем разделе, а здесь мы полностью сосредоточим наше внимание на механизмах передачи управления. Например, даже в случае простой подпрограммы (без передачи параметров) вызов может происходить в двух формах: как вызов фусскт(ии (для подпрограмм, которые в результате своего выполнения непосредственно возвращают некоторые значения) и как вызов процедуры или подпрограммы (для подпрограмм, результат действия которых выражается в побочном воздействии на общие данные).
Реализация. Для понимания реализации простой структуры управления вызов-возврат следует построить более полную модель того, что мы понимаем под 9.1. Управление последовательностью подпрограмм 387 вгвпвлнепием программы. Мы рассматриваем выражения и последовательности операторов как блоки выполняемого кода, Выполнение выражения или последовательности опсраторов означает просто выполнение кода с использованием аппаратно- или программно-моделируемого интерпретатора, как сказано в главе 2, Для выполнения подпрограмм требуется нечто большее: 1.
Сушествует отличие между определением подпрограммы и активацией подпрограммы. Опрелеление — зто то, что мы видим в тексте программы и что при трансляции превращается в шаблон подпрограммы. Активация создается при каждом вызове полпрограммы с помощью шаблона, созданного на основе определения подпрограммы при трансляции.
2. Активация реализуется в ниде лвух частеи: сегмента кода, куда входит выполняемый код и константы, и записи активации, солержашей локальные данные, параметры и различные другие объекты данных. 3. Сегмент кода нв изменяется в процессе выполнения программы. Он создается транслятором и статически хранится в памяти. Он используется во время выполнения программы, но никогда не изменяется. Каждая активация данной подпрограммы использует один и тот же сегмент кода. 4. Запись активации создается заново каждый раз, когда вызывается подпрограмма, а по завершении подпрограммы запись активации разрушается.
Во время выполнения подпрограммы содержимое записи активации постоянно меняется по мере того, как локальным переменным и другим объектам данных присваиваются новые значения. Чтобы избежать путаницы, следует говорить не о «выполнении конкретного оператора Б в подпрограмме», а о «выполнении оператора ь во время активации Р данной подпрограммы». Таким образом, чтобы отслеживать процесс выполнения программы, требуются два параметра, которые мы рассматриваем как два указателя, определяемых системой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
