SBCL中的递归

Question

我遇到了SBCL (在linux上)的问题，这可能与尾递归有关(不是说我完全确定那是什么)。我这次添加了代码(它看起来很长，但那是因为我把它都拉长了)。

问题是，我有一个'compare-pstructs‘函数来比较两个结构。然而，这些结构可以具有与组件相同的结构的列表。当然，这需要一个递归的解决方案。

当上面的函数需要比较这些结构体的列表时，会调用第二个函数' compare -parses‘。自然，compare-parses函数必须再次调用compare-pstructs函数来比较各个结构体。

因此，它应该在这些函数之间来回跳跃，构建堆栈帧，然后在发现个别结构匹配或不匹配时将其弹出，并在发现整个解析匹配或不匹配时执行相同的操作。

实际发生的情况是，第一次弹出堆栈帧时，不会再发生递归调用。更奇怪的是，遍历pstruct列表(在compare-parses函数中)的循环继续迭代，只执行compare-pstructs函数回调下面的代码。

我将尝试将它们组合到一个函数中，但我仍然想知道为什么它不能作为两个函数工作。

代码后面跟着一个日志。感谢大家的关注。

-Todd

(defstruct pstruct
    syntactic-info  ;; A list
    dependents  ;; A list of more pstructs
 )

(defun compare-parses (p1t  p2t)
(defparameter idx  0)
(defparameter max-idx (length p1t))

;; If they're not the same length, all bets are off.
(if     (not 
        (equal 
            (length p1t)
            (length p2t)
        )
    )
        (return-from compare-parses NIL)    
)
(loop
    (print "idx before compare pstructs:")
    (print idx)
    (if
        (null (compare-pstructs (nth idx p1t) (nth idx p2t)))
            (return-from compare-parses NIL)
    )
    (setf idx (1+ idx))
    (print "Added one to idx:")
    (print idx)
    (if (>= idx max-idx)
        (return)
    ) 
)
(return-from compare-parses T)
)

(defun compare-pstructs (p1 p2)
(print "P1")
(print p1)
(print "P2")
(print p2)

(if     (not (equal (pstruct-syntactic-info p1)     (pstruct-syntactic-info p2)))
        (return-from compare-pstructs NIL)
)
(if     (and
        (null (pstruct-dependents p1))  
        (null (pstruct-dependents p2))
    )
    (return-from compare-pstructs T)
)
(if     (and
        (not (null (pstruct-dependents p1)))    
        (not (null (pstruct-dependents p2)))
    )
    (return-from compare-pstructs 
        (compare-parses
            (pstruct-dependents p1) (pstruct-dependents p2)
        )
    )
)
;; If one or the other (not both) dependents is NIL then return NIL.
(return-from compare-pstructs NIL)
)

;; Two structures for test data (notice one has an "X" stuck in it
;; to make the two different.

(defparameter x2
 '#S(PSTRUCT
 :SYNTACTIC-INFO ("Sfin")
 :DEPENDENTS (#S(PSTRUCT
                 :SYNTACTIC-INFO ("Ext" "NP" "Pron_PRON" "Pers_PRON" "S"
                                  "Sin1" "1st" "Sin" "NomC")
                 :DEPENDENTS (#S(PSTRUCT
                                 :SYNTACTIC-INFO ("PRON" "Pron_PRON"
                                                  "Pers_PRON" "Sin1" "S"
                                                  "Sin1" "1st" "Sin"
                                                  "NomC")
                                 :DEPENDENTS NIL)))
              #S(PSTRUCT
                 :SYNTACTIC-INFO ("Plu" "Sin2" "Sin3" "Sin1" "Pres" "V"
                                  "Trans_V" "TransComp_V" "Intrans_V"  
                                  "Ditrans_V" "Inf")
                 :DEPENDENTS NIL)
              #S(PSTRUCT
                 :SYNTACTIC-INFO ("DNI")
                 :DEPENDENTS NIL))))

(defparameter y2
 '#S(PSTRUCT
 :SYNTACTIC-INFO ("Sfin")
 :DEPENDENTS (#S(PSTRUCT
                 :SYNTACTIC-INFO ("Ext" "NP" "Pron_PRON" "Pers_PRON" "S"
                                  "Sin1" "1st" "Sin" "NomC")
                 :DEPENDENTS (#S(PSTRUCT
                                 :SYNTACTIC-INFO ("PRON" "Pron_PRON"
                                                  "Pers_PRON" "Sin1" "S"
                                                  "Sin1" "1st" "Sin"
                                                  "NomC")
                                 :DEPENDENTS NIL)))
              #S(PSTRUCT
                 :SYNTACTIC-INFO ("Plu" "Sin2" "Sin3" "Sin1" "Pres" "V"
                                  "Trans_V" "TransComp_V" "Intrans_V"  
                                  "Ditrans_V" "Inf" "X")   ;;   <=== "X" to make them different 
                 :DEPENDENTS NIL)
              #S(PSTRUCT
                 :SYNTACTIC-INFO ("DNI")
                 :DEPENDENTS NIL))))

;; Here's the log.... 

    * (compare-pstructs x2 y2)

    "P1" 
#S(PSTRUCT
   :SYNTACTIC-INFO ("Sfin")
   :DEPENDENTS (#S(PSTRUCT
                   :SYNTACTIC-INFO ("Ext" "NP" "Pron_PRON" "Pers_PRON" "S"
                                    "Sin1" "1st" "Sin" "NomC")
                   :DEPENDENTS (#S(PSTRUCT
                                   :SYNTACTIC-INFO ("PRON" "Pron_PRON"
                                                    "Pers_PRON" "Sin1" "S"
                                                    "Sin1" "1st" "Sin" "NomC")
                                   :DEPENDENTS NIL)))
                #S(PSTRUCT
                   :SYNTACTIC-INFO ("Plu" "Sin2" "Sin3" "Sin1" "Pres" "V"
                                    "Trans_V" "TransComp_V" "Intrans_V"
                                    "Ditrans_V" "Inf")
                   :DEPENDENTS NIL)
                #S(PSTRUCT :SYNTACTIC-INFO ("DNI") :DEPENDENTS NIL))) 
