Cтраница 3
Указатели статической цепи служат основой простой схемы обработки ссылок. Обрабатывая ссылку на X, мы начинаем с текущей локальной среды на вершине стека. Если в локальной среде не найдено ассоциации для X, то мы переходим ко второй таблице согласно указателю статической цепи в исходной локальной таблице. Если и в этой таблице нет X, то мы продолжаем поиск, следуя указателям статической цепи, пока не найдем локальную таблицу, содержащую ассоциацию для X. [31]
Рассмотрим теперь случай определения нелокальной среды посредством статической блочной структуры. Вспомним, что в этом случае нелокальная среда зависит от места определения подпрограммы в исходной программе. Примем, что для определения нелокальных сред ссылок во время выполнения используется механизм статической цепи. Когда Q передается R, как параметр, ее среда ссылок в момент передачи определяется статической цепью, соответствующей точке определения Q. Если передавать вместе с Q указатель на эту статическую цепь и восстанавливать этот указатель при вызове Q из R, то получается эффективный метод восстановления правильной нелокальной среды для Q. В процессе передачи параметров Q снова представляет собой пару ( указатель на команды, указатель среды), причем указатель среды указывает на таблицу локальной среды в точке определения Q. Эта таблица определяется в точности так же, как если бы Q вызывалась не из R, а из точки, где Q фигурирует в качестве параметра. [32]
Рассмотрим теперь случай определения нелокальной среды посредством статической блочной структуры. Вспомним, что в этом случае нелокальная среда зависит от места определения подпрограммы в исходной программе. Примем, что для определения нелокальных сред ссылок во время выполнения используется механизм статической цепи. Когда Q передается R, как параметр, ее среда ссылок в момент передачи определяется статической цепью, соответствующей точке определения Q. Если передавать вместе с Q указатель на эту статическую цепь и восстанавливать этот указатель при вызове Q из R, то получается эффективный метод восстановления правильной нелокальной среды для Q. В процессе передачи параметров Q снова представляет собой пару ( указатель на команды, указатель среды), причем указатель среды указывает на таблицу локальной среды в точке определения Q. Эта таблица определяется в точности так же, как если бы Q вызывалась не из R, а из точки, где Q фигурирует в качестве параметра. [33]
На каждом из этих шагов нужно изменять среду ссылок. На рис. 6.16 изображены среды ссылок, действующие между любыми двумя соседними шагами. Заметим, что, когда процедура или метка передается новой активации подпрограммы в каче-стве параметра, передается также указатель на локальную таб-лицу, в которой была найдена ассоциация для фактического параметра. Например, на шаге 2 в качестве фактического параметра Р передается QHUM, а также указатель на локальную таблицу В, в которой имеется ассоциация для Q. На шаге 3, когда Р вызывает QHUxc через формальный параметр X, указатель статической цепи в таблице для ( ниж можно установить так, чтобы он указывал на таблицу В, создавая тем самым нужную для выполнения Qh m нелокальную среду. Читателю рекомендуется для каждого шага самостоятельно определить: каким образом можно перейти от предыдущей среды к следующей, имея только эту предыдущую среду; форматы таблиц, показанные на рис. 6.15; и выполняемую инструкцию программы. Заметим, что текущая локальная среда на каждом шаге задается специальным указателем головы статической цепи ( ГСЦ), который хранится в фиксированном месте. Чтобы яснее показать различные среды ссылок в разные моменты выполнения, мы использовали представление в виде дерева, а не непо средственно стековую структуру. Заметим, что локальные таблицы уничтожаются в порядке, строго обратном порядку их со-здания, и поэтому можно создавать и уничтожать таблицы, помещая их в единственный стек. [34]
Необходимость прохождения статической цепи для каждой нелокальной ссылки является недостатком приведенного метода. В этом методе статическая цепь хранится отдельно от главного стека. Текущая статическая цепь записывается в специальный малый стек, называемый дисплеем. Дисплей содержит последовательность указателей на локальные таблицы в главном стеке. В любой момент времени выполнения в дисплее содержится такая же последовательность указателей, какая была бы в тот же момент в статической цепи при старом методе. [35]
Предположим, что подпрограмма Р вызывается из подпрограммы Q и что Р определена в исходной программе внутри блока В. В точке вызова на вершине стека находится локальная таблица для Q, и таблица для Р должна быть помещена выше нее. Заметим, что на сам идентификатор Р в Q имеется нелокальная ссылка. Если Р представлен парой ( 3, 2), то ассоциация для идентификатора Р должна находиться в таблице, лежащей в трех шагах от начала статической цепи для Q, а именно во втором элементе этой таблицы. Но таблицей, содержащей элемент для Р, должна быть таблица для блока В. Таким образом, когда мы обрабатываем ссылку на Р в точке вызова подпрограммы ( в Q), мы можем столь же легко найти соответствующий указатель статической цепи, который следует поместить в локальную таблицу для Р при ее создании. [36]
На каждом из этих шагов нужно изменять среду ссылок. На рис. 6.16 изображены среды ссылок, действующие между любыми двумя соседними шагами. Заметим, что, когда процедура или метка передается новой активации подпрограммы в каче-стве параметра, передается также указатель на локальную таб-лицу, в которой была найдена ассоциация для фактического параметра. Например, на шаге 2 в качестве фактического параметра Р передается QHUM, а также указатель на локальную таблицу В, в которой имеется ассоциация для Q. На шаге 3, когда Р вызывает QHUxc через формальный параметр X, указатель статической цепи в таблице для ( ниж можно установить так, чтобы он указывал на таблицу В, создавая тем самым нужную для выполнения Qh m нелокальную среду. Читателю рекомендуется для каждого шага самостоятельно определить: каким образом можно перейти от предыдущей среды к следующей, имея только эту предыдущую среду; форматы таблиц, показанные на рис. 6.15; и выполняемую инструкцию программы. Заметим, что текущая локальная среда на каждом шаге задается специальным указателем головы статической цепи ( ГСЦ), который хранится в фиксированном месте. Чтобы яснее показать различные среды ссылок в разные моменты выполнения, мы использовали представление в виде дерева, а не непо средственно стековую структуру. Заметим, что локальные таблицы уничтожаются в порядке, строго обратном порядку их со-здания, и поэтому можно создавать и уничтожать таблицы, помещая их в единственный стек. [37]
Предположим, что подпрограмма Р вызывается из подпрограммы Q и что Р определена в исходной программе внутри блока В. В точке вызова на вершине стека находится локальная таблица для Q, и таблица для Р должна быть помещена выше нее. Заметим, что на сам идентификатор Р в Q имеется нелокальная ссылка. Если Р представлен парой ( 3, 2), то ассоциация для идентификатора Р должна находиться в таблице, лежащей в трех шагах от начала статической цепи для Q, а именно во втором элементе этой таблицы. Но таблицей, содержащей элемент для Р, должна быть таблица для блока В. Таким образом, когда мы обрабатываем ссылку на Р в точке вызова подпрограммы ( в Q), мы можем столь же легко найти соответствующий указатель статической цепи, который следует поместить в локальную таблицу для Р при ее создании. [38]