The just-released Dabble DB is, to my mind, one of the most innovative pieces of software since the spreadsheet. It’s a relational database that can figure out your data relations for you. It’s a spreadsheet that can run structured queries on your data. It’s an on-line calendar with RSS feeds. It’s a web form processor that understands dates like “next Tuesday.” It’s a platform for JavaScript development. It’s so cool.

Ah, the loop, so fundamental to programming it’s hard to imagine a single program without one. After all, what’s the use of calculating just one thing? Usually you have a big pile of things you want to calculate, which is why you need a computer in the first place.

I think one of the quickest ways to get a feel for a language is to study its looping constructs. I make no pretense that this is a complete or even an accurate list, but these are some of the general iteration patterns I’ve noticed in different languages.

Counter Variable Loop

for ( int i = 0; i <= 10; ++i ) {
  do stuff with list[i];
}

The old C classic, with deeper roots, I believe, in FORTRAN or PASCAL or both. Successive values of an integer counter are used to retrieve input from an array. Very efficient for small data sets, but requires the entire input to be stored as an array in memory. Also requires the looping code to know about the structure of the input, so not very adaptable. But surprisingly resiliant: Perl and Java support the same syntax.

For-Each Loop

foreach item in list
   do stuff with item
done

Probably the most popular syntactic looping construct, and easy to see why: it’s very easy to read and understand. The for-each loop shows up in Perl, Python, Visual Basic, and a host of other languages. Because it’s usually built in to the language syntax, it can rarely be extended to non-standard container types.

Container Method Loop

list.each do |item|
   do stuff with item
end

In purely object-oriented languages like Smalltalk and Ruby (shown above), looping constructs can be implemented as methods of container classes. This has the great advantages that new looping constructs can be added and standard loops can be implemented for new container types. Since the code “inside” the loop is just an anonymous function that takes a single item as its argument, it doesn’t need to know anything about the structure or type of the container.

List Comprehensions

[ item.do_stuff() for item in list ]

Although Python (syntax above) has gotten a lot of press, both good and bad, for its adoption of list comprehensions, they’ve been around a lot longer. I believe they were originally developed to describe lists in a way that looks more like mathematics. For simple patterns list comprehensions are easy to understand, but I don’t yet grok their full significance. They can be nested and combined to produce complex looping patterns that would be awkward to write with C-style iteration.

Half-Nelson Functional Loop

(map  (lambda (item)  do stuff with item)  list)

