Recursion with multiple matches

[mvpeterson]

Monkey and banana problem

Initial state: Monkey is at door, Monkey is on floor, Box is at window, Monkey does not have a banana

(state at_door on_floor at_window hasnot)

The target state: Monkey is at the middle of the room, Monkey is on box, Box is at the middle, Monkey has the banana (state at_middle on_box at_middle has)

Allowed moves: Grasp banana (move (state at_middle on_box at_middle hasnot) (grasp) (state at_middle on_box at_middle has))

Climb box (move (state $p on_floor $p $h) (climb) (state $p on_box $p $h))

Push box from p1 to p2 (move (state $p1 on_floor $p1 $h) (push $p1 $p2) (state $p2 on_floor $p2 $h))

Walk from p1 to p2 (move (state $p1 on_floor $b $h) (walk $p1 $p2) (state $p2 on_floor $b $h))

(= (_move $state1 $m $state2) (match &self (move $state1 $m $state2) (trace! ($state1 $m $state2) $state2)))
(= (_canget (state $x $y $z $h)) ( if (== $h has) True (_canget (_move (state $x $y $z $h) $m $state2))))

This command don't get out of recursion !(_canget (state at_door on_floor at_window hasnot))

But if I call the (_move) function on certain states step by step, it can be seen that the target state can be reached.

!(_move (state at_door on_floor at_window hasnot) $m $state2)
;[(state $p2#2566 on_floor at_window hasnot)]

!(_move (state $x on_floor at_window hasnot) $m $state2)
;[(state $p2#10412 on_floor at_window hasnot), (state at_window on_box at_window hasnot), (state $p2#10406 on_floor $p2#10406 hasnot)]

!(_move (state $x on_floor $x hasnot) $m $state2)
;[(state $p2#28360 on_floor $x hasnot), (state $x on_box $x hasnot), (state $p2#28354 on_floor $p2#28354 hasnot)]

!(_move (state $x on_box $x hasnot) $m $state2)
;[(state at_middle on_box at_middle has)]

For the second call I get three matches, and the desired option is the third. Does this mean that it will never be selected because subsequent recursion calls will use the options preceding the third one, and they will also produce several options in turn? Will the first option be taken and will it be evaluated until it is reduced? And after that the second option will be processed and so on?

[DaddyWesker]

Does this mean that it will never be selected because subsequent recursion calls will use the options preceding the third one

As i understand non-determinism in Metta, it will be used of course. Moreover, all three variants will be used and will produce several variants of consequent moves. And in the end you should receive several ending states also.

Also it is possible that metta just evaluating too long and it will end with some results when you calls _canget and not caught in endless recursion. Unfortunately, it is unclear what exactly going on since there are no step-by-step debug option in Metta. You can try to just print what is going on with println! Possible way to print and move deeper to recursion calls is something like that (from my SICP examples):

(= (car $x)
    (car-atom $x))

(= (cdr $x)
    (cdr-atom $x))

(= (for-each $proc $list)
    (if (== $list ())
        ()
        (let*
        (
            (() ($proc (car $list)))
            (() (for-each $proc (cdr $list)))
        )
        ())))

!(for-each println! (57 321 88))

Though you probably know this already.

[Necr0x0Der]

@mvpeterson , yes, your program will try to enumerate all possible ways of achieving the goal. It will not terminate, when the first solution is found. There will always be a branch of non-deterministic evaluation with the monkey just walking back and forth. At the moment, we don't have a way to turn non-determinism into a controllable search. Although we have plans to do exactly this in the future. As for now, you can introduce a counter, e.g.

(= (_canget (state $x $y $z $h) $count)
   (if (== $count 0)
       (empty)
       (if (== $h has)
           True
           (_canget (_move (state $x $y $z $h) $m $state2) (- $count 1)))))
!(_canget (state at_door on_floor at_window hasnot) 5)

There is an additional problem that if there is no move from some state, _move will not be reduced. There are different ways of making this search to work somehow via basic non-determinism, but I'd say that it is a good example for further work of turning non-determinism into an inference/search engine.

[Necr0x0Der]

Also, tree search is not always good for solving problems with states. A* algorithm should do better. Not sure if the support for it should be built into the interpreter, inference engine, or a core library, though. But in any case, this example (possibly with some refactoring) can be good for a tutorial demonstrating some pitfalls in using vanilla non-determinism.