6.001, Fall 2007—Recitation 21 — 11/21/2007 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall 2007Recitation 21 — 11/21/2007Logic Programming: Query LanguageQuery LanguageThe evaluator for the query language, qeval, has different operations than the evaluators we’veseen before. There are two main types of operations: assertions, and queries:• Assertions add statements to the database of statements known to be true. Assertions caneither be simple assertions such as:(assert! (address (Bitdiddle Ben) (Slumerville (Ridge Road) 10)))Or they can be compound rule statements which has the form:(assert! (rule hconcli hqueryi))Which means, if the query matches, then add a n ew assertion which consists of concl withany variables filled in. Rules can apply recursively (though we’ll later go into examples ofwhere this can lead to problems).The simple assertions in the SICP example are on the last page.• QueriesQueries also come in simple and compound forms. A simple query with no variables such as(salary (Bitdiddle Ben) 60000) would either find that record if that statement is in thedatabase, or not if it isn’t.Variables can match any value, so (salary ?x ?y) would return a list of all the salary recordsfor all employees.Compound queries such as(and hquery1i hquery2i)(or hquery1i hquery2i)find the intersection or union of the corresponding simple queries.not acts as a filter, removing any records where a query matches.A final special form, lisp-value takes a predicate and applies it to a set of values, forexample, all employees with salary between 30000 and 50000 would be:(and (salary ?p ?x)(lisp-value >= ?x 30000)(lisp-value <= ?x 50000))6.001, Fall 2007—Recitation 21 — 11/21/2007 2Problems1. Define a rule that says that pers on 1 can replace person 2 if either person 1 does the samejob as person 2 or s omeone who does person 1’s job can also do person 2’s job, and if person1 and person 2 are not the same person. (ex. 4.57 from SICP)Using your rule, give queries that fi nd the following:(a) All people wh o can replace Cy D. Fect;(b) All people wh o can replace someone who is being paid more than they are.2. Define a rule th at says that a person is a “big shot” in a division if the person works in thedivision but does not have a supervisor who works in the division. (ex 4.58 from SICP)6.001, Fall 2007—Recitation 21 — 11/21/2007 3Infinite Loops3. Consider the following definitions.(assert! (married Minnie Mickey))(married Mickey ?who)(assert! (rule (married ?x ?y)(married ?y ?x)))(married Mickey ?who)The first call to married will r eturn nothing. The second will go into an infinite loop. Why?4. O ne of the following definitions for outranked-by works, and the other goes into an infiniteloop. Find the difference and explain why:(rule (outranked-by ?staff-person ?boss)(or (supervisor ?staff-person ?boss)(and (supervisor ?staff-person ?middle-manager)(outranked-by ?middle-manager ?boss))))(rule (outranked-by ?staff-person ?boss)(or (supervisor ?staff-person ?boss)(and (outranked-by ?middle-manager ?boss)(supervisor ?staff-person ?middle-manager))))6.001, Fall 2007—Recitation 21 — 11/21/2007 4Example assertionsThese are the examples from Section 4.4.1 of SICP. To use these in the qeval evaluator, each ofthese would be wrapped with inside a call to assert!, but those are not shown(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))(job (Bitdiddle Ben) (computer wizard))(salary (Bitdiddle Ben) 60000)(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78))(job (Hacker Alyssa P) (computer programmer))(salary (Hacker Alyssa P) 40000)(supervisor (Hacker Alyssa P) (Bitdiddle Ben))(address (Fect Cy D) (Cambridge (Ames Street) 3))(job (Fect Cy D) (computer programmer))(salary (Fect Cy D) 35000)(supervisor (Fect Cy D) (Bitdiddle Ben))(address (Tweakit Lem E) (Boston (Bay State Road) 22))(job (Tweakit Lem E) (computer technician))(salary (Tweakit Lem E) 25000)(supervisor (Tweakit Lem E) (Bitdiddle Ben))(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78))(job (Hacker Alyssa P) (computer programmer))(salary (Hacker Alyssa P) 40000)(supervisor (Hacker Alyssa P) (Bitdiddle Ben))(address (Fect Cy D) (Cambridge (Ames Street) 3))(job (Fect Cy D) (computer programmer))(salary (Fect Cy D) 35000)(supervisor (Fect Cy D) (Bitdiddle Ben))(address (Tweakit Lem E) (Boston (Bay State Road) 22))(job (Tweakit Lem E) (computer technician))(salary (Tweakit Lem E) 25000)(supervisor (Tweakit Lem E) (Bitdiddle Ben))(address (Reasoner Louis) (Slumerville (Pine Tree Road) 80))(job (Reasoner Louis) (computer programmer trainee))(salary (Reasoner Louis) 30000)(supervisor (Reasoner Louis) (Hacker Alyssa P))(supervisor (Bitdiddle Ben) (Warbucks Oliver))(address (Warbucks Oliver) (Swellesley (Top Heap Road)))(job (Warbucks Oliver) (administration big wheel))(salary (Warbucks Oliver) 150000)(address (Scrooge Eben) (Weston (Shady Lane) 10))(job (Scrooge Eben) (accounting chief accountant))(salary (Scrooge Eben) 75000)(supervisor (Scrooge Eben) (Warbucks Oliver))(address (Cratchet Robert) (Allston (N Harvard Street) 16))(job (Cratchet Robert) (accounting scrivener))(salary (Cratchet Robert) 18000)(supervisor (Cratchet Robert) (Scrooge Eben))(address (Aull DeWitt) (Slumerville (Onion Square) 5))(job (Aull DeWitt) (administration secretary))(salary (Aull DeWitt) 25000)(supervisor (Aull DeWitt) (Warbucks Oliver))(can-do-job (computer wizard) (computer programmer))(can-do-job (computer wizard) (computer technician))(can-do-job (computer programmer)(computer programmer trainee))(can-do-job (administration secretary)(administration big
View Full Document
Unlocking...