Uh oh, am I being too controlling?
ALWAYS-TRUE: The general form of a rule is
(rule (conclusion) body)
analogous to
(define (function args...) body)
in Scheme.
How do you try using a rule to satisfy a query? There are two steps: (1) Unify the conclusion of the rule with the query. (2) If that succeeds (i.e., doesn't report FAILED), then qeval the body in the frame-stream it reports. This gives rise to a possibly-extended-or-shortened stream of possibly-extended frames.
But some rules have empty bodies, e.g.,
(rule (append () ?b ?b))
They could have made that a special case in APPLY-A-RULE this way (my added code in capital letters -- this is why symbols should be case-insensitive!):
(define (apply-a-rule rule query-pattern query-frame)
(let ((clean-rule (rename-variables-in rule)))
(let ((unify-result
(unify-match query-pattern
(conclusion clean-rule)
query-frame)))
(if (eq? unify-result 'failed)
the-empty-stream
(IF (NULL? (RULE-BODY CLEAN-RULE)) ; no body?
(SINGLETON-STREAM UNIFY-RESULT) ; return unify result
(qeval (rule-body clean-rule)
(singleton-stream unify-result)))))))
but instead they are avoiding having to make that test by being extra clever in the selector RULE-BODY:
(define (rule-body rule)
(if (null? (cddr rule))
'(always-true)
(caddr rule)))
so that instead of seeing an empty body, APPLY-A-RULE sees (ALWAYS-TRUE).
The use of PUT here isn't about polymorphism; it's about recognizing special forms in the query language, which mostly means AND, OR, and NOT. But the PUT makes ALWAYS-TRUE also a special form, which means that instead of treating it as a query (remember, bodies are made of queries) and trying to match it against the database of assertions and rules, qeval will just call the Scheme procedure that's PUT into the table as the value associated with the key ALWAYS-TRUE. (The 'QEVAL as the second argument to PUT is just because back in Chapter 2 they defined PUT to use a 2D table, I think. Just take PUT on faith.)
So what happens when the evaluator finds a special form?
(define (qeval query frame-stream)
(LET ((QPROC (GET (TYPE QUERY) 'QEVAL)))
(IF QPROC
(QPROC (CONTENTS QUERY) FRAME-STREAM)
(simple-query query frame-stream))))
This is the code from the book; I haven't changed it. The capitalized part is what handles special forms. We look up the car of the query (that's what TYPE does) in the get/put table, and if we find it, call the procedure in the table value with two inputs: the special form with its keyword removed (CONTENTS is cdr) and the frame stream. They remove the keyword because in the usual case of AND, OR, or NOT, the contents part of the special form is a list of queries (AND query query ...) and so the handler can call itself recursively on the cdr of that list.
But in the case of ALWAYS-TRUE, the CONTENTS will be empty; there aren't any sub-queries to evaluate. So ALWAYS-TRUE has to be written to expect two arguments: an empty list of queries, which it ignores, and a frame stream, which it returns unchanged.
CONTENTS: Yes, your translation is okay, although PAIR? isn't the same as LIST?. It's making sure the EXPRESSION is a nonempty list. That's so that the query language won't accept (AND) etc.; those special forms require at least one sub-query (exactly one sub-query in the case of NOT). I guess also a perverse user could say (AND . FOO) to get a non-list CONTENTS.
I'm not saying you have to exactly copy the SICP code! Just that you should understand the SICP code and in particular how they use the idea of a stream of frames to make the whole thing functional.
; thus the generating block would be like: 
, looking odd.
I'm afraid that's a subject for juicier fora.
