2

I am a new lisp programmer, I am having trouble wrapping my head around recursion in lisp. I have a series of expressions that I simplify by going through a series of methods that replace symbols with numbers and then I will evaluate the expression. Before evaluation I substitute symbols for numbers, in doing that I get a stack overflow error in my subst-bindings method and/or when I call the deep-subst method from within that method. Any help or advice on my recursive method calls that would help me understand better I would greatly appreciate it! My code is below--

    (setq p1 '(+ x (* x (- y (/z 2)))))
    (setq p2 '(+ (- z 2) (* x 5)))
    (setq p3 '(+ 1 a))


    (defun deep-subst (old new l)
      (cond
       ((null l) 
         nil
       )
       ((listp (car l))
        (cons (deep-subst old new (car l)) (deep-subst old new (cdr l)))
       )
       ((eq old (car l)) 
        (cons new (deep-subst old new (cdr l)))
       )
       (T   
        (cons (car l) (deep-subst old new (cdr l)))
       )
      )
    )

    (defun subst-bindings (bindinglist exp)
      (cond 
        ( (null bindinglist) 
           exp )
        (T
           (subst-bindings  (cdr bindinglist)(deep-subst (car (car bindinglist)) (cdr (car bindinglist)) exp))
        )
       )
     )

    (defun simplify (exp)
        (cond
         ( (listp exp)
          (simplify-triple (car exp) (simplify (car(cdr exp)))(simplify (car (cdr (cdr exp)))))
        (T
           exp))))

    (defun evalexp (binding-list exp)
        (simplify (subst-bindings binding-list exp))
    )
      (evalexp '( (x 2) (z 8) ) p1)  ;Where I call evalexp from and gives me the stack overflow error
Improve this question
7
  • 1
    It would be more helpful if you can show just the smallest amount of code and a test case which reproduce the problem, along with the error message that you receive. Common Lisp also includes a trace macro, so that if you were to do (trace deep-subst), you'll see all the calls to deep-subst, and you'll probably find the problem. Commented Oct 1, 2014 at 17:29
  • I will give the trace a try, I also took out code that was not necessary or helpful to seeing an issue. The last line of code is an example test case where I call evalexp Commented Oct 1, 2014 at 17:43
  • 1
    I think you may want to debug some more. The problem doesn't appear to be solely in the substitution functions. E.g., pastebin.com/NWHPK5PF runs without a problem (although the result may not be what you expect it to be; should that bindinglist be '((x . 2) (z . 8))?). That suggests that something is awry in simplify. Commented Oct 1, 2014 at 17:48
  • Hmmmm very interesting I did not think to cut it all out and test them separately, I believe you are right I need to look at simplify closer. Commented Oct 1, 2014 at 17:55
  • 1
    @Branbron I'll mention one thing though; when I ran the sample that I linked to in my previous comment, I noticed that your substitution algorithm takes bindings of the form (a . b) to replace a with b. In the bindings you've used, you'll be replacing x with (2) and z with (8). Each of those is a list, so there will be more structure that you could recurse on. It wouldn't be too hard to make a mistake there. Commented Oct 1, 2014 at 18:44

1 Answer 1

Reset to default
3

The problem lays in the simplify function as trace proofs

(trace simplify)

(evalexp '( (x 2) (z 8) ) p1)
0: (SIMPLIFY (+ (2) (* (2) (- Y (/Z 2)))))
    1: (SIMPLIFY (2))
      2: (SIMPLIFY NIL)
        3: (SIMPLIFY NIL)
          4: (SIMPLIFY NIL)
            5: (SIMPLIFY NIL)
              6: (SIMPLIFY NIL)
                7: (SIMPLIFY NIL)
                  8: (SIMPLIFY NIL)
                    9: (SIMPLIFY NIL)
                      10: (SIMPLIFY NIL)
                        11: (SIMPLIFY NIL)
                          12: (SIMPLIFY NIL)
                            13: (SIMPLIFY NIL)
                              14: (SIMPLIFY NIL)
                                15: (SIMPLIFY NIL)
                                  16: (SIMPLIFY NIL)
                                    17: (SIMPLIFY NIL)
                                      18: (SIMPLIFY NIL)

And if we take a look at the function

(defun simplify (exp)
        (cond
          ((listp exp)
           (simplify-triple 
              (car exp) 
              (simplify (car(cdr exp)))
              (simplify (car (cdr (cdr exp)))))
          (T
            exp))))

We can see that the recursion is based on the function listp. If listp returns true then simplify-triple will be called which has two calls to simplify as parameters. As we can see in the trace simplify is called with nil over and over again and if we test (listp nil) we can see that it returns T (which makes sense as it represents the empty list) therefore leading to the endless recursion.

You'll have to base your recursion on another (or more throughout) if-condition.

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

3 Comments

I'll play around with checking the return value in a different way, thanks for helping me understand!
you could use something like (and (listp exp) exp) to ensure that you will not use nil as and will interprete nil as the boolean false
The usual way to test for the end of the list is with endp.

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.