Пример дедуктивного ретривера

Question

В Лиспе, предположим, у меня есть два правила в базе знаний:

(append nil ?x ?x)
(<- (append (cons ?x ?l1) ?l2 (cons ?x ?l3))
    (append ?l1 ?l2 ?l3))

Тогда как я могу сделать вывод, что если мы спросим

(ask '(append (cons a (cons b nil))
              (cons c nil)
              ?l)
     '?l))

мы получим результат '((cons a (cons b (cons c nil)))?

Это один пример из моего класса на Лиспе, надеюсь, вы могли бы помочь мне понять этот ретривер. Спасибо.

Answer 1

Чтобы понять проблему, я думаю, вам нужно сначала приобрести два ключевых понятия: обратная цепочка и объединение .

С грубым упрощением вот как работает обратное построение цепочек: попробуйте, если возможно, объединить цель (первый аргумент для «спросить» в вашем примере) с главой любого из правил (обратите внимание на недетерминизм); если да, добавьте тело (которое может быть пустым) этого правила в качестве подцелей и сохраните результат объединения (набор привязок переменных). Рекурсивно применяйте описанную выше процедуру к каждой подцели с накопленными привязками, пока либо (1) не будет применено правило, которое означает, что доказательство не выполнено, либо (2) больше нет подцели, что означает, что доказательство выполнено успешно. В последнем случае ответом будет привязка целевой переменной (второй аргумент).