IMPLEMENTATION OF THE INTERPRETER WITH THE DELAYED CALCULATION

全文:

Под интерпретатором с задержанным вычислением понимается такой интерпретатор, который вычисляет значения аргументов по необходимости, т. е. в тот момент работы программы, когда действительно необходимо значение вычисляемого выражения. Таким образом, в ходе своей работы при вызове какой-либо процедуры интерпретатор с задержанным вычислением определяет, какие аргументы требуется вычислить, а какие задержать. Задержанные аргументы при этом не вычисляются, а преобразуются в объекты, называемые рецептами [1]. В данной статье сделана попытка показать, как можно использовать интерпретатор с задержанным вычислением U для автоматического решения следующей задачи: пусть в банке процедур B имеется относительно обобщённая (или полиморфная) процедура P(xj, ..., xn). Тогда интерпретатор U, вызывая P(x, ., xn) и имея контекстные условия C на текущий момент t процесса вычисления, может задержать немедленное исполнение процедуры P(x1, . , xn) на время, необходимое для конкретизации процедуры P(xb ..., xn), или, другими словами, для адаптации процедуры P(x1, ,. , xn) к текущему контексту C вычислительного процесса. Во время адаптации (т. е. во время задержки и интерпретации) процедуры P интерпретатор U определяет фактические значения некоторых параметров {xib xi2, ..., xim}, где (m < n) исходя из контекста С. Процедура P c вычисленными фактическими параметрами определяет производную процедуру Р1. Можно сказать, что процедура P является родителем процедуры P1, а P1 - потомком P. Отметим, что в банке процедур B все процедуры частич но упорядочены отношением полиморфизма и образуют полную решетку (или декартово-замкнутую категорию Скотта [2; 3]), что отражает структуру знаний, записанную в банке процедур B. Разработка структуры знаний банка процедур B в данной работе не затрагивается и предполагается, что эта задача инженерии знаний конкретной предметной области. Таким образом, имеем следующую схему работы интерпретатора U: исходные данные: [1) P(xb ..., xn); 2) контекст динамического процесса вычисления C; 3) задержка, необходимая интерпретатору U: C ^ {xii, ..., xim} для определения фактических параметров процедуры P] ^ результат: конкретизированная (или адаптированная) процедура P1. Рассмотрим варианты реализации алгоритма работы интерпретатора с задержанным вычислением, разработанного на базе расширенного функционального языка ЛИСП. Реализация интерпретатора с задержанным вычислением для количественной оптимизации процесса вычислений. В качестве примера рассмотрим программу, выполняющую функцию формирования суммы и произведения бесконечного списка чисел: сумпроизвспис(п) = сумпроизв(список(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, НИЛ)) 66 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Данная программа строит список натуральных чисел и вычисляет их сумму и произведение. Пусть нам дан некоторый бесконечный список натуральных чисел, который формируется в программе при помощи функции список(т, n). При нормальном порядке выполнения программа сначала должна построить весь список, а затем вычислить сумму и произведение его членов. Однако если список будет бесконечным, произойдет зацикливание программы на этапе формирования списка и её работа завершится неудачей. Существуют два способа решения данной проблемы. Первый способ заключается в том, чтобы ограничить количество элементов списка до начала его формирования, введя в программу дополнительные функции либо жёсткие ограничения. Однако при этом ухудшатся функциональные характеристики программы - её универсальность. Второй способ более выгоден и основан на применении метода задержанных вычислений. Суть его заключается в том, что формируется не полный список чисел, а только его часть, которая в данный момент используется функцией сумпроизв(х). Причем согласно правилам связывания, функция формирования списка список(т, n) будет выдавать элементы именно в том порядке, в каком они требуются для функции сумпроизв(х) [1]. Реализация этого метода основана на организации задержки при формировании следующего элемента списка в функции список(т, n), которая примет следующий вид: список(т, n) = если m>n то НИЛ иначе cons (т, задержать(список(m+1,n))) либо с использованием функции без параметров: список(т, n) = если m>n то НИЛ иначе cons (m, А( ) список(іті+1,п)) Возобновление же вычислений должно производиться в функции сумпроизв(х) при обращении к следующему элементу списка: сумпроизв(х) = {сп (х, 0, 1) гдерек сп = А(х, s, p) если равно(х, НИЛ) то двучлен (s, p) иначе сп (возобновить cdr(x), s+car(x) p*car(x))} либо с использованием функции без параметров: сумпроизв(х) = {сп (х, 0, 1) гдерек сп = А(х, s, p) если равно(х, НИЛ) то двучлен (s, p) иначе сп (cdr(x) ( ), 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) = сп (cdrM, 1+2, 1*2) = сп (список(3, n), 3, 2) Шаг 3. список(3, n) = cons (3, список(4, n)) так как х + НИЛ, то сумпроизв(4) = сп (cdrM, 3+3, 2*3) = сп (список(4, n), 6, 6) и т. д. Таким образом, мы видим, что организация задержанных вычислений позволяет избежать зацикливания программы и получить некоторый конечный результат без сообщений об ошибке. Иными словами, данный алгоритм будет работать при любых значениях количества элементов списка, и мы получаем количественную оптимизацию вычислений. Реализация интерпретатора с задержанным вычислением для полиморфных вычислений. В качестве примера рассмотрим функцию увеличения всех элементов списка на некоторое число N: увелич(х) = если равно(х, НИЛ) то НИЛ иначе ^ns(car(x) + N, увєлич^г (х))) Если эту функцию применить к списку целых чисел, то она выдает список такой же длины, но с элементами, на единицу увеличенными по сравнению с исходным списком. Рассмотрим также аналогичную предыдущей функцию умножения всех элементов списка на некоторое число N: умнож(х) = если равно(х, НИЛ) то НИЛ иначе cons(car(x) * N, умнож(сdr(x))), Эта функция вычисляет по исходному списку х список, каждый элемент которого умножен на некоторое число N. Семантико-алгоритмическая часть рассматриваемых функций практически одинаковая, различие лишь в операции, совершаемой над элементами списка, т. е. в первом случае это сложение, во втором -умножение. Данный факт приводит нас к решению задачи объединения подобных функций в одну обобщённую функцию, в которой операция, выполняемая над элементами списка, будет являться параметром самой функции. Такая универсальная функция может быть записана в виде следующей программы: вычисл (f) = А (х) если равно(х, НИЛ) то НИЛ иначе cons( f(car(x)) (вычисл (f))(cdr(x))) Здесь f - функция, производящая операции над элементами списка х. При работе программы функция, будучи применена к х, порождает новый список, каждый элемент которого получается применением соответствующей 67 Математика, механика, информатика функции к х. Однако в случае когда f не будет известна заранее, программа завершится неудачей. Во избежание этого применим для данной программы метод задержанных вычислений, в результате программа принимает следующий вид: вычисл (f) = А (х) ( ) если равно(х, НИЛ) то НИЛ иначе cons(f(car(x)), А ( ) (вычисл (f))(cdr(x))) Задержка аргумента при помощи функции без параметров А( ) (вычисл (f))(cdr(x)) позволяет интерпретатору с задержанным вычислением обобщить вызываемые процедуры, обеспечивая таким образом универсальность программы, которая заключается в том, что она будет работать при любых функциях и производить требуемые операции над элементами исходного списка. Вычисление будет производиться, как только становится известной выполняемая функция. На основании изложенного можно заключить, что применение интерпретатора с задержанными вычислениями даёт возможность пользоваться обобщенными процедурами из базы процедур B: из каждой обобщенной процедуры P, принадлежащей B, можно получить при помощи задержанных вычислений производную процедуру Pi от P, что улучшает емкостные характеристики, а что самое главное - улучшает логико-структурную и интеллектуальную мощь системы. Адаптация процедуры с помощью интерпретатора с задержанным вычислением. В качестве примера рассмотрим следующие предложения русского языка. 1. Павел разбил чашку. 2. Павел разбил сквер. В компьютерном словаре слово «разбил» толкуется при помощи базисного слова лингвистики как деструкция или разрушение. Однако в отдельных контекстах слово «разбил» имеет прямо противоположный смысл и означает созидание или креативность. Если рассмотреть слово «разбил» как оболочку полиморфной функции, то в контексте функция «разбил» обретает конкретное значение деструкция или креативности: разбил(Х, чашку):= деструкция; разбил(Х, сквер):= креативность. В различных вычислительных процессах довольно часто возникает необходимость конкретизировать (найти значения) некоторые объекты (функции, процедуры, автоматные структуры), а затем после конкретизации возобновить вычислительный процесс. Для конкретизации объекта приходится задержать вычислительный процесс и начать интерпретировать указанный объект в контексте задержанного вычислительного процесса. Итак, мы рассмотрели методы оптимизации работы алгоритмов, используя интерпретатор с задержанным вычислением. Интерпретатор с задержанным вычислением U можно использовать как автоматический генератор родственных процедур (процедур, обладающих «сходством»), который, работая в режиме динамической интерпретации, существенно повышает интеллектуальную мощь системы программирования. Указанное свойство интерпретатора можно понимать как одну из необходимых составляющих систем баз знаний. В связи с этим введём определение: под динамическим режимом интерпретации будем понимать адаптацию обобщённой процедуры из обобщённой базы процедур к текущему вычислительному контексту под управлением интерпретатора с задержанным вычислением. Также следует отметить одно важное обстоятельство: в ламбда-исчислении аргумент функции может превратиться в функцию (занять активную позицию), а функция, наоборот, превратиться в аргумент (занять пассивную позицию). Используя указанный интерпретатор, можно реализовать данную идею ламбда-исчисления в программировании. Идея принципа активизации данных [4; 5] в программировании имеет чрезвычайно важную роль для ликвидации технологии ручного программирования и переходу к автоматизации программирования для повышения производительности труда программистов и снижения себестоимости программных продуктов. Интерпретатор U выполняет роль метапроцедуры относительно процедуры P(xb ..., xn): исходными данными для U являются неполное тело процедуры P, множество значений для параметров {x,1, ..., xJk} с {xi1, ..., xim}. Для построения процедуры адаптации можно использовать конечную совокупность {Gt} контекстно-свободных грамматик, построив формальную модель предметной области в виде уравнений, использующих нетерминальные символы соответствующих грамматик. Для построения уравнений можно использовать операцию сопоставления образца с шаблоном [6, с. 318]. В следующей статье авторы продемонстрируют сказанное на примерах.

作者简介

P. Mognonov

Email: dek_etf@esstu.ru

D. Chimitov

Email: dorji2009@mail.ru

N. Yaryshkina

Email: tigra_26@mail.ru

参考

补充文件