Just another Perl shrine | |
PerlMonks |
Adjacency List Processing Continued + Expert System Discussionby princepawn (Parson) |
on Aug 20, 2001 at 02:09 UTC ( [id://106089]=perlmeditation: print w/replies, xml ) | Need Help?? |
This post continues with the earlier post in which I
determined which cities were right next to a particular
city. Concretely, we determined that palo alto and
atherton were adjacent to menlo park.
This post extends that post in 2 ways. First, we create a slightly harder problem so that we can see some more XML::Twig code. Then I engage in a long-winded tangent about Perl and problem-solving engines. Now we want to find which cities are 2-away from menlo park. Or put another way, those which are adjacent to palo alto and atherton. In our case, we want to omit backtracking on our path. So even though menlo park is in fact 2-away from menlo park (just go to atherton and come back), we will omit these cases. Here is a program which solves this problem:
If you followed the first program, then this one should really require no explanation other than an analysis of the efficiency of our means of calculating 2-away cities: Because we map() then grep(), we are doing what is known as generate-and-test: we create a bunch of candidates and then later filter them out based on a criteria. a new Twig API function: delete()But since generate and test is wasteful, let's take at another more efficient way of writing the source code starting from the comment Here is the new stuff:
So here we prune the XML-tree of the records which were 1-away from our target city and then our candidate generator can only generate the correct candidates. But actually this change in the program is more than just efficient. We can simply run this loop N times when we want to find the cities which are N+1 hops away. But this is the beauty of using this approach, we can cut away the search space with a single call to delete(). We could also do all sorts of other funky things with our tree just as easily... Expert systems: A Completely Different Idea on Solving this Problemnote: there is some more Perl from this point out, but no more on XML::Twig so you can quit reading now if long-winded philosophy on problem solving and software engineering is not your bag.So far, I have tackled this problem the Perl way - I dove right in and didn't quit coding until I was done. However, I would like to propose another way to handle this problem, and that way is what is known as forward-chaining. A very old, very stable forward-chaining rules-based system is CLIPS. Forward chaining is where you start with a set of facts and then you build a bunch of rules which fire if their preconditions meet some of the facts on the stack. Typically when these rules fire, they assert new facts and retract some old ones. And then some other rules notice these new asserted facts on the stack and then go through the same assert/retract cycle until finally some rule notices that you have reached your goal and announces it and terminates the program. This is opposite of a backward-chaining system like Prolog, where you start with your goal and attempt to find rules which match the goal and search for facts with satisfy these rules. Architecture of CLIPSIt seems that for any problem domain, decoupling this from that seems to provide great benefits at some point. For CLIPS, time has shown that decoupling a problem solver into the following things works well:
The big win with this type of program is that you don't have to run map() or grep() as I have been doing but instead simply code up a bunch of program-state-recognizers. Also, you never have to write the rule selector. But all in all, until something like that shows its necessity I will just keep solving problems in the most intuitive way possible. ConclusionI think it is high-time for me to quit trying to integrate rules-based programming into Perl. Rules systems have means of making statements about objects. Perl has means of creating objects which can be used in a call-by-contract fashion for the same result but simply a different means of expressing it.Edit: chipmunk 2001-08-20
Back to
Meditations
|
|