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 optimization? In non-tail recursive function calls, the current function's stack frame is preserved during the function call, so the function can return to the place the call was made. A tail recursive call is made at the very end of a function, where there is no reason to preserve the current function's stack. As a result, when tail-recursion-optimization detects a function call in the tail position, it collapses out the current stack frame, causing the function called to return directly to the caller.

The compiler detects tail-recursive calls, and the resulting machine code performs a direct jump without pushing a stack-frame. For most people, picking up this style of 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. When length is called, the stack will fill up with a bunch of +1 calls until it reaches the end of the list. It's O(N) time, but it's also O(N) space.

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. [It's called a tail call because it's the very last thing the function does]. Another thing: length2 takes two arguments, not one. Note how the acc variable passes through the pattern match untouched.

The auxiliary function length3 It provides the same interface as the original function, and provides the initial value for the accumulator. You could hide the definition of length2 inside length3, like this:

(define (length4 l)
  (define recur
    ()       acc -> acc
    (_ . tl) acc -> (recur tl (+ 1 acc))
    )
  (recur l 0)
  )

Another approach would be to bind acc inside length4, avoiding the acc argument inside recur. These are style issues, ones that I'm still working out myself.