Ladies and Gentlemen, The Editor War

Scene opens. The Lakota coffee shop in Columbia, MO.

Jane: ... and the other has been really interesting. It's Anthropology, with Jim Metcher.

Ray: (lights up) Yes! I actually got to take one of Metcher's classes during my brief stint in the evening program.

Jane: Are a Mizzou student?

Ray: Close. I graduated from MST in '06. I'm workin' now.

Jane: What do you do?

Ray: I help machines think. I'm a programmer.

Jane: Spiffy! So what's new in the fast-paced world of "programming"?

Ray: Well, lot's of things I guess. Let's see... new languages coming out as usual. PHP making some controversial design decisions regarding namespace. 50th anniversary of Lisp was just celebrated at OOPSLA; I bet there were some great talks at that. Oh yeah, and I just read about a new development in The Editor War.

Jane: ... The editor what?

Ray: War. The Editor War... it's this infamous feud. (waves hand dismissively)

Jane: Feud? (interest grows at the scent of scandal) Over what?

Ray: Which text editor to use.

Jane: (Smirk) No, really. What is it about? I'm actually interested this time, you don't have to make things up to amuse me.

Ray: No... (Slowly raises hand to forehead), that's actually what it's about.

Jane: (Confused) That doesn't sound like a very political decision. Is there some, like, protocol or something that has to... (pauses) I thought text was all sort of... compatible. (glances downward) I guess I don't much about this stuff.

Ray: Actually, you've got a decent grasp of it. While there have been a few new standards in recent years to accommodate different languages, text is overall very compatible from one editor to the next.

Jane: In that case, I don't get it. What other technical hurdle would force all programmers to use the same editor?

Ray: Ahh! I see the source of your confusion. That's not the issue. We're not debating the adoption of an official industry-wide standard editor. Nothing along those lines. It's a matter of personal preference.

Jane: (Disappointed) So it's just different people choosing a different tool? Aren't you exaggerating a bit by calling it a feud?

Ray: I see where you might think that, but believe it or not, I've been to parties where shouting matches broke out spontaneously at the mention of either of these editors.

Jane: Really?

Ray: Really.

Jane: Wow. So this has been going on for what, weeks now?

Ray: A bit longer than that.

Jane: Months?

Ray: It has been going on for over 25 years.

Clone Wizards of Time and Space

The talk, Code Generation: The Safety Scissors Of Metaprogramming by Giles Bowkett.

The quote, "This is how Lisp guys think of Lisp and the Lisp community: intergalactic voluntarily bald clone wizards of time and space who the womens are be lusting fors."

He literally said that. I'm not paraphrasing. One more time in case you missed it.

Intergalactic Voluntarily Bald Clone Wizards of Time and Space Who The Womens Are Be Lusting Fors.

I for one am quite offended! I resent the continuing perception that Lispers are smug and arrogant. Nothing could be further from the truth! We do not see ourselves as some sort of secret society with magic powers beyond the comprehension of you mere mortals.

Signed,
Ray, Squire of the Grand Recursive Order of the Knights of the Lambda Calculus

Learn Recursion

Todays message is short and sweet.

I was just reading chapter seven of Beautiful Code, "Beautiful Testing". As the chapter begins, the reader is challenged to attempt writing a binary search. Here's mine.

int search(int[] arr, int target) {
    return arr.length == 0 ? -1 : search(arr, target, 0, arr.length-1);
}

int search(int[] arr, int target, int min, int max) {
    if (min >= max) return target == arr[min] ? min : -1;
    int middle =  (max + min) >>> 1;
    if (arr[middle] > target) return search(arr, target, min, middle-1);
    if (arr[middle] < target) return search(arr, target, middle+1, max);
    return middle;
}

Yes, it's in Java. I'm not going to rewrite it in eight other languages because that's not the point, for once.

Here's the point: If you call yourself a programmer and don't grok this recursion business, fix it. Now.

This has been a public service announcement brought to you by the "People Who Will Not Take You Seriously If You Don't Understand Recursion" Foundation.

The arrogance of demanding evidence

"No one has the right to destroy another person's belief by
demanding empirical evidence." — Ann Landers

This is widely quoted but I haven't found a full citation of the original source. Thus, it's remotely possible that this is a misquote, out of context, etc...

