Примеры программ на prolog

f(N, FN) :- f(N, FN, 1, 2).
f(N, FN, N, FN) :- !.
f(N, FN, I, P) :-
NewI = I+1,
pow(2, NewI, M),
NewP = P+M,
f(N, FN, NewI, NewP).

4 Ответ от admin 2012-12-21 16:49:24

Re: Примеры программ на PROLOG

predicates
f(real, real)
pow(integer, integer, integer)

clauses
pow(X, Y, M) :- M=exp(Y*ln(X)).

f(X, FX) :-
Y = X-1,
f(Y, FY),
pow(2, X, M),
FX = M+FY.

5 Ответ от admin 2012-12-21 16:49:32

Re: Примеры программ на PROLOG

predicates
f(real, real)
f(real, real, real, real)

clauses
f(N, FN) :- f(N, FN, 1, 0.5).
f(N, FN, N, FN) :- !.
f(N, FN, I, P) :-
NewI = I+1,
NewP = P*(1-(1/(NewI*2))),
f(N, FN, NewI, NewP).

6 Ответ от admin 2012-12-21 16:49:38

Re: Примеры программ на PROLOG

predicates
f(real, real)

7 Ответ от admin 2012-12-21 16:51:39

Re: Примеры программ на PROLOG

8 Ответ от admin 2012-12-21 16:52:03

Re: Примеры программ на PROLOG

domains

Пролог — попытка объяснить без программирования

treetype = tree (string, treetype, treetype); empty ()

predicates
max(integer, integer, integer)
print_all_elements (treetype, integer, integer)

max(X, Y, X) :- X>Y, !.
max(X, Y, Y) :- Y>X, !.

print_all_elements (empty, N, MAX):- max(N, MAX, M), M>MAX, write(M), nl, !.

print_all_elements (tree (X, Y, Z), N, M):-
write (X), nl, N1 = N + 1,
print_all_elements (Y, N1, M),
print_all_elements (Z, N1, M).

goal
print_all_elements (tree («Катя»,
tree («Миша»,
tree («Вова», empty, empty),
tree («Лида»,
tree («Маша», empty, empty),
tree («Дуся»,
tree («Ира», empty, empty),
tree («Вася», empty, empty)))),
tree («Люда»,
tree («Зина», empty, empty),
tree («Петя», empty, empty))), 0, 0).

9 Ответ от admin 2012-12-21 16:52:09

Re: Примеры программ на PROLOG

domains
treetype = tree(string, treetype, treetype); empty()

predicates
pp(treetype, integer)
po(treetype)

po(empty).
po(tree(X, _, _)) :- write(X), nl, !.

pp(empty, _).
pp(tree(X, _, _), 0) :- write(X).
pp(tree(_, Y, Z), N) :- N1 = N+1, po(Y), po(Z), pp(Y, N1), pp(Z, N1).

goal
pp(tree(«Katia»,
tree(«Misha»,
tree(«Vova», empty, empty),
tree(«Lida», empty, empty)),
tree(«Liuda»,
tree(«Zina», empty, empty),
tree(«Petia», empty, empty))),
0), nl, fail; true.

10 Ответ от admin 2012-12-21 16:52:17

Re: Примеры программ на PROLOG

domains
treetype = tree(string, treetype, treetype); empty()
argument=real
result=real
predicates

Три примера решения задачек на Прологе

pp(treetype, integer)
print(treetype)
prob(integer)

prob(0):-!.
prob(N):-write(» «),N1=N-1, prob(N1).
print(empty).
print(tree(X, _, _)) :- write(X), nl, !.

pp(empty, _).
pp(tree(X, _, _), 0) :- write(X),write(«n»).
pp(tree(_, Y, Z), N) :- N1 = N+1, prob(N),print(Y),prob(N),print(Z),pp(Y, N1),pp(Z, N1).

