Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 108
Текст из файла (страница 108)
Но для приведенной здесь упрощенной модели можно использовать часто предоставляемую аппаратурой команду перехода с возвратом лля реализации вызова подпрограммы с помощью одной команды процессора. Указатель 91Р в такой пашей модели представляется непосредственно с помощью аппаратного регистра адресов программы (см. главу 2). Команда перехода с возвратом сохраняет содержимое этого адресного регистра в некоторой области памяти или регистре (часто зта область памяти непосредственно предшествует той области, которой передается управление) и присваивает ссылку на указанную в ией область памяти в качестве нового значения адресного регистра (таким образом осуществляя передачу управления той команде, которая расположена в этой области памяти).
В результате получается именно то, чего мы хотели: старое значение Е1Р сохранено, а его новым значением является адрес первой команды кода вызываемой подпрограммы. Возвращение из подпрограммы тоже, как правило, можно реализовать в виде одной аппаратной команды: сохраненное значение Е1Р снова присваивается адресному регистру (зто делает аппаратная команда перехода).
В результате мы получаем простую реализациго вызова подпрограммы и возврата из нее, правда, за это приходится расплачиваться увеличением используемого объема памяти, так как требуется заранее разместить в памяти записи активации для каждой подпрограммы. Пример такой структуры приведен па рис. 9.2. 9.1. Управление последовательностью подпрограмм 391 Главная программа ПодпРограмма А Подпрограмма В Возврат П: Константы !4 Локальные переменные и т. д, точка возврата из подпрограммы Рис. 9.2.
Структура вызова-возврата из подпрограммы Стековая реализация Самылг простым способом управления памятью для обработки структуры записей активации во время выполнения программы является стек. Свободная на начало выполнения программы память рассматривается как один последовательный блок в памяти.
Когда в атом возникает необходимость, память выделяется из последовательности областей в этом стековом блоке, начиная с какого-то одного конца. Освобождается память в этом блоке в порядке, обратном его заполнению, так что освобождаемый блок памяти всегда расположен в вершине стека, Для управления ресурсами памяти в таком сте коном блоке требуется всего лишь один сгпеховый укаватель. Стековый указатель всегда указывает на вершину стека, следующее доступное слово свободной области в стековом блоке. Вся используемая в данный момент память в стеке расположена ниже того места в памяти, на которое указывает стековый указатель.
Все свободное пространство расположено выше этого указателя. Когда требуется разместить блок из к минимально адресуемых х компьютером областей памяти, указатель просто смещается на я областей дальше в свободном пространстве стека. Когда требуется освободить аналогичный объем памяти, то указатель смещается на к минимально адресуемых областей обратно в занятое пространство стека. Уплотнение происходит автоматически каждый раз, когда освобождается какой-либо объем памяти, Освобождение блока памяти автоматически приводит к его восстановлению как свободной области памяти и делает его доступным для повторного использования.
Больпщнство реализаций языка С построены на основе использования одного центрального стека записей активации подпрограмм и статически размещаемой области, содержащей системные программы и сегменты кодов подпрограмм. Структура типичной записи активации для С-подпрограммы показана на рис. 9.3, а. Запись активации содержит всю изменяемую информацию, связанную с активацией данной подпрограммы.
На рис. 9.3, б показана типичная организация памяти во время выполнения программы на языке С (куча используется для размещения объектов, созданных при помощи функции пеи, которые затем уничтожаются при помощи функции г)) кроке; обе згн функции более подробно обсуждаются в главе 10). Статическая ) область памяти Сегменты кода подпрограмм и сегменты системного кода Системные данные, в том числе указатель статической цепочки Начало блока, образующего стек Местоположение точки возврата Одна запись активации в памяти Вершина стека (рвстет) (изменяется при вызове подпрограммы и расположении в стеке ее записи активации) Формальные параметры Указатель стека Покальные переменные Промежуточные результаты для вычисления выражения Промежуточные результаты для передачи параметров Куча (растет) (область памяти, отводимая пад объекты, создаваемые операцией пеш) Низ кучи ,' Куча Рис. 9.3.
Организация памяти в С: е — запись активации для подпрограмм; б — организация памяти во время выполнения Использование стека в реализации языка 1.1ЯР несколько иное. Вызовы подпрограмм (функций) также являются строго вложенными, а для храпения записей активации также может использоваться стек. 1(аждая запись активации содержит точку возврата и области памяти для временного хранения значений, необходимых для вычисления выражений и передачи параметров.
Локальные среды ссылок могут быть также размещены в том же самом стеке, но отличие заключается в том, что программисту позволено непосредственно манипулировать этими ассоциациями. Вследствие этого они, как правило, хранятся в отдельном стеке, прел- 392 Глава 9. Управление подпрограммами Свободное пространство (доступное для использования) Конец блока, образующего стек 9А.
Управление последовательностью подпрограмм 393 ставленном как связанный список, называемый А-списком. Тогда стек, содержащий точки возврата и временные значения, может быть скрыт от программиста и заполняться последовательно. Для реализации языка Е1 ЯР также необходима куча, которая управляется посредством списка свободной памяти и процессом сборки мусора. Типичная организапия памяти в языке Е!БР представлена на рис. 9А.
Системные программы времени выполнения, интерпретатор ЫБР, программы ввода-вывода Статическая область памяти Стек дпя частичного вычисления функций Блок, ; образующий стек Указатель стека Свободное пространство(доступное дпя использования) Место хранения элементов связанных списков : Куча Рис. 9.4. Организация памяти ва время выполнения дня ЫЗР 9.1.2. Рекурсивные подпрограммы Вернемся к одному из основных предположений, сделанных нами относительно используемых подпрограмм, — отсутствию рекурсии — и попытаемся разработать идеологию языка, который позволял бы использовать рекурсивные подпрограммы. Рекурсия в форме вызовов рекурсивных подпрограмм — зто одна из наиболее важных структур управления в программировании. Большое количество алгоритмов наиболее естественным образом представляется с использованием рекурсии.
В языке Е! ЯР, где первичной доступной структурой данных являются спи сковые структуры, рекурсия является первичным механизмом управления для повторяющихся последовательностей операторов, заменяя циклы, характерные для большинства других языков. Спецификация.
Если мы допускаем вызон рекурсивной подпрограммы, то подпрограмма д может вызывать любую подпрограмму, в том числе и А, и подпрограмму В, содержащую вызов д и т. д. При написании программы зто не требует никаких изменений в синтаксисе, так как вызов рекурсивной подпрограммы ничем не отличается от вызова обычной подпрограммы, Концептуально здесь также нет никаких сложностей при условии, что мы четко представляем себе отличие определения подпрограммы атее активации. Единственное различие между рекурсивным вызовом и обычным вызовом заключается в том, что рекурсивный вызов создает вторую активацию атой же подпрограммы во время жизни ее первой акти- 394 Глава 9.
Управление подпрограммами вации. Если вторая активация подпрограммы приводит к следующему рекурсивному вызову, то три активации могут существовать одновременно и т. д. Вообще говоря, если при выполнении программы образуется цепь, состоящая из первого вызова подпрограммы А, за которым следуют и рекурсивных вызовов этой же подпрограммы, происходящие до того, как произошло хотя бы одно возвращение из А, то перед возвращением из й-й рекурсивно вызванной подпрограмъ>ы будет существовать 11 + 1 активаций подпрограммы А. Единственным нововведением, связанным с рекурсией, является, таким образом, одновременное сосуществование нескольких активаций одной и той же подпрограммы.
Реализация. Поскольку мы хотим обеспечить возможность одновременного сосуществования нескольких активапий, нам нужны оба указателя — СЕР и С1Р. В момент очередного вызова подпрограммы создается новая запись активации, которая впоследствии разрушается при выходе из нес. Обратите внимание: на рис. 9.1 ничто не указывает на то, что новые записи активации следует создавать для уникальных подпрограмм А и В.
Находясь во время выполнения в подпрограмме А, мы могли бы с такой же легкостью создать нову>о запись активации для самой же подпрограммы А, как и для подпрограммы В. В случае, ко~да А вызывает В, их времена жизни не>вохут перекрываться; для любых двух активаций подпрограмм А и В время жизни А полностью включает е себя время жизни В. Отсюда следует, что если поди ро~ рамма А вызовет не В, а реку рси в по саму себя, то отмеченное свойство активаций будет справедливо и в этом случае, и новая запись активации для А может быть также добавлена в стек, содержащий более раннюю запись активации подпрограммы А, Каждая за~ ~ись активации содержит точку возврата, в которой хранятся значения пары (>р, ер), используемые операторами са11 и гегцгп.
Если на рис. 9.1 рассмотреть только значения ер, сохраняемые в точках возврата, можно заметить, что они образуют связный список, связывающий вместе записи активации в центральномм стеке в порядке их создания. С помощью указателя ССР можно получить доступ к записи активации, содержащейся на вершине центрального стека. По значению указателя ер, содержащегося в точке возврата этой записи активации, можно получить доступ ко второй записи активации в центральном стеке; указатель ер этой второй записи активации солсржит ссылку па третью и т. д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
