Week 15 Discussion/Lab Notes

Administrivia

• Friday's lecture will be on Amar's research. I think it should be interesting, so I encourage everyone to attend.
• HKN will be conducting course evaluations this Friday. Please go an fill out an evaluation! (This is your last chance to tell me how much I suck.) If you can't make it, stop by the HKN office and ask them for a survey.
• I will hold review sessions on Saturday (May 13) and on Tuesday (May 16) from 8-10 pm in 306 Soda.
• Check your grades. Let me know as soon as possible of any mistakes.
• In the past, a lot of students started their dead days early and decided to skip HW15. I do not recommend this. Do HW15. This week's material is completely different from what we've done in the past, so you need to practice using the query system. Also, make sure you test your answers.
• No lab Monday.
• My office hours will be different during final exams.
• Want to know what Professor Hilfinger is like? Check out exercises 2.63 through 2.65 in the SICP.

Discussion Outline

• query system is a pattern matcher
• example
• wildcards in Unix or DOS
• all it does is look up facts in the database (or generates inferences from these facts)
• use assert! to add facts or rules
• rules
• (rule <conclusion> <premise>)
• recursive rules are like proofs by induction
• variable names
• variables in a query with the same name must match the same item
• variables with different names do not have to be different
• use (not (same ?x ?y)) to require difference
• unification
• the process of matching variables through inference
• example
• given (assert! (rule (same ?x ?x)))
  how can we match (same (a ?y c) (a b ?z))?
• basic implementation
• although you don't need to know the full details, have some idea about how the query system works
• streams of frames
• see lecture notes for details
• quirks of query system
• using assert!
• assertions are permanent. If you enter incorrect rules, you need to restart
• order of expressions can be important
• it's really easy to get into infinite loops
• try to limit search as much as possible early on
• using and and or to form compound queries
• order of queries can matter
• not is a filter
• order of rules can matter, depending on implementation
• rules are not procedures!
     (assert! (mother Jeanette James))
     (assert! (mother Kim Jeanette))
  
     (assert! (rule (grandmother ?elder ?younger)
                    (mother ?elder (mother ?younger)) )) ;; WRONG
  
     (assert! (rule (grandmother ?elder ?younger)
                    (and (mother ?elder ?mom)
                         (mother ?mom ?younger) ) ))
  
• examples
• duplicate
• is-list
• append
• last-pair
• addition
• multiplication (Fall 97 Final Q11)
• division (Fall 98 Final Q8)
• map

Read the lecture notes. I also recommend reading Wilson Cheung's old notes and Brian Denny's outline.