在SBCL递归

我遇到了SBCL（在Linux上）可能与尾递归有关的问题（不是我完全相信那是什么）。我这次添加了代码（它看起来很长，但那是因为我把它全部展开了）。在SBCL递归

这笔交易是我有一个比较两个结构的函数'compare-pstructs'。但是，这些结构可能具有与组件相同结构的列表。自然，这需要一个递归解决方案。

当上述函数需要比较这些pstructs的列表时，会调用第二个函数'compare-parses'。自然地，比较分析功能必须再次对比较 - 结构函数进行吸引以比较单独的结构。

因此，它应该在构建堆栈帧的这些函数之间来回跳动，然后弹出它们，因为它发现单个pstruct匹配或不匹配，并且执行相同的操作，因为发现整个分析匹配或不。

实际发生的是第一次弹出堆栈帧时，不再发生递归调用。更奇怪的是，沿着pstructs列表循环（在比较分析函数中）的循环继续迭代，只执行比较 - 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 
*

来源

2017-02-08 Todd Pierce

您可能需要'（declaim（optimize（debug 0）（safety 0）（speed 3）））'根据[本页]获取TCO（https://0branch.com/notes/tco- cl.html＃sec-2-2）如果这不起作用，请尝试减少代码，以便它能够显示错误，但没有其他所有内容并将其发布。 – Sylwester

这个人（似乎是一个天才）放在一起调整优化以允许在lisp的几个实现中进行尾递归：https://gitlab.common-lisp.net/frideau/ptc当然，它不会没有帮助，所以也许别的东西就起来了。我正在研究代码的蒸馏版本。 –

那么，只有SBCL和Clozure被支持，并且SBCL通过'（declaim（optimize（debug 0）（safety 0）（speed 3）））'来完成它。 – Sylwester

不要使用DEFPARAMETER内部功能。它定义了一个全局变量，由于递归调用将使用相同的变量，因此会在COMPARE-PARSES中混淆逻辑。

你的代码是相当单一的Lisp。你不应该这样使用IF和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的东西。在这种情况下，你可以如果你使用Emacs和淤泥/狡猾使用TRACE

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

，您还可以使用trace dialog了一下更好的接口。

另见BREAK,INSPECT,STEP和粘液等价物。

来源

2017-02-12 07:49:58 jkiiski

好的，上面的专家提出了一个解决我的问题。我使用defparameter确实犯了一个大错误。我在这里这样做是为了摆脱SBCL的警告，并且由于HyperSpec说：“defparameter和defvar通常显示为顶级表单，但它们对于非顶级表单显得很有意义。”

我认为这意味着它会保持局部范围内的变量，但这不是真的！哎哟。无论如何，代码在添加defparameter宏之前以及删除之后都不起作用。

另一个错误似乎认为在调试过程中将代码拉伸得越来越远，直到最终看起来像（ugh）Pascal或Python没有帮助的那样执行。我在猜测优化器是硬编码的，希望程序流程成为一种特殊的方式，如果代码故意效率低下，可能无法预测。

我原来的代码更浓缩，但虽然逻辑上相同，但我无法让它工作。当然，在我目前的Lisp技能水平下，我从来不会猜到如何将代码压缩到上面的专家的水平......我的意思是“每一个”？我从来不知道有一个内置的！

来源

2017-02-15 19:46:35

回答

相关问题