7.9. Упражнения

1. Использует ли ваш компилятор Ada значения или ссылки для передачи массивов и записей?

2. Покажите, как реализуется оптимизация последнего вызова процедуры при рекурсиях. Можно ли выполнить эту оптимизацию для функции факториала?

3. Функция Маккарти определяется следующей рекурсивной функцией:

function M(l: Integer) return Integer is

Ada

begin

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

begin

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 i = 4;

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 i2 = 20;

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

int *int_ptr; /* Типизированный указатель */

char *char_ptr; /* Типизированный указатель */

void_ptr = int_ptr; /* Правильно */

char_ptr = void_ptr; /* Правильно в С, но ошибка в C++ */

char_ptr = int_ptr; /* Предупреждение в С, ошибка в C++ */

Поскольку в С нет контроля соответствия типов, указателю может быть при­своено произвольное выражение. Нет никакой гарантии, что указуемый объ­ект имеет ожидаемый тип; фактически значение указателя могло бы даже не быть адресом в отведенной программе области памяти. В лучшем случае это приведет к аварийному сбою программы из-за неправильной адресации, и вы получите соответствующее сообщение от операционной системы. В худшем случае это может привести к разрушению данных операционной системы. Ошибки в указателях очень трудно выявлять при отладке, потому что сложно разобраться в абсолютных адресах, которые показывает отладчик. Решение состоит в более строгом контроле соответствия типов для указателей, как это делается в Ada и C++.

Синтаксис

Синтаксические конструкции, связанные с указателями, иногда могут вводить в заблуждение, поэтому очень важно хорошо их понимать. Раскрытие указателей, индексация массивов и выбор полей записей — это средства до­ступа к данным внутри структур данных. В языке Pascal синтаксис самый яс­ный: каждая из этих трех операций обозначается отдельным символом, кото­рый пишется после переменной. В следующем примере Ptr объявлен как ука­затель на массив записей с целочисленным полем:

type Rec_Type =

record

Pascal

Field: Integer;

end;

type Array_Type = array[1 ..100] of Rec_Type;

type Ptr_Type = Array_Type;

Ptr: Ptr_Type;

Ptr (*Указатель на массив записей с целочисленным полем *)

Ptrt (*Массив записей с целочисленным полем *)

Ptrt [78] (*3апись с целочисленным полем *)

