iDrone reprint: Writing an accumulator generating function in Ruby

[This is an iDrone reprint, Written by Mark W on Feb 9th, 2007]

Talking with Matt, this morning, our conversation turned to the very large differences in power between various programming languages. While most would readily agree that higher level programming languages are far more expressive than assembly, many people draw the line there. Java, C++, VB, Python, Fortran are all “about the same” to quite a few people, including ,unfortunately, most of my previous bosses.

One example Paul Graham used to illustrate differences between higher level programming languages is how difficult it is to write a function that generates accumulators— a function that takes a number n as a parameter, and returns a function that takes another number i and returns n + i.

In Python, he said the commonly accepted solution was as follows:

def foo(n):
 class acc:
   def __init__(self, s):
     self.s = s
    def inc(self, i):
      self.s += i
      return self.s
  return acc(n).inc 

In Javascript, a surprisingly powerful language, considering it’s almost completely ignored outside of web page development, the solution is shorter and cleaner:

function acc(n) {
  return function (i) {             
    return n += i 
  } 
}

One language Paul Graham did not mention, was Ruby. I’m still fairly new to Ruby, but the solution was not difficult. Due to the power of blocks in Ruby, this sort of functional programming is extremely clean. Here is the accumulator generating function:


def acc(n)
  lambda {|i| n += i}
end 

Here’s a quick example of it in use:


f1 = acc(3)           # a function that increments by three
f1.call(5)            # returns 8
f1.call(-1)           # returns 2
f2 = acc(1.5)         # a function that increments by 1.5
f2.call(1)            # returns 2.5
f2.call(3)            # returns 4.5
f2.call(f1.call(1))   # returns 5.5 

In some less expressive languages, such as VB, C++, Fortran or Java, it isn’t even possible[1] to write a simple function that can generate accumulators. Obviously since each of those languages are Turing complete, the problem would be solvable, just not with a simple function. You could, given enough time, write a Ruby interpreter in C++, and then input


def acc(n)
  lambda {|i| n+i}
end

to get your accumulator.

---

[1]: Ken Anderson did offer an example of a way to kludge together an accumulator generating function in Java in Graham’s essay above. He used an integer to integer interface. Naturally enough, it fails to work for anything but integers. Generating a polymorphic function in Java, similar to the functions listed in this article would be a Sisyphean undertaking. If you can do it, I’d love to see a link to it in a comment.