Язык декларативного программирования Prolog

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

23 Schwartz, Jacob T. Set Theory as a Language for Program Specification and Program- ming. N. Y.: Courant Institute of Mathematical Sciences, New York University, 1970.

24 Jeff Leonard Levinsky. The GROW Book. San Diego, California, Computer Systems De- sign Group. 1980. P. 60.

 

 

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

Язык программирования Prolog предложен в 1972 году А. Колмерауэром. (Alain Colmerauer), процедурную интерпретацию языка выполнил Р. Коваль- ский (Robert Kowalski) и дал ее описание в 1973 году, опубликованное в 1974 году. Практичность языка резко возросла благодаря созданию Д. Уор- реном (David Warren) компилятора в 1977 году, что приблизило скорость символьной обработки к эффективности языка Lisp.

Существует Pure Prolog в качестве семантического базиса языка, удоб- ного для изучения основных механизмов Prolog-машины. Итеративные алго- ритмы можно программировать как рекурсивные функции. Prolog-машина ищет ответ на запрос в имеющейся системе отношений и, если находит, то сообщает его. Далее приведены алгоритмы мета-интерпретатора для языка Pure Prolog, показывающие его самоприменимость и расширяемость [24].

 

Определение	Примечание
Factorial (N, F) Factorial (0, 1) Factorial  (x+1,  F)  ← Factorial (x, y) * (x + 1)	Функция реализуется двумя клаузами: 1) констатация, что от 0 – значение 1; 2) декларация отношения между значениями функции на соседних числах

Пример 38. Вычисление факториала

 

Определение	Примечание
partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs):- (X @< Pivot -> Smalls = [X|Rest], partition(Xs, Pivot, Rest, Bigs) ; Bigs = [X|Rest], partition(Xs, Pivot, Smalls, Rest) ).   quicksort([]) --> []. quicksort([X|Xs]) --> { partition(Xs, X, Smaller, Bigger) }, quicksort(Smaller), [X], quicksort(Bigger).	Разбиение на участки   Запуск сортировки

Пример 39. Быстрая сортировка

 

Определение	Примечание
maplist(_P, [], []).	Отображать нечего.
maplist(P, [X1|X1s], [X2|X2s]):-	Можно выделить начало.
call(P, X1, X2),	Вызов от первого.
maplist(P, X1s, X2s).	Отображение остального

Пример 40. Отображение

 

Определение	Примечание
mi1(true). mi1((A,B)):- mi1(A), mi1(B). mi1(Goal):- Goal \= true, Goal \= (_,_), clause(Goal, Body), mi1(Body).	Равноправие вариантов.     Продвижение к цели

Пример 41. Расширяемый скелет Prolog-интерпретатора

 

Определение	Примечание
provable(true, _):-!. provable((G1,G2), Defs):-!, provable(G1, Defs), provable(G2, Defs). provable(BI, _):- predicate_property(BI, built_in), !, call(BI). provable(Goal, Defs):- member(Def, Defs), copy_term(Def, Goal-Body), provable(Body, Defs).	Доказуемость Варианты.   Встроенные свойства. Движение к цели

Пример 42. Выводимость цели. Обобщение интерпретатора

В определении функции provable(Goal, Defs) вырабатывается ис- тина, если цель Goal выводима по отношению к Defs, представленным списком клауз в форме Head-Body. Полная реализация бектрекинга требует детерминированного накопления результатов. Отдельная альтернатива пред- ставляется как список целей и ветвей, которые могут использоваться как спи- сок альтернатив.

 

Определение	Примечание
mi_backtrack_([[]-G|_], G). mi_backtrack_(Alts0, G):- resstep_(Alts0, Alts1), mi_backtrack_(Alts1, G).	Других вариантов нет.   Перебор других вариантов

Пример 43. Бэктрекинг. Возвраты при неудачном выборе клаузы

 

Если ни одна цель не доказана, то выбирается решение из внутренней оче- реди. Вторая клауза описывает вычисление.

Существуют версии языка, приспособленные к работе с функциями выс- ших порядков (HiLog, λProlog) и с модулями.

Стандарт ISO языка Prolog поддерживает компиляцию, хвостовую рекур- сию, индексирование термов, хэширование, обработку таблиц.

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

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

 

 

Функциональная модель ЛП

Первые реализации ЛП были выполнены на языке Lisp, поэтому основ- ные механизмы можно рассмотреть как обработку списков.

По смыслу выбор варианта похож на выбор произвольного элемента мно- жества:

{ a | b | c } = э { a, b, c }

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

Чтобы определить выбор произвольного элемента из списка L, можно представить рекурсивное выражение вида:

(любой L) = { (CAR L) | (любой (CDR L)) }

Уточненную схему выбора произвольного элемента списка можно пред- ставить формулой вида:

 

Определение	Примечание
(любой L) = { (car L) | (любой (cdr L)) |ESC}	Множество из первого элемента списка, выбора любого из оставшихся элементов списка и тупика

Пример 44. Тупик как равноправный вариант

 

Более ясное определение имеет вид:

 

Определение	Примечание
(любой L) = { (CAR L) | (любой (CDR L)) | (if (nl L) ESC) }	Выбор тупикового варианта возможен лишь при отсутствии других

