Реализация интерпретатора с задержанным вычислением

Под интерпретатором с задержанным вычислением понимается такой интерпретатор, который вычисляет значения аргументов по необходимости, т. е. в тот момент работы программы, когда действительно необходимо значение вычисляемого выражения. Таким образом, в ходе своей работы при вызове какой-либо процедуры интерпретатор с задержанным вычислением определяет, какие аргументы требуется вычислить, а какие задержать. Задержанные аргументы при этом не вычисляются, а преобразуются в объекты, называемые рецептами [1].

В данной статье сделана попытка показать, как можно использовать интерпретатор с задержанным вычислением U для автоматического решения следующей задачи: пусть в банке процедур B имеется относительно обобщённая (или полиморфная) процедура P(x1, …, xn). Тогда интерпретатор U, вызывая P(x1, …, xn) и имея контекстные условия C на текущий момент t процесса вычисления, может задержать немедленное исполнение процедуры P(x1, …, xn) на время, необходимое для конкретизации процедуры P(x1, …, xn), или, другими словами, для адаптации процедуры P(x1, ,…, xn) к текущему контексту C вычислительного процесса. Во время адаптации (т. е. во время задержки и интерпретации) процедуры P интерпретатор U определяет фактические значения некоторых параметров {xi1, xi2, …, xim}, где (m ≤ n) исходя из контекста С. Процедура P c вычисленными фактическими параметрами определяет производную процедуру Р1. Можно сказать, что процедура P является родителем процедуры P1, а P1 – потомком P. Отметим, что в банке процедур B все процедуры частич- но упорядочены отношением полиморфизма и образуют полную решетку (или декартово-замкнутую категорию Скотта [2; 3]), что отражает структуру знаний, записанную в банке процедур B.

Разработка структуры знаний банка процедур B в данной работе не затрагивается и предполагается, что эта задача инженерии знаний конкретной предметной области. Таким образом, имеем следующую схему работы интерпретатора U : исходные данные: [1) P ( x 1 , …, x n ); 2) контекст динамического процесса вычисления C ; 3) задержка, необходимая интерпретатору U : C → { x i 1 , ..., x im } для определения фактических параметров процедуры P ] ^ результат: конкретизированная (или адаптированная) процедура P 1 .

Рассмотрим варианты реализации алгоритма работы интерпретатора с задержанным вычислением, разработанного на базе расширенного функционального языка ЛИСП.

Реализация интерпретатора с задержанным вычислением для количественной оптимизации процесса вычислений. В качестве примера рассмотрим программу, выполняющую функцию формирования суммы и произведения бесконечного списка чисел:

сумпроизвспис(п) = сумпроизв(список(1, n)) сумпроизв(х) = {сп (х, 0, 1)

гдерек сп = Л(х, s, p)

если равно(х, НИЛ) то двучлен (s, p) иначе сп (cdr(x), s+car(x), p*car(x))} список(т, n) = если m>n то НИЛ иначе cons (m, список(т+1,п))

двучлен(х, y) = cons(x, cons(y, НИЛ))

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

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

Второй способ более выгоден и основан на применении метода задержанных вычислений. Суть его заключается в том, что формируется не полный список чисел, а только его часть, которая в данный момент используется функцией сумпроизв(х) . Причем согласно правилам связывания, функция формирования списка список(т, n) будет выдавать элементы именно в том порядке, в каком они требуются для функции сумпроизв(х) [1].

Реализация этого метода основана на организации задержки при формировании следующего элемента списка в функции список(т, n) , которая примет следующий вид:

список(т, n) = если m>n то НИЛ иначе cons (m, задержать(список(m+1,n))) либо с использованием функции без параметров:

список(т, n) = если m>n то НИЛ иначе cons (т, Л() список(m+1,n))

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

сумпроизв(х) = {сп (х, 0, 1)

гдерек сп = Л(х, s, p)

если равно(х, НИЛ) то двучлен (s, p) иначе сп (возобновить cdr(х), s+car(x) p*car(x))} либо с использованием функции без параметров:

сумпроизв(х) = {сп (х, 0, 1)

гдерек сп = Л(х, s, p)

если равно(х, НИЛ) то двучлен (s, p) иначе сп (cdr(х) (), s+car(x), p*car(x))}

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

