racket - recursion (backtracking) in a search tree

Question

I'm having a problem with the racket language. I want to find a goal state in a list. But in the moment that reaches the limit I gave as parameter I get -> function call: expected a function after the open parenthesis, but received empty. The problem is in expand2.

How do I write this in Racket?

(define (main start limit)  
  (let ([result (expand start limit)])
    (write result)))


(define (expand state limit)
  (cond ((goal state) (list state))
        ((< limit 0) '())
        (else 
         (let ([children (next-states state)]) ;;next states return a list of the kind ((4 3) (2 3))
           (let ((result (expand2 children (- limit 1))))
             (and result (cons state result))))  ;;(append result (cons state result))))) 


         (define (expand2 states limit)                                        
           (if (null? states) 
               (list states) 
               ((expand (car states) limit) 
                (expand2(cdr states) limit))))


(define (next-states state)
    (remove-null
    (list
        (fill-first state)   ;;if state is '(2 3) -> '(4 3) 
        (fill-second state)  ;; and so on
        (pour-first-second state)
        (pour-second-first state)
        (empty-first state)
        (empty-second state)))) 

Thanks

EDIT: I´m trying to write the water jugs problem, where you need to have the first jug with 2 gallons and you have unmeasured jugs of 4 and 3 gallons of capacity. To start the program u use (main '(4 3) 7) for example. 7 is the limit depth of the tree

Answer 1

Searching

Searching nested structures [graph] with backtracking typically requires a queue or a stack or a similar structure to hold temporary state. In Lisps, stacks are easy because it is easy to push elements onto the front of a list with cons and to access the first element of a list with first or car and to take the "popped" list with rest or cdr. Using a list as a stack provides a depth first search.

Handling State

The standard way to handle state in a functional style is passing the state as an additional argument. A typical method is to define an inner function which takes the additional argument and then to call it with a trampoline.

Example Code

This is based on my understanding of the general goal of the question. The specific inputs and outputs can be adjusted depending on your needs:

#lang racket

(define (main start limit)

  (define (success? item limit)
    (equal? item limit))

  (define (inner start limit stack)
    ;; list? any? list? -> any? or null?
    ;; Returns limit on match, null on no match
    (cond 
      ;; There's nothing left
      [(and (empty? start)
            (empty? stack))
       null]
      ;; A list has been exhausted
      ;; So backtrack using the stack
      ;; As start state
      [(empty? start)
       (inner stack limit null)]
      ;; Otherwise look at the first item
      [else
       (let ((item (car start)))
         ;; Does the item match the limit?
         ;; **Remember the limit could be a list**
         (cond 
           ;; If it matches return the matching value
           [(success? item limit) item]
           ;; Otherwise if the item is a list
           ;; Push the elements of item onto the stack
           [(list? item)
            (inner (rest start)
                   limit
                   (append item stack))]
           ;; The item isn't a list and it doesn't match.
           [else (inner (rest start)
                        limit
                        stack)]))]))

  ;; Trampoline the inner function
  (inner start limit null))

Sample Output

> (main '(1 2 3 (4 5) 6) '(4 5))
'(4 5)
> (main '(1 2 3 (4 5) 6) 6)
6
> (main '(1 2 3 (4 5) 6) 4)
4
> (main '(1 2 3 (4 5) 6) 8)
'()

Answer 2

The expression in the alternate branch within expand2

((expand (car states) limit)
 (expand2 (cdr states) limit))

means that you're trying to call the result of the recursive call to expand as a function, but as far as I can see expand never returns a function.

What is it that you actually want to do in this branch?

EDIT:

While I still don't fully understand how your current code is supposed to work, I think some instructions how to implement backtracking with recursion should help you:

The recursive call should be able to go onto all possible branches that follow from the current state. Each time a recursive call returns, check whether it has returned a valid final result - in which case you simply return again to the next higher level -, or if it's a special result that represents failure - in which case you make the next recursive call if there are still branches from the current state remaining, or also return the special result if you've exhausted the possible branches.

EDIT 2:

Here is some example code that should hopefully clarify the basic ideas I explained above about how to do backtracking with recursion. Interesting to note is that the Racket standard library function ormap can do a significant portion of our work for us:

(define (backtrace state)
  (if (goal state)
      (list state)
      (let [[result (ormap backtrace (next-states state))]]
        (and result (cons state result)))))

Answer 3

Racket has this very nice IDE called DrRacket. It will ident the code you're writing according to the code structure. Pressing CTRL+i will "fix" identation for you when you edit code so press it often. Inidented code in LISPy languages are unreadable!

From your original formatting it was not clear to see that the definition of expand2 was inside expand at a illegal place (local definitions goes on the top), but with proper indentation you see it's there.

There are lots of strange things in you code. One is the missing parentheses that makes this program invalid from the start.

Another is the fact you have two applications that themselves are surrounded by parenthesis:

((expand (car states) limit) (expand2 (cdr states) limit))

If you compare that to eg.

(- 10)

You see that (expand (car states) limit) needs to become a procedure, just like the variable - becomes a procedure. Here you either have forgot an operand. eg. (cons expr-1 expr-b) or if there are side effects perhaps you wanted a (begin expr-1 expr-2).

DrRacket has a pretty decent debugger once your application is without syntax errors. You can step through your code and find your other bugs as well. Give it a try!

Answer 4

If (expand (car states) limit) return empty, then

( (expand (car states) limit) 
        (expand2(cdr states) limit))

is the same as (empty ...) and you will get the error function call: expected a function after the open parenthesis, but received empty