Как стать автором
Обновить

Prolog — примеры использования (Часть 2)

Время на прочтение 14 мин
Количество просмотров 102K
В первой части статьи о Prolog рассказывалось о структуре, синтаксисе и интерпретации языка. Конечно же научно-популярная литература интересна для программиста, но гораздо более интересно что-то интерактивное, живое, запускаемое. Поэтому в этой статье я предлагаю вооружиться SWI-Prolog и рассмотреть решения простейших задач на Прологе.

Прежде, чем начинать, хотелось бы кратко ответить на злободневные вопросы от хабрачитателей:
— Где реально используется Пролог?
— Такие проекты существуют, некоторые приводились в комментариях к 1-й статье. Важно что, большинство программистов пишут на Прологе не от безвыходности, а от того, что им нравится Пролог. В конце концов Пролог не может использоваться для любой задачи, такой создание UI или манипулирование с файлами.

— Почему таких проектов мало?
— Потому что программистов владеющих Пролог крайне мало, не только потому что люди не изучали его, а потому что недоизучали для написания полных программ. Главная же причина, что люди недостаточно четко понимают в каких ситуациях лучше всего его использовать. Часто можно видеть, что ярые сторонники Пролога, пишут на нем все, включая обработчиков клавиатуры и мыши, из-за чего код получается еще хуже, чем на С.

— Почему нет сообщества Пролога?
— Оно есть. Такова специфика языка, что он очень полюбился в академической среде (большинство Prolog систем пишутся в различных университетах и наоборот практически любой университет пишет свой Пролог), из-за этого можно сказать страдает и применимость языка. Стоит отметить, что сообщество небольшое, но очень лояльное: практически все известные языки нашли свое отражение в современных языках (Lisp, ML -> F#, Scala; Smalltalk -> Java, Scala (агенты), скриптовые -> Ruby), в отличие от Пролог.

Думаю на этом хватит философских рассуждений и можно приступить к реальным примерам :)

В конце как обычно ожидает задача на приз.



Пример №1 — поиск совершенных чисел


Для этого примера нам понадобится предикат is/2. X is 3 + 1 * 2 — вычисляет выражение справа и заносит в переменную слева, это не присваивание (!), а утверждение что X = 7. Проще говоря фраза X = 7, X = 3 — не имеет решения потому как X не может быть одновременно 7 и 3.
Так же нам понадобится решение задачи из предыдущего топика. Задача была написать предикат, который бы генерировал все натуральные числа подряд, вот решение:
	ints(0).
	ints(X) :- ints(Y), X is Y + 1.
	

На самом деле это декларативная версия стандартного предиката integer/1, который проверяет, что аргумент целое число. Проблема стандартного предиката, что он работает правильно для запроса :- integer(1) и не работает для запроса integer(X).

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

Не пытайтесь описать инструкции поиска решения, предположите, что вы уже нашли решение, а ваша задача только проверить, что решение найдено.

Как ни странно, но это стратегия прекрасно работает.
	%% Декларативное определение натуральных чисел
	ints(0).
	ints(X) :- ints(Y), X is Y + 1.

	%% Совершенное число - это 1) натуральное число 2) сумма делителей равна числу
	perfect_number(X) :- ints(X), Y is X - 1, calculatesum_divisors_till(Sum, X, Y), Sum = X.

	%% Проверка суммы делителей 1-й аргумент Сумма, 2-й - число для которого ищем делители, 
        %%  3-е - число до которого ищем делители
	calculatesum_divisors_till(0, _NumberToDivide, 0).
	calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0,
                Rem is NumberToDivide mod Till,  Rem = 0,  Ts is Till - 1, 
                calculatesum_divisors_till(SumPrev, NumberToDivide, Ts),
	        Sum is SumPrev + Till.

	calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, 
                Rem is NumberToDivide mod Till, Rem > 0, Ts is Till - 1, 
                calculatesum_divisors_till(Sum, NumberToDivide, Ts).
	


