Как работает добавление в форму? (раздел SICP по логическому программированию)

В настоящее время я работаю над разделом SICP по логическому программированию, но я застрял в примерах, касающихся логических выводов, особенно правил добавления в форму. Как они работают? Чего я не совсем понимаю, так это того, как второе правило cdr уменьшает первый список. Например, учитывая:

(правило (дополнение к форме () ?y ?y))

(правило (присоединение к форме (?u . ?v) ?y (?u . ?z)) (присоединение к форме ?v ?y ?z))

а) Как мы достигаем от:

;;; Query input:
(append-to-form (a b) (c d) ?z)

to

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

б) А что насчет этого:

;;; Query input:
(append-to-form (a b) ?y (a b c d))

to

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

в) И последнее:

;;; Query input:
(append-to-form ?x ?y (a b c d))

to

;;; Query results:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))

Я был бы заинтересован в конкретных умственных шагах, необходимых для выполнения сопоставления правил.

Заранее спасибо.


sicp logic-programming
person motxilo    schedule 10.12.2010    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Играйте в переводчика, беря лист бумаги и записывая каждый шаг. Для каждого шага вы записываете, какое правило было/может быть запущено и какая переменная была привязана к какому значению.

Например:

(append-to-form (a b) (c d) ?z)

запускает правило

(rule (append-to-form (?u . ?v) ?y (?u . ?z)) 
  (append-to-form ?v ?y ?z))

с

?u = a, ?v = (b), ?y = (c d), ?z = (a . ?z_2)

Примечание. Предполагается, что ?z в исходном запросе является переменной, отличной от ?z в теле правила, поэтому переименуйте ?z правила в ?z_2. Список (1 2 3) при сопоставлении с (?a . ?b) дает ?a = 1, ?b = (2 3), как при переносе/перезаписи списка.

Эти привязки применяются к телу правила (append-to-form ?v ?y ?z) Итак, мы получаем

(append-to-form (b) (c d) ?z_2)

который снова становится

(append-to-form () (c d) ?z_3)

и запускает другое правило: (rule (append-to-form () ?y ?y)) связывает ?z_3 с (c d). Затем начинается рекурсия, ?z_2 определяется как (b . ?z_3), ?z определяется как (a . ?z2)

Исходный запрос (append-to-form (a b) (c d) ?z) применяется к привязкам, в которых ?z = (a . (b . (c d))) и возвращает (append-to-form (a b) (c d) (a b c d))

Остальные упражнения оставляем читателю ;)

Важнейшими понятиями здесь являются сопоставление с образцом и унификация, которые можно найти по адресу раздел 4.2.2. Весь оценщик запросов — действительно самая сложная часть SICP, так что не расстраивайтесь. Это стоит затраченных усилий. Попробуйте запустить код (в схеме R5RS) и поэкспериментировать с ним, например, добавить трассировку.

person Beef    schedule 11.12.2010
comment
Спасибо за ответ, Биф. На самом деле, я боролся с этим, потому что функционирование оценщика объясняется позже в этой главе. Я должен был заранее прочитать раздел, следующий за этими примерами. - person motxilo; 05.01.2011