Lisp无限递归 [英] Lisp Infinite Recursion

问题描述

我是一名新的Lisp程序员，在用Lisp进行递归时遇到了麻烦.通过一系列用数字替换符号的方法，我简化了一系列表达式，然后对表达式进行求值.在评估之前，我用符号代替数字，这样做会导致在subst-bindings方法中和/或从该方法中调用deep-subst方法时出现堆栈溢出错误.对我的递归方法调用的任何帮助或建议都可以帮助我更好地理解我，我将不胜感激！我的代码如下-

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

推荐答案

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

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)

如果我们看一下功能

(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作为参数.正如我们在跟踪中看到的，一次又一次地用nil调用simplify，如果测试(listp nil)，我们可以看到它返回T(这使

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.

您必须将递归基于另一个(或贯穿整个)if条件.

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

这篇关于Lisp无限递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！