text:
User talk:Greenmanwitch~enwikibooks

Hi there. I've marked Searching For The Beginning for deletion because it doesn't fall within project scope. It will be deleted soon; if you want to move it to another wiki, now is the time to make a copy of the content. More useful info below:

Come introduce yourself at the new users page. If you have any questions, you can ask there or contact me personally. – Mike.lifeguard  | talk 20:01, 13 December 2007 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Greenmanwitch. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Greenmanwitch~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:15, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 05:00, 19 April 2015 (UTC)

title: User talk:Greenmanwitch~enwikibooks


text:
Cookbook:Sour Mix

Sour mix is a mixer used in many cocktails, notably the Long Island Iced Tea family. It is made from approximately equal parts lemon and/or lime juice and simple syrup and shaken vigorously with ice. This produces a pearly-white liquid with a pronounced flavour. Egg white may be added as a foaming agent, to improve the texture of the finished product. Pre-mixed versions are available and are in use in many bars—these typically consist of a powder which must be rehydrated by adding water prior to use.

One of the earliest known printed references to the word "cocktail" described a drink made from "Spirit of any kind, sugar, water and bitters". This is very similar to the drink that would these days be known as sours—a spirit or liqueur, shaken vigorously with ice, lemon juice and sugar.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Cookbook:Sour Mix


text: User talk:209.226.36.10

title: User talk:209.226.36.10


text: User talk:168.170.198.50

title: User talk:168.170.198.50


text: User talk:74.130.231.233

title: User talk:74.130.231.233


text:
User:Stan Shebs

Hi, I'm Stan Shebs, more info at w:en:User:Stan Shebs.

title: User:Stan Shebs


text:
User talk:Stan Shebs

Welcome!
Come introduce yourself at the new users page. If you have any questions, you can ask there or contact me personally.--Whiteknight (Page) (Talk) 20:26, 13 December 2007 (UTC)

title: User talk:Stan Shebs


text: User talk:216.57.41.86

title: User talk:216.57.41.86


text:
User talk:Storkk

Hi Storkk; thanks for requesting an import instead of just doing a copy-paste! More useful info below:

Come introduce yourself at the new users page. If you have any questions, you can ask there or contact me personally. – Mike.lifeguard  | talk 20:49, 13 December 2007 (UTC)

title: User talk:Storkk


text:
User:Kostatoronto3~enwikibooks

Check out my user page is at Wikipedia: Wikibook I'm writing: Student's Guide to Michel Foucault

Kostatoronto3(Talk) 21:05, 13 December 2007 (UTC)

title: User:Kostatoronto3~enwikibooks


text:
Cookbook:Cuisine of Newfoundland

| Canadian Cuisine

The island of Newfoundland has very distinct cuisine, often stemming from its trading with the rest of the world during its prosperous fishing seasons.

title: Cookbook:Cuisine of Newfoundland


text:
User talk:Kostatoronto3~enwikibooks

Feel free to leave me messages on my Wikipedia talk page:

Kostatoronto3(Talk) 21:06, 13 December 2007 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Kostatoronto3. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Kostatoronto3~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:20, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 05:10, 19 April 2015 (UTC)

title: User talk:Kostatoronto3~enwikibooks


text: User talk:142.162.219.125

title: User talk:142.162.219.125


text:
User:Mercunis~enwikibooks

Hi, this is George

title: User:Mercunis~enwikibooks


text:
Talk:Greek Mythology/Heroes/Achilles

Why not use the article from Wikipedia?

 * Good question. If you think the WP article would make a good starting point for this page, you can request that a copy of it be imported. Of course, Wikibooks isn't an encyclopedia, nor collections of encyclopedia articles, so significant formatting work would have to be done to the article to make it suitable for inclusion here. However, if you think it's worth the effort, let us know. --Whiteknight (Page) (Talk) 23:21, 13 December 2007 (UTC)

 * Whiteknight, I could give you a better answer if I knew what age range we are targeting with this book. Obviously we would not present to an elementary school audience facts that would be approrpiate for an high school audience. Haiduc (talk) 13:09, 14 December 2007 (UTC)

title: Talk:Greek Mythology/Heroes/Achilles


text:
Talk:Chess Opening Theory/1. e4/1...a6/2. d4/2...b5/3. c4/3...Bb7

What about Qc2 ?at least it is protecting the e4 pawn.140.77.128.52 (talk) 23:13, 13 December 2007 (UTC)


text:
User talk:Haiduc

Welcome!
Come introduce yourself at the new users page. If you have any questions, you can ask there or contact me personally.--Whiteknight (Page) (Talk) 23:19, 13 December 2007 (UTC)

title: User talk:Haiduc


text:
User talk:Mercunis~enwikibooks

Welcome!
Come introduce yourself at the new users page. If you have any questions, you can ask there or contact me personally.--Whiteknight (Page) (Talk) 23:21, 13 December 2007 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Mercunis. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Mercunis~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:29, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 05:15, 19 April 2015 (UTC)

title: User talk:Mercunis~enwikibooks


text:
User talk:Justin Voshell

Welcome!
Come introduce yourself at the new users page. If you have any questions, you can ask there or contact me personally.--Whiteknight (Page) (Talk) 23:22, 13 December 2007 (UTC)

title: User talk:Justin Voshell


text:
User talk:Josh the Nerd

Welcome!
Come introduce yourself at the new users page. If you have any questions, you can ask there or contact me personally.--Whiteknight (Page) (Talk) 23:22, 13 December 2007 (UTC)

title: User talk:Josh the Nerd


text:
Chess Opening Theory/1. e4/1...e5/2. f4/2...Bc5

= King's Gambit Declined= Black declines the gambit the so called "Classical" way by developing his king's bishop to c5. On c5, it prevents white from castling by having him to slow his tempo to shift the bishop or block its diagonal (for example, white will have to play Nc3 followed by Na4 or c3 followed by d4). Nevertheless, white gets a small advantage with correct play. The main replies to the Classical Variation include:

 * A very important note: White can't accept the pawn and play 3. fxe5??, because of 3...Qh4+! 4. g3 leading to the loss of a rook (attempting to hang onto the rook with 4. Ke2?? leads to 4...Qxe4#).
 * /3. Nf3/, is the most obvious option, preventing the queen from coming to h4 and readying fxe5. From here, black has multiple replies, including 3...d6 or 3...Nf6, from where, white can get ready to gain a tempo on the bishop via c3 then d4. 3...exf4?! is unsound because of 4. d4!, pushing the bishop out. The queen can't come to h4, so white gets an advantage due to the imposing center on d4 and e4. Note that after 4. d4, black can't play 4...Bb4+, because 5. c3! only strengthens white's center AND gains a tempo on the bishop.
 * 3. Bc4 looks good at first right, but is somewhat unsound after 3...d5! 4. Bxd5 Nf6 5. Nf3 Nxd5 6. exd5 e4 7. d4 Bb4+ 8. c3 exf3 9. cxb4 fxg2 10. Qe2+ Qe7 11. Qxe7+ Kxe7 12. Rg1 Bh3.

Theory table
.

1.e4 e5 2.f4 Bc5


text: User talk:190.58.101.127

title: User talk:190.58.101.127


text:
User:VSimonian/monobook.js

// // User:Lupin/popups.js /* document.write('');*/

document.write(''); } //

title: User:VSimonian/monobook.js


text:
User talk:72.139.101.157

Encyclopedic content doesn't belong at Wikibooks and will be deleted, per policy. Please review Wikibooks' project scope before contributing to new modules. – Mike.lifeguard  | talk 02:15, 14 December 2007 (UTC)

Welcome!
Welcome to Wikibooks, a collection of open-content textbooks! You don't have to log in to read or edit articles on Wikibooks, but creating an account is quick, free and non-intrusive, requires no personal information, and gives you many benefits, including:
 * The use of a username of your choice
 * The ability to view all your contributions via a "My contributions" link
 * Your own user page
 * Your own talk page which, if you choose, also allows users to send you messages without knowing your e-mail address
 * The use of your own personal watchlist to which you can add articles that interest you
 * The ability to rename pages.
 * The ability to upload images
 * The ability to customize the appearance and behavior of the website
 * The eligibility to become an administrator
 * The right to be heard in votes and elections
 * Your IP address will no longer be visible to other users.

We hope that you choose to become a Wikibookian and create an account. Feel free to ask me any questions you may have on my talk page. By the way, make sure to sign your posts and comments with four tildes (~~~~), which will let others know who left it.

– Mike.lifeguard  | talk 02:15, 14 December 2007 (UTC)

title: User talk:72.139.101.157


text: Wikibooks:Requests for deletion/Issue Guide


text:
Happiness/Music

Music is so naturally united with us that we cannot be free from it even if we so desired -Boethius

Music, like other forms of art, has more emotional value than the sound vibrations or paint strokes that make them.

As shown in many studies, music has countless benefits, including:
 * Increasing IQ
 * Increasing SAT scores
 * Getting into medical school
 * Helping stroke victims relearn how to speak
 * Improved emotional health
 * Reducing stress

