2.1.4. Эквивалентность типов

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

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

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

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

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

П р и м е р 2. 1. Влияние способа определения эквивалентности типов:

type ТАБЛ1 is array (1.. 10) of integer;

type ТАБЛ2 is array (1.. 10) оf integer;

Х: array(1.. 10) оf integer;

Y: ТАБЛ1;

Z: ТАБЛ2;

В случае эквивалентности по структуре типы переменных Х, Y, Z будут считаться одинаковыми, а в случае эквивалентности по имени -- различными.

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

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

type Т is array (1.. N) of integer;

..................

N:=5;

block

use Т: type, N: in out integer;

X: Т;

begin

N:=10;

block

use Т: type;

Y: Т;

begin

..............

end block;

................

end block;

Типы переменных Х и Y неэквивалентны по имени. Если переменной N внутри блока присвоить вместо 10 значение 5, то типы переменных Х и Y будут эквивалентны по имени.

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

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

П р и м е р 2. 2. Влияние параметров на проверку именной эквивалентности:

type ТАБЛИЦА(Т:type; M, N:integer) is array(M.. N) of Т;

Х: ТАБЛИЦА(integer, 1, 10);

Y: ТАБЛИЦА(integer, 1, 11);

Z: ТАБЛИЦА(real, 1, 10);

Здесь переменные Х, Y, Z имеют неэквивалентные по имени типы, так как у них разные аргументы.

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

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

Далее будем использовать эквивалентность по имени, как это реализовано, например, в языке Ада.

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

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

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

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