Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Re: Rules-based Perl?

by Masem (Monsignor)
on Apr 11, 2001 at 17:53 UTC ( #71661=note: print w/replies, xml ) Need Help??

in reply to Rules-based Perl?

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 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 - || "You've left the lens cap of your mind on again, Pinky" - The Brain

Replies are listed 'Best First'.
Re (tilly) 2: Rules-based Perl?
by tilly (Archbishop) on Apr 12, 2001 at 05:06 UTC
    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.
Re: Re: Rules-based Perl?
by Brovnik (Hermit) on Jun 26, 2001 at 12:53 UTC
    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.
      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 - || "You've left the lens cap of your mind on again, Pinky" - The Brain
        I haven't seen any statement of purpose yet (or in XP jargon "Users stories").

        Are you expecting the knowledge engineer (the person writing a rules base) to be a programmer ? A Perl programmer ?

        What degree of complexitiy of (real-world) problem do you expect to be able to solve ?

        For a user, a table isn't a complex concept, but inputing it might be unless the system is designed to cope at the beginning. Writing a rule such as (in my pseudo code) :

        [ID in (A B C)] => [D = rows from TABLE_D where KEY=ID]

        could be difficult otherwise.

        Re. The rule efficiency, you are right, this is the hard part.
        To some extent the responsibility lies with the knowledge engineer (read ruleset creator), since you can write bad (==slow) programs/algorithms in any language.

        Giving the engineer tools (such as the priority / weighting mechanism you mention can help, as can other options such as choice of search mechanism and direction.

        In my experience, a lot of knowledge engineer time is spent tuning the knowledge base, and the system should be proactive in helping that process, providing timing / coverage analysis.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://71661]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (4)
As of 2021-12-04 17:03 GMT
Find Nodes?
    Voting Booth?
    R or B?

    Results (30 votes). Check out past polls.