17.4. Более сложные понятия логического программирования

Успех языка Prolog стимулировал появление других языков логического про­граммирования. Многие языки попытались объединить преимущества логи­ческого программирования с другими парадигмами программирования типа объектно-ориентированного и функционального программирования. Веро­ятно, наибольшие усилия были вложены в попытки использовать паралле­лизм, свойственный логическому программированию. Вспомните, что логи­ческая программа состоит из последовательности формул:

t=>t

(t = tl || t2)^(SCtl)=>(S=>t)

(t = tl || 12) ^ (s с t2) => (s => t)

Язык Prolog вычисляет каждую цель последовательно слева направо, но цели можно вычислять и одновременно. Это называется и-параллелизмом из-за конъюнкции, которая соединяет формулы цели. Сопоставляя цели с голо­вами формул программы, язык Prolog проверяет каждую формулу последова­тельно в том порядке, в котором она встречается в тексте, но можно проверять формулы и одновременно. Это называется или-параллелизмом, потому что каждая цель должна соответствовать первой или второй формуле, и т. д.

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

Много усилий также прилагалось для интеграции функционального и логического программирования. Существует очень близкая связь между мате­матикой функций и логикой, потому что:

y = f(x_b ...,х„)

Основные разли­чия между двумя концепциями программирования следующие:

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

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

3. Логическое программирование базируется на машине вывода, которая автоматически ищет ответы.

4. Функциональное программирование оперирует с объектами более высо­кого уровня абстракции, поскольку функции и типы можно использо­вать и как данные, в то время как логическое программирование более или менее ограничено формулами на обычных типах данных.

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

Новая область исследования в логическом программировании — расшире­ние отождествления от простой синтаксической унификации к включению семантической информации. Например, если цель определяет 4 < х < 8 и го­лова формулы определяет 6 < х < 10, то мы можем заключить, что 6 s х < 8 и что х = 6 или х = 7. Языки, которые включают семантическую информацию при отождествлении, называются ограниченными (constraint) логическими языками программирования, потому что значения ограничиваются уравнениями. Огра­ниченные логические языки программирования должны базироваться на эф­фективных алгоритмах для решения уравнений.

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