Thursday, December 22, 2005

Approaching functional programming from a procedural mindset

I found an amusing article about allegedly redundant methods in Ruby's Array class that demonstrates the difficulty some people have when first trying to understand functional programming. From reading the author's weblog, it seems his main (only?) programming experience comes from Java. Being accustomed to Java's collections and arrays, but he does not understand the value of a powerful collections library like Ruby's precisely because he is accustomed to writing explicit loops and iteration patterns, rather than combining bulk collection operators in abstract ways. While I don't know much about Ruby, I instantly recognized many of the methods he deemed "redundant" as standard functional programming idioms that I take for granted in Factor, and couldn't live without. They are the utility glue for reshaping data between invocations of higher-order functions. So while I'm not a Ruby expert, most of the "redundant" methods have direct analogues in Factor, and I found enough compelling usage of them to warrant attention.

So lets go through his list; I've skipped some of the entries because I do not know Ruby well enough to make an informed comment:, obj=nil)
This method creates an array that has size copies of the object. Why? Have you ever needed to create an array/list that begins its life containing more than one copy of the same object? I don't think I have. I can imagine a few uses cases, especially if Ruby doesn't distinguish primitive types from objects like Java does; but I don't think they're nearly common enough to justify explicit support in the API. On the rare occasions when you need this, there's a fill method you can call after constructing the list.

Actually creating a repeated sequence of the same element is very useful in practice. Here are some uses of repetitions in the Factor library:
  • Creating mathematical zero vectors. Factor's UI library uses vector math extensively to avoid loops, simplify layout management code, and avoid duplicating code that performs the same logic, except with horizontal or vertical orientation being a parameter (consider split panes, scroll bars, and so on).
  • The prettyprinter uses repetitions to indent source code in a natural way.
  • The type inference code in the compiler uses repetitions to avoid code duplication.

array.each_index {|index| block } -> array
"Same as Array#each, but passes the index of the element instead of the element itself." Am I missing something, or is this just a for loop across the array indexes? Why not just use a for loop, or whatever Ruby's equivalent is?

If you want to argue that any concept is redundant, it is the "for" loop. Higher-order functions can express iteration in a much nicer way. Both iteration over elements and iteration over indices is useful: in Factor, integers are sequences of predecessors, so you can iterate over elements with [ ... ] each and iterate over indices with length [ ... ] each -> obj or nil

As near as I can figure, this is exactly the same as using array brackets except it uses a method call. If there is a difference, it's pretty subtle. DRY, anyone?
My wild guess is that the method exists because of Ruby's superior reflection support. You can get a method object corresponding to 'at' at runtime, pass it somewhere, and invoke it. Try getting a method object for the '[]' or '+' operator in Java for reflective use. You can't. Here is an example where this causes major pain.

array.fetch(index) -> obj
This one is mostly the same as array brackets, but there is one difference. It will throw an IndexErr rather than returning nil if you go outside the range. But will anyone remember that difference and which does which when reading code? Sometimes when presented with different possible options, it's best just to pick one. Don't provide every possible option in an API.

Both bounds-checking and silently-failing sequence access is useful. Factor has both in the form of the nth and ?nth words. Neither word is used very frequently, because Factor encapsulates most collection operations in generic combinators; however having both words make code clearer and shorter than one alone.

array.pop and array.push(obj, ... )
Someone pushed a stack into the list. Didn't we learn from that mistake in Java? (OK. push is really just append, but still, pop? And if you have pop why do you need last? Does anyone here remember DRY?)

Why clutter the code with a stack class when you can use an array? Factor has push, peek, pop and pop* words for working with arrays-that-are-stacks (pop* removes the last element without returning it). If I remove pop just because peek already exists, then I'll just have to change all the usages of pop to duplicate the body of the definition of pop; and if somebody wants to argue that code duplication is not that bad, they might as well stop reading here.

Is it a list? Is it a stack? Is it a map? It's three, three, three data strcutures in one!

Yes, and there's nothing wrong with that. Association lists, while they suffer from linear lookup time, are occasionally useful where you want to have a mapping together with a certain intrinsic order. For example, Factor's generic word code takes the hashtable of methods defined on a generic, converts this to an association list, then sorts the association list according to the partial ordering of classes. Finally, the sorted association list is used to generate code.

array.transpose --> an_array
And now it's a matrix! What's next? a B-tree?
It might surprise the author to learn that mathematically, a matrix is a two-dimensional array. In Factor, you can perform mathematical operations on vectors, such as vector addition, dot product, and so on. The contributed math library defines even more: vector projection, matrix addition and multiplication, polynomials, quaternions, and so on. And everything uses an arrays of numbers, because mathematically that's what these structures are. Polynomials in one variable form a vector space over the complex numbers; since multiplying a vector by a scalar is the same concept as multiplying a polynomial by a scalar, why implement it twice? Ditto for matrices.
With the math rant over, I can list additional non-mathematical usages of a matrix transpose in the Factor library:
  • The hash>alist word, which converts a hashtable to the oft-lamented association list, works by extracting an array of keys from the hash, then extracting an array of values, then it creates a two-element array from these, and finally, it performs a matrix transpose to get an array of key/value pairs:
    : hash>alist ( hash -- assoc ) 
    dup hash-keys swap hash-values 2array flip ;
    This approach to algorithm design requires some practice, but the rewards include more elegant code, and a clearer mental framework for thinking about bulk operations with collections.
  • The inspector uses a similar technique. It builds up a table of strings represented as an array of columns, pads the strings in each column to the same width, transposes the matrix so that now it is an array of rows, and outputs each row.
  • I found four usages of flip in the compiler, all dealing with technical aspects such as value unification and dealing with recursive blocks.
  • The layout manager code in Factor's GUI toolkit does something similar to the inspector's padding of text columns; the frame layout uses transposition and reduction to ensure that each gadget is padded with respect to its row and column. I don't even want to think about what this code looks like when written in a procedural style.

array.reverse and array.reverse!
Have you ever needed to reverse a list outside of a job interview? Iterate through the list in reverse order, yes; reverse the list, no.
This is just silly. Factor reverses sequences, and not just for iteration, in a number of places:
  • In the parser. Syntax tokens are consed onto the head of the current node of the parse tree; when parsing of the node is finished it gets reversed. This is a very, very common idiom in Lisp; Factor only uses it occasionally.
  • The C library interface reverses an array of register numbers to handle differing low-level assembly calling conventions.
  • The library includes a functional queue with O(1) amortized enqueue/dequeue operations. Of course, the implementation of this involves a reverse.
  • The routine to convert an integer to a string repeatedly divides the integer by the numerical base, adding digits to a string; the string is reversed at the end, then returned.
  • The routine to convert an integer to a big-endian byte string is simply defined as follows:
    : >be ( x n -- string ) >le reverse ;
    This is an exceptionally elegant implementation: it converts it to little-endian, then reverses it.

Reverse iteration in Factor is implemented by first creating a virtual reversal sequence using reverse-slice, and then applying one of the standard combinators such as each, map, and so on. I'm not sure if Ruby is the same, but in either case, reverse iteration can be elegantly implemented by reversing your sequence first; no need to implement all your combinators twice, with forward and backward direction.

Do you really need any of this getting in your way? Possibly you need one or two of these methods; but how often, and how many? These methods are all way beyond the 80/20 point. I promised today I was going to show you all the methods you could take out of the Array class and still have a humane, indeed a more humane interface. I'm afraid I haven't fulfilled my promise. I got tired before I got halfway through the class and started skipping some cases. Try reading the entire documentation yourself from start to finish, and you'll see what I mean. It's just too damn big. A smaller, simpler API would be more humane.
As you can see, most of the author's complaints stem from a lack of understanding of functional programming style. In a language without higher order functions, the programmer writes loop after loop after loop, taking care to set up indices, always pulling elements out of collections and storing them back one by one. The result is error-prone, and full of duplication of effort. The duplication goes unnoticed because there is so much boilerplate anyway, that attempting good programming practice makes little difference. However, one should not let their past experience with such broken tools cloud their judgement when it comes to evaluating something new they do not fully grasp yet.


