Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

При применении этого способа к фрагменту программы на рис. 8.2 будут получены имена выражений типов переменных, приведенные в табл. 8.1.


Таблица 8.1

next	link
last	link
p	pointer(cell)
q	pointer(cell)
r	pointer(cell)

---

С точки зрения эквивалентности имен переменные next и last имеют один и тот же тип, поскольку с ними связаны одинаковые выражения типа. Типы переменных р, q и r также эквиваленты, но, например, переменные р и next разнотипны, поскольку связанные с ними имена выражений типа различны.

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

• 
  Структурное представление и сравнение типов
  

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

На рис. 8.3 показан пример фрагмента графа структурного представления типов.

С точки зрения структурной эквивалентности все пять переменных в рассматриваемом примере имеют один и тот же тип, поскольку link представляет собой не что иное, как имя для выражения типа pointer(cell).



Рис. 8.3. Связь переменных и узлов в графе типов

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

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

---

Структурная эквивалентность типов в направленных ациклических графах может быть проверена с использованием рекурсивного алгоритма, параметрами которого являются две заданные вершины A и B:

• 
  если A и B есть один и тот же лист (базовый тип), то вернуть истину,
  
• 
  иначе, если и A и B есть конструкторы, последовательно обойти все пары дуг, исходящие из A и B, и:
  

• 
  если найдется хотя бы одна непарная дуга, вернуть ложь;
  
• 
  или, если хотя бы одна пара вершин, в которые ведут эти дуги, не эквивалентна (для каждой такой пары применяется этот же алгоритм), вернуть ложь;
  
• 
  иначе вернуть истину.
  

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

• 
  Кодирование выражений типа
  

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

Например, в первом трансляторе с языка С [6] базовые типы кодируются с использованием четырех битов. Два младших бита обозначают базовые типы: 00 –

---

char, 01 и 10 – integer, 11 – real. Следующие два бита (которые маскируются при большинстве проверок эквивалентности) используются для хранения значений модификаторов длины (short или long) и знака (signed/unsigned).

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

00 – отсутствие конструктора;

01 – указатель (pointer) на тип t, закодированный левее;

10 – массив (array) неопределенной длины элементов типа t;

11 –функция, возвращающая объект типа t(freturns).

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

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

int	int	000000 0001
int function(…)	freturns(int)	000011 0001
*(int function(…))	pointer(freturns(int))	000111 0001
(*(int function(…)))[…]	array(pointer(freturns(int))	100111 0001

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

---

Кодирование из этого примера в принципе может быть расширено для включения типов записей и объединений (struct и union). При этом каждая запись при кодировании рассматривается как базовый тип; но отдельная последовательность битов кодирует тип каждого поля записи.

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

5. 
   Среды ссылок периода исполнения
   

Вся совокупность объектов, значения которых доступны из произвольной точки текста программы, в литературе называется средой ссылок. Различают два понятия – текстуальная среда ссылок (или среда ссылок периода трансляции; иногда ее называют статической, или лексической) и динамическая, или среда ссылок периода исполнения программы. Задача транслятора – спроецировать текстуальную среду ссылок на среду ссылок периода исполнения.

Строение среды ссылок периода исполнения и способ отображения на нее текстуальной среды определяется тем, как разработчики языка отвечают на следующие вопросы:

1. 
   Допускаются ли рекурсивные вызовы функций?
   
2. 
   В какой момент создаются локальные объекты функций?
   
3. 
   Что происходит с локальными переменными при возвращении управления из функций?
   
4. 
   Может ли функция обращаться к нелокальным объектам, не являющимся ее фактическими аргументами?
   
5. 
   Каким образом в функцию передаются параметры?
   
6. 
   Может ли функция быть передана в качестве параметра?
   
7. 
   Может ли функция быть возвращена в качестве результата?
   
8. 
   Может ли память выделяться динамически, по явному запросу программы?
   
9. 
   Должна ли динамически выделенная память освобождаться также по явному запросу?
   

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

Среду ссылок периода исполнения будем рассматривать применительно к компиляторам. Интерпретаторы моделируют программно те же самые процессы, которые реализуются аппаратно-программным способом при исполнении скомпилированной программы.

---