Разработка компиляторов
Эквивалентность типов
Необходимой частью контроля типов является проверка эквивалентности типов (equivalence of types) . Крайне необходимо, чтобы компилятор выполнял проверку эквивалентности типов быстро.
Структурная эквивалентность типов (Structural equivalence of types) . Два типа называются эквивалентными, если они являются одинаковыми примитивными типами, либо они были сконструированы применением одного и того же конструктора к структурно эквивалентным типам. Иными словами, два типа структурно эквивалентны тогда и только тогда, когда они идентичны. Проверить, являются ли два типа структурно эквивалентными, можно следующей процедурой:
bool sequiv (s, t) { if (s и t - два одинаковых примитивных типа) { return true; } else if (s == array (s1, s2) && t == array (t1, t2)) { return sequiv (s1, t1) && sequiv (s2, t2); } else if (s == s1*s2 && t == t1*t2) { return sequiv (s1, t1) && sequiv (s2, t2); } else if (s==pointer (s1) && t == pointer (t1)) { return sequiv (s1, t1); } else if (s==proc (s1, s2) && t == proc (t1, t2)) { return sequiv (s1, t1) && sequiv (s2, t2); } else { return false; } }
В некоторых языках типам можно давать имена, которые иногда называют индикантами типа. Рассмотрим пример программы на языке Pascal:
type link = ^cell; var next: link; last: link; p: ^cell; q, r: ^cell;
Возникает вопрос, одинаковые ли типы имеют описанные переменные? К сожалению, ответ зависит от реализации, поскольку в определении языка Pascal не определено понятие "идентичные типы". В принципе здесь возможны две ситуации. Одна из них связана со структурной эквивалентностью типов. С этой точки зрения все объявленные переменные имеют одинаковый тип.
Второй подход связан с понятием эквивалентности имен (name equivalence). В этом случае каждое имя типа рассматривается как уникальный тип, таким образом, два имени типов эквивалентны, если они идентичны. При таком подходе переменные p , q , r имеют одинаковый тип, а переменные p и next - нет. Обе эти концепции используются в различных языках программирования. Например, Algol 68 поддерживает структурную эквивалентность.
Проблемы, возникающие в Pascal'е, связаны с тем, что многие реализации связывают с каждым определяемым идентификатором неявное имя типа. Таким образом, приведенные объявления некоторыми реализациями могут трактоваться следующим образом:
type link = ^cell; np = ^cell; npg = ^cell; var next: link; last: link; p: np; q, r: npq;
