Understanding “reduce” (first in a series)

One of the notable things about MIT’s computer science curriculum, at least back when I was studying there, was that you didn’t learn any “practical” programming languages.  Our work was all done in either Scheme (a dialect of Lisp) or in CLU (an early object-oriented language).  I can’t say that I have too many memories, let alone fond ones, of CLU.  But I definitely drank the Kool-Aid about Lisp, and have long believed that it has always represented the pinnacle of programming languages.  Things that I learned long ago in Lisp are only now becoming standard in popular languages.

For example, functional programming has become increasingly popular in the last few years, for a variety of reasons including the shrinking effects of Moore’s Law — and the resulting need to have multiple, immutable copies of your data in the computer, distributed across multiple processors.  Lisp has long had many functional capabilities; it was Lisp that first introduced me to such functions as “map”, which I use multiple times each day.  However, my regular uses of “map” are rarely in Lisp; rather, they’re in Python and Ruby, the languages that I use most in my day-to-day work.

When I teach classes in Ruby and Python, I spend a fair amount of time talking about functional programming techniques.  It might sound funny to discuss functional programming in two languages that are so clearly object-oriented, but I actually find it quite natural.  Sure, I create classes and throw objects around.  But if I have an array of values, then it’s very fast and easy for me to process them with functional techniques.  Python’s list comprehensions have basically taken the place of the “map” and “filter” functions, so while those exist, they’re not as necessary any more.  But once you understand such functions as “map” and “filter”, you’re poised to do all sorts of amazing things.

Perhaps the most intriguing of the functions from this school is “reduce”.  I have found, consistently over time, that “reduce” is the function most likely to surprise and confuse newcomers to this type of programming.  That’s because it’s easy to confuse what “reduce” is doing, and to forget how flexible its output can be.

I’ve thus decided to write a series of blog posts about “reduce”, in both Python and Ruby.  I’ll start with the simple stuff, and then move ahead with increasingly complex tasks.  You won’t necessarily start to use “reduce” all of the time, but if you’re like me, you will find all sorts of interesting uses for it.  I tell people that I tend to use “reduce” about once every six months — but when I do use it, it really saves the day.

In Ruby, we can use the “reduce” method (also available as “inject”, to satisfy people from the Smalltalk world) on any enumerable object.  The invocation looks like this:

[1,2,3,4,5].reduce(0) {|a, b| a+b}

I’ll explain what this all means in a moment.  But the most important change that I can already make is to use better names for the block parameters:

[1,2,3,4,5].reduce(0) {|total, current| total+current}

Ruby goes through each element of the enumerable, invoking the block on each element. Described in this way, we might confuse “reduce” with “map”.  However, in “map”, the output is an array of the same length as the input.  By contrast, with “reduce”, the output of each iteration is remembered for the next time around.  That is, the value of “total” in each iteration is the block’s result from the last iteration.  

The initial value of “total”, in the first iteration, is the parameter value that we pass, which is 0 in this case.  If you don’t pass a parameter, then “total” is initialized with the first element of the enumerable, and the first iteration (i.e., the first application of the block) takes place on the second element.  This is fine in the above example, but depending on the output you want, failing to pass a parameter, or passing one of the wrong type, can make a big difference.

You can also think of “reduce” as a sort of “join”, but one that evaluates its inputs and operations.  So instead of getting the string “1+2+3+4+5”, you get the result of actually invoking 1+2, and then (1+2)+3, and then ((1+2)+3)+4, and then finally (((1+2)+3)+4)+5. This is why some Lisp versions call this “fold”, rather than “reduce”.  I still don’t quite get why Smalltalk people call it “inject”, and thus never use that term in Ruby (except when introducing the five rhyming functional methods — select, detect, collect, inject, and reject — because it’s so much fun to say). But the effect, once you internalize it, can be used in many interesting ways.

Python doesn’t have a “reduce” method on sequences, but does have a builtin “reduce” function that can be invoked on sequences.  (In Python 3, the “reduce” function was moved to the “functools” module — which is better than the fate Guido had originally planned for it.)  Python’s “reduce” is similar to the one in Ruby.  To sum numbers, we say:

>>> numbers = range(10)
>>> reduce(lambda total, current: total + current, numbers)
45

As you can see (I hope), the use of “lambda” to create an anonymous function is analogous to the use of a block in Ruby.  In Python’s “reduce” function, you first pass the function you wish to invoke on the sequence, and then the sequence itself.  If you wish to pass an initial value for “total”, you can do so with an optional third parameter:

>>> reduce(lambda total, current: total + current, numbers, 10)
55

The classic use of “reduce” is to sum integers, as we saw above.  But we can, of course, perform additional types of operations, and produce additional types of output.  And to be honest, that’s where “reduce” starts to get more intriguing.  Any operation that you want to perform on an enumerable, such as an array, set, or range, and apply cumulatively to its elements, makes for a good choice for “reduce”. By experimenting with the input enumerable, the initial value of “total” that we pass as a parameter, and the block, we can do many interesting things.

In coming posts, I’ll explore some more of these ideas, and give you a tour of “reduce” in both Ruby and Python that will hopefully open your eyes to some of them, and give you a sense of where “reduce” can help to improve your thinking, and your code.

rvm do

I’ve been using rvm for many years, and love it.  Yes, I know that it rewrites simple commands, such as “ruby” and “gem”, so that I can use lots of different Ruby versions.  Yes, I know that it can be overkill for certain situations.  And yes, I know that rbenv is preferred by many.

But I’ve been using rvm for a long time, and I find it works very well for my needs.  I can (and do) have many different versions of Ruby running on my computer, and having access to all of them at once is terrific.

I tend to be obsessive about updating Ruby gems on my systems, and I’m sure I’m not the only Rubyist who runs “gem update -V” (and yes, I love the “verbose” option) at least once per day.  Updating gems never removes the old versions, and if you’re using Bundler in your Rails or Sinatra application, then it doesn’t really matter how many versions you have on your system.  (And yes, I know that willy-nilly updating all gems on my system is probably not wise.  If only that were the most foolish thing I do…)

The thing is, when I update gems, I do so in a particular version of Ruby.  So even though I’m always running “gem update -V”, I never quite remember which versions of Ruby have the latest gems, and which haven’t been updated in a while.  There is, of course, a clear correlation between the frequency with which I use a Ruby version and the freshness of the gems for that version on my system.  But I sometimes find myself having to update gems in a version of Ruby that I haven’t used in a while.

So you can imagine my delight when I discovered “rvm do”.  This is an rvm command that lets you execute a command in any or all of the Ruby versions installed on your system.  It basically switches to the Ruby version and then executes the requested shell command — so you’re not executing a Ruby program in each separate version, but rather you’re executing a command-line program once for each version of Ruby installed.  You can think of it as executing the same shell command once for each installed version, prefaced by “rvm VERSION_NUMBER”.

So, how can I ensure that all of the gems, for all versions of Ruby, are up to date?  Very simply, I write:

rvm all do gem update -V

And if I want to check out some Ruby code, and see how it runs in all of the versions on my system, I can say

rvm all do ruby test.rb

If I just want to see the difference between doing something in 1.8, 1.9, 2.0, and 2.1 (without all of the patchlevels for 1.9.3), then I can just say:

rvm 1.8.7,1.9.3,2.0,2.1  do ruby test.rb

I’m already loving this feature, and can easily imagine cases — such as when teaching Ruby programming, and trying to show them the differences between versions — when this will be quite handy.

= and = aren’t equal

When I teach a Ruby or Python class, I always begin by going through the various data types.  My students are typically experienced programmers in Java, C++, or C#, and so it no longer surprises me when I begin to describe numbers, and someone asks, “How many bits is an integer?”

My answer used to be, “Who cares?”  I would then follow this with a demonstration of the fact that in these languages, numbers can be pretty darned big before you have to worry about such things.

But over the last few months, I’ve begun to understand the reason for this question, and others.  Indeed, I have begun to understand one of the reasons why dynamic languages can be so difficult for people to learn after they have worked with a static language.

Let’s take a simple example.  In a typical, C-style statically typed language, you don’t just assign a variable.  You must first declare it with a type.  You can thus say something like this:

int x;
x = 5;

In both Ruby and Python, you can do something similar: 

x = 5    # no type declaration needed

On the face of it, these seem to be doing similar things.  But they aren’t.

In a static language, a variable is an alias to a place in memory.  Thus, when I say “int x”, I’m telling the compiler to set aside an integer-sized piece of memory, and to give it an alias of “x”.  When I say “x = 5”, the compiler will stick the number 5 inside of that int-sized memory location. This is why static languages force you to declare types — so that they can allocate the right amount of space for the data you want to store, and so that they can double-check that the type you’re trying to store won’t overflow that allocated area.

Dynamic languages don’t do this at all.  Whereas assignment in a static language means, “Put the value on the right in the address on the left,” assignment in a dynamic language means, “As of now, the name on the left points to the object on the right.”

In other words, assignment in a dynamic language isn’t really assignment in the traditional sense.  There’s no fixed memory location associated with a variable.  Rather, a variable is just a name in the current scope, pointing to an object.  Given that everything in both Python and Ruby is an object, you never have to worry about assignment not “fitting” into memory.

This is also why you can say “x = 5” and then “x = [1,2,3]” in a dynamic language: Types sit on the data, not on the variable.  As long as a variable is pointing to an object, you’re just fine, because all object pointers are the same size.

The bottom line, then, is that  = in static languages and = in dynamic languages would seem, on the surface, to be doing similar things.  But they’re definitely not.  Once you understand what they are doing — putting data in memory, or telling a name to point to a value — many other mysteries of the language suddenly make more sense.

Ruby and Python and Felix and Oscar

I have been consulting, developing, and offering training classes in both Ruby and Python for a number of years now — more than 15 years in Python, and more than 7 years in Ruby. Inevitably, when someone from one of my courses hears that I use more than one language, they ask me, “So, which one do you prefer?”

One way to address this is to speak like a parent (which I am), and to give the analogy that just like I love all three of my children equally but differently, I love these two languages equally, but differently. But the most recent time I was answering this question, I asked myself, how do you like them differently?  What is appealing about each of these languages?  Why do you enjoy working with (and teaching) both of them?

I began to search for analogies that would describe the relationship between Ruby and Python, and the reason why I enjoy working with them both. I would sometimes extend the children analogy, saying that they’re like siblings.  But beyond the fact that I’m not their parent, I decided that there were enough differences to make the sibling analogy not quite appropriate. Perhaps it would be most appropriate to call them cousins, or even second cousins.

But then I hit upon another analogy, one which might indicate my age and television-watching habits as a child, but which I think is somewhat apt: The Odd Couple.

I remember the Odd Couple as an American sitcom from the 1970s, broadcast in endless reruns on certain stations, in which two divorced men become roommates and friends, despite their with wildly different habits and outlooks on life. (I should note that the Neil Simon play and movie, upon which the TV series was based, is far darker, and really surprised me when I saw it after years of watching the TV show.)

The viewers aren’t ever expected to prefer neatnik, uptight Felix or sloppy, happy-go-lucky Oscar, but rather to appreciate the differences between the two, and to see a bit of themselves in each character.  In some ways — and perhaps more philosophically than was ever intended — the play, movie, and show are there to tell us that there is no one “right” way to approach life, and that each has its advantages and disadvantages.  Balance is the key.

The more I think about it, the more I like this analogy, because it speaks to the differences between the languages, and the reasons why I love to work in each of them. Python, not surprisingly, is Felix: It’s clean, crisp, elegant, and engineered precisely. It’s no surprise that Python has been called “executable pseudo-code,” in that I’ve met a very large number of people (many of whom take my courses) who have been working with Python for months without knowing precisely what they were doing.

Python is conservative by nature, and that has served the language well for more than two decades. Indeed, you could argue that the entire 2-to-3 Python upgrade issue, which has been causing ripples of late, is the result of Python betraying this conservative culture, and making a clean break with past versions for the first time in its history. There are parts of Python that drive me crazy, such as len being a builtin function, list.sort not returning a value,  the limits on lambda. the need for both tuples and lists, and the way that super works.  But every language has its issues, and a very large number of them were improved or removed altogether in Python 3.

But other parts of the language are beautiful, such as the way in which operator overloading is done.  Sure, Ruby lets you rewrite + directly, but I think that there’s something about Python’s __add__ which tells newcomers that they should avoid messing with it until they know what they’re doing.  I have also grown to love list comprehensions (as well as dictionary and set comprehensions), even though I readily admit that the syntax is difficult for beginners.   Also, the Python standard library is just a joy to work with; you can really depend on things working pretty well.  And one of the things that people hate at first about Python, namely the required whitespace, is sheer genius in my book.  Decorators are also wonderful; while I don’t use them much, they are an elegant and powerful way to intercept function and class definitions, and do all sorts of wild stuff with them.

Ruby, on the other hand, is Oscar: It’s infinitely flexible, messy, and creative — but it works the way you want it to work.  Ruby inherited many of the characteristics of Perl, which Larry Wall deliberately meant to be close to natural human language.  Sure, it’s a minor miracle that Ruby’s syntax can be described using computers, given its complexity, but that complexity allows me flexibility, creativity, and intellectual excitement that I can’t get elsewhere.  Add blocks to the mixture, and you have a language which gives you raw building blocks that allow you to solve problems quickly, easily, and naturally, with less code than would otherwise be necessary. For example, ActiveRecord might have its problems, but I  generally love its API and the magic that it performs on my behalf.  The way that validations and associations look like declarations (but are actually class methods) is great, making for readable code.

Of course, Ruby has its problems, as well: The object model is elegant and simple — but nearly impossible for newcomers to the language to grasp. (I should know, I teach quite a lot of them.)  The fact that everything ends with “end” drives me a bit crazy. So do the differences between procs, lambdas, and blocks. And the “stubby lambda” syntax. But again, every language has its issues and trade-offs, and the ones that Ruby has made are more than reasonable for my work.

Matz has said that Ruby was optimized for programmer happiness, and Avdi Grimm has used the word “joy” to describe programming in Ruby — and I have to agree with both of them. Programming in Python feels more like solving a puzzle, but programming feels more satisfying; I’m unleashing my creative energies, and using the language to solve problems in the way that I want. Python is crisp and demanding, and Ruby is messy and fun.  You know, like Felix and Oscar.

Of course, the style of the languages might be very different — but at the end of the day, there’s a lot of overlap between the two. IPython and Pry, PyPi and RubyGems, dicts and hashes, “def initialize” and “def __init__” — if you know Ruby, then learning Python isn’t very difficult, and vice versa. Both are byte compiled, interpreted, object-oriented, strongly typed, dynamic languages. Both have a GIL, which drives people crazy with threading. Both make reflection and metaprogramming easy and natural. Both languages encourage modularization of code, with short functions. Both encourage you to test your code. Both have active open-source communities. And both can be used to solve lots of problems, easily and quickly.

Indeed, the languages are similar enough that I’ve often “stolen” ideas, examples, and exercises from my Python classes for my Ruby classes, and vice versa.  And I’ve often thought, when reading the documentation for a method on a built-in Ruby class, that it’s a shame that there’s no Python equivalent… only to discover that there is.

I love Python’s PEP process, which makes it easy for the community to document and discuss changes to the language.  And yet, somehow, Ruby has moved from version 1.9 to 2.0 to 2.1 in the last few years, with great improvement on all fronts, without such a clear-cut process.  I’m not quite sure how Ruby manages to do it, but it does, and rather impressively.

So, which do I prefer?  For Web development, I use Ruby (and Rails or Sinatra).  For small projects and problem solving, and sysadmin types of things, I use Python.  If I had to do large-scale calculations, then NumPy would make Python a no-brainer.  As a first programming language to teach young people, I think that Python is an almost perfect choice.  And for mind-twisting, understand-how-languages-work examples, Ruby beats everyone hands down.

At the end of the day, I’m happy to have a foot in each camp, and to be comfortable with both. Because sometimes you want to be Felix, and sometimes you want to be Oscar, and it’s always nice to have to choose between the two.