Лекции, страница 2

Эти комиксы позволяют обнаруживать ошибки, неочевидные из текста программы. с1 В свою очередь эта графическая иллюстрация может быть выра>кена следующими соотношениями на языках программирования; р . - ь ФР .— — Фс1; р! Г; *р!»г; 0; р ' ' и Р п11; 196 Динамические объекты определенного типа порождаются при выполнении встроенных процедур Паскаля и Си (пелч и ша11ос), фактическим параметром которой является ссылка на элемент этого типа.

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

Состояние памяти, выделенной под этот объект, вообще говоря, остается неопределенным (1 ). В С»е 1 одна из форм оператора пелл позволяет сконструировать объект в ранее выделенной памяти, тем самым функции распределения памяти и создания объекта разделяются. При работе процедуры певуч памягь для динамических объектов выделяется из так называемой «кучи» -- области основной памяти машины, зарезервированной для этой цели.

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

Поэтому, если процедура пелл вызывается многократно (например, в случае зацикливания программы), то может наступить такой момент, когда вся память, предназначенная системой для динамических перелгенпых, будет исчерпана, и программа не еллоу т продолжить работу. В языке Паскаль определена также специальная процедура аароне, уничтожанлцая динамический объект, ссылка на, который передана ей в качестве фактического параметра. 11оэгому обрабогка диналшч ских объектов обычно происходич по след1кнцей схеме: печ (р); 1' порождение динамического объекта р7 ~ р": = ...; 1' обработка динамического объекта р)' 7' лчг1$е1р ); йэрове(р); 1' уничтожение динамического объекта ~ Однако точный результат работы (основной эффект) процедуры с11вроэе в стандарте языка Паскаль нс определен, поэтому реализация этой процедуры целиком зависит от решений, принятых разработчиком системы программирования.

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

маг р, й: ""1"; Ьеи1п пеж(р); Ч: — 1~:. 197 Йвровс(р); 1' р указывает «в никуда,», программист помнит об атом; а тооюс указывает «в никцда», но об этом легко завыть г епй. После уничтожения объекта р обе ссылки на него р и е1 становятся некорректными. Деструктор с11врове мог бы обнулить передаваемую ему ссылку, но это не предусмотрено стандартом языка. Это проблема решается в современных языках сборщиком мусора. Поэтому. необходимо присваивать ссылке значение ш1 непосредственно после вызова с11врове. Альтернативой является использование «умного» указателя (вшаг1 рспп1ег), все копии которого при уничтожении объекта автоматически обнуляются.

Таким ооразом, единственным источником начальных значений ссылочных переменных является процедура типа пеъ -- своеобразное присваивание, совмещенное с порождением динамического объекта. Поскольку ссылочный тип является внутримашинным, непечатным, его значения пе имеют текстовых изображений и не могут быть введены или выведены процедурами геас1 или жг1Се. В Си ссылочный тип хорошо согласован с целым, а целый -- со ссылочным, поэтому ввод-вывод ссылочных переменных осуществляется обычными функциями всап1 и ргш11 (спецификация формата, %р). Конечно же, используя вариантные записи или обьединения, можно наложить в памяти ссылочную и целую переменные и распечатать целочисленное значение ссылки.

Суре рСг2пй — гесогс1 саве Ьоо1еап оГ Га1ве: (ча1: шСеяег); Сгпе: (р1г: шСеяег):, епс1; фшс1пс1е <в1с111Ь.1т> Сурес1еГ пп1оп ( шС ча1: шС* р1г; ) р1,г21п!: Поскольку в языке Си ссылочный тип идентичен адресному, а тот, в отличие от Паскаля, согласован с целым, ссылки могут быть не только напечатаны, по и введены, что может быть применено для задания абсолютных адресов. Поэтому пример на Си пригнет лаконичный вид: 1>г1п11("Значение %<1 находится по адресу %1>", »р1, р1); чаг р1: шСеяег; р21; р1,г2пП,: Ьеяш певуч(1й); р1-: з11; р21.

