Tail Recursion

Like Scheme, Irken is properly tail recursive. Even Irken's imperative-style looping constructs, such as loop, are built from tail-recursion.

What is tail recursion? In non-tail recursive function calls, the current stack frame is preserved so after the next function returns, the program execution can continue immediately after the function call. A tail recursive call is made at the very end of a function, where there is no reason to preserve the current stack, because there is no more code in the function to execute. As a result, when tail-recursion-optimization detects a function call in the tail position, it collapses out the current stack frame, causing the next function called to return directly to the current function's caller.

For most people, picking up tail-recursive programming is relatively easy, especially when you learn the 'accumulator' trick. Let's look at a pattern-matching length function:

(define length
    ()       -> 0
    (_ . tl) -> (+ 1 (length tl)))

This function is recursive, but it's not tail-recursive. Why? Look at the recursive call to length. After calling length, it adds one to the result. This causes the stack to fill up as we disassemble the list, and then collapse as we accumulate the counter. This runs in O(N) time, but it also unnecessarily consumes O(N) space. Here is an illustration:

  (length (list 1 2 3 4))
  ; first stack accumulates, then stack collapses
  ; (length (list 1 2 3 4))                        -> (+ 1 3) -> 4
  ;   (length (list 2 3 4))                  -> (+ 1 2) -> 3
  ;     (length (list 3 4))            -> (+ 1 1) -> 2
  ;        (length (list 4)      -> (+ 1 0) -> 1
  ;          (length (list)   -> 0

The accumulator trick will fix the problem. We need to accumulate the counter first, and pass the new accumulated counter into our length function as a second parameter. We can easily hide these details inside the original length function's closure.

(define (length l)
  (define length-internal 
     ()       acc -> acc
     (_ . tl) acc -> (length-internal tl (+ 1 acc))
  )
  (length-internal l 0)
)

Note here that the call to the + function is inside the recursive call (i.e., one of its arguments), rather than outside. This version of the length function is properly tail recursive, and will compute the length of a list in O(N) time and O(1) space; just like the loop you might have written in C.

Of course you may also write this in imperative style, with a for-list and a mutable accumulator variable:

(define (length l)        
  (let ((acc 0))       
     (for-list elem l 
         (set! acc (+ 1 acc)))
     acc))

---

Next: Runtime