Exercise 4.77.  In section 4.4.3 we saw that not and lisp-value can 
cause the query language to give ``wrong'' answers if these filtering 
operations are applied to frames in which variables are unbound. Devise 
a way to fix this shortcoming. One idea is to perform the filtering in a 
``delayed'' manner by appending to the frame a ``promise'' to filter 
that is fulfilled only when enough variables have been bound to make the 
operation possible. We could wait to perform filtering until all other 
operations have been performed. However, for efficiency's sake, we would 
like to perform filtering as soon as possible so as to cut down on the 
number of intermediate frames generated.

————————————————————————————————————————————————————————————————————————

The example given in the text,

(and (supervisor ?x ?y)
     (not (job ?x (computer programmer))))

(and (not (job ?x (computer programmer)))
     (supervisor ?x ?y))

can be easily fixed by re-ordering all conjuctions when they are scanned 
so that any 'not' expression which uses a variable comes after the 
expression which binds it.

Once disjunctions are introduced, this seems to become complicated 
quickly, but might work well enough for most cases.  The idea is that 
every time the evaluator sees a conjunction, it examines each conjunct 
to find any `not` statements, and collects the free[1] variables 
appearing in them, and for every conjunct, collects the variables that 
can be bound by that expression.  Then it re-orders the conjuncts so 
that each `not` statement comes after each conjunct which could bind its 
free variables.  Unfortunately we can easily create dependency loops 
where no such ordering is possible.

A more robust solution then is the one suggested in the exercise, where 
a 'promise' to filter is attached to each frame.

This can be implemented with a few changes.  When a `not` expression is 
encountered, we scan it for variables not yet bound, and if any are found, 
create a 'promise', which is a list of the unbound variables on which it 
depends, and the `not` expression itself.  Whenever a binding is added 
to a frame, we call a procedure which scans the list of promises on that 
frame.  For each promise, if it contains a reference to the variable we 
have just bound, we remove that from the list.  If the list is empty, we 
then run the predicate against the frame, and if it fails, remove the 
frame from the stream, otherwise we remove the promise from the list.

When frames are displayed to the user, we must test if any promises 
remain attached to them.  If so, then a Lisp expression or a `not` was 
used which referenced a variable that was never bound and so could never 
be tested; in such cases we could raise an error.