р1т: — р1; ът1Се1п('Значение„', р1 , .'„находится „по адресу ', р21.ча1: Сгппс(!п(р21.ча!) ! 1п (10.0)) + 1); дбврове(р1); епс1. шС шаш(чоЫ) шС» р1 -- ша11ос~в1яеоГ(шС)): *р1 314; р1г21п1 р21; р21.р1г -- р1: рг1п11("Значение %с1 находится„по адресу %е1", »р1, р21ла1): 1гее (р1); В качестве примера статико-динамического дуализма рассмотрим константы. Казалось бы, значение константы чисто статическое свойство, но в развитых языках программирования (С+ '-) это свойство об"ьекта может быть изкленено в процессе работы программы.

С другой стороны константы можно порождать и уничтожать динамически, т. е. постоянство значения не озна гает фиксированного времени существования. сопвС шС* рог =- пеж шС(100);,г, Указатель на константу, иниииализированную значением 100 *рог =- 150;,'' Ошибка! Попытка изменить константное значение. рсг - пеггг 1пС(200); ~' Указатель иа новую константу со значением 200 шС сопвС* срг - пеиг шС(100);,~У Неизменя мый указатель г срг =- 150:,/',г Теперь по адресу срг' находггтся число 150 срг = пеггг шС(200);,7 Ошибка! Поггытка изменигпь константый адрес сопвС шС сопвС~ срсг == певуч 1пС(100); г','' Неизменяемый указатель на константу *срв' — 150; /,'' Отибка1 срсг = пеиг шС(200);,г'.~' Отиггбка1 Динамическими объектами в основной памяти можно также считать различные процессы, задачи, которые запускаются.

останавливаются, г:инхронизируются, обмениваются данными и взаимодсйствукгт в процессе выполнения программы. Мы рассмотрели явное манипулирование динамическими объектами. Ранее изученная блочная структура с локальными переменными представляла собой неявное динамическое распределение и освобождение памяти, выполняемое языковой средой при входе в блок и выходе из него. Локальные переменные динамически размещаются в стеке, что естественным образом обеспечивает их омонимию. Своеобразным случаем блочной структуры можно считать рекурсивный вызов процедур, при котором неявным образом динамически формируется семейство вложенных блоков со своими наборами независимых локальных переменных.

Стек, в отличие от кучи, предназначен для систематического последовательного выделения и освобождения памяти, в то время как куча рассчитана на беспорядочное размещение ггосвобождепие об ьектов. Естествешго, что весь этот неявный процесс автоматического управления памятью нсдоступен и неподконтролен программисту. Х1етоды динаьпгческого распределения памяти подробно рассматриваются в первом томе монографии Донаггьда, Кнута [63]. Динамические структуры данных, поггезные для распределения памяти, будут изучаться в нашем курсе позднее. Глава 5 Структуры данных 5.1 Уровни описания структур данных При описании какого-либо объекта, (простого или структурного) необходимо четко различать его абстрактные свойства и их конкретную реализацию на данном языке программирования и в данной мщпине ~36, 59, 63, 68, 72~.

Для описания абстрактных свойств рассматриваемого обьекта удобно иметь определение класса всех объектов, обладавших этими свойствами, т. е. определение типа данных ~43~. Функциональной спецификацией какого-либо типа данных называкхг внешнее формальное определение этого типа данных, не зависящее ни от языка программирования, ни от конкретной вычислительной машины.

Дать формальное определение типа данных это значит задать множество значений этого типа, и множество изображений этих значений вместе с правилом их интерпретации (только через изображения можно работать со значениями объектов типа),а также базовое множество атрибутов этого типа,включающее изображения некоторых выделенных значений, операции и их свойства, отношения и их свойства, функции создания, доступа и модификации объектов этого типа Щ. Функциональная спецификация обеспечивает полное описание данного типа, однако в нее нс включаются никакие требования к внутренней организации объектов этого типа, диктуемые особенностями используемых языка программирования и машины.

11апример, функциональная спешлфикапия целого типа вообще определяет множество изображений значений этого типа как последовательность цифр со знаком или без знака, полиномиальную интерпретацию любого такого изображения как числа в позиционной системе счисления с основанием 10, операции (+, †, ~, деление (п1ч и люс1)) с их свойствами (законы ассоциативности, дистриоутивности и т. д.), отношения (=, <>, «,=, »,=) и их свойства, а также ряд функций, аргументами и,~или результатами которых являются значения этого типа [6).