Ptrt [78].Field ("Целочисленное поле *)

В языке С символ раскрытия ссылки (*) является префиксным оператором, поэтому приведенный пример записывался бы так:

typedef struct {

int field;

C

} Rec_Type;

typedef Rec_Type Array_Type[ 100];

Array_Type *ptr;

ptr /* Указатель на массив записей с целочисленным полем */

*ptr /* Массив записей с целочисленным полем */

(*ptr)[78] /* Запись с целочисленным полем */

(*ptr)[78].field /* Целочисленное поле */

Здесь необходимы круглые скобки, потому что индексация массива имеет бо­лее высокий приоритет, чем раскрытие указателя. В сложной структуре дан­ных это может внести путаницу при расшифровке декомпозиции, которая ис­пользует разыменование как префикс, а индексацию и выбор поля как пост­фикс. К счастью, наиболее часто используемая последовательность операций, в которой за разыменованием следует выбор поля, имеет специальный, про­стой синтаксис. Если ptr указывает на запись, то ptr->field — это краткая за­пись для (*ptr).field.

Синтаксис Ada основан на предположении, что за разыменованием почти всегда следует выбор поля, поэтому отдельная запись для разыменования не нужна. Вы не можете сказать, является R.Field просто выбором поля обычной записи с именем R, или R — это указатель на запись, который раскрывается перед выбором. Хотя такой подход и может привести к путанице, но он имеет то преимущество, что в структурах данных мы можем перейти от использования самих записей к использованию указателей на них без других изменений программы. В тех случаях, когда необходимо только разыменова­ние, используется довольно неуклюжий синтаксис, как показывает вышеупо­мянутый пример на языке Ada:

type Rec_Type is

record

Ada

Field: Integer;

end record;

type Array_Type is array( 1 .. 100) of Rec_Type;

type Ptr_Type is access Array_Type;

Ptr: Ptr_Type;

Ptr -- Указатель на массив записей с целочисленным полем

Ptr.all -- Массив записей с целочисленным полем

Ptr.all[78] -- Запись с целочисленным полем

Ptr.all[78].Field --Целочисленное поле

Обратите внимание, что в Ada для обозначения указателей используется клю­чевое слово access, а не символ. Ключевое слово all используется в тех немно­гих случаях, когда требуется разыменование без выбора.

Реализация

Для косвенного обращения к данным через указатели требуется дополнитель­ная команда в машинном коде. Давайте сравним прямой оператор присваива­ния с косвенным присваиванием, например:

C

int i,j;

int*p = &i;

int *q = &j;

i=j; /* Прямое присваивание */

*p = *q; /* Косвенное присваивание */

Машинные команды для прямого присваивания:

C

load R1J

store R1,i

в то время как команды для косвенного присваивания:

load R1,&q Адрес (указуемого объекта)

C

load R2,(R1) Загрузить указуемый объект

load R3,&p Адрес (указуемого объекта)

store R2,(R3) Сохранить в указуемом объекте

При косвенности неизбежны некоторые издержки, но обычно не серьезные, поскольку при неоднократном обращении к указуемому объекту оптимизатор может гарантировать, что указатель будет загружен только один раз. В опера­торе

p->right = p->left;

раз уж адрес р загружен в регистр, все последующие обращения могут вос­пользоваться этим регистром:

load R1 ,&p Адрес указуемого объекта

load R2,left(R1) Смещение от начала записи

store R2,right(R1) Смещение от начала записи

Потенциальным источником неэффективности при косвенном доступе к данным через указатели является размер самих указателей. В начале 1970-х го­дов, когда разрабатывались языки С и Pascal, компьютеры обычно имели только 16 Кбайт или 32 Кбайт оперативной памяти, и для адреса было доста­точно 16 разрядов. Теперь, когда персональные компьютеры и рабочие стан­ции имеют много мегабайтов памяти, указатели должны храниться в 32 раз­рядах. Кроме того, из-за механизмов управления памятью, основанных на кэше и страничной организации, произвольный доступ к данным через указате­ли может обойтись намного дороже, чем доступ к массивам, которые распола­гаются в непрерывной последовательности ячеек. Отсюда следует, что опти­мизация структуры данных для повышения эффективности сильно зависит от системы, и ее никогда не следует делать до измерения времени выполнения с помощью профилировщика.

Типизированные указатели в Ada предоставляют одну возможность для оптимизации. Для набора указуемых объектов, связанных с конкретным типом доступа, т. е. для так называемой коллекции (collection), можно задать размер:

C

type Node_Ptr is access Node;

for Node_Ptr'Storage_Size use 40_000;

Поскольку объем памяти, запрошенный для Node, меньше 64 Кбайт, указате­ли относительно начала блока могут храниться в 16 разрядах, при этом эконо­мятся и место в структурах данных, и время центрального процессора для за­грузки и сохранения указателей.

Указатели и алиасы в Ада 95

Указатель в языке С может использоваться для задания алиаса (альтерна­тивного имени) обычной переменной:

C

inti;

int *ptr = &i;

Алиасы бывают полезны; например, они могут использоваться для создания связанных структур во время компиляции. Так как в Ада 83 структуры, осно­ванные на указателях, могут быть созданы только при выполнении, это может привести к ненужным издержкам и по времени, и по памяти.

В Ada 95 добавлены специальные средства создания алиасов, названные типами обобщенного доступа (general access types), но на них наложены ограни­чения для предотвращения создания повисших ссылок (см. раздел 8.3). Пре­дусмотрен и специальный синтаксис как для объявления указателя, так и для

переменной с алиасом:

type Ptr is access all Integer; -- Ptr может указывать на алиас

C

I: aliased Integer; -- I может иметь алиас

P: Ptr := I'Access; -- Создать алиас

Первая строка объявляет тип, который может указывать на целочисленную переменную с алиасом, вторая строка объявляет такую переменную, и третьястрока объявляет указатель и инициализирует его адресом переменной. Такие типы обобщенного доступа и переменные с алиасом могут быть компонента­ми массивов и записей, что позволяет построить связанные структуры, не об­ращаясь к администратору памяти во время выполнения.

* Привязка к памяти

В языке С привязка к памяти тривиальна, потому что указателю может быть присвоен произвольный адрес:

C

int * const reg = Ox4fOO; /* Адрес (в шестнадцатеричной системе) */

*reg = Ox1f1f; /* Присваивание по абсолютному адресу */

Благодаря использованию указателя-константы мы уверены, что адрес в reg не будет случайно изменен.

В Ada используется понятие спецификации представления для явного ус­тановления соответствия между обычной переменной и абсолютным адресом:

Ada

Reg: Integer;

for Reg use at 16#4fOO#; -- Адрес (в шестнадцатеричной системе)

Reg := 16#1 f1 f#; -- Присваивание по абсолютному адресу

Преимущество метода языка Ada состоит в том, что не используются явные указатели.