Глобальный анализ

Глобальный анализ

Этот раздел посвящен описанию промежуточного подхода. Основные практические решения изложены в лекции 17.

Изучая вариант с закреплением, мы заметили, что его основной идеей было разделение ковариантного и полиморфного наборов сущностей. Так, если взять две инструкции вида

s := b ...

s.share (g)

каждая из них служит примером правильного применения важных ОО-механизмов: первая - полиморфизма, вторая - переопределения типов. Проблемы начинаются при объединении их для одной и той же сущности s. Аналогично:

p := r ...

p.add_vertex (...)

проблемы начинаются с объединения двух независимых и совершенно невинных операторов.

Ошибочные вызовы ведут к нарушению типов. В первом примере полиморфное присваивание присоединяет объект BOY к сущности s, что делает g недопустимым аргументом share, так как она связана с объектом GIRL. Во втором примере к сущности r присоединяется объект RECTANGLE, что исключает add_vertex из числа экспортируемых компонентов.

Вот и идея нового решения: заранее - статически, при проверке типов компилятором или иными инструментальными средствами - определим набор типов (typeset) каждой сущности, включающий типы объектов, с которыми сущность может быть связана в период выполнения. Затем, опять же статически, мы убедимся в том, что каждый вызов является правильным для каждого элемента из наборов типов цели и аргументов.

В наших примерах оператор s := b указывает на то, что класс BOY принадлежит набору типов для s (поскольку в результате выполнения инструкции создания create b он принадлежит набору типов для b). GIRL, ввиду наличия инструкции create g, принадлежит набору типов для g. Но тогда вызов share будет недопустим для цели s типа BOY и аргумента g типа GIRL. Аналогично RECTANGLE находится в наборе типов для p, что обусловлено полиморфным присваиванием, однако, вызов add_vertex для p типа RECTANGLE окажется недопустимым.

Эти наблюдения наводят нас на мысль о создании глобального подхода на основе нового правила типизации:

Правило системной корректности

Вызов x.f (arg) является системно-корректным, если и только если он классово-корректен для x, и arg, имеющих любые типы из своих соответствующих наборов типов.

В этом определении вызов считается классово-корректным, если он не нарушает правила Вызова Компонентов, которое гласит: если C есть базовый класс типа x, компонент f должен экспортироваться C, а тип arg должен быть совместим с типом формального параметра f. (Вспомните: для простоты мы полагаем, что каждый подпрограмма имеет только один параметр, однако, не составляет труда расширить действие правила на произвольное число аргументов.)

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

1 Для каждой сущности начальный набор типов пуст.

2 Встретив очередную инструкцию вида create {SOME_TYPE} a, добавим SOME_TYPE в набор типов для a. (Для простоты будем полагать, что любая инструкция create a будет заменена инструкцией create {ATYPE} a, где ATYPE - тип сущности a.)

3 Встретив очередное присваивание вида a := b, добавим в набор типов для a все элементы набора типов для b.

4 Если a есть формальный параметр подпрограммы, то, встретив очередной вызов с фактическим параметром b, добавим в набор типов для a все элементы набора типов для b.

5 Будем повторять шаги (3) и (4) до тех пор, пока наборы типов не перестанут изменяться.

Данная формулировка не учитывает механизма универсальности, однако расширить правило нужным образом можно без особых проблем. Шаг (5) необходим ввиду возможности цепочек присваивания и передач (от b к a, от c к b и т. д.). Нетрудно понять, что через конечное число шагов этот процесс прекратится.

Число шагов ограничено длиной максимальной цепочки присоединений; другими словами максимум равен n, если система содержит присоединения от xi+1 к xi для i=1, 2, ... n-1. Повторение шагов (3) и (4) известно как метод "неподвижной точки".

Как вы, возможно, заметили, правило не учитывает последовательности инструкций. В случае

create {TYPE1} t; s := t; create {TYPE2} t

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

create b

s := b

s.share (g)

будет объявлена системно-некорректной, несмотря на то, что последовательность их выполнения не приводит к нарушению типа.

