2. Средства описания данных

Средства описания и использования данных -- одна из важнейших составных частей языков программирования. На развитие средств описания данных большое влияние оказали языки ПЛ/1, Паскаль, Ада. Особую значимость имеют вопросы типизации языков [31, 50]. Конкретные типы данных, их использование рассматриваются в [3, 5, 31, 36, 39, 49, 51 -- 55].

2.1. Типизация языка

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

В современных языках программирования эффектив-

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

2.1.1. Определение типа

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

array(1..10) of integer и array(1..11) of integer

Для языка Паскаль ответ на этот вопрос положительный, а для ПЛ/1 -- отрицательный. В языке Паскаль при вызове некоторой процедуры, у которой есть параметр-массив, этому параметру может соответствовать аргумент лишь одного из двух указанных типов данных, в языке ПЛ/1 эту процедуру можно вызвать с аргументом как первого, так и второго типа. Этот пример свидетельствует о важности определения типа с точки зрения практического использования языка.

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

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

если дана переменная некоторого типа, то можно определить и изменить ее текущее значение;

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

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

Если два типа отличаются с точки зрения перечисленных моментов, то будем считать их различными. Таким образом, мы небудем считать одинаковыми приведенные выше типы, так как невозможно определить операцию сравнения на равенство, удовлетворяющую общепринятым свойствам (например, транзитивности, инвариантности относительно функциональных преобразований x=y => f(x)=f(y) и т.д.). Этот подход существенно упростит ответы на ряд вопросов, возникающих при изучении семантики языков программирования.

Определение нового типа будем записывать следующим образом:

type имя_типа is описание_типа;

Как конкретно описываются различные типы, рассмотрим позднее.