Representing Non-Determinism

EntropyFails (http://programmingkungfuqi.blogspot.com/2006/04/qi-programming-basics-where-guards-and.html) chose an nice example - depth-first search - to illustrate the handling of non-determinism in Qi. For people new to Qi you can also find the relevant chapter on non-determinism in my online book (chapter 7).

Perhaps readers would find some interest in a typed higher-order version of depth first search which is domain-neutral (i.e. not constrained to any particular domain).

The Basics

What does depth-first search need? A basic version needs

a. An initial start State.
b. A Successors function that maps any State to a list of Successor States.
c. A Goal? function that tests a state to see if it is a goal state.

To this bread and butter version I add one extra ingredient.

d. A Fail? function that tests a State and sees if it should trigger backtracking.

Using these ingredients, we can build a higher-order typed depth-first search function. First the code without comments; then the comments.

Code

(define depth
{A --> (A --> [A]) --> (A --> boolean) --> (A --> boolean) --> boolean}
State Successors Goal? Fail? -> (depth-help [State] Successors Goal? Fail?))

(define depth-help
{[A] --> (A --> [A]) --> (A --> boolean) --> (A --> boolean) --> boolean}
[State | _] _ Goal? _ -> true where (Goal? State)
[State | _] _ _ Fail? -> false where (Fail? State)
[State | _] Successors Goal? Fail? <- (fail-if (/. X (= X false)) (depth-help (Successors State) Successors Goal? Fail?))
[_ | States] Successors Goal? Fail? -> (depth-help States Successors Goal? Fail?)
_ _ _ _ -> false)

Comments

depth takes a initial start state; a successor function that maps a state to a list of successor states, a function that tests a state to see if it is a goal state, and a test for failure. Lets look at depth-help line by line. The first two lines are just name and type; the next line is:

1. [State | _] _ Goal? _ -> true where (Goal? State)

means 'return true if the State is a goal state'

2. [State | _] _ _ Fail? -> false where (Fail? State)

means 'return false if the State is a failure state'

3. [State | _] Successors Goal? Fail?
<- (fail-if (/. X (= X false)) (depth-help (Successors State) Successors Goal? Fail?))

means 'recurse using the State at the head of the list and fail under the condition that the function returns 'false'. Notice the use of <- rather than ->. This is important. EntropyFails explains how it works in his post quite well. So I'll quote him here.

"..... 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 does, it starts backtracking. If the test returns false, however, it stops backtracking. It basically means "backtrack if true"."

4. [_ | States] Successors Goal? Fail? -> (depth-help States Successors Goal? Fail?)

means 'If control has got to this point then, the first State has failed so have a look at the others.'

5. _ _ _ _ -> false

means that we've gone through all the successor states and found nothing - so return 'false'.

Trial

Lets try it. Here is a problem

From 4 can I make 27 by adding 3, 4 and 5 in any order?

This can be phrased as a search problem. The start state is 4, the goal function is (/. X (= X 27)) (that is, is X 27?, remember Qi uses /. for a lambda). Failure occurs if we exceed 27 (that is, (/. X (> X 27)) returns true when applied) and the successors function adds the current number to 3,4 and 5 and forms a list of the results (that is, (/. X [(+ X 3) (+ X 4) (+ X 5)])).

(8+) (depth 4 (/. X [(+ X 3) (+ X 4) (+ X 5)]) (/. X (= X 27)) (/. X (> X 27)))
true : boolean

Yes this can be done!

From 4 can I make 27 by adding 3?

(9+) (depth 4 (/. X [(+ X 3)]) (/. X (= X 27)) (/. X (> X 27)))
false : boolean

No it cannot.

Returning a Path

Well, true and false are not very informative really. So lets add an extra input and change the types of the functions. First I switch off the type checker and wipe the board clean.

(10+) (tc -)
false : boolean

(11-) (destroy depth)
depth

(12-) (destroy depth-help)
depth-help

(13-) (tc +)
true

This removes the functions and their types from the environment. I'm back in to the type checker again.

(You can overwrite types in Qi, but it's not type-secure and the top level tells you off before complying. So lets be good and avoid the telling off.)

We add an extra argument Path in depth-help that maintains the path to our solution. Every time we apply the Successors function to a State in travelling down a branch we push
the State onto the Path. Our failure object is the empty Path ([]) which is what we get if there is no path. Otherwise if we find a solution, we return the Path (in reverse order because we want the goal State last).

Here is the new program - only 1 line longer than the last one.

(define depth
{A --> (A --> [A]) --> (A --> boolean) --> (A --> boolean) --> [A]}
State Successors Goal? Fail? -> (depth-help [State] Successors Goal? Fail? []))

(define depth-help
{[A] --> (A --> [A]) --> (A --> boolean) --> (A --> boolean) --> [A] --> [A]}
[State | _] _ Goal? _ Path -> (reverse [State | Path]) where (Goal? State)
[State | _] _ _ Fail? _ -> [] where (Fail? State)
[State | _] Successors Goal? Fail? Path <- (fail-if empty? (depth-help (Successors State) Successors Goal? Fail? [State | Path]))
[_ | States] Successors Goal? Fail? Path -> (depth-help States Successors Goal? Fail? Path)
_ _ _ _ _ -> [])

Give me a path from 4 to 27 by adding 3, 4 or 5.

(14+) (depth 4 (/. X [(+ X 3) (+ X 4) (+ X 5)]) (/. X (= X 27)) (/. X (> X 27)))
[4 7 10 13 16 19 22 27] : (list number)

Give me a path from 4 to 27 by adding 3 only.

(15+) (depth 4 (/. X [(+ X 3)]) (/. X (= X 27)) (/. X (> X 27)))
[] : (list number)

The verdict is there isn't one.

This is a polymorphic program, so you can experiment with this program in different domains than the numeric example given here.

This post is taken from the thread at the Qilang news group. You can post your discussion here.

Have fun.

Mark