Эта функция схемы кажется хвостом рекурсивной, поэтому почему я получаю переполнение стека

Question

Недавно я впервые возился со схемой в течение многих лет. Я использую repl.it, чтобы поиграть немного. Я написал эту основную функцию, чтобы взять список и вернуть двусвязный список. Каждая ячейка списка представляет собой пару, автомобиль которой является элементом списка, а cdr - пара с предыдущим элементом в автомобиле и следующий элемент в cdr. Первый и последний элементы имеют нуль как предыдущий и следующий элементы соответственно. Я написал эту функцию как хвост рекурсивный. Теперь я знаю, что на самом деле схема имеет петлевый синтаксис, но я был под впечатлением, когда писал, что единственный способ петли в схеме - это рекурсия хвоста. Мой код выглядит следующим образом:

(define (dbllink li) 
    (letrec ((step (lambda (lis prev head) 
          (if (null? lis) 
           head 
           (let ((cell (cons (car lis) 
               (cons prev '())))) 
           (if (null? prev) 
            (step (cdr lis);<--recursive call 
              cell 
              cell) 
            (begin (set-cdr! (cdr prev) 
                 cell) 
              (step (cdr lis);<--recursive call 
                cell 
                head)))))))) 
     (step li '() '()))) 

Я отметил, что я считаю только два рекурсивных вызова. Они оба кажутся мне в хвостовом контексте, согласно R6RS, но вызов функции вызывает переполнение стека. Любые идеи о том, почему?

Answer 1

Да. Ваш код действительно хвост рекурсивный. Когда я пробую это в r6rs в DrRacket, я получаю

(dbllink '(1 2 3 4 5)) 
; ==> #0={1() . #1={2 #0# . #2={3 #1# . #3={4 #2# 5 #3#}}}} 

Это делает круговую структуру. Я думаю, что, возможно, BiwaScheme пытается распечатать это, и вы не можете распечатать структуру списка с рекурсией хвоста, и он не проверяет циклические списки, поэтому вы получаете переполнение стека.

Вы можете проверить это, назначив результат вместо этого, чтобы он не распечатывал результат.

(define test (dbllink '(1 2 3 4 5)) ; ==> #void 
(car test) ; ==> 1 
test ; ("too much recursion" in Biwa)