Stack Overflow with BFS LISP

Question

I have created a search function following the BFS algorithm but found a problem, it works fine on other problem domains but on this problem domain I am only getting stack overflows.

This specific problem domain is a modified mancala game where the solution is the minimum number of moves to make until the board '((2 4 6 8 10 12) (12 10 8 6 4 2)) is completely empty. There is only one player and he can play wherever.

I think it is due to tail recursion not being optimized but im not sure why, here is my code:

(defun remove-existing (l closed algorithm)
  "Removes nodes from L that are already in CLOSED."
  (remove-if (lambda (node) (or (null (node-state node)) (node-existsp node closed algorithm))) l)
)

(defun check-solution (l objective)
  "Returns the first node in L that satisfies OBJECTIVE, or NIL if none do."
  (find-if objective l)
)

(defun bfs-open (nodes-open nodes-children)
  "Puts the children nodes NODES-CHILDREN at the back of NODES-OPEN."
  (append nodes-open nodes-children) ; We can just append the children to the back.
)

(defun bfs (initial-node objective generator operators)
  (let 
    (
      (open (list initial-node))
      (closed nil)
    )
    (labels 
      ((bfs-go 
        ()
        (cond 
          ((null open) nil) ; If open is empty, return nil, no solution.
          (t (let* 
            (
              (first-node (car open)) 
              (new-closed (append closed (list first-node))) 
              (children (remove-existing (funcall generator first-node operators 'bfs) new-closed 'bfs))
              (new-open (bfs-open (cdr open) children))
              (solution-node (check-solution children objective))
            )
            (cond 
              ((not (null solution-node)) solution-node)
              (t 
                (setf open new-open)
                (setf closed new-closed)
                (bfs-go))
            )
            ))
          )
        )
      )
      (
        bfs-go
      )
    )
  )
)

This is what the generator function looks like:

(defun generate-children (node operator algorithm &optional (max-depth 0) heuristic)
  "Goes through every line and row, creating a child for every possible move (as long as the move is valid)."
  (labels 
    (
      (children-helper (i1 i2)
        (cond 
          ((or (null node) (null operator) (> i1 1)) nil) ; We have ran through board lines.
          ((= i2 6) (children-helper (+ i1 1) 0)) ; We have ran through line indexes.
          ((null (node-state (new-child node operator algorithm i1 i2))) (children-helper i1 (+ i2 1))) ; The move is invalid, no need to keep the child.
          ((eq algorithm 'a-star) (cons (new-child node operator algorithm i1 i2 heuristic) (children-helper i1 (+ i2 1)))) ; If the algorithm is A*, we need to pass the heuristic.
          (t (cons (new-child node operator algorithm i1 i2) (children-helper i1 (+ i2 1)))) ; We create a new child and move to the next, without a heuristic.
        ))
    )
    (cond 
      ((null node) nil) ; Node is nil, we don't create any children.
      ((and (eq algorithm 'dfs) (>= (node-depth node) max-depth)) nil) ; If the current node has reached the max depth, we don't create any children.
      (t (progn 
        (set-expanded-nodes (+ (get-expanded-nodes) 1)) ; Increment the number of expanded nodes.
        (children-helper 0 0)) ; We create children for this node.
      ) 
    )
  )
)

The stack frame is being filled up with bfs-go, for context my BFS function generates about 12 nodes per child (maximum case scenario) and there is virtually no limit to how far it could go. This is what the backtrace gives me:

Call to INVOKE-DEBUGGER
Call to ERROR
Interpreted call to REPLACE-POSITION
Interpreted call to REPLACE-VALUE
Interpreted call to INCREMENT-VALUE
Interpreted call to GAME-OPERATOR
Call to FUNCALL
Interpreted call to NEW-CHILD
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS CHILDREN-HELPER) :UNKNOWN)
Interpreted call to GENERATE-CHILDREN
Call to FUNCALL
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to (SUBFUNCTION (LABELS BFS-GO) :UNKNOWN)
Interpreted call to BFS
Call to INITIALIZE
Call to EVAL
Call to CAPI::CAPI-TOP-LEVEL-FUNCTION
Call to CAPI::INTERACTIVE-PANE-TOP-LOOP
Call to MP::PROCESS-SG-FUNCTION

I am using LispWorks 8.0.1. This is for a school assigment and we were recommended to use recursion but im always hitting stack overflow.

In general, a recursive function should take a parameter, and it should test that parameter to tell if it has reached the base case. Using an external variable like open is poor design. I haven't really traced it myself, but I suspect that's the problem. — Barmar
– Barmar, Commented Feb 10 at 16:51
As @Barmar says, recursive procedures usually recurse on their arguments; I doubt that this is what our instructor has in mind. "I think it is due to tail recursion not being optimized" -- note that Common Lisp doesn't require TCO, but LispWorks does do it. — ad absurdum
– ad absurdum, Commented Feb 10 at 17:40
Regarding style: if you want experienced lisp programmers to review your code you should at least write it in a somewhat idiomatic style. Don't scatter parenths all over different lines like they are curly braces. The posted code is very hard to read: many parentheses taking up way too many lines, and many lines which contain way too many expressions. Use indentation to format your code so that it is readable. And calling bfs-go over three lines with the parentheses on two of those lines (at the end of bfs) is just inexcusably bad style. — ad absurdum
– ad absurdum, Commented Feb 10 at 17:44
Does remove-existing work as intended? are you sure you do not have an infinite cycle somewhere due to nodes being children of their children? — coredump
– coredump, Commented Feb 11 at 13:58

JauneMrG · Accepted Answer · 2025-02-11 09:13:05Z

1

IIRC, "Interpreted call to" don't do tail call optimisation?

Compile the function and try it again. I.e.

(compile 'generate-children)

etc.

Or (compile-file ...)

edited Feb 11 at 9:13

answered Feb 11 at 8:58

JauneMrG

112 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Community Feb 12 at 0:38

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Collectives™ on Stack Overflow

Stack Overflow with BFS LISP

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related