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無限遞歸

回答

相關問題