Lisp Infinite Recursion

问题:

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

回答1:

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.