Как работает добавление к форме?(Раздел SICP по программированию логики) - PullRequest
Новая
       19

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

3 голосов
/ 10 декабря 2010

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

(правило (append-to-form ()? 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))

c) И наконец: 

;;; 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))

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

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

1 Ответ

3 голосов
/ 11 декабря 2010

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

Например: 

(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) и поиграть с ним, например, добавив трассировку.

...