title: Happiness/Music


text:
Template talk:No thanks

I Propose a minor change to the template
To:

This templates should be generic and intended to be minimal and easy to understand, the prosed change is minimal. It can lead not only to a better understanding but also will automatically increase the chance on promoting Wikibooks (if the user does fell that the content is important enough to seek authorization), altering not the intended message but providing a way to address the issue. I also changed the references to sources (as it was incomplete) except the Websites (since Wikibookians may think otherwise), probably someone could reword it better... If no objection arises I will make the change it in a few days. --Panic (talk) 02:54, 14 December 2007 (UTC)
 * Well the first problem is that we can't use "content which uses an unacceptable license" with permission - they have to license it appropriately, right? They can't just say "Yes, it is copyrighted, but I give you permission to use it on Wikibooks." That's not OK - it must be GFDL-compatible. I'm sure that's what you intended to mean, but this wording is currently incorrect. Something like this would be better: "... which uses an unacceptable license or is lacking one. You may want to ask the copyright holder(s) for permission to use the content here." This is both accurate and complete. Keep in mind that this is mostly used for egregious copyright violations where there is little to no doubt that they've just ripped it off some corporate website which would never give them permission. Since that's the case, I don't think we need to be overly concerned about covering all the bases like this; they can check out Media if they're interested. – Mike.lifeguard  | talk 03:03, 14 December 2007 (UTC)

 * Nope the license can be even against the GFDL but if the contributor gets permission from the copyright holder, it constitutes a relicense to you or to Wikimedia (the scope depends on how it is done).
 * They may relicense the work completely or grant you permission to user it (in any way or with limitations) or even limited to the place you intend to add the content to (it may not be limited to Wikibooks). (as for the details the copyright information here covers all that and the proposal I linked to is complete, even overstating the GFDL issue).
 * Well I don't think most do it in bad faith (and we shouldn't aim that low), most do it out of lack of information or misunderstanding of how copyrights work. Does this address your objections ? --Panic (talk) 03:17, 14 December 2007 (UTC)
 * Are you trying to say that things like "You can use it only on Wikibooks" or "You can use it for anything noncommercial" are ok? – Mike.lifeguard  | talk 03:21, 14 December 2007 (UTC)
 * For instance those would be valid limitations a copyright holder can impose (on use, to the publisher, in distribution, etc...), he doesn't have to write a long license to go about it, some licenses can even be only invoked and not aggregate, it all falls down to how the permission was given. In case of wikibooks it is required that they conform to the GFDL (the limitations if any). --Panic (talk) 03:27, 14 December 2007 (UTC)
 * Right, but they're not suitable for inclusion on Wikibooks. See here: "The text and images of Wikibooks are covered by the GNU Free Documentation License. Unless an item is covered by the same or a similar license, or is in the public domain, it cannot be used on Wikibooks. So you have to ask the copyright holder of the material to license it under GFDL."
 * So back to the original issue: We need content to be specifically GFDL-compatible for inclusion here (with exceptions that aren't relevant here). The most correct way to impart this would be to say "We can't accept copyrighted content unless it is licensed in a GFDL-compatible way" and then link to a description of what that is (ie Mike.lifeguard ''' | talk 03:32, 14 December 2007 (UTC)
 * Or see this – Mike.lifeguard  | talk 03:35, 14 December 2007 (UTC)

 * reset

Yup, but "unless it is licensed in a GFDL-compatible way" is equal to "unless it is given permission to be used in a GFDL-compatible way" (I didn't remove any reference to the GFDL on the template above). The link to the example request for authorization does address in high detail the GFDL and limitations we use on Wikibooks, a similar valid proposal (but not as informative to the other party would be, "DO you grant permission to use your work XPTO at Wikibooks on the work XPTO123", this is oversimplification but there is no deep need to explain the particular in so much detail for it to be valid. I think that the way the actual example is written can cause an increase on anxiety to the target, and requires a deeper understanding of the GFDL, trouble that most will not get into. But that is another matter. --Panic (talk) 03:43, 14 December 2007 (UTC) That last example is in error or badly phrased. Take for example the UNESCO case...  --Panic (talk) 03:45, 14 December 2007 (UTC)
 * OK; what you meant to say was correct then. Let's try this language on for size:
 * "Hello; welcome to Wikibooks! We welcome and appreciate your contributions, such as :, but we regretfully cannot accept copyrighted content which uses an unacceptable license (or is lacking one). This includes using content from most websites. You may wish to ask for appropriate permission from the copyright holders. For more information, please read Media. Thank you; happy editing!"
 * – Mike.lifeguard  | talk 04:02, 14 December 2007 (UTC)
 * Good enough for me, all I wanted was a reference to the "get permission and all will be fine" with the involved perks, turning a clearly negative or prohibitive into a surmountable wall. I'm fine with the change and did alter the proposal.  --Panic (talk) 04:34, 14 December 2007 (UTC)
 * Humm... "You may wish" can be simplified to simply "You may". Do you tag the page as a copyvio at the same time you post the template on the users talk page ? (Since it is missing a time limit or an need to address the subject in any way or whom to contact in particular.) --Panic (talk) 04:40, 14 December 2007 (UTC)
 * Done; time limit added. – Mike.lifeguard  | talk 04:55, 14 December 2007 (UTC)

Use
The tag may be use to obligate the provision of information regarding a works copyright license. PD works are considered out of copyright but still acceptable. This has more to do with what is tagged so I'm attempting to make this clear here. --Panic (discuss • contribs) 17:22, 7 April 2012 (UTC)

title: Template talk:No thanks


text: User talk:69.136.97.37

title: User talk:69.136.97.37


text:
Expert Systems/CLIPS

About CLIPS
CLIPS is a public-domain software tool for building expert systems. The name is an acronym for "C Language Integrated Production System." The syntax and name was inspired by Charles Forgy's OPS. The first versions of CLIPS were developed starting in 1985 at NASA-Johnson Space Center until the mid 1990s when the development group's responsibilities ceased to focus on expert system technology.

CLIPS is probably the most widely used expert system tool because it is fast, efficient and free. Although it is now in the public domain, it is still updated and supported by the original author, Gary Riley. CLIPS incorporates a complete object-oriented language "COOL" for writing expert systems. Though it is written in C, its interface more closely resembles that of the programming language LISP. Extensions can be written in C, and CLIPS can be called from C.

Like other expert system languages, CLIPS deals with rules and facts. Various facts can make a rule applicable. An applicable rule is then asserted. Facts and rules are created by first defining them, as shown below:

Descendants of the CLIPS language include Jess, Haley Eclipse (of Haley Systems -> RuleBurst ->Oracle), FuzzyCLIPS, EHSIS, and others.

title: Expert Systems/CLIPS


text:
Expert Systems/Jess

About Jess
Jess, a rule engine for the Java platform, is a superset of CLIPS, developed by Ernest Friedman-Hill of Sandia National Labs. It was first written in late 1995.

It provides rule-based programming suitable for automating an expert system, and is often referred to as an expert system shell. In recent years, intelligent agent systems have also developed, which depend on a similar capability.

Rather than a procedural paradigm, where a single program has a loop that is activated only one time, the declarative paradigm used by Jess continuously applies a collection of rules to a collection of facts by a process called pattern matching. Rules can modify the collection of facts, or they can execute any Java code.

Jess can be used to build Java servlets, EJBs, applets, and full applications that use knowledge in the form of declarative rules to draw conclusions and make inferences. Since many rules may match many inputs, there are few effective general purpose matching algorithms. The Jess rules engine uses the Rete algorithm.

While CLIPS is licensed as open source, Jess is not open source.

Example 1
Code examples:

Example 2
Sample code:

title: Expert Systems/Jess


text:
Expert Systems/Prolog

History
Prolog is a logic programming language. It is a general purpose language often associated with artificial intelligence and computational linguistics. It has a purely logical subset, called "pure Prolog", as well as a number of extralogical features.

It was created around 1972 by Alain Colmerauer with Philippe Roussel, based on Robert Kowalski's procedural interpretation of Horn clauses. It was motivated in part by the desire to reconcile the use of logic as a declarative knowledge representation language with the procedural representation of knowledge that was popular in North America in the late 1960s and early 1970s.

Much of the modern development of Prolog came from the impetus of the fifth generation computer systems project (FGCS), which developed a variant of Prolog named Kernel Language for its first operating system.

Pure Prolog was originally restricted to the use of a resolution theorem prover with Horn clauses of the form

 * H :- B1, …, Bn..

The application of the theorem-prover treats such clauses as procedures

 * to show/solve H, show/solve B1 and … and Bn.

Pure Prolog was soon extended, however, to include negation as failure, in which negative conditions of the form not(Bi) are shown by trying and failing to solve the corresponding positive conditions Bi.

Data types
Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms.

Example atoms are: x, blue, 'Some atom', and [].

Numbers can be floats or integers. Many Prolog implementations also provide unbounded integers and rational numbers.

Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms. A variable can become instantiated via unification. A single underscore (_) denotes an anonymous variable and means "any term".

A compound term has a functor and a number of arguments, which are again terms. The number of arguments is called the term's arity. (Atoms can be regarded as a special case of compound terms of arity zero.)

Examples for terms are f(a,b) and p(x,y,z). Some operators can be used in infix notation. For example, the terms +(a,b) and =(X,Y) can also be written as a+b and X=Y, respectively. Users can also declare arbitrary sequences of symbols as new infix or postfix operators to allow for domain-specific notations. The notation f/n is commonly used to denote a term with functor f and arity n.

Special cases of compound terms:

 * Lists are defined inductively: The atom [] is a list. A compound term with functor . (dot) and arity 2, whose second argument is a list, is itself a list. There exists special syntax for denoting lists: .(A, B) is equivalent to [A|B]. For example, the list .(1, .(2, .(3, []))) can also be written as [1,2,3].
 * Strings: A sequence of characters surrounded by quotes is equivalent to a list of (numeric) character codes, generally in the local character encoding or Unicode if the system supports Unicode.

Programming in Prolog
Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses, a Turing-complete subset of first-order predicate logic. There are two types of clauses: Facts and rules. A rule is of the form

Head :- Body.

and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which are called the rule's goals. The built-in predicate ,/2 denotes conjunction of goals, and ;/2 denotes disjunction. Conjunctions and disjunctions can only appear in the body, not in the head of a rule. Clauses with empty bodies are called facts. An example of a fact is:

cat(tom).

which is equivalent to the rule:

cat(tom) :- true.

The built-in predicate true/0 is always true.

Given above fact, one can ask:

is tom a cat?

?- cat(tom). Yes

what things are cats?

?- cat(X). X = tom

Due to the relational nature of many built-in predicates, they can typically be used in several directions. For example, length/2 can be used to determine the length of a list (length(List, L), given a list List) as well as to generate a list skeleton of a given length (length(X, 5)), and also to generate both list skeletons and their lengths together (length(X, L)). Similarly, append/3 can be used both to append two lists (<tt>append(ListA, ListB, X)</tt> given lists <tt>ListA</tt> and <tt>ListB</tt>) as well as to split a given list into parts (<tt>append(X, Y, List)</tt>, given a list <tt>List</tt>). For this reason, a comparatively small set of library predicates suffices for many Prolog programs. All predicates can also be used to perform unit tests: Queries can be embedded in programs and allow for automatic compile-time regression testing.

As a general purpose language, Prolog also provides various built-in predicates to perform routine activities like input/output, using graphics and otherwise communicating with the operating system. These predicates are not given a relational meaning and are only useful for the side-effects they exhibit on the system. For example, the predicate <tt>write/1</tt> displays a term on the screen.

Evaluation
Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a resolution refutation of the negated query. The resolution method used by Prolog is called SLD resolution. If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded. Operationally, Prolog's execution strategy can be thought of as a generalization of function calls in other languages, one difference being that multiple clause heads can match a given call. In that case, the system creates a choice-point, unifies the goal with the clause head of the first alternative, and continues with the goals of that first alternative. If any goal fails in the course of executing the program, all variable bindings that were made since the most recent choice-point was created are undone, and execution continues with the next alternative of that choice-point. This execution strategy is called chronological backtracking. For example:

sibling(X, Y)     :- parent_child(Z, X), parent_child(Z, Y). parent_child(X, Y) :- father_child(X, Y). parent_child(X, Y) :- mother_child(X, Y). mother_child(trude, sally). father_child(tom, sally). father_child(tom, erica). father_child(mike, tom).

This results in the following query being evaluated as true:

?- sibling(sally, erica). Yes

This is obtained as follows: Initially, the only matching clause-head for the query sibling(sally, erica) is the first one, so proving the query is equivalent to proving the body of that clause with the appropriate variable bindings in place, i.e., the conjunction (parent_child(Z,sally), parent_child(Z,erica)). The next goal to be proved is the leftmost one of this conjunction, i.e., parent_child(Z, sally). Two clause heads match this goal. The system creates a choice-point and tries the first alternative, whose body is father_child(Z, sally). This goal can be proved using the fact father_child(tom, sally), so the binding Z = tom is generated, and the next goal to be proved is the second part of the above conjunction: parent_child(tom, erica). Again, this can be proved by the corresponding fact. Since all goals could be proved, the query succeeds. Since the query contained no variables, no bindings are reported to the user. A query with variables, like:

?- father_child(Father, Child).

enumerates all valid answers on backtracking.

Notice that with the code as stated above, the query sibling(sally, sally) also succeeds (X = Y). One would insert additional goals to describe the relevant restrictions, if desired.

Loops and recursion
Iterative algorithms can be implemented by means of recursive predicates. Prolog systems typically implement a well-known optimization technique called tail call optimization (TCO) for deterministic predicates exhibiting tail recursion or, more generally, tail calls: A clause's stack frame is discarded before performing a call in a tail position. Therefore, deterministic tail-recursive predicates are executed with constant stack space, like loops in other languages.

Negation
The built-in Prolog predicate \+/1 provides negation as failure, which allows for non-monotonic reasoning. The goal "\+ illegal(X)" in the rule

legal(X) :- \+ illegal(X).

is evaluated is follows: Prolog attempts to prove illegal(X). If a proof for that goal can be found, the original goal (i.e., \+ illegal(X)) fails. If no proof can be found, the original goal succeeds. Therefore, the \+/1 prefix operator is called the "not provable" operator, since the query "?- \+ Goal" succeeds if Goal is not provable. This kind of negation is sound if its argument is ground. Soundness is lost if the argument contains variables. In particular, the query "?- legal(X)." can now not be used to enumerate all things that are legal.

Operational considerations
Under a declarative reading, the order of rules, and of goals within rules, is irrelevant since logical disjunction and conjunction are commutative. Procedurally, however, it is often important to take into account Prolog's execution strategy, either for efficiency reasons, or due to the semantics of impure built-in predicates for which the order of evaluation matters.

DCGs and parsing
There is a special notation called definite clause grammars (DCGs). A rule defined via -->/2 instead of :-/2 is expanded by the preprocessor (expand_term/2, a facility analogous to macros in other languages) according to a few straight-forward rewriting rules, resulting in ordinary Prolog clauses. Most notably, the rewriting equips the predicate with two additional arguments, which can be used to implicitly thread state around, analogous to monads in other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to list differences.

Parser example
A larger example will show the potential of using Prolog in parsing.

Given the sentence expressed in BNF:

<stat_part>  ::=  | <stat_part> ::= <id> = ; ::= |        ::=  <id> | <id>         ::=  a | b       ::=  0..9 ::= + | - | *

This can be written in Prolog using DCGs, corresponding to a predictive parser with one token look-ahead:

sentence(S)               --> statement(S0), sentence_r(S0, S). sentence_r(S, S)          --> []. sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S). statement(assign(Id,E)) --> id(Id), [=], expression(E), [;]. expression(E) --> term(T), expression_r(T, E). expression_r(E, E) --> []. expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E). expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E). term(T)      --> factor(F), term_r(F, T). term_r(T, T) --> []. term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T). factor(id(ID))  --> id(ID). factor(digit(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D)}. id(a) --> [a]. id(b) --> [b].

