Процедура смешанных вычислений

Смешанные вычисления

Поиск универсальных методов – одна из главных парадигм современной науки. Но более эффективны специализированные методы. Между универсальными и специальными методами существует глубинная связь.

Поскольку ЭВМ - детерминированный автомат, то при фиксированной программе ρ для любого входного данного x выходное значение z будет некоторой функцией φ, полностью определяемой программой ρ φ(x) = z.

Сама программа ρ вместе с ее данными х выполняется посредством интерпретации Int (алгоритм Int встроен в конструкцию ЭВМ).

Int(ρ,x) = φ(x) =z.

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

Пусть φ = φ(х,y) и x = a - фиксировано;

Тогда φ(а,у) = π(у): Int(π,b) = φ(a,b).

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

Определение:

Результат смешанных вычислений называется остаточной программой.

Если все входные переменные связаны, то остаточная программа выродится в выдачу результата; если все входные переменные оставить свободными, то остаточная программа совпадет с исходной.

Пример.

[λxy. +xy]

Пусть x=1

[λy. +1y] – специальная программа, прибавляющая к числу 1

х = 1

у = 1

Специальная программа будет выдавать результат.

а¹⁶=(((а²) ²) ²)² - т.е. вместо 16 умножений будем иметь только 4 умножения.

Обычные и смешанные вычисления связаны друг с другом. Обычные вычисления –процедура Int, которая для любой программы ρ и заданных значений всех ее входных переменных вычисляет значение функции φ, реализуемой программой.

Определение:

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

Int(p;a,b) = φ(a,b)

Mix(p,a,b) = out(с), где с = φ(a,b)

Mix(p,0,{x,y}) = p

Mix(p,a,y) = pa, где Int(pa,b) = φ(a,b).

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

Эта последовательность базисных команд называется протоколом вычисления.

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

λх.if x=0 ERR 3/x _{↓предикат}

Протокол: (zerop x) ERR

Not (zerop x) 3/x

Определения:

Предикат - функция одного аргумента, принимающая значение истина или ложь.

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

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

1) Извлечение базисных команд, образующих протокол;

2) Выполнение базисных команд, образующих протокол (т.е. прямые вычисления).

Множество протоколов возникает из-за разных выборов альтернатив при проверке условий. Это множество протоколов называется детерминантом программы.

Выполнение программы - передача ее входных данных всем протоколам детерминанта. (Все протоколы противоречивы – функция невычислима, результат неизвестен; существует несколько непротиворечивых протоколов – функция многозначна; существует единственный непротиворечивый протокол – он выдает результат выполнения программы).

Протокол - линейная запись команд; при выполнении очередной команды она редуцируется (убирается).

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

Определим частичные вычисления:

1) выполним программу для не полностью заданных значений переменных;

2) будем печатать те команды, которые нельзя выполнить из-за отсутствия информации (в том числе нередуцируемые альтернативы и присваивания, нераскрытые итерации). Последовательность невыполненных команд образует остаточную программу.

Детерминант остаточной программы - некоторое непротиворечивое расширение редукции детерминанта исходной программы.

Вычисления смешанные потому, что чередуются шаги обычных вычислений и формирования остаточных программ.

Дата добавления: 2014-01-11