Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 109
Текст из файла (страница 109)
если в этой позиции уже содержится некая переменная, время жизни которой еше не закончилось (что указывается активным битом). то значение старой переменной на время жизни новой следует сохранить в какой-нибудь ячейке памяти. Одновременно с началом жизни какой-либо переменной должен быть установлен активный бит в ее позиции в центральной таблице.
Разработано несколько вариантов центральной таблицы н способов, с помощью которых переменные, временно замещаемые другими переменными. хранятся в памяти. Один из вариантов — "скрытый" стек, в который записываются все объекты, подлежащие хранению. Поскольку подпрограммы выполняют вызовы и возвращают управление, и, следовательно. времена жизни их локальных переменных вкладываются друг в друга, этот метод работает хорошо. Второй вариант, возможно, наиболее ясен и прост лля реализации. Используется центральная таблица с отдельными ячейками, в которых хранятся только текущие имена всех переменных. Замененные переменные хранятся в записях активации тех подпрограмм, в которых они создавались.
При этом используются стеки, однако один из них всегда уже существует, так что дополнительные затраты минимальны. Выбор между теневым и глубоким доступом к нелокальным переменным зависит от относительной частоты вызовов подпрограмм и обращений к нелокальным переменным. Метод глубокого доступа обеспечивает быструю связь между подпрограммами, однако при его использовании обращения к нелокальным переменным, особенно к отдаленным (в смысле статической цепочки), требуют дополнительного времени. Метод теневого доступа ускоряет обращение к нелокальным переменным, особенно к отдаленным, однако требует дополнительного времени на связь между подпрограммами. 9.6.
Реализация параметров, явля8ощихся именами подпрограмм Параметры. представляющие собой имена подпрограмм, детально обсуждались в главе 8. Напомним, что языки со статическим обзором данных для связывания среды ссылок с активацией подпрограммы, которая передается как параметр, используют метод, называемый глубоким связыванием. Теперь мы исследуем, как именно можно реализовать глубокое связывание с помощью статической цепочки и индикаторов. зг.6.1. Статические цепочки Предположим, что при реализации языка используется метод статических цепочек. Подпрограмма, которая передает имя некоей подпрограммы как параметр, должна иметь в качестве своего статического предка модуль, в котором была объявлена передаваемая подпрограмма. Если это не так, то имя передаваемой подпрограммы будет невидимым, и компилятор обнаружит синтаксическую ошибку.
Таким образом, при синтаксически правильных вызовах компилятор может просто передать связь статическому предку передаваемой подпрограммы вместе с ее именем. Затем при инициализации экземпляра активационной записи передаваемой подпрограммы эта связь заносится в его поле статических связей вместо связи, вычисляемой обычным путем. Завершение работы передаваемой подпрограммы не требует никаких особых действий. 422 Глава 9.
Реализация подпрограмм 9.6.2. Индикаторы Предположим, что прп реализации языка используются индикаторы. Подчеркнем еше что поддержка индикаторов, описанная в разделе 9.3.4.2, корректна. только если :па подпрограмм не передавались как параметры и не применялась передача парамет. з по имени. Использование индикаторов лля вызовов полпрограмм в других ситуациях .:. -плось к замене отлельного индикаторного указателя.
Когда при вызове подпрограм. ей в качестве параметра передается имя некоей подпрограммы, в индикатор должны : ть помещены указатели на все статические предки этой подпрограммы. При этом в -=мяти должно сохраняться большое количество старых индикаторных указателей. По...льку статическая среда активации подпрограммы. передаваемой как параметр, может ' еть мало обшего со статической средой вызываемой подпрограммы, во многих случа: . е пиликаторе приходится заменять несколько указателей.
В некоторых реализациях -=и каждом вызове подпрограммы, передаваемой как параметр, в памяти сохраняется зесь сушествуюший индикатор, причем часто он записывается в экземпляр актиаацион-эп записи выполняемой подпрограммы. Когда подпрограмма, передаваемая как пара' етр, завершает свою работу, полностью сохраненный индикатор заменяет собой инди° зтор. использованный для ее выполнения. 9.6.3.
Ошибочное повторное обращение к среде ссылок Перейдем к обсуждению проблемы, описанной в главе б; какая среда ссылок является -равильной при выполнении подпрограммы, передаваемой как параметр. Рассмотрим глелуюшую скелетную программу, представляюшую собой вариант программы, описан.-о й в работе Спетл( апг) )азауег( ( ! 987): ртодтва МА1М 7; ртосесЫте ЯВВ1; Ьеддп ( ЯВВ! 1 епс(; ( БОВ! ртосес(амтв Я()В2 (ртосвгзите ЯОВХ); тат Я0М : тва1; ртосес(сте ЯОВЗг Ьедзп ( Я0ВЗ ) Я0М := 0.0; аг ( Яввз 1 Ьвдап ( ЯВВ2 ) ЯЯВХг ЯВВ2 (БУВЗ)г (г ( БОВг 1 Ъедап ( МА1М 7 ) Яввг(БУВ1)г а. (МММ71 423 9.6. Реализация параметров, являющихся именами подпрограмм Подпрограмма (чНЗВ '.
вызывает процедуру В(>В2, передавая процедуру ВВВЗ как парамезр. Затем процедура ВВВ2 вызывает переданную процелуру В(>В1. После возврашения нз процедуры ВВ!В1 процедура В В В 2 вызывает сама себя, перелавая свою собственную процедуру В:>ВЗ как параметр. Теперь в стеке существует два экземпляра записи актипашш процедуры ВВВ", причем верхний экземпляр используется лля рекурсивного вызова. Затем верхняя активация процелуры ВВВЗ вызывает процелуру ВВВЗ. В тот момент, котла процедура "ВВЗ обрашается к переменной ВВМ, сушествуют лве версии этой переменной.
по одной на каждую активацикз процедуры ВВ32. в которой она объявлена. Поскольку среда ссылок процедуры БЗВЗ совпадает со средой ссылок вызывающей процедуры В(!и", которая передаст процелуру В' ВЗ как параметр, она относится к первой алтнвацин процедуры В'>В2. а не к последней по времени. В дейгпвитеяьности, это совсем не очевидно лля случайного чигатеэя программь, Ясно. что этот пример является надуманным. (>днако аналогичные ситуации кюгут возникнуть и в более реалистичных программах. Проблема заключается в том.
что, хотя интуитивно ясно, что среда ссылок должна относиться к самой последней по времени активации, это не всегда так. На рнс. 9. (3 показано состояние стека во время выполнения процедуры В ВВ3 из прелылушего примера программы. ЗЗА ь;вз ! ч ! х ! ! ! ! ЗЗА я:вз (зызаанной из ззэз! ЗЗА ясьз (аызаанной из изцц П ЗЗА хаги т ЗЗА — зкзаыппнр записи актиаанни Рнс. 9.1В.
Состояние стека дзя прзснвра прагра»- .ны ((1(Е(! 7 с парииетроз|, яазяющиыся подпро- граммой Гпралед> ра 5(>В1 была вызвана, но уззсв завернсила свою работ>) 424 Глава 9. Реализация подпрограмм сиантнка связей между подпрограммами при своей реализации требует выполне. нию.их действий. В языке РОКТКА)Ч 77 эти действия относительно просты по сле.дим причинам: отсутствуют нелокш>ьные ссылки, кроме ссылок через блоки '.:;; локальнь<е переменные обычно являются статическими, а рекурсия не полдер:..>ся.
В языках, полобных языку АГ.ООГ.. связь между подпрограммами намного - се. Это является следствисл< требований поддержки вост) па к нелокальным переыи с помощью статического обзора. наличия автоматических локальных перемен: рскурспи. :!олпрограммы в языках, подобных языку А1.0О1., состоят из двух частей: собст> кола, являющегося статическим. и активациоиной записи, являющейся линамиче° и хранящейся в стеке. ':>кземпляры активацнонных записей, кроме всего прочего, :.: жзт формальные параметры и локальные переменные.
ь татические цепочки и индикаторы прелставляк>т собой два основных метода реалии доступа к нелокалы<ым переменным в языках со статическим обзором данных. : их методах пути доступа к переменным во всех статических предках можно уста', ть статически. Д-ступ к нелокальным переменным в языках с динамическим обзором ланных мож-сазизовать с помо<пью динамических цепочек нли метода центральной таблицы пе":чных. Динамические цепочки обеспечивают медленный доступ к нелокальнь<ь< пе:нным.
но позволяют быстро выполнять вызовы подпрограмм и возвраты из них. > центральной таблицы обеспечивает быстрый доступ к нелокальным переменным, .пп мом вызовы подпрограмм и возврат из них происхозят медленнее. ! !олпрограммы, передаваемые как параметры, принося< определенную пользу. од.» нногла в них трулно разобраться.
Их запутанность объясняется неопределенностью :. зы ссылок, лоступной во врел<я выполнения таких подпрограмм. 11олпрограмчы. пе...>ваемые как параметры, можно рсалнзовь<вать с помощью как статических цепочек. . г индикаторов. .. >извиня метолов статического н лннамнческого обзора описана в книгах Ргац (1984) и О(<еаа! ап<Г Загауег! (1987), однако более детально она рассмотрена в книгах, посвященных разработке компиляторов. например, Р!зс(>ег ап<Г (.еВ!апс (1988). 1. Назовите четыре причины. по которым реализация подпрограмм на языках. подобных языку АГ,СО(., является более трулной, чем реализация подпрограмм на языке, подобном языку РОКТКА)>Г 77, В чем состоит различно между записью акз ивацни н экземпляром записи активации? 3.
Что такое адрес, статическая связь, динамическая связь и параметры. Размещенные на лне активационной записи? 425 Вопросы 18. 19. 20. 426 Глава 9. Реализация подпрограмм 1О. 11. 12. 13. 14. 15. 1б. 17. Назовите два действия, которые следует выполнить при размещении нелокальной переменной в языках со статическим обзором независимо от используемого метода.
Дайте определение статической целочки, статической дубины, гзубины вло- жения и стеи1ения в цепочке. Объясните, как обнаруживается ссылка на нелокальную переменную при исподь- зованин статических цепочек. В чем заключаются две потенциальные проблемы, связанные с методом статиче- ских цепочек? Что такое индикатор".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