"P2" 
#S(PSTRUCT
   :SYNTACTIC-INFO ("Sfin")
   :DEPENDENTS (#S(PSTRUCT
                   :SYNTACTIC-INFO ("Ext" "NP" "Pron_PRON" "Pers_PRON" "S"
                                    "Sin1" "1st" "Sin" "NomC")
                   :DEPENDENTS (#S(PSTRUCT
                                   :SYNTACTIC-INFO ("PRON" "Pron_PRON"
                                                    "Pers_PRON" "Sin1" "S"
                                                    "Sin1" "1st" "Sin" "NomC")
                                   :DEPENDENTS NIL)))
                #S(PSTRUCT
                   :SYNTACTIC-INFO ("Plu" "Sin2" "Sin3" "Sin1" "Pres" "V"
                                    "Trans_V" "TransComp_V" "Intrans_V"
                                    "Ditrans_V" "Inf" "X")
                   :DEPENDENTS NIL)
                #S(PSTRUCT :SYNTACTIC-INFO ("DNI") :DEPENDENTS NIL))) 
"idx before compare pstructs:" 
0 
"P1" 
#S(PSTRUCT
   :SYNTACTIC-INFO ("Ext" "NP" "Pron_PRON" "Pers_PRON" "S" "Sin1" "1st" "Sin"
                    "NomC")
   :DEPENDENTS (#S(PSTRUCT
                   :SYNTACTIC-INFO ("PRON" "Pron_PRON" "Pers_PRON" "Sin1" "S"
                                    "Sin1" "1st" "Sin" "NomC")
                   :DEPENDENTS NIL))) 
"P2" 
#S(PSTRUCT
   :SYNTACTIC-INFO ("Ext" "NP" "Pron_PRON" "Pers_PRON" "S" "Sin1" "1st" "Sin"
                    "NomC")
   :DEPENDENTS (#S(PSTRUCT
                   :SYNTACTIC-INFO ("PRON" "Pron_PRON" "Pers_PRON" "Sin1" "S"
                                    "Sin1" "1st" "Sin" "NomC")
                   :DEPENDENTS NIL))) 
"idx before compare pstructs:" 
0 
"P1" 
#S(PSTRUCT
   :SYNTACTIC-INFO ("PRON" "Pron_PRON" "Pers_PRON" "Sin1" "S" "Sin1" "1st"
                    "Sin" "NomC")
   :DEPENDENTS NIL) 
"P2" 
#S(PSTRUCT
   :SYNTACTIC-INFO ("PRON" "Pron_PRON" "Pers_PRON" "Sin1" "S" "Sin1" "1st"
                    "Sin" "NomC")
   :DEPENDENTS NIL) 
"Added one to idx:" 
1 
"Added one to idx:"    <== See how the loop keeps iterating
2 
T
* 

Answer 1

不要在函数内部使用DEFPARAMETER。它定义了一个全局变量，因为递归调用将使用相同的变量，这会使您在COMPARE-PARSES中的逻辑变得混乱。

您的代码相当单一的Lisp。你不应该那样使用IFs和RETURN-FROM。改为将函数结构化为单个表达式。

(defstruct pstruct
  ;; Instead of comments to say what type these are,
  ;; you could use code to tell it.
  (syntactic-info nil :type list)
  (dependents nil :type list))

;; Since the functions call each other, it's better to declare
;; their ftypes beforehand.
(declaim (ftype (function (list list) boolean) compare-parses)
         (ftype (function (pstruct pstruct) boolean) pstruct=))

(defun compare-parses (p1t p2t)
  (and (= (length p1t)
          (length p2t))
       (every #'pstruct= p1t p2t)))

(defun pstruct= (p1 p2)
  (and (equal (pstruct-syntactic-info p1)
              (pstruct-syntactic-info p2))
       (compare-parses (pstruct-dependents p1)
                       (pstruct-dependents p2))))

Common Lisp还提供了一些调试工具，因此您不需要PRINT东西。在这种情况下，您可以使用TRACE

CL-USER> (trace compare-parses pstruct=)
CL-USER> (pstruct= *x2* *y2*)
... Prints the trace ...
CL-USER> (untrace compare-parses pstruct=)

如果你使用的是Emacs和Slime，你也可以使用trace dialog来获得更好的界面。

另请参阅BREAK、INSPECT、STEP和Slime等效项。

Answer 2

好的，上面的专家想出了我的问题的解决方案。我确实犯了一个很大的错误，那就是使用defparam.我在这里这样做是为了摆脱SBCL警告，因为HyperSpec说："defparameter和defvar通常显示为顶级表单，但它们显示为非顶级表单是有意义的。“

我认为这意味着它将在局部范围内维护变量，但事实并非如此！唉哟。无论如何，在添加defparamumer宏之前和删除它之后，代码都不起作用。

另一个错误似乎是认为在调试过程中将代码延伸得越来越远，直到最终得到类似于Pascal或Python的外观和执行的代码是没有帮助的。我推测优化器已经被硬编码，以期望程序流是一种特定的方式，并且如果代码故意低效，则可能是不可预测的。

我的原始代码更简洁，但虽然逻辑上相同，但我无法让它工作。当然，以我目前的Lisp技术水平，我永远不会猜到如何像上面的专家那样压缩代码……我是说“每一次”？我从来不知道有一个内置的！！