1.3.1. Объекты данных

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

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

ссылки на объекты данных с помощью определенных пользователем имен, а не конкретных адресов памяти;

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

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

Здесь мы четко провели различие между тем, где содержится, и тем, что содержится. Или

┌───┐ ╔══════════════════╗ ╔═════╗

│ │──────>║ Тип │ Указатель ║─────>║ ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

Рис. 1. 3

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

I:=I+1;

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

Таким образом, для обработки объектов данных в программе используются специальные конструкции. Самая важная из них -- переменная, которая определяется тремя характеристиками (рис. 1. 3): ссылкой, однозначно идентифицирующей связанный с переменной объект данных и описывающей тип этого объекта; значением -- хранимым объектом, который обрабатывает программа; именем, под которым переменная известна в программе [49).

Теперь можно показать, как разрешается неоднозначность при использовании имен в таких операторах, как I:=I+1;.Имя I в левой части обозначает ссылку (поскольку оно определяет место для размещения), в правой части -- значение (поскольку оно требуется для вычислений). Таким образом, в правой части неявно выполняется операция определения значения по ссылке.

Переменные вводятся с помощью описаний, например:

I: тип;

┌───┐ ╔══════════════════╗ ╔═════╗

│ I │─────> ║ │ ║─────>║ 0 ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

(не определено)

а)

┌───┐ ╔══════════════════╗ ╔═════╗

│ I │──────>║ │ ║─────>║ ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

б)

Рис. 1.4

По этому описанию создается переменная указанного типа, однако значение ее не задается. Это проиллюстрировано диаграммой на рис. 1. 4, а. Одновременно с созданием переменной можно присвоить ей начальное значение (рис.1. 4,6):

I: тип:= значение;

Рассмотрим возможные способы взаимодействия имен, ссылок и значений переменных. Во-первых, несколько переменных с различными именами и ссылками могут иметь одно и то же значение (рис. 1. 5, а). Во-вторых, несколько переменных с различными именами могут иметь одну и ту же ссылку, а следовательно, и одно и то же значение (рис. 1. 5, б). В-третьих, несколько переменных могут иметь одинаковые имена и различные ссылки (рис. 1. 5, в). (Способы разрешения неоднозначности в последнем случае, а также ситуации, когда возникают такие взаимодействия имен и ссылок, рассмотрим позднее.)

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

┌───┐ ╔══════════════════╗

Х: тип:= 2; │ I │──────>║ │ ║───┐ ┌────────┐

└───┘ ╚══════════════════╝ │───┤ 2 │

┌───┐ ╔══════════════════╗ │ └────────┘

Y: тип:= 2; │ I │──────>║ │ ║───┘

└───┘ ╚══════════════════╝

┌───┐

│ │─┐

└───┘ │ ╔══════════════════╗ ┌────────┐

┌───┐ ├───>║ │ ║─────┤ │

│ │─┘ ╚══════════════════╝ └────────┘

└───┘

╔══════════════════╗ ┌────────┐

┌───>║ │ ║───┤ │

┌───┐ │ ╚══════════════════╝ └────────┘

│ │──┤

└───┘ │ ╔══════════════════╗ ┌────────┐

└───>║ │ ║──┤ │

╚══════════════════╝ └────────┘

которой можно было бы получить доступ к области памяти, где хранится ее значение, и изменить содержимое памяти); она определяется двумя характеристиками: именем и значением (рис.1. 6).

┌─────┐ ╔═════════╗

│ │ ───────────>║ ║

└─────┘ ╚═════════╝

ИМЯ Значение

Рис. 1. 6

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

РI: constant тип:=3.1415926536;

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

1.3.2. Типы данных

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

╔══════════════════╗ ╔═════╗

║ │ ║─────>║ ║

╚══════════════════╝ ╚═════╝

Ссылка Значение

а)

┌───┐ ╔══════════════════╗

│ │─────> ║ │ 0 ║

└───┘ ╚══════════════════╝

ИМЯ Ссылка

(не создан объект данных)

б)

┌───┐ ╔══════════════════╗ ╔═════╗

│ │─────> ║ 0 │ ║─────>║ 0 ║

└───┘ ╚══════════════════╝ ╚═════╝

ИМЯ Ссылка Значение

(не определен тип объекта данных

и, следовательно, его значение)

