лекции (1998) (Буров), страница 6

пусть нам надо найти в матрице максимальный элемент и что-то с ним сделать. Не имея ссылочного типа мы бы написали функцию, возвращающую координаты i,j максимального элемента в матрице, но гораздо удобнее поступить следующим образом:

double& Max(m&) { // m - матрица, но m может быть, например, классом

...

return m[i][j];

}

...

Max(x)=0.0; // это выражение корректно!

И реально после выполнения функции будет возвращено значение ссылки на максимальные элемент.

Поскольку таким образом мы имеем в руках механизм динамического вычисление ссылок, то это сразу расширяет мощность языка C++.

Чем еще ссылка лучше или удобнее указателя? Пусть мы пишем структуру данных, элемент которой ссылается на другую структуру данных. Например, возьмем дерево: довольно часто, вместо того, чтобы осуществлять поиск родителя, удобнее иметь обратную ссылку. Естественно, традиционная схема реализует это с помощью понятия указателя. Чем это плохо? Тем, что указатель может иметь какое угодно значение, вообще его не иметь или указыывать не туда. Ссылку же мы должны инициализировать в момент создания объекта (очевидно, что родитель уже есть), а за счет того, что ссылка всегда указывает на нужный нам объект и значение ссылки изменить нельзя, мы избегаем целого ряда проблем, связанных с возможными изменениями указателей. Кроме того, удобнее и нагляднее писать p.x, чем p->x.

Заметим, что можно делать ссылку и на динамический объект:

T& x=*new T;

Теперь x абсолютно эквиланетен вновь созданному объекту. Чтобы его удалить, мы можем написать:

delete &x; //совершенно корректная операция

Лекции 6, 7

Указатели и ссылки – по сути одно и тоже, т.к. их множество значений совпадает. Это адреса некоторых объектов в памяти. Основное отличие этих типов – набор операций. Ссылки обладают только операцией инициализации. Ссылки служат для доступа к объекту, время жизни которого больше либо равно времени жизни ссылки. Указатели обладают большим набором операций.

Давайте рассмотрим, как ведут себя указатели в различных языках программирования, поскольку здесь есть некоторый разнобой, который вытекает из одного факта: концепция указателя слишком низкоуровневая. При этом указатель имеет большой набор операций, и с этим связана его потенциальная ненадежность.

В чем выражается эта ненадежность? Для этого задумаемся: зачем нужны указатели? Для чего нужен механизм ссылок, приблизительно ясно. С помощью ссылок реализуются соответственные отношения (например, в случае дерева, если есть потомок, значит должен быть предок). Указатели необходимы в некоторых случаях для организации рекурсивных структур данных – типичный пример дерево:

t := | пусто | (n, t1, t2) n - узел,

t1,t2 – поддеревья

В книге Вирта "Алгоритмы + структуры данных" представлен способ представления дерева без понятия указателя. Мы можем представлять дерево в виде массива. Для определения таких структур данных, как сеть, указатели необходимы, т.к. без них в линейной памяти поместить такую структуру очень тяжело. Кроме того, указатели нужны, когда время жизни объекта должно быть потенциально меньше времени жизни соответствующего указателя.

Указатель более динамичен, чем ссылка, следовательно, нужны средства для реализации динамических структур данных. Для этого используется понятие динамической памяти.

Память делится на несколько классов:

• Статическая (static)– объекты этой памяти находятся в течение всего времени выполнения программы.

• Квазистатическая – время жизни объектов этой памяти меньше времени выполнения программы, однако, в программе (исходя из ее текста) можно проследить отрезок жизни объекта (в Си – это объекты класса auto).

• Динамическая – для объектов динамической памяти нельзя (в общем случае) выделить те части программы, в которых они существуют.

Объектам статической и квазистатической памяти можно давать имена. Объектам динамической памяти давать имена затруднительно (исключение S = &(new Т)).

А стоит ли разделять объекты из этих трех классов? На объекты из динамической памяти с помощью имен обычного рода ссылаться невозможно. Указатель может ссылаться на объекты динамической памяти. Стоит ли разрешать указателю ссылаться на объекты статической памяти? С этой точки зрения есть два подхода.