goal
pp(tree(«Anna(0)»,
tree(«Victor(1)»,
tree(«Alexandr(2)», empty, empty),
tree(«Joneya(2)», empty, empty)),

tree(«Luda(1)»,
tree(«Vic(2)», empty, empty),
tree(«vicki(2)», empty, empty))),
0), nl, fail; true.

11 Ответ от admin 2012-12-21 16:52:23

Re: Примеры программ на PROLOG

/* Обход дерева «сначала вглубь» и печать каждого элемента, который попадается на пути. */

domains
treetype = tree (string, treetype, treetype); end()
predicates
writetree (treetype)
clauses
writetree (end).
writetree (tree (X, Y, Z)):-
write (X),
writetree (Y),
writetree (Z) ,T=+1, write(T).

goal
writetree (tree («Катя»,
tree («Миша»,
tree («Вова», end, end),
tree («Лида», end, end)),
tree («Люда»,
tree («Зина», end, end),
tree («Петя», end, end)))),nl,fail;true.

12 Ответ от admin 2012-12-21 16:52:31

Re: Примеры программ на PROLOG

/* Простые процедуры построения дерева
create_tree (A, B) помещает A в поле данных одноузлового
дерева B
insert_left (A, B, C) вставляет A как левое поддерево B
и присваивает результат C
insert_right (A, B, C) вставляет A как правое поддерево
B и присваивает результат C */

domains
treetype = tree (string, treetype, treetype); empty ()

predicates
create_tree (string, treetype)
insert_left (treetype, treetype, treetype)
insert_right (treetype, treetype, treetype)
run

clauses
create_tree (A, tree (A, empty, empty)).
insert_left (X, tree (A, _, B), tree (A, X, B)).
insert_right (X, tree (A, B, _), tree (A, B, X)).

run:-
/* Сначала создадим несколько одноузловых деревьев*/

create_tree («Вова», V),
create_tree («Лида», Ld),
create_tree («Миша», M),
create_tree («Зина», Z),
create_tree («Петя», P),
create_tree («Люда», L),
create_tree («Катя», K),

/*. затем соединим их. */

insert_left (V, M, M2),
insert_right (Ld, M2, M3),
insert_left (Z, L, L2),
insert_right (P, L2, L3),
insert_left (M3, K, K2),
insert_right (L3, K2, K3),

/*. и печатаем результат. */

Источник: itpmr.ru

Введение в логическое программирование (Prolog)

На блоге я публиковал ряд статей по логическому программированию, а также разбирал решения задач на языке Prolog. Недавно я заметил, что из всего этого могла бы получиться полноценная методичка если добавить введение. Введение написано так, чтобы после его прочтения Вы смогли начать программировать на Prolog, более строгой с математической точки зрения материал стоит искать в книгах по ФЛП [2].

Первые языки логической парадигмы программирования были разработаны в середине 20 века как инструменты для автоматического доказательства теорем, при этом в их основе лежал математический аппарат исчисления предикатов [1]. Позже их стали применять в качестве языков программирования общего назначения, при этом языки были дополнены рядом синтаксических конструкций.

Языки логического программирования имеют небольшое распространение, тем не менее их применяют при разработке трансляторов и искусственного интеллекта [2], они могут использоваться для разработки любых десктопных и мобильных приложений [3, 4], а также сайтов [5]. Компания PDC, разрабатывающая Visual Prolog, применяет его при программировании авиационных и медицинских систем (конкретные проекты можно посмотреть на официальном сайте) [6]. Сам я разрабатываю на Prolog инструменты оптимизации программ — это оказалось гораздо удобнее чем на С++, при этом пользуюсь SWI Prolog (поэтому именно на нем написаны все примеры этой статьи).

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

