\documentstyle[6.001-ps]{article}
\begin{document}
\header{4}{March 10, 1989}
\part{1: Homework Exercises}
\exercise{4.1}
\bv
(cons a b)
;Value: ((1 2) 3 4 5)

(append a b)
;Value: (1 2 3 4 5)

(list a b)
;Value: ((1 2) (3 4 5))
\end{verbatim}
\exercise{4.2}
\bv
(list a 'b c 'd)
;Value: (4 b 2 d)

(list (list a) (list b))
;Value: ((4) (3))

(cons (list d) 'b)
;Value: ((1) . b)

(cadr '((a b) (c d) (a d) (b c)))
;Value: (c d)

(cdr '(a))
;Value: ()

(atom? (caddr '(Welcome to MIT)))
;Value: #t

(memq 'sleep '(where getting enough sleep))
;Value: #t

(memq 'time '((requires good) (management of time)))
;Value: ()
\end{verbatim}
\exercise{4.3}
\bv
(define (equal? a b)
  (cond ((and (null? a) (null? b)) #t)
        ((and (symbol? a) (symbol? b)) (eq? a b))
        ((and (list? a) (list? b)) (and (equal? (car a) (car b))
                                        (equal? (cdr a) (cdr b))))
        (else '())))
\end{verbatim}
\exercise{4.4}
\bv
(member '(great fun) '(spelunking is great fun))
;Value: ()

(member '(great fun) '((spelunking is) (great fun) (so they say)))
;Value: #t

(member '(great fun) '((spelunking is) ((great fun) (so they say))))
;Value: ()
\end{verbatim}
\exercise{4.5}
\bv
(define (filter f l)
  (cond ((null? l) '())
        ((f (car l)) (cons (car l) (filter f (cdr l))))
        (else (filter f (cdr l)))))
\end{verbatim}
\exercise{4.6}
\bv
(tree-acc + (lambda (x) x) 0 '(1 (2) ((3) 4 5)))
;Value: 15

(tree-acc append (lambda x (list x)) '() '((a b) (c d) (e (f g))))
;Value: ((a) (b) (c) (d) (e) (f) (g))

(tree-acc
 cons
 (lambda (x) (if (memq x '(liberal ACLU)) '*censored* x))
 '()
 '((my opponent) is (a (bleeding-heart liberal)) member (of the (ACLU))))
;Value: ((my opponent) is (a (bleeding-heart *censored*)) member (of the (*censored*)))
\end{verbatim}
\exercise{4.7}
\bv
(define (same-parity num . lst)
  (if (odd? num)
      (cons num (filter odd? lst))
      (cons num (filter even? lst))))
\end{verbatim}
\part{3: Building a freshman advisor - To do in lab}
\problem{4.1}
\bv
(define (entry-keys entry)
  (car entry))

(define (entry-value entry)
  (cadr entry))

(define (filter f l)
  (cond ((null? l) '())
        ((f (car l)) (cons (car l) (filter f (cdr l))))
        (else (filter f (cdr l)))))


(see-advisor 'marc)
(HI MARC) 
(I AM YOUR FRESHMAN ADVISOR) 
(WHAT ARE YOUR PLANS FOR THE SEMESTER) 
**(I plan on taking 6:001 and 18:02)
(YOU HAVE TO TAKE 18:01 FIRST) 
**(What about 6:001 ?)
(6:001 IS TOO MUCH WORK FOR FRESHMEN -- WAIT UNTIL NEXT YEAR) 
**(Do you have any suggestions for a hass-d ?)
(MIT HAS A LOT OF INTERESTING DEPARTMENTS) 
**(That wasn't very specific)
(I AM GLAD TO HEAR THAT THAT WASN 'T VERY SPECIFIC) 
**(Schedule me for 18:01)
(HAVE YOU CONSIDERED A CONTEXT SUBJECT) 
**(I want to take 18:01 !!!!)
(HOW ABOUT A FRESHMAN SEMINAR) 
**(I am getting a new advisor)
(I AM GLAD TO HEAR THAT YOU ARE GETTING A NEW ADVISOR) 
**(goodbye)
(GOODBYE MARC) 
(HAVE A GOOD SEMESTER!) 
\end{verbatim}
\problem{4.3}
\bv
(define (make-entry keys . values)
  (list keys values))

(define (entry-value entry)
  (pick-random (cadr entry)))


(see-advisor 'marc)
(HI MARC) 
(I AM YOUR FRESHMAN ADVISOR) 
(WHAT ARE YOUR PLANS FOR THE SEMESTER) 
**(I want to take 6:001)
(WHY DON 'T YOU TAKE 1:00 INSTEAD) 
**(What is wrong with 6:001)
(COMPUTERS ARE A WASTE OF TIME) 
**(I'm sure the 6:001 instructor doesn't think that)
(6:001 IS TOO MUCH WORK FOR FRESHMEN -- WAIT UNTIL NEXT YEAR) 
**(But 6:001 is not being offered then)
(6:001 IS TOO MUCH WORK FOR FRESHMEN -- WAIT UNTIL NEXT YEAR) 
**(fine.  I'll take 18:02)
(YOU HAVE TO TAKE 18:01 FIRST) 
**(goodbye)
(GOODBYE MARC) 
(HAVE A GOOD SEMESTER!) 
\end{verbatim}
\problem{4.4}
\bv
(define (find-response entries input)
  (let ((possible-responses
         (filter (lambda (val) (not (null? val)))
                 (mapcar (lambda (x) (lookup input (entry-keys x) (entry-value x)))
                         entries))))
    (if (null? possible-responses)
        '()
        (pick-random possible-responses))))

(define (lookup sentence keys value)
  (cond ((null? keys) '())
        ((in-sentence sentence (car keys)) value)
        (else (lookup sentence (cdr keys) value))))

(define (in-sentence sentence key)
  (if (symbol? key)
      (member key sentence)
      (sub-phrase sentence key)))

(define (sub-phrase sentence key)
  (cond ((null? key) t)
        ((null? sentence) '())
        ((equal? (car key) (car sentence))
         (or (is-front (cdr key) (cdr sentence))
             (sub-phrase (cdr sentence) key)))
        (else (sub-phrase (cdr sentence) key))))

(define (is-front phrase sentence)
  (cond ((null? phrase) t)
        ((null? sentence) '())
        ((equal? (car phrase) (car sentence))
         (is-front (cdr phrase) (cdr sentence)))
        (else '())))

(define conventional-wisdom
  (list
   (make-entry
    '(6:001)
    '(6:001 is too much work for freshmen -- wait until next year))
   (make-entry
    '(8:01 physics)
    '(students really enjoy 8:01))
   (make-entry
    '(seminar seminars)
    '(i hear that snorkeling in Boston Harbor is a really exciting seminar))
   (make-entry
    '((major in course 6) (major in computer science))
    '(course 6 is too crowded -- find something else))
   (make-entry
    '((major in course 14) (major in aero-astro))
    '(no one could possible want to take unified))
   (make-entry
    '((double major))
    '(forget it.  too much work.)
    '(are you absolutely sure you want to do that?))
   ))
\end{verbatim}

The functions here implement a system which matches whole strings, not just
words.  The function \verb+find-response+ takes a list of entries and a 
list of input words.  It then makes a list of all the responses generated
when each rule is applied to the entire input by calling mapcar on the list
of entries with \verb+lookup+ as the action.  \verb+lookup+ takes a list
of input words (a sentence), a list of keys, and the value which should be
returned if any keys are found in the string.  The function just applies
\verb+in-sentence+ to each word or list of words (phrase) in the key list.
\verb+in-sentence+checks to see if the key it is passed is a word or a list.
If it is a word, \verb+member+ is called to see if it is in the string.  If it
is a phrase, then \verb+sub-phrase+ is called to determine if the phrase is
in the sentence.  \verb+sub-phrase+ checks several things in order to determine
if the phrase is in the sentence.  If the phrase is \verb+'()+, then it is
definitely in the sentence.  This state is really just and end-state for the
recursion.  If the sentence is \verb+'()+, then the phrase is not in the
sentence.  This is also a recursion end-state.  If the first words of the
sentence and the phrase are the same, then the phrase is a sub-phrase if
either the rest of the phrase is at the front of the sentence, or if
the entire phrase is found somewhere else in the sentence.  Otherwise, the
phrase is in the sentence if it is found past the first word.  The last
function is \verb+is-front+, which simply makes sure that the phrase is
at the front of the sentence.  The algorithm is similar to \verb+sub-phrase+,
except the first words must always match in each successive call.  The
rest of the sentence is not checked.

\bv
(see-advisor 'marc)
(HI MARC) 
(I AM YOUR FRESHMAN ADVISOR) 
(WHAT ARE YOUR PLANS FOR THE SEMESTER) 
**(I want to double major in course 6 and major in aero-astro)
(COURSE 6 IS TOO CROWDED -- FIND SOMETHING ELSE) 
**(I want to double major in course 6 and major in aero-astro)
(NO ONE COULD POSSIBLE WANT TO TAKE UNIFIED) 
**(I want to double major in course 6 and major in aero-astro)
(NO ONE COULD POSSIBLE WANT TO TAKE UNIFIED) 
**(I want to double major in course 6 and major in aero-astro)
(NO ONE COULD POSSIBLE WANT TO TAKE UNIFIED) 
**(I want to double major in course 6 and major in aero-astro)
(COURSE 6 IS TOO CROWDED -- FIND SOMETHING ELSE) 
**(I want to double major in course 6 and major in aero-astro)
(FORGET IT. TOO MUCH WORK.) 
**(I want to double major in course 6 and major in aero-astro)
(COURSE 6 IS TOO CROWDED -- FIND SOMETHING ELSE) 
**(i have come to the conclusion that the random number algorithm is not very good)
(HAVE YOU CONSIDERED A CONTEXT SUBJECT) 
**(context subjects don't teach probability.  Does 6:002)
(I AM GLAD TO HEAR THAT CONTEXT SUBJECTS DON 'T TEACH PROBABILITY. DOES 6:002) 
**(context subjects don't teach probability.  Does 18:03)
(YOU HAVE TO TAKE 18:02 FIRST) 
**(goodbye)
(GOODBYE MARC) 
(HAVE A GOOD SEMESTER!)
\end{verbatim}
\part{4: On your own}
In this section, I extend the phrase algorithm to include wildcards.  That
is, if a \verb+?+ appears in the phrase, then it will match exactly one 
word, whatever it is.  A \verb+*+ will match any series of words, including
no words at all.  In addition, by placing a list of the form
\verb+(variable n)+ in the response, the wildcard can be substituted in
the answer.

\bv
(define (find-response entries input)
  (let ((possible-responses
         (filter (lambda (val) (not (null? val)))
                 (mapcar (lambda (x) (lookup (entry-keys x) input (entry-value x)))
                         entries))))
    (if (null? possible-responses)
        '()
        (pick-random possible-responses))))

(define (lookup keys sentence value)
  (cond ((null? keys) '())
        ((match-whole-key (car keys) sentence)
         (replace value (variables (car keys) sentence)))
        (else (lookup (cdr keys) sentence value))))

(define (match-whole-key key sentence)
  (if (symbol? key)
      (match-key key sentence)
      (match-key (cons '* key) sentence)))

(define (match-key key sentence)
  (cond ((null? key) t)
        ((null? sentence) '())
        ((symbol? key) (member key sentence))
        ((eq? (car key) '?) (match-? (cdr key) sentence))
        ((eq? (car key) '*) (match-* (cdr key) sentence))
        ((eq? (car key) (car sentence)) (match-key (cdr key) (cdr sentence)))
        (else '())))

(define (match-* key sentence)
  (define (scan-for word sentence)
    (cond ((null? sentence) '())
          ((eq? word (car sentence)) sentence)
          (else (scan-for word (cdr sentence)))))
  (cond ((null? key) t)
        ((null? sentence) '())
        (else (let ((after-* (scan-for (car key) sentence)))
                (cond ((null? after-*) '())
                      ((match-key key after-*) t)
                      ((match-* key (cdr after-*)) t)
                      (else '()))))))

(define (match-? key sentence)
  (if (null? sentence)
      '()
      (match-key key (cdr sentence))))

(define (variables key sentence)
  (if (symbol? key)
      '()
      (merge-vars (vars-key (cons '* key) sentence '()))))

(define (vars-key key sentence vars)
  (cond ((null? key) vars)
        ((null? sentence) vars)
        ((eq? (car key) '?) (vars-? (cdr key) sentence vars))
        ((eq? (car key) '*) (vars-* (cdr key) sentence vars))
        ((eq? (car key) (car sentence))
         (vars-key (cdr key) (cdr sentence) vars))
        (else vars)))

(define (vars-* key sentence vars)
  (define (scan-for word sentence)
    (cond ((null? sentence) '())
          ((eq? word (car sentence)) sentence)
          (else (scan-for word (cdr sentence)))))
  (define (scan-for-var word sentence this-var)
    (cond ((null? sentence) '())
          ((eq? word (car sentence)) this-var)
          (else (scan-for-var word (cdr sentence)
                              (add-to-list this-var (car sentence))))))
  (cond ((null? key) '())
        ((null? sentence) vars)
        (else (let ((after-* (scan-for (car key) sentence))
                    (this-var (scan-for-var (car key) sentence '())))
                (cond ((null? after-*) '())
                      ((match-key key after-*)
                       (vars-key key after-* (add-to-list vars this-var)))
                      ((match-* key (cdr after-*))
                       (vars-* key (cdr after-*)
                               (add-2-to-list vars this-var (car after-*)))))))))

(define (vars-? key sentence vars)
  (if (null? sentence)
      vars
      (vars-key key (cdr sentence) (add-to-list vars (list (car sentence))))))

(define (merge-vars vars)
  (cond ((null? vars) '())
        ((null? (cdr vars)) vars)
        ((symbol? (cadr vars))
         (merge-vars (cons (append (car vars) (list (cadr vars)) (caddr vars)) 
                           (cdddr vars))))
        (else (cons (car vars) (merge-vars (cdr vars))))))

(define (replace sentence vars)
  (if (null? sentence)
      '()
      (append (if (list? (car sentence))
                  (get-variable (cadar sentence) vars)
                  (list (car sentence)))
              (replace (cdr sentence) vars))))

(define (get-variable num vars)
  (list-ref vars num))

(define (add-to-list lst item)
  (append lst (list item)))

(define (add-2-to-list lst item1 item2)
  (append lst (list item1) (list item2)))

(define conventional-wisdom
  (list
   (make-entry
    '(6:001)
    '(6:001 is too much work for freshmen -- wait until next year))
   (make-entry
    '(8:01 physics)
    '(students really enjoy 8:01))
   (make-entry
    '(seminar seminars)
    '(i hear that snorkeling in Boston Harbor is a really exciting seminar))
   (make-entry
    '((major in course 6) (major in computer science))
    '(course 6 is too crowded -- find something else))
   (make-entry
    '((major in course 14) (major in aero-astro))
    '(no one could possible want to take unified))
   (make-entry
    '((double major))
    '(forget it.  too much work.)
    '(are you absolutely sure you want to do that?))
   (make-entry
    '((major in course ? and course ?))
    '(thats too much work, but you can try majoring in either course
            (variable 1) or course (variable 2) and course 21))
   (make-entry
    '((take ? or ?))
    '((variable 1) and (variable 2) are both excellent courses))
   (make-entry
    '((is * a good course for a course ? major))
    '(there is no reason why a course (variable 2) major should take (variable 1)))
   ))


(see-advisor 'marc)
(HI MARC) 
(I AM YOUR FRESHMAN ADVISOR) 
(WHAT ARE YOUR PLANS FOR THE SEMESTER) 
**(i want to major in course 5 and course 16)
(THATS TOO MUCH WORK, BUT YOU CAN TRY MAJORING IN EITHER COURSE 5 OR COURSE 16 AND COURSE 21) 
**(do I have to take 5:11 or 8:02)
(5:11 AND 8:02 ARE BOTH EXCELLENT COURSES) 
**(is a physics course a good course for a course 6 major)
(THERE IS NO REASON WHY A COURSE 6 MAJOR SHOULD TAKE A PHYSICS COURSE) 
**(goodbye)
(GOODBYE MARC) 
(HAVE A GOOD SEMESTER!) 
\end{verbatim}

\hspace{0.3 in}The functions to implement the wildcards are split into two 
groups.  The first group determine if a phrase is present in the sentence,
and the second group parse the variables out of the sentence if it
matches.  The function \verb+match-whole-key+ simply calls
\verb+match-key+ with the key if the key is a word.  Otherwise, a
\verb+*+ is prepended to the key to allow the algorithm to match on
the key anywhere in the sentence.  The most complex function in the
group is \verb+match-*+.  This scans down the sentence for the the
first word after the wildcard in the sentence.  If the word is
found, the function checks the rest of the sentence against the
rest of the key to make sure that the key matches.  If the key does
not match the rest of the sentence, then the rest of the sentence is
repetitively scanned for the word after the \verb+*+ to see if there
are any other matches.  This is repeated until a match is found
or until the end of the sentence is reached.

\hspace{0.3 in}The second group of functions closely parallel the
first group.  Each adds one parameter to the end of the list which acts
as an iterative variable.  When the end of the sentence is reached, this
variable is the list of wildcard substitutions from the sentence.  The
only other function which needs explanation is \verb+merge-vars+.  This
function scans the variable list for any member which is not a list in
itself and merges it with the two variables around it.  This is necessary
because if the word after a \verb+*+ matches the key in an appearance
after the first, then it is lost from the iterative variable which scans
the sentence (in \verb+scan-for-var+).  To get around this, the extra
word is added to the variable list and merged in later.
\end{document}
