Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Rules-based Perl?

by Masem (Monsignor)
on Apr 10, 2001 at 17:13 UTC ( [id://71319]=perlmeditation: print w/replies, xml ) Need Help??

Beyond the two typical programming architectures, procedural and object-oriented, there is a third type typically called rules-oriented. In such a program, the state of the program is represented by a "cloud" of facts. Operations are initized when facts matching certain requirements exist within the "cloud" as defined by rules; these rules, when initiated, can remove the matched facts completely from the complete, or add new facts, in addition to other less mundane tasks. For example, the following 'program' describes how one would prepare a meal and clean up afterwards:
Rule 1 - Clean-Up: Given 1: ( dirty-dishes ) Do Remove fact 1 add fact ( clean-dishes ) Rule 2 - Prepare-Food: Given 1: ( clean-dishes ) 2: ( raw-food ?foodtype ) Do Remove fact 1, fact 2 add fact ( cooked-food ?foodtype ) add fact ( dirty-dishes ) Rule 3 - Serve-Food Given 1: ( clean-dishes ) 2: ( cooked-food ?foodtype ) Do Remove fact 1, fact 2 add fact ( dirty-dishes )
If this code was then executed with the initial facts "( dirty-dishes )" and "( raw-food beef )", the following would happen:
Start                  ( dirty-dishes ) ( raw-food beef )
Clean-Up               ( clean-dishes ) ( raw-food beef )
Prepare-Food           ( dirty-dishes ) ( cooked-food beef )
Clean-Up               ( clean-dishes ) ( cooked-food beef )
Serve-Food             ( dirty-dishes )
Clean-Up               ( clean-dishes )
While a simple example, rules-based programming is very powerful when it comes to AI-like systems, including expert systems and fuzzy logic. For example, I worked out a symbolic differentiation system given any equation (typed out specifically) back when I was in high school using a rules-based system.

Currently the only langauge that I'm aware that does rules-based stuff is CLIPS, which you can get for free; the only caveat is that CLIPS 'functionality' outside of the rules matching is weak beyond simply print and file IO statements. I'm wondering if anyone has seen anything like this for perl yet; a check of CPAN shows nothing, and a google search doesn't turn up concrete answers. Mixing perl into a rules language may make it much more powerful than it seems. For example, having the ability to put any sort of perl code in the "Do" blocks of the prototypes above, or even more powerful, allow regex expersions to help with the fact matching in the "Given" blocks.

Because I don't see anything like this yet, I figure that this would be a good project to attempt after I get done with my current updating project. But as I don't want to reinvent the wheel, I'd figure I'd ask to see if anyone knew of such a beast to start with.


Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

Replies are listed 'Best First'.
Re: Rules-based Perl?
by knobunc (Pilgrim) on Apr 10, 2001 at 17:21 UTC

    You may want to look at Language::Prolog on CPAN. Prolog is another of the rules based languages. I have never used this module so I am not sure how well it is integrated with Perl. Prolog itself is pretty good if you can twist your head around the rules-based stuff (which it looks like you already know).

    -ben

      I've been learning to use Prolog in the last 2 weeks and yes, it's quite different to use rules based languages. You are right, you have to be able to twist your head around to understand rules-based stuff! Great food program btw, i'll use it next time i try some chicken recipes :)
Re: Rules-based Perl?
by zigster (Hermit) on Apr 10, 2001 at 17:35 UTC
    The difference is imperative based programming vs functional programming. C/C++/perl/java are imperative, prolog miranda ASL (lisp at a push) (scheme at a push) are functional or rule based as you call them. Do web searches for functional and you will find NUFF info

    I must confess I could never get my head around functional programming languages although I can certainly see the benifits.

    A quick web search turns up the following links

    Hope these links are of use to you.
    --

    Zigster
Re: Rules-based Perl?
by princepawn (Parson) on Apr 10, 2001 at 23:33 UTC
    Well, with Data::Flow, which I maintain, you use rules (or as Ilya calls them, recipies), to define, how hash keys are generated.

    One important thing I would like to see out of any such efforts in Perl is that the rules should be invertable. For example, if you go through a series of steps to turn input into output, then given the output, you should be able to chain backwards and re-generate the input.

    The language currently compiling on my macosx ibook right now is the language used to place 4th in the International Conference on Functional Programming Contest. It is both logical and functional and is called Mercury It has a short tutorial and I think you will find it's description appealing. Both first and second place were taken by CAML (from inria.fr --- I lost interest in this langauge when I saw it was not purely functional or logical but also contained imperative elements.) And 3rd place was taken by a team working in Haskell a purely functional language.

    Also, Perl 6 is planned to have additional functional capability. And finally, what you have above is known as an Agenda design pattern and was described in the article "Design Patterns" in The Perl Journal a few issues before it's first crucifixion (TPJ will rise from the dead right?!)

Re: Rules-based Perl?
by larsen (Parson) on Apr 11, 2001 at 00:38 UTC
    knobunc's reply is good. Check Language::Prolog As far as I know, it is currently a beta version.
    But, if you want to "reinvent the wheel", you should consider reading something on the following topics:
    • Propositional logic
    • Predicate logic
    • Herbrand's Theory
    • Godel-Herbrand-Skolen Theorem
    • Resolution and Robinson's Algorithm
    • Horn Clause Programs
    • Prolog
    You can check them in that order :)
    Logic programming slogan "I tell you what I know and what I'd like to know, without telling you how" showed its practical unapplicability over the years: every logic programming language includes extralogic operators, such as cut, that introduce elements of imperative programming in the language ("I tell you what I know and what I'd like to know, without telling you how... Well, I will help you a bit").
    Despite of their impure nature, logic programming languages are very interesting and I think they're worth studying.

      If you want to reinvent the wheel here, start by reading through Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig. It has working code examples on what you want. Especially relevant are chapters 6 (Tools), 11 and 12 (Logic Programming and Prolog Compiler), and 16 (Expert Systems). It should not be too hard to pull out the code you need from this book.

      Christian Lemburg
      Brainbench MVP for Perl
      http://www.brainbench.com

Re: Rules-based Perl?
by Masem (Monsignor) on Apr 11, 2001 at 17:53 UTC
    Ok, I've read some of the links provided by the kind monks on thread for functional languages, and while I'm still wrapping my head around some of these (Haskill seemed interesting at least from the most descriptive of functional programming), it seems to me that these don't quite capture what I was looking for. So hopefully a little enlightment would help here.

    The key of a rules-based system as I learned it (back in high-school, so please be aware that this is rusty!) is that there is no definitive progression of events through a system, unlike typical procedural or OO programming (and, what seems to me to be the same as functionaly programming). The rules as defined above trigger 'instantly' when the Given sides are matched by facts in the 'cloud'; rules can be given a numerical priority, but for rules of the same priority, the one that fires should be random if both Givens are successfully matched. While in most instances of rules-based programming, the initial state of that cloud is fixed, and thus one can follow how rules fire and facts appear and disappear, a most robust rules-based system would allow facts to appear at any time in the cloud (say from a client-server like interaction), and thus the progression would be difficult to monitor, much more like debugging some GUI elements.

    As I'm reading this functional programming features, it feels more like they handle data in an abstract a way as possible to avoid evaluation until the last possible moment, thus allowing 'infinite' lists to exist within a few bytes of memory (As an example, the Functional.pm module has an example of calculating the first 10 primes starting from the infinite set of integers).

    Mind you, with CLIPS, the operations part of each rule used a functional-like language to print out, store, or do other things with data. (part of CLIPS' name came from the resemblence to LISP). Certainly, if I were to work on developing this for perl, I'd include those functional elements in the abilities of the package. Also, it would not be hard to maintain a history of facts as princepawn suggests, given that as facts are 'deleted' they go to a 'fact heaven' with ties to what rule deleted them as well as what facts it birthed.


    Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
      Indeed and agreed. Why I like functional programming talked a little bit about the differences. There I called your rules-based programming "Logical programming". But it clearly is not the same as functional.
      Apologies if i get a bit misty-eyed in the middle, this is a subject dear to me.

      My first job involved writing an expert system in VAX Pascal.

      It used a list-oriented code/data structures that could be easily serialised for fast store/load.

      My main role was writing the search engine part. Initially, we worked hard to build a 'proper' depth-first and breadth-first search engines, but found over time that often, only one rule could fire, or a few independent rules could fire. In these cases, a lot of time and effort was wasted in the 'proper' search mechanisms, and the best (=fastest) way to the result was a combined approach which executed as many independent rules as possible at each stage.

      The problem areas were the usual with these sorts of languages, namely Input. You want to minimise the number of questions asked, but what if you backtrack over a question already asked ? Do you ask it again, because the context (to the user) might be different in a different search order. The system also allowed backward-chaining rules if that resulted (as it did sometimes) in a faster result.

      P.S. The result was IMHO pretty good. It was used for designing telephone exchanges, which had a certain number of constraints, e.g "given that we want 100 trunk lines and 1000 subscriber lines, how do we layout the exchange in this room ?" Constraints/Rules included trying to make sure units with lots of interconnections were placed close together.

      Summary of key issues:

      1. You can write a rules-based system in some surprising languages.
      2. Input/Output of code/results needs careful design.
      3. Handling of input of data/questions needs care.
      4. The 'proper' searches are often less efficient than more intuitive searches for many real-world operations.
      5. Multiple control-schemes(search-engines) are needed for different problems.
      6. Some real-world problems are best solved by rules-based systems !
      Hope that provides some food for thought.
      --
      Brovnik
        Pretty much, the way I plan to develop this is as follows:
        • Develop the basic Rules/Fact classes and the like. This will start by using simple code blocks as the criteria units, but eventually will use things like Array::PatternMatcher that princepawn posted recently. (I've been talking to him on more details). The rules system would currently be explicitly defined in perl and would require perl calls to start it going.
        • Develop a way to test the rules system by simply iterating over all possible rules/facts until a rule is fired.
        • Develop a way to cache facts vs rules such that the above step is more efficient
        • Build up a standalone text format that can be used to simply have a perl-based rules system but without using any perl code to initiate it.
        • Modify the system from there.
        My current thoughts is that the key data item, facts, are only arrays; they may be arrays of mixed data, or just scalars, but they are arrays. Of course, from the practical understanding of a rules-system, you shouldn't be using very complex data structures in any case, as you can always alter them to be replaced by multiple facts, but I want to leave that open in case someone wants to take the concept to advanced levels. The only time that data is introduced to the system would be by facts; while perl input can be used to generate data, the data would go out of scope at the end of the rule unless specifically put into a fact and stored away. Standard perl output can be used for any other generation, while backend stuff can be directed to another file (ie which rules have fired, with which facts, etc).

        The trickiest part, for me, is making the rule triggering more efficient. Rules will have two values associated with them: priority (higher priority rules will trigger first) and probability (rules of the same priority and that all can be triggered at the current step; probability will select a random rule from this to trigger). These could change as the rules are fired, though this can lead to bad rule-based systems. In addition, some criteria for rules are dynamic, for example in my pseudo code...:

        rule find-max 1:( value ?id1 ?X ) 2!( value ?id2:{ ?id2 != ?id1 } ?Y:{ ?Y > ?X } ) => etc...
        That is, the first criteria takes a rule that matches the format of "value <id> <number>". The second is a negative criteria; this is, we don't want any rule where a different ID has a larger number. Now, to check this, one must take all N facts, and do N^2 checks with the criteria (though it can be assumed that this might be closer to 0.5 * N^2, since once a fact denies the second criteria, the first rule obvious cannot match. In small cases (few rules & facts) this isn't bad, but it won't scale well to larger systems. I'd like to have a side strucutre that notes when facts match the criteria of rules in order to improve this efficiency; this is easily done for the first criteria of the example above but the second step may still require O(N^2) checks. In general, for N rules with an average of K criteria per rule, and M facts, the system scales as N*(M^K), and any possible reduction of this would help.

        At this point, I've mostly got ideas, and it's a matter of implementing things in a perl-ish way (eg transferring variables from matched rules to the 'body' of the rule).


        Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
Re: Rules-based Perl?
by MeowChow (Vicar) on May 10, 2001 at 22:05 UTC
Re: Rules-based Perl?
by Anonymous Monk on Apr 10, 2001 at 23:24 UTC
    What about make? TMTOWTDI, you know.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://71319]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (7)
As of 2024-03-28 08:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found