3.07.2008

Erlang List Comprehensions: By Necessity

List comprehensions are a powerful programming language construct that provide a concise means of dynamically generating lists of values. Erlang and Python, amongst other languages, support them.

There is an interesting observation to be made about Erlang list comprehensions, namely that emergent properties of Erlang make list comprehensions a practical necessity as opposed to merely being "kewl" syntax.

I had to write a simple function that takes a point tuple {Row,Column} identifying a square on a bounded plane (think checkers) and return the squares that neighbor it to the north, west, south and east (so to speak).

The bounded plane has point {1,1} in the top-left hand corner, with rows that increment downwards (as per Excel) and columns that increment to the right. So, given the point {2,2}, the function should return {1,2} (the point to the 'north'), {3,2} (south), {2,1} (west) and {2,3} (east). Also, the notion of a bounded plane implies that, given an edge point e.g. {1,2}, the function should return only the three points {1,1} (west), {1,3} (east) and {2,2} (south), as there is no point to the north: it is 'out of bounds'. Finally, given a corner point e.g. {1,1}, there are only two neighbors {1,2} (south) and {2,1} (east). Simple enough, yes?

Let's take a look at how this can be implemented in a couple of programming languages before admiring the solution that employs list comprehensions.

Here are the unit tests for what I previously described using C# 2.0 and NUnit 2.4.3.0:


[Test]
public void TestFourNeighboredPoint()
{
IList<Point>neighbors = Point.Neighbors(new Point(2,2));
Point[] expectedNeighbors = new Point[4] { new Point(1,2), new Point(3,2), new Point(2,1), new Point(2,3) };

Assert.IsTrue(neighbors.Count == 4);
Assert.IsTrue(Array.TrueForAll(expectedNeighbors, delegate(Point p) { return neighbors.Contains(p); }));
}

[Test]
public void TestThreeNeighboredPoint()
{
IList<Point> neighbors = Point.Neighbors(new Point(1,2));
Point[] expectedNeighbors = new Point[3] { new Point(1,1), new Point(1,3), new Point(2,2) };

Assert.IsTrue(neighbors.Count == 3);
Assert.IsTrue(Array.TrueForAll(expectedNeighbors, delegate(Point p) { return neighbors.Contains(p); }));
}

[Test]
public void TestTwoNeighboredPoint()
{
IList<Point> neighbors = Point.Neighbors(new Point(1,1));
Point[] expectedNeighbors = new Point[2] { new Point(1,2), new Point(2,1) };

Assert.IsTrue(neighbors.Count == 2);
Assert.IsTrue(Array.TrueForAll(expectedNeighbors, delegate(Point p) { return neighbors.Contains(p); }));
}

