А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 97
Текст из файла (страница 97)
Неформально мы определяем, могут ли а и 6 быть сделаны структурно эквивалентными путем замены переменных типов в а и ~ выражениями типов. Подстановка представляет собой отображение переменных типов на выражения типов. Мы записываем результат применения подстановки Я к переменным в выражении типа т как Я(6); см. врезку "Подстановки, экземпляры и унификация". Два выражения типов г1 и ~з унифицированы, если существует некоторая подстановка Я, такая, что Я (~г) = Я (~з). На практике нас интересует наиболь- 6.5.
Проверка типов ший обший унификатор, представляющий собой подстановку, которая налагает наименьшие ограничения на переменные в выражениях. См, алгоритм унификации в разделе 6.5.5. Алгоритм 6.16. Выведение типа для полиморфных функций Вход; программа, состоящая из последовательности определений функций, за которыми следуют вычисляемые выражения. Выражение состоит из применений функций и имен, где имена могут иметь предопределенные полиморфные типы. Выход: выведенные типы для имен в программе.
Метод: для простоты будем работать только с унарными функциями. Тип функции г" (хм хз) с двумя параметрами может быть представлен выражением типа в~ х х аз — Г, где а~ и аз — типы х~ и хз соответственно, а 1 — тип результата г" (тп хз). Выражение ~ (а, 6) может быть проверено путем сопоставления типа а с вп а типа 6 — с аз. Проверяем определения функций и выражения во входной последовательности. Если функция впоследствии используется в выражении, используем выводимый тип функции.
° Для определения функции Гпп Ы~ (Ыз) = Е создадим новые переменные типов а и (1. Свяжем тип а — б с функцией Ыы а тип о — с параметром Ыз. Затем выведем тип для выражения Е. Предположим, что после выведения типа Е о обозначает тип а, а ~3 обозначает тип т.
Выведенный тип функции Ы~ — а — 1. Свяжем квантором Ч все переменные типов, оставшиеся в а — 1 без ограничений. ° Дли применения функции Е, (Ез) выведем типы Е~ и Ез. Поскольку Е, используется в качестве функции, соответствующий тип должен иметь вид а — в'. (Технически тип Е~ должен быть унифицирован с )3- Т, где 3 и г — новые переменные типа.) Пусть 1 — выведенный тип Ез. Унифицируем з и г. Если унификация завершилась неудачей, выражение содержит ошибку типа.
В противном случае выведенный тип Ез (Ез) — в'. ° Для каждого вхождения полиморфной функции заменим в их типах связанные переменные различными новыми переменными и удалим кванторы Ч Получившееся выражение типа является выведенным типом данного вхождения. ° Для впервые встречающегося имени введем новую переменную, обозначающую его тип. и Пример 6.17. На рис, 6.30 выволится тип функции 1еляй.
Корень синтаксического дерева на рис. 6.29 соответствует определению функции, так что мы вводим 486 Глава 6. Генерация промежуточного кода переменные 13 и у и связываем тип 13 — Т с функцией!еп8!Ь, а тип 13 — с х (см. строки 1 — 2 на рис. 6.30). Рнс. 6.30. Выведение типа для функции!еп8й на рнс. 6.28 В правом дочернем узле корня мы рассматриваем Ы как полиморфную функцию, которая применяется к тройке, состоящей из логического значения и двух выражений, представляющих части Феп и е)ве. Тнп Ы вЂ” Ча.Ьоо1еап х а х а — а.
Каждое применение полиморфной функции может иметь свой тип, так что мы вводим новую переменную а; (где 1 указывает на 11) и удаляем Ч (см. строку 3 на рис. 6.30). Тип левого дочернего узла!Р должен быть унифицирован с Ьоо!еап, а типы двух других дочерних узлов — с а,. Предопределенная функция пиП имеет тип Ча.йз! (а) — Ьоо1еап. Мы используем новую переменную типа а„(где и указывает на пий) вместо связанной переменной а (см.
строку 4). Из применения пий к х мы выводим, что тип х Д должен соответствовать йк! (ап) (см. строку 5). В первом дочернем узле 11'тип Ьоо1еап для пиП (х) соответствует типу, ожидаемому конструкцией!8 Во втором дочернем узле тип а, унифицируется с инедег (см. строку 6). Теперь рассмотрим подвыражение 1епйтй (11 (х)) + 1. Мы создаем новую переменную а~ (где ! указывает на !1) для связанной переменной а в типе 11 (см. строку 8). Исходя из применения 11 (х) мы выводим йтп(а~) = Д = йз!(а„) (см. строку 9). 487 6.5.
Проверка типов Поскольку 1епдй (11 (х) ) является операндом +, его тип 7 должен быть унифицирован с 1лгедег (ем. строку 10). Отсюда следует, что тип 1епдй йлг(ст„) — 1л1едег. После проверки определения функции в типе 1елдй остается переменная типа ст„. Поскольку об оо не было сделано никаких предположений, при применении функции вместо нее может быть подставлен любой тип. Поэтому мы делаем ее связанной переменной и записываем тип 1елдй как отто.1144 (Оп) — И!Е8ЕГ.
и 6.5.5 Алгоритм унификации Неформально унификация представляет собой определение, можно ли выражения л и 1 сделать идентичными путем подстановки выражений вместо переменных в л и 1. Проверка эквивалентности выражений является частным случаем унификации; если л и 1 содержат константы, но не переменные, то л и 1 унифицируются тогда и только тогда, когда они идентичны. Алгоритм унификации в этом разделе распространяется на графы с циклами, так что он может использоваться для проверки структурной эквивалентности циклических типовт.
Мы реализуем графотеоретическую формулировку унификации, в которой типы представлены графами. Переменные типов представлены листьями, а конструкторы типов — внутренними узлами. Узлы группируются в классы эквивалентности; если два узла принадлежат одному и тому же классу эквивалентности, то выражения типов, которые они представляют, должны унифицироваться. Таким образом, все внутренние узлы одного и того же класса должны иметь один и тот же конструктор типа, а их соответствующие дочерние узлы должны быть эквивалентны. Пример 6.18.
Рассмотрим два выражения типа ((сЯ1 — стг) х 1тл1 (скз)) — 11л1 (стг) ((стз ст4) к 11л1 (с"3)) ~ ск5 Приведенная далее подстановка Я представляет собой наиболее общую унификацию для этих выражений: х о(х) ст1 СК2 С" 2 скз ск4 ск2 ск5 11т1 (сл2) 'В некоторых приложениях является ошибкой унификация переменной с выражением, солержашим эту переменную. Алгоритм бд 9 допускает такую подстановку. 488 Глава 6. Генерация промежуточного кода Данная подстановка отображает два приведенных выше выражения типа на выражение Исгг — аз) х 1!в! (ггг)) — !гв1 (гэз) Эти два выражения представлены двумя узлами с метками —: 1 на рис.
6.31. Целые числа в узлах указывают классы эквивалентности, которым принадлежат узлы после унификации узлов с номером 1. о Рис. 6.31. Классы эквивалентности после унификации Алгоритм 6.19. Унификация пар узлов в графе типа Вход: граф, представляющий тип, и пара узлов т и и, которые должны быть унифицированы. Выход: логическое значение 1гце, если выражения, представленные узлами т и п, унифицированы; Га!ае в противном случае. МетОД: узел реализуется записью с полями для бинарного оператора и указателей на левый и правый дочерние узлы.
Множества эквивалентных узлов поддерживаются с использованием поля зеп Один узел в каждом классе эквивалентности выбирается в качестве уникального представителя класса эквивалентности, что делается путем установки его поля лег равным нулевому указателю. Поля лег остальных узлов класса эквивалентности указывают (возможно, косвенно, через другие узлы множества) на представительный узел. Изначально каждый узел п принадлежит классу эквивалентности, состоящему из одного этого узла.
Алгоритм унификации, показанный на рис. 6.32, использует две следующие операции над узлами. ° ллй(п) возвращает представительный узел класса эквивалентности, содержащего узел и. ° илюл (т, п) объединяет классы эквивалентности, содержащие узлы гп и п. Если один из представителей классов эквивалентности т и гг является не переменной, то операция ил!оп делает представителем нового класса эквивалентности именно его; в противном случае операция делает представителем любого из представителей исходных классов. Эта асимметрия 489 6.5.
Проверка типов Ьоо1еап ип(1) (АСоде т, Савойе и) ( а =Япй(т) С = йпй (и); СГ ( а = С ) гегцгп Сгие; е)яе С!' ( Узлы а и С представляют один и тот же фундаментальный тип ) гегцгп С ие; е!яе !!' ( а является узлом операции с дочерними узлами а1 и аз, а С является узлом операции с дочерними узлами С1 и Сз ) ( ип1оп (а, С); гетпгп ип(Гу(ем Сс) апд ила(аз, Сз); е!яе !!' (з или С представляет собой переменную) ( ипюп (а, С); гегпгп сгие; е!яе гегпгп Са1зе; Рис.
6.32. Алгоритм унификации операции игйоп важна в связи с тем, что переменная не может использоваться как представитель класса эквивалентности для выражений, содержащих конструктор типа или фундаментальный тип: в противном случае два неэквивалентных выражения могут быть унифицированы посредством этой переменной. Операция ипюп над множествами реализуется простым изменением поля зес представителя одного класса эквивалентности таким образом, чтобы оно указывало на представителя другого класса. Чтобы найти класс эквивалентности, которому принадлежит узел, надо проследовать по цепочке указателей яеС до достижения представителя (узла с нулевым указателем зеС).
Обратите внимание, что алгоритм на рис. 6.32 использует а = дпИ(т) и С = = 11пд(п) вместо самих узлов т и и. Представительные узлы е и С равны, если т и и принадлежат одному классу эквивалентности. Если а и С представляют один и тот же фундаментальный тип, вызов ипф (е, С) вернет Сгие. Если и а, и С являются внутренними узлами для бинарного конструктора типа, мы объединяем их классы эквивалентности и рекурсивно проверяем эквивалентность их соответствующих дочерних узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