This code defines a relation between a sentence (given as a list of tokens) and its abstract syntax tree (AST). Example query:

?- phrase(sentence(AST), [a,=,1,+,3,*,b,;,b,=,0,;]). AST = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;

The AST is represented using Prolog terms and can be used to apply optimizations, to compile such expressions to machine-code, or to directly interpret such statements. As is typical for the relational nature of predicates, these definitions can be used both to parse and generate sentences, and also to check whether a given tree corresponds to a given list of tokens. Using iterative deepening for fair enumeration, each arbitrary but fixed sentence and its corresponding AST will be generated eventually:

?- length(Tokens, _), phrase(sentence(AST), Tokens). Tokens = [a, =, a, ], AST = assign(a, id(a)) ; Tokens = [a, =, b, ], AST = assign(a, id(b)) etc.

Higher-order programming
Since arbitrary Prolog goals can be constructed and evaluated at run-time, it is easy to write higher-order predicates like maplist/2, which applies an arbitrary predicate to each member of a given list, and sublist/3, which filters elements that satisfy a given predicate, also allowing for currying.

To convert solutions from temporal representation (answer substitutions on backtracking) to spatial representation (terms), Prolog has various all-solutions predicates that collect all answer substitutions of a given query in a list. This can be used for list comprehension. For example, perfect numbers equal the sum of their proper divisors:

perfect(N) :- between(1, inf, N), U is N // 2, findall(D, (between(1,U,D), N mod D =:= 0), Ds), sumlist(Ds, N).

This can be used to enumerate perfect numbers, and also to check whether a number is perfect.

