4.4.4-ch4-query.scm

;;;;QUERY SYSTEM FROM SECTION 4.4.4 OF
;;;; STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS

;;;;Matches code in ch4.scm
;;;;Includes:
;;;;  -- supporting code from 4.1, chapter 3, and instructor's manual
;;;;  -- data base from Section 4.4.1 -- see microshaft-data-base below

;;;;This file can be loaded into Scheme as a whole.
;;;;In order to run the query system, the Scheme must support streams.

;;;;NB. PUT's are commented out and no top-level table is set up.
;;;;Instead use initialize-data-base (from manual), supplied in this file.


;;;SECTION 4.4.4.1                                                      ; finally caved and used quadruple section numbers
;;;The Driver Loop and Instantiation

(define input-prompt ";;; Query input:")
(define output-prompt ";;; Query results:")

(define (query-driver-loop)
  (prompt-for-input input-prompt)
  (let ((q (query-syntax-process (read))))                              ; 4.4.4.7: pre-process query syntax for efficient processing; 4.4.4.3 p. 475: (read) NATIVELY supports dotted-tail notation.
    (cond ((assertion-to-be-added? q)                                   ; 4.4.4.7: (assertion-to-be-added?) and (add-assertion-body)
           (add-rule-or-assertion! (add-assertion-body q))              ; 4.4.4.5: (add-rule-or-assertion!)
           (newline)
           (display "Assertion added to data base.")
           (query-driver-loop))
          (else
           (newline)
           (display output-prompt)
           ;; [extra newline at end] (announce-output output-prompt)
           (display-stream
            (stream-map
             (lambda (frame)
               (instantiate q                                           ; concrete instantiations for display
                            frame
                            (lambda (v f)
                              (contract-question-mark v))))             ; unbound-var-handler from 4.4.4.7 - transform back to input representation - i.e., "undo" (query-syntax-process)
             (qeval q (singleton-stream '()))))                         ; with initial frame stream of a single empty frame
           (query-driver-loop)))))                                          ; result: a stream of frames generated by satisfying the query with variable values found in the data base

(define (instantiate expr frame unbound-var-handler)
  (define (copy expr)
    (cond ((var? expr)
           (let ((binding (binding-in-frame expr frame)))               ; 4.4.4.8: replace any variables by their values in the frame. also, (binding-value)
             (if binding
                 (copy (binding-value binding))                         ; values themselves need to be instantiated (they might be vars, or lists)
                 (unbound-var-handler expr frame))))                    ; unbound variable is passed to EXTERNAL handler from arguments
          ((pair? expr)
           (cons (copy (car expr)) (copy (cdr expr))))                  ; lists are instantiated item by item (converts from query to Lisp object)
          (else expr)))
  (copy expr))


;;;SECTION 4.4.4.2
;;;The Evaluator                                                        ; <==== "qeval ... is the basic evaluator of the query system."

(define (qeval query frame-stream)                                          ; args: a query and a stream of frames; return-val: a stream of extended frames (although this latter doesn't seem to be obvious from this function itself)
  (let ((qproc (get (type query) 'qeval)))                                  ; identifies special forms by data-directed dispatch (cf. 2.5)
    (if qproc
        (qproc (contents query) frame-stream)                               ; 4.4.4.7: (type) and (contents) implement the abstract syntax of the special forms.
        (simple-query query frame-stream))))                                ; Any query that is not identified as a special form is assumed to be a simple query

;;;Simple queries

(define (simple-query query-pattern frame-stream)                       ; returns the stream formed by extending each frame by all data-base matches of the query.
  (stream-flatmap                                                           ; 4.4.4.6 - one large stream of all ways to extend frames to match pattern
   (lambda (frame)                                                          ; strategy from p. 461
     (stream-append-delayed                                                 ; from 4.4.4.6; see also Exercise 4.71
      (find-assertions query-pattern frame)                                 ; 4.4.4.3 - match the pattern against all assertions in the data base, producing a stream of extended frames
      (delay (apply-rules query-pattern frame))))                           ; 4.4.4.4 - apply all possible rules, producing another stream of extended frames
   frame-stream))                                                               ; the WHOLE second stream must be delayed to prevent evaluating its (stream-car) out of order

;;;Compound queries

(define (conjoin conjuncts frame-stream)                                ; (AND) queries - Figure 4.5 p. 456
  (if (empty-conjunction? conjuncts)                                        ; 4.4.4.7: predicates and selectors
      frame-stream
      (conjoin (rest-conjuncts conjuncts)                                   ; process results in series
               (qeval (first-conjunct conjuncts)                            ; all possible frame extensions that satisfy the first query in the conjunction
                      frame-stream))))

;;(put 'and 'qeval conjoin)                                                 ; from (initialize-data-base) - so (get 'and 'qeval) will dispatch here.


(define (disjoin disjuncts frame-stream)                                ; (OR) queries - Figure 4.6 p. 457
  (if (empty-disjunction? disjuncts)                                        ; 4.4.4.7: predicates and selectors
      the-empty-stream
      (interleave-delayed                                                   ; 4.4.4.6 and exercises 4.71, 4.72
       (qeval (first-disjunct disjuncts) frame-stream)
       (delay (disjoin (rest-disjuncts disjuncts)                           ; interleave the results in parallel instead of processing in series
                       frame-stream)))))

;;(put 'or 'qeval disjoin)                                                  ; from (initialize-data-base) - so (get 'or 'qeval) will dispatch here.

;;;Filters

(define (negate operands frame-stream)                                  ; (NOT) filters - p. 457
  (simple-stream-flatmap    ; changed for Exercise 4.74
   (lambda (frame)
     (if (stream-null? (qeval (negated-query operands)                      ; attempt to extend each frame in input stream to satisfy the query being negated
                              (singleton-stream frame)))                    ; 4.4.4.7: selectors
         (singleton-stream frame)                                           ; include a given frame in the output stream only if it cannot be extended 
         the-empty-stream))
   frame-stream))

;;(put 'not 'qeval negate)                                                  ; from (initialize-data-base) - so (get 'not 'qeval) will dispatch here.

(define (lisp-value call frame-stream)                                  ; Lisp filters - p. 458
  (simple-stream-flatmap    ; changed for Exercise 4.74
   (lambda (frame)
     (if (execute
          (instantiate
           call
           frame
           (lambda (v f)                                                    ; (unbound-var-handler var frame). remember?
             (error "Unknown pat var -- LISP-VALUE" v))))                   ; error: unbound pattern variables
         (singleton-stream frame)
         the-empty-stream))                                                 ; frames for which the predicate returns false are filtered out
   frame-stream))

;;(put 'lisp-value 'qeval lisp-value)                                       ; from (initialize-data-base) - so (get 'lisp-value 'qeval) will dispatch here.

(define (execute expr)                                                  ; applies Lisp predicate to query arguments using UNDERLYING apply/eval!
  (apply (eval (predicate expr) user-initial-environment)                   ; (predicate) from 4.4.4.7; user-initial-environment is a Scheme built-in - p. 387
         (args expr)))                                                      ; (args) from 4.4.4.7: not (eval (args expr)), since args of expr come in pre-evaluated
                                                                                ; ok, (eval) is what magically pulls the lisp function into the query system.
(define (always-true ignore frame-stream) frame-stream)                 ; special form used by (rule-body) in 4.4.4.7 for bodyless rules (conclusions always satisfied)
                                                                            ; (qeval): ((get 'always-true 'qeval) (contents query) frame-stream)
;;(put 'always-true 'qeval always-true)

;;;SECTION 4.4.4.3
;;;Finding Assertions by Pattern Matching

(define (find-assertions pattern frame)                                 ; returns stream of frames extended by the database match
  (simple-stream-flatmap (lambda (datum)    ; changed for Exercise 4.74
                    (check-an-assertion datum pattern frame))
                  (fetch-assertions pattern frame)))                        ; 4.4.4.5: stream of assertions to be checked (cheap pre-check - p. 455 Footnote 67?)

(define (check-an-assertion assertion query-pat query-frame)            ; helper function ONLY used by (find-assertions)
  (let ((match-result
         (pattern-match query-pat assertion query-frame)))                  ; match? (punt)
    (if (eq? match-result 'failed)
        the-empty-stream                                                    ; match failed
        (singleton-stream match-result))))                                  ; match succeeded! return one-element stream w/ the extended frame

(define (pattern-match pat dat frame)                                   ; helper function ONLY used in 4.4.4.3 - returns extended frame OR 'failed
  (cond ((eq? frame 'failed) 'failed)                                       ; 'failed will cascade all the way home.
        ((equal? pat dat) frame)                                            ; match succeeds (not a variable!) - do nothing.
        ((var? pat) (extend-if-consistent pat dat frame))                   ; extend frame if consistent (punt)
        ((and (pair? pat) (pair? dat))                                      ; check pattern vs data, element by element, accumulating bindings for the pattern variables.
         (pattern-match (cdr pat)                                           ; recurse on 2nd+ elements
                        (cdr dat)
                        (pattern-match (car pat)                            ; frame extended by 1st element
                                       (car dat)
                                       frame)))
        (else 'failed)))

(define (extend-if-consistent var dat frame)                            ; helper function ONLY used by (pattern-match)
  (let ((binding (binding-in-frame var frame)))                             ; from 4.4.4.8
    (if binding
        (pattern-match (binding-value binding) dat frame)                   ; pp 474-5, 459: reality check, OR recursively check variables bound as values during unification
        (extend var dat frame))))                                           ; from 4.4.4.8: bind previously unbound variable.

;;;SECTION 4.4.4.4                                                      ; ok, now to move beyond simple queries...
;;;Rules and Unification

(define (apply-rules pattern frame)                                     ; "the rule analog of (find-assertions)"
  (stream-flatmap (lambda (rule)                                            ; returns stream of frames extended by database rule applications
                    (apply-a-rule rule pattern frame))                      ; (apply-a-rule) instead of (check-an-assertion)
                  (fetch-rules pattern frame)))                             ; (fetch-rules) instead of (fetch-assertions). 
                                                                                ; 4.4.4.5: stream of possibly applicable rules (cheap pre-check)
(define (apply-a-rule rule query-pattern query-frame)                   ; method outlined in 4.4.2 p. 460; SIMILAR to (check-an-assertion)
  (let ((clean-rule (rename-variables-in rule)))                            ; 0. rename all rule variables with unique names, to prevent collisions between different rule applications
    (let ((unify-result
           (unify-match query-pattern                                       ; 1. Unite query pattern with... 
                        (conclusion clean-rule)                                 ; 4.4.4.7: rule conclusion to...
                        query-frame)))                                          ; augment the argument frame.
      (if (eq? unify-result 'failed)                                        ; 2. If this succeeds...
          the-empty-stream
          (qeval (rule-body clean-rule)                                         ; 4.4.4.7: evaluate the rule body...
                 (singleton-stream unify-result))))))                           ; in the new frame from 1.

(define (rename-variables-in rule)                                      ; helper function ONLY used in (apply-a-rule); no analog in pattern matching. "[instead], we could devise a more clever environment structure... [see] exercise 4.79... A good answer is probably worth a Ph.D."
  (let ((rule-application-id (new-rule-application-id)))                    ; 4.4.4.7: unique id for this rule application
    (define (tree-walk expr)                                                ; need nested function because all recursions share the same id
      (cond ((var? expr)
             (make-new-variable expr rule-application-id))                  ; 4.4.4.7: syntax procedures. ?x becomes ?x-7, say (p. 476)
            ((pair? expr)                                                   ; parse lists recursively
             (cons (tree-walk (car expr))
                   (tree-walk (cdr expr))))
            (else expr)))
    (tree-walk rule)))                                                      ; "root node" is the entire rule.

(define (unify-match p1 p2 frame)                                       ; helper function ONLY used in this subsection. 
  (cond ((eq? frame 'failed) 'failed)                                       ; cf. (pattern-match), except
        ((equal? p1 p2) frame)                                              ; ...matching TWO patterns instead of pattern and datum
        ((var? p1) (extend-if-possible p1 p2 frame))
        ((var? p2) (extend-if-possible p2 p1 frame)) ; {\em ; ***}          ; ...so the other direction needs extension too
        ((and (pair? p1) (pair? p2))
         (unify-match (cdr p1)
                      (cdr p2)
                      (unify-match (car p1)
                                   (car p2)
                                   frame)))
        (else 'failed)))

(define (extend-if-possible var val frame)                              ; helper function ONLY used in (unify-match)
  (let ((binding (binding-in-frame var frame)))                             ; same as (extend-if-consistent) + new cases 2 and 3
    (cond (binding                                                          ; 1. var already bound. match with its value!
           (unify-match
            (binding-value binding) val frame))
          ((var? val)                     ; {\em ; ***}                     ; 2. var not bound but VAL is itself a (different) variable (guaranteed by "equal?" case in (unify-match))
           (let ((binding (binding-in-frame val frame)))
             (if binding                                                        ; if val is bound...
                 (unify-match                                                   
                  var (binding-value binding) frame)                            ; match its value...
                 (extend var val frame))))                                      ; else both var and val are unbound! bind one to the other (direction doesn't matter)
          ((depends-on? val var frame)    ; {\em ; ***}                     ; 3. reject unifying (?x ?x) (?y <expr in ?y>) - p. 478
           'failed)                                                             ; (unify (?x ?x) (?y ?y)) is handled by (equal?) check in (unify-match)
          (else (extend var val frame)))))                                  ; 4. var unbound, val is neither a variable nor f(var). bind to var!

(define (depends-on? expr var frame)                                    ; helper function ONLY used in (extend-if-possible); no analog in pattern matching
  (define (tree-walk e)                                                     ; nested function lets all recursions share var, frame more easily
    (cond ((var? e)
           (if (equal? var e)                                               
               true                                                         ; expr contained var somewhere! (equal? expr var) is ruled out by (unify-match), where it is handled preemptively
               (let ((b (binding-in-frame e frame)))                        ; might need to scan multiple mappings (bindings) in the frame
                 (if b
                     (tree-walk (binding-value b))                          ; substitute values of variables whenever they exist    
                     false))))
          ((pair? e)                                                        ; parse expr down to individual variables
           (or (tree-walk (car e))                                          ; a SINGLE dependence is enough to return "yes" conclusively
               (tree-walk (cdr e))))
          (else false)))
  (tree-walk expr))

;;;SECTION 4.4.4.5
;;;Maintaining the Data Base

(define THE-ASSERTIONS the-empty-stream)                                ; <----- initialize the (unindexed) assertion database

(define (fetch-assertions pattern frame)                                ; helper function ONLY used in (find-assertions) from 4.4.4.3
  (if (use-index? pattern)                                                  ; pp. 479-80: index all patterns starting with a symbol, like (job ...)
      (get-indexed-assertions pattern)
      (get-all-assertions)))

(define (get-all-assertions) THE-ASSERTIONS)

(define (get-indexed-assertions pattern)
  (get-stream (index-key-of pattern) 'assertion-stream))

(define (get-stream key1 key2)                                          ; key1 = name, key2 = 'assertion-stream or 'rule-stream
  (let ((s (get key1 key2)))                                                ; (get <name> <category>) from GLOBAL TABLE (stores indexed assertions/rules, and also special forms for qeval)
    (if s s the-empty-stream)))                                             ; each table entry is a stream - e.g. multiple (job) assertions or (lives-near) rules

(define THE-RULES the-empty-stream)                                     ; <----- initialize the (unindexed) rule database

(define (fetch-rules pattern frame)                                     ; helper function ONLY used in (apply-rules) from 4.4.4.4
  (if (use-index? pattern)                                                  ; cf. (fetch-assertions)
      (get-indexed-rules pattern)
      (get-all-rules)))

(define (get-all-rules) THE-RULES)

(define (get-indexed-rules pattern)                                     ; helper function ONLY used in (fetch-rules)
  (stream-append                                                            ; why not (stream-append-delayed)? because fetched rules are unified immediately anyway?
   (get-stream (index-key-of pattern) 'rule-stream)
   (get-stream '? 'rule-stream)))                                           ; (<symbol> ...) can match rule conclusions starting with a variable

(define (add-rule-or-assertion! assertion)                              ; helper function ONLY used in (query-driver-loop)
  (if (rule? assertion)
      (add-rule! assertion)
      (add-assertion! assertion)))

(define (add-assertion! assertion)                                      ; helper function ONLY used in (add-rule-or-assertion!)
  (store-assertion-in-index assertion)                                      ; store in indexed database if possible (may fail silently)
  (let ((old-assertions THE-ASSERTIONS))
    (set! THE-ASSERTIONS                                                    ; store in main (unindexed) assertion database
          (cons-stream assertion old-assertions))                           ; NOT paranoid! required basically because assignment + delayed streams DON'T MIX
    'ok))                                                                       ; see Exercise 4.70 for details

(define (add-rule! rule)                                                ; helper function ONLY used in (add-rule-or-assertion!)
  (store-rule-in-index rule)                                                ; store in indexed database if possible (may fail silently)
  (let ((old-rules THE-RULES))
    (set! THE-RULES (cons-stream rule old-rules))                           ; store in main (unindexed) rule database
    'ok))

(define (store-assertion-in-index assertion)                            ; helper function only used by (add-assertion!) and (initialize-data-base)
  (if (indexable? assertion)                                                ; shouldn't this be (use-index?) instead? assertions can't contain variables...
      (let ((key (index-key-of assertion)))
        (let ((current-assertion-stream
               (get-stream key 'assertion-stream)))
          (put key
               'assertion-stream
               (cons-stream assertion
                            current-assertion-stream))))))

(define (store-rule-in-index rule)                                      ; helper function only used by (add-rule!) and (initialize-data-base)
  (let ((pattern (conclusion rule)))                                        ; index by CONCLUSION, not the entire rule
    (if (indexable? pattern)                                                ; rules starting with a symbol OR a variable will be indexed.
        (let ((key (index-key-of pattern)))
          (let ((current-rule-stream
                 (get-stream key 'rule-stream)))
            (put key
                 'rule-stream
                 (cons-stream rule                                          ; store the entire rule in the indexed database
                              current-rule-stream)))))))

(define (indexable? pat)                                                ; helper function ONLY used in (store-assertion) and (store-rule)   
  (or (constant-symbol? (car pat))                                          ; this function is only used to decide whether to WRITE pat=rule/assertion to the index
      (var? (car pat))))                                                    

(define (index-key-of pat)
  (let ((key (car pat)))
    (if (var? key) '? key)))                                            ; (get '? 'rule-stream) = all rules starting with a variable

(define (use-index? pat)                                                ; helper function ONLY used in (fetch-assertions) and (fetch-rules)
  (constant-symbol? (car pat)))                                             ; this function is only used to decide whether to READ pat=query from the index (else, read full unindexed database)

;;;SECTION 4.4.4.6
;;;Stream operations

(define (stream-append-delayed s1 delayed-s2)                           ; helper function ONLY used in (simple-query)
  (if (stream-null? s1)                                                     
      (force delayed-s2)                                                    ; unlike (stream-append), 2nd argument is FULLY delayed (not just its stream-cdr)
      (cons-stream
       (stream-car s1)
       (stream-append-delayed (stream-cdr s1) delayed-s2))))                ; "postpones looping in some cases (see Exercise 4.71)"

(define (interleave-delayed s1 delayed-s2)                              ; helper function ONLY used in (disjoin) and (flatten-stream)
  (if (stream-null? s1)                                                     ; although (stream-flatmap) is used in several places...
      (force delayed-s2)
      (cons-stream
       (stream-car s1)
       (interleave-delayed (force delayed-s2)
                           (delay (stream-cdr s1))))))                      ; "postpones looping in some cases (see exercise 4.71)"

(define (stream-flatmap proc s)                                         ; e.g. from (simple-query) - (stream-map) returns a stream for each frame
  (flatten-stream (stream-map proc s)))                                     ; flatten merges the streams for all the frames into one BIG stream.

(define (flatten-stream stream)                                         ; helper function used ONLY by (stream-flatmap)    
  (if (stream-null? stream)
      the-empty-stream
      (interleave-delayed                                                   ; uses interleave instead of append, unlike ordinary flatmap [because streams might be infinite? or at least very long...?]
       (stream-car stream)                                                  ; "see exercises 4.72 and 4.73"
       (delay (flatten-stream (stream-cdr stream))))))


(define (singleton-stream x)                                            ; generate a stream consisting of a single element
  (cons-stream x the-empty-stream))
  
(define simple-stream-flatmap stream-flatmap)   ; override in Exercise 4.74                    


;;;SECTION 4.4.4.7
;;;Query syntax procedures

(define (type expr)                                                     ; low-level selector ONLY used in (qeval) and (assertion-to-be-added?)
  (if (pair? expr)                                                          ; same as (type-tag) in 2.4.2, except error message
      (car expr)
      (error "Unknown expression TYPE" expr)))

(define (contents expr)                                                 ; low-level selector ONLY used in (qeval) and (add-assertion-body)
  (if (pair? expr)                                                          ; same as (contents) in 2.4.2, except error message
      (cdr expr)
      (error "Unknown expression CONTENTS" expr)))

(define (assertion-to-be-added? expr)                                   ; low-level predicate ONLY used in (query-driver-loop)
  (eq? (type expr) 'assert!))                                               ; Query input: (assert! <rule-or-assertion>)

(define (add-assertion-body expr)                                       ; low-level SELECTOR only used in (query-driver-loop)
  (car (contents expr)))                                                    ; a less misleading name would be (assertion-body expr)

(define (empty-conjunction? exps) (null? exps))                         ; "syntax definitions" for (and) special form handler, (conjoin)
(define (first-conjunct exps) (car exps))                                   ; these are for PARSING QUERIES, not constructing streams per se...
(define (rest-conjuncts exps) (cdr exps))                                   ; stream construnction is done via (qeval) and frame accounting.

(define (empty-disjunction? exps) (null? exps))                         ; syntax definitions for (or) special form handler, (disjoin)
(define (first-disjunct exps) (car exps))
(define (rest-disjuncts exps) (cdr exps))

(define (negated-query exps) (car exps))                                ; syntax definition for (not) special form handler, (negate)

(define (predicate exps) (car exps))                                    ; syntax definitions for (lisp-value) special form sub-handler, (execute)
(define (args exps) (cdr exps))


(define (rule? statement)                                               ; syntax definitions of rules
  (tagged-list? statement 'rule))                                           ; helper selector only used in (add-rule-or-assertion!) and (initialize-data-base)

(define (conclusion rule) (cadr rule))                                      ; helper selector only used in (apply-a-rule) and (store-rule-in-index)

(define (rule-body rule)                                                    ; helper selector ONLY used in (apply-a-rule).
  (if (null? (cddr rule))
      '(always-true)
      (caddr rule)))

(define (query-syntax-process expr)                                     ; helper function only called from (query-driver-loop) and (initialize-data-base)
  (map-over-symbols expand-question-mark expr))                             ; Substitutes in expression: ?variable -> (? variable), etc.
                                                                            ; 1. don't have to re-parse variables, and 2. prepares vars for application id below
(define (map-over-symbols proc expr)                                    ; helper function only called from (query-syntax-process)
  (cond ((pair? expr)
         (cons (map-over-symbols proc (car expr))
               (map-over-symbols proc (cdr expr))))
        ((symbol? expr) (proc expr))
        (else expr)))                                                       ; leave all non-symbols alone

(define (expand-question-mark symbol)                                   ; helper function only called from (map-over-symbols) on a symbol.
  (let ((chars (symbol->string symbol)))
    (if (string=? (substring chars 0 1) "?")                                ; if a symbol is of the form ?<name>...
        (list '?                                                            ; replace with (? <name>)...
              (string->symbol
               (substring chars 1 (string-length chars))))
        symbol)))                                                           ; otherwise, leave it alone.

(define (var? expr)                                                     ; predicate to match (expand-question-mark)
  (tagged-list? expr '?))

(define (constant-symbol? expr) (symbol? expr))                         ; predicate to match (expand-question-mark) NEGATIVE case (symbol unchanged)

(define rule-counter 0)                                                 ; global id for rule applications!? NOT thread-safe?

(define (new-rule-application-id)                                       ; helper function ONLY called in (rename-variables-in)
  (set! rule-counter (+ 1 rule-counter))                                    ; definitely not thread-safe...
  rule-counter)

(define (make-new-variable var rule-application-id)                     ; helper function ONLY called in (rename-variables-in)
  (cons '? (cons rule-application-id (cdr var))))                           ; (? <id#> <name>) - since var = (? <name>) from (rename-variables-in)

(define (contract-question-mark variable)                               ; helper function ONLY called from (query-driver-loop)
  (string->symbol                                                           ; printifies result of (expand-question-mark) AND (make-new-variable), 
   (string-append "?"                                                       ; (if the latter was ever applied)
     (if (number? (cadr variable))
         (string-append (symbol->string (caddr variable))                   ; must be (? <id#> <name>) from (make-new-variable)
                        "-"
                        (number->string (cadr variable)))                       ; result is '?<name>-<id#>
         (symbol->string (cadr variable))))))                               ; (? <name>) -> '?<name>


;;;SECTION 4.4.4.8
;;;Frames and bindings                                                  ; "Frames are represented as lists of bindings, which are variable-value pairs."
(define (make-binding variable value)                                       ; i.e., as 1-d tables, p. 267
  (cons variable value))

(define (binding-variable binding)                                          ; this is actually UNUSED - until Exercise 4.76, that is...
  (car binding))

(define (binding-value binding)                                             ; helper selector ONLY used in (instantiate) and the 2 (extend) procedures
  (cdr binding))


(define (binding-in-frame variable frame)
  (assoc variable frame))                                                   ; pp. 267-268: assoc does 1-d table lookup via (caar)

(define (extend variable value frame)                                       ; low-level "constructor" for (extend-if-consistent) and (extend-if-possible)
  (cons (make-binding variable value) frame))


;;;;From Section 4.1

(define (tagged-list? expr tag)
  (if (pair? expr)
      (eq? (car expr) tag)
      false))

(define (prompt-for-input string)
  (newline) (newline) (display string) (newline))


;;;;Stream support from Chapter 3

;(define (stream-map proc s)                                             ; actually, aren't these built-in?
;  (if (stream-null? s)
;      the-empty-stream
;      (cons-stream (proc (stream-car s))
;                   (stream-map proc (stream-cdr s)))))
;
;(define (stream-for-each proc s)
;  (if (stream-null? s)
;      'done
;      (begin (proc (stream-car s))
;             (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))
(define (display-line x)
  (newline)
  (display x))

;(define (stream-filter pred stream)
;  (cond ((stream-null? stream) the-empty-stream)
;        ((pred (stream-car stream))
;         (cons-stream (stream-car stream)
;                      (stream-filter pred
;                                     (stream-cdr stream))))
;        (else (stream-filter pred (stream-cdr stream)))))
;
;(define (stream-append s1 s2)
;  (if (stream-null? s1)
;      s2
;      (cons-stream (stream-car s1)
;                   (stream-append (stream-cdr s1) s2))))

(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

;;;;Table support from Chapter 3, Section 3.3.3 (local tables)

(define (make-table)                                                    ; 2-d table used by indexed database in 4.4.4.5, and (qeval) special forms
  (let ((local-table (list '*table*)))
    (define (lookup key-1 key-2)
      (let ((subtable (assoc key-1 (cdr local-table))))
        (if subtable
            (let ((record (assoc key-2 (cdr subtable))))
              (if record
                  (cdr record)
                  false))
            false)))
    (define (insert! key-1 key-2 value)
      (let ((subtable (assoc key-1 (cdr local-table))))
        (if subtable
            (let ((record (assoc key-2 (cdr subtable))))
              (if record
                  (set-cdr! record value)
                  (set-cdr! subtable
                            (cons (cons key-2 value)
                                  (cdr subtable)))))
            (set-cdr! local-table
                      (cons (list key-1
                                  (cons key-2 value))
                            (cdr local-table)))))
      'ok)    
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            (else (error "Unknown operation -- TABLE" m))))
    dispatch))

;;;; From instructor's manual                                           ; this'd be LOW if they hadn't open-sourced everything

(define get '())                                                            ; initially uninitialized because no table has been constructed...

(define put '())                                                            ; global get/put, but table lives in (initialize-data-base). inconsistent, or encapsulated?

(define (initialize-data-base rules-and-assertions)                     ; input: raw data as a list of assertions and rules
  (define (deal-out r-and-a rules assertions)                           ; local function that builds up databases ITERATIVELY
    (cond ((null? r-and-a)                                                  ; done parsing input
           (set! THE-ASSERTIONS (list->stream assertions))              ; output 1: unindexed assertion database (global variable)
           (set! THE-RULES (list->stream rules))                        ; output 2: unindexed rule database (global variable)
           'done)
          (else
           (let ((s (query-syntax-process (car r-and-a))))
             (cond ((rule? s)
                    (store-rule-in-index s)                             ; output 3: indexed rules as (<name> 'rule-stream) in local table below
                    (deal-out (cdr r-and-a)                                 ; "deal out" into rule/assertion piles
                              (cons s rules)
                              assertions))
                   (else
                    (store-assertion-in-index s)                        ; output 4: indexed assertions as (<name 'assertion-stream) in local table below
                    (deal-out (cdr r-and-a)
                              rules
                              (cons s assertions))))))))
  (let ((operation-table (make-table)))                                 ; assign get and put as in ch2support.scm
    (set! get (operation-table 'lookup-proc))                               ; (get <name> <category>) and (put <name> <category> value)    
    (set! put (operation-table 'insert-proc!)))                             ; categories: 'qeval (4.4.4.2); 'assertion-stream and 'rule-stream (4.4.4.5)
  (put 'and 'qeval conjoin)
  (put 'or 'qeval disjoin)
  (put 'not 'qeval negate)
  (put 'lisp-value 'qeval lisp-value)
  (put 'always-true 'qeval always-true)
  (deal-out rules-and-assertions '() '()))                              ; start iterative dealing

;; Do following to reinit the data base from microshaft-data-base
;;  in Scheme (not in the query driver loop)
;; (initialize-data-base microshaft-data-base)

(define microshaft-data-base
  '(
;; from section 4.4.1
(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))
(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 60000)

(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78))               ; "A Lisp Hacker" - had to Google that one...
(job (Hacker Alyssa P) (computer programmer))
(salary (Hacker Alyssa P) 40000)
(supervisor (Hacker Alyssa P) (Bitdiddle Ben))

(address (Fect Cy D) (Cambridge (Ames Street) 3))
(job (Fect Cy D) (computer programmer))
(salary (Fect Cy D) 35000)
(supervisor (Fect Cy D) (Bitdiddle Ben))

(address (Tweakit Lem E) (Boston (Bay State Road) 22))
(job (Tweakit Lem E) (computer technician))
(salary (Tweakit Lem E) 25000)
(supervisor (Tweakit Lem E) (Bitdiddle Ben))

(address (Reasoner Louis) (Slumerville (Pine Tree Road) 80))        ; Loose Reasoner
(job (Reasoner Louis) (computer programmer trainee))
(salary (Reasoner Louis) 30000)
(supervisor (Reasoner Louis) (Hacker Alyssa P))

(supervisor (Bitdiddle Ben) (Warbucks Oliver))

(address (Warbucks Oliver) (Swellesley (Top Heap Road)))            ; apparently this is Little Orphan Annie's adoptive father
(job (Warbucks Oliver) (administration big wheel))
(salary (Warbucks Oliver) 150000)

(address (Scrooge Eben) (Weston (Shady Lane) 10))
(job (Scrooge Eben) (accounting chief accountant))
(salary (Scrooge Eben) 75000)
(supervisor (Scrooge Eben) (Warbucks Oliver))

(address (Cratchet Robert) (Allston (N Harvard Street) 16))
(job (Cratchet Robert) (accounting scrivener))
(salary (Cratchet Robert) 18000)
(supervisor (Cratchet Robert) (Scrooge Eben))

(address (Aull DeWitt) (Slumerville (Onion Square) 5))              ; not sure about this one... unless always intended to be read Last, First?
(job (Aull DeWitt) (administration secretary))
(salary (Aull DeWitt) 25000)
(supervisor (Aull DeWitt) (Warbucks Oliver))

(can-do-job (computer wizard) (computer programmer))
(can-do-job (computer wizard) (computer technician))

(can-do-job (computer programmer)
            (computer programmer trainee))

(can-do-job (administration secretary)                              ; p. 443: "as is well known"
            (administration big wheel))

(rule (lives-near ?person-1 ?person-2)
      (and (address ?person-1 (?town . ?rest-1))
           (address ?person-2 (?town . ?rest-2))
           (not (same ?person-1 ?person-2))))

(rule (same ?x ?x))                                                 ; Footnote 66: "allow rules without bodies...to mean that the rule conclusion is satisfied by any values of the variables."

(rule (wheel ?person)
      (and (supervisor ?middle-manager ?person)
           (supervisor ?x ?middle-manager)))

(rule (outranked-by ?staff-person ?boss)
      (or (supervisor ?staff-person ?boss)
          (and (supervisor ?staff-person ?middle-manager)
               (outranked-by ?middle-manager ?boss))))
))






; my new convenience function.
(define (run) 
    (initialize-data-base microshaft-data-base)
    (query-driver-loop)
)



; my new convenience functions - for running batch scripts. based on (query-driver-loop)
(define (init-query)
    (initialize-data-base microshaft-data-base))    
(define (query input)

    (define (done) (display "\nOkie dokie, boss\n\n"))
    
  ;(prompt-for-input 
  (display "\n;;; Input from batch file\n")
  (display input)
  (newline)

  (let ((q (query-syntax-process input)))
    (cond ((assertion-to-be-added? q)
           (add-rule-or-assertion! (add-assertion-body q))
           (newline)
           (display "Assertion added to data base.")
           (done)) ;(query-driver-loop))
          (else
           (newline)
           (display output-prompt)
           ;; [extra newline at end] (announce-output output-prompt)
           (display-stream
            (stream-map
             (lambda (frame)
               (instantiate q
                            frame
                            (lambda (v f)
                              (contract-question-mark v))))
             (qeval q (singleton-stream '()))))
           (done))))) ;(query-driver-loop)))))