Язык логического программирования PROLOG

[Shaos]

В старом форуме на shaos.ru у меня было несколько топиков про пролог - по какой-то причине они не перекочевали в этот форум - восполню этот досадный пробел цитатами оттуда.

Почитать про PROLOG можно тут - http://www.mari-el.ru/mmlab/home/prolog/study_l.html (начинать читать прямо с первой лекции - там очень интересное введение в язык с картинками)

Можно скачать бесплатный gprolog в исходниках - http://sourceforge.net/projects/gprolog

Под винду можно взять фришный Amzi! Prolog - http://www.amzi.com/download/prolog_16bit.htm

Ешё есть "условно" бесплатный Visual Prolog (потомок купленного Борландом Turbo-Prolog) - http://www.visual-prolog.com/vip6/Download/default.htm

[Shaos]

Вот моя программка для gprolog от августа 2005, которая показывает, что пролог может обойтись вообще без арифметики - сложение и вычитание описаны прямо на прологе (это я тогда вынашивал планы создания пролог-машины на мелкой логике):

Code: Select all

digit(0).
digit(1).
digit(2).
digit(3).
digit(4).
digit(5).
digit(6).
digit(7).
digit(8).
digit(9).

sym(+,43).
sym(-,45).
sym(.,46).
sym(0,48).
sym(1,49).
sym(2,50).
sym(3,51).
sym(4,52).
sym(5,53).
sym(6,54).
sym(7,55).
sym(8,56).
sym(9,57).

minus(-).
plus(+).
dot(.).

digitadd2(0,0,0,0).
digitadd2(0,1,1,0).
digitadd2(0,2,2,0).
digitadd2(0,3,3,0).
digitadd2(0,4,4,0).
digitadd2(0,5,5,0).
digitadd2(0,6,6,0).
digitadd2(0,7,7,0).
digitadd2(0,8,8,0).
digitadd2(0,9,9,0).

digitadd2(1,0,1,0).
digitadd2(1,1,2,0).
digitadd2(1,2,3,0).
digitadd2(1,3,4,0).
digitadd2(1,4,5,0).
digitadd2(1,5,6,0).
digitadd2(1,6,7,0).
digitadd2(1,7,8,0).
digitadd2(1,8,9,0).
digitadd2(1,9,0,1).

digitadd2(2,0,2,0).
digitadd2(2,1,3,0).
digitadd2(2,2,4,0).
digitadd2(2,3,5,0).
digitadd2(2,4,6,0).
digitadd2(2,5,7,0).
digitadd2(2,6,8,0).
digitadd2(2,7,9,0).
digitadd2(2,8,0,1).
digitadd2(2,9,1,1).

digitadd2(3,0,3,0).
digitadd2(3,1,4,0).
digitadd2(3,2,5,0).
digitadd2(3,3,6,0).
digitadd2(3,4,7,0).
digitadd2(3,5,8,0).
digitadd2(3,6,9,0).
digitadd2(3,7,0,1).
digitadd2(3,8,1,1).
digitadd2(3,9,2,1).

digitadd2(4,0,4,0).
digitadd2(4,1,5,0).
digitadd2(4,2,6,0).
digitadd2(4,3,7,0).
digitadd2(4,4,8,0).
digitadd2(4,5,9,0).
digitadd2(4,6,0,1).
digitadd2(4,7,1,1).
digitadd2(4,8,2,1).
digitadd2(4,9,3,1).

digitadd2(5,0,5,0).
digitadd2(5,1,6,0).
digitadd2(5,2,7,0).
digitadd2(5,3,8,0).
digitadd2(5,4,9,0).
digitadd2(5,5,0,1).
digitadd2(5,6,1,1).
digitadd2(5,7,2,1).
digitadd2(5,8,3,1).
digitadd2(5,9,4,1).

digitadd2(6,0,6,0).
digitadd2(6,1,7,0).
digitadd2(6,2,8,0).
digitadd2(6,3,9,0).
digitadd2(6,4,0,1).
digitadd2(6,5,1,1).
digitadd2(6,6,2,1).
digitadd2(6,7,3,1).
digitadd2(6,8,4,1).
digitadd2(6,9,5,1).

