Лекция: Язык Пролог
Логическое программирование идет дальше функционального. Здесь программист не только не занимается управлением памятью, но и не управляет вычислениями. (Для логической программы, например, нельзя нарисовать блок-схему).
Логическое программирование не является программированием в традиционном понимании этого слова, поскольку программист в данном случае пишет не программу-алгоритм, а логическую модель. Как правило, такая модель может быть использована для решения не одной, а ряда задач, определенного моделью круга.
Архитектура машины Фон-Неймана еще меньше приспособлена к специфике и потребностям логического программирования, чем функционального. То есть «эффективность вычислений» еще ниже.
Математическим фундаментом логического программирования служат аксиоматические теории. Например, как в случае Пролога – метод резолюции.
Язык Пролог (ПРОграммироване с помощью ЛОГики) создан А. Колмеройер 1970 году во Франции, распространен в Венгрии, Англии, Японии.
Программа на Прологе представляет из себя систему аксиом, представленных в виде не содержащих свободных переменных дизъюнктов. В Прологе используются только хорновские дизъюнкты,то естьдизъюнкты, в которых не больше одного положительного предиката. В Прологе их называют обычно предложениями или клозами.
То есть исходные аксиомы могут иметь в общем случае вид A1 & A2 &… & An ® B
что при переводе в дизъюнкты будет ØA1 Ú ØA2 Ú… ÚØAn Ú B
Дизъюнкт, состоящий только из отрицательных предикатов — вопрос. А дизъюнкт, состоящий лишь из одного положительного предиката – факт.
Примеры программы на Прологе.
1. append ([ ], L, L).
2. append ([ x | L1], L2, [x | L3]) :- append (L1, L2, L3).
Здесь [ ] выделяют список.
| — отделяет голову (первый элемент списка) от хвоста списка.
Добавим к предложениям, описывающим функцию append, вопрос: “Какой получится список при объединении списков [a, b] и [c, d]?
3. ?-append ([a, b], [c, d], z).
Выполнение программы:
2 – 3: 4: append ([a | b], [c, d], [a | z1]) :- append ( [b], [c, d], z1).
2 – 4: 5: append ([b | [ ]], [c, d], [b | z2]) :- append ( [ ], [c, d], z2).
5 – 1: 6: append ([ ], [c, d], [c, d]).
В результате получим искомое z.
z2 = [c, d]; z1 = [b | z2] = [b, c, d]
z = [a, z1] = [a, b, c, d].
Даже на такой скромной модели можно решаить не одну, а ряд задач, Например, вопрос 3`: “ Какой список надо добавить к [a, b])., чтобы получился список
[a, b, c, d]).?“
3`. ?-append ([a, b], z, [a, b, c, d]).
Обращение списка:
обращение ([], []).
обращение ([Y | T], L) :- обращение (T, Z), append (Z, [H], L).
?- обращение ([a, b, c], X).
Важной особенностью логического программирования то, что синтез конкретного алгоритма происходит