Процедура смешанных вычислений
Смешанные вычисления
Поиск универсальных методов – одна из главных парадигм современной науки. Но более эффективны специализированные методы. Между универсальными и специальными методами существует глубинная связь.
Поскольку ЭВМ - детерминированный автомат, то при фиксированной программе ρ для любого входного данного 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=(((а2) 2) 2)2 - т.е. вместо 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) будем печатать те команды, которые нельзя выполнить из-за отсутствия информации (в том числе нередуцируемые альтернативы и присваивания, нераскрытые итерации). Последовательность невыполненных команд образует остаточную программу.
Детерминант остаточной программы - некоторое непротиворечивое расширение редукции детерминанта исходной программы.
Вычисления смешанные потому, что чередуются шаги обычных вычислений и формирования остаточных программ.