digitadd2(7,0,7,0).
digitadd2(7,1,8,0).
digitadd2(7,2,9,0).
digitadd2(7,3,0,1).
digitadd2(7,4,1,1).
digitadd2(7,5,2,1).
digitadd2(7,6,3,1).
digitadd2(7,7,4,1).
digitadd2(7,8,5,1).
digitadd2(7,9,6,1).

digitadd2(8,0,8,0).
digitadd2(8,1,9,0).
digitadd2(8,2,0,1).
digitadd2(8,3,1,1).
digitadd2(8,4,2,1).
digitadd2(8,5,3,1).
digitadd2(8,6,4,1).
digitadd2(8,7,5,1).
digitadd2(8,8,6,1).
digitadd2(8,9,7,1).

digitadd2(9,0,9,0).
digitadd2(9,1,0,1).
digitadd2(9,2,1,1).
digitadd2(9,3,2,1).
digitadd2(9,4,3,1).
digitadd2(9,5,4,1).
digitadd2(9,6,5,1).
digitadd2(9,7,6,1).
digitadd2(9,8,7,1).
digitadd2(9,9,8,1).

digitsub2(0,0,0,0).
digitsub2(0,1,9,1).
digitsub2(0,2,8,1).
digitsub2(0,3,7,1).
digitsub2(0,4,6,1).
digitsub2(0,5,5,1).
digitsub2(0,6,4,1).
digitsub2(0,7,3,1).
digitsub2(0,8,2,1).
digitsub2(0,9,1,1).

digitsub2(1,0,1,0).
digitsub2(1,1,0,0).
digitsub2(1,2,9,1).
digitsub2(1,3,8,1).
digitsub2(1,4,7,1).
digitsub2(1,5,6,1).
digitsub2(1,6,5,1).
digitsub2(1,7,4,1).
digitsub2(1,8,3,1).
digitsub2(1,9,2,1).

digitsub2(2,0,2,0).
digitsub2(2,1,1,0).
digitsub2(2,2,0,0).
digitsub2(2,3,9,1).
digitsub2(2,4,8,1).
digitsub2(2,5,7,1).
digitsub2(2,6,6,1).
digitsub2(2,7,5,1).
digitsub2(2,8,4,1).
digitsub2(2,9,3,1).

digitsub2(3,0,3,0).
digitsub2(3,1,2,0).
digitsub2(3,2,1,0).
digitsub2(3,3,0,0).
digitsub2(3,4,9,1).
digitsub2(3,5,8,1).
digitsub2(3,6,7,1).
digitsub2(3,7,6,1).
digitsub2(3,8,5,1).
digitsub2(3,9,4,1).

digitsub2(4,0,4,0).
digitsub2(4,1,3,0).
digitsub2(4,2,2,0).
digitsub2(4,3,1,0).
digitsub2(4,4,0,0).
digitsub2(4,5,9,1).
digitsub2(4,6,8,1).
digitsub2(4,7,7,1).
digitsub2(4,8,6,1).
digitsub2(4,9,5,1).

digitsub2(5,0,5,0).
digitsub2(5,1,4,0).
digitsub2(5,2,3,0).
digitsub2(5,3,2,0).
digitsub2(5,4,1,0).
digitsub2(5,5,0,0).
digitsub2(5,6,9,1).
digitsub2(5,7,8,1).
digitsub2(5,8,7,1).
digitsub2(5,9,6,1).

digitsub2(6,0,6,0).
digitsub2(6,1,5,0).
digitsub2(6,2,4,0).
digitsub2(6,3,3,0).
digitsub2(6,4,2,0).
digitsub2(6,5,1,0).
digitsub2(6,6,0,0).
digitsub2(6,7,9,1).
digitsub2(6,8,8,1).
digitsub2(6,9,7,1).

