Cтраница 3
Трудность, вызываемая нелокальными ссылками в параметре-подпрограмме, состоит в следующем: когда ссылка на формальный параметр приводит к выполнению подпрограммы-фактического параметра, среда ссылок, нужная для. Вместо нее обычно необходимо создать некоторую другую нелокальную среду ссылок специально для выполнения подпрограммы-параметра. Если нелокальные среды описываются явно ( как в Фортране), то никаких трудностей не возникает, поскольку все нелокальные ссылки обычно являются глобальными и, таким образом, не зависят от точки вызова или передачи. Однако если используются неявные нелокальные среды, то восстановление подходящей нелокальной среды в момент вызова может быть довольно сложной задачей. [31]
Проведя эксперимент с некоторыми тестовыми программами, определите, как передаются параметры подпрограмм в доступной вам реализации ПЛ / I - по ссылке или по результату. Необходимы главная программа и подпрограмма. С точки зрения главной программы оба метода передачи параметров должны быть неразличимы; но в подпрограмме имеются некоторые тонкие отличия, которые проявляются, когда, передача параметров сочетается с нелокальными ссылками. [32]
Алгол ( и частично ПЛ / 1) иллюстрируют вложенную структуру программ, при которой определения подпрограмм в главной программе выступают в качестве деклараций и могут в свою очередь содержать другие вложенные определения подпрограмм на любом уровне. Такая общая организация программы непосредственно связана с ярко выраженным в Алголе стремлением к структурированным инструкциям, но фактически служит другой цели. Вложенные же определения подпрограмм обеспечивают для подпрограмм среду нелокальных ссылок, которая определяется во время компиляции и допускает поэтому статическую проверку типов и компиляцию эффективного выполняемого кода для подпрограмм, содержащих нелокальные ссылки. Если бы определения подпрограмм не были вложенными, то пришлось бы либо снабдить описаниями все нелокальные переменные внутри каждого определения подпрограммы ( как это сделано в Фортране), либо отложить все проверки типов нелокальных ссылок до момента прогона программы. Вложенность несет еще и менее важную функцию, позволяющую именам подпрограмм быть че обязательно глобальными. [33]
Оба эти метода моделирования нелокальной среды, основанной на последней ассоциации, значительно снижают эффективность на стадии выполнения. И только потому, что необходим поиск последней ассоциации. Уже сам по себе поиск требует времени. К локальным ссылкам по-прежнему применим эффективный метод базовый адрес смещение, но любая нелокальная ссылка обязательно приводит к поиску вниз по цепи таблиц локальных ассоциаций. Эта цепь определяется динамически в процессе выполнения и может изменяться при различных вызовах одной и той же подпрограммы, поэтому нельзя обойтись без поиска по цепи. Предположим, например, что в подпрограмме R содержится нелокальная ссылка на X. Один раз R может быть вызвана из Q, в которой есть локальная ассоциация для X. В следующий раз R может быть вызвана из Р, не имеющей ассоциации для X, и тогда понадобится ассоциация для X, расположенная глубже в цепи вызовов. Еще позже R может быть вызвана из S, и в цепи вызовов вовсе не окажется ассоциации для X, что приведет к останову по ошибочной ссылке. [34]
Преимущество явного задания состоит в простоте моделирования, поскольку определяется только одна глобальная среда. Кроме того, явное задание, веооятно, обеспечивает хо рошую защиту от ошибок, поскольку ссылки, которые не являются ни локальными, ни явно заданными нелокальными, могут быть обнаружены во время трансляции. С другой стороны, метод явного задания менее гибок в том смысле, что допускается только один уровень нелокальных ссылок. Кроме того, может потребоваться значительное количество дополнительных деклараций, если широко используются нелокальные ссылки. [35]
Алгол ( и частично ПЛ / 1) иллюстрируют вложенную структуру программ, при которой определения подпрограмм в главной программе выступают в качестве деклараций и могут в свою очередь содержать другие вложенные определения подпрограмм на любом уровне. Такая общая организация программы непосредственно связана с ярко выраженным в Алголе стремлением к структурированным инструкциям, но фактически служит другой цели. Вложенные же определения подпрограмм обеспечивают для подпрограмм среду нелокальных ссылок, которая определяется во время компиляции и допускает поэтому статическую проверку типов и компиляцию эффективного выполняемого кода для подпрограмм, содержащих нелокальные ссылки. Если бы определения подпрограмм не были вложенными, то пришлось бы либо снабдить описаниями все нелокальные переменные внутри каждого определения подпрограммы ( как это сделано в Фортране), либо отложить все проверки типов нелокальных ссылок до момента прогона программы. Вложенность несет еще и менее важную функцию, позволяющую именам подпрограмм быть че обязательно глобальными. [36]
Определение функции в Лиспе имеет форму списковой структуры. Поэтому с помощью примитива READ определение функции можно считать и странслировать во внутреннее представление, имеющее вид связанного списка, точно так же, как любую другую списковую структуру. APPLY использует в качестве аргументов ( 1) определение функции ( начинающееся с LAMBDA и списка формальных параметров), ( 2) список фактических параметров и ( 3) А-список для разрешения нелокальных ссылок во время выполнения функции ( см. следующий разд. APPLY сначала вычисляет фактические параметры, затем устанавливает попарное соответствие между полученными значениями и формальными параметрами функции и, наконец, последовательно добавляет эти пары на вершину А-списка. Затем APPLY вызывает второй примитив, EVAL, для вычисления тела определения функции ( в форме списковой структуры оно всегда является выражением); при этом в качестве среды ссылок используется модифицированный А-список. [37]
Ссылки на идентификаторы называются локальными ссылками, если они используют ассоциацию, активную только внутри выполняемых в настоящий момент блока или подпрограммы. Например, в Алголе локальной является ссылка на идентификатор, описанный в блоке, вход в который был выполнен Позднее всего. Глобальной ссылкой называется ссылка на ассоциацию, активную на протяжении всего выполнения программы. Примерами глобальных ссылок являются ссылки на имена подпрограмм в Фортране, а в Алголе - ссылки на идентификаторы, описанные в самом внешнем блоке. Нелокальная ссылка - это, как показывает название, любая ссылка, не являющаяся локальной. В Фортране ссылки бывают только локальными или глобальными. [38]
Использование имени подпрограммы в качестве фактического параметра представляет особый случай. Различий между передачей по имени, по значению и по ссылке в сущности нет: мы ожидаем, что будет передаваться указатель на блок выполняемых команд подпрограммы, вероятно, вместе с описанием нелокальной среды ссылок. Тот же метод применим, если фактический параметр, передаваемый по имени, скомпилирован в санк. Передается указатель на команды для санка совместно с описанием нелокальной среды ссылок, в которой должен выполняться этот санк. В санке вообще имеются только нелокальные ссылки, поэтому описание среды ссылок очень важно. Обычная подпрограмма может содержать нелокальные ссылки. [39]
Предположим, что подпрограмма Р вызывается из подпрограммы Q и что Р определена в исходной программе внутри блока В. В точке вызова на вершине стека находится локальная таблица для Q, и таблица для Р должна быть помещена выше нее. Заметим, что на сам идентификатор Р в Q имеется нелокальная ссылка. Если Р представлен парой ( 3, 2), то ассоциация для идентификатора Р должна находиться в таблице, лежащей в трех шагах от начала статической цепи для Q, а именно во втором элементе этой таблицы. Но таблицей, содержащей элемент для Р, должна быть таблица для блока В. Таким образом, когда мы обрабатываем ссылку на Р в точке вызова подпрограммы ( в Q), мы можем столь же легко найти соответствующий указатель статической цепи, который следует поместить в локальную таблицу для Р при ее создании. [40]
Передача информации между подпрограммами через пара метры встречается чаще, чем передача через нелокальные среды. Цель в обоих случаях одна - позволить подпрограммам совместно использовать некоторые элементы данных и программ. Параметры особенно полезны в тех случаях, когда при каждом вызове подпрограммы ей нужно передавать для обработки различные данные. Применение нелокальной среды более подходит в случае, когда при всех вызовах используются одни и те же данные. Если, например, подпрограмма Р вызывается, чтобы занести новый элемент данных в таблицу, разделяемую с другими подпрограммами, то обычно для доступа к таблице используется нелокальная ссылка в Р, но элемент данных передается при каждом вызове как явный параметр. [41]
Алгол ( и частично ПЛ / 1) иллюстрируют вложенную структуру программ, при которой определения подпрограмм в главной программе выступают в качестве деклараций и могут в свою очередь содержать другие вложенные определения подпрограмм на любом уровне. Такая общая организация программы непосредственно связана с ярко выраженным в Алголе стремлением к структурированным инструкциям, но фактически служит другой цели. Вложенные же определения подпрограмм обеспечивают для подпрограмм среду нелокальных ссылок, которая определяется во время компиляции и допускает поэтому статическую проверку типов и компиляцию эффективного выполняемого кода для подпрограмм, содержащих нелокальные ссылки. Если бы определения подпрограмм не были вложенными, то пришлось бы либо снабдить описаниями все нелокальные переменные внутри каждого определения подпрограммы ( как это сделано в Фортране), либо отложить все проверки типов нелокальных ссылок до момента прогона программы. Вложенность несет еще и менее важную функцию, позволяющую именам подпрограмм быть че обязательно глобальными. [42]
Использование имени подпрограммы в качестве фактического параметра представляет особый случай. Различий между передачей по имени, по значению и по ссылке в сущности нет: мы ожидаем, что будет передаваться указатель на блок выполняемых команд подпрограммы, вероятно, вместе с описанием нелокальной среды ссылок. Тот же метод применим, если фактический параметр, передаваемый по имени, скомпилирован в санк. Передается указатель на команды для санка совместно с описанием нелокальной среды ссылок, в которой должен выполняться этот санк. В санке вообще имеются только нелокальные ссылки, поэтому описание среды ссылок очень важно. Обычная подпрограмма может содержать нелокальные ссылки. [43]
Оба эти метода моделирования нелокальной среды, основанной на последней ассоциации, значительно снижают эффективность на стадии выполнения. И только потому, что необходим поиск последней ассоциации. Уже сам по себе поиск требует времени. К локальным ссылкам по-прежнему применим эффективный метод базовый адрес смещение, но любая нелокальная ссылка обязательно приводит к поиску вниз по цепи таблиц локальных ассоциаций. Эта цепь определяется динамически в процессе выполнения и может изменяться при различных вызовах одной и той же подпрограммы, поэтому нельзя обойтись без поиска по цепи. Предположим, например, что в подпрограмме R содержится нелокальная ссылка на X. Один раз R может быть вызвана из Q, в которой есть локальная ассоциация для X. В следующий раз R может быть вызвана из Р, не имеющей ассоциации для X, и тогда понадобится ассоциация для X, расположенная глубже в цепи вызовов. Еще позже R может быть вызвана из S, и в цепи вызовов вовсе не окажется ассоциации для X, что приведет к останову по ошибочной ссылке. [44]
Этот, шире распространенный метод обеспечивает неявное создание нелокальной среды для подпрограммы при входе в нее. Неявная нелокальная среда содержит набор ассоциаций, разделяемых с другими подпрограммами. Если в подпрограмме содержится ссылка на X и для X нет локальной ассоциации, то эта ссылка рассматривается как нелокальная, и ассоциация для X выбирается из неявной нелокальной среды. Но какой должна быть эта нелокальная среда. Предположим, что Р вызывает Q, a Q вызывает R и в R имеется нелокальная ссылка на X. И Р, и Q, и еще сколько угодно других подпрограмм могут иметь локальную ассоциацию для X. Как сделать правильный выбор при отсутствии каких-либо явных указаний на то, какую из этих ассоциаций нужно использовать. [45]