Контрольные вопросы

1. Какие процедуры и функции следует считать полиморфными?

2. Чем отличаются полиморфные функции от функций, имеющих одинаковые имена?

4.11. Примеры спецификации типов данных

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

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

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

Var день1, день2 : (пн, вт, ср, чт, пт, сб, вс);

в операторе

день1 := день2;

оба идентификатора обозначают переменные, а в операторе

день1 := вт;

второй идентификатор обозначает «сам себя», т.е. идентификаторное значение.

Непосредственным следствием использования идентификаторных значений является введение типа идентификаторов с соответствующими операциями создания и анализа:

тип идентификатор = модуль

[create_ident : функция (первый_символ : буква, следующий_символ : строка_букв_и_цифр) *;

«=», «» : функция (идентификатор1, идентификатор2 : *) логическое].

Предполагается, что в этой спецификации использованы предварительно определенные типы данных «буква», «строка_букв_и_цифр», «логическое».

Операция create_ident вырабатывает идентификатор из буквы и строки букв и цифр. Ввиду частого использования идентификаторов в программах для облегчения работы пользователей во всех языках программирования принято соглашение явно указывать только аргументы этой операции, не отделяя их друг от друга никакими знаками. В то же время вычислитель постоянно пользуется ею при распознавании и формировании внутреннего представления идентификаторов. Поскольку аргументы данной операции являются базисными термами (константами) алгебры слов, она также порождает базисные термы алгебры слов. Благодаря такому свойству всегда возможно прямое вычисление идентификаторных значений, при котором функции  соответствует функция перевода идентификатора во внутреннее представление, а функции  - само внутреннее представление.

Анализирующие операции «=» и «» дают вычислителю возможность сравнивать идентификаторы между собой с целью нахождения определяющего вхождения, проверки уникальности и т.д.

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

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

тип переменная = модуль (Т : тип)

[create_var : функция *;

assign : процедура (идентификатор_переменной : * , значение_переменной : Т);

value : функция (идентификатор_переменной : * ) Т;

«=», «» : функция (переменная1, переменная2 : * ) логическое].

Предполагается, что тип «логическое» определен ранее.

Операция create_var создает новую переменную с неопределенным вторым компонентом. Эта операция может использоваться как вычислителем, так и программистом. Переменные, создаваемые вычислителем, принято называть статическими, а переменные, создаваемые программистами, - динамическими. В Паскале операция create_var предоставляется программисту в виде стандартной процедуры new.

Операция assign устанавливает значение второй компоненты переменной равным некоторому значению ее типа. В языках программирования операция assign известна под названием «оператор присваивания». У этой операции первый операнд всегда имеет тип переменной, а второй – тип ее значений.

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

тип отрезок = модуль (родительский_тип : тип  succ : функция (значение : * ) * ;

«=» : функция (значение1, значение2 : *) логическое,

нижняя_грань, верхняя_грань : *)²

[into : функция (аргумент : родительский_тип) * ;

out : функция (значение : * ) родительский_тип) * ;

first, last : * ;

pred, succ : функция (значение : * ) *;

«=», «», «», «», «», «» : функция (значение1, значение2 : * ) логическое ].

Предполагаем, что используемый в приведенной спецификации тип данных «логическое» был определен ранее.

Тип отрезка требует, чтобы все его аргументы относились к одному и тому же перечислимому типу (отражается указанием в спецификации типа параметра «родительский_тип» функции succ) и сам в свою очередь является перечислимым типом. Параметры «нижняя_грань» и «верхняя_грань» указывают соответственно нижнюю и верхнюю границы отрезка. Функции into и out осуществляют преобразование значения родительского типа в значение типа отрезка и наоборот и в языке программирования изображаются своими аргументами. Операции first, last, pred и succ вырабатывают соответственно первое, последнее, предыдущее и последующее значения типа, при этом значение атрибута first соответствует аргументу «нижняя_грань», а last – аргументу «верхняя_грань». Операция succ входит дважды. Первое вхождение соответствует родительскому типу, второе – определяемому типу. Они должны соответствовать друг другу. Однако второе вхождение учитывает ограничения множества значений, накладываемое типом данных отрезок. Тоже самое можно сказать и про операцию «=». Смысл остальных операций очевиден.

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

тип от1до10 = отрезок (целый, 1, 10)

на Паскале пишут тип от1до10 = 1 .. 10.

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

тип массив = модуль (тип_индекса : тип  first, last : *;

succ : функция(значение : * ) *,³

тип_компонентов : тип  «=» : функция (значение : * ) * ) ⁴

[create_array : функция (n : последовательность( тип_компонентов)) *;

lwb : функция ( m : * ) тип_индекса;

upb : функция ( m : * ) тип_индекса;

component : функция (m : *, i : тип_индекса) тип_компонентов;

«=», «» : функция (m1, m2 : * ) логическое].

Предполагается, что типы данных «последовательность» и «логическое» предварительно получили свое описание.

В качестве типа индекса допускается обычно любой перечислимый тип ограниченной мощности (достаточной для размещения массива в памяти компьютера), что отражается в спецификации типа индекса требованием наличия операций first, last и succ. В качестве области значений допускается любой тип, обладающий операцией «=».

Операция create_array создает значение массива на основе значения аргументной последовательности. Операции lwb (lower bound) и upb (upper bound) вырабатывают соответственно значения нижней и верхней границ массива. Операция component вырабатывает значение компонента массива, соответствующего заданному значению индекса. Переменная типа массива представляет собой совокупность переменных типа компонентов. Операции «=» и «» позволяют сравнивать между собой два однотипных массива.

В языках программирования операция component изображается обычно квадратными скобками вокруг индекса. Таким образом, если  и i – переменные типа массива и типа индекса, соответственно, то операция  [ i ] вырабатывает переменную-компонент, соответствующую индексу i; если же  - константа типа массива, то эта же операция вырабатывает значение компонента, соответствующего индексу i.

Операция конкретизации типа массива типом индекса T_i и типом компонентов T_k вместо канонического массив ( T_i , T_k ) языках программирования приобретает вид array [T_i ] of T_k .

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

тип функция = модуль (параметры_функции : блок_спецификаций, тип_результата : тип)

[create_func : функция (тело_функции : терм тип_результата) *;

appl : функция (функция : * , параметры_функции) тип_результата].

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

Операция create_func на основе терма, вырабатывающего значение типа результата (тела функции), создает конкретную функцию данного типа. Она всегда префиксируется изображением типа функции и составляет с ним единое целое, в языках программирования она называется «описанием функции». Например, требуется образовать функцию f типа

функция (а : целое, b : вещественное) вещественное

с телом «a / b». В канонической форме запись этой операции приобретает вид:

f = функция (а : целое, b : вещественное) вещественное) create_func(a / b);

в языке программирования она приобретает форму описания функции

f = функция (а : целое, b : вещественное) вещественное) начало a / b конец.

Таким образом, первая часть описания функции, а именно

функция (а : целое, b : вещественное) вещественное,

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

Операция appl означает применение (аппликацию) функции к своим аргументам с выработкой значения типа результата. В языках программирования она изображается обычно своими аргументами. Операция применения рассмотренной выше функции f к своим аргументам из канонической формы appl (f, 2, 3.5) в языке программирования запишется как f ( 2, 3.5).

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