(Update 26 July 2006: Replaced the idiotic example (map (lambda (item) (process item)) list) with the above. I’m talking about block structures in code here, using the body of the lambda like the body of a for loop in the other languages. Obviously, if your loop body was just a single function, you would just use (map #'process list). Same changes apply to the next example below.)

Functional languages, including most dialects of Lisp, usually have a map operator that takes a function and a list and applies that function successively to each element of that list. I call this the Half-Nelson Functional Loop because it’s not, to my mind, the ultimate of functional behavior. For that, we turn to…

Full-Nelson Functional Loop

((lift (lambda (item)  do stuff with item))  list)

This looks pretty much like the previous example. But here, instead of map, we have lift, which takes only one argument, a function, and returns a new function that applies that function to every element of a list. That new function is then applied (here, in a Scheme-like syntax) to the list argument. I learned about lift from this blog article.

A desktop that actually behaves like a real desk. I don’t know if I’d want to use it all day, but it sure looks like fun.

As part of my exploration of Ruby, I attended Francis Hwang’s presentation to the New York Linux Users’ Group. One feature that caught my interest in his talk was the OpenStruct class, which lets you assign values to arbitrary “slots” within an object.

require 'ostruct'

me = OpenStruct.new
me.name = "Stuart Sierra"
me.net_worth = -500

Now me.name returns “Stuart Sierra” and me.net_worth returns -500. The clever thing about this is that nowhere did I define name or net_worth as member variables or methods of a class. They just spring into being in the OpenStruct instance as soon as I use them. This is great for developing new data structures before you’re entirely sure what slots you’ll need.

Objects in JavaScript always work this way. JavaScript is prototype-based, so there are no classes, just objects. Each object effectively has its own unique namespace in which you can create new slots simply by using them.

Common Lisp can do this too. Every CL symbol has a property list that can be accessed with get.

CL-USER> (defvar me)
ME
CL-USER> (setf (get 'me 'name) "Stuart Sierra")
"Stuart Sierra"
CL-USER> (get 'me 'name)
"Stuart Sierra"

What I find curious is that this feature of Common Lisp is totally distinct from the object system. Object slots are not symbol properties, just as symbols are not objects (they are bound to objects). But one could make a passable prototype-based object system using just symbol properties and function closures. I think it’s one of those places that shows how Common Lisp grew from many different sources, resulting in similar but distinct ways of doing the same thing. Peter Seibel demonstrates that it can be useful to have both, by using symbol properties to store bookkeeping information needed by macros that generate new classes.

An excellent article introducing the concepts and advantages of functional programming in non-academic language. Now if I could just understand monads…

A popular game on comp.lang.lisp is comparing Lisp with Python. Lispers complain that Python has a crippled lambda and no lexical closures, and they hiss and boo whenever Python’s development tends in a non-functional direction.

I’ve recently been playing with Ruby. Lo and behold, it has real lambdas, closures, and a generally more functional style. The syntax is almost as clean as Python’s, without that significant whitespace that raises so many hackles.

One thing I don’t yet understand about Ruby is the way it treats functional arguments. A function or method in Ruby can have only one functional argument, which must be the last argument. Functional arguments, or “blocks,” as they’re called in Ruby, appear outside the argument list of the function when it is called. So it looks like this for short blocks:

object.method(arg1, arg2) { |var| block code }

Or like this for multi-line blocks:

object.method(arg1, arg2) do |var|
   block code . . .
end

In both examples, |var| is the block’s own argument list, so the Lispy equivalent of the above would be:

(method object arg1 arg2 (lambda (var) . . . ))

The main advantage to this syntax comes with iterators, which I take it were the reason Ruby got blocks in the first place. Ruby’s iterators are just methods of container objects that take a block as their only argument. Then one can omit the parentheses to get something like:

list.each do |item|
   do stuff with item
end

This looks a bit like Smalltalk, one of Ruby’s inspirations. The Smalltalk approach has the advantage that most control constructs are just object methods, so they can be extended and modified as needed. (Unlike Smalltalk, Ruby has a few primitive controls that are not methods, such as if.)

So the special syntax for blocks isn’t strictly necessary, but it does make the most common use for blocks syntactically very simple. In short, a compromise. Ruby also provides the Proc class when general-purpose lambdas are needed.

I won’t advocate Lisp, Ruby, or Python over any other language; each has its place. But Lispers looking for a compromise with Python may want to give Ruby a spin.

It’s great to be here, even if I am a little intimidated by the company. I’ll try to keep my writing interesting.

One big difference between Lisp and most other programming languages is its use of recursion instead of iteration.

So while I was working on some text-parsing code, I fell in to this simple pattern:

(defun process (list)
  (if list
      (cons (do-something (first list))
	    (process (rest list)))))

Ah, the joys of Lisp-2.

If do-something were actually a function, this example would be better written:

(mapcar #'do-something list)

But the CL Hyperspec explicitly states, “For list traversal operations, the cdr chain of the list is not allowed to be destructively modified.” Stepping through the list myself means I can modify its structure along the way. I can insert new CONS cells into the list, or even rebind list to something else. This makes it easy to convert a flat list like this:

• Heading 1
• Paragraph
• Paragraph
• Heading 2
• Paragraph
• Paragraph

Into a structured tree like this:

• Heading 1
  • Paragraph
  • Paragraph
• Heading 2
  • Paragraph
  • Paragraph

Here I encounter the Lisper’s Dilemma: to CONS or not to CONS. Articles and books about Lisp frequently say “CONS is expensive, avoid it where possible.” The pattern above does a lot of CONSing, effectively rebuilding its input. But when I tried to modify my code to use destructive list operations like rplaca and nconc I quickly ran into problems. Destructive operations are tricky at the best of times. Using them while experimenting with new code is just plain asking for trouble. The CONSing code I ended up with was plenty fast enough for my purposes.

I think the constant repetition of “CONS is expensive” is disingenuous for Lisp, especially when it comes to teaching new programmers about its advantages. Yes, CONS is computationally inefficient, but its benefits in readability and maintainability make it is very programmer-efficient.

Or, What I Have In Common With Craig Silverstein.

I’ve been enjoying John Battele’s The Search, a history of the search engine business from Archie to Google. He quotes Google’s first employee, Craig Silverstein, as saying, “I would like to see the search engines become like the computers in Star Trek. You talk to them and they understand what you’re asking.”

This is exactly what I’ve often said I want, except that I would extend the concept beyond search engines to computers in general. This leads me to a Grand Prediction On The Future Of Computing. I call it “Do Engines.” No, seriously, stay with me here. Google has gotten pretty close to the Star Trek computer when it comes to one specific task, namely, searching for information. The Google search box lets you tell the computer “find this” and it gets what you want.

The next stage must be the ability to say “do this” and have the computer know what you want, as in “email my résumé to Craig Silverstein.” Natural-language processing has so far had little success at this. (Battele cites GNP Development, a product that added natural-language spreadsheet formulas to to Lotus 1-2-3, but it didn’t catch on.) I believe that now, with the advent of web-based applications for desktop tasks such as word processing and spreadsheets, the “do engine” can become a reality. Instead of digging through menus and dialog boxes to find a command or setting to achieve the effect you want, you just type in what you want and click “do.”

This can leverage the vastness of the web much like open-source software. If I want to accomplish a specific task with my computer, I might search on Freshmeat, CPAN, or the Common Lisp Directory to find a piece of code that does what I want. If a web-based application has a programmable API with that kind of user community, the same advantages come to everyone who uses them. Therefore, the successful web-based applications will be the ones that make it possible for users to extend them beyond what the original desigers imagined. Google Maps mashups are a perfect example of this, but the trend at the moment seems to be simply porting traditional desktop applications to JavaScript, e.g. Google Spreadsheets. By leveraging the input of millions of users, a web application can “know” how to do common tasks the same way a search engine “knows” how to find things.

Microsoft Office 12 will feature a new interface called the ribbon. I’m not usually a fan of Microsoft interfaces, but this one shows some potential. Office’s hierarchical menus are definitely overloaded, and “Task Panes” are clunky. Moving controls that were formally buried in modal dialogs out into the ribbon should also make working with the interface faster. My only worry here is accessibility: plain menus and dialogs are very easy to access via the keyboard. Looking at screenshots of the ribbon makes me think using it with a keyboard would be awkward.