Шаг 1. Первый вызов функции сумпроизвспис(п) вызывает функцию список(1, n), результатом выполнения которой будет список(1, n) = cons (1, список(2, n)), где второй параметр функции cons - список(2, n) -задержан и представляет собой рецепт и может быть использован как аргумент в функции сумпроизв(х), которая выполняется далее и результат её работы отображается следующим образом: так как х # НИЛ, то сумпроизв(1) = сп (cdr(х), 0+1, 1*1) = сп (список(2, n), 1, 1), где cdr(х) - следующий элемент списка, генерируемый при необходимости, вместо которого и подставляется невычисленный рецепт.

Шаг 2. Теперь требуется, чтобы задержанное вычисление список(2, n) было возобновлено при задержке вычисления список(3, n), в результате чего получаем список(2, n) = cons (2, список(3, n)) так как х # НИЛ, то сумпроизв(3) = сп (cdr(х), 1+2, 1*2) = сп (список(3, n), 3, 2)

Шаг 3. список(3, n) = cons (3, список(4, n)) так как х # НИЛ, то сумпроизв(4) = сп (cdr(х), 3+3, 2*3) = сп (список(4, n), 6, 6) и т. д.

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

Реализация интерпретатора с задержанным вычислением для полиморфных вычислений. В качестве примера рассмотрим функцию увеличения всех элементов списка на некоторое число N :

увелич(х) = если равно(х, НИЛ) то НИЛ иначе сons(car(x) + N, увелич(сdr (х)))

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

Рассмотрим также аналогичную предыдущей функцию умножения всех элементов списка на некоторое число N :

умнож(х) = если равно(х, НИЛ) то НИЛ иначе cons(car(x) * N, умнож(сdr(x))),

Эта функция вычисляет по исходному списку х список, каждый элемент которого умножен на некоторое число N .

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

вычисл (f) = Л (х) если равно(х, НИЛ) то НИЛ иначе cons( f(car(x)) (вычисл (f))(cdr(x)))

Здесь f – функция, производящая операции над элементами списка х.

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

вычисл (f) = Л (х) () если равно(х, НИЛ)

то НИЛ иначе cons(f(car(x)), Л () (вычисл (f))(cdr(x)))

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

На основании изложенного можно заключить, что применение интерпретатора с задержанными вычислениями даёт возможность пользоваться обобщенными процедурами из базы процедур B : из каждой обобщенной процедуры P , принадлежащей B , можно получить при помощи задержанных вычислений производную процедуру P i от P , что улучшает емкостные характеристики, а что самое главное – улучшает логико-структурную и интеллектуальную мощь системы.

Адаптация процедуры с помощью интерпретатора с задержанным вычислением . В качестве примера рассмотрим следующие предложения русского языка.

• 1.    Павел разбил чашку.

• 2.    Павел разбил сквер.

В компьютерном словаре слово «разбил» толкуется при помощи базисного слова лингвистики как деструкция или разрушение. Однако в отдельных контекстах слово «разбил» имеет прямо противоположный смысл и означает созидание или креативность. Если рассмотреть слово «разбил» как оболочку полиморфной функции, то в контексте функция «разбил» обретает конкретное значение деструкция или креативности:

разбил(Х, чашку):= деструкция;

разбил(Х, сквер):= креативность.

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

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

Интерпретатор с задержанным вычислением U можно использовать как автоматический генератор родственных процедур (процедур, обладающих «сходством»), который, работая в режиме динамической интерпретации, существенно повышает интеллектуальную мощь системы программирования. Указанное свойство интерпретатора можно понимать как одну из необходимых составляющих систем баз знаний.

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

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

Используя указанный интерпретатор, можно реализовать данную идею ламбда-исчисления в программировании. Идея принципа активизации данных [4; 5] в программировании имеет чрезвычайно важную роль для ликвидации технологии ручного программирования и переходу к автоматизации программирования для повышения производительности труда программистов и снижения себестоимости программных продуктов.

Интерпретатор U выполняет роль метапроцедуры относительно процедуры P ( x 1 , …, x n ): исходными данными для U являются неполное тело процедуры P , множество значений для параметров { x j 1 , …, x jk } ^⊂ { x i 1 , …, x im }. Для построения процедуры адаптации можно использовать конечную совокупность { G t } контекстно-свободных грамматик, построив формальную модель предметной области в виде уравнений, использующих нетерминальные символы соответствующих грамматик. Для построения уравнений можно использовать операцию сопоставления образца с шаблоном [6, с. 318]. В следующей статье авторы продемонстрируют сказанное на примерах.