Вставляем исходный текст в файл, запускаем интерпретатор и компилируем его (через запрос :-compile('путь_к_файлу/perfect_numbers.pl'). Пишете запрос :- perfect_number(X). и интерпретатор выдает ответ, при нажатии ';' выдает следующий. Обратите внимание запрос может быть :- perfect_number(X), X > 6. Тогда все ответы будут больше 6. Конечно программа работает не оптимально, сама проверка может быть упрощена с использованием простых делителей, попробуйте.



Пример №2 — генерация перестановок.


Для постановки и решения этой задачи нам понадобятся понятие списков. Списки не являются базовым понятиям языка, между списками можно провести прямую аналогию со связными списками в C. Вернемся к определению терма как к рекурсивной структуре данных.
	%% Определим пустой список как объект nil
	list(nil). 
	%% Определим список из одного элемента 1 
	list(t(1, nil)).
	%% Определим список из элементов 1, 2, 3
	list(t(1, t(2, t(3, nil) ) ) ).

	%% Опишем к примеру процедуру поиска в списке
	%% 1. результат находится в голове списка (1-й элемент)
	%%  _ - означает незначимую для нас переменную
	member(X, t(Y, _)) :- X = Y.

	%% 2. результат не первый элемент, но содержится в хвосте списка после первого элемента
	member(X, t(_, Tail)) :- member(X, Tail).
	


Как многие бы сказали обычная рекурсия и чтобы списки не выглядели как-то особенно в Прологе существует синтаксический сахар для них: nil можно записать [], t(1, nil) — [1], t(1, t(2, nil)) — [1, 2], t(1, Sublist) — [1 | Sublist], t(1, t(2, Sublist)) — [1, 2 | Sublist]. Рекомендуется пользоваться синтаксическим сахаром для списков, потому как внутреннее название термов может отличаться (чаще всего терм называется '.').
	%% 1. результат находится в голове списка (1-й элемент)
	member(X, [X|_]).

	%% 2. результат не первый элемент, но содержится в хвосте списка после первого элемента
	member(X, [_| Tail]) :- member(X, Tail).
	

Вернемся к исходной задаче генерации перестановок. Все прекрасно помнят, что количество перестановок n!, но вот дай эту задачу большинству программистов и все начнут судорожно вспоминать и говорить, что писали это в школе и забыли как делается перебор. В среднем алгоритм появляется после стараний и мучений через минут 20. При знании Пролога этот алгоритм пишется за 2 минуты или не пишется вообще :)

Как же решить на Прологе? Воспользуемся правилом не поиска решения, а проверки, что решение найдено. Предикат perm(Source, Permutation) — где Source исходный список, Permutation — перестановка.

	%% Если исходный список пустой то существует одна перестановка пустой список
	perm([], []).
	%% 1-й элемент перестановки должен содержаться в исходном списке,
	%% при чем его надо сразу исключить  из оригинального списка, 
	%%  остальные элементы должны быть перестановкой перестановкой 
        %%     оставшегося оригинального списка
	perm(Source, [Element|Tail]) :- member_list_exclude(Element, Source, SourceExcluded), 
	             perm(SourceExcluded, Tail).

	%% Проверка того, что элемент содержится в списке, а 2-й список является списком без элемента
	%% Название предиката member_list_exclude соответствует порядку аргументов 
	%%  1-й - элемент, 2-й - список, 3-й - список без элементов
	member_list_exclude(X, [X|L], L).
	member_list_exclude(X, [Y|L], [Y|Ls]) :- member_list_exclude(X, L, Ls).
	

Запрос :-perm([1, 2, 3], X) генерирует все перестановки. Интересно, что запросы симметричны :-perm(X, [1, 2, 3]) относительно аргументов, правда данный запрос зависает и чтобы он работал необходимо поменять member_list_exclude и perm местами в perm.