Логическая программа состоит из предикатов, представляющими собой функции, вырабатывающие логические значения — любой предикат содержит вычисления, которые могут быть либо истинными, либо ложными. При этом результаты вычисления предикат возвращает только если вычисления истинны. Предикаты состоят из правил (предложений), описывающих вычисления и соединенных между собой логическими операторами И/ИЛИ, при этом логическому И соответствует оператор запятая, а ИЛИ — оператор точка. Программы на языке Prolog могут содержать также переменные (их имена обязательно должны начинаться с большой буквы — этим они отличаются от других объектов), однако одним из базовых в логическом и функциональном программировании является принцип однократного присваивания, в соответствии с которым переменная может получить значение лишь один раз, все остальные попытки присваивания будут работать как проверка на равенство. Следствием принципа однократного присваивания является отсутствия циклических конструкций в Prolog — вместо них везде применяется рекурсия, что не снижает скорость работы программы, т.к. хвостовая рекурсия также эффективна, как и цикл [9].

Для понимания принципов управления вычислениями в prolog, удобно представлять программу в виде дерева как показано на примере вычисления суммы цифр числа.

digit_sum(Number, Sum):- Number < 10, !, Sum is Number. digit_sum(Number, Sum):- Digit is Number mod 10, NumberPart is Number div 10, digit_sum(NumberPart, SumPart), Sum is SumPart + Digit.

Подобное дерево строится во многих интерпретаторах языка Prolog, т.к. выбор операторов для выполнения в программе должен выполняться в порядке обхода дерева слева направо. Розовым цветом я обозначил предикат, состоящий из двух правил, выделенных зеленым цветом. Листья дерева соответствуют операциям, вычисление которых может завершится либо истиной, либо ложью. В операциях, соединенных логическим И все операции должны вернуть истинное значение чтобы результатом стала истина, поэтому если любая из таких операций завершилась ложью — результат может быть получен сразу (без вычисления остальных). Так например, если Number >= 10, то первое правило сразу завершится ложью и управление будет передано второму правилу, т.к. они соединены с помощью логического ИЛИ.

Чуть позже мы еще раз вернемся к примеру с суммой цифр числа, но сначала рассмотрим механизмы поиска с возвратами ( backtracking ) и сопоставления с образцом ( pattern matching ), которые также лежат в основе логического программирования. Рассмотрим их на примере программы вычисления стоимости покраски плоской поверхности.

colour_cost(red, 1000). colour_cost(white, 1030). colour_cost(blue, 1070). colouring_cost(Height, Width, Colour, Cost):- colour_cost(Colour, ColourCost), Square is Height * Width, Cost is Square * ColourCost.

В данном случае программа состоит из двух предикатов:

• colour_cost позволяет получить информацию о цене покраски одного метра квадратного заданным цветом, например красная краска стоит 1000 рублей, а белая — 1030. Мы можем спросить у интерпретатора:

• сколько стоит покраска белой краской?;
• у какой краски цена метра равна 1070 рублям?;
• какие есть варианты покраски? (вывести все цены);
• у каких красок цена метра квадратного ниже 1050 рублей.

• colouring_cost возвращает стоимость покраски для заданных площади и цвета, при этом для получения стоимости покраски одного метра обращается к предикату colour_cost. Мы можем написать запросы для получения всех возможных вариантов покраски заданной площади или узнать сколько будет стоить покраска определенным цветом:

В приведенном фрагменте исходного кода предикат colour_cost состоит из трех правил, в качестве аргументов правила используются константы (например red и 1000), значения которых интерпретатор пытается присвоить передаваемым переменным или выполнить сравнение. Так, например, при обработке colour_cost(Color, 1070) выбирается сначала самый левый узел дерева, поэтому переменной Color присваивается значение red, а 1070 сравнивается с 1000 — сравнение возвращает false поэтому результат работы не возвращается и интерпретатор пытается подставить следующий узел дерева (colour_cost(white, 1030)). Такой механизм называется сопоставлением с образцом.

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

Так например, при интерпретации цели всех вариантов покраски прямоугольника 10 на 5 метров с ценой менее 52000 вызывается colour_cost, который в свою очередь вызывает colour_cost(Colour, ColourCost), а значит инициирует полный перебор вариантов покраски. Для каждого варианта будет рассчитана цена, которая после выхода из функции colour_cost сравнивается с константной 52000. Если сравнение проваливается (оператор возвращает false), интерпретатор пытается найти другое решение путем возврата внутрь colouring_cost, а затем подставит следующий необработанный цвет и его стоимость. Если решение для цели найдено — результат возвращается, однако поиск все равно может быть продолжен.

