0

I am creating a heuristic function and it returns what it is supposed to but also there is a stack overflow problem and I can't understand where is the problem. Here is the code of the functions i created:

(defun nextPositions (position)
  (let*((listaPosAdjacentes)
        (positionFinal position)
        (listaFinal NIL))
    (setf listaPosAdjacentes (possible-actions2))
    (dolist (posAdjacente listaPosAdjacentes)
      (setf positionFinal position)
      (setf positionFinal (list (+ (nth 0 positionFinal) (nth 0 posAdjacente))
                                (+ (nth 1 positionFinal) (nth 1 posAdjacente))))
      (push positionFinal listaFinal))
    listaFinal))

(defun push-unique (element lista)
  (let ((auxlist lista))
    (dolist (i lista)
      (if (and (equal (nth 0 i) (nth 0 element)) (equal (nth 1 i) (nth 1 element)))
          (return-from push-unique auxlist)))

    (push element auxlist)
    auxlist))

(defun recursive (track1 positionslist distance track)
  (let ((NextValidPositions NIL))
    (dolist (position positionslist)
      (if (equal (track-startpos track) position)
          (return-from recursive track1)
        (progn (dolist (i (nextPositions position))
                 (if (equal (nth (nth 1 i) (nth (nth 0 i) track1)) T)
                     (progn 
                       (setf NextValidPositions (push-unique i NextValidPositions))
                       (setf (nth (nth 1 i) (nth (nth 0 i) track1)) (+ 1 distance))))))))
    (recursive track1 NextValidPositions (+ 1 distance) track)))

(defun compute-heuristic(st)
  (let* ((track (state-track st))
         (distance 0)
         (track1Final nil)
         (track1heuristica (track-env track)))
    (dolist (position (track-endpositions track))
      (setf (nth (nth 1 position) (nth (nth 0 position) track1heuristica)) distance))
    (setf track1Final (recursive track1heuristica (track-endpositions track) distance track))
    (print track1Final)
    (return-from compute-heuristic track1Final)))

The result is the following: result

The list it returns is what it is supposed to return but I can't understand the stack overflow problem.

The code is called like this:

  (format t "~&Exercise 3.1 - Heuristic~&")
  (with-open-file (str "out3.1.txt"
     :direction :input)
  (format t "~% Solution is correct? ~a~&" (equal (list (compute-heuristic (initial-state *t1*)) (compute-heuristic (make-state :pos '(1 6)  :track track)) (compute-heuristic (make-state :pos '(2 8)  :track track))) (read str))))

It is a local test and this code was provided by our professor to test our code and that's why I think the problem is not there.

Any ideas what the problem might be? Thanks.

5
  • Before delving into this, can you tell us how you call the code? Also, general debugging hint: (trace) all or some of the functions involved in the recursion. Commented Dec 7, 2016 at 20:51
  • FYI, there's a built-in macro PUSHNEW that's like your PUSH-UNIQUE. Commented Dec 7, 2016 at 21:05
  • I don't think the problem is in the code you posted. Since (print track1Final) is executing successfully, the problem is happening after that, so it must be in the code that calls compute-heuristic. Commented Dec 7, 2016 at 21:07
  • 2
    P.S. Please don't post images unnecessarily. Copy and paste from the command prompt as text. Commented Dec 7, 2016 at 21:08
  • I edited the post with the code where the function is called. And thanks for the tips. Commented Dec 7, 2016 at 21:39

1 Answer 1

0

About style:

Generally the code is not well written, since it uses too many control structures and variables which are not really needed.

Example:

(defun push-unique (element lista)
  (let ((auxlist lista))
    (dolist (i lista)
      (if (and (equal (nth 0 i)
                      (nth 0 element))
               (equal (nth 1 i)
                      (nth 1 element)))
          (return-from push-unique auxlist)))
    (push element auxlist)
    auxlist))
  • unnecessary variable auxlist
  • no dolist needed, use member
  • no return-from needed, just return the value. In many case the use of return-from is a code smell, indicating too complicated code.
  • no push needed, just return the result of cons

Better:

(defun push-unique (element list)
  (if (member element list
              :test (lambda (a b)
                      (and (equal (first a) (first b))
                           (equal (second a) (second b)))))
      list
      (cons element list)))

The functionality exists already

The function push-unique exists already in standard Common Lisp. It is called adjoin:

CL-USER 34 > (adjoin 1 '(2 3 4 1 3))
(2 3 4 1 3)

CL-USER 35 > (adjoin 1 '(2 3 4 3))
(1 2 3 4 3)

Just pass the right test function for your purpose...

(defun push-unique (element list)
  (adjoin element list
          :test (lambda (a b)
                  (and (equal (first a) (first b))
                       (equal (second a) (second b))))))

Comments & documentation

Probably it's also a good idea to write comments and documentation. Otherwise one has to guess/infer what the purpose of these functions is.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.