Meta-interpreters and reflection
Prolog is a homoiconic language and provides many facilities for reflection. Its implicit execution strategy makes it possible to write a concise meta-circular evaluator (also called meta-interpreter) for pure Prolog code. Since Prolog programs are themselves sequences of Prolog terms (:-/2 is an infix operator) that are easily read and inspected using built-in mechanisms (like read/1), it is easy to write customized interpreters that augment Prolog with domain-specific features.

Implementation techniques
For efficiency, Prolog code is typically compiled to abstract machine code, often influenced by the register-based Warren Abstract Machine (WAM) instruction set. Some implementations employ abstract interpretation to derive type and mode information of predicates at compile time, or compile to real machine code for high performance. Devising efficient implementation techniques for Prolog code is a field of active research in the logic programming community, and various other execution techniques are employed in some implementations. These include clause binarization and stack-based virtual machines.

Examples
Here follow some example programs written in Prolog.

QuickSort
The QuickSort sorting algorithm, relating a list to its sorted version:

partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs) :- (  X @< Pivot ->         Smalls = [X|Rest],         partition(Xs, Pivot, Rest, Bigs)     ;   Bigs = [X|Rest],         partition(Xs, Pivot, Smalls, Rest)     ). quicksort([])    --> []. quicksort([X|Xs]) --> { partition(Xs, X, Smaller, Bigger) }, quicksort(Smaller), [X], quicksort(Bigger).

Turing machine
Turing completeness of Prolog can be shown by using it to simulate a Turing machine:

turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :- symbol(Rs0, Sym, RsRest), once(rule(Q0, Sym, Q1, NewSym, Action)), action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1), perform(Q1, Ls1, Ls, Rs1, Rs). symbol([], b, []). symbol([Sym|Rs], Sym, Rs). action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). action(stay, Ls, Ls, Rs, Rs). action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs). left([], [], Rs0, [b|Rs0]). left([L|Ls], Ls, Rs, [L|Rs]).

A simple example Turing machine is specified by the facts:

rule(q0, 1, q0, 1, right). rule(q0, b, qf, 1, stay).

This machine performs incrementation by one of a number in unary encoding: It loops over any number of "1" cells and appends an additional "1" at the end. Example query and result:

?- turing([1,1,1], Ts). Ts = [1, 1, 1, 1] ;

This example illustrates how any computation can be expressed declaratively as a sequence of state transitions, implemented in Prolog as a relation between successive states of interest. As another example for this, an optimizing compiler with three optimization passes could be implemented as a relation between an initial program and its optimized form:

program_optimized(Prog0, Prog) :- optimization_pass_1(Prog0, Prog1), optimization_pass_2(Prog1, Prog2), optimization_pass_3(Prog2, Prog).

or equivalently using DCG notation:

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

Dynamic programming
The following Prolog program uses dynamic programming to find the longest common subsequence of two lists in polynomial time. The clause database is used for memoization:

memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ). lcs([], _, []) :- !. lcs(_, [], []) :- !. lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)). lcs([X|Xs], [Y|Ys], Ls) :- memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)), length(Ls1, L1), length(Ls2, L2), (  L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

Example query:

?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls). Ls = [m, j, a, u]

Some Prolog systems, like BProlog and XSB, implement an extension called tabling, which frees the user from manually storing intermediate results.

Extensions

 * Constraint logic programming is important for many Prolog applications in industrial settings, like time tabling and other scheduling tasks. Most Prolog systems ship with at least one constraint solver for finite domains, and often also with solvers for other domains like rational numbers.
 * HiLog and λProlog extend Prolog with higher-order programming features.
 * F-logic extends Prolog with frames/objects for knowledge representation.
 * OW Prolog has been created in order to answer Prolog's lack of graphics and interface.
 * Logtalk is an open source object-oriented extension to the Prolog programming language. Integrating logic programming with object-oriented and event-driven programming, it is compatible with most Prolog compilers. It supports both prototypes and classes. In addition, it supports component-based programming through category-based composition.
 * Prolog-MPI is an open-source SWI-Prolog extension for distributed computing over the Message Passing Interface.

Related languages

 * Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog. Visual Prolog is a strongly-typed object-oriented dialect of Prolog, which is considerably different from standard Prolog.  As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm PDC (Prolog Development Center) that originally produced it.
 * Datalog is actually a subset of Prolog. It is limited to relationships that may be stratified and does not allow compound terms. In contrast to Prolog, Datalog is not Turing-complete.
 * In some ways Prolog is a subset of Planner, e.g., see Kowalski's early history of logic programming. The ideas in Planner were later further developed in the Scientific Community Metaphor.

Frameworks also exist which can provide a bridge between Prolog and the Java programming language:

 * InterProlog, a programming library bridge between Java and Prolog, implementing bi-directional predicate/method calling between both languages. Java objects can be mapped into Prolog terms and vice-versa. Allows the development of GUIs and other functionality in Java while leaving logic processing in the Prolog layer. Supports XSB, SWI-Prolog and YAP.
 * Prova provides native syntax integration with Java, agent messaging and reaction rules. Prova positions itself as a rule-based scripting (RBS) system for middleware. The language breaks new ground in combining imperative and declarative programming.

title: Expert Systems/Prolog


text:
Expert Systems/DENDRAL

Dendral was an influential pioneer project in artificial intelligence (AI) of the 1960s, and the computer software expert system that it produced. Its primary aim was to help organic chemists in identifying unknown organic molecules, by analyzing their mass spectra and using knowledge of chemistry. It was done at Stanford University by Edward Feigenbaum, Bruce Buchanan, Joshua Lederberg, and Carl Djerassi. It began in 1965 and spans approximately half the history of AI research.

The software program Dendral is considered the first expert system because it automated the decision-making process and problem-solving behavior of organic chemists. It consists of two sub-programs, Heuristic Dendral and Meta-Dendral,. It was written in Lisp, which was considered the language of AI.

Many systems were derived from Dendral, including MYCIN, MOLGEN, MACSYMA, PROSPECTOR, XCON, and STEAMER.

The name Dendral is a portmanteaux of the term "Dendritic Algorithm".

Heuristic Dendral
Heuristic Dendral is a program that uses mass spectra or other experimental data together with knowledge base of chemistry, to produce a set of possible chemical structures that may be responsible for producing the data. A mass spectrum of a compound is produced by a mass spectrometer, and is used to deterime its molecular weight, the sum of the masses of its atomic constituents. For example, the compound water (H2O), has a molecular weight of 18 since hydrogen has a mass of 1.01 and oxygen 16.00, and its mass spectrum has a peak at 18 units. Heuristic Dendral would use this input mass and the knowledge of atomic mass numbers and valence rules, to determine the possible combinations of atomic constituents whose mass would add up to 18. As the weight increases and the molecules become more complex, the number of possible compounds increases drastically. Thus, a program that is able to reduce this number of candidate solutions through the process of hypothesis formation is essential.

Meta-Dendral
Meta-Dendral is a knowledge acquisition system that receives the set of possible chemical structures and corresponding mass spectra as input, and proposes a set of hypotheses to explain correlation between some of the proposed structures and the mass spectrum. These hypotheses would be fed back to Heuristic Dendral to test their applicability. Thus, "Heuristic Dendral is a performance system and Meta-Dendral is a learning system". The program is based on two important features: the plan-generate-test paradigm and knowledge engineering.

Plan-generate-test paradigm
The plan-generate-test paradigm is the basic organization of the problem-solving method, and is a common paradigm used by both Heuristic Dendral and Meta-Dendral systems. The generator generates potential solutions for a particular problem, which are then expressed as chemical graphs in Dendral. However, this is feasible only when the number of candidate solutions is minimal. When there are large numbers of possible solutions, Dendral has to find a way to put constraints that rules out large sets of candidate solutions. This is the primary aim of Dendral planner, which is a “hypothesis-formation” program that employs “task-specific knowledge to find constraints for the generator”. Last but not least, the tester analyzes each proposed candidate solution and discards those that fail to fulfill certain criteria. This mechanism of plan-generate-test paradigm is what holds Dendral together.

Knowledge Engineering
The primary aim of knowledge engineering is to attain a productive interaction between the available knowledge base and problem solving techniques. This is possible through development of a procedure in which large amounts of task-specific information is encoded into heuristic programs. Thus, the first essential component of knowledge engineering is a large “knowledge base.” The knowledge base would include specific knowledge about the mass spectrometry technique, large amount of information that forms the basis of chemistry and graph theory, and any information that might be helpful in finding the solution of a particular chemical structure elucidation problem. Through knowledge engineering Dendral is able to use this “knowledge base” to both determine the set of possible chemical structures that correspond to the input data, and form new “general rules” that helps it reduce the number of candidate solutions. Thus, at the end the user is now provided with a minimal number of possible solutions, which can now be tested by any non-expert user to find the right solution.

Heuristics
A heuristic is a rule of thumb, an algorithm that does not guarantee a solution, but reduces the number of possible solutions by discarding unlikely and irrelevant solutions. The use of heuristics to solve problems is called "heuristics programming", and was used in Dendral to allow it to replicate in machines the process through which human experts induce the solution to problems via rules of thumb and specific information.

