А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 109
Текст из файла (страница 109)
Предположим, что запись активации для 7' включает следующие элементы в указанном порядке: (возвращаемое значение, аргумент и, локальная переменная а, локальная переменная 1). В записи активации находятся и другие обычные элементы. Приведенные ниже вопросы предполагают, что начальным вызовом был вызов 7' (5). а) Изобразите полное дерево активаций. б) Как выглядит стек и записи активации в нем в момент первого возврата из вызова 7" (1)? ! в) Как выглядит стек и записи активации в нем в момент пятого возврата из вызова ~ (1)? 1пк й(1пс и) ( 1пс 1, в; 11 (и < 2) теспгп 1; в = 1(п-1); й(п-2)г теТптп а+к; Рис.
7.9. Код вычисления чисел Фибоначчи к упражнению 7.2.3 Упражнение 7.2.4. Перед вами набросок двух функций на языке программиро- вания С: 1пс й(1пс х) ( 1пс 1; гесикп 1+1г 1пт. 9(1пт. у) ( 1пс 3Г т(3+1) ) Как видите, функция д вызывает функцию )'.
Изобразите вершину стека, начиная с записи активации д, после того, как д вызывает )', в момент непосредственно перед возвратом из функции г. Вы можете рассматривать только возвращаемые значения, параметры, связи управления и память для локальных переменных; рассматривать сохраненное состояние машины или временные переменные (а также локальные переменные, помимо приведенных в наброске) не требуется. Для каждого из элементов вы должны указать следующее. 542 Глава 7. Среды времени выполнения а) Какая функция создает место в стеке для элемента? б) Какая функция записывает значение элемента? в) Какой записи активации принадлежит элемент? Упражнение 7.2.5.
В языке, в котором параметры передаются по ссылке, имеется функция 7' (х, у), делающая следующее: х = х + 1; у = у + 2; кегцгп х+у; Что вернет вызов г" (а, а), если перед ним а присвоено значение 3? Упражнение 7.2.6. Функция 7' на языке программирования С определена следу- ющим образом: 1пт. й(хпт. х, *ру, **ррк) ( **ррх += 1; *ру += 2; х += 3; ге~или к+у+к; Переменная а представляет собой указатель на 6; переменная 6 — указатель на с, а с — целочисленная переменная, значение которой в настоящий момент равно 4. Что вернет вызов 7" (с, б, а)? 7.3 Доступ к нелокальным данным в стеке В этом разделе мы рассмотрим, как процедура обращается к своим данным.
Особенно важен механизм поиска данных, используемых в процедуре р, но не принадлежащих р. Доступ становится особенно сложным в языках программирования, которые допускают объявление одних процедур в пределах других процедур. Поэтому мы начнем с простого случая функций С, а затем перейдем к языку программирования М1., который допускает как вложенные объявления функций, так и использование функций в качестве объектов, т.е. функции могут как принимать функции в качестве параметров, так и возвращать функции. Эта возможность может быть обеспечена путем изменения реализации стека времени выполнения, и мы рассмотрим несколько вариантов такого изменения записей активации из раздела 7.2. 7.3.1 Доступ к данным при отсутствии вложенных процедур В семействе языков программирования С все переменные определены либо в одной из функций, либо вне любой функции (" глобально" ). Самое важное то, 543 7.3.
Доступ к нелокальным данным в стеке что невозможно объявить одну процедуру, область видимости которой находится полностью внутри другой процедуры. Глобальная переменная н имеет область видимости, которая состоит из всех функций, следующих после объявления н, за исключением мест, где имеется локальное определение идентификатора н. Переменные, объявленные внутри функции, имеют область видимости, состоящую только из этой функции (или ее части, если в функции имеются вложенные блоки, рассматривавшиеся в разделе 1.6.3).
Для языков, которые не допускают вложенные объявления процедур, выделение памяти для переменных и доступ к ним просты. 1. Глобальным переменным выделяется статическая память. Размещение этих переменных остается фиксированным и известно во время компиляции. Так что для доступа к любой переменной, не являющейся локальной для текущей выполняемой процедуры, просто используются статически определенные адреса. 2. Любое другое имя должно быть локально для активации на вершине стека. Обратиться к этим переменным можно при помощи указателя стека гор зр.
Важное преимущество статического распределения памяти для глобальных переменных заключается в том, что объявленные процедуры могут передаваться в качестве параметров и возвращаться в качестве результата (в С передается указатель на функцию) без существенных изменений в стратегии обращения к данным. В случае правил статических областей видимости С и при отсутствии вложенных процедур любое имя, нелокальное для одной процедуры, будет нелокальным для всех процедур, независимо от того, как они были активированы.
Аналогично, если процедура возвращается как результат, нелокальные имена в ней ссылаются на статически выделенную для них память. 7.3.2 Вложенные процедуры Доступ существенно усложняется, если язык программирования разрешает объявлениям процедур быть вложенными и при этом использует обычные правила областей видимости (т.е. процедура имеет доступ к переменным процедуры, обьявление которой охватывает объявление текущей процедуры, следуя правилам для вложенных областей видимости, которые были изложены для блоков в разделе !.6.3). Причина этого в том, что знание во время компиляции того, что объявление р непосредственно вложено в объявление д ничего не говорит нам об относительном размещении их записей активации во время выполнения.
В действительности, поскольку процедуры р или д (или обе) могут быть рекурсивными, в стеке могут быть несколько записей активации для р и/или д. Поиск объявления, применимого к нелокальному имени х во вложенной процедуре р выполняется статически; он может быть выполнен при помощи рас- 544 Глава 7. Среды времени выполнения ширения статических правил областей видимости для блоков. Предположим, что имя х объявлено в охватывающей процедуре ц. Поиск соответствующей активации д из активации р выполняется динамически, так как требует дополнительной информации времени выполнения об активациях. Одно из возможных решений заключается в использовании связей доступа", о которых мы расскажем в разделе 7.3.5. 7.3.3 Язык с вложенными объявлениями процедур Семейство языков программирования С, как и многие другие распространенные языки программирования, не поддерживает вложенные процедуры, так что мы вкратце расскажем о них здесь. Вложенные процедуры в языках программирования имеют долгую историю.
Предшественник С А1яо! 60 обладал этой возможностью, как и его другой потомок — Рааса!, популярный учебный язык программирования. Среди более поздних языков программирования с вложенными процедурами одним из наиболее важных является МЬ, у которого мы позаимствуем синтаксис и семантику (см. врезку "Дополнительная информация об МЬ"). ° МЬ представляет собой функциональный язык; это означает, что однажды объявленные и инициализированные переменные не изменяются. Сушествует лишь несколько исключений, таких как массивы, элементы которых могут быть изменены специальными вызовами функций.
° Переменные определяются и получают свои начальные неизменяемые значения при помощи инструкций вида ча1 (имя) = (выражение) ° Функции определяются при помощи следующего синтаксиса: йцп (имя) ((аргументы)) = (тело) ° Для тел функций используются инструкции вида 1ес (список определений) 1п (инструкции) епб Определения обычно являются инструкциями ча1 или 1цп. Область видимости каждого такого определения состоит из всех определений до 1п и всех инструкций до епсЬ Особенно важно то, что определения функций могут быть вложенными. Например, тело функции р может содержать 1ет-инструкцию, которая включает определение другой (вложенной) функции д.
Аналогично д может иметь в своем теле определения функций, что приводит к вложенности функций произвольной глубины. 7гй Доступ к нелокальным данным в стеке 545 Дополнительная информация об МЬ В дополнении к чистой функциональности МЬ готовит массу сюрпризов программисту, работающему с языком программирования С или иным языком из его семейства. ° МЬ поддерживает функции высшего порядка ((з(ййег-оп(ег (ппс!(опя), т.е. функция может принимать функции в качестве аргументов, а также создавать и возвращать другие функции.
Эти функции, в свою очередь, могут принимать функции как аргументы — до любого уровня. ° МЬ, по сути, не имеет итераций, таких, например, как Рог- и и4з1!еинструкции С. Эффект итераций достигается путем применения рекурсии. Этот подход является неотъемлемым свойством функционального языка, поскольку изменение переменной итерации наподобие ( в аког(1=0;1<10!1++) в С невозможно.
Вместо этого МЬ делает ( аргументом функции, и эта функция вызывает саму себя с возрастающим значением Ь пока не будет достигнут требуемый предел. ° МЬ поддерживает в качестве примитивных типов данных списки и помеченные древовидные структуры. ° МЬ не требует объявления типов переменных. Вместо этого он выводит типы во время компиляции, и, если это невозможно, программа считается содержащей ошибку. Например, из оа1 х = 1 совершенно очевидно, что х имеет целочисленный тип, а из ча1 у = 2*х становится ясно, что тот же тип имеет и у.
7.3.4 Глубина вложенности Присвоим глубину вложенности (пезйпд с(ер!и) ! процедурам, которые не вложены ни в какую иную процедуру. Например, все функции С имеют глубину вложенности !. Однако если процедура р определена непосредственно в процедуре с глубиной вложенности (, то глубина вложенности такой процедуры р составляет ( -! 1, Пример 7.5.
На рис. 7.(0 приведен набросок нашего примера быстрой сортировки на МЬ. Единственная функция с глубиной вложенности ! -- внешняя функция хогд которая считывает массив а из 9 целых чисел и сортирует его с применением алгоритма быстрой сортировки. Во второй строке функции яог! определен массив и. Обратите внимание на вид этого объявления МЬ. Первый аргумент актау 546 Глава 7.
Среды времени выполнения указывает, что нам нужен массив из 11 элементов; все массивы МЬ индексируются целыми числами, начинающимися с О, так что этот массив очень похож на массив а языка программирования С на рис. 7.2. Второй аргумент аггау говорит о том, что изначально все элементы массива а хранят значение О. Выбор целочисленного начального значения 0 позволяет компилятору М1. вывести, что а— массив целых чисел, так что мы не должны объявлять тип а. 1) йцп зогс (фпрпсе 11е, опсрцсл 11е ) 1еп з«а1 а = аггау(11,0); йцп геасйггау ( 1присс 11е ) а аппп ехс)запое(1,3) а йип с(цфс)сзогс(зв, п) 1еГ з«а1 з« = . аппп рагСфс1оп(у«в) а ..
з« . ехс)танце 2) 3) 4) 5) 6) 7) 8) 9) 10) 1п а . ч рагсфсйоп .. с(и1с)сзсгг епс1 з.п 12) а геас)Аггау .. с(п1с)сзогГ епс(; Рис. 7.10. Версия быстрой сортировки в стиле МЬ с использованием вложенных функций Внутри зог( объявлены несколько функций: геаАА«гау, ехс)зан8е и цн(с(слога Предполагается, что в строках 4 и 6 функции «еас(А«гау и ехс)зап8е получают доступ к массиву а. Заметим, что в МЬ массивы позволяют нарушать функциональную природу языка и обе указанные функции изменяют значение элементов а, как и в С-версии быстрой сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
