Язык программирования Пролог (в английской транскрипции Prolog, читается с ударением на первый слог) — декларативного типа, относится к языкам логического программирования. Один из немногих такого типа. Считается классическим языком для обучения основам написания кода. Во многих вузах бывшего СНГ его преподают на начальных курсах. В советское время активно изучали в школах и техникумах. Программирование на нём развивает мышление, умение строить предложения в рамках текущей семантики правильно, без ошибок. Несмотря на то, что он практически не используется в решении обычных задач, за исключением некоторых случаев, когда это делается горячими поклонниками Пролога, решение задач как обычной, так и олимпиадной сложности на нём помогает в высокой степени развить основные навыки написания программ.
Задача о рыцаре, лжеце и шпионе
Итак, задача, которая будет решаться с помощью Пролога, была сформирована в книге «Алиса в стране смекалки» Р. Смаллиана. Там есть и другие интересные задачи, которые тоже можно было бы решить с помощью этого языка. Формулировка задачи следующая.
В суд привели рыцаря, лжеца и шпиона. Рыцарь всегда говорит только правду. Лжец всегда лжёт. Шпион может говорить и правду, и лгать. Все трое знают друг о друге, кто из них кто, но суду также хотелось бы выяснить это. Первый подсудимый утверждает, что шпионом является второй. Второй говорит, что шпион — это третий. Третий говорит, что шпион — кто-то из первых двух, но не он. Кто из них кто?
Обычно для решения задачи без использования программирования предлагается нарисовать некоторую таблицу решений, а затем выбрать из них то, которое непротиворечиво. Однако можно сделать гораздо проще — использовать язык программирования. Давайте разберёмся, как с помощью Пролога можно решить данную задачу.
Пишем код программы
Пролог — декларативный язык программирования. Поэтому будет очень важно сформулировать задачу. Как происходит её решение — будет рассмотрено далее. Переходим к написанию кода, далее идёт только он. Все пояснения будут даны в соответствующих /*комментариях*/, которые заключены между косой чертой и звёздочкой. Имена в программе будут даваться на кириллице, так как Prolog поддерживает такой формат. Да и читателям, особенно младшим, так будет понятнее. Текст программы можно просто скопировать в файл, и она должна оттуда выполняться.
/*
Начало программы.
*/
/*
Итак, у нас есть трое подсудимых. Запишем это:
*/
подсудимый(‘рыцарь’).
подсудимый(‘лжец’).
подсудимый(‘шпион’).
/*
Имена подсудимым даются в одинарных кавычках, это строковые константы, они не меняют своё значение в ходе выполнения программы. «Подсудимый» — это предикат. Он может быть как истинным, так и ложным. То есть утверждение, что подсудимый рыцарь, шпион или лжец, может быть истинным или ложным.
*/
/*
Подсудимые могут давать показания, в данном случае у них спрашивают, кто есть кто. Рыцарь всегда говорит правду, лжец всегда лжёт, а шпион может говорить что угодно. Запишем в виде предикатов.
*/
показания (‘рыцарь’, X, X).
показания(‘лжец’, X, Y) :- not (X=Y).
показания (‘шпион’, _, _).
/*
То есть рыцарь говорит то, что есть на самом деле, X, X, где первое значение — то, что он сказал, второе — то, что есть на самом деле. Лжец всегда лжёт, то, что он сказал, всегда противоречит истине. Ну и шпион может сказать что угодно.
*/
/*
Запишем, что сказали первые два. Первый утверждает, что шпион второй, второй — что шпион это третий.
*/
промежуточное_решение(A, B, C):-
подсудимый(A),
подсудимый(B),
подсудимый(C),
not(A=B), not(A=C), not(B=C),
показания(A, B, ‘шпион’),
показания(B, C, ‘шпион’).
/*
Здесь записано, что есть подсудимый А, B, C, и каждый может быть только одним — рыцарем, лжецом или шпионом. То есть два шпиона или два рыцаря быть не может. Первый утверждает, что шпион второй, второй — что шпион это третий. Запятая означает логическое «и», not – логическое «не».
*/
/*
Третий говорит, что шпион — кто-то из первых двух. В принципе, он может быть даже и рыцарем, так как общий смысл его высказывания, если даже он ошибётся в отношении одного из них, может быть верным. Но кто? Это порождает два варианта решения.
*/
решение1 (A, B, C) :-
промежуточное_решение (A, B, C),
показания (C, A, ‘шпион’).
решение2 (A, B, C) :-
промежуточное_решение(A, B, C),
показания(C, B, ‘шпион’).
/*
Истиной может быть две ситуации, так как третий указывает на первых двух, а не на кого-то одного. Либо выполняется промежуточное решение, при этом показания третьего падают на первого, что он шпион, либо промежуточное решение, и при этом показания третьего говорят о втором, что он шпион.
*/
/*
Окончательное решение формируется из двух предыдущих решений задачи — оно будет истинным только тогда, когда оба, и решение 1, и решение 2, будут истинными. Запишем в виде логического «и».
*/
решение(A, B, C) :- (решение1(A, B, C)), (решение2(A, B, C)).
/*конец программы*/
Итак, мы сформировали общее решение задачи и её условия, то, что есть рыцарь, лжец и шпион, что они говорят друг о друге, сформировали в виде отдельного решения, когда правда то, что третий говорит о первом или правда то, что первый говорил о втором, а затем объединили их в одно общее решение, в котором решение1 и решение2 оба могли бы быть истинными. Теперь исполним данную программу на языке Пролог. В среде программирования SWI-Prolog необходимо после записи программы в файл выбрать опцию Consult, а затем выбрать файл, в котором записана программа. После этого просим Пролог вывести результат решения:
>?- решение(A, B, C).
И получаем результат:
A=лжец
B=рыцарь
C=шпион.
Других решений данная задача не имеет. При желании можно также посмотреть и все результаты других предикатов, в том числе промежуточное_решение, решение1 и решение2 — это может быть важно для того, чтобы понять, как работает программа.
Что делает Пролог во время выполнения программы
Задача средой программирования решается методом простого перебора. Вначале возможны три значения переменных А, B и C: рыцарь, лжец или шпион. Все эти три значения по очереди подставляются в условие задачи, и производится проверка программы на истинность итогового решения. Если истинность не подтверждается, то одно из значений меняется, и производится новая проверка решения — так до тех пор, пока не будет найдено истинное решение.
Данный метод, на самом деле, применяется во всех декларативных языках программирования, в том числе и другого типа: Scheme, Erland, Haskell, Lisp, Lua, если, конечно, используется декларативный стиль программирования в них. Оптимизация проверки и подстановки вариантов решения — это уже следующий этап развития программиста, который потребует хорошего знания алгоритмов.
Здесь же язык программирования может считаться «чёрным ящиком», который выдаёт верное решение, исходя из исходных данных. Также может быть выдано пустое решение, результат false, если такого не существует, или множество решений — для этого при получении решений нужно на клавиатуре нажимать «;», чтобы получить следующий подходящий вариант. В задачу программиста входила лишь правильная формулировка задачи так, чтобы машина могла с ней работать, а это самое важное.