Пример №3 — генерация сочетаний.


Генерация сочетаний по простоте реализации похожа на генерацию перестановок. Нам понадобится предикат member/2 — принадлежность элемента списку. Предположим у нас есть 2 списка: 1-й исходный список, 2-й — предполагаемое сочетание, необходимо проверить правильность сочетания. Элементы сочетания располагаются в порядке исходного списка.

	member(X, [X|_]).
	member(X, [_|L]) :- member(X, L).

	comb([], []).
	%% Вариант 1 : 1-й элемент сочетания содержится в исходном списке
	comb([X|List], [X|Tail]) :- comb(List, Tail).
	%% Вариант 2 : сочетание является правильным сочетанием хвоста списка,
	%%     то есть 1-й элемент исходного списка не содержится в сочетании
	comb([_|List], Tail) :- comb(List, Tail).
	




Пример №4 — сортировка.


Данный пример рассмотрим достаточно подробно и попытаемся провести оптимизацию первичного решения. Процесс написания на Прологе выглядит следующим образом: 1) первичное описание задачи и получение переборного решения 2) логическая оптимизация перестановкой предикатов справа 3) логическая оптимизация введения упрощенных проверок или удаление лишних условий 4) введение эвристик и оптимизация отдельних случаев путем отсечений.

Вариант 1. Сортировка наивная : первый элемент отсортированного массива должен быть минимальным, остальные элементы должны быть отсортированы. Первый массив исходный, второй массив отсортированный исходный.

	sort([], []).
	sort(List, [Min|SortRest]) :- min_list_exclude(Min, List, Exclude), sort(Exclude, SortRest).

	%% Рекурсивно исключаем минимальное число, если в списке одно число исключаем его
	min_list_exclude(M, [M],  []).
	min_list_exclude(Min, [M|L],  ExcludeRes) :- min_list_exclude(Ms, L, Exclude), 
	          find_result(result(M, L), result(Ms, [M|Exclude]), result(Min, ExcludeRes)).

	%% Дополнительный предикат для определения пары с минимальным ключом
	find_result(result(M, L), result(Ms, _), result(M, L)):- M < Ms. 
	find_result(result(M, _), result(Ms, Exclude), result(Ms, Exclude)):- Ms =< M. 

	

Можно заметить, что сложность данного алгоритма квадратичная и основная проблема в том, что мы каждый раз ищем минимальный элемент, не сохраняя при этом никакой полезной информации.
Отметим также, что мы пытаемся определить, что такое 1-й элемент отсортированного массива.

Вариант 2. Быстрая сортировка. Посмотрим на проблему со второй стороны и попытаемся определить место 1-го элемента списка в отсортированном массиве (применим рекурсию к исходному массиву).

	sort_b([], []).
	sort_b([T|R], List) :- split(T, R, Less, Great), sort_b(Less, LessSort), sort_b(Great, GreatSort), 
	                                append(LessSort, [T|GreatSort], List).

	%% Разделяем массив на 2 массива больше и меньше
	split(_, [],[], []).
	split(T, [M|R],[M|Less], Great) :- M < T, split(T,R, Less,Great).
	split(T, [M|R],Less, [M|Great]) :- M >= T, split(T,R, Less,Great).

	%% Склеиваем 2 списка
	append([], M, M).
	append([L|Left], Right, [L|Res]) :- append(Left, Right, Res).
	

Можно заметить, что мы улучшили результаты сортировки, так как быстрая сортировка заведомо быстрее пузырьковой. Для того, чтобы еще улучшить результаты, мы можем вспомнить сортировку слияниями, которая в любом случае дает O(n lg n), но к сожалению данная сортировка применима только к массивам, а не к связным списка, с которыми мы работаем. Единственный вариант использовать дополнительную структуру данных для хранения — дерево.

Вариант 3. Сортировка с использованием бинарного дерева.

