4.4.3 · Сопоставление с образцом

Сопоставление с образцом и кадр связываний

Переменная образца расширяет явный кадр при первой встрече, а затем требует то же самое значение при каждом повторном появлении этой переменной.

Вопрос для размышления

Как сопоставитель может переносить частичное знание при обходе двух структур данных?

Представление переменных образца в виде явных данных списка
Хранение связываний переменных в кадре на основе ассоциативного списка
Рекурсивное сопоставление структуры пар слева направо
Отклонение повторяющейся переменной при конфликте ее значений

Форма (? who) представляет переменную образца, а не литеральный список. При первом появлении extend-if-consistent добавляет who и совпадающие данные в кадр. Обычные символы и структура пар должны сопоставляться напрямую.

При последующем появлении выполняется поиск существующего связывания перед любым расширением. Одинаковые данные сохраняют кадр, а конфликтующие данные возвращают failed, что распространяется на все оставшиеся рекурсивные шаги. Это одностороннее сопоставление с переменными в образце, а не полная двунаправленная унификация или поиск по базе данных.

Код SICP970 из 1,048,576 байт UTF-8

(begin
  (define (variable? pattern)
    (and (pair? pattern) (eq? (car pattern) '?)))
  (define (extend-if-consistent variable value frame)
    (let ((found (assoc (cadr variable) frame)))
      (cond (found
             (if (equal? value (cdr found)) frame 'failed))
            (else
             (cons (cons (cadr variable) value) frame)))))
  (define (pattern-match pattern datum frame)
    (cond ((eq? frame 'failed) 'failed)
          ((variable? pattern)
           (extend-if-consistent pattern datum frame))
          ((and (pair? pattern) (pair? datum))
           (pattern-match
             (cdr pattern)
             (cdr datum)
             (pattern-match (car pattern) (car datum) frame)))
          ((equal? pattern datum) frame)
          (else 'failed)))
  (define frame
    (pattern-match '(parent (? who) (? child))
                   '(parent bob alice)
                   '()))
  (list (cdr (assoc 'who frame))
        (cdr (assoc 'child frame))))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает (bob alice). Вторая программа возвращает (apple failed).

На что обратить внимание в трассе

Проследите за рекурсивным сопоставлением car перед сопоставлением cdr, затем найдите каждое расширение кадра. Во втором запуске проследите, как поиск второго элемента один раз сохраняет кадр со значением apple и возвращает failed для pear. Трассы выполнения фиксируют одностороннее сопоставление с образцом и каждое расширение кадра.

Попробуйте сами

Измените программу и сравните результат.

Измените первый образец на (parent (? person) (? person)). Перед запуском предскажите результат для (parent bob alice).

Показать подсказку

Второе появление должно быть равно значению, сохраненному при первом появлении.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%