Пример 45. В какой-то момент L становится пустым списком, и его разбор оказывается невозможным. Тогда действует ESC

 

Другие построения, характерные для теории множеств:

{    x  |  P(X) } – множество элементов, обладающих свойством P.

 

Определение	Примечание
(F L) = {(if (P (CAR L)) (CONS (CAR L) (F (CDR L)))) | (if (nl L) ESC) }	Соединяются в список по проверке предиката. Тупик

Пример 46. Выбор элементов списка, удовлетворяющих предикату

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

Определение	Примечание
(F L) = (ALL {(if (P (CAR L)) (CONS (CAR L) (F (CDR L)))) | (if (nl L) ESC) })	Специальная форма для накоп- ления всех результатов

Пример 47. Множество всех элементов списка, удовлетворяющих предикату

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

 

Определение	Примечание
(ALL (LAMBDA (x y) { (if (= x y) x) | ESC }) (любой A) (любой B) )	Форма выбора элементов пересечения.   Перебор элементов двух множеств в произвольном порядке

Пример 48. Пересечение множеств A и B

Можно добиться равноправия порядка вычисления «a» и «b» в формуле

«a & b».

 

Определение	Примечание
(if (not a) NIL b)	a & b

Пример 49. b вычисляется лишь при истинном a, что результативно, но не всегда соответствует интуитивным ожиданиям (логика, предложенная в свое время Маккарти, позволяет добиться высокой эффективности)

Математически более надежны варианты, исключающие зависимость от порядка перебора операндов:

 

Определение	Примечание
(ALL(LAMBDA x { (if (not x) NIL) | ESC }) {a | b})	Если a и b оба истины, то получается ESC

Пример 50. Значение ESC отличается от NIL тем, что может работать как истина

 

 

Аналогичная проблема возникает при построении ветвлений.

 

Определение	Примечание
((LAMBDA L {(COND ((eval(caar L)AL) (eval(cadr L)AL))) | ESC }) (любой ((p1 e1) (p2 e2)...)))	Снятие зависимости от порядка записи

Пример 51. (cond (p1 e1) (p2 e2)...)

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

 

Определение	Примечание
((LAMBDA (x y z) {(if (< (+ x y) K) (+ (+ x y) z)) | ESC}) {(a b c) | (b c a) | (c a b)})	Обеспечение максимальной вычислимости

Пример 52. a+b+c = (a+b)+c = a+(b+c) = (a+c)+b – профилактика переполнения

 

Модели недетерминизма

Необходимая для такого стиля работы инструментальная поддержка обеспечивается в GNU Clisp механизмом обработки событий throw - catch, для которого следует задать примерно такое взаимодействие.

 

Определение	Примечание
(DEFUN vars (xl)(catch 'ESC (COND ((null xl)(escape)) ((CAR xl) (CONS (CAR xl)(vars (CDR xl)))) )))	Перебор вариантов до первого тупика vars not NIL
	Сигнал о попадании в тупик
(DEFUN escape () (throw 'ESC NIL))
(print(vars ())) (print(vars '(a))) (print(vars '(a b c))) (print(vars (list 'a 'b (vars ()) 'c)))	Демонстрация

Пример 53. Механизм обработки событий throw - catch как модель недетерминизма вариантов

 

 

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

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

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

3. Обобщение идеи абстрактных машин с целью теоретического исследо- вания, экспериментального моделирования и прогнозирования недетермини- рованных процессов на суперкомпьютерах и многопроцессорных комплек- сах (многопроцессорная машина Тьюринга и т. п.).

4. Конструирование учебно-игровых программ и экспериментальных ма- кетов, в которых скорость реализации важнее, чем производительность.

5. Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskell и др.

6. Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул матема- тиками.

7. Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.

8. Обработка и исследование естественно языковых конструкций, рече- вого поведения, культурных и творческих стереотипов, социально-психоло- гических аспектов и т. п.

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

В истории ЛП можно выделить ряд специализированных линий:

– абдуктивное логическое программирование;

– металогическое программирование;

– логическое программирование в ограничениях;

– параллельное логическое программирование (FGCS – японский проект 5-го поколения компьютерных систем);

– индуктивное логическое программирование;

– линейное логическое программирование;

– объектно-ориентированное логическое программирование;

– транзакционное логическое программирование.

 

 

Спецификация

Таблица 33

Парадигматическая характеристика языков логического программирования

Параметр	Конкретика
Эксплуатационная прагматика ЯП	Неопределенные постановки задач. Эмпирическое накопление рецептов, достаточное для решения некоторых практических задач
Регистры абстрактной машины	S E C D R S – стек промежуточных результатов. E – стек локальных переменных. C – стек основной программы. D – дамп для защиты и восстановления данных. R – стек для перебора вариантов. Результат – заключение об успехе-неудаче вывода цели
Категории команд абстрактной машины	Кроме типов команд, характерных для ФП: – выбор варианта; – восстановление контекста при переборе вариантов
Реализационная прагматика	В дополнение к ФП обработка разностных списков, отслеживание низкого приоритета тупиков и сечений. Вместо произвольного выбора варианта реально варианты перебираются в порядке представления
Парадигмальная специфика	Расширение класса решаемых задач использованием недетерминированных моделей