| You can combine facts, rules, and lists into logic programs that solve complex problems. Rules add much more power and complexity to a logic program than facts do. A program with ten rules may take an hour or more for a human reader to comprehend. A well-written logic program may be much harder to understand than a well-written Java program. In part, this is because most developers have more experience with procedural programming elements than with recursive programming. It may also be that recursive programming is simply harder to comprehend than procedural programming. 13.12.1 An Authorization Program Here is a program that models privileges in a semiconductor fabrication facility: priv(jim, operate, sputter); priv(jim, operate, implant); priv(janie, supervise, sputter); priv(rivki, operate, photo); priv(bill, supervise, photo); teammates(P1, P2) :- priv(P1, _, Machine), priv(P2, _, Machine), !=(P1, P2); The priv facts in this program allow various queries about which person the program authorizes to perform which operations on which machine. The teammates rule finds people who can work on the same machine. For example, the query teammates(jim, T) produces the results T = janie no You encounter a problem if you ask for all teammates with the query teammates(P1, P2) This query produces these results: P1 = jim, P2 = janie P1 = janie, P2 = jim P1 = rivki, P2 = bill P1 = bill, P2 = rivki no The problem is that the results show every pair twice. You can address this problem by adding a comparison to the query: teammates(P1, P2), <(P1, P2) Now the query asks to see only teammates with the workers' names in alphabetical order: P1 = janie, P2 = jim P1 = bill, P2 = rivki no If you think this is a common query, you can add it to the program as a rule: orderedTeammates(P1, P2) :- teammates(P1, P2), <(P1, P2); Storing a useful query as a rule is an effective approach to building a logic program iteratively. As you add rules, you should reexamine how the rules interact. For example, the orderedTeammates rule will force a not-equals comparison followed by a less-than comparison. You might accept this inefficiency, but it is important to create collections of rules that work together to form a complete logical model. 13.12.2 Epidemic An epidemic occurs when a problem is transmitted through contact between objects. The word usually applies to human disease, but it also applies to computer viruses and may apply to factory problems. For example, semiconductor fabs often fire many wafers together in a single run of an oven. If a wafer emits a contaminant that sticks to other wafers, those wafers may go on to contaminate any other wafers that future firings expose them to. A common example of an epidemic is the spread of a kissing disease through a high school. Imagine that a local epidemiologist (perhaps the principal) has traced an outbreak of symptoms to a single infected person and a lot of kissing. The following program models the epidemic: kiss(jill, james, 0321); kiss(julian, jill, 0405); kiss(jill, jasper, 0412); kiss(james, jenni, 0420); kiss(julian, judy, 0508); kiss(jed, judy, 0614); kissed(Student1, Student2, Date) :- kiss(Student1, Student2, Date); kissed(Student1, Student2, Date) :- kiss(Student2, Student1, Date); infected(julian, 0307); exposed(Student, Date) :- infected(Student, Date1), >(Date, Date1); exposed(Student2, Date2) :- kissed(Student2, Student1, Date1), >(Date2, Date1), exposed(Student1, Date1); This program models kissing as a symmetric relation, so the fact kiss(jill, james, 0321); implies both that Jill kissed James and that James kissed Jill. The date format records this event as occurring on March 21. The program models the symmetric nature of kissing with the kissed rules: kissed(Student1, Student2, Date) :- kiss(Student1, Student2, Date); kissed(Student1, Student2, Date) :- kiss(Student2, Student1, Date); The program notes that Julian is known to have been infected as of March 7: infected(julian, 0307); The first exposed rule says a that student counts as having been exposed on a given date if he or she is known to have been infected before that date: exposed(Student, Date) :- infected(Student, Date1), >(Date, Date1); The second exposed rule says that a student was exposed on a given date if the student has kissed another student on a prior date, and if the other student had been exposed at the time. exposed(Student2, Date2) :- kissed(Student2, Student1, Date1), >(Date2, Date1), exposed(Student1, Date1); If it is now June 15, the epidemiologist can enter the query exposed(Student, 0615) with the results Student = julian Student = jed Student = jill Student = jasper Student = judy no Note that James has been spared because his kiss with Jill preceded her kiss with the infected Julian. His luck spread to Jenni, who kissed James after the onset of the epidemic but happened to kiss an unexposed student. All other students have been exposed, and that is not surprising because this was, after all, an epidemic. 13.12.3 Generate and Test Some problems have many possible solutions, along with a way to score or validate the strength of each solution. For example, a basketball coach might consider all possible starting lineups against a known lineup of the competing coach's team. If the coach can model a matchup based on height, skill, and other factors, he or she can compare every possible permutation of a starting lineup to find the best match. In other cases, each permutation may be either acceptable or unacceptable. Logic puzzles, for example, typically have only one acceptable answer. Consider the following problem: Each of four martial arts students has a different specialty. From the following clues, can you determine each student's full name and her special skill? -
Ms. Ellis (whose instructor is Mr. Caldwell), Amy, and Ms. Fowler are all martial arts students. -
Sparring isn't the specialty of either Carla or Dianne. -
Neither the shoot fighting expert nor the pressure point fighter is named Fowler. -
Children's techniques aren't the specialty of Dianne (whose instructor is Ms. Sherman). -
Amy, who disdains pressure point fighting, isn't Ms. Goodrich. -
Betti and Ms. Fowler are roommates. -
Ms. Hightower avoids sparring because of its point scoring nature. To solve this problem with a logic program, you must generate all permutations of first-name/last-name/specialty and verify each permutation against the clues. The following program achieves this: // karate.txt geneval(Solution) :- generate(Solution), evaluate(Solution); // generate all possible solutions select(X, [X Rest], Rest); select(X, [Y Rest1], [Y Rest2]) :- select(X, Rest1, Rest2); permutation(InList, [H OutRest]) :- select(H, InList, InOther), permutation(InOther, OutRest); permutation([], []); generate(Solution) :- permutation( [ellis, fowler, goodrich, hightower], LastNames), permutation( [sparring, shootFighting, pressurePoints, childrens], Specialties), associate( [amy, betti, carla, dianne], LastNames, Specialties, Solution); // "associate" combines three lists into one list of // students with three attributes associate( [FirstName Frest], [LastName Lrest], [Specialty Srest], [student(FirstName, LastName, Specialty) StudentsRest]) :- associate( Frest, Lrest, Srest, StudentsRest); associate([], [], [], []); // "evaluate" takes a list of "student" structures, and // succeeds if all the criteria are met. member(X, [X Rest]); member(X, [Y Rest]) :- member(X, Rest); evaluate(Solution) :- // Clue 1 not member(student(amy, ellis, _), Solution), not member(student(amy, fowler, _), Solution), // Clue 2 not member(student(carla, _, sparring), Solution), not member(student(dianne, _, sparring), Solution), // Clue 3 not member(student(_, fowler, shootFighting), Solution), not member(student(_, fowler, pressurePoints), Solution), // Clue 4 not member(student(dianne, _, childrens), Solution), // Clue 5 not member(student(amy, goodrich, _), Solution), not member(student(amy, _, pressurePoints), Solution), // Clue 6 not member(student(betti, fowler, _), Solution), // Clue 7 not member(student(_, hightower, sparring), Solution), // Clue 4, 1 not member(student(dianne, ellis, _), Solution); The program generates permutations of each of three lists, containing first names, last names, and karate specialties. The generate rule associates these three lists by building a list of student structures that contains a student's first name, last name, and specialty. The Solution variable contains a prospective solution ”namely, a list of student structures. The evaluate rule checks to see whether a prospective solution runs afoul of any of the clues. The geneval rule early in the program generates and evaluates all possible solutions. Querying this rule with geneval(Solution) produces the output Solution = [student(amy, hightower, shootFighting), student(betti, ellis, sparring), student(carla, fowler, childrens), student(dianne, goodrich, pressurePoints)] This is the only solution that passes the gauntlet of clues. Amy Hightower is the shoot fighting expert; Betti Ellis is the sparring specialist; Carla Fowler's forte is children's techniques, and Dianne Goodrich concentrates on pressure points. 13.12.4 Generate and Test in Java The solution to the karate puzzle is complex, in part because of the inherent complexity of the problem, and in part because of the complexity of logic programming in Logikus. The package sjm.examples.karate solves the karate puzzle using Java. It uses classes from sjm.combinatorics , which has utilities for generating permutations. If you compare the Logikus and Java solutions, you may find that one or the other seems more straightforward. A key question is whether logic puzzles are more easily solved in a logic language than in an object-oriented language. Of course, the Logikus solution is a Java solution in that Logikus is built from Java. 13.12.5 Altitude Bands Suppose that you want to visit a collection of cities in order of their elevation so that you can gradually acclimatize to the deficiency of oxygen at higher altitudes. To establish your itinerary you want to iterate over ranges, or bands of altitude, finding the cities in each band . Here is a general algorithm for iteration: for(X, X, Upper) :- <= (X, Upper); for(X, Lower, Upper) :- <(Lower, Upper), #(LowerPlusOne, Lower + 1), for(X, LowerPlusOne, Upper); If you enter these rules as a Logikus program and enter the query for(X, 1, 20) the Results area will display X = 1.0 X = 2.0 X = 3.0 // ... X = 19.0 X = 20.0 no When the query first proves itself, it unifies with the first rule, which causes X to unify with 1 . The first rule can prove itself only once, so when the query wants a second proof, it unifies with the second rule. When the query unifies with the second rule, the variable Lower unifies with 1 and the variable Upper unifies with 20 . To prove itself, the rule first verifies that Lower is less than Upper . The rule then uses an evaluation that unifies LowerPlusOne with the value of Lower + 1 . Here the evaluation is effectively an assignment because LowerPlusOne is unbound when the evaluation begins. The rule then looks for a proof of for(X, 2, 20) . This structure finds the first rule in the program and unifies X with 2 . The flow of the proof continues until the lower bound is no longer less than the upper bound. You can incorporate a version of the "for" algorithm in a program that increments altitudes by 1,000 feet to find cities sorted by altitude band: // travel.txt city(abilene, 1718); city("addis ababa", 8000); city(denver, 5280); city(flagstaff, 6970); city(jacksonville, 8); city(leadville, 10200); city(madrid, 1305); city(richmond, 19); city(spokane, 1909); city(wichita, 1305); highCity(Name) :- city(Name, Alt), >(Alt, 5000); for(I, I, Upper) :- <= (I, Upper); for(I, Lower, Upper) :- <(Lower, Upper), #(LowerPlus, Lower + 1000), for(I, LowerPlus, Upper); travel(AltBand, Name) :- for (AltBand, 1000, 20000), city(Name, Alt), >(Alt, AltBand - 1000), <= (Alt, AltBand); Querying this program with travel(AltBand, X) prints AltBand = 1000.0, X = jacksonville AltBand = 1000.0, X = richmond AltBand = 2000.0, X = abilene AltBand = 2000.0, X = madrid AltBand = 2000.0, X = spokane AltBand = 2000.0, X = wichita AltBand = 6000.0, X = denver AltBand = 7000.0, X = flagstaff AltBand = 8000.0, X = addis ababa AltBand = 11000.0, X = leadville no |