Для данного вида сортировки переведем исходный список в бинарное дерево, а затем, воспользовавшись обходом дерева слева, получим отсортированный массив. Дерево будем представлять рекурсивным термом tree(Object, LeftSubTree, RightSubTree).
	sort_tree([], nil).
	sort_tree([X|L], Tree) :- sort_tree(L, LTree), plus(X, LTree, Tree).

	%% Добавление в элемента в дерево
	plus(X, nil, tree(X, nil, nil)).
	plus(X, tree(O, L, R), tree(O, ResL, R)) :- O >= X, plus(X, L, ResL).
	plus(X, tree(O, L, R), tree(O, L, ResR)) :- O < X, plus(X, R, ResR).

	sort_t(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y).

	append_list([], L, L).
	append_list([X|L], R, [X|T]) :- append_list(L, R, T).

	tree_list(nil, []).
	tree_list(tree(X, L, R), List) :- tree_list(L, ListL), tree_list(R, ListR),
	    append_list(ListL, [X|ListR], List).
	


Вариант 4. Сортировка с использованием сбалансированного бинарного дерева.

Проблема использования бинарного дерева такая же как использования быстрой сортировки. Метод не гарантирует оптимальной работы. В случае бинарного дерева, дерево может быть разбалансировано и процедура добавления элемента в него может быть линейна, а не логарифмична. Специально для этого выполняются процедуры балансировки дерева, ниже для ознакомления будет приведен алгоритм с использованием АВЛ-дерева.

	sort_btree(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y).

	tree_list(nil, []).
	tree_list(tree(X, L, R, _), List) :- tree_list(L, ListL), tree_list(R, ListR),
	    append(ListL, [X|ListR], List).

	sort_tree([], nil).
	sort_tree([X|L], Tree) :- sort_tree(L, LTree), plus_tree(X, LTree, Tree).

	construct_tree(A, AL, AR, tree(A, AL, AR, ADepth)) :- diff(AL, AR, _, ADepth).
	diff(AL, AR, ADiff, ADepth) :- depth_tree(ALs, AL), depth_tree(ARs, AR), 
				ADiff is ALs - ARs, max_int(ALs, ARs, AD), ADepth is AD + 1.

	max_int(A, B, A) :- A > B.
	max_int(A, B, B) :- A =< B.

	append([], L, L).
	append([X|L], R, [X|T]) :- append(L, R, T).

	depth_tree(0, nil).
	depth_tree(X, tree(_, _, _, X)).

	plus_tree(X, nil, tree(X, nil, nil, 1)).
	plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep),
			 balance_tree(tree(O, ResL, R, Dep), Diff, Res).
								
	plus_tree(X, tree(O, L, R, _), Res) :- O < X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep),
			 balance_tree(tree(O, L, ResR, Dep), Diff, Res).

	%% No rotations
	balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff > -2.
	%% Small right rotation
	balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- 
			ADiff > 1, diff(BL, BR, BDiff, _), BDiff >= 0, 
	                construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Result).

	%% Big right rotation
	balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- 
			ADiff > 1, diff(BL, BR, BDiff, _), BDiff < 0, BR = tree(C, CL, CR, _), 
	                construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree),
	                construct_tree(C, BSubTree, ASubTree, Result).

	%% Small left rotation
	balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- 
			ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0, 
	                construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result).

	%% Big left rotation
	balance_tree(tree(A, AL, tree(B, BL, BR, _),  _), ADiff, Result) :- 
			ADiff < -1, diff(BL, BR, BDiff, _), BDiff > 0, BL = tree(C, CL, CR, _), 
	                construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree),
	                construct_tree(C, ASubTree, BSubTree, Result).
	

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



Пример №5 — Задача о переливаниях.


