admin管理员组

文章数量:1302913

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.

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.

  • lisp
  • common-lisp
  • stack-overflow
  • breadth-first-search
  • lispworks
Share edited Feb 10 at 22:09 Christoph Rackwitz 15.6k5 gold badges39 silver badges51 bronze badges asked Feb 10 at 11:27 hrodrichrodric 4353 silver badges13 bronze badges 7
  • 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 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 Commented Feb 10 at 17:40
  • 1 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 Commented Feb 10 at 17:44
  • 1 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 Commented Feb 11 at 13:58
  • 1 Can you also include the definition of node-existsp? – coredump Commented Feb 12 at 14:30
 |  Show 2 more comments

1 Answer 1

Reset to default 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 ...)

本文标签： Stack Overflow with BFS LISP

版权声明：本文标题：Stack Overflow with BFS LISP 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1741719152a2394285.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。