4.4.2 · 질의 시스템의 동작

질의는 프레임 스트림을 다른 프레임 스트림으로 바꾼다.

명시적인 변수 패턴을 assertion과 맞추고 일관된 프레임을 확장하며 답을 instantiate하고 유한 프레임 목록을 conjunction 파이프라인으로 넘깁니다.

생각해 볼 질문

질의 하나가 가능한 변수 바인딩을 보존하면서 뒤 질의가 일치하는 프레임을 어떻게 가려낼까요?

질의 변수를 (var name)으로 명시적으로 표현하기
한 assertion과 패턴을 맞추며 프레임 확장하기
기존 프레임 항목과 충돌하는 바인딩 거부하기
성공한 프레임에서 결과 패턴 instantiate하기
simple-query를 입력 프레임 변환으로 다루기
한 conjunct의 모든 출력 프레임을 다음 conjunct에 넘기기

pattern-match는 질의 패턴과 assertion을 함께 순회합니다. 변수가 없던 바인딩을 더하고 이미 있으면 같은 데이터인지 요구합니다. simple-query는 모든 입력 프레임에 대해 모든 assertion에 matcher를 적용하여 확장된 프레임의 유한 목록을 만듭니다. instantiate는 결과 패턴을 걸으며 바인딩된 변수를 데이터로 바꿉니다.

qeval은 and를 파이프라인으로 알아봅니다. 첫 질의가 programmer마다 가능한 who 프레임을 만들고 둘째 질의는 각 프레임을 따로 받아 같은 who가 bob 아래 supervisor인 경우만 남깁니다. 이 수업은 유한 프레임 스트림을 리스트로 구체화하면서 파이프라인 프로토콜을 보존합니다.

SICP 코드UTF-8 2,300 / 1,048,576바이트

(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))를 반환합니다. conjunction은 (alice)를 반환합니다.

실행 추적에서 볼 점

각 assertion에서 재귀 pattern-match를 따라가고 who가 프레임에 처음 추가되는 지점을 찾으세요. conjunction에서는 programmer 프레임 두 개를 따로 유지한 뒤 supervisor 질의가 기존 who 바인딩의 일관성을 요구하여 alice는 남기고 cy는 거부하는 과정을 보세요.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

salary assertion을 추가하고 정확한 급여 하나를 가진 programmer를 질의하세요. 그 다음 두 대안 질의의 프레임 결과를 append하는 유한 or 형식을 구현하세요.

힌트 보기

각 disjunct는 같은 입력 프레임을 받습니다. conjunction은 앞 질의의 출력 프레임을 다음 질의에 넘깁니다.

이 수업 완료하기

이 장의 총 23개 수업 중 0개 완료0%