В качестве следующей задачи рассмотрим классическую задачу о состояниях, эта задача гораздо лучше отражает преимущества использования Пролог. Общая постановка задачи: даны некоторые емкости с водой, необходимо путем переливаний получить определенное количество воды в некоторой емкости. Для примера возьмем 3 кувшина емкостью 12 литров, 8 литров, 5 литров, наполним 1-й полностью, то есть 12 литрами и поставим задачу получить 6 литров. Для начала попытайтесь решить эту школьную задачу при помощи ручки и листка бумаги :)

Прежде чем генерировать различные алгоритмы и пытаться их применить к задаче, давайте сначала перепишем условия в терминах Пролога. Опишем емкость как терм sosud(Id, MaximumCapacity, CurrentCapacity), состояние системы опишем как список емкостей. Пример [sosud(1, 12, 12), sosud(2, 8, 0), sosud(3, 5, 0)]. Теперь опишем запрос:

        %% solve_pr_wo(InitialState, Goal, Steps).
	 :- solve_pr_wo([sosud(1, 12, 12), sosud(2, 8, 0), sosud(3, 5, 0)], sosud(X, _, 6), Steps).
        


Обратите внимание, что Goal = sosud(_, _, 6), то есть нам не важно какой емкости сосуд главное чтобы в нем было именно 6 литров.

Теперь когда нам все известно опишем способ проверки решения, считая что шаги заданы в переменной Steps.

	%% Для получения состояния не требуется ни одного шага, 
	%%  значит один из сосудов находится в списке
	solve_pr_wo(State, Goal, []) :- member(Goal, State).

	%% Первый шаг это перелить из Sosud в Sosud2 и получить состояние 
	%% первого сосуда ResSosud, а второго ResSosud2.
	%% Конкретный пример шага :
        %%  mv(sosud(1, 12, 12) -> sosud(2, 8, 0),  sosud(1, 12, 4) -> sosud(2, 8, 8)).
	solve_pr_wo(State, Goal, [mv(Sosud -> Sosud2 , ResSosud -> ResSosud2)| Steps]) :- 
	                        %% В первую очередь проверка домена, что сосуды действительно 
	                        %% содержатся в текущем состоянии и они не равны друг другу
				member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), 

	                        %% Осуществление самого переливания, здесь 
                                %% участвуют все 4 переменных шага
				mv(Sosud, Sosud2, ResSosud, ResSosud2),
	                        %% Замена состояния сосудов в списке состояний по очереди
	                        replace(Sosud, State, ResSosud, State2), 
                                replace(Sosud2, State2, ResSosud2, StateX),
	                        %% Дальнейшие шаги должны выполняться по рекурсии 
	                        solve_pr_wo(StateX, Goal, Steps).

	%% На самом деле обычная замена элемента в списке
	%% replace(ElementToReplace, InList, ElementToReplaceWith, OutList).
	replace(S, [S|L], X, [X|L]).
	replace(S, [T|L], X, [T|Ls]) :- replace(S, L, X, Ls).

	%% Процедура переливания - 2 варианта
        %% исходный сосуд будет исчерпан или целевой наполнен

	%% Опустошение первого сосуда во второй 
	mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), 
		sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- 
			Current > 0, Current3 is Current2 + Current, Current3 =< Max2.

	%% Переливание из первого сосуда до краев второго
	mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), 
		sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- 
			Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.
	


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

Что же, описание программы написано — можно запустить. Не стоит удивляться программа не заработает, оно попросту зависнет :) Это не так плохо как может показаться, потому что если бы программа не зависла, то она выдала бы правильный ответ. Следует разобраться почему же она зависла и здесь нам на помощь придет понимание как же Пролог разворачивает правила, чтобы найти решение. На самом деле, не надо иметь голову способную запомнить до 10 точек возврата, чтобы понять, что каждый следующий раз когда solve_pr_wo -> вызывает по рекурсии solve_pr_wo, он вызывает 2 предиката member/2, которые всегда выдают одно и то же 1-й и 2-й сосуд (предикат not вызывает backtracking и не позволяет member выбрать 1-й и 1-й сосуд). То есть алгоритм постоянно переливает из 1-го во 2-й и обратно.

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