в)

Рис. 1. 7

объектам данных могут присваиваться логически некорректные значения, так, если объект данных используется для подсчета числа появления некоторого события, то присваивание этому объекту отрицательного значения будет некорректным;

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

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

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

Язык программирования кроме высокой надежности должен обеспечить и адекватное области применения множество типов данных. Современные языки имеют множество предопределенных типов данных и один или более механизмов спецификации типов, определяемых пользователем. Обычно имеются предопределенные целые (integer), действительные (real), символьные (character) и логический (boolean) типы. Над данными числовых типов можно выполнять обычные арифметические операции, операции сравнения; символьные данные можно сравнивать друг с другом; над данными логического типа можно выполнять обычные логические операции. Обозначения операций этих типов обычно совпадают с общепринятыми.

──────────────────────

П р и м е р 1. 1. Описание переменных и запись опе-

раций над данными различных типов:

I: integer:=1;

С: character:='1';

В: boolean:= true;

I+1 I<=2 С>'A' B and false B or true

──────────────────────

Символьные и логический типы определяются перечислением возможных значений -- это так называемые перечислимые типы. Кроме предопределенных перечислимых типов современные языки программирования позволяют определять новые перечислимые типы путем явного указания их значений (констант нового типа).

Имена этих констант выбираются самим программистом из соображений удобочитаемости. Значения перечислимого типа можно сравнивать в порядке перечисления их при определении типа.

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

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

──────────────────

П р и м е р 1. 2. Описание массива из пяти объектов целого типа, записи из трех объектов целого, символьного и логического типов и обращения к четвертому элементу массива и логической компоненте записи:

А: array (1..5) оf integer;

R: record

I: integer;

С: character;

В: boolean;

end record;

А(4) R.В

Можно считать, что операция выбора элемента массива или записи в качестве результата имеет ссылку на этот элемент (рис. 1. 8). Это пример использования безымянных объектов.

──────────────────────────

Важным частным случаем массивов является массив символов, называемый строкой. Для него обычно вводятся специальные более короткие обозначения, а также специальные обозначения для констант. Например, константа СТРОКА представляет строку из 6 символов. Обычно со строками можно выполнять операцию сцепления (т.е. соединения двух строк в одну).

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

┌─────┐ ╦════════════════════╗ ╔═══════════╗

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ A ├────────>║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ┌──>║ ║int │ ║───║──────║──>║ ║ ║

│ │ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │A(4)─┘ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ │ ║ ║ ║

└─────┘ ╚════════════════════╝ ╚═══════════╝

┌─────┐ ╦════════════════════╗ ╔═══════════╗

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ║ ║int │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ R ├────────>║ ║char │ ║───║──────║──>║ ║ ║

│ │ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ ╔══════│══════╗ ║ ║ ╔═════╗ ║

│ │ ┌──>║ ║bool │ ║───║──────║──>║ ║ ║

│ │R.B ─┘ ║ ╚══════│══════╝ ║ ║ ╚═════╝ ║

│ │ ║ │ ║ ║ ║

└─────┘ ╚════════════════════╝ ╚═══════════╝

Рис. 1. 8

Это пример динамических структур данных, которые меняют свою форму при выполнении программы.

──────────────────

П р и м е р 1. 3. Описание объединения объектов целого, символьного и логического типов:

U: union

integer;

character;

boolean;

end union;

╔═════╗

║ 0 ║

┌───┐ ╔══════════════════╗ ╔═════╗══╝

│ U │─────> ║ 0 │ ║────────>║ 0 ║

└───┘ ╚══════════════════╝ ╔═════╗══╝

║ 0 ║

╚═════╝

a)

╔═════╗

║ 0 ║

┌───┐ ╔══════════════════╗ ╔═════╗══╝

│ U │─────> ║ char │ ║─────────>║ 'A' ║

└───┘ ╚══════════════════╝ ╔═════╗══╝

║ 0 ║

╚═════╝

б)

Рис. 1. 9

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

При создании переменной U тип ее не определен (рис. 1. 9, а), поэтому, чтобы начать обрабатывать U, необходимо задать ее тип и значение. Это можно сделать, присвоив ей значение одном из указанных при описании переменной типа, например символ ' А'. При этом тип переменной U станет символьным (рис. 1. 9, б).

────────────────────

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