This scheme function seems to be tail recursive, so why am I getting a stack overflow

Question

I recently have been messing around with scheme for the first time in years. I'm using repl.it to play around a bit. I wrote this basic function to take a list and return a doubly-linked list. Each cell of the list is a pair whose car is the list element and whose cdr is a pair with the previous element in car and the next element in cdr. The first and last elements have null as the previous and next item, respectively. I wrote the function to be tail recursive. I know now that scheme actually does have looping syntax, but I was under the impression when I wrote it that the only way to loop in scheme was with tail recursion. My code is as follows:

(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 '() '())))

I marked what I believe to be the only two recursive calls. They both seem to me to be in tail context, according to R6RS, yet calling the function causes a stack overflow. Any Ideas as to why?

Sylwester Sylwester · Accepted Answer · 2016-06-02T23:18:18

Yes. Your code is indeed tail recursive. When I try this out in r6rs in DrRacket I get

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

This makes a circular structure. I think perhaps BiwaScheme tries to print this and you cannot print list structure with tail recursion and it doesn't check for circular lists so you end up with a stack overflow.

You can verify this by assigning the result instead so that it doesn't print the result.

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

This scheme function seems to be tail recursive, so why am I getting a stack overflow

1 Answers