Lisp无限递归

我是一位新的lisp程序员，在绕过lisp递归时遇到了麻烦。我有一系列的表达式，我通过一系列用数字替换符号的方法来简化，然后我将评估表达式。在评估之前，我用符号替换数字，这样做会导致我的subst-bindings方法中出现堆栈溢出错误，或者当我从该方法内调用deep-subst方法时。任何关于递归方法调用的帮助或建议可以帮助我更好地理解，我将不胜感激！我的代码是below--Lisp无限递归

(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

来源

2014-10-01 Branbron

如果您只能显示最少量的代码和重现问题的测试用例以及您收到的错误消息，那将会更有帮助。 Common Lisp还包含一个跟踪宏，因此如果您要执行'（trace deep-subst）'，您将看到所有对deep-subst的调用，并且您可能会发现问题。 – 2014-10-01 17:29:31

我会试一试，我也拿出了没有必要的或有助于看到问题的代码。代码的最后一行是一个示例测试用例，我打电话evalexp – Branbron 2014-10-01 17:43:24

我想您可能需要调试更多。这个问题在替代函数中似乎不是*完全*。例如，http://pastebin.com/NWHPK5PF运行没有问题（尽管结果可能不是你期望的结果;如果该绑定列表是“（（x。2）（z。8））？”）。这表明“简化”中的某些内容是错误的。 – 2014-10-01 17:48:37

的问题在简化功能痕迹证据规定

(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条件。

来源

2014-10-01 19:53:10 Sim

我会以不同的方式检查返回值，谢谢帮助我理解！ – Branbron 2014-10-01 20:36:07

你可以使用类似'（和（listp exp）exp）'来确保你不会使用'nil'，因为'和'会将'nil'解释为布尔错误 – Sim 2014-10-01 20:40:39

通常的方法来测试列表使用'endp'。 – Svante 2014-10-02 09:27:40

Lisp无限递归

回答

相关问题