Heuristics programming was a major approach and a giant step forward in artificial intelligence, as it allowed scientists to finally automate certain traits of human intelligence. It became prominent among scientists in the late 1940s through George Polya’s book, How to Solve It: A New Aspect of Mathematical Method. As Herbert Simon said in The Sciences of the Artificial, "if you take a heuristic conclusion as certain, you may be fooled and disappointed; but if you neglect heuristic conclusions altogether you will make no progress at all."

History
During mid 20th century, the question "can machines think?" became intriguing and popular among scientists, primarily to add humanistic characteristics to machine behavior. John McCarthy, who was one of the prime researchers of this field, termed this concept of machine intelligence as "artificial intelligence" (AI) during the Dartmouth summer in 1956. AI is usually defined as the capacity of a machine to perform operations that are analogous to human cognitive capabilities. Much research to create AI was done during the 20th century.

Also around mid 20th century, science, especially biology, faced a fast-increasing need to develop a "man-computer symbiosis", to aid scientists in solving problems. For example, the structural analysis of myogoblin, hemoglobin, and other proteins relentlessly needed instrumentation development due to its complexity.

In the early 1960s, Joshua Lederberg started working with computers and quickly became tremendously interested in creating interactive computers to help him in his exobiology research. Specifically, he was interested in designing computing systems that to help him study alien organic compounds. As he was not an expert in either chemistry or computer programming, he collaborated with Stanford chemist Carl Djerassi to help him with chemistry, and Edward Feigenbaum with programming, to automate the process of determining chemical structures from raw mass spectrometry data. Feigenbaum was an expert in programming languages and heuristics, and helped Lederberg design a system that replicated the way Carl Djerassi solved structure elucidation problems. They devised a system called Dendritic Algorithm (Dendral) that was able to generate possible chemical structures corresponding to the mass spectrometry data as an output.

Dendral then was still very inaccurate in assessing spectra of ketones, alcohols, and isomers of chemical compounds. Thus, as seen in figure 1, Djerassi "taught" general rules to Dendral that could help eliminate most of the "chemically implausible" structures, and produce a set of structures that could now be analyzed by a "non-expert" user to determine the right structure. Figure 2 shows how Dendral operates without an expert, after all the general rules were entered into Dendral's knowledge base.

The Dendral team recruited Bruce Buchanan to refine Feigenbaum’s Lisp program. Buchanan had similar ideas and interests as Feigenbaum and Lederberg, but his special interest was hypothesis formation. As Joseph November said in Digitizing Life: The Introduction of Computers to Biology and Medicine, "(Buchanan) wanted the system (Dendral) to make discoveries on its own, not just help humans make them". Buchanan designed "Meta-Dendral", which was a "hypothesis maker". Meta-Dendral and Dendral were fused together to create Heuristic Dendral" in 1966-67. The prime difference was that Heuristic Dendral "would serve as a template for similar systems in other areas" rather than just concentrating in the field of organic chemistry.

title: Expert Systems/DENDRAL


text:
Expert Systems/MYCIN

Mycin was an early expert system developed over five or six years in the early 1970s at Stanford University; it was written in Lisp, by Edward Shortliffe under the direction of Bruce Buchanan and others; it derived from the earlier Dendra] expert system, but considerably modified and extended the basic Dendral software. This computer system was designed to diagnose infectious blood diseases and recommend antibiotics, with the dosage adjusted for patient's body weight — the name derived from the antibiotics themselves, as many antibiotics have the suffix "-mycin".

Method
Mycin operated using a fairly simple inference engine,a knowledge base of ~500 rules. It would query the physician running the program via a long series of simple yes/no or textual questions. At the end, it provided a list of possible culprit bacteria ranked from high to low based on the probability of each diagnosis, its confidence in each diagnosis' probability, the reasoning behind each diagnosis (that is, Mycin would also list the questions and rules which led it to rank a diagnosis a particular way), and its recommended course of drug treatment.

Despite Mycin's success, it is sometimes now used as a cautionary tale in AI courses for people who generate their own ad hoc probability frameworks. Mycin had a limited depth to its reasoning hierarchy due to the noise introduced by its certainty factor system. This problem can be solved by using a rigorous probabilistic framework, such as Bayesian statistics.

Results
Research conducted at the Stanford Medical School found Mycin to have a correct diagnosis rate of about 65%, which was better than most physicians who were not specialists in diagnosing bacterial infections, even though it was worse than those physicians who were themselves experts in the field who had average correct diagnosis rates of about 80%.

Practical use
Mycin was never actually used in practice. This wasn't because of any weakness in its performance — in tests it outperformed members of the Stanford medical school. It was as much because of ethical and legal issues related to the use of computers in medicine — if it gives the wrong diagnosis, who can be held responsible? Issues with whether human experts would find it acceptable to use arose as well.

A difficulty that rose to prominence during the development of Mycin and subsequent complex expert systems has been the extraction of the necessary knowledge for the inference engine to use from the humans expert in the relevant fields into the rule base (the so-called knowledge engineering).

title: Expert Systems/MYCIN


text:
Expert Systems/Fuzzy Logic

About Fuzzy Logic
Fuzzy logic is derived from fuzzy set theory dealing with reasoning that is approximate rather than precisely deduced from classical predicate logic. It can be thought of as the application side of fuzzy set theory dealing with well thought out real world expert values for a complex problem (Klir 1997).

Degrees of truth are often confused with probabilities. However, they are conceptually distinct; fuzzy truth represents membership in vaguely defined sets, not likelihood of some event or condition. For example, if a 100-ml glass contains 30 ml of water, then, for two fuzzy sets, Empty and Full, one might define the glass as being 0.7 empty and 0.3 full. Note that the concept of emptiness would be subjective and thus would depend on the observer or designer. Another designer might equally well design a set membership function where the glass would be considered full for all values down to 50 ml. A probabilistic setting would first define a scalar variable for the fullness of the glass, and second, conditional distributions describing the probability that someone would call the glass full given a specific fullness level. Note that the conditioning can be achieved by having a specific observer that randomly selects the label for the glass, a distribution over deterministic observers, or both. While fuzzy logic avoids talking about randomness in this context, this simplification at the same time obscures what is exactly meant by the statement the 'glass is 0.3 full'.

Fuzzy logic allows for set membership values to range (inclusively) between 0 and 1, and in its linguistic form, imprecise concepts like "slightly", "quite" and "very". Specifically, it allows partial membership in a set. It is related to fuzzy sets and possibility theory. It was introduced in 1965 by Lotfi Zadeh at the University of California, Berkeley.

Fuzzy logic is controversial in some circles and is rejected by some control engineers and by most statisticians who hold that probability is the only rigorous mathematical description of uncertainty. Critics also argue that it cannot be a superset of ordinary set theory since membership functions are defined in terms of conventional sets.

Applications
Fuzzy logic can be used to control household appliances such as washing machines (which sense load size and detergent concentration and adjust their wash cycles accordingly) and refrigerators.

A basic application might characterize subranges of a continuous variable. For instance, a temperature measurement for anti-lock brakes might have several separate membership functions defining particular temperature ranges needed to control the brakes properly. Each function maps the same temperature value to a truth value in the 0 to 1 range. These truth values can then be used to determine how the brakes should be controlled.

In this image, cold, warm, and hot are functions mapping a temperature scale. A point on that scale has three "truth values" — one for each of the three functions. For the particular temperature illustrated with the vertical line, the three truth values could be interpreted as describing the temperature as, say, "fairly cold" (blue arrow), "slightly warm" (yellow arrow), and "not hot" (red arrow).

Misconceptions and controversies

 * Fuzzy logic is the same as "imprecise logic".
 * Fuzzy logic is not any less precise than any other form of logic: it is an organized and mathematical method of handling inherently imprecise concepts. The concept of "coldness" cannot be expressed in an equation, because although temperature is a quantity, "coldness" is not. However, people have an idea of what "cold" is, and agree that there is no sharp cutoff between "cold" and "not cold", where something is "cold" at N degrees but "not cold" at N+1 degrees — a concept classical logic cannot easily handle due to the principle of bivalence. The result has no set answer so it is believed to be a 'fuzzy' answer.

 * Fuzzy logic is a new way of expressing probability.
 * Fuzzy logic and probability are different ways of expressing uncertainty. While both fuzzy logic and probability theory can be used to represent subjective belief, fuzzy set theory uses the concept of fuzzy set membership (i.e. how much a variable is in a set), probability theory uses the concept of subjective probability (i.e. how probable do I think that a variable is in a set). While this distinction is mostly philosophical, the fuzzy-logic-derived possibility measure is inherently different from the probability measure, hence they are not directly equivalent. However, many statisticians are persuaded by the work of Bruno de Finetti that only one kind of mathematical uncertainty is needed and thus fuzzy logic is unnecessary. On the other hand, Bart Kosko argues that probability is a subtheory of fuzzy logic, as probability only handles one kind of uncertainty. He also claims to have proven a derivation of Bayes' theorem from the concept of fuzzy subsethood. Lotfi Zadeh, the creator of fuzzy logic, argues that fuzzy logic is different in character from probability, and is not a replacement for it. He has created a fuzzy alternative to probability, which he calls possibility theory. Other controversial approaches to uncertainty include Dempster-Shafer theory and rough sets.

 * Fuzzy logic will be difficult to scale to larger problems.
 * This criticism is mainly due to the fact that there exist problems with conditional possibility, the fuzzy set theory equivalent of conditional probability (see Halpen (2003), section 3.8). This makes it difficult to perform inference. However there have not been many studies comparing fuzzy-based systems with probabilistic ones.

