Иван Андреевич (diente_de_lion) wrote,
Иван Андреевич
diente_de_lion

Про Пролог

Захотелось мне чего-нибудь новенького, интересненького, из профессиональной сферы. Какой-нибудь язык оригинальный. Попался на глаза Haskell - ну, думаю, ща. Функциональный язык, все такое. Взял какой-то мануал, начал читать. И что же? Опять списки, опять кортежи, все тот же бессмысленный питон, только с прибаутками. Тоска. Бросил нафиг. Да и потом, если мне захочется функционального программирования - у меня всегда есть плюсовые шаблоны, есть где поизвращаться.

И тут попадается на глаза Prolog. Гляжу - что-то оригинальное. Язык тоже декларативный, но другой. Ни на что не похожий. Ты ему - условие задачи, он тебе - решение. Взять хотя бы элегантнейшее решение знаменитой "задачи Эйнштейна". Почитал мануалы - вроде все просто. Ну, думаю, надо какую-нибудь задачку забабахать ради интереса.

Долго ли, коротко ли, а вспомнилась мне задачка про ведра. Есть у нас ведро на 5 литров и ведро на 3 литра. И воды в досталь. И надобно отмерить ровнехонько 4 литра воды (или 2... или 1... какая, в общем, разница?). Когда в прошлый раз решал эту задачку в уме (да, с Маринкой смотрели долбаный сериал "Шерлок" upd. выяснилось, что это был "Крепкий орешек какой-то там", Шерлок, сорри) появилось сразу желание решить более общий случай: пусть есть ведро в M литров и ведро в N литров, надо получить K литров - возможно ли? Но как-то не дошли руки писать все этот перебор на императивном языке, а для Пролога задача кажется идеальной. Что ж, приступим.

Первое что надо сделать - определиться с тем, как описывать условие задачи. Я не мудрствуя лукаво обознгачил баклашку так:
vol(V, W)

Это обозначает, что объем канистры V литров и залито в нее в настоящий момент W литров. Состояние всей системы описал так:
state(vol(V1, W1), vol(V2, W2))

Соответственно две канистры, объемом V1 и V2 литра, в первой залито W1 литров, во второй - W2 литров. Вроде пока все просто. Далее система должна переходить из состояния в состояние. Самое простое - вылить все из канистры или налить ее до краев. Декларативно можно описать так:
move(state(vol(V1, _), X), state(vol(V1,  0), X)).
move(state(vol(V1, _), X), state(vol(V1, V1), X)).

Видно, что работаю я тут только в первой канистрой, позже объясню почему. Читается буквально так: "если у нас есть канистра объемом V1 и неважно сколько в ней воды, то из нее можно получить канистру в которой 0 (или V1) литров воды". В Прологе это - факты, у них нет условий.

А дальше нужно записать переливания. Там уже будут некоторые условия. Сначала то, что попроще. Вылить все что есть в первой канистре во вторую канистру:
move(state(vol(V1, W1), vol(V2, W2)), state(vol(V1, 0), vol(V2, W))) :- W is W1 + W2, V2 >= W.

Чтобы Пролог выполнил сложение ему надо явно указать на это оператором is - это довольно занятно. Условие V2 >= W буквально означает, что в канистру нельзя залить воды больше, чем в нее в принципе влезает. И более сложный случай - перелить из первой канистры воды столько, чтобы вторая канистра заполнилась до верху:
move(state(vol(V1, W1), vol(V2, W2)), state(vol(V1, W), vol(V2, V2))) :- W is W1 + W2 - V2, W >= 0.

Арифметика довольно нехитрая. Нужно только следить, чтобы в первой канистре не получилось отрицательного количества воды, что и задается условием W >= 0.

С первой канистрой - все. Теперь, по идее, надо все то же самое написать для второй канистры. Но есть идея получше - введем операцию "поменять канистры местами":
move(state(X, Y), state(Y, X)).

Теперь, собственно, понятно, почему достаточно было декларировать все допустимые операции только лишь для первой канистры.

Итак, все возможные изменения состояния описаны, осталось написать только выражение для поиска. Сначала определим некий "путь" состоящий из последовательных преобразований состояний системы:
path(S, G, L) :- move(S, S1), not(member(S1, L)), path(S1, G, [S1 | L]).
path(S, S, _).

Здесь S - исходное состояние, G - целевое состояние, в L храниться список состояний, которые мы прошли, чтобы не зацикливаться. Вторая строчка объясняет Прологу, что если S и G совпали, то мы пришли. Выражение для поиска теперь кажется совершенно очевидным:
search(V1, V2, W) :-
  path(state(vol(V1, 0), vol(V2, 0)), state(vol(_, W), _), []).

Параметарми V1 и V2 задаем объемы сосудов, параметром W - требуемый объем жидкости на выходе. А пролог проверяет, можно ли получить требуемый объем:
?- search(5, 3, 4).
true.

?- search(6, 3, 1).
false.

Зкспериментируя я обнаружил, что если числа взаимнопростые, то получить можно любой объем (в пределах разумного, конечно). Если же оба числа кратны какому-то другому числу, то все доступные объемы будут кратны этому числу. Вывод на экран всей последовательонсти действий для получения нужного объема я делал, это неинтересно, т.к. Пролог находит обычно неоптимальную последовательность. А вот заставить его вывести все доступные объемы... это мне показалось интересным, но пришлось поломать голову. В итоге получился у меня вот такой код:
search_all(V1, V2) :- search_all(V1, V2, []).
search_all(V1, V2, L) :- 
  search(V1, V2, W), not(member(W, L)), !, search_all(V1, V2, [W | L]); 
  sort(L, L1), write_all(L1), true.

write_all([H | T]) :- write(H), nl, write_all(T).
write_all([]).

Кажется несколько безумным, но как сделать лучше - не знаю. Учитывая, что я вообще впервые в жизни пишу на Прологе, допускаю, что вообще все что я написал можно было лучше написать как-то по-другому. С другой стороны, задачка для "Хелло Ворлд" кажется довольно крутой, на том же Питоне, допустим, я бы решать ее не взялся (а ведь я даже учил на нем программировать, о ужас). В работе вся эта канитель выглядит так:
?- search_all(5, 3).
0
1
2
3
4
5
true.

?- search_all(6, 3).
0
3
6
true.

Над запросом search_all(100, 11) Пролог очень долго думает, на search_all(100, 25) отвечает мгновенно. Как ускорить работу программы - вопрос отдельный. Вообще язык кажется очень интересным, но вот практическое применение... Не знаю даже куда можно было бы его пришить. Искусственный интеллект какой-нибудь? Задачки всякие решать на сообразительность? Широкого применения не вижу как-то. Но чисто для собственного удовольствия повозиться приятно. Рекомендую всем, кому хочется чего-нибудь необычного.
Tags: программирование, пролог
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments