Tail Recursion

Like Scheme, Irken is properly tail recursive. Even imperative-style looping constructs, such as loop, are built from tail-recursion. The compiler detects tail-recursive calls and translates them into a goto (with the C back end, literally). 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:

(define length2 
  ()       acc -> acc
  (_ . tl) acc -> (length2 tl (+ 1 acc))
  )

(define (length3 l)
  (length2 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.

Notice 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.