Qi Programming Basics: Where Guards and Backtracking
Qi Programming Basics: Where Guards and Backtracking.In Pattern Matching Basics, we learned about values that must match literals or named parameters. We also learned that this pattern matching can fail. We learned that on the right hand side, you can return a value when the left hand side matches. But what if we want to ensure our variable matches also meet some other specific conditions?
Having covered the left hand side of the arrow operator, we can now cover the right hand side of the -> operator, which deals with restricting function calls. The “where” allows us to call whatever function we want to and have it return only if said “where’ function returns true. If the where returns false, we continue down the function definitions until we find both a left hand pattern match, and a right hand “where” clause satisfaction. Let us take a simple example, greater-than-10
(define greater-than-10
X -> true where (> X 10)
_ -> false
)
(11-) (greater-than-10 20)
true
(12-) (greater-than-10 5)
false
Just as the pattern matching side acts as a sieve for the structure of the input, the where clause acts as functional sieve to ensure that the data matches certain parameters. It makes it easy to define recursive functions. Simply specify the basic cases first and the recursive cases after. The prime? function given in the Qi language book shows this behavior well and I’ll include it here
(define prime?
X -> (prime1? X (sqrt X) 2))
(define prime1?
X Max Div -> true where (> Div Max)
X Max Div -> false where (integer? (/ X Div))
X Max Div -> (prime1? X Max (+ 1 Div)))
So prime calls prime1? setting X to the prime we want to test for, Max to the sqrt of X to limit the prime testing, and Div to 2. If the Div is greater than the Max, it returns true because obviously we have tested for primeness up to the sqrt of X. If it finds any integer divisors, the number is obviously non prime so it returns false. If we pass the first 2 where clauses, then we know we need to test another number so it adds 1 to Div and calls itself recursively and thus walks up to Div > Max. This specifies the prime numbers and is easy to read, but inefficient.
So now that we understand the simple basics of the where clause, we use them to implement some very interesting constructs. Qi provides some syntactic sugar to make writing these sorts of constructs easier, but we should remember that we are only truly dealing with the “where” clause fundamentally. We need to learn about a few new important operators and a new literal. First, we introduce the <- notation that we use instead of -> to signify that if the pattern on the left matches, and the function on the right does not fail, then we can return the result. We specify the idea of “failure” by the literal #\Escape, which is also known as the failure object. We will also introduce a form called “fail-if” that can help make these functions more readable and robust.
Let us begin with a simple case of a binary tree of numbers built out of lists. We will use the empty list to signify a null tree. So we have structures like [L X R] where L and R are lists of that type or empty lists.
(62-) [[[[] 4 [] ] 2 [[] 5 []]] 1 [ [[] 6 []] 3 [ [] 7 []] ]]
[[[[] 4 []] 2 [[] 5 []]] 1 [[[] 6 []] 3 [[] 7 []]]]
Now let us use an old backtracking standby of the computer science world, DFS. DFS, for those who do not know, stands for Depth First Search. A DFS goes to the left hand side and right hand side while printing its way around the list. How it prints depends on if we have want a preorder DFS, an inorder DFS, or a postorder DFS. You can find more on the concept at the Wikipedia Tree Search Algorithm page. We can define a tree that looks like the tree on that page as follows. (Here we use the “set” function to set a symbol to the value of the list, to make things easier to read.)
(70-) (set *b-list* [ [[[] g []] h [[[] f []] i [[] e []]]] a [[] b [[[] d []] c []]] ] )
[[[[] g []] h [[[] f []] i [[] e []]]] a [[] b [[[] d []] c []]]]
So how can we use the backtracking operator and the #\Escape symbol to implement this algorithm? First, we must note that we will need to return the #\Escape object for every result. This will ensure that our backtracking operations continue to happen even after we have matched something successfully and have “done” something (in this case print out an element). The basic case is when we have an empty node of only one element, for example [ [] 7 [] ] should print 7 and return the failure object.
[[] X []] -> (do (output "~A " X) #\Escape)
That accomplishes that for us. It is also the base case so we can put it at the top of the function. Obviously, we don’t want it to backtrack, as it is the basic case, so we use the -> operator to indicate that we wish to stop backtracking when this rule matches. But note that it does return the #\Escape element, as we don’t’ know where we are in the tree and we want any additional backtracking left on the stack to continue. The important point to remember is when a function returns something other than #\Escape, we halt the computation.
What about the rest of the function? It depends on if we want preorder, inorder, or postorder printing of elements. We will start with the preorder case as we can follow the computation a bit more easily. It should print the first element, then print the left tree, then print the right tree. But at each of those operations, we want it to backtrack and continue on even after it has printed or displayed part of the tree for us. In this way, we can use the function stack as our “visit” stack. (Stacks are a requirement of DFS) By going back up the computational stack, we can find the next element that we should print. For Preorder we have
[L X R] <- (do (output "~A " X) #\Escape) [L X R] <- (dfs-pre L) [L X R] <- (dfs-pre R) So what this means is that it prints out the X, then returns #\Escape which fails. This causes us to backtrack to the next rule, the (dfs-pre L) rule. Note that this also uses the <- operator, so when it finishes with an #\Escape (which is the only thing our function returns) we then can go to the (dfs-pre R) rule. But what happens when the (dfs-pre R) rule fails? We want another default case to return #\Escape for any computation that has gone this far. _ -> #\Escape
Putting this together gives us the following definition.
(define dfs-pre
[[] X []] -> (do (output "~A " X) #\Escape)[L X R] <- (do (output "~A " X) #\Escape)
(86-) (dfs-pre (value *b-list*))
[L X R] <- (dfs-pre L)
[L X R] <- (dfs-pre R)
_ -> #\Escape
)
a h g i f e b c d #\Escape
The letters above are the results from the “output” function. The #\Escape is the end of our computation, as our function only returns #\Escape, we should not feel surprised to see it at the end of our output from the top level.
We can accomplish post order by simply switching around the order that the function calls come in the list. Instead of printing first and backtracking to dfs L and dfs R, we can put the print at the end and come up with postorder.
(define dfs-post
[[] X []] -> (do (output "~A " X) #\Escape)
[L X R] <- (dfs-post L)
[L X R] <- (dfs-post R)
[L X R] <- (do (output "~A " X) #\Escape)
_ -> #\Escape
)
(88-) (dfs-post (value *b-list*))
g f e i h d c b a #\Escape
And finally, we can define inorder as the following, by placing the print in between the L and R cases.
(define dfs-in
[[] X []] -> (do (output "~A " X) #\Escape)
[L X R] <- (dfs-in L)
[L X R] <- (do (output "~A " X) #\Escape)
[L X R] <- (dfs-in R)
_ -> #\Escape
)
(89-) (dfs-in (value *b-list*))
g h f i e a b d c #\Escape
Now if you input the following at the top level and run that program again, you will be able to see each of the inputs and watch how the #\Escape return values help move this backtracking along.
(91-) (track dfs-in)
dfs-in
(92-) (step +)
True
Long time computer science types will realize that this is a foolish way to handle DFS, and I would like to point out that I chose this method because walking trees is fairly well known and simply helps us learn. We can define a DFS inorder much easier by simply appending lists together. It takes no more lines in Qi than it does in Haskell.
(define dfs-pre*
[] -> []
[L X R] -> (append (append [X] (dfs-pre* L)) (dfs-pre* R)) )
(95-) (dfs-pre* (value *b-list*))
[a h g i f e b c d]
Nicer, but not my point. *smile*
Now perhaps we want to fail on a specific test of a result as opposed to using only the #\Escape operator to handle backtracking. Could our dfs function return true and still allow for backtracking? Fortunately, Qi provides us with a special form called “fail-if” that does exactly that. It takes in a function and a value. It tests to see if the value causes the function to return true. If it dose, it starts backtracking. If the test returns false, however, it stops backtracking. It basically means “backtrack if true”. Let us make a version of dfs-pre that uses these semantics.
(define dfs-pre
[[] X []] -> (do (output "~A " X) true)
[L X R] <- (fail-if (/. Y Y) (do (output "~A " X) true))
[L X R] <- (fail-if (/. Y Y) (dfs-pre L))
[L X R] <- (fail-if (/. Y Y) (dfs-pre R))
_ -> true
)
(111-) (dfs-pre (value *b-list*))
a h g i f e b c d true
Now after listing this form, try to see how the backtracking operator connects to the “where” clause described earlier. We have a test like in where. (/. Y Y), and we pass over clauses that do not match this test. All we are missing is a way to ensure that we don’t double up on the clauses. We want to return the clause AND test it in our where. Let us try a final rewrite of dfs-pre that uses only the usual -> operators and the where. We would like it to look like.
(define dfs-pre
[[] X []] -> (do (output "~A " X) true)
[L X R] -> (let Result (do (output "~A " X) true)
Result) where (not Result)
[L X R] -> (let Result (dfs-pre L)
Result) where (not Result)
[L X R] -> (let Result (dfs-pre R)
Result) where (not Result)
_ -> true
)
However, you can see the Result variable goes out of scope at the end of the let and thus is not available to the where clause. If you tried to compile this you would get
======> Warning:
the following variables are free in dfs-pre: Result;
But you should remember that Qi deals with this internally and we can simply use the expressive power of the <- and fail-if operators to handle our backtracking for us.
Obviously, that serves as only the beginning of what we can accomplish with backtracking in Qi. In chapter 7 of the language book, we find a proplog based system that uses backtracking to build a backward chaining proof procedure. Hopefully, this guide should give you enough background on how the Qi where clause works so that you can fully understand the code in that chapter.
I hope you enjoyed this little guide to the Qi where clause and backtracking in general. Using backtracking can greatly enhance the expressiveness of your program and provide a powerful syntax for dealing with recursion and non-determinism. Please let me know any questions or comments that you have!
1 Comments:
Thank's for your posts about Qi and how to program types. They are very instructive and always fun to read!
