[HN Gopher] Rete algorithm
___________________________________________________________________
Rete algorithm
Author : skilled
Score : 160 points
Date : 2024-05-26 07:03 UTC (1 days ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| skilled wrote:
| Some other links,
|
| _The Rete Matching Algorithm_
| (https://news.ycombinator.com/item?id=11364718) - Mar 2016 (21
| comments)
|
| _Project Area52_ (http://phrack.org/issues/56/6.html)
| nmadden wrote:
| I did some work with Rete for my undergraduate dissertation. One
| thing I remember about the original paper is that it defines the
| algorithm in terms of a kind of virtual machine, where specific
| instructions implement the matching process. I've never seen
| anyone implement it that way.
| jll29 wrote:
| I cannot comment on this for "it = Rete", but virtual machine-
| like models for matching are not that un-common, from PROLOG
| (WAM = Warren Abstract Machine) to regular expressions.
| Stretching things slightly, SQLite's SQL engine also
| technically is a byte-code interpreter of a DSL VM.
| kredens wrote:
| Besides DROOLS, what other production-ready rule-based-engine
| options are there?
| fermigier wrote:
| Here a small collection:
|
| - https://github.com/nemonik/Intellect (Dead - 2017)
|
| - https://github.com/jruizgit/rules (dead)
|
| - https://github.com/cmaclell/py_rete (dead)
|
| - https://github.com/nilp0inter/experta (dead)
|
| - https://github.com/GNaive/naive-rete (dead)
|
| (All of them are rule engine - I guess they implement the Rete
| algo or some variant but no time to check ATM).
|
| Also: "production" is probably false since all of them are dead
| (or were, last time I checked - I'd be happy to be proven
| wrong).
| fermigier wrote:
| My best bet would be CLIPS: https://www.clipsrules.net/ (which
| has a Python integration, among others).
| c1sc0 wrote:
| I'm using CLIPS + Python for a kind of Neuro-Symbolic system,
| kind of an old-school expert system for a specific (small)
| domain blended with an LLM. Coincidence I see this here.
| felixyz wrote:
| Clara is a good one.
|
| http://www.clara-rules.org/
|
| Self-plug: my interview with its original author.
| https://thesearch.space/episodes/2-ryan-brush-on-retaking-ru...
| mdaniel wrote:
| Interestingly https://github.com/cerner/clara-rules redirects
| to https://github.com/oracle-samples/clara-rules so I'd guess
| Cerner was acquired by Oracle, although the repo is Apache 2
| and doesn't seem to have any weird stuff in their
| contributing.md
|
| For me, the "It's just Clojure" part is a drawback, not only
| for me personally but when I think about the kind of
| audiences that I have traditionally wanted to author rules,
| between a real, lisp-y, dynamically-typed, programming
| language and asking folks to write in the Drools DSLs, I'll
| take my chances with the DSLs
| zokier wrote:
| IBM has full stack of various rule-based stuff, e.g.
| https://www.ibm.com/docs/en/odm/8.12.0?topic=modes-reteplus-...
| maho wrote:
| I really like nools, which is a drools clone, but for
| JavaScript. It's fantastic for quick hacks and for getting to
| know how to write code for rule engines.
|
| Sadly, it is no longer maintained.
| rch wrote:
| I've been experimenting with Evrete:
|
| https://www.evrete.org/
|
| It's a little strange, but very flexible. I'd like to try
| adapting it to evaluate rules specified using annotated Kotlin.
| sixdimensional wrote:
| Commercial offering that's been around a long time - InRule
| [1].
|
| I don't have any affiliation with them, it was considered for a
| project I worked on in 2005.
|
| [1] https://inrule.com/
| dmofp wrote:
| FICO makes one. It's called Blaze Advisor and it's used heavily
| in multiple sectors.
| lunatuna wrote:
| Worked with a rete engine in Tibco's CEP. This was used for
| utility events and deciding what if anything to be done with
| the event in the context of others and then route it. I've seen
| it similarly used with bank security and customer management.
| Another interesting use case was using it as a master data
| management platform for customer data across a company with a
| bunch of subsidiaries that had the same customers.
|
| What we liked about it was the ability to contextualize events
| by keeping a history and relationship between objects and
| events that we could reference as part of our rules.
| Particularly when we get an event storm and putting more signal
| into situational awareness when there is a lot of noise.
| amelius wrote:
| Could this help to speed up CSS rules?
| exabrial wrote:
| Actually... that would be a fascinating application. RETE works
| best when all of the facts and rules known are presented up
| front (versus human thinking, which we are trained from
| kindergarten to follow flow charts and decision trees).
| ryjo wrote:
| I've been studying Rete for the past few years, and I've been
| working exclusively in CLIPS for the past year, a programming
| language that uses the Rete Algorithm at it's core. It's a very
| clever algorithm, and provides a lot of "nice features" that
| developers find themselves re-implementing in mature code bases.
| Things like:
|
| - pattern matching - custom DSL - caching
|
| I find it difficult to summarize in an "elevator pitch," and I
| only started seeing things fall into place after trying to use it
| in earnest on my own. I highly recommend reading the CLIPS
| documentation posted on the main CLIPS website. The PDFs are
| long, but quite complete and well written.
|
| Self promotion: If you prefer something a little more
| interactive, check out the Tour of CLIPS I made:
| https://ryjo.codes/tour-of-clips.html
|
| Just a heads up: this is not light reading. Rules-based
| programming is a confusing departure from traditional
| programming; there's more "magic" involved, similar to
| convention-over-configutation in other languages/frameworks. The
| benefits outweigh the upfront learning cost, though.
|
| Here is a recent post on HN that recently got some traction and
| has some pretty good discussions: Tour of CLIPS (2022) -
| https://news.ycombinator.com/item?id=40201729
|
| If anyone is working directly with CLIPS, let me know! I'm
| actively working on a low level networking library called
| CLIPSockets, and would like to work with the language full time
| some day.
| aduitsis wrote:
| Hey! I was using CLIPS in my network management PhD work, but
| life happened and I was absorbed by my profession. Maybe one
| day I'll dig up the half finished material and continue, who
| knows.
|
| CLIPS is one of those definitely underrated gems, many many
| thanks for what you are doing!
| ryjo wrote:
| Fantastic. Thanks for chiming in!
| bollu wrote:
| I have a very well documented implementation of rete, that also
| produces nice looking SVGs of the state of the rete algorithm
| here: https://github.com/bollu/rete
|
| It's a really interesting algorithm, and allows one to get O(1)
| incremental pattern matching (ie, when one adds a pattern, one is
| told of a matching pattern in O(1) time) at the cost of
| O(npattern * nitems) memory usage. I was trying to use it in the
| context of pattern matching within a compiler, but I never went
| anywhere since I had COVID, then a PhD to get to :)
| mark_l_watson wrote:
| Wow, that is so cool! I love the diagrams showing the internal
| state.
| graycat wrote:
| The RETE algorithm was the core of IBM's rule-based language
| YES/LI.
| olivierduval wrote:
| Nota: some extension/generalization of Rete includes
|
| - TREAT
|
| - GATOR
| anonymousDan wrote:
| Yeah from what I recall RETE can be quite memory intensive in
| that it keeps the results of any intermediate rule computations
| that result from changing inputs in memory, in the hope that it
| will speed up answering subsequent queries (similar to how you
| might want to incrementally update a materialized view).
| Subsequent algorithms explored trading off memory consumption
| for query latency (amongst other differences).
| mark_l_watson wrote:
| The coolest thing I ever did with the Rete algorithm was to hack
| OPS5 to support spawning multiple working memories (or data
| worlds).
|
| I have a funny history with OPS5. When my company bought me a
| Xerox 1108 Lisp Machine in 1982, converting OPS5 to run on
| InterLisp-D and adding a nice UI was my first project. I also
| ported it to the Mac in 1984 (ExperOPS5), and one weekend I
| converted Charles Forgy's original Common Lisp code to MIT
| Scheme.
| chc4 wrote:
| This just seems like a very specific way of implementing tree
| matching? Top-down graph matching instruction selection
| implementations look a lot like this if you squint (apply labels
| to child nodes, then have rules that fire on simple trees of
| labels, which gives you structural sharing of rules) but without
| the multiple explicit node types and specifying exactly a linked
| list and things. It being so specific to the implementation and
| not a high level overview of what the algorithm is trying to do
| is kinda weird and make it hard to understand, honestly.
| photonthug wrote:
| I was mostly imagining legacy banking systems are the main use-
| cases for stuff like this, and was a little surprised to see
| Apache adopted Drools in 2023[1].
|
| In case anyone might be able to answer..
|
| What are some of the biggest rule systems deployed in the wild,
| and are any of them recent? Since it seems like this is mostly
| about first order logic.. do any of these rule-engines actually
| out perform all the modern work on SMT solvers and other theorem-
| provers? Same question for this more probabilistic Rete-OO
| flavor.. isn't there already some faster and more generic engine
| available that handles this kind of thing as a special case?
|
| [1] https://en.wikipedia.org/wiki/Drools#Drools_in_Apache_Kie [2]
| https://en.wikipedia.org/wiki/Rete_algorithm#Rete-OO
| belter wrote:
| Rules engines are massively used in Credit Scoring, Claims
| Processing and Insurance Policy Writing. That is not where you
| would use a SMT Solver.
|
| You have plenty of business cases here by FICO, the market
| leader: https://www.fico.com/en/customers
|
| Also IBM is pretty strong in this area:
| https://www.ibm.com/products/operational-decision-manager
| 7373737373 wrote:
| I'm pretty sure the part of the Magic the Gathering game engine
| that implements the card rules uses something like it:
| https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-n...
| wisemang wrote:
| Not recent but the cybersecurity company Rapid7 uses a Java
| implementation called JESS (Java Expert System Shell) within
| their vulnerability management product to help determine
| vulnerable / unpatched state of scanned assets.
|
| https://www.rapid7.com/blog/post/2013/11/01/vulnerability-ma...
| dmofp wrote:
| The Rete algorithm is at the core of FICO's commercial rule
| engine (Blaze Advisor) and Blaze Advisor is used heavily in
| Insurance, Finance, Tax / Revenue Management etc.
|
| More than a decade after i used it last, recruiters still
| randomly call out of the blue for short to medium term
| contracts using Blaze Advisor.
| nanolith wrote:
| Early in my career, I wrote a LEAPS based rules engine for
| managing business rules when deciding how to pack orders into
| boxes across multiple warehouses. As part of it, I also wrote a
| heuristic for approximating solutions to the 3-dimensional bin
| packing problem, along with a visualizer for solutions as the
| warehouse staff did not believe that certain pack orders could
| "fit".
|
| Among other things, the rules engine would ensure that bowling
| balls wouldn't be packed in with ceramic dolls, or that goods
| that could be dangerous if spilled and mixed wouldn't be packed
| together. Overall, a very fun project for a young programmer.
|
| https://www.cs.utexas.edu/ftp/predator/tr-94-28.pdf
| verdverm wrote:
| This reminds me of the CUE evaluator, which has its roots in
| LinGo and the data structures / algos for efficiently
| representing / evaluating linguistic rules for old-style (pre NN)
| NLP systems. I believe it is more like Typed Feature Structures
| now, though it is evolving into something different since the
| target language is not a human language or doesn't involve
| probabilities
| whartung wrote:
| One of the coolest applications of Rete out there in the wild
| right now is that they have a Rete engine built in to Apache
| Jena, which operates on RDF. (I do not believe its unique to
| Jena, inference seems to be part of the whole RDF ontology schema
| thing.)
|
| So, now your knowledge base is RDF nodes.
|
| I have not yet had a chance to play with it myself, but when I
| was playing with RDF and turned down that corridor in surprise:
| "Oh my, what. have. we. here!"
|
| I think it's pretty neat.
| fmeyer wrote:
| Despite modern advancements in ML, rules engines are still
| preferred in some scenarios as their execution tends to be
| deterministic.
|
| They have different heuristics for conflict resolution when more
| than one rule can be fired. Once you define the strategy, it will
| be consistent throughout the entire lifecycle.
|
| Once the network is compiled, it ensures that previously matched
| patterns are not recomputed, which increases performance.
| mrdoops wrote:
| Yeah modern ML is not really at all comparable and they're more
| complementary than modern approaches replacing rules. All these
| agent frameworks and platforms cropping up will be using things
| like rules, workflow DAG models and so on as the execution
| engine with LLMs embedded as steps and/or to construct a
| workflow.
|
| Likewise either with knowledge graphs or using LLMs to generate
| possible predicates and constraints to run against a rule
| engine or backwards chain through facts is a way to minimize
| hallucinations of generative models.
| whartung wrote:
| The other big question regarding Rete is, today, at what point is
| the complexity of the algorithm worth the performance.
|
| A primary goal of Rete is to narrow the rule set to be applied
| based on changes in the working memory. Quite important if you
| have a large rule set over a more naive, perhaps brute force,
| approach of apply rules.
|
| But modern machines are pretty stupid fast, and when operating on
| very slow hardware of the day, Rete was very important. Today, I
| don't know. Or, simply, that the use cases perhaps narrow
| particularly for smaller rule sets.
|
| "Here's a bunch of rules (say, anonymous JS functions). Run each
| one against this working set (which is little more than a fancy
| map). If any of the members of the map change, do it again."
|
| Cheap hack 2B. Register with each rule what variables its
| interested in: addRule(['weight', 'height'],
| function(map) { var w = map.get("weight"); var h =
| map.get("height"); var bmi = w / (h * h); map.put("bmi", bmi);
| }); addRule(['bmi'], function(map) { var bmi =
| map.get("bmi"); if (bmi > 30) { map.put("weight_status",
| "obese"); } });
|
| (No, this isn't a rule development environment. Yes, rule engines
| can be very complicated, and rule interaction, precedence, etc.
| are a Thing. This is a trivial example, doesn't mean it's not
| potentially useful for some scenarios however.)
| Sniffnoy wrote:
| Where does the name come from?
| bazzargh wrote:
| it's named after anatomical structures with the name "rete"
| (which is just latin for net, but Forgy meant specifically that
| kind of structure). eg
| https://en.wikipedia.org/wiki/Rete_mirabile
|
| Source: via Forgy himself, see
| https://www.youtube.com/watch?v=BUw-67B_qA4#t=4m30s (the video
| and the blog that goes along with it are really annoying in
| holding out the explanation until the end)
| dang wrote:
| Recent and Rete-related:
|
| _Tour of CLIPS (2022)_ -
| https://news.ycombinator.com/item?id=40201729 - April 2024 (41
| comments, with more links at
| https://news.ycombinator.com/item?id=40213716)
|
| Also:
|
| _Rust rule matching engine (Rete algorithm) (2020)_ -
| https://news.ycombinator.com/item?id=37649161 - Sept 2023 (2
| comments)
|
| _The Rete Matching Algorithm (2002)_ -
| https://news.ycombinator.com/item?id=11364718 - March 2016 (21
| comments)
| szarnyasg wrote:
| I used Rete in my PhD work, where I designed incremental view
| maintenance techniques for the openCypher graph query language
| (https://szarnyasg.github.io/phd/szarnyasg-phd-
| dissertation.p...).
|
| Rete is an elegant algorithm that is also quite flexible: one can
| make non-distributive aggregations, outer joins and recursive
| traversal work. However, it is quite memory-hungry due to the
| large state of certain nodes (e.g., join operators). I tried to
| work around this by using distributed execution, but that made
| the system very inefficient and complex to operate. I also looked
| into the TREAT algorithm but found that it is more limited in its
| functionality than Rete.
|
| For incremental view maintenance, the state of the art has now
| moved on to techniques such as differential dataflow or DBSP
| (https://www.vldb.org/pvldb/vol16/p1601-budiu.pdf).
| mrdoops wrote:
| My research went in similar directions although I was looking
| at RETE for rule evaluation as part of a general purpose
| workflow engine with rules as just one part.
|
| Incremental view maintenance is different enough from rule
| composition and evaluation that the model diverges to be more
| optimal. Collections of tuples and instead of DAGs lots of
| cyclical loops to continue computation of the diffs.
|
| There are deep and intrinsic space or time trade offs so many
| of the modern approaches moved toward natural dataflow
| concurrency, and streaming semantics where space or time trade
| offs can be chosen at runtime through batching and data context
| opposed to early RETE variations which were very OOP and
| eagerly evaluated instead of lazy (all in memory in the same
| place instantiated and mutated).
|
| It'll be interesting to see where these differential dataflow
| approaches go as we head into local-first constraints where
| central authority on data isn't possible and long divergence of
| synchronization occurs. Lots of CRDTs in this future for sure.
| E.g. https://github.com/RhizomeDB/rs-rhizome /
| https://fission.codes/blog/fission-reactor-dialog-first-look...
___________________________________________________________________
(page generated 2024-05-27 23:01 UTC)