На механизм поиска с возвратам, а следовательно и на управление вычислениями (порядок выполнения операторов) может влиять оператор отсечения, обозначаемое в языке Prolog восклицательным знаком (вы могли видеть его использование в примере функции вычисления суммы цифр числа). При выполнении оператора отсечения перебор решений ограничивается так, что значения всех узлов, выполненных до отсечения (находящихся в дереве «левее») считаются константами — запрещается возврат к ним для расчета других значений.

Мы уже использовали отсечение при вычислении суммы цифр числа — если число меньше десяти, то оно содержит лишь одну цифру, а значит нет смысла в рекурсивной обработке числа, т.е. переходе ко второму правилу. В связи с этим первое правило вычисления суммы содержит отсечение. Другие примеры использования отсечения [8]. Различают красные и зеленые отсечения [10].

Важной особенностью логических языков программирования является наличие встроенной базы данных. В зависимости от диалекта, встроенная БД может хранить либо только факты (предикаты, правила которых не содержат тело — как рассмотренный выше предикат colour_cost), либо произвольные предикаты. Работа с записями базы данных в Prolog происходит точно также, как и с любыми другими предикатами, однако их можно добавлять и удалять во время выполнения встроенными функциями assert и retract, чтобы это стало возможным в Vusial Prolog факты требуется описать в секции database, а в SWI Prolog — описать динамическими [11]:

:- colour_cost/2.

Тогда добавление записи в базу может быть выполнено командой assert(colour_cost(black, 900)), а удаление — retract(colour_cost(red, Cost)). В остальном работа с ними не изменится. В силу того, что записи базы данных пролога в плане обработки никак не отличаются от других предикатов (обрабатываются в соответствии с механизмом поиска с возвратами) — встроенная база данных имеет существенные отличия от баз данных SQL [12].

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

При обработке списков на Prolog учитывается их рекурсивная природа — любой список из одного или более элемента возможно разделить на первый элемент и другой список, особым видом списка является пустой список. Список может быть задан перечислением элементов в квадратных скобках — [1, 2, 3], для обозначения пустого списка используется конструкция из двух квадратных скобок — [].

Основной операцией по работе со списками является разделение списка на голову (первый элемент) и хвост (список из остальных элементов) — обозначается вертикальной чертой: [Head|Tail] = [1, 2, 3] — в результате Head = 1, Tail = [2, 3]. Обработка списка происходит рекурсивно, при этом от исходного списка отделяются первые элементы до тех пор, пока он не станет пустым (такой случай обрабатывается отдельно). Примеры рекурсивной обработки списков [13]. Списки являются тем более важными, что с их помощью в Prolog задаются строки, даже в тех диалектах, где строки не являются списком (например Turbo/Visual Prolog), для обработки их удобно преобразовать в список, т.к. это позволит применять к ним более богатый набор функций [14].

Заключение

Статья призвана объединить и сгруппировать информацию по логическому программированию, размещенную на этом блоге — в связи с этим в ней описано небольшое число примеров, но содержится много ссылок, где такие примеры можно найти. Статья является вводной, поэтому в ней разобраны лишь самые основы языка, но любой желающий читатель без труда найдет больше информации, например по работе с файлами [15]. Кроме того, статья ориентированна на начинающих, я хотел, чтобы после ее прочтения (и беглого просмотра связанных ссылок) неподготовленные читатели смогли писать простые простые программы на языке Prolog — поэтому она не содержит строго математического описания логических языков программирования (которое при желании можно найти в книгах) [2].

Литература по языку Prolog:

1. Решение логических задач на Prolog: https://pro-prof.com/archives/1299
2. Сергиевский Г.М., Волченков Н.Г.:Функциональное и логическое программирование. М.: Академия, 2010
3. Building SWI-Prolog on Android using LinuxOnAndroid: https://www.swi-prolog.org/build/linuxonandroid.html
4. Jekejeke Prolog Runtime: https://play.google.com/store/apps/details?id=jekpro.platform.headless
5. Creating Web Applications in SWI-Prolog: https://www.swi-prolog.org/howto/http/
6. Официальный сайт компании PDC: https://www.pdc.com
7. Как объяснить своей младшей сестре (9 лет) принципы логического программирования?:
8. Принципы построения программ на Prolog: https://pro-prof.com/forums/topic/semantics-prolog
9. Рекурсия в программировании. Анализ алгоритмов: https://pro-prof.com/archives/813
10. Красные и зеленые отсечения: https://pro-prof.com/forums/topic/red-green-cut-operator-prolog
11. Предикаты assert и retract: https://pro-prof.com/forums/topic/assert-retract-permanent-changes
12. Отличия базы данных SQL от Prolog : https://pro-prof.com/forums/topic/differences_prolog_sql
13. Списки в Prolog. Теория, примеры: https://pro-prof.com/archives/845
14. Преобразование строки в список символов. Turbo Prolog: https://pro-prof.com/forums/topic/string_to_list-turbo_prolog
15. Работа с файлами в SWI Prolog: https://pro-prof.com/forums/topic/read-strings-from-file-swipl

Источник: pro-prof.com

Prolog: Привет, Мир!

Prolog – язык логического программирования. В отличие от популярных языков использующих объектно–ориентированную или функциональную парадигмы Prolog использует логическую парадигму и основан на языке предикатов математической логики. Логика программы выражается в терминах отношений, представленных в виде фактов и правил.
Для того чтобы начать вычисления, выполняется специальный запрос к базе знаний, на которые Prolog генерирует ответы «истина» или «ложь». Задача пролог–программы заключается в том, чтобы доказать, является ли заданное утверждение следствием из имеющихся фактов и правил.

Изучать язык программирования, по традиции, начинают с программы ‘Hello, World!’, которая выводит этот текст на экран.

Hello, World!

В языке Prolog это будет выглядеть так:

:– write(«Hello, World!»).

В данном примере мы определяем новое правило без заголовка. Далее мы используем оператор присваивания :– . Когда Prolog видит оператор :– , он сразу выполняет тело правила, поэтому в данном случае текст появится на экране сразу после запуска программы.

С помощью команды write() мы выводим текст указанный в скобках («Hello, World!») . Сама строка обрамляется двойными кавычками «». Если этого не сделать, то компилятор укажет на синтаксическую ошибку.

# Например так ERROR: Syntax error: Operator expected ERROR: write(Hello, Worl ERROR: ** here ** ERROR: d!) .

Все правила и факты должны обязательно заканчиваться точкой.

SWISH

Двигаясь по урокам, вы постоянно будете встречаться с примерами кода и описаниями его работы. Чтобы их лучше понимать и уметь пользоваться языком, нужно постоянно практиковаться и экспериментировать. Поэтому запускайте, по возможности, все примеры из теории и проводите эксперименты с непонятными моментами. С Prolog проще всего начать на сайте swish, который позволяет запускать код прямо в браузере. Попробуйте перейти туда прямо сейчас и набрать код write(«Hello, World!»). в окне Your query goes here . .

Задание

Наберите в редакторе код из задания символ в символ и нажмите «Проверить».

:– write(«Hello, World!»).

Если вы напишете команду с большой буквы, например Write(«Hello, World!»)., то увидите ошибку компиляции. Размер буквы называют регистром, и говорят: регистр — важен!

Это касается почти всего в коде, поэтому привыкайте всегда обращать внимание на регистр.

Упражнение не проходит проверку — что делать?

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

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

В моей среде код работает, а здесь нет

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя

Это нормально , в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

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

Полезное

• Если в редакторе есть запись // BEGIN и // END , то код нужно писать между этими строчками.
• Что такое компилятор?
• SWI–Prolog

Источник: code-basics.com