Полная версия программа с распечаткой состояний и единственным предикатом для вызова solution:

	write_list([]).
	write_list([X|L]) :- writeln(X), write_list(L).

	solution :- solve_pr([sosud(1, 12, 12), sosud(2, 8, 0), sosud(3, 5, 0)], sosud(_, _, 6), [], Steps), 
		    write_list(Steps).

	replace(S, [S|L], X, [X|L]).
	replace(S, [T|L], X, [T|Ls]) :- replace(S, L, X, Ls).

	%% будем считать стратегией переливания не сами шаги, а просто конечные состояния
	%% зная начальное и конечное состояние, не трудно догадаться, какой шаг был выполнен
	solve_pr(State, Goal, _, [State]) :- member(Goal, State).
	solve_pr(State, Goal, History, [State|Steps]) :- 
				member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), 
				mv(Sosud, Sosud2, ResSosud, ResSosud2),
	                        replace(Sosud, State, ResSosud, State2),
                                replace(Sosud2, State2, ResSosud2, StateX),
	                        %%% та самая проверка конечного состояния
			        not(member(StateX, [State|History])), 
	                        solve_pr(StateX, Goal, [State|History], Steps).


	%% mv(sosud(_Id, Max, Current), sosud(_Id2, Max2, Current2), ...,...).
	%% Опустошение первого сосуда во второй 
	mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), 
		sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- 
			Current > 0, Current3 is Current2 + Current, Current3 =< Max2.

	%% Переливание из первого сосуда до краев второго
	mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), 
		sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- 
			Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.
	


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

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



Заключение



Хотелось бы отметить, что задачи рассмотренные в данной статье являются этюдами для программирования на Прологе. Так как большинство из них занимает около 10-15 строк, то программист на Прологе в состоянии воспроизвести их по памяти при достаточном частом порешевании их. А возвращаться к ним обязательно стоит, так как это напоминает об искусстве программирования (точно так же как быстрая сортировка на C). Более сложные и более прикладные задачи для повседневного использования будут рассмотрены позже.

В конце аж 2 задачки на приз :
  1. Как известно в функциональном и логическом всячески пытаются избежать программ с side эффектами, оборачивают их в монады, придумывают специальные концепции. Стандартная проблема — это проблема внешнего мира, например, запись данных в файл, невозможно откатить запись в файл или отменить отсылку нескольких байт по сокету, а следовательно бэктрекинг будет работать не совсем корректно. Совет один — не используйте для этих целей Пролог. Но есть такие предикаты, которые очень хороши и специфичны для Пролога, но имеют side effect. Пример assert (asserta, assertz): он добавляет в базу правил (фактов) простое правило (факт). Пример assert(prime(3)): добавляет факт, что 3 простое число и запрос :-prime(X), теперь будет выдавать 3, даже при пустой исходной программе.

    Задача: написать декларативную версию assert, то есть при возврате программы по бэктрекингу факт не должен оставаться в памяти, а должен работать как логическое предположение.

    Пример работы: запрос c(X) должен выдавать одно число 4 для следующей программы!
                  a(X) :- b(Y), X is Y + 1 .
                  c(X) :- my_assert(b(3)), a(X).
                  c(X) :- b(X).
             

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

    Задача: дан некоторый одноместный предикат a/1 (в общем случае множество элементов не ограничено, может быть бесконечно), написать предикат subset_a/1, который будет выдавать подмножества, состоящие из элементов множества a.

    Пример: запрос subset_a(X) выдает X = [], X = [1], X = [2], X = [1, 2] (порядок не важен):
                  a(1).
                  a(2).
                  subset_a(X) :- ....?
             



Спасибо за внимание.
Теги:
Хабы:
+37
Комментарии 62
Комментарии Комментарии 62

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн