Recursive reduction

Posted by ungraspiness Mon, 23 Jul 2007 03:39:00 GMT

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.

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 "<stdin>", 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).

(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
      (progn 
          (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.

Posted in Programming | Tags Lisp, Looping, Python, Recursion, Reduce, Ruby

Red vs. Blue (or don't be so blue man)

Posted by ungraspiness Thu, 12 Jul 2007 22:05:00 GMT

Pointing out the cons of a language like Java can be risky. The responses sometimes are that such attempts are based on highly subjective opinions. Let’s take byte code manipulation for example. Many Java coders find this invaluable for doing anything remotely interesting in Java. After all it’s heavily used in servlet containers and object-relational mapping tools such as JDO implementations. How is this not an invaluable feature ? Well, a Lisp hacker knows Java byte code manipulation to be a con because they can’t help but compare it with Lisp’s macros. Byte code manipulation is still a con for Java programmers too, it’s just that many of them may not be aware of why this is so. It’s really not a case of subjectivity but of awareness(or lack thereof) on the part of those that make the statement against anyone that’s able to see the cons of Java byte code manipulation (or any of Java’s other cons). Seems obvious enough and probably one of the reasons that Sun has so happily backed the current JRuby project.

This entry started after reading a somewhat biased comparison of Ruby and Python which still made some good points (or at least it made me write this !).

First off, Ruby’s meta-programming is superior to Python’s in terms of simplicity and power. Nothing new here .

Now that we have that stuff out of the way here’s another biased article with my points of view. Let’s look at some issues with Python/Django…

Snake Bites

  result = {
    'a': lambda x: x * 5,
    'b': lambda x: x + 7,
    'c': lambda x: x - 2
  }[value](x)

  class Example:
    def method(self, x):
      print "method was passed ", x

class thing:
  count = 0
  def __init__(self, value):
    self.value = value
    thing.count += 1
  def getval(self):
    return self.value
  def getcount(cls):
    return thing.count
  counter = classmethod(getcount)

There are so many examples that could follow but let’s leave it at these and figure out why we have…

Too much gas

• White space: (there I said it) Python’s significant white-space is part of the reason for Django’s crappy and almost unusable template syntax.
• Design: Unrelated (but still annoying) is Django’s broken MVC design. Django calls a controller a view, there’s an unnecessary model layer for form handling (manipulators and now forms which are really just new manipulators) and views are templates that support a funky object-oriented hierarchy similar to ASP.Net (but easier to grasp).
• Badly used meta-programming: Decorators are used in Django to change parameter types and not in the way that you may find useful like for form handling, where converting strings to integers would be useful.
• ORM: The Object Relational mapping features require a degree in HtHdtW(How the hell does this Work!). e.g. Entry.objects.exclude(pub_date__gt=datetime.date(2005, 1, 3)).exclude(headline=’Hello’) Why all the double underscores ? Tried multi-table queries recently ? or how about database transactions (they need to be defined in a view?!). SQLalchemy is supposed to transmute this lead into gold in the near future and it honestly does look like a big improvement.
• Debugging: Trying to debug a Django application more complex than “hello world” can be really difficult. Django has no logging facility so some pretty cool folks have taken this upon themselves
• Community: Has anyone had any success in submitting bug fixes for these ? (I don’t know anyone that has) Any sizable project I’m aware of has had to do a fork of the framework.
• Why is Django’s version number so close to 1.0 at this point ?

This provides some valid reasons as to how language can play a role in the frameworks built using them. Language effects how programmers think about problems (more so than they realize sometimes) and this can effect what and how certain things are built with a language.

Now, to the person who first responded to the comparison article: Are most of Python’s(and as an extension Django’s) cons just highly subjective ? It seems more like we all love to call them just “preferences” and repeat the mantra of peaceful language/framework co-existence in spite of what we remain unaware of in other languages (or worse, remain in denial of).

Co-exist ?

Negativa

So Python/Django are pretty cool but Ruby/Rails are much better and Lispy frameworks are best(but just not as widely accessible… ...yet). Hopefully Ruby/Rails heads even further in the direction of Lisp. It does seem very likely with cool projects like RLisp starting to take shape.

the end

Posted in Philosophy, Programming | Tags Django, Lisp, Python, Rails, Ruby