Автоматическая генерация программ

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

Метод частичных вычислений всегда порождает корректную программу:

out = [[ source]]_S input = [[int]] [source, input] = [[[[mix]] [int, source] ]] input = [[target]] input

Здесь:int — интерпретатор,.

mix — процедура частичных вычислений.

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

• 1. Интерпретация исходного кода программы, написанной на языке S.
• 2. Преобразование исходной программы с использованием методики частичных вычислений.
• 3. Генерация результирующей преобразованной программы на языке L.

Выражение [target] = [mix] int, source часто называется первой проекцией Футамуры и впервые описано в [1].

Автором разрабатывались алгоритмы оптимизации, основанные на технике частичных вычислений. Например [2].

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

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

Для разработки вычислительно-эффективного метода классификации необходимо разработать алгоритмы оптимизации:

• · разбиения заданного набора точек на множества в соответствии с целевой функцией;
• · определения принадлежности выбранной точки одному из классов;
• · определения принадлежности выбранного множества точек классам.

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

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

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

Рассмотрим простейшую процедуру оптимизации.

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

Например, выражение, преобразуется к виду .

А так же выражение к виду.

Однако такой алгоритм уже не преобразует к виду, а выражение к виду.

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