Factor Language Blog

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:

Array.new(size=0, 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

array.at(index) -> 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.

array.rassoc(key)

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.