Несколько странное условие 5 связано с рекурсивностью типов. Оно делает отношение структурной эквивалентности наибольшим среди отношений, удовлетворяющих условиям 1-4.

П р и м е р:

Пусть

T1=rec([info:int,next:T1])

T2=rec([info:int,next:T2])

Применяя только правила 1-4, получим, что T1 и T2 эквивалентны, если T1 и T2 эквивалентны. Правило 5 заставляет сделать вывод, что T1 и T2 действительно эквивалентны (на основании только правил 1-4 можно сделать и обратный вывод).

Если бы не было ссылочных и, следовательно, рекурсивных типов (как в Фортране или Алголе 60), то определение структурной эквивалентности сводилось бы к условию 1, т.е. к равенству базовых типов.

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

Сначала строится праволинейная грамматика:

1. Для каждого описания идентификатора типа, переменной или параметра declared(I,B,Inf), где Inf равно type(T), var(T) или par(T), типу T ставится в соответствие новый нетерминал t.
2. Если нетерминалу t соответствует базовый тип arr(m,n,T1), то типу T1 ставится в соответствие новый нетерминал t1 и вводится правило t -> arr m n t1.
3. Если нетерминалу t соответствует базовый тип rec([f1:T1, .,fn:Tn]), то типу Ti ставится в соответствие новый нетерминал ti для каждого i и вводятся правила t -> ref i fi ti.
4. Если нетерминалу t соответствует базовый тип ref(T1), где T1=int или T1=real, то вводится правило t -> T1.
5. Если нетерминалу t соответствует базовый тип ref(tid(I,B)), а типу tid(I,B) уже сопоставлен нетерминал t1, то вводится правило t -> ^ t1.

Нетерминалы этой грамматики эквивалентны, если и только если соответствующие типы структурно эквивалентны.

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

Отношение структурной эквивалентности действительно является эквивалентностью, т.к. оно рефлексивно, транзитивно и симметрично. Кроме того, два типа структурно эквивалентны тогда и только тогда, когдаони допускают одни и те же последовательности операций. Это делает такую эквивалентность простой и понятной программистам. Её основным и весьма существенным недостатком является сложный и громоздкий алгоритм проверки эквивалентности. Насколько известно автору, структурная эквивалентность была принята только в языке Алгол 68.

Предикат consist в этом случае определим следующим образом:

consist(T1,T2):-

base_type(T1,BT1),base_type(T2,BT2),

(BT1=int,BT2=real ; % приводимость

equiv(BT1,BT2) ; % эквивалентность

error("Несовместимые типы")).

Именная эквивалентность

При стандартизации языка Паскаль была принята именная эквивалентность. Согласно её определению эквивалентными могут быть только именованные типы, т.е. типы с атрибутами int, real или tid(_,_):

1. Именованный тип эквивалентен сам себе.
2. Если тип T=tid(I,B) имеет описание declared(I,B,T1), где T1 – именованный тип, то типы T и T1 эквивалентны.

Это очень ограничительное определение. Даже в Паскале допустимо присваивание

U:=V,

если переменные U и V описаны как

var U,V: array[1 10]of real,

хотя имеют неименованный тип "массив". Но в том же Паскале этот оператор недопустим из-за неэквивалентности типов переменных, если они описаны как

var U: array[1 10]of real;

var V: array[1 10]of real;

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

В соответствии со сказанным следует внести изменения в правила DC-грамматики для нетерминала type, определяющие атрибут типа. В них включается теперь порождение и описание псевдонимов типа. Для генерации новых "имен" можно использовать самые разные методы; мы здесь воспользуемся предикатом recorda, генерирующем в качестве псевдонима уникальную ссылку на пустой терм, записываемый по ключу alias. описание этого псевдонима типа включается в виде предиката declared.

type(B,tid(A,B)) -->

[array,`[,n(M),`:,n(N),`],of],type(B,T),

{recorda(alias,_,A),

assert(declared(A,B,type(arr(M,N,T)))}.

type(B,tid(A,B)) -->

[record],field(B,F),fields(B,LF),

{correct(F,LF),

recorda(alias,_,A),

assert(declared(A,B,type(rec([F|LF])))},

[end].

type(B,tid(A,B)) -->

[`^,id(I)],

{(type_id2(I,B,B1,type(_));

assert(declared(I,B,type(referred))),

B1=B),

recorda(alias,_,A),

assert(declared(A,B,type(ref(I,B1)))}.

Предикат consist в этом случае определяется следующим образом:

consist(T1,T2):-

T1=int,T2=real ; % приводимость

equiv(T1,T2) ; % эквивалентность

error("Несовместимые типы").

equiv(T,T).

equiv(tid(I,B),tid(I1,B1)):-

declared(I,B,type(tid(I1,B1)));

declared(I1,B1,type(tid(I,B))).

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

Структурно-именная эквивалентность

Этот тип эквивалентности самый простой: эквивалентными считаются типы, имеющие одинаковый базовый тип. Предикат consist в этом случае определяется следующим образом:

consist(T1,T2):-

base_type(T1,BT1),base_type(T2,BT2),

(BT1=int,BT2=real ; % приводимость

BT1=BT2 ; % эквивалентность

error("Несовместимые типы")).

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

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

Примеры