4.4.2 · How the query system works

A query transforms a stream of frames into another stream of frames.

Match explicit variable patterns against assertions, extend consistent frames, instantiate answers, and pass frame lists through a finite conjunction pipeline.

Guiding question

How does one query preserve possible variable bindings while a later query narrows those possibilities?

Represent a query variable explicitly as (var name)
Match a pattern against one assertion while extending a frame
Reject a binding that conflicts with an existing frame entry
Instantiate a result pattern from a successful frame
Treat simple-query as a transformation over input frames
Feed every output frame from one conjunct into the next conjunct

pattern-match walks a query pattern and an assertion together. A variable adds a binding when absent and requires equal data when already present. simple-query applies that matcher to every assertion for every input frame, producing a finite list of extended frames. instantiate walks a result pattern and replaces every bound variable with its datum.

qeval recognizes and as a pipeline. The first query creates possible who bindings for all programmers. The second query receives each frame separately and keeps only the frame whose same who also supervises under bob. This lesson materializes the finite frame stream as a list while preserving the pipeline protocol.

SICP code2,300 of 1,048,576 UTF-8 bytes

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

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The simple query returns ((job alice programmer) (job cy programmer)). The conjunction returns (alice).

Trace focus

For each assertion, follow recursive pattern-match and note when who is first added to the frame. In the conjunction, keep the two programmer frames separate, then show how the supervisor query retains alice and rejects cy because the existing who binding must remain consistent.

Try it yourself

Change the program and compare the result.

Add salary assertions and query for programmers with one exact salary. Then implement a finite or form that appends the frame results of two alternative queries.

Show hint

Each disjunct receives the same input frames. Conjunction instead passes output frames from one query into the next.

Complete this lesson

0 of 23 lessons complete in this chapter0%