Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 107
Текст из файла (страница 107)
При этом статическая цепочка прослеживается звено за звеном, по одному звену на каждую вложенную область видимости, начиная со ссылки на переменную и заканчивая ее объявлением. Другой недостаток состоит в том, что программисту, разрабатывающему программу, продолжительность выполнения которой очень важна, трудно оценить затраты времени на обработку нелокальных ссылок, поскольку эти затраты зависят от глубины вложения между ссылкой и областью видимости объявления переменной. Еще более усложняет эту про- аЗО Глава 9.
Реализация подпрограмм блему тот факт, что при последующих модификациях кода глубины вложений могут измениться, приведя таким образом к изменению времени обработки некоторых ссылок кзк в этом, так и, возможно, в других сегментах кода. У.З.4.2. Индикатгэрег Единственной широко распространенной альтернативой статической цепочке являет:я индикатор. При этом подходе статические связи объединяются в одном массиве, наываемом индикатором, вместо того, чтобы храниться в своих активационных записях.
одержание индикатора в любой конкретный момент времени представляет собой спи:ок адресов доступных экземпляров акгивационных записей в стеке — по одному на ка«з)ю активную область видимости — в том порядке, в котором они вложены друг в друга. Каждый доступ к нелокальным переменным с помощью индикатора состоит из двух .гапон, независимо от количества вложенных областей видимости, разделяющих ссылку л объявление переменной, к которой требуется получить доступ. Во-первых, с помощью :татнчески вычисляемого значения, называемого смещением индикатора (огзр!ау гТзег) и тесно связанного со смешением в цепочке, обнаруживается связь с нужной актизацнонной записью, которая хранится в индикаторе.
Во-вторых, локальное смешение зн)три экземпляра активационной записи вычисляется и используется точно так же, как '. при применении статической цепочки. Нелокальная ссылка представляется упорядо-.енной парой целых чисел (смешение индикатора, локальное смешение). Нелокальную -.еременную можно удобно и быстро адресовать, дважды выполнив косвенную адреса. ню, основанную на смешениях.
При каждом вызове подпрограммы и возврате из нее необходимо изменять содержимое индикатора, чтобы отражать новое состояние областей видимости. Теперь мы иссле-) ем действия, которые следует выполнять лля поддержания работы индикатора. Пред-оложим, что параметры не могут быть именами подпрограмм и передаваться по имени. Эти более сложные случаи рассматриваются в разделе 9.6. Смешение индикатора зависит только от статической глубины процедуры, в которой -:является обращение к нелокальной переменной.
Если статическая глубина процедуры .= равна 2, то связь с экземпляром записи активации процедуры Р всегда будет появпять.: в индикаторе во второй позиции. Индексы индикатора отсчитываются от нуля, причем -)левая позиция используется лля доступа к переменным, обьявленным во внешней об.зстн видимости (главном модуле).
Указатель на позицию я в индикаторе адресует экземпляр активационной записи проедуры, имеющей статическую глубину, равную /г. При вызове процедуры Р, имеющей ;татическую глубину, равную гг, индикатор следует модифицировать, выполнив следую- не действия. Е Сохранить копию указателя, записанного в «-й позиции индикатора, в новом экземпляре записи активации.
2. Поместить связь с экземпляром записи активации процедуры Р в л-ю позицию инликатора, Прн завершении работы подпрограммы указатель, сохраненный в экземпляре записи зктнвации завершенной подпрограммы, следует вернуть в индикатор. Затем экземпляр :зчиси активации подпрограммы удаляется из стека точно так же, как это происхолило -"и работе со статической цепочкой.
=.3. Реопнзоция подпрограмм но языках, подобных языку А10О1 411 епс) 1 Я))В1 ргосес)сге Я))В21 ргосес)цге ЯБВЗ) епс ( Я\)ВЗ епк) ( Я))В2 ) епс) [ В16Я))В ) епс1. ) МА1М 3 ) Первый случай может возникнуть, если процедура ЯВВ2 вызывается процедурой Я))В1. поскольку они обе имеют статическую глубину, равную 2. Состояние стека и индикатор непосредственно перед вызовом и сразу после него показаны на рис. 9. ) О. 2 1 О Индикатор 2 1 О Индикатор Стек Сэек а) иа:и 3 вызывает в1сзэв; вэозпв аыэыааеэ вцв2 б! впв2 аыэывает вцв1 ЭЗА — зкэеыииар записи активации Рис. 9.10.
Изменение индикаторов, соответствующих вызывающей и вы- зываечой лодорограччач одиниковои статической глубины Глава 9. Реализация подпрограмм Для того чтобы убедиться, что описанные выше действия всегда выполняются корректно, рассмотрим три возможные ситуации, возникающие при вызове процедуры Р из процедуры О. Обозначим через Рэд статическую глубину процедуры Р, а через Озд— статическую глубину процедуры )3.
Рассмотрим три случая. Рд Оэд 2. Рад <Оэд 3. Рэд > Оэд Воспользуемся следующей программой, представляющей собой скелетную версию программы из предыдущего примера программы МА1М 2. ргодгаж МА1)1 31 ргосек)сге В16ЯУВ) ргосеспге ЯУВ11 Для вызова, как всегда, необходимо, чтобы новый экземпляр активанионной записи бьщ помещен в стек. Новая среда ссылок содержит только подпрограммы Я1)В1. 3133 'В и М)т1р) 3. Поскольку значения статической глубины подпрограмм Я))В1 и "':-2 равны между собой, их индикаторные связи должны занимать в индикаторе одинаковые места.
Это означает, что их смешения в индикаторе должны быть равными. Поскольку индикаторные связи всегда хранятся в новом экземпляре активапнонной записи, никаких проблем не возникает. Следовательно, элемент индикатора, соответствующий подпрограмме Я!)В2. должен быть удален, и на его место должен быть записан новый элемент индикатора, соответствующий подпрограмме Я1)В1. В ланном случае он является вторым элементом индикатора в соответствии со статической глубиной подпрограммы 5))В1.
После того как подпрограмма Я!)В1 завершит свою работу и вернет управление подпрограмме Я))В2, элемент индикатора, соответствующий подпрограмме Я!)В2, должен быть восстановлен на прежнем месте. Непосредственно перед удалением экземпляра активапнонной записи пропедуры Я!)В1 из стека сохраненный экземпляр индикатора перемещается из экземпляра обратно в индикатор. Второй случай может возникнуть, если подпрограмма Я!)В2 вызывает подпрограмму 3':ВЗ. Статическая глубина подпрограммы Я1)В2 равна 2, а подпрограммы Ят)ВЗ вЂ” 3.
Состояние стека и дисплея непосредственно перед вызовом н сразу после него показаны на рис. 9. ! !. Стек Стек Индикатор Индикатор б) эсвг вызывает всвз в)катк з вызываатв:сзэв; в сзсавызываатзсвг ЭЗА — экземпляр записи активации Рис. 9. 11. Изменение индикатора в сит»ацитт, когда статическая ты»бина выэыватгцей падпраграттны этеньитв статической ат»бины вызываемой подпрограммы тьгэд < РЫ) В данном случае в стеке, как обычно, создается новая запись активапни, однако среда гсыток просто увеличивается на одну новую область видимости, соответствующую вызываемой подпрограмме. Таким образом, в индикатор можно просто добавить новый .
казатель. В этом конкретном примере нет необходимости сохранять в экземпляре актиэзшюнной записи существующий указатель, записанный в индикаторе на месте, предназначенном для нового указателя. Однако в общем случае это неверно. В других ситуашткк это делать необходимо. Намного проще каждый раз сохранять существующий указатель. чем определять при каждом вызове подпрограммы, следует ли это делать. В качес- «.3. Рвплнзпция подпрограмм но языках, подобных языку АЮО).
тве примера ситуации, в которой указатель необходимо сохранять, рассмотрим следующую подпрограмму Я()В4: ргодгае МА1(Ч 4; ргооесЫге В16Я()вг ргосес(иге Я()В1; ргооейиге Я()В41 епа; ( Я()В4 ) Зг ( Я((В1 ) ргосейиге Я()В24 ргооес(цге Я()ВЗз епс(ч ( Я()ВЗ ) епй; ( Я()В2 ) а; ( В1ВЯив ) еЫ. ( МДПЧ 4 ) Предположим.
что в ходе выполнения программы ее подпрограммы вызываются слелующим образом: ИА (Ч 4 вызывает В16Я()В В1ВЯОВ вызывает Я()В2 ЯВВ2 вызывает Я()ВЗ Я 'ВЗ вь:зывает Я((В4 Состояние стека и индикатора, полученное в результате этих вызовов, показано на рис. 9.12. Допустим теперь, что подпрограмма 5()В! вызывает подпрограмму 5()В4. Это пример ситуации. при которой статическая глубина вызывающей подпрограммы меньше, чем вызываемой. В этом случае указатель, соответствующий подпрограмме 5(/ВЗ, занимает в индикаторе место, на котором должен был бы находиться указатель, соответствующий подпрограмме 5ОВ4. Обе эти подпрограммы имеют статическую глубину, равную 3.
Слеловательно. существующий в индикаторе указатель следует сохранить перед тем. как на его место будет помещен новый указатель. Правильное состояние стека и индикатора при выполнении подпрограммы 5()В4 показано на рис. 9.13. Третий случай (Озд > Рзд) возникает, когда подпрограмма Я()ВЗ вызывает подпрограмму ЯВЗ1. Статическая глубина процедуры Я()ВЗ равна 3, а процедуры Я()В1 — 2. Состояния стека и индикатора непосредственно перед вызовом и сразу после него показаны на рис. 9.14. В данном случае оказывается, что два элемента индикатора, соответствующие поллрограммам Я()В2 и ЯВВЗ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
