лекции (2004) (1160823), страница 8

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

Текст из файла (страница 8)

Б) Метод ключей и замков.

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

р1 = р2; // копируется и адрес и соответствующий ключ

delete p1; // замку присваивается какое-то недопустимое значение

*p2 (попытка разыменования р2) // уже вызывает ошибку поскольку уже ключ и замок не совпадают

Заметим, что происходит единственное обращение к памяти и данная схема немного более эффективна, чем схема с надгробиями.

3. рассмотрим методы борьбы с висячими ссылками

Создатели языка Ада решали эту проблему с использованием того, что нет смешения типов. Только указатели могут ссылаться на объекты динамической памяти. И как только такие указатели (если являются локальными переменными) прекращают свое существование и объекты, на которые они ссылаются могут прекратить свое существование.

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

1. Метод подсчёта ссылок (активный). Основан на том, что система должна отслеживать все присваивания указателей, передачу их как параметров, и кроме того указатели должны ссылаться только на объекты динамической памяти (проблема смешения адресов решена).

p2 = new T

p1 = p2;(**)

Когда отводиться объект в динамической памяти, выделяется дополнительная память к объекту, в которой содержится количество ссылок на объект. В начале после new(T) счетчик равен нулю. При каждом присваивании счётчик ссылок увеличивается на 1 (в (**) для объекта, на который указывал р2 счетчик увеличивается, а для объекта, на который указывал р1 уменьшается), если указатель является локальным и уходит из области видимости то счетчик уменьшается. Как только счётчик ссылок становится равным 0, объект никому не нужен, в принципе менеджер памяти имеет право его использовать в данный момент. Главный недостаток - с каждым объектом связывается счётчик ссылок и появляются дополнительные накладные расходы.

2. Пассивный метод (применяется в динамических языках типа ЛИСПа) - mark-and-scan, сборка мусора.

При каждом объекте памяти выделяется дополнительный бит, указывающий, используется объект или нет. В начале все объекты помечаются как неиспользованные. Как только объект отводится в память – то используется (бит = 0). При этом объект, на который указывал р1 не помечается как неиспользованный. В определенный момент не хватает памяти для операции new, когда все объекты используемые включается сборщик мусора. Он проходит по всем указателям и помечает реально используемые объекты памяти, а те которые им не помечаются- считаются неиспользуемыми.

Метод хорош минимальными присваиваниями, а недостаток в хитром и долгом алгоритме сканирования, и включения сборщика мусора предсказать нельзя, и нельзя использовать для систем с гарантированным временем отклика.

Реально менеджеры памяти используют комбинацию двух методов. Из-за соображений надежности современные языки используют исключительно сборщик мусора, платя за это эффективностью.

Возникает вопрос – толи отказаться от всяких проблем связанных с висячими ссылками и мусором, введя динамический сборщик мусора, либо сделать работу с указателями чуть менее эффективной, но решить проблему ссылок и разрешить явным образом операторы типа delete. Современные яп предпочитаю решить проблему висячих ссылок и мусора, отказавшись от явного оператора освобождения памяти. Хотя возможно все еще поменяется, так как сейчас большее внимание уделяется более эффективным программам, чем более надежным.

Последнее замечание о простых типах данных.

Нужны ли простые типы данных вообще? Существует язык объектно-ориентированный язык SmallTalk, в котором конструкция 5+3 рассматривается так, объект 5 посылает сообщение "+" объекта 3 и в результате получается объект 8. В SmallTalk есть только тд, встроенные в язык, и все тд являются объектами. У объектов есть методы, и объекты общаются путем посылки сообщений. Сообщение - имя(параметры). Например, у методы «+» есть два параметра – сам объект и объект, которому посылается сообщение. Объект, которому посылается сообщение, просматривает таблицу методов, если у него есть методы, которые обрабатывают полученное сообщение, то происходит некоторые действия (в примере - операция «+»).

Такой стиль программирования очень удобен – когда все рассматривается единообразно, как объекты с методами и свойствами. Однако простые тд остаются в языках, так как все объекты в современных яп размещаются в динамической памяти, и работа с ними весьма накладна. В Си# и Java используется некий компромисс, а именно для каждого простого тд существует класс-обертка. Для каждого тд, встроенного в язык существует тд, который представляет из себя класс (так для int существует класс integer в Java, или int32 в Си#). Понятие обертка это из Java, а для Си# существует CLR, где объявлены и описаны все процедуры и функции с соответствующими классами. Таким образом, когда нам надо работать с объектами простых тд как с переменными и значениями, мы работаем как в Си, если нам нужны их объектные свойства, тогда происходит моментальная обертка, т.е. преобразование в соответствующий класс (в Си# такой процесс получил название Boxing, а обратный Unboxing). В частности в результате в этих языках решена проблема передачи параметров.

Глава 2: Составные ТД

Составные ТД

- Массивы (регулярный тип, последовательность элементов одного и того же типа)

- Записи (в современных яп присутствуют как класс)

- Множества

- Таблицы

- Файлы

- Строки (можно трактовать как массивы символов, но это не совсем удобно).

В современных ЯП:

- Массивы

В документации на языки Java и Cи# массивам там уделено всего несколько страниц. Но в Си# есть тип коллекций ArrayList - чистые объекты, предлагающие функциональность массивов. Теоретически можно вообще обойтись без массивов, однако из соображений эффективности реализации понятие массива сохранено. Хотя мы видим, что современное понятие класса, в общем-то, включает в себя понятие массива.

В Си++ старое понятие массивов сохранено, но средства языка позволяют реализовать объекты-массивы.