riffraff said...

In general I think you have hit the nail on the head, but a note:
Array#at really is a slightly different version of Array#[].
Both are mathod calls, but the latter has some overloading that allows passing ranges, start/length pairs and somethign else.
There are no operators that are not messages in ruby, so you could do [1,2,3].method(:[]).call(-1) and get "3" just fine.

(where :foo is a symbol)

Jason Marshall said...

I don't believe his thesis was about the stupidity or wisdom of each method. The first few paragraphs end up with him asserting that 78 methods is far far too many methods for any one interface.

He then proceeds to give a priority to each of the methods in the interface. A few he points out, rightly in my opinion, belong in -some other- interface. For the remainder, he questions the utility. In some cases, as you say, he's clearly wrong.

However, even if he's only half-right, the interface for this class could still be cut by half: 1/4 by subtyping, 1/4 by eliminating rarely-used methods. Do you honestly believe that a method you used only 4 times in a compiler, or once in a number-to-text converter, belongs in one of the most fundamental types in the language? These are not precisely common usages.

What the language designer needs, what the core API writers need, is not what 90% of the user base needs. Without a sufficient quantity of these 'customers' around to give value judgement, we have a young language where one of the 'starter' types has already balooned to rival the size of the most top-heavy, unapproachable classes in Java. I'm afraid to guess what Array will look like in a couple of major revisions, once more of these 'common' idioms are identified.

Slava Pestov said...

Jason, if I use the same piece of code four times, I factor it out. Anything else would go against good programming practice. Unlike Ruby, I don't have methods "inside" classes in Factor. If I define a new utility word inside some vocabulary, then any other piece of code can use the vocabulary and call this word. It only makes sense to group all sequence-related words in one vocabulary. I presume Ruby with its "Array" class is following the same reasoning.

David Gurba said...

I have to say that I agree with Slava's interpretation on the matter. This Array class issue is/was a hot topic on the Ruby mailing list(s) recently.

I do believe many aspects to its size are directly related to the functional paradigm that Ruby allows...again as Slava said.

I come from heavy Java usage at CalPoly, and have explored Ruby for the past ~1.5 years...I think it is really a great language. I also have alot of experience with other languages like ada95, C, ML, C++. For certain applications functional programming is both easier to write and to understand (1 year down the road when you need to maintain something).

Working with PHP at work right now (designing websites/internet applications) with a 'functional programming' approach (no classes persay, just method calls) is *really* ugly and everything is very piecemeal/boilerplate/redunant/kludged together (haha).

Rails (a Ruby framework) is a nice example of how functional programming can help with this (meta programming, ect.) in both readability and maintainability. [end shameless plug]

I did want to mention that programming language tools and GUI tools are not 'out of the ordinary' use-cases for methods included in an API. You just take them (GUI/language tools) granted since they exist already. Somebody's gotta write it though, and the proper API calls will make that easier.

As always Slava, reading your posts is both informative and entertaining.

riffraff said...

jsson, actually 26/78 methods in Array come from the Enumerable mixin, so you can think that 1/3 of the methods are taken from free by subclassing. It is not half as you'd prefer but it is quite a bit.

Florian Gross said...

Thanks for defending the position Ruby is also taking on this.

True, it might be right that defining a lot of methods dealing with a single kind of data entity is more problematic for the Java guys who can't define new methods in the most natural way without changing the source code where the data type is originally defined.

So I can see why they would think having much built-in functionality (that in their language could not have been implemented by other people than those who inititally authored that data type) might make things overly complex.

Personally, I think being able to add operations to everything is one part that hugely enhances languages like Ruby and C#. Even if Ruby's approach (where you can also override methods defined elsewhere) might have some downsides.

Anyway, thanks for this posting. It was a very interesting read and I think that Ruby can still learn a lot from Factor.

supplements said...

In this document, we'll take a tour of Python's features suitable for implementing programs in a functional style. After an introduction to the concepts of functional programming, we'll look at language features such as iterators and generators and relevant library modules such as itertools and functools.