digitsub2(7,0,7,0).
digitsub2(7,1,6,0).
digitsub2(7,2,5,0).
digitsub2(7,3,4,0).
digitsub2(7,4,3,0).
digitsub2(7,5,2,0).
digitsub2(7,6,1,0).
digitsub2(7,7,0,0).
digitsub2(7,8,9,1).
digitsub2(7,9,8,1).

digitsub2(8,0,8,0).
digitsub2(8,1,7,0).
digitsub2(8,2,6,0).
digitsub2(8,3,5,0).
digitsub2(8,4,4,0).
digitsub2(8,5,3,0).
digitsub2(8,6,2,0).
digitsub2(8,7,1,0).
digitsub2(8,8,0,0).
digitsub2(8,9,9,1).

digitsub2(9,0,9,0).
digitsub2(9,1,8,0).
digitsub2(9,2,7,0).
digitsub2(9,3,6,0).
digitsub2(9,4,5,0).
digitsub2(9,5,4,0).
digitsub2(9,6,3,0).
digitsub2(9,7,2,0).
digitsub2(9,8,1,0).
digitsub2(9,9,0,0).

listdigit([X|T]) :- 
 minus(X),!,
 listdigitall(T).
listdigit([X|T]) :-
 digit(X),
 listdigitall(T).

listdigitall([]) :- !.
listdigitall([X|T]) :-
 digit(X),
 listdigitall(T).
 
nuke(A,L) :-
 var(L),!,
 name(A,Codes),
 nukes(Codes,L),!.
nuke(A,L) :-
 nukes(Codes,L),
 name(A,Codes),!.
 
nukes([],[]).
nukes([X|C],[Y|T]) :- 
 sym(Y,X),
 nukes(C,T).

integer1(X) :-
 nuke(X,L),
 listdigit(L).
 
add(A,B,C) :-
 integer(A),
 integer(B),
 nuke(A,L1),
 nuke(B,L2),
 listadd(L1,L2,L),
 nuke(C,L).

listadd([-|L1],[-|L2],[-|L]) :-
 listadd(L1,L2,L),!.
listadd([-|L1],L2,L) :-
 listsub(L2,L1,L),!.
listadd(L1,[-|L2],L) :-
 listsub(L1,L2,L),!.
listadd(L1,L2,L) :-
 reverse(L1,LL1),
 reverse(L2,LL2),
 listrevadd(0,LL1,LL2,LL),
 reverse(LL,L),!.

listrevadd(0,L,[],L).
listrevadd(0,[],L,L).
listrevadd(1,[],[],[1]). 
listrevadd(1,[A|L1],[],[S|L]) :-
 digitadd(1,A,0,S,C),
 listrevadd(C,L1,[],L).
listrevadd(1,[],[B|L2],[S|L]) :-
 digitadd(1,0,B,S,C),
 listrevadd(C,[],L2,L).
listrevadd(C1,[A|L1],[B|L2],[S|L]) :-
 digitadd(C1,A,B,S,C),
 listrevadd(C,L1,L2,L).

digitadd(0,A,B,S,C) :-
 digitadd2(A,B,S,C).
digitadd(1,A,B,S,C) :-
 digitadd2(A,B,S1,C1),
 digitadd2(1,S1,S,C2),
 digitadd2(C1,C2,C,_).

listsub([-|L1],[-|L2],L) :-
 listsub(L2,L1,L),!.
listsub([-|L1],L2,[-|L]) :-
 listadd(L2,L1,L),!.
listsub(L1,[-|L2],L) :-
 listadd(L1,L2,L),!.
listsub(L1,L2,L) :-
 reverse(L1,LL1),
 reverse(L2,LL2),
 listrevsub(0,LL1,LL2,LL),
 reverse(LL,LLL),
 listdelz(LLL,L),!.
listsub(L1,L2,[-|L]) :-
 reverse(L1,LL1),
 reverse(L2,LL2),
 listrevsub(0,LL2,LL1,LL),
 reverse(LL,LLL),
 listdelz(LLL,L),!.

listdelz([0|L],LL) :-
 listdelz(L,LL).
listdelz(L,L).

