-
Notifications
You must be signed in to change notification settings - Fork 42
Introduction to Ruleby
Good programming depends on selecting the right tool for the job. In most cases imperative languages like Ruby, Java and C++ are good solutions. But they are not perfect. This article will present some of these cases and introduce a new tool that improves one imperative language: Ruby.
Imperative programming often results in complex code with a myriad of state transitions and interdependencies. Edgar Dijkstra noted that this can lead to programmers relying on the execution of a program in order to understand it. Debuggers are a nice tool, but it’s unfortunate that we require one to write our programs.
As an example where imperative languages fail, consider a system that performs some data validation. The program would consist of a number of IF-THEN statements that parse the data. If the rules are complex enough, the program can turn into “spaghetti code” where there are too many nested IF-THEN statements.
if firstname && lastname
if type == :group
if groupname
...
end
elsif type == :individual
...
end
end
It does not take long before the rules of validation grow, and there are hundreds of conditional statements. In addition to the code becoming messy and difficult to maintain, it will also be inefficient. This is because every time the data changes, the entire series of IF-THEN statements must be execute again.
There are alternatives to imperative languages for situations like this. Functional languages like Prolog or Lisp are excellent tools for tasks like data validation and parsing. But it is rarely an option to rewrite your entire application in a functional language. It is also a bad idea if it solves only one requirement.
Let us say, for example, that the data validation system described above is part of a web application written in Ruby and running on Rails. Wouldn’t it be nice to mix in some methods to declaratively program the validation rules’ That’s what Ruleby does.
Ruleby is an open source rule engine written in the Ruby language. It is used to derive answers from a knowledge base. For example, it could answer the question of “Is this data valid?” The knowledge base then would contain the rules that define how valid data looks.
It can be said that rules are to a rule engine as instructions are to a procedural language. In a rule engine, the computation is data-driven. The rules communicate with each other by way of data. This is opposed to an imperative language where procedures and functions explicitly call each other.
So a rule engine is comprised of three parts:
- Facts :: This is the data. It is known as the “working memory.”
- Rules :: the IF-THEN statements that define what valid data looks like
- Inference Engine :: an efficient mechanism for executing the rules against the facts
The Inference Engine in Ruleby is an implementation of the Rete algorithm. This is a forward chaining algorithm for matching patterns to objects. It was developed by Charles Forgy in his seminal paper Rete: a fast algorithm for the many pattern/many object pattern match problem.
Ruleby provides an internal Domain Specific Language (DSL) for building rules and asserting facts. The internal DSL is built on top of the Ruby language, and takes advantage of the various language features Ruby provides.
This internal DSL is in contrast to the external DSL’s provided by most rule engines. External DSL’s are built from scratch and require a compiler or interpreter. Ruby has become a popular General Purpose Language (GPL) for creating DSL’s. This is due in part to its easy readability and concise syntax.
Here is an example of a production rule in Ruleby (this example can be found in the Ruleby source code):
rule [Message, :m, m.status == :HELLO] do |e,v|
puts v[:m].message
v[:m].message = "Goodbye world"
v[:m].status = :GOODBYE
e.modify v[:m]
end
In this example, an object of type
Message with a status of :HELLO must exist in the collection of facts. If such an object has been added to the working memory, then the “action” specified in the right-hand of this production rule will be fired.
Now let us demonstrate how this rule is used:
engine :hello_engine do |e|
HelloWorldRulebook.new(e).rules
assert e, Message.new(:HELLO, 'Hello World')
e.match
end
The “HelloWorld” rule is contained in the HelloWorldRulebook class (this is shown in the source code). To use it we create a new inference engine, a new rule set, and a new fact. The
assert method adds the fact to working memory.
When the match method is invoked, the action in the “HelloWorld” rule will be fired. And the system will output the following to the console:
Hello World
If we introduce a second rule to our rulebook, we can show how rules interact.
rule [Message, :m, m.status == :GOODBYE] do |e,v|
puts v[:m].message
end
When the
match method is called with this new rule, the output will be:
Hello World
Goodbye
Because the fact in working memory was modified by the action in the first rule, the “Goodbye” rule became satisfied.
The Ruleby project is dedicated to providing documentation and examples for its users. But aside from that, Ruleby already supports one standard benchmark: Miss Manners.
The Miss Manners benchmark, as described in Effects of Database Size on Rule System Performance: Five Case Studies [PDF], uses a depth-first search to determine the alternating seating arrangements of males and females with one common hobby.
This test ran well on Ruleby for 16 guests. However, as the number of guests increases to 32 and 64, the relative performance of the benchmark drops off. This is due to a hack/bug in the implementation of the Rete algorithm. This problem is described on the Open Issues page. The Ruleby developers have identified a solution to this problem, and are working to correct it.
Ruleby turns Ruby into a multi-paradigm programming language that provides support for rule-based, object-oriented and procedural programming. This is advantageous because is allows a programmer to select the best tool for any given problem. In this way we can follow Dr. Dijkstra’s advice and apply efficient structuring to otherwise intellectually unmanageable complexity.