Язык Пролог

Логическое программирование.

Логическое программирование идет дальше функционального. Здесь программист не только не занимается управлением памятью, но и не управляет вычислениями. (Для логической программы, например, нельзя нарисовать блок-схему).

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

Архитектура машины Фон-Неймана еще меньше приспособлена к специфике и потребностям логического программирования, чем функционального. То есть «эффективность вычислений» еще ниже.

Математическим фундаментом логического программирования служат аксиоматические теории. Например, как в случае Пролога – метод резолюции.

Язык Пролог (ПРОграммироване с помощью ЛОГики) создан А. Колмеройер 1970 году во Франции, распространен в Венгрии, Англии, Японии.

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

То есть исходные аксиомы могут иметь в общем случае вид A₁ & A₂ & ... & A_n ® B

что при переводе в дизъюнкты будет ØA₁ Ú ØA₂ Ú ... ÚØA_n Ú 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).

Важной особенностью логического программирования то, что синтез конкретного алгоритма происходит