Wednesday, January 9, 2008

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.

2 comments:

  1. paul's python skills must be somewhat out of date

    def acc(n):
    return lambda i:i+n

    ReplyDelete
  2. Here is what Paul Graham said about the simple Python solution:

    If you try to translate the Lisp/Perl/Smalltalk/Javascript code into Python you run into some limitations. Because Python doesn't fully support lexical variables, you have to create a data structure to hold the value of n. And although Python does have a function data type, there is no literal representation for one (unless the body is only a single expression) so you need to create a named function to return.

    Python users might legitimately ask why they can't just write

    def foo(n):
      return lambda i: return n += i

    or even

    def foo(n):
      lambda i: n += i

    and my guess is that they probably will, one day. (But if they don't want to wait for Python to evolve the rest of the way into Lisp, they could always just...)

    ReplyDelete

Note: Only a member of this blog may post a comment.