М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 24
Текст из файла (страница 24)
Преимущество явной статической цепочки в том, что она часто короче, чем динамическая (вспомните здесь о предельном случае рекурсивной процедуры). Однако мы все еще должны осуществлять поиск при каждом обращении к промежуточной переменной. Более эффективное решение состоит в том, чтобы использовать индикатор, который содержит текущую статическую цепочку в виде массива, индексируемого по уровню вложенности (см. рис. 7.10). В этом случае для обращения к переменной промежуточного уровня, чтобы получить указатель на правильную запись активации, в качестве индекса используется уровень вложенности, затем из записи извлекается указатель дна, и, наконец, прибавляется смещение, чтобы получить адрес переменной. Недостаток индикатора в том, что необходимы дополнительные затраты на его обновление при входе и выходе из процедуры.
Возможная неэффективность доступа к промежуточным переменным не должна служить препятствием к применению вложенных процедур, но программистам следует учитывать такие факторы, как глубина вложенности, и правильно находить компромисс между использованием параметров и прямым доступом к переменным.
7.8. Реализация на процессоре Intel 8086
Чтобы дать более конкретное представление о реализации идей стековой архитектуры, рассмотрим вход в процедуру и выход из нее на уровне машинных команд для процессора серии Intel 8086. В качестве примера возьмем:
procedure Main is
Global: Integer;
procedure Proc(Parm: in Integer) is
Local'1, Local2: Integer;
begin
| Ada |
end Proc;
begin
Proc(15);
end Main;
Процессор 8086 имеет встроенные команды push и pop, в которых подразумевается, что стек растет от старших адресов к младшим. Для стековых операций выделены два регистра: регистр sp, который указывает на «верхний» элемент в стеке, и регистр bр, который является указателем дна и идентифицирует местоположение начала записи активации.
При вызове процедуры в стек помещается параметр и выполняется команда вызова (call):
mov ax, #15 Загрузить значение параметра
push ax Сохранить параметр в стеке
call Proc Вызвать процедуру
На рисунке 7.11 показан стек после выполнения этих команд — параметр и адрес возврата помещены в стек.
Следующие команды являются частью кода процедуры и выполняются при входе в процедуру; они сохраняют старый указатель дна (динамическая связь), устанавливают новый указатель дна и выделяют память для локальных переменных, уменьшая указатель стека:
push bp Сохранить старый динамический указатель
mov bp, sp Установить новый динамический указатель
sub sp,#4 Выделить место для локальных переменных
Получившийся в результате стек показан на рис. 7.12.
Теперь можно выполнить тело процедуры:
mov ax,ds:[38] Загрузить переменную Global
add ax,[bp+06] Прибавить параметр Parm
add ax,[bp-02] Прибавить переменную Local 1
mov ax,[bp] Сохранить в переменной Local2
Обращение к глобальным переменным делается через смещения относительно специальной области памяти, на которою указывает регистр ds (сегмент данных). К параметру Parm, который располагается в стеке «ниже» начала записи активации, обращаются при положительном смещении относительно bp. К локальным переменным, которые в стеке располагаются «выше», обращаются при отрицательном смещении относительно bp. Важно обратить внимание, что поскольку процессор 8086 имеет регистры и способы адресации, разработанные для обычных вычислений с использованием стека, то ко всем этим переменным можно обращаться одной командой.
При выходе из процедуры должны быть ликвидированы все изменения, сделанные при входе в процедуру:
mov sp,bp Очистить все локальные переменные
pop bp Восстановить старый динамический указатель
ret 2 Вернуться и освободить память параметров
Указатель вершины стека принимает значение указателя дна и таким образом действительно освобождает память, выделенную для локальных переменных. Затем старый динамический указатель выталкивается (pop) из стека, и bр теперь указывает на предыдущую запись активации. Остается только выйти из процедуры, используя адрес возврата, и освободить память, выделенную для параметров. Команда ret выполняет обе эти задачи; операнд команды указывает, сколько байтов памяти, выделенных для параметра, необходимо вытолкнуть из стека.
Подведем итог: как для входа, так и для выхода из процедуры требуется только по три коротких команды, и доступ к локальным и глобальным переменным и к параметрам является эффективным.
7.9. Упражнения
1. Использует ли ваш компилятор Ada значения или ссылки для передачи массивов и записей?
2. Покажите, как реализуется оптимизация последнего вызова процедуры при рекурсиях. Можно ли выполнить эту оптимизацию для функции факториала?
3. Функция Маккарти определяется следующей рекурсивной функцией:
function M(l: Integer) return Integer is
| Ada |
if I > 100 then return 1-10;
else return M(M(I + 11));
end M;
а) Напишите программу для функции Маккарти и вычислите M(l) для 80</<110.
б) Смоделируйте вручную вычисление для М(91), показав рост стека.
в) Напишите итерационную программу для функции Маккарти.
4. Функция Акерманна определяется следующей рекурсивной функцией:
function A(M, N: Natural) return Natural is
| Ada |
if M = 0 then return N + 1 ;
elsif N = 0 then return A(M -1,1);
else return A(M - 1, A(M, N-1));
end A;
а) Напишите программу для функции Акерманна и проверьте, что А(0,0)=1, А(1,1 )=3, А(2,2)=7, А(3,3)=61.
б) Смоделируйте вручную вычисление для А(2,2)=7, проследив за ростом стека.
в) Попытайтесь вычислить А(4,4) и опишите, что при этом происходит. Попробуйте выполнить вычисление, используя несколько компиляторов. Не забудьте перед этим сохранить свои файлы!
г) Напишите нерекурсивную программу для функции Акерманна.
5. Как получить доступ к переменным промежуточной области действия на процессоре 8086?
6. Существует механизм передачи параметров, называемый вызовом по имени (call-by-name), в котором при каждом обращении к формальному параметру происходит перевычисление фактического параметра. Этот механизм впервые использовался в языке Algol, но его нет в большинстве обычных языков программирования. Что послужило причиной такого решения в языке Algol, и как оно было реализовано?
3
Более сложные
понятия
Глава 8
Указатели
8.1 . Указательные типы
Переменная — не более чем удобная нотация адресования ячейки памяти. Имя переменной является статическим и определено на этапе компиляции: разные имена относятся к разным ячейкам, и не существует способов «вычисления имени», кроме как в определенных видах контекстов, таких как индексирование массива. Значение указательного (ссылочного) типа (pointer type) — это адрес; указательная переменная (указатель) содержит адрес другой переменной или константы. Объект, на который указывают, называется указуемым или обозначаемым объектом (designated object). Указатели применяются скорее для вычислений над адресами ячеек, чем над их содержимым.
Следующий пример:
| C |
int *ptr = &i;
породит структуру, показанную на рис. 8.1. Указатель ptr сам является переменной со своим собственным местом в памяти (284), но его содержимое — это адрес (320) другой переменной i.
Синтаксис объявления может ввести в заблуждение, потому что звездочка «*» по смыслу относится к типу int, а не к переменной ptr.
Объявление следует читать как: «ptr имеет указатель типа на int».. Унарная операция «&» возвращает адрес следующего за ней операнда.
К значению переменной i, конечно, можно получить доступ, просто использовав ее имя, например, как i + 1, но к нему также можно получить доступ путем разыменования (dereferencing)* указателя с помощью синтаксиса *ptr. Когда вы разыменовываете указатель, вы хотите увидеть не содержимое переменной-указателя ptr, а содержимое ячейки памяти, адрес которой содержится в ptr, то есть указуемый объект.
Типизированные указатели
В приведенном примере адреса записаны как целые числа, но адрес не является целым числом. Форма записи адреса будет зависеть от архитектуры компьютера. Например, компьютер Intel 8086 использует два 16-разрядных слова, которые объединяются при формировании 20-разрядного адреса. Разумно предположить, что все указатели представляются единообразно.
Однако в программировании полезнее и надежнее использовать типизированные указатели, которые объявляются, чтобы ссылаться на конкретный тип, такой как тип int в приведенном выше примере. Указуемый объект *ptr должен иметь целый тип, и после разыменования его можно использовать в любом контексте, в котором требуется число целого типа:
inta[10];
a[*ptr] = a[(*ptr) + 5]; /* Раскрытие и индексирование */
a[i] = 2 * *ptr; /* Раскрытие и умножение */
Важно делать различие между переменной-указателем и указуемым объектом и быть очень осторожными при присваивании или сравнении указателей:
int i1 = 10;
| C |
int *ptr1 = &i1; /* ptrl указывает на i1 */
int *ptr2 = &i2; /* ptr2 указывает на i2 */
*ptr1 = *ptr2; /* Обе переменные имеют одно и то же значение */
if(ptr1 == ptr2)... /* «Ложь», разные указатели */
if (*ptr1 == *ptr2) /* «Истина», обозначенные объекты равны */
ptrl = ptr2; /* Оба указывает на i2 */
На рисунке 8.2а показаны переменные после первого оператора присваивания: благодаря раскрытию указателей происходит присваивание указуемых объектов и i1 получает значение 20. После выполнения второго оператора присваивания (над указателями, а не над указуемыми объектами) переменная i1 больше не является доступной через указатель, что показано на рис. 8.26.
Важно понимать различие между указателем-константой и указателем на константный указуемый объект. Создание указателя-константы не защищает указуемый объект от изменения:
inti1,i2;
int * const p1 = &i1; /* Указатель-константа */
const int * p2 = &i1; /* Указатель на константу */
const int * const p3 = &i1; /* Указатель-константа на константу */
p1 =&i2; /* Ошибка, указатель-константа */
*p1=5 /* Правильно, указуемый объект не является
константой */
р2 =&i2; /* Правильно, указатель не является
константой */
*р2 = 5; /* Ошибка, указуемый объект — константа */
рЗ =&i2; /* Ошибка, указатель-константа */
*рЗ = 5; /* Ошибка, указуемый объект — константа */
В языке С указатель на void является нетипизированным указателем. Любой указатель может быть неявно преобразован в указатель на void и обратно, хотя смешанное использование присваиваний типизированных указателей обычно будет сопровождаться предупреждающим сообщением. К счастью, в C++ контроль соответствия типов делается намного тщательнее. Типизированные указатели неявно могут быть преобразованы в указатели на void, но не обратно:
void *void_ptr; /* Нетипизированный указатель */
| C |
char *char_ptr; /* Типизированный указатель */
void_ptr = int_ptr; /* Правильно */
char_ptr = void_ptr; /* Правильно в С, но ошибка в C++ */
char_ptr = int_ptr; /* Предупреждение в С, ошибка в C++ */
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
