\documentstyle[6.001-ps]{article}
\begin{document}
\header{9}{May 3, 1989}
\part{1: Homework exercises}
\exercise{9.1}
Added to \verb+CDATA.SCM+:
\bv
(rule (reverse () ()))

(rule (reverse (?x . ?restx) ?y)
      (and (reverse ?restx ?rrestx)
           (append-to-end ?rrestx ?x ?y)))

(rule (append-to-end () ?x (?x)))

(rule (append-to-end (?x . ?restx) ?y (?x . ?z))
      (append-to-end ?restx ?y ?z))
\end{verbatim}
\vbreak
Sample query:
\bv
query==> (reverse (1 2 3) ?x)
Responses to query:
(REVERSE (1 2 3) (3 2 1))
"done" 
\end{verbatim}
\exercise{9.2}
The \verb+let+/\verb+set!+ combination is necessary because a \verb+set!+ by
itself would modify the rule or assertion-list for all delayed frames
which still have to be executing.  The \verb+let+ creates a new frame
so that everything acts as expected.
\part{2: Freshman Advisors, Revisited}
\problem{9.1}
\begin{itemize}
\item
\bv
query==> (meets ?class tuesday ?time)
Responses to query:
(MEETS 18:02 TUESDAY 1:00)
(MEETS 18:01 TUESDAY 1:00)
(MEETS 6:003 TUESDAY 12:00)
(MEETS 6:002 TUESDAY 11:00)
(MEETS 6:001 TUESDAY 10:00)
"done" 
\end{verbatim}
\item
\bv
query==> (meets ?class ?day 1:00)
Responses to query:
(MEETS 18:03 FRIDAY 1:00)
(MEETS 18:03 WEDNESDAY 1:00)
(MEETS 18:03 MONDAY 1:00)
(MEETS 18:02 THURSDAY 1:00)
(MEETS 18:02 TUESDAY 1:00)
(MEETS 18:01 THURSDAY 1:00)
(MEETS 18:01 TUESDAY 1:00)
"done" 
\end{verbatim}
\item
\bv
query==> (is-in-prerequisite-chain ?class 6:003)
Responses to query:
(IS-IN-PREREQUISITE-CHAIN 6:001 6:003)
(IS-IN-PREREQUISITE-CHAIN 18:03 6:003)
(IS-IN-PREREQUISITE-CHAIN 6:002 6:003)
(IS-IN-PREREQUISITE-CHAIN 18:02 6:003)
(IS-IN-PREREQUISITE-CHAIN 18:01 6:003)
"done" 
\end{verbatim}
\item
\bv
query==> (is-in-prerequisite-chain 6:001 ?class)
Responses to query:
(IS-IN-PREREQUISITE-CHAIN 6:001 6:003)
"done" 
\end{verbatim}
\item
\bv
query==> (and (is-in-prerequisite-chain 6:001 ?class)
              (is-in-prerequisite-chain 18:01 ?class))
Responses to query:
(AND (IS-IN-PREREQUISITE-CHAIN 6:001 6:003)
     (IS-IN-PREREQUISITE-CHAIN 18:01 6:003))
"done" 
\end{verbatim}
\item
\bv
query==> (must-take-first-for hal ?class 6:003)
Responses to query:
(MUST-TAKE-FIRST-FOR HAL 18:03 6:003)
(MUST-TAKE-FIRST-FOR HAL 6:002 6:003)
(MUST-TAKE-FIRST-FOR HAL 18:02 6:003)
"done" 
\end{verbatim}
\item
\bv
query==> (and (meets ?class tuesday ?time)
              (units ?class ?units)
              (lisp-value > ?units 12))
Responses to query:
(AND (MEETS 6:003 TUESDAY 12:00) (UNITS 6:003 15) (LISP-VALUE > 15 12))
(AND (MEETS 6:002 TUESDAY 11:00) (UNITS 6:002 15) (LISP-VALUE > 15 12))
(AND (MEETS 6:001 TUESDAY 10:00) (UNITS 6:001 15) (LISP-VALUE > 15 12))
"done" 
\end{verbatim}
\item
\bv
query==> (conflicts ?x 18:02)
Responses to query:
(CONFLICTS 18:01 18:02)
(CONFLICTS 18:01 18:02)
(CONFLICTS 18:01 18:02)
"done" 
\end{verbatim}
\end{itemize}
\problem{9.2}
Added to \verb+CDATA.SCM+:
\bv
(rule (time-sink ?class)
      (and (units ?class ?units)
           (lisp-value > ?units 12)))
\end{verbatim}
\vbreak
Sample query:
\bv
query==> (and (is-in-prerequisite-chain ?class 6:003)
              (time-sink ?class))
Responses to query:
(AND (IS-IN-PREREQUISITE-CHAIN 6:001 6:003) (TIME-SINK 6:001))
(AND (IS-IN-PREREQUISITE-CHAIN 6:002 6:003) (TIME-SINK 6:002))
"done" 
\end{verbatim}
\problem{9.3}
The second definition will not work.  It will not work because
\verb+not+ acts as a filter.  Because there is nothing in the incoming
stream, none of the variables are bound, there is nothing to be
filtered, and the output is undefined.  When the database is searched
first, then there is something in the stream to process, and
\verb+conflicts+ works.
\problem{9.4}
Added to \verb+CDATA.SCM+:
\bv
(rule (ultimate-prerequisite-for ?prereq ?s)
      (and (is-in-prerequisite-chain ?prereq ?s)
           (not (has-prerequisite ?prereq ?anything))))
\end{verbatim}
\vbreak
Sample query:
\bv
query==> (ultimate-prerequisite-for ?class 6:003)
Responses to query:
(ULTIMATE-PREREQUISITE-FOR 6:001 6:003)
(ULTIMATE-PREREQUISITE-FOR 18:01 6:003)
"done" 
\end{verbatim}
\problem{9.5}
Both the query interpreter and my brain noticed that 18:01 and 18:03 do not
conflict.  This is not what the problem set says, but this is not a problem.
I just ``rescheduled'' 18:03 for TRF instead of MWF for this problem.

The duplicates occur because there are multiple data items which match
the query.  In this example, 18:01 and 18:03 conflict two days a week and
18:01 and 18:02 conflict three days a week.  When the stream is being filtered,
each frame matches, so they are all returned, even though they appear
the same in terms of the query.
\problem{9.6}
\bv
(define (process-syntaxed-query q)
  (print-stream-elements-on-separate-lines
   (remove-duplicates
    (map-stream (lambda (frame)
                        (instantiate q
                                     frame
                                     (lambda (v f) 
                                       (contract-question-mark v))))
                (qeval q (singleton '()))))))

(define (remove-duplicates q)
  (cond ((empty-stream? q) q)
        ((empty-stream? (tail q)) q)
        ((equal? (head q)
                 (head (tail q)))
         (remove-duplicates (cons-stream (head q) (tail (tail q)))))
        (else (cons-stream (head q) (remove-duplicates (tail q))))))
\end{verbatim}
\vbreak
Sample query:
\bv
query==> (conflicts ?x 18:01)
Responses to query:
(CONFLICTS 18:03 18:01)
(CONFLICTS 18:02 18:01)
"done"
\end{verbatim} 
\end{document}