Глобальный анализ системы был (более детально) представлен в 22-й главе монографии [M 1992]. При этом была решена как проблема ковариантности, так и проблема ограничений экспорта при наследовании. Однако в этом подходе есть досадный практический недочет, а именно: предполагается проверка системы в целом, а не каждого класса в отдельности. Убийственным оказывается правило (4), которое при вызове библиотечной подпрограммы будет учитывать все ее возможные вызовы в других классах.

Хотя затем были предложены алгоритмы работы с отдельными классами в [M 1989b], их практическую ценность установить не удалось. Это означало, что в среде программирования, поддерживающей возрастающую компиляцию, необходимо будет организовать проверку всей системы. Желательно проверку вводить как элемент (быстрой) локальной обработки изменений, внесенных пользователем в некоторые классы. Хотя примеры применения глобального подхода известны, - так, программисты на языке C используют инструмент lint для поиска несоответствий в системе, не обнаруживаемых компилятором, - все это выглядит не слишком привлекательно.

В итоге, как мне известно, проверка системной корректности осталась никем не реализованной. (Другой причиной такого исхода, возможно, послужила сложность самих правил проверки.)

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Измерения и анализ

Из книги автора

Измерения и анализ Измерение 1 Выполнение измерений и использование их результатов для определения статуса операций по управлению установленными требованиями.Примеры измерений:определение статуса каждого из установленных требований;определение статуса изменений


Измерения и анализ

Из книги автора

Измерения и анализ Измерение 1 Выполнение измерений и использование их результатов для определения состояния работ по планированию проекта разработки.Примеры измерений:определение степени выполнения этапов работ по планированию разработки в сравнении с


Измерения и анализ

Из книги автора

Измерения и анализ Измерение 1 Выполнение измерений и использование их результатов для определения состояния работ по отслеживанию хода проекта и контролю над ним.Примеры измерений: определение объема трудозатрат и других ресурсов, вложенных в выполнение работ по


Урок № 96. Анализ счета и анализ субконто

Из книги автора

Урок № 96. Анализ счета и анализ субконто Анализ счета также относится к числу популярных отчетов программы "1С". Чтобы сформировать этот отчет, нужно выполнить команду главного меню Отчеты | Анализ счета, затем в открывшемся окне указать отчетный период, счет и


  8.1. Анализ

Из книги автора

  8.1. Анализ Определение границ рассматриваемой задачи Врезка ознакомила вас с требованиями к системе мониторинга погоды. Это довольно простая задача, решение которой позволяет обойтись всего несколькими классами. Инженер, не вполне искушенный во всех особенностях


9.1. Анализ

Из книги автора

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


10.1. Анализ

Из книги автора

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


11.1. Анализ

Из книги автора

11.1. Анализ Определение границ предметной области Как сказано во врезке, мы намерены заняться криптоанализом - процессом преобразования зашифрованного текста в обычный. В общем случае процесс дешифровки является чрезвычайно сложным и не поддается даже самым мощным


12.1. Анализ

Из книги автора

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


Анализ CIL-кода

Из книги автора

Анализ CIL-кода Напомним, что компоновочный блок не содержит специфических для платформы инструкций, а содержит независимый от платформы CIL-код. Когда среда выполнения .NET загружает компоновочный блок в память, этот CIL-код компилируется (с помощью JIT-компилятора) в


Последний глобальный шанс для обработки исключений

Из книги автора

Последний глобальный шанс для обработки исключений Позвольте указать на роль обработчика событий Application_Error(). Напомним, что страница может использовать обработчик события Error для обработки любого исключения, сгенерированного в контексте страницы и оставшегося без


2.4. АНАЛИЗ ТРЕБОВАНИЙ К СИСТЕМЕ (СИСТЕМНЫЙ АНАЛИЗ) И ФОРМУЛИРОВКА ЦЕЛЕЙ

Из книги автора

2.4. АНАЛИЗ ТРЕБОВАНИЙ К СИСТЕМЕ (СИСТЕМНЫЙ АНАЛИЗ) И ФОРМУЛИРОВКА ЦЕЛЕЙ Задача оптимизации разработки программ состоит в достижении целей при минимально возможной затрате ресурсов.Системный анализ в отличие от предварительного системного исследования — это