(Aside: I use both a generic IList<point> and a Point[] so I can Array.TrueForAll(), which is something of a poor man's Array#map. This way we avoid having to iterate, thus keeping the code very concise, but at the expense of this anomaly).

Now, the implementation of Point.Neighbors written in a curly-brace language - i.e. without the benefit of list comprehensions - could resemble something like the following C# 2.0:

internal static IList<Point> Neighbors(Point p)
{
IList<Point> neighbors = new List<Point>();

if (p.Row - 1 > 0)
neighbors.Add(new Point(p.Row - 1, p.Column)); // north

if (p.Row + 1 <= MAP_SIZE)
neighbors.Add(new Point(p.Row + 1, p.Column)); // south

if (p.Column - 1 > 0)
neighbors.Add(new Point(p.Row, p.Column - 1)); // west

if (p.Column + 1 <= MAP_SIZE)
neighbors.Add(new Point(p.Row, p.Column + 1)); // east

return neighbors;
}

This code obviously works because the temporary variable neighbors is mutable. We mutate neighbors (i.e. change its value) depending on the bounds we check on the Row and Column of the given Point p.

Now, this code doesn't translate into Erlang very elegantly at all (to put it mildly), because Erlang doesn't support mutable variables. In Erlang, after a value has been bound to an identifier, the value cannot change. This language property is known as single-assignment and is not unique to Erlang. So, Erlang doesn't really have variables, at least if we take the term literally, in the sense that they can vary.

To illustrate what impact single assignment has on code written in the style above, here is the closest possible translation of the curly-brace code above in Erlang:

!! DO NOT DO THIS !!

if
% Normal case: not on any boundary
Row > 1, Col > 1, Row < ?MAP_SIZE, Col < ?MAP_SIZE ->
[{Row-1, Col}, {Row, Col+1}, {Row+1, Col}, {Row, Col-1}];

% Row is 1, but Col is not on a boundary
Row == 1, Col > 1, Col < ?MAP_SIZE ->
[{Row, Col+1}, {Row+1, Col}, {Row, Col-1}];

% Col is 1, but Row not on a boundary
Col == 1, Row > 1, Row < ?MAP_SIZE ->
[{Row-1, Col}, {Row, Col+1}, {Row+1, Col}];

% Row is boundary, Col not on a boundary
Row == ?MAP_SIZE, Col > 1, Col < ?MAP_SIZE ->
[{Row, Col-1}, {Row-1, Col}, {Row, Col+1}];

% Row not boundary, Col on boundary
Row > 1, Row < ?MAP_SIZE, Col == ?MAP_SIZE ->
[{Row-1, Col}, {Row, Col-1}, {Row+1, Col}];

% Corner case top left
Row == 1, Col == 1 ->
[{1,2},{2,1}];

% Corner case bottom left
Row == ?MAP_SIZE, Col == 1 ->
[{?MAP_SIZE-1, Col}, {?MAP_SIZE, Col+1}];

% Corner case top right
Row == 1, Col == ?MAP_SIZE ->
[{Row, Col-1}, {Row+1, Col}];

% Corner case bottom right
Row == ?MAP_SIZE, Col == ?MAP_SIZE ->
[{?MAP_SIZE, ?MAP_SIZE-1}, {?MAP_SIZE-1, ?MAP_SIZE}];

% else
true ->
io:format("Logic error! Row: ~p Col: ~p", [Row, Col]),
error
end.

Because Erlang doesn't support mutable variables, we're forced to check every condition prior to assigning the return value. In this instance, we only need to check four basic conditions but the possible permutations of the result set leads to verbose (and unmaintainable) code. So, how can we elegantly satisfy our requirement in Erlang?

List Comprehensions to the Rescue

As you've probably guessed by now, the proper way to satisfy this requirement is to use a list comprehension:

adjacent_points({Row,Col}) ->
[{R1,C1} || {R1,C1} <- [{Row-1,Col}, {Row+1,Col}, {Row, Col-1}, {Row, Col+1}],
R1 > 0, R1 =< ?MAP_SIZE, C1 > 0, C1 =< ?MAP_SIZE].

Believe it or not, these two lines of code replace the dozen or so lines of code of C#, not to mention the naive Erlang implementation.

Anatomy of a List Comprehension

List comprehensions are powerful, because they enable creating lists from one or more source lists, and they emit values that can be selectively filtered using one or more filters.

Erlang list comprehensions are enclosed in square brackets. The initial {R1,C1} preceding the || is the constructor, which can be any expression. In this example, it will simply instantiate the point tuples that we want to generate:

[ {R1,C1} || ... ]

Immediately following the || is a generator which is composed of a pattern {R1,C1}, followed by "<-", followed by the list. In our case, the list is simply in-lined:

[ {R1,C1} || {R1,C1} <- [{Row-1,Col}, {Row+1,Col}, {Row, Col-1}, {Row, Col+1}], ... ]

Each of the generated values in a list comprehension must satisfy all of the filters that are specified in the list comprehension (if any). In our case, there are four filters, each of which equate to the conditions that we check in the curly-brace implementation, but with far less baggage:

R1 > 0, R1 =< ?MAP_SIZE, C1 > 0, C1 =< ?MAP_SIZE

Again, each of the tuples emitted by the generator will be checked against each of these filters. All of the filters must be satisfied (i.e. evaluate to true) for the constructor part to be invoked. These filters will evaluate to false for tuples that are out of bounds.

Even though our example used a single generator and multiple filters, it should be noted that list comprehensions can be any arbitrary number of generators or filters. You should also be aware of Erlang's facility to efficiently generate bit strings with Bit String Comprehensions, which work very similarly to what we have just seen.

Re-Entry Checklist

It is a curious property that the incidence of defects in software remains constant irrespective of the number of lines of code written. Thus as an industry, we should be naturally inclined to use concise languages. List comprehensions are one way that Erlang affords a succinct notation. Succinct programming languages exhibit less defects than their more verbose counterparts because there is simply less room for error. Some programmers assert that this leads to more obtuse syntax, but in consideration of the constant defect ratio, I believe that this trade off is fully justified.

Afterword

My thanks to Daryn Holmes and Darren Bishop for providing several illuminating, alternative implementations of the code above in various programming languages, and to the folks on #erlang IRC.


6 comments:

Anonymous said...

In a production environment we need to consider code maintainability, I feel that you have skimped over this point in your post. On a number of occasions I have read that developers would rather take 10 minutes to write code that can be understood in 1 minute, as opposed to taking 1 minute to write code that takes 10 minutes to be understood.
In fact Rick Cadruvi’s Coding Principles and Standards state:
“Make code easy to understand quickly. It should take no more than 30 seconds to understand a line of code, and no more than 10 minutes to understand a routine. If the reader has to sit down and figure it out, the code is poorly written. Poorly written code is guaranteed to have bugs!” – The ‘poorly written part’ is very subjective in this context, but may still hold true.

It also states that we should make code concise…but also understandable:

“Make code understandable and concise. Think about the code just written and see if there's a shorter, more concise and understandable way of writing it. However, sometimes taking a shortcut to write the code smaller can make it LESS understandable--so keep in mind that understandability is the main goal!”

More often than not, less lines of code adds to the complexity – provided the solution is not cluttered with dead code. Surely writing maintainable production code trumps less lines of code? I would expect this to hold true particularly in a thoroughly tested development environment.

A departing shot…
I can’t help but feel that your 1 line list comprehension solution took more than 10 minutes to write and will take more than 10 minutes to understand.

Darren Bishop said...

I agree in principal and well, in many cases in practice too, with Daryn. I do however think a professional (read: adept) programmer, for whatever langugage, that is one worthy of writing 'production code', should be able to read and understand a 'language construct' in well under 1o seconds, let alone 10 minutes.

My gripe is with those who believe horizontal scroll blindness is a lesser affliction than vertical scroll blindess, which I think a lot of people may agree is more natural anyway.

Immo Hüneke said...

I found this article very instructive - I now understand what a list comprehension is and when and how to apply it.

However, the full Erlang example was rendered less comprehensible than it might have been by the typo in the inequality expressions (which is corrected where the filters are considered in isolation).

Edward Garson said...

@darynholmes: List comprehensions might fall into the same 'comprehensibility category' as regular expressions. That is to say, when you first encounter them, they're not exactly the epitome of readability. However you get used to them and you learn how to read them. Before too long, you come to appreciate their succinct beauty. The second paragraph that you quote ("Make code understandable...") is in alignment with constructs such as list comprehensions, with the caveat that you need to learn to work with them first. In fact I would go so far as to say that without the benefit of constructs such as regular expressions and list comprehensions, code becomes unnecessarily verbose and more difficult to comprehend as a result. So in effect we're both in agreement, and I suspect if you gave list comprehensions a chance then you might come around to appreciating them. And yes, that means investing more than 10 minutes toward them, particularly as without them you can see how dire some kinds of code can be in Erlang.

Edward Garson said...

@darren bishop: Sorry for the formatting with respect to horizontal scrolling; I favor a wider horizontal scroll area than most. I've now reduced the horizontal width of the published code in line with your comment.

Edward Garson said...

@Immo Huneke: Thanks for the heads up, this happened when I escaped the equality expressions in html. Duly fixed!