Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214
 Скачать 452.53 Kb.
|
|
С точки зрения эквивалентности имен переменные 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.) примеры выражений типа в тексте программы (первый столбец), во внутреннем представлении транслятора (второй столбец) и соответствующих им кодов (третий столбец):
Рис. 8.4. Примеры кодированных выражений типа Такое представление является чрезвычайно компактным (по сравнению и с именным, и со структурным) и отслеживает последовательность применения конструкторов, появляющихся в любом выражении типа. Две различные последовательности битов не могут представлять один и тот же тип, поскольку при этом различны либо базовые типы, либо примененная к ним последовательность конструкторов. Тем не менее разные типы могут иметь одну и ту же последовательность битов – в силу того, например, что размеры массивов и аргументы функций не представлены в данной системе кодирования. Кодирование из этого примера в принципе может быть расширено для включения типов записей и объединений (struct и union). При этом каждая запись при кодировании рассматривается как базовый тип; но отдельная последовательность битов кодирует тип каждого поля записи. При использовании кодированного представления типов задача выявления эквивалентности резко упрощается, так как вместо сравнения имен типов (с предварительным приведением к каноническому представлению) или рекурсивной обработки вершин графа надо всего лишь сравнивать числа, поставленные в соответствие именам типов. Среды ссылок периода исполнения Вся совокупность объектов, значения которых доступны из произвольной точки текста программы, в литературе называется средой ссылок. Различают два понятия – текстуальная среда ссылок (или среда ссылок периода трансляции; иногда ее называют статической, или лексической) и динамическая, или среда ссылок периода исполнения программы. Задача транслятора – спроецировать текстуальную среду ссылок на среду ссылок периода исполнения. Строение среды ссылок периода исполнения и способ отображения на нее текстуальной среды определяется тем, как разработчики языка отвечают на следующие вопросы: Допускаются ли рекурсивные вызовы функций? В какой момент создаются локальные объекты функций? Что происходит с локальными переменными при возвращении управления из функций? Может ли функция обращаться к нелокальным объектам, не являющимся ее фактическими аргументами? Каким образом в функцию передаются параметры? Может ли функция быть передана в качестве параметра? Может ли функция быть возвращена в качестве результата? Может ли память выделяться динамически, по явному запросу программы? Должна ли динамически выделенная память освобождаться также по явному запросу? Возможный спектр ответов на эти очень широк. В последующих разделах будут рассматриваться в основном типичные решения и вкратце обсуждаться последствия других возможных ответов на данные вопросы. Среду ссылок периода исполнения будем рассматривать применительно к компиляторам. Интерпретаторы моделируют программно те же самые процессы, которые реализуются аппаратно-программным способом при исполнении скомпилированной программы. Будем считать, что для исполнения программы операционная системы компьютера выделяет один связный блок элементов памяти. Способ выделения этого блока (будем называть его памятью задачи) и его отображения на физическую память компьютера может быть различен для разных операционных систем и тем более – для разных аппаратных платформ. Если программа запускается неоднократно, то вполне вероятно, что при разных запусках место расположения памяти задачи в физической памяти компьютера будет различным. Ясно, что в этих условиях транслятору не может быть известно будущее местоположение программы в памяти. Известными могут быть: максимально возможный размер памяти задачи; ограничения на использование некоторых фрагментов этой памяти, занятых модулями поддержки периода исполнения; аппаратные особенности (направление роста аппаратного стека, количество байт, извлекаемых из памяти за одно обращение и, соответственно, рекомендации по выравниванию объектов, и т.д.). Некоторые возможные варианты внутреннего устройства памяти задачи для разных программно-аппаратных платформ представлены на рис. 8.5 (предполагается, что адреса памяти возрастают по направлению сверху вниз). Здесь под функциями понимается совокупность исполняемых инструкций, под областью подгрузки – фрагмент памяти, выделенный для динамически подгружаемых в процессе исполнения программы библиотек (тоже совокупностей функций), под кучей – специально организованная область памяти, блоки которой выделяются/освобождаются динамически по явным запросам из программы. Статические данные – совокупность объектов, существующих в течение всего времени работы программы (в некоторых языках в явном виде возможность использования статических данных может отсутствовать). Аппаратно реализуемый стек используется многопланово. В частности, именно в стеке, как правило, размещаются локальные данные функций.
Рис. 8.5. Варианты размещения совокупностей объектов в памяти задачи Организация памяти образа задачи, представленная на рис. 8.5 (все варианты), предполагает, что память времени исполнения состоит из единого непрерывного блока, выделенного программе при запуске. При этом суммарный размер стека и кучи, обычно растущих навстречу друг другу в процессе исполнения программы, должен быть достаточно большим, чтобы эти две области никогда не пересекались. Столкновение границ стека и кучи (т.е. пересечение этих областей) обычно приводит к аварийному завершению программы, поскольку для ее выполнения оказалось недостаточно отведенной системой памяти. Для обнаружения такой ситуации предусматриваются программные и/или аппаратные средства контроля значений границ стека и кучи. В этих условиях при трансляции логично и естественно считать, что адресация памяти задачи для транслятора начинается с нуля и что процессор компьютера обеспечивает эффективное отображение такой памяти на любой предоставленный операционной системой блок. Именно на такие потребности запуска и исполнения программ и ориентированы базируемые и индексируемые способы адресации памяти современных процессоров, обеспечивающие «на лету» модификацию адресов, сформированных трансляторами, в реальные адреса памяти. Заметим, что термин «реальные» здесь относится только к адресам памяти внутри образа выполняемой программы. Фактическая система адресации памяти может быть значительно сложнее и предусматривать страничную, сегментную либо странично-сегментную организацию виртуальной памяти, при которой последовательно расположенным областям (страницам или сегментам) образа памяти ставятся в соответствие участки физической памяти компьютера, выделяемые операционной системой по мере необходимости и возможности. При этом отнюдь не обязательно весь образ программы в течение всего времени ее исполнения присутствует в оперативной памяти. Делается это «прозрачным» для исполняемых программ образом и поэтому на логику работы трансляторов влияния не оказывает. В том случае, когда язык программирования сконструирован для совместной трансляции, компилятор может распоряжаться всеми известными ему в пределах памяти задачи свободными участками по собственному усмотрению (естественно, с учетом ограничений и особенностей аппаратной платформы) для размещения всей совокупности объектов программы: функций и обрабатываемых ими данных. Задачи компилятора при раздельной трансляции могут показаться несколько более сложными в связи с тем, что в этом случае ему уже не может быть известным будущее размещение транслируемых частей единой программы внутри памяти задачи. В действительности все сложности по размещению раздельно транслируемых частей программы в одной линейно организованной памяти задачи выпадают на долю других компонент программного обеспечения: либо редактора связей (другие названия: линковщик, компоновщик, сборщик, …), либо загрузчика операционной системы. Компилятор же, как и в случае совместной трансляции, обеспечивает размещение объектов транслируемых частей программы в линейном образе памяти. Отметим, что размеры сгенерированных при трансляции последовательностей инструкций каждой функции становятся известны во время компиляции, так что компилятор может разместить их в образе памяти задачи при генерации объектного кода. Под размещением здесь пока что понимается просто связывание инструкций и адресов элементов памяти задачи, отводимых компилятором для хранения этих инструкций. Аналогично инструкциям формируются и связываются с памятью и такие объекты данных, которые должны в единственном экземпляре существовать в течение всего периода исполнения программы. Совокупность таких объектов названа статическими данными. Одной из причин стремления к статическому выделению памяти для как можно большего количества объектов данных является то, что адреса этих объектов могут быть использованы прямо при компиляции для формирования использующих эти объекты инструкций. Ниже мы увидим, что для преобразования операторов исходной программы, работающих не со статическими объектами, в инструкции целевой машины приходится формировать дополнительные структуры данных и специальные последовательности машинных команд для их создания и обработки. Это приводит к появлению накладных расходов как памяти, так и затрат процессорного времени при исполнении программы. В некоторых языках, в частности в языке Fortran, память для всех объектов данных может быть выделена статически, т.е. доля таких накладных расходов равна нулю. Однако цена этого «преимущества» – запрет рекурсивных вызовов функции – может оказаться слишком большой. В тех языках, которые предполагают возможность рекурсивных вызовов функций, неизбежно появляются и не статические данные – локальные данные активаций функций и некоторые другие объекты, необходимые для реализации доступа из функций к не принадлежащим им данным. Понятие активации функции необходимо рассмотреть во всех деталях. Активация функции Активацией функции называется процесс ее выполнения в результате одного конкретного вызова. Этот процесс включает следующие действия (возможно, не все из перечисленных ниже и не обязательно выполняемые в приведенном порядке): Формирование адреса точки входа в вызываемую функцию (в том случае, если функция является частью динамически загружаемой библиотеки и этой библиотеки еще нет в памяти выполняемой программы, может выполняться предварительное обращение к операционной системе с целью ее подгрузки). Формирование значений, которые должна обработать вызываемая функция, – фактических параметров. Обеспечение доступности этих значений для инструкций вызываемой функции. Формирование и сохранение адреса возврата – адреса той инструкции вызывающей функции, которая должна получить управление в момент завершения выполнения вызываемой функции. Обеспечение возможности доступа к значениям локальных объектов текущей активации вызывающей функции (и, возможно, функций, находящихся еще раньше в цепочке вызовов) из вызываемой функции, если такая возможность предусмотрена языком программирования. Сохранение содержимого регистров процессора, необходимых для восстановления правильного выполнения текущей активации вызывающей функции. Собственно вызов функции, т.е. передача управления в ее точку входа. Создание локальных объектов (выделение памяти для их размещения). Выполнение функции, т.е. обработка значений фактических параметров, протекающая путем: формирования и использования значений локальных объектов текущей активации; формирования и последующего использования результатов промежуточных вычислений; использования/модификации локальных объектов других существующих активаций этой же или других функции; использования/модификации значений статических данных программы. Формирование результата – значения, возвращаемого из функции. Обеспечение доступности этого значения для инструкций вызывающей функции (как правило, только для той инструкции, к которой возвращается управление и которая должна обработать или сохранить результат вызова). Уничтожение объектов, созданных исключительно для выполнения данной активации функции. Восстановление содержимого ранее сохраненных регистров. Возврат из функции – передача управления в ту точку вызывающей функции, адрес которой сформирован на шаге 3. Заметим, что в тексте исходной программы (имеются в виду, естественно, языки высокого уровня) в явном виде обычно присутствует только вызов функции и ее описание (определение типов параметров и типа возвращаемого значения) или объявление – то же самое описание, за которым следует тело. Все вышеперечисленные действия подразумеваются, но явно не указываются. Задача транслятора – обеспечить выполнение этих действий. От того, каким образом будут реализовываться эти действия в процессе исполнения программы, зависит и то, как должны выполняться семантические проверки во время трансляции. Некоторые из описанных выше действий (например, 1–3, 6) могут быть выполнены только инструкциями вызывающей функции. В свою очередь, действия 8, 9, 12 могут быть выполнены только инструкциями вызываемой функции. Остальные действия (4, 5, 7, 10, 11) в принципе могут выполняться инструкциями как вызывающей, так и вызываемой функций. В разных языках (и даже в разных реализациях одного и того же языка) могут приниматься различные решения по отнесению этих действий к вызывающей или вызываемой функции. Все данные, необходимые только для однократного исполнения функции, обычно размещаются в одном связном блоке памяти и называются записью активации. Запись активации может содержать следующие поля (все или только часть – определяется свойствами языка, его реализации и текущими условиями) (рис. 8.6):
Рис. 8.6. Состав записи активации функции Для последующего рассмотрения важно знать, в какой момент и каким образом может быть определен размер всей записи активации в целом, а следовательно, размер каждого из ее полей. Поэтому кратко рассмотрим назначение и, соответственно, способ формирования содержимого записи активации. |