Examples where fuzzy logic is used

 * Automobile and other vehicle subsystems, such as automatic transmissions, ABS and cruise control (e.g. Tokyo monorail)
 * Air conditioners
 * The Massive engine used in the Lord of the Rings films, which helped show huge scale armies create random, yet orderly movements
 * Cameras
 * Digital image processing, such as edge detection
 * Rice cookers
 * Dishwashers
 * Elevators
 * Washing machines and other home appliances
 * Video game artificial intelligence
 * Language filters on message boards and chat rooms for filtering out offensive text
 * Pattern recognition in Remote Sensing
 * Fuzzy logic has also been incorporated into some microcontrollers and microprocessors, for instance, the Freescale 68HC12.

How fuzzy logic is applied
Fuzzy Set Theory defines Fuzzy Operators on Fuzzy Sets. The problem in applying this is that the appropriate Fuzzy Operator may not be known. For this reason, Fuzzy logic usually uses IF/THEN rules, or constructs that are equivalent, such as fuzzy associative matrices.

Rules are usually expressed in the form: IF variable IS set THEN action

For example, an extremely simple temperature regulator that uses a fan might look like this: IF temperature IS very cold THEN stop fan IF temperature IS cold THEN turn down fan IF temperature IS normal THEN maintain level IF temperature IS hot THEN speed up fan

Notice there is no "ELSE". All of the rules are evaluated, because the temperature might be "cold" and "normal" at the same time to differing degrees.

The AND, OR, and NOT operators of boolean logic exist in fuzzy logic, usually defined as the minimum, maximum, and complement; when they are defined this way, they are called the Zadeh operators, because they were first defined as such in Zadeh's original papers. So for the fuzzy variables x and y:

NOT x = (1 - truth(x))

x AND y = minimum(truth(x), truth(y))

x OR y = maximum(truth(x), truth(y))

There are also other operators, more linguistic in nature, called hedges that can be applied. These are generally adverbs such as "very", or "somewhat", which modify the meaning of a set using a mathematical formula.

In application, the programming language Prolog is well geared to implementing fuzzy logic with its facilities to set up a database of "rules" which are queried to deduct logic. This sort of programming is known as logic programming.

Once fuzzy relations are defined, it is possible to develop fuzzy relational databases. The first fuzzy relational database, FRDB, appeared in Maria Zemankova's dissertation. After, some other models arose like the Buckles-Petry model, the Prade-Testemale Model, the Umano-Fukami model or the GEFRED model by J.M. Medina, M.A. Vila et al. In the context of fuzzy databases, some fuzzy querying languages have been defined, highlighting the SQLf by P. Bosc et al. and the FSQL by J. Galindo et al. These languages define some structures in order to include fuzzy aspects in the SQL statements, like fuzzy conditions, fuzzy comparators, fuzzy constants, fuzzy constraints, fuzzy thresholds, linguistic labels and so on.

Other examples
IF male IS true AND height >= 1.8 THEN is_tall IS true; is_short IS false
 * If a man is 1.8 meters, consider him as tall:

IF height <= medium male THEN is_short IS agree somewhat IF height >= medium male THEN is_tall IS agree somewhat
 * The fuzzy rules do not make the sharp distinction between tall and short, that is not so realistic:

In the fuzzy case, there are no such heights like 1.83 meters, but there are fuzzy values, like the following assignments:

dwarf male = [0, 1.3] m short male = (1.3, 1.5] medium male = (1.5, 1.8] tall male = (1.8, 2.0] giant male > 2.0 m

For the consequent, there are also not only two values, but five, say:

agree not = 0 agree little = 1 agree somewhat = 2 agree a lot = 3 agree fully = 4

In the binary, or "crisp", case, a person of 1.79 meters of height is considered short. If another person is 1.8 meters or 2.25 meters, these persons are considered tall.

The crisp example differs deliberately from the fuzzy one. We did not put in the antecedent

IF male >= agree somewhat AND ...

as gender is often considered as a binary information. So, it is not so complex as being tall.

Formal fuzzy logic
In mathematical logic, there are several formal systems that model the above notions of "fuzzy logic"; most of them belong among so-called t-norm fuzzy logics. Note that they use a different set of operations than above mentioned Zadeh operators.

Propositional fuzzy logics
The most important propositional fuzzy logics are: All these logics encompass the traditional propositional logic (whose models correspond to Boolean algebras).
 * Basic propositional fuzzy logic BL is an axiomatization of logic where conjunction is defined by a continuous |t-norm, and implication is defined as the residuum of the t-norm. Its models correspond to BL-algebras.
 * Łukasiewicz fuzzy logic is a special case of basic fuzzy logic where conjunction is Łukasiewicz t-norm. It has the axioms of basic logic plus an axiom of double negation (so it is not intuitionistic logic), and its models correspond to MV-algebras.
 * Gödel fuzzy logic is a special case of basic fuzzy logic where conjunction is Gödel t-norm. It has the axioms of basic logic plus an axiom of idempotence of conjunction, and its models are called G-algebras.
 * Product fuzzy logic is a special case of basic fuzzy logic where conjunction is product t-norm. It has the axioms of basic logic plus another axiom, and its models are called product algebras.
 * Monoidal t-norm logic MTL is a generalization of basic fuzzy logic BL where conjunction is realized by a left-continuous t-norm. Its models (MTL-algebras) are prelinear commutative bounded integral residuated lattices.
 * Rational Pavelka logic is a generalization of multi-valued logic. It is an extension of Łukasziewicz fuzzy logic with additional constants.

Predicate fuzzy logics
These extend the above-mentioned fuzzy logics by adding universal and existential quantifiers in a manner similar to the way that predicate logic is created from propositional logic. The semantics of the universal resp. existential quantifier in t-norm fuzzy logics is the infimum resp. supremum of the truth degrees of the instances of the quantified subformula.

Effectiveness for fuzzy logics
The notions of a "decidable subset" and "recursively enumerable subset" are basic ones for classical mathematics and classical logic. Then, the question of a suitable extension of such concepts to fuzzy set theory arises. A first proposal in such a direction was made by E.S. Santos by the notions of fuzzy Turing machine, Markov normal fuzzy algorithm and fuzzy program. Successively, L. Biacino and G. Gerla proposed the following definition where Ü denotes the set of rational numbers in [0,1]. A fuzzy subset μ : S $$\rightarrow$$[0,1] of a set S is recursively enumerable if a recursive map h : S×N $$\rightarrow$$Ü exists such that, for every x in S, the function h(x,n) is increasing with respect to n and μ(x) = lim h(x,n). We say that μ is decidable if both μ and its complement –μ are recursively enumerable. An extension of such a theory to the general case of the L-subsets is proposed in a paper by G. Gerla. The proposed definitions are well related with fuzzy logic. Indeed, the following theorem holds true (provided that the deduction apparatus of the fuzzy logic satisfies some obvious effectiveness property).

Theorem. Any axiomatizable fuzzy theory is recursively enumerable. In particular, the fuzzy set of logically true formulas is recursively enumerable in spite of the fact that the crisp set of valid formulas is not recursively enumerable, in general. Moreover, any axiomatizable and complete theory is decidable.

