← All posts tagged Prolog

omnivore

решил проверить tuprolog — реализацию пролога на java. И в итоге я оказался разочарован скоростью его работы. Вот для сравнения за сколько отрабатывают разные пролог-машины на повторяемом 600 раз вычислении палиндрома списка из нескольких десятков элементов с помощью давнешнего рефал-модуля:

tuprolog — 15 секунд
swi prolog — 0.1 секунды
yap — 0.03 секунды

Один плюс у этого тупролога, что у него еще есть экспериментальный пакет для андроида. И хотя там указано, что он для версии >= 2.3.1, но все нормально запускается и на моем 2.2 Froyo.

omnivore

Продолжаем играться с прологом и рефалом. На этот раз добавим к нашей реализации рефаловского сопоставления по образцу жадные(greedy) переменные.

Напомню, что в языке Рефал есть такая интересная возможность, как паттерн-матчинг с так сказать "опережающим" поиском. (про Рефал писали, например, в недавнем номере ПФП). Т.о., предикат списка-палиндрома в рефале можно описать так:

Pal {
s.1 e.2 s.1 = ;
s.1 = True ;
= True;
e.1 = False ;
}

где e. переменные могут принимать любое значение подсписка (пустой, из одного или более элементов), а s. — один элемент списка.

Мы пытаемся построить с помощью пролога такой DSL, который позволил бы использовать рефаловское сопоставление по образцу (попутно добавив несколько других интересных плюшек :).

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

==
?- re([e(A), e(B)], [1,2,3]).
A = [],
B = [1, 2, 3].

?- re([e*(A), e(B)], [1,2,3]).
A = [1, 2, 3],
B = [].
==

Как видите, во втором примере "жадная" переменная A захватила максимально допустимое паттерном число элементов. Еще пример:

==
?- re([e(A), s(B), e(C)], [1,2,3]).
A = [],
B = s(1),
C = [2, 3].

?- re([e*(A), s(B), e(C)], [1,2,3]).
A = [1, 2],
B = 3,
C = [].
==

Добавим еще один тип переменных — непустые e-переменные. Назовем их "e+" переменные. Пример использования:
==
?- re([e+(A), e(B)], [1,2,3]).
A = [1],
B = [2, 3].

?- re([e*(A), e+(B)], [1,2,3]).
A = [1, 2],
B = [3].
==

И, в заключении, самый интересный, на мой взгляд, пример. Не забываем, что под капотом у нас пролог:
==
?- re([A,B], [1,2,3]).
A = s(1),
B = e([2, 3]).
==

В этом примере мы не указали тип переменных A и B, и пролог подставляет возможные значения типов переменных сам! Подставляет так, чтобы удовлетворить ограничению в две переменные. (замечу, что предлагается только 1 вариант, т.к. в реализации нашего DSL каждое правило оканчивается отсечением).

Вот такой вот получился наколеночный рефал :)

p.s. исходный код этой поделки на pastebin.com

omnivore

скачал 5й рефал, скомпилял и сравнил скорость вычисления палиндрома :) Рефал считает на порядок быстрее (в 10 с небольшим раз быстрее), чем моя прологовская реализация "рефаловского" сопоставления по образцу из предыдущего поста. Не так и плохо, я доволен :) Все-таки там ядро на си и идет компиляция в байткод.

omnivore

попытаемся реализовать "рефаловское" сопоставление по образцу с помощью пролога. В рефале есть интересная возможность паттерн-матчинга с т.с. "опережающим" поиском. (про язык Рефал писали в недавнем номере ПФП).

Т.е. например предикат списка-палиндрома в рефале можно описать примерно так (синтаксис некоего условного рефал-языка взят по памяти):

pal( ).
pal(s.X).
pal(s.X e.Y s.X) :- pal(e.Y).

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

Но кроме как в рефале в явном виде такого механизма, как будто, и нет. Попытаемся реализовать такое поведение на прологе:

pref([], [X|Xs], [X|Xs]).
pref([X|Prefix], [X|List], Rest) :- pref(Prefix, List, Rest).

re([X | Pat], [X|Xs]) :- re(Pat, Xs), !.
re([e(X) | Pat], Xs) :- pref(X, Xs, Rest), re(Pat, Rest), !.
re([e(X)], X) :- !.
re([], []) :- !.

И теперь предикат списка-палиндрома на прологе можно записать так:

pal([]) :- !.
pal([X]) :- !.
pal(A) :- re([X, e(Y), X], A), pal(Y).

получился почти рефал :)

omnivore

а вот хочется мне рефаловского паттерн-матчинга в прологе. посоветуйте какой инструмент лучше использовать? в идеале бы расширение синтаксиса для какого-нибудь swi-prolog'а