Язык логического программирования PROLOG (далее – ПРОЛОГ) большинству программистов представляется чем-то запутанным и малопригодным для практического применения. В то же время, Интернет основан на символьной информации, поэтому практически все современные программисты сталкиваются с необходимостью обрабатывать символьные структуры данных, а ведь для этого и предназначен язык логического программирования ПРОЛОГ. Этот язык – идеальный для работы с символьными структурами, текстовыми файлами и для построения интеллектуальных программ.
После многолетней работы с ПРОЛОГом, столкнулся с новомодным Haskell, о котором все авторы гордо говорят – «высокий порог вхождения». По-моему, «высота» этого порога образовалась в результате запутанного синтаксиса и нагромождения встроенных процедур. Еще один источник этой «высоты» — высокомерие авторов многочисленных руководств, которые написаны так, будто читатель никогда программ не писал.
Сразу захотелось назад, к «родному» ПРОЛОГу – простому и понятному. Думаю, если объяснить без нагромождений, типа декларативной семантики, время вхождения в логическое программирование для «обычного» программиста не превысит 30 минут.
Попробую описать его с точки зрения процедурного программирования.
ПРОЛОГ имеет два основных отличия от процедурных языков — способ организации вычислений и способ представления данных. Оба этих аспекта языка коренным образом отличаются от традиционных языков программирования. Но не будем забывать, что логическое программирование реализуется на тех же машинах с фон — Неймановской архитектурой.
Представим себе язык программирования, в котором все операции сводятся к вызову процедур. При этом каждая процедура существует в нескольких вариантах и программа сама выбирает себе правильный, точнее говоря, пригодный для каждого конкретного варианта исходных данных вариант реализации (тело) процедуры. Как определяется пригодность – каждый вызов процедуры, во время исполнения программы, по результатам исполнения процедуры, получает логическое значение – TRUE или FALSE. Совокупность процедур с одинаковым именем и арностью называется предикатом.
Каждый предикат в языке ПРОЛОГ идентифицируется двумя параметрами –именем и арностью – количеством параметров. Например, предикат инвертирования списков идентифицируется, как nrev/2, а предикат соединения списков как append/3. Никакого объявления параметров или переменных не требуется, но можно ограничить параметры паттерном в заголовке процедуры. Например, в одном варианте предиката первый параметр может быть указан как [] – пустой список, в другом – как [A,B,C] – список из трех элементов, а в третьем как [H|T] – произвольный непустой список.
Если какое-то условие в теле процедуры не выполняется, выполнение прекращается и вызов процедуры, точнее говоря, выполнение очередного варианта тела процедуры, прекращается и получает значение FALSE. В этом случае, интерпретатор языка запускает следующий по порядку вариант тела этой процедуры. Если же все варианты оказались непригодными, происходит возврат к предыдущей процедуре и для нее также происходит перебор вариантов, таким образом, вычисление в ПРОЛОГе сводится к обходу дерева вложенности процедур.
Возврат к предыдущему вызову называется бэктрекингом (backtracking). По существу это откат, поскольку все значения, полученные переменными в отмененной процедуре, отменяются. Бэктрекинг – уникальное средство данного языка, не имеющее аналогов ни в одном из других массовых языков программирования. Бэктрекинг обеспечивает полный обход дерева логического вывода, что обеспечивает основу для решения интеллектуальных задач.
Алгоритм интерпретации программы (выполнения цели) в системе ПРОЛОГ.
Вход: цель p(A1,A2,…,An)
1. Найти в памяти процедуру по имени p с арностью n.
2. Унифицировать входные параметры цели с заголовком найденной процедуры.
3. Если унификация параметров прошла, выполнить первую цель из тела найденной процедуры.
4. Если унификация не прошла, найти следующий вариант процедуры P/n.
5. Если следующий вариант процедуры P/n не найден, закончить работу с результатом FAIL.
6. Если первая цель выполнилась, перейти к выполнению следующей цели.
7. Если следующая цель не выполнилась, вернуться к предыдущей цели и выполнить следующий вариант ее реализации.
8. Если текущий вариант реализации процедуры P/n не выполнился, перейти к следующему варианту.
9. Если все цели из тела процедуры выполнены, закончить работу с результатом TRUE.
В связи с такой структурой вычислений каждый вызов процедуры называется целью, которая может быть достигнута или нет. Всякое вычисление в ПРОЛОГе имеет логическое значение. Вычисление еще называют поиском вывода (доказательства), а язык ПРОЛОГ – языком логического программирования.
Наверное, синтаксически ПРОЛОГ – самый простой среди языков программирования. Основной синтаксической процедурой является предикат – выражение, аналогичное вызову процедуры — имя и список аргументов –
P(x1, …xn). Имена пишем с малой буквы, а переменные – с большой.
Если опустить детали, синтаксис ПРОЛОГа можно описать следующим образом:
<ПРОЛОГ-предложение> ::= <правило> | <факт> | <запрос>
<правило> ::= <заголовок> ‘:-’<тело>
<факт> ::= <заголовок> ‘.’
<запрос> ::= <тело>‘.’
<тело> ::= <цель> /’,’<цель>/’.’
<заголовок>::= <предикат>
<цель>::= <предикат> |<выражение>
<предикат>::= <имя>/ ‘(‘<терм> /’,’<терм>/ ‘)’/
<терм>::= <атом> |<предикат>|<список>
<атом>::= <переменная> |<число> |<строка>|<имя>
<список>::= <список с заголовком>| <простой список>
<список с заголовком >::= ‘[‘ <терм >/’,’<терм>/’|’ < терм>’]’
< простой список>::= ‘[‘ <терм >/’,’<терм>/’]’|‘['’]’
<выражение>::= <терм> /<оператор><терм>/
<оператор>::= ‘is’ | '=' | ‘==' | ’\=' | ’>=' | ’=<’ | ‘=\=' |
Как видно из синтаксиса, в ПРОЛОГе нет зарезервированных имен за исключением предиката “is”, хотя и применяются различные встроенные предикаты для удобства и связи с внешней средой.
Пример – семейные отношения.
Определим правила для отношений – супруг, ребенок, мать, дочь, брат, потомок. Семейные отношения задаются бинарными и унарными предикатами – правилами (предикаты с переменными) и фактами (предикаты с константами). Правила легко понять, поскольку семейные отношения всем понятны. Например, первое правило гласит: X является матерью Y, если Y есть ребенок X и X женского пола.
mother(X,Y):-child(X,Y),female(X).
daughter(X,Y):-child(Y,X),female(X).
grandchild(X,Y):-child(X,Z),child(Z,Y).
descendant(X,Y):-child(X,Y).
descendant(X,Y):-grandchild(X,Z).
Факты описывают родственников конкретной семьи.
marrow(john, meri). female(meri).
child(john, jack). child(meri, jack). child(john, kate).
marrow(jack,joan). marrow(kate, dick).
child(jack,henry). child(kat,josh).
male(john). female(mery).
male(henry). female(joan).
male(josh). male(dick).
Один набор правил (программа) может применяться к различным наборам фактов (данные).
Набор возможных запросов определяется существующим набором правил. Заголовок каждого правила является основой построения запросов.
Запросы могут быть двух видов – проверочный и поисковый.
Примеры поисковых запросов:
Чья дочь Kat? – daughter(X,kat).
Чей внук Henry? — grandchild(X,henry)
Примеры проверочных запросов:
Dick – ребенок Meri? – child(mery,dick).
Главные понятия ПРОЛОГа: списки, рекурсия, унификация, бэктрекинг. Списки – основная структура данных, применяемая в этом языке. Списки являются основой для организации всех сложных вычислений. Одно из основных свойств списка – отсутствие ограничений на элементы и размер списка. Вложенность списков также ничем не ограничивается. Список в языке трактуется как структура из двух элементов – «головы» и «хвоста». Это разделение является основой вычислений над списками, поэтому наиболее часто применяемый паттерн списка имеет вид [H|T].
Первый элемент списка может иметь любую структуру, а второй – также является списком. Пустой список не содержит элементов и обозначается как [ ].
Вторая базовая структурная единица языка – предикат имеет вид — p(A1,A2,..). Предикаты удобны для группирования данных в одну смысловую единицу. В отличие от списка, количество аргументов предиката фиксировано. Имя предиката пишется с малой буквы, как и все константы в языке.
Переменные всегда начинаются с заглавной буквы. На основе переменных можно строить паттерны для списков.
Примеры списковых паттернов:
[H|T] – не пустой список;
[ ] – пустой список;
[A1,A2,A3] – список из трех произвольных элементов;
[A,A,A|T] – список, в котором первые три элемента совпадают;
[x,10|T] – список, в котором на первом месте стоит символьная константа “x”, а на втором – числовая константа 10.
Рекурсивность структуры списка является важным элементом организации рекурсивных вычислений. Рекурсивные предикаты имеют не менее двух процедур – одна для общего случая, другая – для завершения.
Рекурсивность списков обеспечивает возможность простой формулировки алгоритма операций над списками.
Пример: Вычисление длины списка.
length([H|T],N):-length(T,N1), N is N1+1.
length([],0).
Пример: Инвертирование списка.
nrev([H|T],L) :- nrev(T,L1), append(L1,[H],L).
nrev([],[]).
В ПРОЛОГе нет функций, поэтому нельзя вставить, например, длину списка length(L) в качестве аргумента, как это делается во всех процедурных языках.
В то же время, ПРОЛОГ можно рассматривать как вполне императивный язык, в котором все операции, за исключением бэтрекинга, прописываются явно.
Унификация с первого взгляда вносит некую загадочность и непонятность в язык, но она имеет вполне процедурное объяснение.
Унификация – это подстановка параметров в паттерн и применяется не только для селекции входных параметров, но и для автоматического выделения нужных элементов списка и манипулирования ими – добавления и удаления головного элемента списка.
Пример: соединение списков.
append([H|T], L, [H|L2]):-append(T, L, L2).
append([], L, L).
Правильнее было бы записать второй аргумент в виде [H1|T1], поскольку второй аргумент должен быть списком, но это усложнит предикат, поскольку второй аргумент может быть и пустым списком.
Переменные в ПРОЛОГе – логические, т.е. повторная унификация внутри одной процедуры невозможна. Нельзя написать L = [a,b,c], а потом — L=[12]. Логичность переменных приводит к усложнению унификации, поскольку все унификации в теле одной процедуры не могут быть пересмотрены в процессе вычисления, а значит, они не могут противоречить друг другу.
Унификация логических переменных приводит к неожиданным эффектам, которые имеют вполне императивное объяснение.
Пример: варианты использования предиката соединения списков.
Соединение:
append([a,b,c],[d,e,f],L).
L = [a,b,c,d,e,f] =>
yes.
Проверка связи списков:
append([a,b,c],[1,2,3],[a,b,c,1,2,3]).
yes.
Разложение списка:
append(L1,L2,[a,b,c]).
L1=[a,b,c]
L2=[] ->;
L1=[a,b]
L2=[c] ->;
L1=[a]
L2=[b,c] ->;
L1=[]
L2=[a,b,c] ->;
no.
Здесь символ “;” означает запрос другого варианта решения путем запуска бэктрекинга.
Вычитание списков:
append([a,b], L, [a,b,c,d]).
L=[c,d].
В ПРОЛОГе принято различать вычисления с бэктрекингом (недетерминированные) и без него (детерминированные).
Пример недетерминированного предиката: Решение числовой головоломки.
/*
D O N A L D
+
G E R A L D
— R O B E R T */
sum(L1,L2,L3):-
sum1(L1,L2,L3,L1,L2,L3,0,[0,1,2,3,4,5,6,7,8,9]).
sum1(L1,L2,L3,L11,L12,L13,Ii,Lv):-
dl(L11,L111,E1),
dl(L12,L121,E2),
dl(L13,L131,E3),
val(E1,Lv,Lv1),val(E2,Lv1,Lv2),val(E3,Lv2,Lv3),
sd(E1,E2,E3,Ii,Io),
sum1(L1,L2,L3,L111,L121,L131,Io,Lv3).
sum1(L1,L2,L3,[],_,_,0,_):-!..
dl([H|T],[H|T1],E):- dl(T,T1,E).
dl([H],[],H).
val(E,L,L):-nonvar(E).
val(E,L1,L2):-del(E,L1,L2).
sd(A,B,C,Ii,Io):-
C1 is A+B+Ii,
C is C1 mod 10,
Io is C1 // 10.
del(E,[E|T],T).
del(E,[H|T],[H|T1]):-del(E,T,T1).
s:-
A1=[D, O, N, A, L, D],
A2=[G, E, R, A, L, D],
A3=[R, O, B, E, R, T],
sum(A1,A2,A3),
write(A1),nl,
write(A2),nl,
write(A3),nl.
Предикат sum/3 выполняет основную операцию подбора значений цифр для заданной буквенной формулы. Вычисление проводится для формулы сложения двух чисел любой длины. При наличии известных цифр можно их вставлять вместо переменных. Если длина слагаемых различна, можно вставить нули в начале соответствующего списка.
Предикат sum1/8 использует первые три аргумента для записи результата, аргументы под номером 4,5,6 – в качестве рабочих переменных, седьмой аргумент – начальное значение разряда переноса, восьмой аргумент – список допустимых значений цифр.
Предикат dl/3 выполняет выбор и удаление последнего элемента из списка переменных.
Предикат val/3 выбирает допустимое значение из списка оставшихся вариантов, при этом выбранный вариант цифры, удаляется из списка допустимых вариантов.
Если вариант значения для очередной буквы устанавливался ранее, то он остается без изменений.
Предикат sd/5 проверяет вариант заданной тройки цифр одного столбца:
A+B+Ii = C+Io*10
Если sd/5 не выполняется, возникает бэктрекинг — последний из вызовов предиката val/3 присваивает новое значение переменной E3. Если ни одно из значений E3 не подошло, бэктрекинг продолжается на шаг назад — для E2 выбирается новое значение, затем – если не подойдет ни один вариант E3 E2, для E1.
Предикат sum1/8 выполняется рекурсивно до исчерпания входного списка переменных.
Предикат s/0 – пример вызова предиката sum/3 для решения одного варианта головоломки.
Как видно из примера, программа на ПРОЛОГе может быть очень компактной, при этом алгоритм прост и прозрачен, поскольку никакие неявные вызовы функций не используются.
Можно развивать программу решения таких головоломок, например, сделать ее универсальной – для всех типов числовых ребусов, улучшить ввод исходных данных.
Для этого надо делать такие операции как лексический и синтаксический анализ. Эти операции рассмотрим во второй части.
После многолетней работы с ПРОЛОГом, столкнулся с новомодным Haskell, о котором все авторы гордо говорят – «высокий порог вхождения». По-моему, «высота» этого порога образовалась в результате запутанного синтаксиса и нагромождения встроенных процедур. Еще один источник этой «высоты» — высокомерие авторов многочисленных руководств, которые написаны так, будто читатель никогда программ не писал.
Сразу захотелось назад, к «родному» ПРОЛОГу – простому и понятному. Думаю, если объяснить без нагромождений, типа декларативной семантики, время вхождения в логическое программирование для «обычного» программиста не превысит 30 минут.
Попробую описать его с точки зрения процедурного программирования.
ПРОЛОГ имеет два основных отличия от процедурных языков — способ организации вычислений и способ представления данных. Оба этих аспекта языка коренным образом отличаются от традиционных языков программирования. Но не будем забывать, что логическое программирование реализуется на тех же машинах с фон — Неймановской архитектурой.
Представим себе язык программирования, в котором все операции сводятся к вызову процедур. При этом каждая процедура существует в нескольких вариантах и программа сама выбирает себе правильный, точнее говоря, пригодный для каждого конкретного варианта исходных данных вариант реализации (тело) процедуры. Как определяется пригодность – каждый вызов процедуры, во время исполнения программы, по результатам исполнения процедуры, получает логическое значение – TRUE или FALSE. Совокупность процедур с одинаковым именем и арностью называется предикатом.
Каждый предикат в языке ПРОЛОГ идентифицируется двумя параметрами –именем и арностью – количеством параметров. Например, предикат инвертирования списков идентифицируется, как nrev/2, а предикат соединения списков как append/3. Никакого объявления параметров или переменных не требуется, но можно ограничить параметры паттерном в заголовке процедуры. Например, в одном варианте предиката первый параметр может быть указан как [] – пустой список, в другом – как [A,B,C] – список из трех элементов, а в третьем как [H|T] – произвольный непустой список.
Если какое-то условие в теле процедуры не выполняется, выполнение прекращается и вызов процедуры, точнее говоря, выполнение очередного варианта тела процедуры, прекращается и получает значение FALSE. В этом случае, интерпретатор языка запускает следующий по порядку вариант тела этой процедуры. Если же все варианты оказались непригодными, происходит возврат к предыдущей процедуре и для нее также происходит перебор вариантов, таким образом, вычисление в ПРОЛОГе сводится к обходу дерева вложенности процедур.
Возврат к предыдущему вызову называется бэктрекингом (backtracking). По существу это откат, поскольку все значения, полученные переменными в отмененной процедуре, отменяются. Бэктрекинг – уникальное средство данного языка, не имеющее аналогов ни в одном из других массовых языков программирования. Бэктрекинг обеспечивает полный обход дерева логического вывода, что обеспечивает основу для решения интеллектуальных задач.
Алгоритм интерпретации программы (выполнения цели) в системе ПРОЛОГ.
Вход: цель p(A1,A2,…,An)
1. Найти в памяти процедуру по имени p с арностью n.
2. Унифицировать входные параметры цели с заголовком найденной процедуры.
3. Если унификация параметров прошла, выполнить первую цель из тела найденной процедуры.
4. Если унификация не прошла, найти следующий вариант процедуры P/n.
5. Если следующий вариант процедуры P/n не найден, закончить работу с результатом FAIL.
6. Если первая цель выполнилась, перейти к выполнению следующей цели.
7. Если следующая цель не выполнилась, вернуться к предыдущей цели и выполнить следующий вариант ее реализации.
8. Если текущий вариант реализации процедуры P/n не выполнился, перейти к следующему варианту.
9. Если все цели из тела процедуры выполнены, закончить работу с результатом TRUE.
В связи с такой структурой вычислений каждый вызов процедуры называется целью, которая может быть достигнута или нет. Всякое вычисление в ПРОЛОГе имеет логическое значение. Вычисление еще называют поиском вывода (доказательства), а язык ПРОЛОГ – языком логического программирования.
Наверное, синтаксически ПРОЛОГ – самый простой среди языков программирования. Основной синтаксической процедурой является предикат – выражение, аналогичное вызову процедуры — имя и список аргументов –
P(x1, …xn). Имена пишем с малой буквы, а переменные – с большой.
Если опустить детали, синтаксис ПРОЛОГа можно описать следующим образом:
<ПРОЛОГ-предложение> ::= <правило> | <факт> | <запрос>
<правило> ::= <заголовок> ‘:-’<тело>
<факт> ::= <заголовок> ‘.’
<запрос> ::= <тело>‘.’
<тело> ::= <цель> /’,’<цель>/’.’
<заголовок>::= <предикат>
<цель>::= <предикат> |<выражение>
<предикат>::= <имя>/ ‘(‘<терм> /’,’<терм>/ ‘)’/
<терм>::= <атом> |<предикат>|<список>
<атом>::= <переменная> |<число> |<строка>|<имя>
<список>::= <список с заголовком>| <простой список>
<список с заголовком >::= ‘[‘ <терм >/’,’<терм>/’|’ < терм>’]’
< простой список>::= ‘[‘ <терм >/’,’<терм>/’]’|‘['’]’
<выражение>::= <терм> /<оператор><терм>/
<оператор>::= ‘is’ | '=' | ‘==' | ’\=' | ’>=' | ’=<’ | ‘=\=' |
Как видно из синтаксиса, в ПРОЛОГе нет зарезервированных имен за исключением предиката “is”, хотя и применяются различные встроенные предикаты для удобства и связи с внешней средой.
Пример – семейные отношения.
Определим правила для отношений – супруг, ребенок, мать, дочь, брат, потомок. Семейные отношения задаются бинарными и унарными предикатами – правилами (предикаты с переменными) и фактами (предикаты с константами). Правила легко понять, поскольку семейные отношения всем понятны. Например, первое правило гласит: X является матерью Y, если Y есть ребенок X и X женского пола.
mother(X,Y):-child(X,Y),female(X).
daughter(X,Y):-child(Y,X),female(X).
grandchild(X,Y):-child(X,Z),child(Z,Y).
descendant(X,Y):-child(X,Y).
descendant(X,Y):-grandchild(X,Z).
Факты описывают родственников конкретной семьи.
marrow(john, meri). female(meri).
child(john, jack). child(meri, jack). child(john, kate).
marrow(jack,joan). marrow(kate, dick).
child(jack,henry). child(kat,josh).
male(john). female(mery).
male(henry). female(joan).
male(josh). male(dick).
Один набор правил (программа) может применяться к различным наборам фактов (данные).
Набор возможных запросов определяется существующим набором правил. Заголовок каждого правила является основой построения запросов.
Запросы могут быть двух видов – проверочный и поисковый.
Примеры поисковых запросов:
Чья дочь Kat? – daughter(X,kat).
Чей внук Henry? — grandchild(X,henry)
Примеры проверочных запросов:
Dick – ребенок Meri? – child(mery,dick).
Главные понятия ПРОЛОГа: списки, рекурсия, унификация, бэктрекинг. Списки – основная структура данных, применяемая в этом языке. Списки являются основой для организации всех сложных вычислений. Одно из основных свойств списка – отсутствие ограничений на элементы и размер списка. Вложенность списков также ничем не ограничивается. Список в языке трактуется как структура из двух элементов – «головы» и «хвоста». Это разделение является основой вычислений над списками, поэтому наиболее часто применяемый паттерн списка имеет вид [H|T].
Первый элемент списка может иметь любую структуру, а второй – также является списком. Пустой список не содержит элементов и обозначается как [ ].
Вторая базовая структурная единица языка – предикат имеет вид — p(A1,A2,..). Предикаты удобны для группирования данных в одну смысловую единицу. В отличие от списка, количество аргументов предиката фиксировано. Имя предиката пишется с малой буквы, как и все константы в языке.
Переменные всегда начинаются с заглавной буквы. На основе переменных можно строить паттерны для списков.
Примеры списковых паттернов:
[H|T] – не пустой список;
[ ] – пустой список;
[A1,A2,A3] – список из трех произвольных элементов;
[A,A,A|T] – список, в котором первые три элемента совпадают;
[x,10|T] – список, в котором на первом месте стоит символьная константа “x”, а на втором – числовая константа 10.
Рекурсивность структуры списка является важным элементом организации рекурсивных вычислений. Рекурсивные предикаты имеют не менее двух процедур – одна для общего случая, другая – для завершения.
Рекурсивность списков обеспечивает возможность простой формулировки алгоритма операций над списками.
Пример: Вычисление длины списка.
length([H|T],N):-length(T,N1), N is N1+1.
length([],0).
Пример: Инвертирование списка.
nrev([H|T],L) :- nrev(T,L1), append(L1,[H],L).
nrev([],[]).
В ПРОЛОГе нет функций, поэтому нельзя вставить, например, длину списка length(L) в качестве аргумента, как это делается во всех процедурных языках.
В то же время, ПРОЛОГ можно рассматривать как вполне императивный язык, в котором все операции, за исключением бэтрекинга, прописываются явно.
Унификация с первого взгляда вносит некую загадочность и непонятность в язык, но она имеет вполне процедурное объяснение.
Унификация – это подстановка параметров в паттерн и применяется не только для селекции входных параметров, но и для автоматического выделения нужных элементов списка и манипулирования ими – добавления и удаления головного элемента списка.
Пример: соединение списков.
append([H|T], L, [H|L2]):-append(T, L, L2).
append([], L, L).
Правильнее было бы записать второй аргумент в виде [H1|T1], поскольку второй аргумент должен быть списком, но это усложнит предикат, поскольку второй аргумент может быть и пустым списком.
Переменные в ПРОЛОГе – логические, т.е. повторная унификация внутри одной процедуры невозможна. Нельзя написать L = [a,b,c], а потом — L=[12]. Логичность переменных приводит к усложнению унификации, поскольку все унификации в теле одной процедуры не могут быть пересмотрены в процессе вычисления, а значит, они не могут противоречить друг другу.
Унификация логических переменных приводит к неожиданным эффектам, которые имеют вполне императивное объяснение.
Пример: варианты использования предиката соединения списков.
Соединение:
append([a,b,c],[d,e,f],L).
L = [a,b,c,d,e,f] =>
yes.
Проверка связи списков:
append([a,b,c],[1,2,3],[a,b,c,1,2,3]).
yes.
Разложение списка:
append(L1,L2,[a,b,c]).
L1=[a,b,c]
L2=[] ->;
L1=[a,b]
L2=[c] ->;
L1=[a]
L2=[b,c] ->;
L1=[]
L2=[a,b,c] ->;
no.
Здесь символ “;” означает запрос другого варианта решения путем запуска бэктрекинга.
Вычитание списков:
append([a,b], L, [a,b,c,d]).
L=[c,d].
В ПРОЛОГе принято различать вычисления с бэктрекингом (недетерминированные) и без него (детерминированные).
Пример недетерминированного предиката: Решение числовой головоломки.
/*
D O N A L D
+
G E R A L D
— R O B E R T */
sum(L1,L2,L3):-
sum1(L1,L2,L3,L1,L2,L3,0,[0,1,2,3,4,5,6,7,8,9]).
sum1(L1,L2,L3,L11,L12,L13,Ii,Lv):-
dl(L11,L111,E1),
dl(L12,L121,E2),
dl(L13,L131,E3),
val(E1,Lv,Lv1),val(E2,Lv1,Lv2),val(E3,Lv2,Lv3),
sd(E1,E2,E3,Ii,Io),
sum1(L1,L2,L3,L111,L121,L131,Io,Lv3).
sum1(L1,L2,L3,[],_,_,0,_):-!..
dl([H|T],[H|T1],E):- dl(T,T1,E).
dl([H],[],H).
val(E,L,L):-nonvar(E).
val(E,L1,L2):-del(E,L1,L2).
sd(A,B,C,Ii,Io):-
C1 is A+B+Ii,
C is C1 mod 10,
Io is C1 // 10.
del(E,[E|T],T).
del(E,[H|T],[H|T1]):-del(E,T,T1).
s:-
A1=[D, O, N, A, L, D],
A2=[G, E, R, A, L, D],
A3=[R, O, B, E, R, T],
sum(A1,A2,A3),
write(A1),nl,
write(A2),nl,
write(A3),nl.
Предикат sum/3 выполняет основную операцию подбора значений цифр для заданной буквенной формулы. Вычисление проводится для формулы сложения двух чисел любой длины. При наличии известных цифр можно их вставлять вместо переменных. Если длина слагаемых различна, можно вставить нули в начале соответствующего списка.
Предикат sum1/8 использует первые три аргумента для записи результата, аргументы под номером 4,5,6 – в качестве рабочих переменных, седьмой аргумент – начальное значение разряда переноса, восьмой аргумент – список допустимых значений цифр.
Предикат dl/3 выполняет выбор и удаление последнего элемента из списка переменных.
Предикат val/3 выбирает допустимое значение из списка оставшихся вариантов, при этом выбранный вариант цифры, удаляется из списка допустимых вариантов.
Если вариант значения для очередной буквы устанавливался ранее, то он остается без изменений.
Предикат sd/5 проверяет вариант заданной тройки цифр одного столбца:
A+B+Ii = C+Io*10
Если sd/5 не выполняется, возникает бэктрекинг — последний из вызовов предиката val/3 присваивает новое значение переменной E3. Если ни одно из значений E3 не подошло, бэктрекинг продолжается на шаг назад — для E2 выбирается новое значение, затем – если не подойдет ни один вариант E3 E2, для E1.
Предикат sum1/8 выполняется рекурсивно до исчерпания входного списка переменных.
Предикат s/0 – пример вызова предиката sum/3 для решения одного варианта головоломки.
Как видно из примера, программа на ПРОЛОГе может быть очень компактной, при этом алгоритм прост и прозрачен, поскольку никакие неявные вызовы функций не используются.
Можно развивать программу решения таких головоломок, например, сделать ее универсальной – для всех типов числовых ребусов, улучшить ввод исходных данных.
Для этого надо делать такие операции как лексический и синтаксический анализ. Эти операции рассмотрим во второй части.