It is an open question to give supports for a Church thesis for fuzzy logic claiming that the proposed notion of recursive enumerability for fuzzy subsets is the adequate one. To this aim, further investigations on the notions of fuzzy grammar and fuzzy Turing machine should be necessary (see for example Wiedermann's paper). Another open question is to start from this notion to find an extension of Gödel’s theorems to fuzzy logic.

Sample applications

 * Agriculture
 * GIS
 * Image Processing (in Internet Archive)
 * Machine Learning
 * Machine Vision
 * Medicine
 * Model Validation
 * OCR
 * Shape Recognition
 * Telecommunications

title: Expert Systems/Fuzzy Logic


text:
Expert Systems/Rete Algorithm

About the Rete Algorithm
The Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper (see References). Rete has become the basis for many popular expert systems, including CLIPS, Jess, JBoss Rules, and Soar.

A naïve implementation of an expert system might check each rule against the known facts in the Knowledge base, firing that rule if necessary, then moving on to the next rule (and looping back to the first rule when finished). For even moderate sized rules and facts knowledge-bases, this naïve approach performs far too slowly.

The Rete algorithm (usually pronounced either 'REET', 'REE-tee' or, in Europe, 're-tay' after the Latin pronunciation, from the Latin 'rete' for net, or network) provides the basis for a more efficient implementation of an expert system. A Rete-based expert system builds a network of nodes, where each node (except the root) corresponds to a pattern occurring in the left-hand-side of a rule. The path from the root node to a leaf node defines a complete rule left-hand-side. Each node has a memory of facts which satisfy that pattern. This structure is essentially a generalized Trie.

As new facts are asserted or modified, they propagate along the network, causing nodes to be annotated when that fact matches that pattern. When a fact or combination of facts causes all of the patterns for a given rule to be satisfied, a leaf node is reached and the corresponding rule is triggered.

The Rete algorithm is designed to sacrifice memory for increased speed. In most cases, the speed increase over naïve implementations is several orders of magnitude (because Rete performance is theoretically independent of the number of rules in the system). In very large expert systems, however, the original Rete algorithm tends to run into memory consumption problems. Other algorithms, both novel and Rete-based, have since been designed which require less memory.

Description
The Rete algorithm provides a generalized logical description of an implementation of functionality responsible for matching data tuples (‘facts’) against productions (‘rules’) in a pattern-matching production system (a category of rule engine). A production consists of one or more conditions and a set of actions which may be undertaken for each complete set of facts that match the conditions. Conditions test fact attributes, including fact type specifiers/identifiers. The Rete algorithm exhibits the following major characteristics:

The Rete algorithm is widely used to implement matching functionality within pattern-matching engines that exploit a match-resolve-act cycle to support forward chaining and inferencing.
 * It reduces or eliminates certain types of redundancy through the use of node sharing.
 * It stores partial matches when performing joins between different fact types.  This, in turn, allows production systems to avoid complete re-evaluation of all facts each time changes are made to the production system’s working memory.   Instead, the production system needs only to evaluate the changes (deltas) to working memory.
 * It allows for efficient removal of memory elements when facts are retracted from working memory.

Retes are directed acyclic graphs that represent higher-level rule sets. They are generally represented at run-time using a network of in-memory objects. These networks match rule conditions (patterns) to facts (relational data tuples). Rete networks act as a type of relational query processor, performing projections, selections and joins conditionally on arbitrary numbers of data tuples.

Productions (rules) are typically captured and defined by analysts and developers using some high-level rules language. They are collected into rule sets which are then translated, often at run time, into an executable Rete.

When facts are ‘asserted’ to working memory, the engine creates ‘working memory elements’ (WMEs) for each fact. Facts are n-tuples, and may therefore contain an arbitrary number of data items. Each WME may hold an entire n-tuple, or, alternatively, each fact may be represented by a set of WMEs where each WME contains a fixed-length tuple. In this case, tuples are typically triplets (3-tuples).

Each WME enters the Rete network at a single root node. The root node passes each WME on to its child nodes, and each WME may then be propagated through the network, possibly being stored in intermediate memories, until it arrives at a terminal node.

Alpha Network
The ‘left’ (alpha) side of the node graph forms a discrimination network responsible for selecting individual WMEs based on simple conditional tests which match WME attributes against constant values. Nodes in the discrimination network may also perform tests that compare two or more attributes of the same WME. If a WME is successfully matched against the conditions represented by one node, it is passed to the next node. In most engines, the immediate child nodes of the root node are used to test the entity identifier or fact type of each WME. Hence, all the WMEs which represent the same entity type typically traverse a given branch of nodes in the discrimination network.

Within the discrimination network, each branch of alpha nodes (also called 1-input nodes) terminates at a memory, called an ‘alpha’ memory. These memories store collections of WMEs that match each condition in each node in a given node branch. WMEs that fail to match at least one condition in a branch are not materialised within the corresponding alpha memory. Alpha node branches may fork in order to minimise condition redundancy.

A possible variation is to introduce additional memories for each intermediate node in the discrimination network. This increases the overhead of the Rete, but may have advantages in situations where rules are dynamically added to or removed from the Rete, making it easier to vary the topography of the discrimination network dynamically.

An alternative implementation is described by Doorenbos. In this case, the discrimination network is replaced by a set of memories and an index. The index may be implemented using a hash table. Each memory holds WMEs that match a single conditional pattern, and the index is used to reference memories by their pattern. This approach is only practical when WMEs represent fixed-length tuples, and the length of each tuple is short (e.g., 3-tuples). In addition, the approach only applies to conditional patterns that perform equality tests against constant values. When a WME enters the Rete, the index is used to locate a set of memories whose conditional pattern matches the WME attributes, and the WME is then added directly to each of these memories. In itself, this implementation contains no 1-input nodes. However, in order to implement non-equality tests, the Rete may contain additional 1-input node networks through which WMEs are passed before being placed in a memory. Alternatively, non-equality tests may be performed in the beta network described below.

Beta Network
The ‘right’ (beta) side of the graph chiefly performs joins between different WMEs. It is optional, and is only included if required. It consists of 2-input nodes where each node has a ‘left’ and a ‘right’ input. Each beta node sends its output to a ‘beta’ memory.

Beta nodes process tokens. A token is a unit of storage within a memory and also a unit of exchange between memories and nodes. In many implementations, tokens are introduced within alpha memories where they are used to hold single WMEs. These tokens are then passed to the beta network.

Each beta node performs its work and, as a result, may create new tokens to hold a list of WMEs representing a partial match. These extended tokens are then stored in beta memories, and passed to subsequent beta nodes. In this case, the beta nodes typically pass lists of WMEs through the beta network by copying existing WME lists from each received token into new tokens and then adding a further WMEs to the lists as a result of performing a join or some other action. The new tokens are then stored in the output memory.

A common variation is to build linked lists of tokens where each token holds a single WME. In this case, lists of WMEs for a partial match are represented by the linked list of tokens. This approach may be more optimal because it eliminates the need to copy lists of WMEs from one token to another. Instead, a beta node needs only to create a new token to hold a WME it wishes to join to the partial match list, and then link the new token to a parent token stored in the input beta memory. The new token now forms the head of the token list, and is stored in the output beta memory.

In descriptions of Rete, it is common to refer to token passing within the beta network. In this article, however, we will describe data propagation in terms of WME lists, rather than tokens, in recognition of different implementation options and the underlying purpose and use of tokens. As any one WME list passes through the beta network, new WMEs may be added to it, and the list may be stored in beta memories. A WME list in a beta memory represents a partial match for the conditions in a given production.

WME lists that reach the end of a branch of beta nodes represent a complete match for a single production, and are passed to terminal nodes. These nodes are sometimes called ‘p-nodes’, where ‘p’ stands for ‘production’. Each terminal node represents a single production, and each WME list that arrives at a terminal node represents a complete set of matching WMEs for the conditions in that production. For each WME list it receives, a production node will ‘activate’ a new production instance on the ‘agenda’. Agendas are typically implemented as prioritised queues.

Beta nodes typically perform joins between WME lists stored in beta memories and individual WMEs stored in alpha memories. Each beta node is associated with two input memories. An alpha memory holds WMEs and performs ‘right’ activations on the beta node each time it stores a new WME. A beta memory holds WME lists and performs ‘left’ activations on the beta node each time it stores a new WME list. When a join node is right-activated, it compares one or more attributes of the newly stored WME from its input alpha memory against given attributes of specific WMEs in each WME list contained in the input beta memory. When a join node is left-activated it traverses a single newly stored WME list in the beta memory, retrieving specific attribute values of given WMEs. It compares these values with attribute values of each WME in the alpha memory.

Each beta node outputs WME lists which are either stored in a beta memory or sent directly to a terminal node. WME lists are stored in beta memories whenever the engine will perform additional left activations on subsequent beta nodes.

Logically, a beta node at the head of a branch of beta nodes is a special case because it takes no input from any beta memory higher in the network. Different engines handle this issue in different ways. Some engines use specialised adapter nodes to connect alpha memories to the left input of beta nodes. Other engines allow beta nodes to take input directly from two alpha memories, treating one as a ‘left’ input and the other as a ‘right’ input. In both cases, ‘head’ beta nodes take their input from two alpha memories.

In order to eliminate node redundancies, any one alpha or beta memory may be used to perform activations on multiple beta nodes. As well as join nodes, the beta network may contain additional node types, some of which are described below. If a Rete contains no beta network, alpha nodes feed tokens, each containing a single WME, directly to p-nodes. In this case, there may be no need to store WMEs in alpha memories.

Conflict Resolution
During any one match-resolve-act cycle, the engine will find all possible matches for the facts currently asserted to working memory. Once all the current matches have been found, and corresponding production instances have been activated on the agenda, the engine determines an order in which the production instances may be ‘fired’. This is termed ‘conflict resolution’, and the list of activated production instances is termed the ‘conflict set’. The order may be based on rule priority (salience), rule order, the time at which facts contained in each instance were asserted to the working memory, the complexity of each production or some other criteria. Many engines allow rule developers to select between different conflict resolution strategies or to chain a selection of multiple strategies. Conflict resolution is not defined as part of the Rete algorithm, but is used alongside the algorithm. Some specialised production systems do not perform conflict resolution.

Production Execution
Having performed conflict resolution, the engine now ‘fires’ the first production instance, executing a list of actions associated with the production. The actions act on the data represented by the production instance’s WME list.

By default, the engine will continue to fire each production instance in order until all production instances have been fired. Each production instance will fire only once, at most, during any one match-resolve-act cycle. This characteristic is termed ‘refraction’. However, the sequence of production instance firings may be interrupted at any stage by performing changes to the working memory. Rule actions can contain instructions to assert or retract WMEs from the ‘working memory’ of the engine. Each time any single production instance performs one or more such changes, the engine immediately enters a new match-resolve-act cycle. This includes ‘updates’ to WMEs currently in the working memory. Updates are represented by retracting and then re-asserting the WME. The engine undertakes matching of the changed data which, in turn, may result in changes to the list of production instances on the agenda. Hence, after the actions for any one specific production instance have been executed, previously activated instances may have been de-activated and removed from the agenda, and new instances may have been activated.

As part of the new match-resolve-act cycle, the engine performs conflict resolution on the agenda and then executes the current first instance. The engine continues to fire production instances, and to enter new match-resolve-act cycles, until no further production instances exist on the agenda. At this point the rule engine is deemed to have completed its work, and halts.

Some engines support advanced refraction strategies in which certain production instances executed in a previous cycle are not re-executed in the new cycle, even though they may still exist on the agenda.

It is possible for the engine to enter into never-ending loops in which the agenda never reaches the empty state. For this reason, most engines support explicit ‘halt’ verbs that can be invoked from production action lists. They may also provide automatic loop detection in which never-ending loops are automatically halted after a given number of iterations. Some engines support a model in which, instead of halting when the agenda is empty, the engine enters a wait state until new facts are asserted externally.

As for conflict resolution, the firing of activated production instances is not a feature of the Rete algorithm. However, it is a central feature of engines that use Rete networks. Some of the optimisations offered by Rete networks are only useful in scenarios where the engine performs multiple match-resolve-act cycles.

Existential and Universal Quantifications
Conditional tests are most commonly used to perform selections and joins on individual tuples. However, by implementing additional beta node types, it is possible for Rete networks to perform quantifications. Existential quantification involves testing for the existence of at least one set of matching WMEs in working memory. Universal quantification involves testing that an entire set of WMEs in working memory meets a given condition. A variation of universal quantification might test that a given number of WMEs, drawn from a set of WMEs, meets a given criteria. This might be in terms of testing for either an exact number or a minimum number of matches.

Quantification is not universally implemented in Rete engines, and, where it is supported, several variations exist. A variant of existential quantification referred to as ‘negation’ is widely, though not universally, supported, and is described in seminal documents. Existentially negated conditions and conjunctions involve the use of specialised beta nodes that test for non-existence of matching WMEs or sets of WMEs. These nodes propagate WME lists only when no match is found. The exact implementation of negation varies. In one approach, the node maintains a simple count on each WME list it receives from its left input. The count specifies the number of matches found with WMEs received from the right input. The node only propagates WME lists whose count is zero. In another approach, the node maintains an additional memory on each WME list received from the left input. These memories are a form of beta memory, and store WME lists for each match with WMEs received on the right input. If a WME list does not have any WME lists in its memory, it is propagated down the network. In this approach, negation nodes generally activate further beta nodes directly, rather than storing their output in an additional beta memory. Negation nodes provide a form of 'negation as failure'.

When changes are made to working memory, a WME list that previously matched no WMEs may now match newly asserted WMEs. In this case, the propagated WME list and all its extended copies need to be retracted from beta memories further down the network. The second approach described above is often used to support efficient mechanisms for removal of WME lists. When WME lists are removed, any corresponding production instances are de-activated and removed from the agenda.

Existential quantification can be performed by combining two negation beta nodes. This represents the semantics of double negation (e.g., ‘If NOT NOT any matching WMEs, then...’). This is a common approach taken by several production systems.

Memory Indexing
The Rete algorithm does not mandate any specific approach to indexing the working memory. However, most modern production systems provide indexing mechanisms. In some cases, only beta memories are indexed, whilst in others, indexing is used for both alpha and beta memories. A good indexing strategy is a major factor in deciding the overall performance of a production system, especially when executing rule sets that result in highly combinatorial pattern matching (i.e., intensive use of beta join nodes), or, for some engines, when executing rules sets that perform a significant number of WME retractions during multiple match-resolve-act cycles. Memories are often implemented using combinations of hash tables, and hash values are used to perform conditional joins on subsets of WME lists and WMEs, rather than on the entire contents of memories. This, in turn, often significantly reduces the number of evaluations performed by the Rete network.

Removal of WMEs and WME lists
When a WME is retracted from working memory, it must be removed from every alpha memory in which it is stored. In addition, WME lists that contain the WME must be removed from beta memories, and activated production instances for these WME lists must be de-activated and removed from the agenda. Several implementation variations exist, including tree-based and rematch-based removal. Memory indexing may be used in some cases to optimise removal.

Handling OR’ed conditions
When defining productions in a rule set, it is common to allow conditions to be grouped using an ‘OR’ connective. In many production systems, this is handled by interpreting a single production containing multiple OR’ed patterns as the equivalent of multiple productions. The resulting Rete network contains sets of terminal nodes which, together, represent single productions. This approach disallows any form of short-circuiting of the OR’ed conditions. It can also, in some cases, lead to duplicate production instances being activated on the agenda where the same set of WMEs match multiple internal productions. Some engines provide agenda de-duplication in order to handle this issue.

Miscellaneous Considerations
Although not defined by the Rete algorithm, some engines provide extended functionality to support greater control of truth maintenance. For example, when a match is found for one production, this may result in the assertion of new WMEs which, in turn, match the conditions for another production. If a subsequent change to working memory causes the first match to become invalid, it may be that this implies that the second match is also invalid. The Rete algorithm does not define any mechanism to define and handle these logical truth dependencies automatically. Some engines, however, support additional functionality in which truth dependencies can be automatically maintained. In this case, the retraction of one WME may lead to the automatic retraction of additional WMEs in order to maintain logical truth assertions.

The Rete algorithm does not define any approach to justification. Justification refers to mechanisms commonly required in expert and decision systems in which, at its simplest, the system reports each of the inner decisions used to reach some final conclusion. For example, an expert system might justify a conclusion that an animal is an elephant by reporting that it is large, grey, has big ears, a trunk and tusks. Some engines provide built-in justification systems in conjunction with their implementation of the Rete algorithm.

This article does not provide an exhaustive description of every possible variation or extension of the Rete algorithm. Other considerations and innovations exist. For example, engines may provide specialised support within the Rete network in order to apply pattern-matching rule processing to specific data types and sources such as programmatic objects, XML data or relational data tables. Another example concerns additional time-stamping facilities provided by many engines for each WME entering a Rete network, and the use these time-stamps in conjunction with conflict resolution strategies. Engines exhibit significant variation in the way they allow programmatic access to the engine and its working memory, and may extend the basic Rete model to support forms of parallel and distributed processing.

Optimisation and Performance
Several optimisations for Rete have been identified and described in academic literature. Several of these, however, apply only in very specific scenarios, and therefore often have little or no application in a general-purpose rules engine. In addition, alternative algorithms such as TREAT and LEAPS have been formulated which may provide additional performance improvements. There are currently very few commercial or open source examples of productions systems that support these alternative algorithms.

The Rete algorithm is orientated to scenarios where forward chaining and ‘inferencing’ is used to calculate new facts from existing facts, or to filter and discard facts in order to arrive at some conclusion. It is also exploited as a reasonably efficient mechanism for performing highly combinatorial evaluations of facts where large numbers of joins must be performed between fact tuples. Other approaches to performing rule evaluation, such as the use of decision trees, or the implementation of sequential engines, may be more appropriate for simple scenarios, and should be considered as possible alternatives.

The following diagram illustrates the basic Rete topography, and shows the associations between different node types and memories.

 * Most implementations use type nodes to perform the first level of selection on n-tuple working memory elements.  Type nodes can be considered as specialized select nodes.   They discriminate between different tuple relation types.
 * The diagram does not illustrate the use of specialized nodes types such as negated conjunction nodes.  Some engines implement several different node specialisations in order to extend functionality and maximise optimisation.
 * The diagram provides a logical view of the Rete.  Implementations may differ in physical detail.   In particular, the diagram shows ‘dummy’ inputs providing right activations at the head of beta node branches.  Engines may implement other approaches, such as adapters that allow alpha memories to perform right activations directly.
 * The diagram does not illustrate all node-sharing possibilities.

For a more detailed and complete description of the Rete algorithm, see chapter 2 of Production Matching for Large Learning Systems by Robert Doorenbos (see link below).

Rete II
In the 1980s Charles L. Forgy developed a successor to the Rete algorithm named Rete II. Unlike the original Rete (which is public domain) this algorithm was not disclosed. Rete II claims better performance for more complex problems (even orders of magnitude).

title: Expert Systems/Rete Algorithm