listrevsub(0,L,[],L).
listrevsub(0,[],_,_) :- !,fail.
listrevsub(1,[],_,_) :- !,fail. 
listrevsub(1,[A|L1],[],[S|L]) :-
 digitsub(1,A,0,S,C),
 listrevsub(C,L1,[],L).
listrevsub(1,[],_,_) :- !,fail.
listrevsub(C1,[A|L1],[B|L2],[S|L]) :-
 digitsub(C1,A,B,S,C),
 listrevsub(C,L1,L2,L).

digitsub(0,A,B,S,C) :-
 digitsub2(A,B,S,C).
digitsub(1,A,B,S,C) :-
 digitsub2(A,B,S1,C1),
 digitsub2(S1,1,S,C2),
 digitadd2(C1,C2,C,_).

В турбо-прологе этот фокус не пройдёт, т.к. тут используется предикат name (в новых прологах - atom_codes), который конвертит атом в строку или строку в атом (т.е. числа тут являются атомами).

[Shaos]

Дочке в школе задали задачку - чувак собирает в уличных автоматах сдачу, которую забыли люди - и вот за день он насобирал $1.80 в количесте 11 монет - вопрос какие это монеты?

Я решил заставить компьютер это посчитать - самый простой способ решать подобные переборные задачи это конечно же пролог (в лице gprolog):

Code: Select all

coin(1).
coin(5).
coin(10).
coin(25).
?- coin(X1),coin(X2),coin(X3),coin(X4),coin(X5),coin(X6),coin(X7),coin(X8),coin(X9),coin(X10),coin(X11),180 is X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11.

Ответ:
X1 = 5
X10 = 25
X11 = 25
X2 = 5
X3 = 5
X4 = 5
X5 = 10
X6 = 25
X7 = 25
X8 = 25
X9 = 25

[Shaos]

Задачки на арифметические выражения из слов тоже легко на прологе решаются...

[Shaos]

Сделать таки чтоли пролог-машину на фпга?

[Mixa64]

Дочке в школе задали задачку - чувак собирает в уличных автоматах сдачу, которую забыли люди - и вот за день он насобирал $1.80 в количесте 11 монет - вопрос какие это монеты?

Я решил заставить компьютер это посчитать - самый простой способ решать подобные переборные задачи это конечно же пролог (в лице gprolog):

Code: Select all

coin(1).
coin(5).
coin(10).
coin(25).
?- coin(X1),coin(X2),coin(X3),coin(X4),coin(X5),coin(X6),coin(X7),coin(X8),coin(X9),coin(X10),coin(X11),180 is X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11.

Ответ:
X1 = 5
X10 = 25
X11 = 25
X2 = 5
X3 = 5
X4 = 5
X5 = 10
X6 = 25
X7 = 25
X8 = 25
X9 = 25

А второй вариант Пролог не дает?

[b2m]

А второй вариант Пролог не дает?

Точку с запятой ; нажимать пробовал?

[Shaos]

Ну да - если семиколон нажимать, то он все вариации будет предлагать, подпадающие под условие.
Можно сузить круг ответов добавив условие, чтобы X1...X10 были расставлены по возрастанию например...

[Mixa64]

«Нажми на кнопку, получишь результат»
Стало интересно, в какие машинные конструкции прологовское задание компилится..
И пока думал про вложенные циклы, завлёк не машинный подход, он оказался интереснее. coin(1) исключился, остальное свелось к диофантову 3x+4y=19 в натуральных, а у него два решения

[Lavr]

Дочке в школе задали задачку - чувак собирает в уличных автоматах сдачу, которую забыли люди - и вот за день он насобирал $1.80 в количесте 11 монет - вопрос какие это монеты?

Что-то интересно стало: это по какому предмету задача? И как её рекомендуют решать в школе?

[Shaos]

Ну видимо по математике - дочка в третьем классе была (судя по дате публикации сообщения) - решать перебором вариантов пока не наткнёшься на подходящий

[Mondx]

Ну, по моему, логика нужна всегда, независимо от класса.)
С ребёнком соорудили светофор (написали и собрали из подручных средств).
Она была тогда 4-м классе. Так даже препод заинтересовался что да как.)