Магия сохраняет силу


Простые bcf-украшения


В преобразованиях методом магических множеств, рассматриваемых в [BMSU86, BR87, MFPR90], предполагается, что на вход поступает уже украшенная программа. Поэтому в преобразовании требуются две фазы. На первой фазе программа украшается, а на второй – магически преобразуется. В этом подразделе мы представляем однофазный алгоритм, совместно выполняющий украшение и магическое преобразование, и показываем, как это может помочь для сокращения сложности украшений.

Мы видим, что украшения обеспечивают три функции:

Функция 1: Украшение α на таблице t является абстракцией для ограничения таблицы t в точке ее использования. Эта абстракция α, а не реальное ограничение, используется для принятия решения о том, как будет вычисляться табличное выражение для .

Функция 2: вычисляется идентичным образом для всех ограничений, абстрагируемых украшением α (одни и те же SIPS, порядок SIPS, порядок соединений и украшения для таблиц, на которые имеются ссылки в табличном выражении t). Следовательно, если абстракция не является хорошей, то для некоторых ограничений будет разрешаться не оптимально. Украшение должно быть правильным ([MFPR90]) в том смысле, что оно должно позволять производить выбор оптимального вычисления всех ограничений (внутри класса ограничений, которые пытает фиксировать паттерн украшения), генерирующих это украшение.

Функция 3: Украшения указывают, когда в двух использованиях t может разделяться одна и та же копия t как общее подвыражение. Основанием для того требования, чтобы в использованиях имелось одно и то же украшение, является то, что тогда магические множества генерируются на основе этих использований с одними и теми же аргументами, что позволяет применять объединения.

В паттерне bcf-украшения, введенном в [MFPR90], c-украшение используется только для независимых условий. Условие на атрибуте X называется независимым, если оно может быть выражено без ссылки на какой-либо свободный (f) атрибут. Таким образом, условие X > 10 является независимым.


Начало  Назад  Вперед