Recursive reduction

Mon, Jul 23, 2007

The previous post was pretty grumpy about Python/Django and I was going to write a follow-up about why Ruby is a better language (unfortunately not the platform’s performance just yet but that is soon to change with YARV).

For this post to appear more fair about Ruby/Python than the last let’s look at one reason where these don’t come close to Lisp. This is something mentioned less often(but still important) when comparing Lisp with other languages which usually focus on macros and s-exprs.

Here’s a python snippet that was shared with me not so long ago:

def myreduce(f, t, list):
  size = len(list)
  if size == 1:
    return f(list[0], t)
  else:
    return myreduce(f, f(list[0], t), list[1:size])

It’s a reduce function^[1] that I’m not sure the author knows is buggy.
It takes a function as the first parameter, an initializer value and the list to reduce.

To test the function we could code something like this in Python:

import random
func = lambda x,y: x + y
>>> myreduce(f, 100, [1,2,3,4,5,6])
121

A first attempt at improving on this in Ruby:

def myreduce(l, t, &f)
  return yield(t, l[0]) if l[0] and l.size == 1
  myreduce( l[1..(l.size-1)], yield(t, l[0]), &f )
end
$ myreduce( [1,2,3,4,5,6], 100 ) { |x,y| x + y }   # returns 121

Much simpler (and terse) also using a block. Seemed to work just fine but what happens when we have a longer list to reduce, a million integers ?

$ myreduce( [*1..1000000], 100 ) { |x,y| x + y }
>>SystemStackError: stack level too deep
>        from (irb):2:in `myreduce'
>        from (irb):3:in `myreduce'
>        from (irb):19
>        from :0

Oops, we run out of stack space !
The same problem exists in the Python version.

random_list = [random.randrange(1,1000000) for i in range(1,1000000)]
myreduce(func, 100, random_list)

> File "", line 4, in myreduce
> RuntimeError: maximum recursion depth exceeded

We could increase the stack size but this is a hack and we would never have a large enough stack size for any practical purposes if we were to modify this code for real world use.

To have a more robust version we need to drop the recursive call and just use a loop. So the new Ruby version would look like this

def myreduce_loop(l, t, &f)
  tot = t
  for it in l
    tot = yield(tot, it)
  end
  tot
end
$myreduce_loop( [*1..1000000], 100 ) { |x,y| x + y }
=> 500000500100

The Python version would be very similar.
It’s obvious that the Lisp way of using recursion isn’t practical with Python or Ruby. Yes, there are ways to hack stack frames in Python and possibly in Ruby too.

In Lisp we can use tail recursion because this allows the compiler to optimize recursive calls so that the stack doesn’t blow up and performance is improved(hopefully).

Here’s the tail-recursive reduce function in Lisp.

(defun range(s e)
  (let ((l nil))
    (do ((n s (+ n 1)))
        ((> n e) (reverse l))
      (setf l (cons n l)))))
(defun myreduce(f l &optional (i 0))
  (if (null l)
      i
      (if (null (cdr l))
          (funcall f i (car l))
          (myreduce f (cdr l) (funcall f i (car l) )))))
$ (format t "~D ~%" (myreduce #'+ (range 1 1000000) 100))
500000500100

Ok so we’ll get back to why Ruby is still the next best language in the following post.

[1] Python’s built in functions include ‘reduce’. Search the page after clicking on the link.