Рассуждение через программу в Prolog

Question

Я пытаюсь ответить на прошлый вопрос для экзамена Prolog. Я нарисовал «дерево», как я полагал, что Пролог должен вести себя с учетом программы и определенной цели. Однако Prolog не ведет себя так, как я ожидал, и дал запрос, для которого я полагал, что он вернет «true», он фактически вернул «false».

Вот моя программа:

sum(Term,N) :- Term = 0, N = 0. 
sum(Term,N) :- Term = f(M,Subterm), number(M), sum(Subterm,N-M). 

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

[сумма (е (1,0), 1) ]

Используя правило 1, пусть Term = 0, N = 0, пытается объединить [1 = 0, 1 = 0] сбой.

Redo: используя правило 2, пусть Term = f (1,0), N = 1 [f (1,0) = f (M, подтермер), число (M), сумма (подтема, 1- 1)]

объединительный, пусть М = 1 и подтерм = 0 [номер (1), сумма (0,0)]

Используя Правило 1, то это должно иметь успех. Однако (SWI) Prolog говорит «false».

Если кто-то может указать мне, почему мои рассуждения ошибочны (и как я могу учиться на этом в будущем), я был бы очень благодарен.

Answer 1

Чтобы быть более точным, первое правило пытается объединить f(1,0) = 0 и 1 = 0, что, конечно же, не удастся.

Анализ правила 2 также неверен. Отчасти это связано с тем, что Prolog не оценивает арифметические выражения inline. Термин N-M просто термин (стенография для '-'(N, M). Это не приводит к M быть вычтен из M, если оценка не делается явно через is/2 или арифметическое сравнение (например, =:=/2, =</2, и т.д.).

анализ правило 2 будет идти следующим образом. Шаг 5, где логика ломается из-за выше.

1. Вызов sum(f(1,0), 1) приводит Term = f(1,0) и N = 1.
2. в правиле 2 Term = f(M, Subterm) становится f(1,0) = f(M, Subterm), результатом которого является M = 1 и Subterm = 0.
3. number(N) становится number(1) и успешно (с 1 представляет собой число)
4. Вызов sum(Subterm, N-M) становится sum(0, 1-1).
5. Пролог соответствует sum(0, 1-1) с головой правила 1 sum(Term, N) :- Term = 0, N = 0., но он терпит неудачу, потому что 1-1 = 0 (который является таким же, как '-'(1, 1) = 0 объединения терпит неудачу.
6. Пролог соответствует sum(0, 1-1) с головкой правила 2, и объединяет Term = 0 и N = 1-1 (или N = '-'(1, 1)).
7. Term = f(M, Subterm) становится 0 = f(M, Subterm), который терпит неудачу, потому что 0 не может совпадать с термином f(M, Subterm).
8. Нет больше правил для попытки, поэтому предикатный вызов завершается с ошибкой.

Простое исправление здесь является общим, основным узором Пролог использовать новую переменную для вычисления выражения в явном виде:

sum(Term,N) :- 
    Term = f(M,Subterm), 
    number(M), 
    R is N - M, 
    sum(Subterm, R). 

Вы можете также привести в порядок код совсем немного, объединяя в головах положений. Таким образом, положения можно переписать:

sum(0, 0). 
sum(f(M, Subterm), N) :- 
    number(N), 
    R is N - M, 
    sum(Subterm, R). 

---

EDIT: Мой ответ предназначен для вас через прогулку по вашей существующей логики. Помимо исправления недоразумений в отношении оценки выражения, я не проанализировал ваше решение для общей правильности.

Answer 2

Поскольку ваша программа почти чистая 1, вы можете систематически найти ошибку, не используя отладчик. Идея состоит в том, чтобы обобщать вашу программу, удаляя цели, один за другим. Я придумал следующее чистое обобщение, которое я получил от «комментирования» некоторых цели, как так:

 
:- op(950, fy, *). 
*(_). 

sum(Term,N) :- 
    Term = 0, 
    N = 0. 
sum(Term,N) :- 
    * Term = f(M,Subterm), 
    * number(M), 
    sum(Subterm,N-M). 

?- sum(Term, N). 
    Term = 0, N = 0 
; false. 

Также выше запрос является более общим, чем ваш. Это очень полезный метод в Prolog: вместо того, чтобы думать о конкретных решениях, мы сначала делаем Prolog всю работу для нас.

Ответ был совершенно ясен: для этого отношения существует ровно одно решение, даже если отношение теперь обобщено.

Таким образом, проблема должна быть где-то в оставшейся видимой части. На самом деле это -. Почему бы не написать вместо этого:

:- use_module(library(clpfd)). 

sum(0, 0). 
sum(Term, N0) :- 
    Term = f(M, Subterm), 
    N0 #= M+N1, 
    sum(Subterm, N1). 

Я нахожу эту программу намного понятнее. Если я прочитаю имя sum, я сразу же ищу соответствующий +. Конечно, если вы настаиваете, вы можете написать N0-M #= N1. Это было бы точно так же, за исключением того, что это требует немного большего мышления.

---

_{Fine печати вам не нужно читать}

1) Ваша оригинальная программа используется number/1, который не является чистым. Но поскольку проблема продолжалась, удалив ее, это не повредило нашим рассуждениям.