Первый подход – всеразрешающий (подход языка Си и C++), указатель является просто адресом места памяти. Это плохо тем, что по самому указателю никак нельзя определить, к какому классу памяти принадлежит соответствующий объект. Ошибка, типичная для этого случая:

p=&a;

………

free(p); //удаляется объект статической памяти

Такую ошибку трудно отловить, потому что она проявляется не сразу. Возможность ссылаться на любой объект памяти сильно понижает надежность и безопасность систем. Если в языке есть операция взятия адреса переменной, следовательно, он поддерживает эту абсолютистскую концепцию (Turbo Pascal имеет операцию ADDR(), и поэтому менее надежен, чем стандартный Паскаль, в котором этой операции нет).

Языки, которые большее внимание уделяют надежности, принимают другую концепцию. В стандартном Паскале указатель может получить свое значение только двумя способами: p1:=p2; и p1=new(T). Естественно, что указатель всегда указывал на объекты динамической памяти. Эта концепция также была реализована в языке Ада 83:

type PT is access T;

PT := new T;

Тем не менее, на стандартном Паскале по большому счету никто никогда не программировал. Все программировали на реализациях Паскаля, которые расширяли язык. Есть статья Брайана Кернигана "16 причин, почему я люблю Паскаль", в которой автор указал причины, по которым на Паскале нельзя разрабатывать серьезные программы. В языке Модула-2 на первый взгляд поддерживалась та же концепция, однако, там имелся тип ADDRESS, значениями которого были любые адреса в памяти. Любой указатель можно было привести к этому типу и обратно. Это было дыркой в типовой системе языка. Дело в том, что функции Модулы-2 allocate и deallocate работали именно с типом ADDRESS, иначе пришлось бы писать такие функции для любого типа. Хотя Вирт определил этот тип для ограниченных случаев, программисты использовали его очень широко, к великому разочарованию автора.

Разработчики языка Ада-95 попытались ослабить эту концепцию. Они ввели понятие совмещенных элементов. Иногда хочется адресовать объекты из статической и квазистатической памяти, но в то же время, хотелось бы, чтобы можно было бы разобраться, к какому классу памяти относится указатель. Пример демонстрирует решение разработчиков:

type P_INT is access INTEGER; // Тип указателей на динамические объекты

type PP_INT is access all INTEGER; // Тип указателей на любые объекты

I : aliased INTEGER; // На эту переменную можно ссылаться указателем

J : INTEGER; // На эту переменную нельзя ссылаться указателем

P1 : P_INT; //Этот указатель получает значение только от NEW

P2 : PP_INT; //Этот указатель может содержать адрес только aliased-переменной или динамического объекта

P2: =I'Access; // Можно

P2: =J'Access; // Нельзя!

P1: =I'Access; // Нельзя!

Вообще говоря, понятие указателя можно надежно внедрить в типовую систему языка программирования, если указатель ссылается только на динамические объекты, а статические и квазистатические объекты адресовать нельзя. Однако, в системах, в которых допускается явное освобождение динамической памяти программистом, мы сталкиваемся с двумя проблемами, которые в общем случае преодолеть очень тяжело:

1. Проблема сборки мусора.

p1 = new T ;

p1 = p2;

2. Проблема висячих ссылок.

p = new T;

p1 = p;

delete p;

Эти проблемы можно решить с помощью алгоритма динамической сборки мусора. Т.е. необходимо отказаться от оператора освобождения динамической памяти, и ответственность за освобождение памяти ложится на соответствующую систему времени выполнения (RTS). В чисто динамических языках все операции над объектами производились в динамической памяти. Возьмем язык Лисп: пусть есть два списка S1 и S2, и к ним применяется операция объединения списков (CONS S1,S2). Результирующий список также создается в динамической памяти, причем он создается без копирования, как ссылка на два списка. При этом, какие то объекты также могут ссылаться на S1 и S2. Поэтому Лисп может работать исключительно на алгоритме динамической сборки мусора.

