4.4.2 · Как работает система запросов

Конвейер запросов над потоком кадров

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

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

Как один запрос сохраняет возможные связывания переменных, пока последующий запрос сужает эти возможности?

Явное представление переменной запроса в виде (var name)
Сопоставление шаблона с одним утверждением с расширением кадра
Отклонение связывания, конфликтующего с существующей записью кадра
Инстанцирование результирующего шаблона из успешного кадра
Обработка simple-query как преобразования над входными кадрами
Передача каждого выходного кадра из одного конъюнкта в следующий конъюнкт

pattern-match параллельно обходит шаблон запроса и утверждение. Переменная добавляет связывание при его отсутствии и требует совпадения данных, если оно уже существует. simple-query применяет этот сопоставитель к каждому утверждению для каждого входного кадра, порождая конечный список расширенных кадров. instantiate обходит результирующий шаблон и заменяет каждую связанную переменную ее значением.

qeval распознает and как конвейер. Первый запрос создает возможные связывания who для всех программистов. Второй запрос получает каждый кадр отдельно и сохраняет только тот кадр, где тот же who также руководит под началом bob. Этот урок материализует конечный поток кадров в виде списка, сохраняя протокол конвейера.

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

(begin
  (define failed 'failed)
  (define (variable? expression)
    (and (pair? expression) (eq? (car expression) 'var)))
  (define (variable-name variable) (cadr variable))
  (define (binding variable frame)
    (assoc (variable-name variable) frame))
  (define (extend-if-consistent variable value frame)
    (let ((record (binding variable frame)))
      (cond (record
             (if (equal? (cdr record) value) frame failed))
            (else
             (cons (cons (variable-name variable) value) frame)))))
  (define (pattern-match pattern datum frame)
    (cond ((eq? frame failed) failed)
          ((equal? pattern datum) frame)
          ((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)))
          (else failed)))
  (define (simple-query pattern assertions input-frames)
    (define (matches-for-frame frame records)
      (if (null? records)
          '()
          (let ((result
                 (pattern-match pattern (car records) frame)))
            (if (eq? result failed)
                (matches-for-frame frame (cdr records))
                (cons result
                      (matches-for-frame frame (cdr records)))))))
    (if (null? input-frames)
        '()
        (append
          (matches-for-frame (car input-frames) assertions)
          (simple-query pattern assertions (cdr input-frames)))))
  (define (instantiate expression frame)
    (cond ((variable? expression)
           (let ((record (binding expression frame)))
             (if record (cdr record) expression)))
          ((pair? expression)
           (cons (instantiate (car expression) frame)
                 (instantiate (cdr expression) frame)))
          (else expression)))
  (define assertions
    '((job alice programmer)
      (job bob manager)
      (job cy programmer)
      (supervisor alice bob)
      (supervisor cy dana)))
  (define frames
    (simple-query
      '(job (var who) programmer)
      assertions
      (list '())))
  (map (lambda (frame)
         (instantiate '(job (var who) programmer) frame))
       frames))

(begin
  (define failed 'failed)
  (define (variable? expression)
    (and (pair? expression) (eq? (car expression) 'var)))
  (define (variable-name variable) (cadr variable))
  (define (binding variable frame)
    (assoc (variable-name variable) frame))
  (define (extend-if-consistent variable value frame)
    (let ((record (binding variable frame)))
      (cond (record
             (if (equal? (cdr record) value) frame failed))
            (else
             (cons (cons (variable-name variable) value) frame)))))
  (define (pattern-match pattern datum frame)
    (cond ((eq? frame failed) failed)
          ((equal? pattern datum) frame)
          ((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)))
          (else failed)))
  (define (simple-query pattern assertions input-frames)
    (define (matches-for-frame frame records)
      (if (null? records)
          '()
          (let ((result
                 (pattern-match pattern (car records) frame)))
            (if (eq? result failed)
                (matches-for-frame frame (cdr records))
                (cons result
                      (matches-for-frame frame (cdr records)))))))
    (if (null? input-frames)
        '()
        (append
          (matches-for-frame (car input-frames) assertions)
          (simple-query pattern assertions (cdr input-frames)))))
  (define (instantiate expression frame)
    (cond ((variable? expression)
           (let ((record (binding expression frame)))
             (if record (cdr record) expression)))
          ((pair? expression)
           (cons (instantiate (car expression) frame)
                 (instantiate (cdr expression) frame)))
          (else expression)))
  (define assertions
    '((job alice programmer)
      (job bob manager)
      (job cy programmer)
      (supervisor alice bob)
      (supervisor cy dana)))
  (define frames
    (simple-query
      '(job (var who) programmer)
      assertions
      (list '())))
  (map (lambda (frame)
         (instantiate '(job (var who) programmer) frame))
       frames))

Примеры

Результат—

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

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

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

Простой запрос возвращает ((job alice programmer) (job cy programmer)). Конъюнкция возвращает (alice).

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

Для каждого утверждения проследите рекурсивный pattern-match и отметьте момент, когда who впервые добавляется в кадр. В конъюнкции сохраняйте два кадра программистов раздельно, а затем покажите, как запрос supervisor оставляет alice и отклоняет cy, поскольку существующее связывание who должно оставаться непротиворечивым.

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

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

Добавьте утверждения salary и запросите программистов с одной точной зарплатой. Затем реализуйте конечную форму or, объединяющую результаты кадров двух альтернативных запросов.

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

Каждый дизъюнкт получает те же входные кадры. Конъюнкция вместо этого передает выходные кадры одного запроса в следующий.

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

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