recursion - Lisp 无限递归

Question

我是一名新的 lisp 程序员，我在理解 lisp 中的递归时遇到了困难。我有一系列表达式，通过一系列用数字替换符号的方法来简化它们，然后我将计算表达式。在评估之前，我用符号替换数字，这样做时，我在 subst-bindings 方法中和/或当我从该方法中调用 deep-subst 方法时出现堆栈溢出错误。任何有关我的递归方法调用的帮助或建议可以帮助我更好地理解，我将不胜感激!我的代码如下--

    (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

Answer 1

问题在于简化函数作为跟踪证明

(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)

如果我们看一下这个函数

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

我们可以看到，递归是基于函数listp的。如果 listp 返回 true，则将调用 simplify-triple，其中两次调用 simplify 作为参数。正如我们在跟踪中看到的，simplify 被一遍又一遍地用 nil 调用，如果我们测试 (listp nil) 我们可以看到它返回 T (这使得 sense 因为它代表 empty list )，因此导致无限递归。

您必须将递归基于另一个(或更多)if 条件。