Вплоть до 70-х годов считалось, что алгоритмы сборки мусора неприменимы к языкам программирования, предназначенным для написания эффективных программ. Первые реализации Лисп-систем примерно 65-70% времени тратили на сборку мусора. Кроме того, этот алгоритм включается в априори недетерминированный момент времени (часто, в самый неподходящий момент). В 70-е годы появились действительно эффективные алгоритмы динамической сборки мусора в реальном времени. Интересно, что в языке Ада операция освобождения памяти в сам язык явно не прописана. Создатели этого языка понимали (исходя из концепции надежности), что освобождение динамической памяти – опасная вещь, но в тоже время динамически собирать мусор в то время было еще накладно. Поэтому создатели языка Ада пошли на компромисс – они внедрили в язык некий стандартный пакет, в котором в частности, была процедура с очень длинным названием UNCHECKED_DEALLOCATION(p) (чтоб боялись). Ответственность за корректность освобождения памяти, при использовании этой процедуры, ложилась на программиста. Большинство реализаций Ады не использовали динамическую сборку мусора, и поэтому проблемы с мусором и висячими ссылками сохранились.

В конце 80-х годов появился язык Оберон, прямой наследник Модула-2. В этом языке была процедура new, но не было процедуры dispose. Т.е. Вирт, который сконструировал Оберон исключительно для целей системного программирования (а это требует эффективности), предполагал динамическую сборку мусора. В языке Java также операции освобождения динамической памяти нет (хотя можно поспорить об эффективности этого языка). Тот факт, что в языке явно зафиксирована концепция динамической сборки мусора – это признак сдвига в позитивном направлении.

А можно ли реализовать динамическую сборку мусора в таких языках, как Си или C++? Страуструп, когда описывал историю развития C++, с некоторой завистью говорил о том, что хорошо бы конечно, если бы в язык вошла концепция динамической сборки мусора, однако эта концепция в язык так и не вошла. Что препятствует этому в C++? Прежде всего – это концепция указателя. Для надежного алгоритма динамической сборки мусора требуется, чтобы понятие указателя было ограничено (см. выше подход стандартного Паскаля, Ады-83,95), т.к. адресная арифметика и адресная операция сводят на нет эффективность сборки мусора.

Поэтому, естественно, что в указатель включено понятие ссылки. Ссылка - значительно более четкое и определенное понятие. Но тогда получается, что все объекты нужно разделить более жестким образом. И это было сделано в более современных языках программирования - прежде всего, в языке Java. Разработчики поступили революционно. С одной стороны, с точки зрения средств развития, язык Java во многом похож на C++, с другой стороны, главное отличие языка Java – это то, что концепции указателя вообще нет. А что же тогда делать с достаточно сложными объектами? В языке Java сделано очень просто: все типы делятся на два класса – простые типы и ссылочные типы. К простым типам относятся все арифметические типы, тип Boolean и символьный тип. Ссылочные типы данных - это массивы, классы и т.н. интерфейсы. При этом память под ссылки отводится динамически. При объявлении массива (T[] a;) размер его не указывается. Мы должны указать длину массива и расположить объект явно, выполняя инициализацию (a= new T[20]). После этого мы можем использовать этот массив, и в том числе отвести под него другой объект (a= new T[12]). То же самое относится к классам и интерфейсам.

Интересно, что подобного рода подход находит отражение и в языках, которые эволюционируют. Например, Turbo Pascal вначале был языком с синтаксисом Паскаля, который использовал средства, похожие на средства языка Си, и модульная структура которого, была очень похожа на модульную структуру языка Модула-2. Интересно, что язык программирования Borland Pascal with Objects (язык программирования системы Delphi) – это уже не тот старый Turbo Pascal. Это язык, который следует, хотя и не до конца, идеологии Java. Основное понятие класса в Delphi полностью соответствует понятию класса в Java. Точно также, все классы являются потомками одного класса TObject (в Java это класс Object). Любой объект типа класс – это всегда ссылка, и точно также после описания объекта этого класса, его надо инициализировать (a = new T). Точно также, все классы Delphi находятся в динамической памяти. Отличие в том, что в Java есть динамическая сборка мусора, а в Delphi – ее нет. У любого класса Delphi, наследника TObject, есть метод Free, который позволяет освободить память, и программист обязан рано или поздно этот метод задействовать. В этом плане, все проблемы висячих ссылок и мусора в Delphi остаются (хотя Delphi эффективнее Java).