Пролог обратного просмотра и проверки ввода одновременно
Я недавно начал изучать пролог, и хотя отодвигаться от функционального программирования приятно, но вещи все еще кажутся чуждыми. У меня возникли проблемы с пониманием того, как я могу написать предикат, проверяющий, соответствует ли его аргумент определенному набору правил, и в то же время, если задана переменная, он установит для него возможные значения, которые удовлетворяют этим правилам.
Я пытался решить проблему с сиденьями за круглым столом, где вы определяете набор условий, чтобы люди сидели рядом друг с другом. Таким образом, база знаний содержит 10 человек с языками, на которых они говорят, и цель состоит в том, чтобы расположить их таким образом, чтобы два человека, сидящие рядом, должны были говорить на одном языке.
Я определил предикат speaksSame(X, Y) который возвращает истину, если оба индивида X и Y говорят на одном языке. Теперь цель состоит в том, чтобы написать функцию сидения за столом так, чтобы table-seating([mark, carl, emily, kevin, oliver]) возвращает true, если каждые два человека, сидящие рядом друг с другом в списке, говорят на одном языке. Конечно, для этого каждый человек говорит на нескольких языках. А также стол для сидения (L). Получил бы возможные сидения стола, которые удовлетворяют условию.
На мой взгляд, я могу либо написать предикат, который проверяет, удовлетворяет ли ранее определенный список правилам, либо создать список в соответствии с этими правилами. Я не понимаю, как я могу сделать оба с одной функцией.
Любая помощь будет очень признательна, спасибо!
3 ответа
Я не понимаю, как я могу сделать оба с одной функцией.
Да, поначалу это кажется странным, но потом, когда вы освоите его, вы упустите его на других языках.
Слово, которое вы хотите запомнить, ссылаясь на это: режим
Также см. Справочник по режимам Mercury для более подробной информации о языке программирования Mercury.
В Прологе аргумент может быть входом и выходом, или оба могут использоваться как вход или выход в зависимости от того, как он вызывается.
В заголовках объявлений Тип, Режим и Детерминизм внизу перечислены 4 примера.
- длина (+ Список: список, -Длина:int) является дет.
- длина (?List:list, -Length:int) не определена.
- длина (? Список: список, + Длина:int) является дет.
- Истинно, если List является списком длины Length.
и определение length/2 шоу
length(?List, ?Int)
имея в виду
что за List аргумент, список может быть связан или не связан, и
что за Int аргумент, значение может быть связано или не связано.
Таким образом, для двух аргументов с двумя вариантами есть четыре способа использования length/2
Здесь они перечислены снова, но в фактическом использовании.
1.
length(+List:list, -Length:int) is det.
в этом случае List связан, а Length не связан и всегда дает один ответ.
?- length([1,2,3],N).
N = 3.
2.
length(?List:list, -Length:int) is nondet.
в этом случае List не связан, а Length не связан и может возвращать любое количество ответов.
?- length(List,N).
List = [],
N = 0 ;
List = [_5362],
N = 1 ;
List = [_5362, _5368],
N = 2 ;
List = [_5362, _5368, _5374],
N = 3 ;
List = [_5362, _5368, _5374, _5380],
N = 4 ;
List = [_5362, _5368, _5374, _5380, _5386],
N = 5
...
3.
length(?List:list, +Length:int) is det.
в этом случае List не связан, а Length связан и всегда дает один ответ.
?- length(List,4).
List = [_5332, _5338, _5344, _5350].
4.
True if List is a list of length Length.
в этом случае List связан, а Length связан и всегда действует как предикат, возвращающий либо true или же false,
?- length([1,2,3],3).
true.
?- length([1,2,3],5).
false.
Так как это возможно?
Пролог использует синтаксическое объединение (↦) и НЕ присваивание (=).
Если мы посмотрим на исходный код для length/2 с помощью listing/1 мы получаем
?- listing(length/2).
system:length(B, A) :-
var(A), !,
'$skip_list'(D, B, C),
( C==[]
-> A=D
; var(C)
-> C\==A,
'$length3'(C, A, D)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(B, A) :-
integer(A),
A>=0, !,
'$skip_list'(D, B, C),
( C==[]
-> A=D
; var(C)
-> E is A-D,
'$length'(C, E)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(_, A) :-
integer(A), !,
throw(error(domain_error(not_less_than_zero, A),
context(length/2, _))).
system:length(_, A) :-
throw(error(type_error(integer, A), context(length/2, _))).
что слишком много деталей, но делает все 4 режима правильно.
Чтобы облегчить понимание, мы будем использовать эту версию, но она не поддерживает один из режимов правильно, но делает несколько режимов, поэтому работает достаточно хорошо, чтобы продемонстрировать.
length_2([] , 0 ).
length_2([_|Xs] , L ) :-
length_2(Xs,N),
L is N+1 .
Теперь, чтобы увидеть объединение в действии, мы будем использовать функцию трассировки SWI-Prolog и разрешить всем портам для блочной модели использовать visible / 1, чтобы не останавливать его при запуске, использовать leash / 1.
?- visible(+all),leash(-all).
?- trace.
1.
[trace] ?- length_2([1,2,3],N).
Call: (8) length_2([1, 2, 3], _2352)
Unify: (8) length_2([1, 2, 3], _2352)
Call: (9) length_2([2, 3], _2580)
Unify: (9) length_2([2, 3], _2580)
Call: (10) length_2([3], _2580)
Unify: (10) length_2([3], _2580)
Call: (11) length_2([], _2580)
Unify: (11) length_2([], 0)
Exit: (11) length_2([], 0)
Call: (11) _2584 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2590 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) _2352 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
N = 3.
2.
[trace] ?- length_2(List,N).
Call: (8) length_2(_2296, _2298)
Unify: (8) length_2([], 0)
Exit: (8) length_2([], 0)
List = [],
N = 0 ;
Redo: (8) length_2(_2296, _2298)
Unify: (8) length_2([_2528|_2530], _2298)
Call: (9) length_2(_2530, _2550)
Unify: (9) length_2([], 0)
Exit: (9) length_2([], 0)
Call: (9) _2298 is 0+1
Exit: (9) 1 is 0+1
Exit: (8) length_2([_2528], 1)
List = [_2528],
N = 1 ;
Redo: (9) length_2(_2530, _2550)
Unify: (9) length_2([_2534|_2536], _2556)
Call: (10) length_2(_2536, _2556)
Unify: (10) length_2([], 0)
Exit: (10) length_2([], 0)
Call: (10) _2560 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_2534], 1)
Call: (9) _2298 is 1+1
Exit: (9) 2 is 1+1
Exit: (8) length_2([_2528, _2534], 2)
List = [_2528, _2534],
N = 2 ;
Redo: (10) length_2(_2536, _2556)
Unify: (10) length_2([_2540|_2542], _2562)
Call: (11) length_2(_2542, _2562)
Unify: (11) length_2([], 0)
Exit: (11) length_2([], 0)
Call: (11) _2566 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_2540], 1)
Call: (10) _2572 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_2534, _2540], 2)
Call: (9) _2298 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_2528, _2534, _2540], 3)
List = [_2528, _2534, _2540],
N = 3
3.
[trace] ?- length_2(List,3).
Call: (8) length_2(_5534, 3)
Unify: (8) length_2([_5724|_5726], 3)
Call: (9) length_2(_5726, _5746)
Unify: (9) length_2([], 0)
Exit: (9) length_2([], 0)
Call: (9) 3 is 0+1
Fail: (9) 3 is 0+1
Redo: (9) length_2(_5726, _5746)
Unify: (9) length_2([_5730|_5732], _5752)
Call: (10) length_2(_5732, _5752)
Unify: (10) length_2([], 0)
Exit: (10) length_2([], 0)
Call: (10) _5756 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_5730], 1)
Call: (9) 3 is 1+1
Fail: (9) 3 is 1+1
Redo: (10) length_2(_5732, _5752)
Unify: (10) length_2([_5736|_5738], _5758)
Call: (11) length_2(_5738, _5758)
Unify: (11) length_2([], 0)
Exit: (11) length_2([], 0)
Call: (11) _5762 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_5736], 1)
Call: (10) _5768 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_5730, _5736], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_5724, _5730, _5736], 3)
List = [_5724, _5730, _5736]
Action (h for help) ? abort
% Execution Aborted
4.
[trace] ?- length_2([1,2,3],3).
Call: (8) length_2([1, 2, 3], 3)
Unify: (8) length_2([1, 2, 3], 3)
Call: (9) length_2([2, 3], _2058)
Unify: (9) length_2([2, 3], _2058)
Call: (10) length_2([3], _2058)
Unify: (10) length_2([3], _2058)
Call: (11) length_2([], _2058)
Unify: (11) length_2([], 0)
Exit: (11) length_2([], 0)
Call: (11) _2062 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2068 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
true.
[trace] ?- length_2([1,2,3],5).
Call: (8) length_2([1, 2, 3], 5)
Unify: (8) length_2([1, 2, 3], 5)
Call: (9) length_2([2, 3], _2442)
Unify: (9) length_2([2, 3], _2442)
Call: (10) length_2([3], _2442)
Unify: (10) length_2([3], _2442)
Call: (11) length_2([], _2442)
Unify: (11) length_2([], 0)
Exit: (11) length_2([], 0)
Call: (11) _2446 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2452 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 5 is 2+1
Fail: (9) 5 is 2+1
Fail: (8) length_2([1, 2, 3], 5)
false.
и выключить след
[trace] ?- notrace.
true.
[debug] ?- nodebug.
true.
Я не буду проходить каждую строку в выводе трассировки, но если вы понимаете синтаксическое объединение и можете следовать трассировке, после проработки приведенных примеров вы увидите, как объединяются переменные в Prolog, что приводит к различным режимам по сравнению с императивным программирование.
Помните, что переменные связаны только один раз в Прологе и никогда не переназначаются, и что числа слева в трассировке в скобках, например (10), являются уровнем стека, поэтому, когда снова вызывается предикат, новый набор переменных становится доступным, и, хотя может показаться, что они переназначают значение, на самом деле это другая переменная в стеке, просто в другом кадре стека.
Кроме того, при изучении Пролога, я даю совет, что легче учиться, если вы откладываете то, что знаете об императивном и функциональном программировании, за исключением, возможно, рекурсии, и начинаете с нуля с объединения, а затем с обратной цепочкой.
Если вы можете прочитать OCaml, вот упрощенная версия объединения и обратной цепочки. Обратите внимание, что это не пролог, так как в нем нет списка или оператора вырезки, но если вы можете это понять, то способы объединения и обратного связывания становятся очевидными.
Я должен добавить, что я не полностью удовлетворен своим ответом, так как знаю, что вы новичок, и этот ответ содержит много информации для усвоения и требует большой работы с вашей стороны для проработки 4 примеров трассировки. Однако он отвечает на вопрос и дает практический пример с более чем достаточным количеством мяса на кости. Я работаю над попыткой придумать лучший пример, который включал бы логическую чистоту и который демонстрирует, что не только объединение, но и отношения являются ключом к тому, как несколько режимов могут быть достигнуты в одном предикате. Будь рад, что я не использовал общую теорию относительности, как перефразировал релятивист Джон Джон Арчибальд Уилер, spacetime tells matter how to move; matter tells spacetime how to curve,
Я занимаюсь Прологом в течение нескольких лет, и я чувствую, что мое утешение и понимание различных паттернов реализации пришло в несколько отдельных шагов. Первое существенное препятствие - это, конечно, рекурсия, и это все, что вам действительно нужно, чтобы разобраться с этой проблемой. По сути, вы знаете, что ваше табличное назначение для двух человек является правильным, если они говорят на одном языке, так что это ваш базовый случай:
table_seating([X,Y]) :- speaksSame(X, Y).
Так что, если вы добавите третье лицо в смесь? Вы бы сделали что-то вроде этого:
% for exposition only; do not include this clause
table_seating([A,X,Y]) :- speaksSame(A,X), speaksSame(X, Y).
Теперь, надеюсь, вы заметили, что ваша новая работа speaksSame(A,X) но ваша старая работа осталась прежней. Давайте просто позаботимся о новом человеке и поверим, что мы могли бы справиться с этим до конца списка.
table_seating([X,Y,Z|Rest]) :-
speaksSame(X, Y),
table_seating([Y,Z|Rest]).
То, что мы здесь делаем, говорит: предположим, у нас есть как минимум три элемента в списке. Тогда, если первые двое говорят на одном языке, и следующие два плюс остальные могут быть сесть, то все они могут сесть. Вы всегда можете взять правильно сидящий стол и добавить человека в переднюю часть стола, если он говорит на том же языке, что и человек, находящийся в настоящее время в передней части стола.
У рекурсии почти всегда есть такой вкус: как я могу настроить минимальную правильную ситуацию, базовый случай, а затем, как я могу правильно добавить еще одну вещь в эту ситуацию?
Интересно, что если вы предоставите этому предикату список некоторой длины, он "просто сработает" и даст решения такой длины. Попробуйте это так:
?- length(L, 6), table_seating(L).
Вы, вероятно, получите решения (я полагаю, speaksSame/2 будет генерировать решения). Это потому, что все Пролог знает об этих переменных, о которых он знает из-за вашей speaksSame/2 сказуемое. Таким образом, до тех пор, пока вы используете предикаты, которые имеют много шаблонов создания экземпляров в ваших предикатах и не навязывают вещи или странным образом не упорядочивают вещи, часто ваши предикаты наследуют эти режимы. Вот почему я рекомендую людям succ/2 вместо N is N0 + 1 или же N0 is N - 1, так как succ/2 определяет связь между двумя числами, а не выполняет некоторую арифметику (clpfd продвигает эту идею намного дальше).
В Prolog генерация и проверка - это одно и то же:
т.е. Prolog гарантирует, что правда всегда побеждает. И «убедиться» - это выполнение / оценка (которая реализована как потенциально неудачный поиск).
Таким образом, предикат просто должен выражать, что значит быть местом для сидения за столом.