- Запись замещена понятием класс.

- Множества, Таблицы, Файлы – объекты из стандартной библиотеки.

В языке Паскаль присутствуют все перечисленные составные тд, кроме таблиц. В Обероне (потомке Паскаля) есть записи(являются объектами), массивы, множества приведены к одному тип set, а таблиц, строк и файлов просто нет.

Современные яп существенно упрощают базисную систему типов при помощи классов.

Массивы

Какие атрибуты есть у массивов. Для простоты будем рассматривать одномерные массивы - вектора. Это последовательность элементов одного и того же типа длины N, основная операция для вектора - индексирование: V[i], V(i) – в Ада, Фортран.

Атрибуты:

1) AB:T; - базовый тип, или тип компоненты вектора

2) L..R - начальный и конечный индексы

3) N – Длина (L – R +1, если L и R имеют некоторую целочисленную интерпретацию)

Реализация массивов в различных яп отличаются только временем связывания соответствующих атрибутов. Во всех языках, которые мы рассматриваем связывание базового типа с типом массива статическое.

Паскаль

В языке Паскаль считается связывание всех атрибутов статическое, определяется во время трансляции и оно не может менять во время выполнения.

type A = array [L..R] of T;

type B = array [L..R] of T;

L, R - константные выражения. Таким образом изменить границы массива, или ео длину во время выполнения никак нельзя. Как следствие, никакой мало-мальски серьёзной программы на Паскале не напишешь. Потому что в любой мало-мальски серьёзной программы на Паскале должны встречаться массивы, каждый объект типа массив должен иметь свой тд, различные тд с различными именами в общем случае в Паскале считаются различными. Объекты типа А и В различны и не совместимы даже по присваиванию. Например, нельзя написать универсальную процедуру скалярного произведения массивов (после введения нового типа (type C = ...) придётся писать новую функцию). Возникает проблема – если процедура обрабатывает массивы, то для каждого типа массивов надо писать свою процедуру обработку.

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

Отметим, что есть еще индексный тип – базовый тип диапазона. Это может быть целочисленный тип, перечислимый тип. Дискретные типы, которые можно использовать так или иначе в Паскаль сводятся к целому либо к перечислимому типу. Кроме того в Паскаль как индексный тип может использоваться символьный тип, который не является ни перечислимым (как в Аде).

Модула2

В языке Модула-2 (ответ на недостатки Паскаля в системном программировании) есть ряд существенных изменений.

Чтобы решить проблему универсальности обработки массивов (см. выше) придумали следующее. Для всех объектов данных массивов, которые не являются формальными параметрами процедур и функций, все атрибуты являются статическими. Для объектов, являющихся формальными параметрами – L и R являются динамическими атрибутами. Введено понятие открытого массива - ARRAY OF T. Мы задаём только тип массива, а его длина остаётся неизвестной, и такой тип данных может появиться только как формальный параметр процедур и функций.

PROCEDURE SUM(VAR X:ARRAY OF REAL): REAL;

Для открытых массивов L,R, N неизвестны во время выполнения, для простоты считается L = 0; R = N-1; существует специальная HIGH(X) - динамически вычисляемая функция, которая дает R. С каждым открыт массивом неявно передается дескриптор массива, в котором хранится его длина. В то же время базовый тип элементов известен. С одной стороны эффективность языка Паскаль сохранена, потому что требования к переменным типа массива он такие же как и в Паскаль – все атрибуты зафиксированы в момент трансляции. А гибкость решена за счет введения для процедур и функций понятия открытого массива.

Ада

Язык Ада является в некотором смысле развитием этого подхода. Там есть понятие типа и подтипа, эти понятии применимы не только к простым тд, но и к массивам.

Объявление массива имеет вид:

type A is array (INDEX range L..R) of T; явным образом указываем тип базового элемента, указываем диапазон range L..R, и указываем базовый тип диапазона.

Если речь идет об объектах типа А, необходимо чтобы все соответствующие значения были статические (тип Т и тип INDEX задаются статически, L и R обязаны быть константными выражениями). Тогда под объекты типа А можно отводить память, присваивать эти объекты.

В Аде существует понятие неограниченного типа, что относится и к массиву. Неограниченный массив:

type B is array (INDEX range <>) of T; можно не ограничивать как раз значение L и R.

• Кроме того есть механизм выведения нового типа:

type NewType is new OLDTYPE; - никак не совместим с типом-родителем OLDTYPE, несмотря на то, что новый тип наследует и множество допустимых значении и набор операций.

• Механизм выведении подтипа:

subtype NewST is OLDT; - полностью совместим по операциям с типом-родителем OLDT, кроме того множество значений и набор операций наследуются.

• И еще в Аде после определения типа может стоять уточнение:

1) уточнение для простого тд

type POSITIVE is new INTEGER range 1..MAX_INT

При этом тип данных POSITIVE абсолютно не совместим с типом INTEGER. И если далее мы укажем диапазон 1..50, то придется дописать к какому типу POSITIVE или INTEGER он относится.

2) уточнение для массива

type C is new B range 1..100;

subtype D is B range 0..10;

subtype E is B range 1..11;

subtype F is B range 1..10;

Мы породили новы тип С и три подтипа, принадлежащих одному типу B. Переменные типа С никак несовместимы с переменными типов D, E, F.

Если у нас есть тип Т и из него механизмом подтипов выведены типы Т1, Т2, Т3, то объекты типа Т совместимы с объектами типов Тi (i=1..3).

Характеристики

Список файлов лекций