Still, I'm not too worried about misquoting a shared pen name. My main concern is that in 2008, it is still possible to read a quote like this without flinching. One might even agree!

The statement implies two things. The first is that the freedom of speech should be abolished. (We'll look past that one for now.) The second is that it is unreasonable, inhumane, and simply impolite to expect people to base their worldviews on ... the world. In intellectual discourse, once someone says the magic words "I believe," it is inappropriate for other parties to continue further.

In fact, a more honest phrasing of the Ann Landers quote might be:

"Don't speak up; you might inadvertently cause someone to change their mind."

I've had my beliefs turned upside-down by empirical evidence dozens of times in my life, and I'm probably not done. I used to believe that aliens crashed in Roswell, New Mexico in 1947. I used to believe that Uri Geller was psychic. I used to believe that homeopathic preparations had medicinal properties. I used to believe that computers couldn't think — and would never think.

I am a better person for being able to change my mind.

"It is far better to grasp the universe as it really is than to persist in delusion, however satisfying and reassuring." — Carl Sagan

"Isn't it enough to see that a garden is beautiful without having to believe that there are fairies at the bottom of it too?" — Douglas Adams

Subsequences With BGGA Closures

Just a quick followup on Returning '(()) Considered Difficult. I just rewrote the "subsequences of length n" exercise yet again (surprise, surprise), this time using the Java BGGA prototype by Neal Gafter et al. I really like being able to abstract away the accumulation loop.

import static com.cadrlife.ListUtils.*;
...
private static <T> List<List<T>> subn(int n, List<T> list) {
    if (n == 0) {
        return Collections.<List<T>>singletonList(new ArrayList<T>());
    }
    if (list.isEmpty()) {
        return new ArrayList<List<T>>();
    }
    T first = list.get(0);
    List<T> rest = list.subList(1, list.size());
    return addAll(collect(subn(n-1, rest), {List<T> sub => push(first, sub)}), 
                  subn(n, rest));
}

A word on syntax: Some people have come down on the {=>} closure syntax but I wonder if they have actually used it. This was my first time using BGGA; everything compiled and worked on the first try. I can't say the same about trying to simulate closures with anonymous Transformer classes using the Apache Commons CollectionUtils version of collect.

Just in case you don't have com.cadrlife.ListUtils in your classpath, here are the obvious definitions of collect, addAll, and push.

package com.cadrlife.ListUtils;
...
public static <A,B> List<B> collect(List<A> list, {A => B} function) {
    List<B> result = new ArrayList<B>();
    for (A element : list) {
        result.add(function.invoke(element));
    }       
    return result; 
}
public static <T> List<T> push(T el, List<T> list) {
    list.add(0, el);
    return list;
}   

public static <T> List<T> addAll(List<T> a, List<T> b) {
    a.addAll(b);
    return a;
}

FunctionalJ: Steve points out that the last bit could be done this way, using the Java library FunctionalJ.

DynReflect reflect = new JdkDynReflect();
Function1 pushFirstElem = reflect.staticFunction(
        AnnotatedSequencer.class, "push").f2().bind(first(list));
return addAll(map(pushFirstElem, subn(n - 1, tail(list))),
        subn(n, tail(list)));

Be forewarned that using reflection to simulate first-order functions in this way will sacrifice compile-time verification.

Returning '(()) Considered Difficult

Suppose you want a function to find all subsequences of a list with a certain length. For instance, the subsequences of (1...5) with length 2 are as follows.

(1 2) (1 3) (1 4) (1 5)
(2 3) (2 4) (2 5)
(3 4) (3 5)
(4 5)

This is not a red-herring example cooked up just to make Java look bad. This actually came up at work! I did something along these lines. Yuck.

private static <T> List<List<T>> subn(int n, List<T> li) {
  List<List<T>> ret = new ArrayList<List<T>>();
  if (n == 0) {
      ret.add(new ArrayList<T>());
      return ret;
  }
  if (li.isEmpty()) {
      return ret;
  }
  T x = li.get(0);
  List<T> xs = li.subList(1, li.size());
  for (List<T> sub : subn(n-1, xs)) {
      sub.add(0, x);
      ret.add(sub);
  }
  ret.addAll(subn(n, xs));
  return ret;
}

However, that was not the way my thoughts originally took shape. I think in Lisp.

(def subn (n li)
 (if (is 0 n) '(())
     (no li) '()
       (join (map [cons (car li) _] (subn (- n 1) (cdr li)))
             (subn n (cdr li)))))

Then I moved it to Haskell for greater clarity.

subn 0 _      = [[]]
subn _ []     = []
subn n (x:xs) = map (x:) (subn (n-1) xs) ++ subn n xs

With great pain, I converted those three lines of Haskell into the ugly splatter of Java you saw above. Later on, I started playing around with Scala and gradually compacted the Java into something strikingly similar to its Haskell ancestor.

def subn[T](n: int, li : List[T]) : List[List[T]] = (n,li) match {
   case (0,_)     => List(Nil)
   case (_,Nil)   => Nil
   case (_,x::xs) => (subn(n-1, xs) map (x :: _)) ::: subn(n, xs)
}

The title of today's post refers to the inordinate amount of trouble it is to simply return "The list containing the empty list" in Java. I tried such monstrosities as these:

Collections.singletonList(Collections.EMPTY_LIST) // List<List>
Arrays.asList(Collections.emptyList()) // List<List<Object>>
Collections.singletonList(new ArrayList<T>()) // List<ArrayList<T>>
Collections.singletonList((List<T>)new ArrayList<T>()) // List<List<T>>

The last option does give the correct type, but it causes a compiler warning and is not much less cumbersome than the naive approach, i.e.:

List<List<T>> ret = new ArrayList<List<T>>();
ret.add(new ArrayList<T>());
return ret;

So here's a challenge for you Java developers out there. What would you change about the admittedly sloppy Java code at the beginning of this post? I'm issuing an all points bulletin to the refactoring mavericks (Mike, James), the simple-design visionaries (Steve), and the speed-freak optimizers (Dan). I wouldn't even mind seeing a C# version (Ethan), or an improvement on the Haskell (Eric).

Incidentally, I know some people think recursion is hard to read. I'd love to see an iterative solution as well.

P.S. I realize that the comment boxes don't hold code blocks very well. Feel free to link to a solution.


Updates:
Based on your input, I am now happy to give three different ways of returning '(()) in one line. I am only including ways that would work in the context I gave (i.e. the inner list must be mutable). The last is my favorite because the others cause compiler warnings.

return Arrays.<List<T>>asList(new ArrayList<T>());
// Type safety : A generic array of ArrayList is created for a varargs parameter

return new ArrayList<List<T>>() {{add(new ArrayList<T>());}};
// The serializable class does not declare a static final serialVersionUID...
// Ricky points out that this is an "Eclipse warning".

return Collections.<List<T>>singletonList(new ArrayList<T>());
// No warnings :)

Eric has blessed us with a version in Factor (not to be confused with my aversion to Factor). He also added a Haskell version using list comprehensions to achieve better laziness properties.

Meanwhile, back in Javaland, Dan suggested using SortedSet, particularly the subSet method. This seems to be a dead end in this case, but is certainly a useful corner of the Collection hierarchy.

After briefly attaining List Enlightenment, Thomas produced an implementation in Java with no recursion. Aside from being much longer and totally opaque, it also has worse performance charactoristics. It essentially produces every subsequence and then filters by length, similar to the Haskell one-liner suggested in the comments.

Speaker Spotlight - Simon Peyton-Jones

Simon Peyton-Jones was one of the designers of the Haskell programming language. Here are links some of his presentations.

A Taste of Haskell
Introduction to Haskell with XMonad as an example
(video 1) (video 2) (slides)

Composing Contracts - An Adventure in Financial Engineering
Very interesting case study on domain specific languages
(video) (slides)

Nested Data Parallelism in Haskell
Beating FORTRAN is the name of the game!
(video) (slides)

Taming Effects - The Next Big Challenge
The virtues of purity in functional languages
(video) (slides)

Transactional Memory for Concurrency
OSCON 2007 Keynote
(video) (slides)

Programming in the Age of Concurrency: Software Transactional Memory
Interview with Simon and Tim Harris about Transactional Memory
(video)

Type-driven Testing
Demonstration of the Haskell library QuickCheck
(video) (slides)

Haskell and Erlang: Growing Up Together
At Erlang Factory 2009
(video)

Interview at QCon 2008
(video)