Each program language paradigm has some problems which are immediately suited to it. The problem of finding all the permutations of a list of values is a good example of a problem especially suitable to rules. The operation frequently shows up in situations where we must search through all possibilities to find a solution.
Let's state the problem in simple terms. Given a list of values, say letters, find all the possible orders of the letters. We will use this problem to demonstrate some of the fundamental characteristics of production rule systems.
We begin by showing a list as a CLIPS fact. We have a word followed by a sequence of values. If the list is a1 2 3 4 5, then the clips fact may be as: (list 1 2 3 4) The other list will be things like (list 2 3 4 1). We must be given an initial lists and we will use the first mentioned. The CLIPS construct deffacts collects facts that should be initialized every time we reset to begin operation anew. It's shown below:
(deffacts list
(list 1 2 3 4))
So each time we start, there will be a fact that a list has 1, ,2, 3 and 4. We know want to make all the other lists we can from this. The trick is just what you might do in your head. Find two items in the list and swap them. CLIPS rules match named variables to parts of a fact. In our case we want some initial part $?A two items ?x and ?y and a final part $?B. In CLIPS speak, A will match 0 or more values at the beginning, x one, y one and $? B any zero or more remaining values in the list. The things to note are two. The first is that ?x and ?y capture two items somewhere in the list. Any and all remaining are either before these two ($?A) or after ($?B).
(defrule permuteList
(list $?A ?x ?y $?B)
=>
(assert (list $?A ?y ?x $?B)))
The assert just creates a new fact using pieces of the old. The rule system does redo the same rule with the same datum. The inference has already been done. However we have created a new datum.
But notice that there are several ways of matching (list $?A ?x ?y $?B) in (list 1 2 3 4). The possible values for ?x and ?y are 1 and 2 or 2 and 3 or 3 and 4. That means $?A and $?B are () and (3 4) or (1) and (4) or (1 2) and (4). The original fact may be matched in any of three ways. Each is an instantiation of the rule with the fact.. More correctly, a rule system never reuses an instantiation.
If you now imagine the various instantiations being fired. You should realize that different instantiations may repeat facts! Imagine the list with (list 1 2 3 4) and $?A = (). It generates (list 2 1 3 4). But the rule can be instantiated with the new fact and $?A=() which would generate (list 1 2 3 4)!
Every instantiation will be fired, but no duplicates facts are recorded in normal operation. This is a policy called fact refraction. Why record the same fact multiple times?
If we rest and run the clip the code description we have so far, the following facts are made:
f-0 (initial-fact)
f-1 (list 1 2 3 4)
f-2 (list 2 1 3 4)
f-3 (list 2 3 1 4)
f-4 (list 3 2 1 4)
f-5 (list 3 1 2 4)
f-6 (list 1 3 2 4)
f-7 (list 1 3 4 2)
f-8 (list 3 1 4 2)
f-9 (list 3 4 1 2)
f-10 (list 4 3 1 2)
f-11 (list 4 1 3 2)
f-12 (list 1 4 3 2)
f-13 (list 1 4 2 3)
f-14 (list 4 1 2 3)
f-15 (list 4 2 1 3)
f-16 (list 2 4 1 3)
f-17 (list 2 1 4 3)
f-18 (list 1 2 4 3)
f-19 (list 2 4 3 1)
f-20 (list 4 2 3 1)
f-21 (list 4 3 2 1)
f-22 (list 3 4 2 1)
f-23 (list 3 2 4 1)
f-24 (list 2 3 4 1)
The facts are numbered in the order the were recorded so their index is historical.
You should understand that each list fact, first to last, had three instantiations with the permute rule. All those were fired - i.e. executed. that is 24*3=72 rule instantiations fired, each trying to create a fact. All but the 24 recorded were rejected as duplicates to the some earlier fact.Think of the last fact, everything it creates must be a duplicate.
If you did this manually you might use some discipline to make sure you get all possibilities. In rule based system there are three essential disciplines for choosing instantiations to fire. They are depth, breadth and random strategies. Without specifying full details, depth tries to use the newest facts to get farther in a hurry. Breadth tries to get everything out of the old facts before going on. Random is - well random. Below you can see how the results differ from the depth strategy we used at first when we try depth or random strategies.
BREADTH
f-1 (list 1 2 3 4)
f-2 (list 1 2 4 3)
f-3 (list 1 3 2 4)
f-4 (list 2 1 3 4)
f-5 (list 1 4 2 3)
f-6 (list 2 1 4 3)
f-7 (list 1 3 4 2)
f-8 (list 3 1 2 4)
f-9 (list 2 3 1 4)
f-10 (list 1 4 3 2)
f-11 (list 4 1 2 3)
f-12 (list 2 4 1 3)
f-13 (list 3 1 4 2)
f-14 (list 3 2 1 4)
f-15 (list 2 3 4 1)
f-16 (list 4 1 3 2)
f-17 (list 4 2 1 3)
f-18 (list 2 4 3 1)
f-19 (list 3 4 1 2)
f-20 (list 3 2 4 1)
f-21 (list 4 3 1 2)
f-22 (list 4 2 3 1)
f-23 (list 3 4 2 1)
f-24 (list 4 3 2 1)
RANDOM
f-1 (list 1 2 3 4)
f-2 (list 2 1 3 4)
f-3 (list 1 2 4 3)
f-4 (list 2 1 4 3)
f-5 (list 1 4 2 3)
f-6 (list 2 4 1 3)
f-7 (list 4 1 2 3)
f-8 (list 2 4 3 1)
f-9 (list 4 2 3 1)
f-10 (list 4 2 1 3)
f-11 (list 2 3 4 1)
f-12 (list 3 2 4 1)
f-13 (list 3 2 1 4)
f-14 (list 3 4 2 1)
f-15 (list 4 3 2 1)
f-16 (list 4 3 1 2)
f-17 (list 3 4 1 2)
f-18 (list 2 3 1 4)
f-19 (list 3 1 2 4)
f-20 (list 3 1 4 2)
f-21 (list 1 3 4 2)
f-22 (list 1 4 3 2)
f-23 (list 1 3 2 4)
f-24 (list 4 1 3 2)
The moral of all this is: rules can be very concise but they imply a lot of action of the part of the system It's a little little like the difference between mathematics and programming. Knowing something can be done doesn't always mean there is a practicable way of doing it. The failure may be the in ability to describe it to a computer, or it may be the inability to do enough work in reasonable time.
For the sake of the curious., I have used CLIPS to write two more code examples. Each makes permutations. One is in the normal procedural paradigm, i.e. it give a definite series of steps, in terms of sequence, selection and iteration, to be carried out. The second is a nearly pure functional code example. A pure functional language applies functions to arguments, possibly using the same function over (recursion) to get to an answer. Of course no practical language is purely any of these. However for the curious I give the procedural and functional example below without comment.
PROCEDURAL
This was taken from https://en.wikipedia.org/wiki/Heap%27s_algorithm on July 27 2017
I transliterated the original code as nearly simply as I could. I allowed no function except the aset and aget which emulate array operations. I used the flexibility of CLIPS identifiers to make suggestine names for array values. The comments in the CLIPS code show the original procedural code.
Even the original pseudocode is an excellent example of how data structures and sequence can clutter up. Can you find the idea coded there?
; fix indexing base and supply direct 'array' access operation
(deffunction aset (?Array ?inx ?value)
(replace$ ?Array (+ ?inx 1)(+ ?inx 1) ?value))
(deffunction aget (?Array ?inx)
(nth$ (+ ?inx 1) ?Array))
(deffunction proceduralPermute(?n $?A) ;procedure generate(n : integer, A : array of any):
; c : array of int
(bind $?C (create$)) ; for i := 0; i < n; i += 1 do
(loop-for-count ?n ; c[i] := 0
(bind $?C (create$ $?C 0))
) ; end for
(printout t $?A crlf) ; output(A)
(bind ?i 0) ; i := 0;
(while (< ?i ?n) ; while i < n do
(if (< (aget $?C ?i) ?i) ; if c[i] < i then
then
(if (= (mod ?i 2) 0) ; if i is even then
then
(bind ?A[0] (aget $?A 0)) ; swap(A[0], A[i])
(bind ?A[i] (aget $?A ?i))
(bind $?A (aset $?A 0 ?A[i]))
(bind $?A (aset $?A ?i ?A[0]))
else ; else
(bind ?c[i] (aget $?C ?i)) ; swap(A[c[i]], A[i])
(bind ?A[c[i]] (aget $?A ?c[i]))
(bind ?A[i] (aget $?A ?i))
(bind $?A (aset $?A ?c[i] ?A[i]))
(bind $?A (aset $?A ?i ?A[c[i]]))
) ; end if
(printout t $?A crlf) ; output(A)
(bind $?C (aset $?C ?i (+ (aget $?C ?i) 1))) ; c[i] += 1
(bind ?i 0) ; i := 0
else ;else
(bind $?C (aset $?C ?i 0)) ; c[i] := 0
(bind ?i (+ ?i 1)) ; i += 1
) ; end if
) ;end while
)
FUNCTIONAL
For simplicity I do not try to return the list or check that an item is in the list. . Progn$ is doing the work of a map function. The rest is obvious? The permutations will come out in counting order!
; assuming ?item is in the list(s)
(deffunction remove$ (?item $?List)
(delete$ ?List (member$ ?item $?List)
(member$ ?item $?List))
)
(deffunction all-permutations (?sofar $?list)
(if (= (length$ $?list) 0)
then (printout t ?sofar crlf)
else (progn$ (?x $?list)
(all-permutations (create$ ?sofar ?x)
(remove$ ?x $?list)))))
(deffunction permute ($?List)
(all-permutations (create$) $?List))
No comments:
Post a Comment