Учебное пособие 800529
.pdfПредположим, что мы хотим записать значение V в позицию L, а дескриптор V отличается от дескриптора величины, хранящейся в данный момент в L. Например, L может содержать целое число, в то время как V – вещественное, или обе величины могут быть цепочками литер, но V длиннее цепочки, хранящейся в L. Возможны два разных метода для разрешения конфликта:
1.Преобразовать V так, чтобы дескриптор V стал таким же, как у величины, хранящейся в L; то есть считать, что величины, хранящиеся в L, имеют инвариантный тип данных, и записать преобразованную величину в L как новое значение.
Такой метод типичен для ЯзПр, в которых предусмотрены программные декларации для структур данных, например в Алголе. Поскольку типы данных фиксируются в программе декларациями, они не могут изменяться во время выполнения программы,
ипри конфликтах присваивание должно сопровождаться преобразованием типов (если переменная в левой части целого типа, а в правой – вещественная, то она автоматически округляется до целого). Преимущество такого метода такое же, как при использовании деклараций: улучшение управления памятью из-за статичности ее размера, отводимой под величину, статическая проверка типов, более быстрый доступ.
2.Допустить изменение типа данных величин, содержащихся в L, и тогда записать V в L как новое значение без преобразования. Этот метод с гибким преобразованием типов используется в Сноболе 4 (в нем впервые использован CURSOR), используемый, в основном, для обработки цепочек литер (очень интересный язык). Преимущество метода состоит в исключении ненужных преобразований.
Почти во всех языках кроме явной инструкции присваивания операция присваивания выполняется и в других случаях. Например, операции ввода-вывода порождают присваивания структурам данных новых введенных значений или присваивание файлу вывода новых данных; операция сопоставления с образцом также порождает присваивание (см. далее).
171
3.8.3. Создание структур данных и включение элемента. Операции, создающие новые структуры данных или увеличи-
вающие существующие путем включения новых элементов, имеют первостепенное значение в каждом ЯзПр. Такие операции требуют выделения новой памяти.
Создание структуры данных включает 4 основных шага: а) создание дескриптора для структуры;
б) выделение памяти для самой структуры (то есть цепочки битов);
в) задание значений элементов структуры; г) установление пути доступа к структуре.
Операции включения элемента обычно состоят в: а) выделении памяти для новых элементов; б) задании значений элементов;
в) настройке указателей (не всегда) элемента в существующую структуру.
В предыдущих лекциях мы рассмотрели дескрипторы и способы представления элементов цепочками битов для различных структур данных. Установление пути доступа к новой структуре осуществляется либо путем ассоциации структуры с идентификатором, ее именем в некоторой среде ссылок, либо путем запоминания указателя на эту структуру в некоторой другой существующей структуре, доступ к которой уже налажен.
При этом под средой ссылок понимается определенное множество активных ассоциаций идентификаторов, существующих в данной точке программы в момент ее выполнения. Среда ссылок определяет для каждой встречающейся ссылки соответствующую ей ассоциацию (то есть связь по содержанию). Операции именования, разыменования, активирования (установления принадлежности к среде ссылок) и дезактивирования изменяют среду ссылок.
Среда ссылок имеет область действия, то есть правило для определения среды. Область действия является статической, то есть определяемой при трансляции и динамической, действующей с учетом процесса выполнения программы.
Рассмотрим пример создания структуры и включения элементов в нее применительно к языку Алгол.
172
Декларация в программе указывает момент создания массива (в Алголе других структур нет) во время выполнения программы; оно должно произойти при входе в подпрограмму или блок (begin - end). Например, описание real array A[1:20] в начале блока указывает, что во время выполнения программы при входе в данный блок необходимо создать вектор из 20 элементов. Описания позволяют построить во время трансляции неполные дескрипторы. Создание массива при входе в блок включает формирование недостающей части дескриптора, выделение памяти и установление пути доступа к массиву посредством ассоциации с именем. Только что созданный массив пуст (для него только зарезервировано место в памяти), значения его элементов не определены; он должен заполняться посредством присваивания значений индивидуальных элементов массива.
3.8.4. Уничтожение структур данных и исключение элемента (появление мусора)
Следует отличать операцию уничтожения структуры, делающую структуру логически недоступной, от операций утилизации (восстановления) памяти, занимаемой этой структурой. Во многих ЯзПр это две совершенно отдельные операции; например, память, которую занимают уничтоженные структуры, часто утилизируется (восстанавливается) только тогда, когда она действительно понадобится для создания или модификации других структур. Есть такие механизмы сбора мусора, например в Лиспе. Отмеченные детали не важны при использовании компьютеров по прямому назначению, но для защиты информации в них принципиально необходимо "разбираться в мусоре", остающемся на задворках компьютерных вычислений.
Дополнительной трудностью при обсуждении операции уничтожения является то, что она обычно вызывается неявно, то есть в ЯзПр нет явной операции, с помощью которой программист может уничтожить существующую структуру (исключая операцию FREE в ПЛ/1, но это очень перегруженный язык). Обычно возможна более простая операция, которая разрушает пути доступа к структуре, после чего занимаемая ей память может быть утилизована и повторно использована. Рассмотрим ее суть.
173
При создании структуры данных должен быть также создан и путь доступа к ней (см. п.3.8.3 настоящей лекции, шаг 2); иначе созданную структуру будет невозможно использовать. Обычно структуре дается имя, когда она ассоциируется с идентификатором или когда указатель на нее записывается в другую структуру.
Во время существования этой структуры к первоначально созданному пути доступа могут быть присоединены другие пути доступа, например, с помощью ассоциаций с другими идентификаторами (например, массив передается в подпрограмму и ему присваивается имя формального параметра). Поэтому существование нескольких путей доступа к одной структуре - это обычное явление и попытки отслеживания всех путей трудно реализуемы. В связи с этим, когда для доступа к структуре используется один путь, то невозможно сказать, единственен ли он. В этом состоит главная проблема уничтожения структур. Если предположить, что программисту позволено явно указывать, когда следует уничтожить конкретную структуру данных, то указав путь доступа к структуре, он может уничтожить как путь доступа, так и саму структуру. Однако, если существуют и другие пути доступа к этой структуре, то после ее уничтожения они остаются, указывая на неопределенные области памяти. Такие пути доступа называются висячими ссылками.
Висячие ссылки появляются потому, что утилизация памяти, занимаемой якобы уничтоженной структурой, происходит раньше уничтожения всех путей доступа к ней. Поэтому утилизация должна "подождать". Так рождается вторая, не менее опасная проблема - мусор. Структура-мусор - это такая структура, которая существует, но не может быть использована, поскольку отсутствуют пути доступа к ней.
Поэтому висячие ссылки и мусор - две ключевые проблемы в конструировании операций, уничтожающих структуры данных. В большинстве ЯзПр принято соглашение, что структура данных не может быть явным образом уничтожена программистом. Он может разрушить только путь доступа, сама структура уничтожается неявно, когда исчезнут все пути доступа к ней. При этом следует помнить, что основная причина порождения многих путей - это
174
передача структуры подпрограммам как параметра, когда структура начинает ассоциироваться с другим идентификатором (именем). Поэтому этот вопрос надо рассмотреть.
3.8.5. Операции, определяемые программистом; подпрограм-
мы
Программиста всегда не удовлетворяет набор примитивных операций, встроенных в ЯзПр. Он желает расширить язык путем включения новых операций своей конструкции. Большинство ЯзПр имеют средства для расширения набора операций с помощью подпрограмм.
Можно выделить две категории подпрограмм: подпрограммы, написанные на том же языке, что и главная программа, и подпрограммы, написанные на другом языке, например ассемблере. Последние встречаются реже, но у классных программистов - всегда, ибо тут имеются большие трудности, но обеспечивающие большие возможности повышения гибкости программы. Чаще всего используются заранее скомпилированные подпрограммы.
Подпрограммы подразделяются на подпрограммы-функции, возвращающие результат явным образом, и просто подпрограммы, не возвращающие явного результата, а работающие только через побочные эффекты. Подпрограммы-функции употребляются в выражениях, где результат сразу же используется в качестве входных данных другой операции. Подпрограммы должны вызываться отдельно, обычно с помощью специальной инструкции. При этом под вызовом понимают указание подпрограмме выполнить некоторое вычисление (действие), для которого подпрограмма предназначена.
Операторы подпрограмм называются фактическими параметрами или аргументами. На них не накладывается никаких ограничений и они могут быть любым элементом данных: число, структура или даже другая подпрограмма.
На результаты подпрограмм накладываются бóльшие ограничения. Они могут быть как явные значения функции, либо как побочные эффекты - следствие модификации параметров или нелокальных переменных. Поэтому требуется, чтобы память под результат была выделена до того, как начнется выполнение подпро-
175
граммы. Все осложняется механизмом управления памятью, что и ограничивает выдаваемые подпрограммами результаты. В тех языках, где используются более мощные методы управления памятью (Лисп, Снобол 4, АПЛ) требования к результату не являются столь критическими.
3.8.6. Сопоставление с образцом (зацеп на вирусы) Большинство операций над структурами данных применимо
либо ко всей структуре (например, создание и уничтожение), либо к указанным элементам структуры (например, присваивание). Операции сопоставления с образцом отличаются тем, что часть структуры, с которой необходимо оперировать, они определяют динамически в зависимости от отношений между различными элементами структуры. Это имеет определенное отношение к вирусам и вы должны знать.
Можно выделить два типа операций сопоставления с образ-
цом:
1.Простое сопоставление с образцом. Используется для простой проверки некоторых соотношений между элементами внутри структуры.
2.Сопоставление с образцом и подстановка. Используется для идентификации части структуры, которая затем заменяется указанной новой структурой. Если новая структура является пустым элементом, получается операция исключения, а если она представляет собой исходную часть плюс некоторые новые данные, получается операция включения.
Сопоставление с образцом наиболее часто употребляется для цепочки литер, и поэтому является главной операцией в ЯзПр Снобол 4, основное назначение которого состоит в обработке цепочек литер. Но нужно помнить, что в общем любая программа независимо от языка является функцией (как мы установили "рыхлой", нечеткой), преобразующей входную цепочку литер в выходную цепочку литер.
Простое сопоставление с образцом является элементарной операцией в том смысле, что в ее выполнение не вовлекается явно управление памятью. При добавлении подстановки появляется вся совокупность проблем, связанных с управлением памятью.
176
Операцию сопоставления с образцом можно рассматривать как обобщение операции доступа к структуре данных. При обычном доступе задается набор индексов, определяющих некоторый элемент структуры. Операция доступа использует в качестве операндов структуру и набор индексов и выдает указатель на искомый элемент структуры. Операция сопоставления использует в качестве операндов структуру и образец, определяющий искомый элемент или набор элементов структуры, и тоже выдает указатель на них. Основное отличие состоит в том, что
1)искомые элементы могут отсутствовать в структуре;
2)в образце не обязательно указывается конкретное место искомых элементов в структуре, достаточно указать их положение относительно других элементов.
Образцы являются специальным типом структур данных; они создаются выражениями, определяющими образцы, и функциями, встроенными в ЯзПр. Сама операция задается специальной инструкцией. Операции сопоставления бывают простые (например, найти подцепочку литер заданной длины) и комбинированными из простых за счет конкатенации (сцепления).
3.9.Управление данными
Операции и данные объединяются в программе посредством управляющих структур. Здесь имеется два аспекта: управление последовательностью выполнения операций, называемое управление последовательностью действий и управление передачей данных между группами операций. Это мы и назовем управлением данными.
При этом под структурой управления (синтаксического! )) данными будем понимать те аспекты ЯзПр, которые связаны с их идентификаторами (именами), с определением области их действия, с механизмами выполнения ссылок между программными фрагментами (процедурами, подпрограммами, модулями) и передачи параметров. Необходимость специального рассмотрения этих
) Обратите внимание на «синтаксическое управление». Его еще нет в науке
(Ю.Б.)
177
вопросов объясняется тем, что в отличие от очевидности содержания последовательности действий, управление данными является косвенным и принципиально неоднозначным процессом, ибо в ходе выполнения программы очень трудно предсказать, что эти данные будут представлять из себя. Если бы мы на каждом шагу знали операнды, то есть управляемые данные, то писать программу уже незачем, мы задачу решили бы автоматически. То есть ссылки на данные в программе большей частью косвенные; составляя программу, мы не знаем, какими будут эти данные.
Рассмотрим пример. Пусть программа на Алголе содержит инструкцию
X := Y + Z ґ 2 .
Рассматривая эту инструкцию, мы отчетливо видим три операции, выполняемые последовательно: умножение, сложение и присваивание. Но что можно сказать об операндах этих операций? Ясно, что один из операндов умножения - это число 2, а остальные? Они просто помечены идентификаторами Y, Z и X, которые не являются операндами, а лишь обозначают их по имени. Поэтому центральной задачей управления данными является выяснение смысла операндов, например, Y, при каждом выполнении инструкции присваивания. При этом Y может быть: нелокальной переменной - нужны правила для определения области деклараций; Y может быть формальным параметром - нужно знать методы передачи параметров; Y может быть именем подпрограммы без параметра - нужно знать механизмы передачи результатов подпрограмм. Эти случаи и необходимо рассмотреть.
Центральным вопросом в управлении данными является вопрос о смысле имен, которые должны раскрываться в адрес памяти или указатель регистра
). В самом общем виде имя может означать любое выражение в программе, используемое для задания операнда. Другой аспект имен - это имена переменных с индексами или элементов структур данных. Операция определения структуры, ассоциированной с конкретным именем называется обработ-
) Вот «железные персты» ортогонального (разуму субъекта) компьютера.
178
кой ссылки (на структуру данных). Ее не следует путать с доступом к структуре данных.
Обычно структуре данных дается имя, например массив А. Выражение А[2] порождает двухшаговый процесс, образованный операцией ссылки и последующей операцией доступа к позиции (или к значению).
Операция ссылки определяет объект, который в данный момент обозначается идентификатором А, возвращая в качестве результата указатель на местоположение массива в памяти как целого. Операция доступа по указателю местоположения массива и индексу 2 элемента массива формирует указатель местоположения этого элемента в массиве.
Операции доступа мы рассмотрели выше, сейчас мы займемся обработкой ссылки. При этом мы будем рассматривать имена простых переменных, имена структур данных, имена подпрограмм
иформальных параметров.
Вуправлении данными значительное место занимают ассоциации (или связывание) идентификаторов и элементов программ или данных. Каждую ассоциацию можно представить в виде пары, состоящей из идентификатора и ассоциированного с ним элемента или указателя на этот элемент.
Впроцессе выполнения программы ассоциации конкретного идентификатора (например, Х) претерпевают следующие изменения:
1. Создать первую ассоциацию. Декларация создает первоначальную ассоциацию для Х в начале выполнения программы или при входе в подпрограмму.
2. Сослаться на ассоциацию. Ссылка на Х в программе вызывает операцию обработки ссылки, в которой созданная для Х ассоциация используется для поиска ассоциированного элемента программы или данных, или указателя на этот элемент.
3. Деактивировать ассоциацию. При передаче управления другой части программы ассоциация для Х переводится в неактивное состояние, в котором эта ассоциация продолжает существовать, но на нее нельзя сослаться.
179
4.Вновь активировать ассоциацию. Повторное активирование ассоциации для Х происходит в результате возврата управления соответствующему сегменту программы, после чего вновь можно ссылаться на ассоциацию. Деактивирование и активирование ассоциации могут встречаться много раз.
5.Уничтожить ассоциацию. Ассоциация для Х уничтожается
ина нее более нельзя ссылаться.
6.Повторить шаги 1 - 5. Можно создать другую ассоциацию для Х, сослаться на нее и т.д.
Чтобы ассоциировать идентификатор с элементом данных или элементом программы, необходимо выполнить операцию именования. Она должна предшествовать ссылке, так как операция именования создает ассоциацию для идентификатора, тогда как операция обработки ссылки использует эту ассоциацию для поиска объекта. Противоположная операция, то есть операция уничтожения ассоциации для идентификатора называется разыменование.
Важнейшим источником путей доступа к структурам данных являются ассоциации идентификаторов. Если структура данных уничтожается, оставаясь именованной, то есть ассоциированной с идентификатором, то попытка сослаться в дальнейшем на эту структуру данных через ее бывшее имя приводит к образованию висячих ссылок. Они могут образоваться также, если в других структурах существуют указатели на разрушенную структуру.
Причиной появления мусора может оказаться разыменование структур данных. Мусор возникает, когда все пути доступа к структуре данных утеряны, а память не утилизована, то есть не использована по-новому. Операция разыменования разрушает пути доступа через ассоциации идентификаторов и может привести к образованию мусора. Он может также возникнуть и при уничтожении указателей, записанных в других структурах.
Операции активирования и деактивирования ассоциаций идентификаторов часто путают с операциями именования и разыменования. Чтобы ассоциация могла использоваться в ссылках, она должна существовать (как результат операции именования) и быть активной. Неактивные ассоциации, которые существуют, но временно не могут использоваться в ссылках. Например, блочная
180