Given a recursive function, how do I change it to tail recursive and streams?

Question

Given a recursive function in scheme how do I change that function to tail recursive, and then how would I implement it using streams? Are there patterns and rules that you follow when changing any function in this way?

Take this function as an example which creates a list of numbers from 2-m (this is not tail recursive?)

Code:

(define listupto
  (lambda (m)
    (if (= m 2)
        '(2)
        (append (listupto (- m 1)) (list m)))))

Hellas

Answer 1

I'll start off by explaining your example. It is definitely not tail recursive. Think of how this function executes. Each time you append you must first go back and make the recursive call until you hit the base case, and then you pull your way back up.

This is what a trace of you function would look like:

(listupto 4)
| (append (listupto(3)) '4)
|| (append (append (listupto(2)) '(3)) '(4))
||| (append (append '(2) '(3)) '(4))
|| (append '(2 3) '(4))
| '(2 3 4)
'(2 3 4)

Notice the V-pattern you see pulling in and then out of the recursive calls. The goal of tail recursion is to build all of the calls together, and only make one execution. What you need to do is pass an accumulator along with your function, this way you can only make one append when your function reaches the base case.

Here is the tail recursive version of your function:

(define listupto-tail
  (lambda (m)
     (listupto m '())))

# Now with the new accumulator parameter!
(define listupto
   (lambda (m accu)
     (if (= m 2)
        (append '(2) accu)
        (listupto (- m 1) (append (list m) accu)))))

If we see this trace, it will look like this:

(listupto 4)
| (listupto (3) '(4))  # m appended with the accu, which is the empty list currently
|| (listupto (2) '(3 4)) # m appended with accu, which is now a list with 4
||| (append '(2) '(3 4))
'(2 3 4)

Notice how the pattern is different, and we don't have to traverse back through the recursive calls. This saves us pointless executions. Tail recursion can be a difficult concept to grasp I suggest taking a look here. Chapter 5 has some helpful sections in it.

Inanna

This is along the lines of what I have been reading in separate tutorials but makes much more sense. Thank you! Now, how might I alter this example to be a stream? Say I want a infinite list 2-inf but I do not want to calculate it all (obvious). How does/would this work? wouldn't I need to make separate calls to an object that holds the streams state (namely the next (first) item in the stream, and how to calculate the rest of it)? – Hellas

I'm glad my example was helpful! I think you should take at continuation passing style, where instead of passing passing an accumulator you are going to pass the continuation of the current function. Which will build up one big statement to execute all at once. This way you can keep track of the current state of your function, and also short circuit it whenever (like with a base case, or any other input). Wikipedia does a pretty good job of explaining this concept, it is a very tough concept to grasp initially, but a beautiful technique when mastered. – Inanna

Answer 2

Generally to switch to a tail recursive form you transform the code so that it takes an accumulator parameter which builds the result up and is used as the final return value. This is generally a helper function which your main function delegates too.

Something of the form:

(define listupto
  (lambda (m)
     (listupto-helper m '())))

(define listupto-helper
   (lambda (m l)
     (if (= m 2)
        (append '(2) l)
         (listupto-helper (- m 1) (append (list m) l)))))

As the comments point out, the helper function can be replaced with a named let which is apparently (haven't done much/enough Scheme!) more idiomatic (and as the comments suggest cons is much better than creating a list and appending.

(define listupto
  (lambda (n)
    (let loop ((m n) (l '()))
      (if (= m 2)
          (append '(2) l)
          (loop (- m 1) (cons m l))))))

Kaki

Actually, named let is the idiomatic way to write this, but +1 for accumulator variables. – Islamism

@larsmans You're right, that does look neater. Thanks for pointing this out! – Kaki

Also, but this is really a mistake in the OP's code, (append (list x) y) is idiomatically written (cons x y). – Islamism

The name is also confusing. It's called listupto, but it should be listfromtwoupto, it seems silly to not start at 0 or 1. – Inanna

I agree with cons, so I've changed that. Didn't want to change the name of the function though as it diverts from the point of the question. – Kaki

Answer 3

You also ask about streams. You can find a SICP styled streams used e.g. here or here which have a from-By stream builder defined:

 ;;;; Stream Implementation
 (define (head s) (car s))
 (define (tail s) ((cdr s))) 

 (define-syntax s-cons
   (syntax-rules () 
     ((s-cons h t) (cons h (lambda () t))))) 

 ;;;; Stream Utility Functions
 (define (from-By x s)
   (s-cons x (from-By (+ x s) s)))

Such streams creation relies on macros, and they must be accessed by special means:

 (define (take n s) 
   (cond  ; avoid needless tail forcing for n == 1 !
      ((= n 1) (list (head s)))   ; head is already forced
      ((> n 1) (cons (head s) (take (- n 1) (tail s))))
      (else '())))

 (define (drop n s)
   (cond 
      ((> n 0) (drop (- n 1) (tail s)))
      (else s)))

But they aren't persistent, i.e. take and drop recalculate them on each access. One way to make streams persistent is to have a tailing closure surgically altering the last cons cell on access:

(1 . <closure>)
(1 . (2 . <closure>))
....

like this:

(define (make-stream next this state)
  (let ((tcell (list (this state))))  ; tail sentinel cons cell
    (letrec ((g (lambda ()
                    (set! state (next state))
                    (set-cdr! tcell (cons (this state) g))
                    (set! tcell (cdr tcell))
                    tcell)))
      (set-cdr! tcell g)
      tcell)))

(define (head s) (car s))

(define (tail s)
  (if (or (pair? (cdr s))
          (null? (cdr s)))
    (cdr s)
    ((cdr s))))

We can now use it like this

(define a (make-stream (lambda (i) (+ i 1)) (lambda (i) i) 1))
;Value: a

a
;Value 13: (1 . #[compound-procedure 14])

(take 3 a)
;Value 15: (1 2 3)

a
;Value 13: (1 2 3 . #[compound-procedure 14])

(define b (drop 4 a))
;Value: b

b
;Value 16: (5 . #[compound-procedure 14])

a
;Value 13: (1 2 3 4 5 . #[compound-procedure 14])

(take 4 a)
;Value 17: (1 2 3 4)

a
;Value 13: (1 2 3 4 5 . #[compound-procedure 14])

Now, what does (make-stream (lambda (i) (list (cadr i) (+ (car i) (cadr i)))) car (list 0 1)) define?

---

update: in Daniel Friedman's 1994 slides "The Joys of Scheme, Cont'd" we find simpler implementation of these "memoized streams" (as they are called there), making the tail function itself store the forced stream in the tail sentinel, as

(define (tail s)
  (if (or (pair? (cdr s))
          (null? (cdr s)))
    (cdr s)
    (let ((n ((cdr s))))
       (set-cdr! s n)
       (cdr s))))

;; can be used as e.g. (https://ideone.com/v6pzDt)
(define fibs 
   (let next-fib ((a 0) (b 1))
      (s-cons a (next-fib b (+ a b)))))
      

Perdition

Answer 4

Here's a tail recursive form -

(define (listupto n)
  (let run
    ((m 0)
     (return identity))
    (if (> m n)
        (return null)
        (run (add1 m)
             (lambda (r) (return (cons m r)))))))

(listupto 9)
; '(0 1 2 3 4 5 6 7 8 9)

And here it is as a stream -

(define (listupto n)
  (let run
    ((m 0))
    (if (> m n)
        empty-stream
        (stream-cons m
                     (run (add1 m))))))

(stream->list (listupto 9))
; '(0 1 2 3 4 5 6 7 8 9)

Cosmography