М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 50
Текст из файла (страница 50)
Вычисление выражения и присваивание вновь созданной переменной можно использовать для моделирования циклов:
loop (0).
loop (N) :-
proc,
N1 isN-1,
loop(N1).
Следующая цель выполнит proc десять раз:
?-loop (10).
Аргумент является переменной, которая используется как индекс. Первая формула — базовый случай рекурсии: когда индекс равен нулю, больше ничего делать не нужно. В противном случае выполняется процедура proc, создается новая переменная N1 со значениями N-1, которая используется как аргумент для рекурсивного вызова loop. Унификация создает новую переменную для каждого использования второй формулы loop. Нельзя сказать, что это слишком неэффективно, потому что это можно выполнить в стеке. К тому же многие компиляторы Prolog могут делать оптимизацию хвостовой рекурсии, т. е. заменять рекурсию обычной итерацией, если рекурсивный вызов является последним оператором в процедуре.
Причина того, что использование is — нелогическое, состоит в том, что оно не симметрично, т. е. вы не можете написать:
28 is V1 * V2
или даже:
28 is V1*7
где V1 и V2 — переменные, которые еще не получили своих значений. Для этого потребовалось бы знать семантику арифметики (как разлагать на множите ли и делить целые числа), в то время как унификация устанавливает только синтаксическое соответствие термов.
База данных на языке Prolog
Нет никаких других ограничений на количество формул, которые может содержать программа на языке Prolog, кроме ограничений, связанных с размером памяти компьютера. В частности, нет ограничения на количество фактов, которые можно включить в программу, поэтому набор фактов на языке Prolog может выполнять функцию таблицы в базе данных:
customer(1, "Jonathan"). /* клиент(Идент_клиента, Имя) */
customer(2, "Marilyn"),
customer^, "Robert").
salesperson 101, "Sharon"). /* продавец(Идент_продавца, Имя) */
salesperson 102, "Betty").
salesperson 103, "Martin").
order(103, 3, "Jaguar"). /*заказ(Идент_продавца,
order(101, 1, "Volvo"). Идент_клиента, товар)*/
order(102, 2, "Volvo").
order(103, 1, "Buick").
Обычные цели языка Prolog могут интерпретироваться как запросы к базе данных. Например:
?- salesperson(SalesJD, "Sharon"), /* ID Шэрон */
order(SalesJD, CustJD, "Volvo"), /* Заказ Volvo */
customer(CustJD, Name). /* Клиент заказа */
означает следующее: «Кому Шэрон продала Volvo?». Если запрос успешный, переменная Name получит значение имени одного из клиентов. В противном случае мы можем заключить, что Шэрон никому Volvo не продавала.
Сложные запросы базы данных становятся простыми целями в языке Prolog. Например: «Есть ли клиент, которому продавали автомобиль и Шэрон, и Мартин?»:
?- salesperson(ID1,"Sharon"), /* ID Шэрон */
salesperson(ID2, "Martin"), /* ID Мартина */
order(ID1, CustJD, _), /* ID клиента Шэрон */
order(ID2, CustJD, _). /* ID клиента Мартина */
Поскольку переменная CustJD является общей для двух элементарных формул, цель может быть истинной только, когда один и тот же клиент делал заказ у каждого из продавцов.
Является ли язык Prolog реальной альтернативой специализированному программному обеспечению баз данных? Реализация списков фактов вполне эффективна и может легко отвечать на запросы для таблиц из тысяч записей. Однако, если ваши таблицы содержат десятки тысяч записей, необходимы более сложные алгоритмы поиска. К тому же, если ваша база данных предназначена для непрограммистов, необходим соответствующий интерфейс пользователя, и в этом случае ваша реализация языка Prolog может и не оказаться подходящим языком программирования.
Важно подчеркнуть, что «это не было сделано профессионалами», т. е. мы не вводили ни новый язык, ни понятия базы данных; это было всего лишь обычное программирование на языке Prolog. Любой программист может создавать небольшие базы данных, просто перечисляя факты, а затем в любой момент выдавать запросы.
Динамические базы данных
Если все наборы фактов, существуют с самого начала программы на языке Prolog, запросы совершенно декларативны: они только просят о заключении, основанном на ряде предположений (фактов). Однако язык Prolog включает нелогическое средство, с помощью- которого можно менять базу данных в процессе вывода. Элементарная формула assert(F) всегда истинна как логическая формула, но в качестве побочного эффекта она добавляет факт F к базе данных; точно так же retract(F) удаляет факт F:
?- assert(order( 102, 2, "Peugeot")), /* Бетти продает автомобиль'*/
assert(order(103,1 , "BMW")), /* Мартин продает автомобиль */
assert(order(102, 1, "Toyota")), /* Бетти продает автомобиль*/
assert(order(102, 3, "Fiat")), /* Бетти продает автомобиль */
retract(salesperson(101, "Sharon")). /* Уволить Шэрон! */
С помощью изменений базы данных можно в языке Prolog смоделировать оператор присваивания. Предположим, что факт count(O) существует в программе, тогда:
increment :-
N1 is N +1, /* Новая переменная с новым значением */
retract(count(N)), /* Стереть старое значение */
assert(count(N1)). /* Сохранить новое значение */
Ни одна из трех элементарных формул не является логической!
Вспомните, что присваивание используется, чтобы записать состояние вычисления. Таким образом, альтернатива моделированию присваивания — внести каждую переменную состояния как дополнительный аргумент в формулы, которые могут стать и сложными, и запутанными. На практике в программах на языке Prolog допустимо использовать нелогические операции с базой данных как для того, чтобы реализовать динамические базы данных, так и для того, чтобы улучшить читаемость программы.
Сортировка в языке Prolog
В качестве примера соотношения между описательным и процедурным взглядами на логическую программу мы обсудим программы сортировки на языке Prolog. Мы ограничимся сортировкой списков целых чисел. Обозначения: [Head]Tail] является списком, первый элемент которого — Head, а остальные элементы образуют список Tail. [] обозначает пустой список.
Сортировка в логическом программировании вполне тривиальна, потому нам нужно только описать смысл того, что список L2 является отсортированной версией списка L1. Это означает, что L2 представляет собой перестановку (permutation) всех элементов L1 при условии, что элементы упорядочены (ordered):
sort(L1, L2):- permutation(L1, L2), ordered(L2).
где формулы в теле процедуры определены как:
permutation([], []).
permutation(L, [X | Tail]) :-
append(Left_Part, [X | Right_Part], L),
append(Left_Part, Right_Part, ShortJJst),
permutation(Short__List, Tail).
ordered([]).
ordered([Single]).
ordered([First, Second | Tail]) :-
First =< Second,
ordered([Second | Tail]).
Прочитаем их описательно:
• Пустой список является перестановкой пустого списка. Перестановка непустого списка является разделением списка на элемент X и две части Left_Part и Right_Part, так, что X добавляется в начало перестановки конкатенации двух частей. Например:
permutation([7,2,9,3], [91Tail])
если Tail является перестановкой [7,2,3].
• Список с не более чем одним элементом упорядочен. Список упорядочен, если первые два элемента упорядочены, и список, состоящий из всех элементов, кроме первого, также упорядочен.
С точки зрения процедуры это не самая эффективная программа сортировки; действительно, ее обычно называют медленной сортировкой! Она просто перебирает (генерирует) все перестановки списка чисел, пока не найдет отсортированный список. Однако также просто написать описательную версию более эффективных алгоритмов сортировки типа сортировки вставкой, который мы рассмотрели на языке ML в предыдущей главе:
insertion_sort([], []).
insertion_sort([Head | Tail], List) :-
insertion_sort(Tail, Tail _1),
insert_element(Head, Tail_1, List).
insert_element(X, [], [X]).
insert_element(X, [Head | Tail], [X, Head | Tail]) :-
X=<Head.
insert_element(X, [Head Tail], [Head Tail_1]) :-
insert_element(X, Tail, Tail_1).
С процедурной точки зрения программа вполне эффективна, потому что она выполняет сортировку, непосредственно манипулируя подсписками, избегая бесцельного поиска. Как и в функциональном программировании, здесь нет никаких индексов, циклов и явных указателей, и алгоритм легко обобщается для сортировки других объектов.
Типизация и «неуспех»
В языке Prolog нет статического контроля соответствия типов. К сожалению, реакция машины вывода языка Prolog на ошибки, связанные с типом переменных, может вызывать серьезные затруднения для программиста. Предположим, что мы пишем процедуру для вычисления длины списка:
length([], 0). /* Длина пустого списка равна 0 */
length([Head | Tail], N) : - /* Длина списка равна */
length(Tail, N1), /* длине Tail */
N is N1+1. /* плюс 1*/
и случайно вызываем ее с целочисленным значением вместо списка:
?- length(5, Len).
Это не запрещено, потому что вполне возможно, что определение length содержит дополнительную нужную для отождествления формулу.
Машина вывода при вызове lenght в качестве реакции просто даст неуспех, что совсем не то, что вы ожидали. A length была вызвана внутри некоторой другой формулы р, и неуспех length приведет к.неуспеху р (чего вы также не ожидали), и так далее назад по цепочке вызовов. Результатом будут неуправляемые откаты, которые в конце концов приведут к неуспеху первоначальной цели при отсутствии какой-либо очевидной причины. Поиск таких
ошибок — очень трудный процесс трассировки вызовов шаг за шагом, пока ошибка не будет диагностирована.
По этой причине некоторые диалекты языка Prolog типизированы и требуют, чтобы вы объявили, что аргумент является или целым числом, или списком, или некоторым типом, определенным программистом. В типизированном языке Prolog вышеупомянутый вызов был бы ошибкой компиляции. В таких диалектах мы снова встречаем привычный компромисс: обнаружение ошибок во время компиляции за счет меньшей гибкости.
17.4. Более сложные понятия логического программирования
Успех языка Prolog стимулировал появление других языков логического программирования. Многие языки попытались объединить преимущества логического программирования с другими парадигмами программирования типа объектно-ориентированного и функционального программирования. Вероятно, наибольшие усилия были вложены в попытки использовать параллелизм, свойственный логическому программированию. Вспомните, что логическая программа состоит из последовательности формул:
t=>t
(t = tl || t2)^(SCtl)=>(S=>t)
(t = tl || 12) ^ (s с t2) => (s => t)
Язык Prolog вычисляет каждую цель последовательно слева направо, но цели можно вычислять и одновременно. Это называется и-параллелизмом из-за конъюнкции, которая соединяет формулы цели. Сопоставляя цели с головами формул программы, язык Prolog проверяет каждую формулу последовательно в том порядке, в котором она встречается в тексте, но можно проверять формулы и одновременно. Это называется или-параллелизмом, потому что каждая цель должна соответствовать первой или второй формуле, и т. д.
При создании параллельных логических языков возникают трудности. Проблема м-параллелизма — это проблема синхронизации: когда одна переменная появляется в двух различных целях, подобно tl в примере, фактически только одна цель может конкретизировать переменную (записывать в нее), и это должно заблокировать другие цели от чтения переменной прежде, чем будет выполнена запись. В мям-параллелизме несколько процессов выполняют параллельный поиск решения, один для каждой формулы процедуры; когда решение найдено, должны быть выполнены некоторые действия, чтобы сообщить этот факт другим процессам, и они могли бы завершить свои поиски.
Много усилий также прилагалось для интеграции функционального и логического программирования. Существует очень близкая связь между математикой функций и логикой, потому что:
y = f(xb ...,х„)
Основные различия между двумя концепциями программирования следующие:
1. Логическое программирование использует (двунаправленную) унификацию, что сильнее (однонаправленного) сопоставления с образцом, используемого в функциональном программировании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
