Bubble sort (CLIPS)

From LiteratePrograms

Other implementations: C | CLIPS | C++ | C# | Eiffel | Erlang | Io | Java | Lisp | Smalltalk

NASA CLIPS[1] the (C Language Integrated Production rule System) matches rules against facts choosing one possible match (an 'instantiaion') to perform ('fire') and then repeating the process as long as possible.

Below we show two ways to 'bubble' sort a sequence of values, first when they are collected into a single long list (called a 'multifield) and then when they are independent but indexed facts.

Sorting in a Simple Fact

<<bubbleSortNumericMultifield.clp>>=
(defrule sort 
    (data $?X ?a ?b $?Y)
    (test (< ?b ?a))
=>
    (assert (data $?X ?b ?a $?Y)))

The data fact is simply a list of numbers like '(data 51 33 87 1 200)'. The patterns $?X and $?Y match any 0 or more umbers, so the two numbers ?a and ?b may are a pair anywhere in the list. There are generally many ways to match a fact! The test '(test (< ?b ?a))' makes sure that ?a < ?b in the fact match. When everything matches we have an "instantiation".

One chosen instantiation is fired. Here the only action is to make a new fact similar to the old, but with these two elements now in order. Note we are not assured of the order of swaps as we would be in a procedural language.

Since the rule is applied to exhaustion, MANY data facts will be made. Since each will have 1 less set of 'out of order' elements, eventually we will reduce the out of order number to zero. For the same reason we must stop eventually - since CLIPS does not normally record duplicate facts, thereby avoiding a possible infinite regression.

We can avoid the plethora of facts by removing old facts as we make new. The fact assignment '?f<-' captures an id of the matched fact. The retract function removes it from memory.:

<<bubbleSortNumericMultifieldDeterminate.clp>>=
(defrule sort 
?f<-(data $?X ?a ?b $?Y)
    (test (< ?b ?a))
=>
    (retract ?f)
    (assert (data $?X ?b ?a $?Y)))

We are still correct:

Since the rule must reduce the number of out-of-order's we must stop.
Since it stops only when none are out of order we are sorted (Turn around the test for descending order.)

Of course we could use a test other than '<' for other types, even mixed types, so our routine is quite general - as long as we have a single fact.

Sorting Facts

To sort individual facts we need some index to tell the place in the order. We assume unique random places to start with. Here we also keep the bubble sort characteristic of swapping only adjacent pairs by adding a test for that: (test (= (+ ?place1 1) ?place2))

<<bubbleSortNumericIndexedFacts.clp>>=
(defrule bubble
?f<-(datum ?datum1 ?place1)
?g<-(datum ?datum2 ?place2)
    (test (> ?datum1 ?datum2))
    (test (= (+ ?place1 1) ?place2)))   ; (< ?place1 ?place2) is better, but no known sort
=>
    (retract ?f ?g)
    (assert (datum ?datum1 ?place2)
            (datum ?datum2 ?place1))
)

The reasoning for correctness is similar to the previous: The rule fires whenever then is an adjacent pair out-of-order. It stops when no adjacent pairs are out of order.

Of course more complex data sorts would require a specific comparison, but we still only need to find the data order and the current place.