A Usenet posting sent me to a short article by Edsger W. Dijkstra titled Why numbering should start at zero.

Now, I have never used a programming language that wasn’t zero-indexed (like Fortran), but neither have I adopted the habit of numbering lists starting with zero.

I think the difficulty I have with zero-indexing is that in normal English we refer to items in a list by ordinals: “first, second, third, … nth.” But translated into Common Lisp, we get the slightly disorienting:

(first *list*) ≠ (nth 1 *list*)

(that’s a not-equals sign for the Unicode-deprived)

Now, I understand that nth is zero-indexed, just like elt, and that’s consistent with how most other programming languages work. But then why don’t we have zeroth?

I guess the simple answer is that zeroth isn’t normally thought of as a real word, except occasionally to refer to something added to a sequence “before the first.” My Websters Collegiate doesn’t even define it. Of course, the copy I have is from 1973; Webster’s online does include zeroth. Has zeroth entered the English language because of computers?

So I have been dropped from Planet Lisp, scarcely two months after being added. I wonder if that’s a record of some kind? Apparently, the maintainer found my tone too didactic and my knowledge too lacking. Fair criticisms both, but I meant no harm. I’m certainly not trying to set myself up as a Lisp guru. I’m just trying to learn things, and one of the ways I do that is by writing out explanations as if I’m teaching myself. Publishing them on the web is the fastest way to find out where I’ve made mistakes.

I only started this blog a few months ago, so I’m still exploring the form and what I want to do with it. I won’t let the infamous Common Lisp “community” scare me way just yet. I’ll continue writing, I hope others will continue reading.

Hello, Lisp world! This is my first released Common Lisp code. Perl in Lisp is a Common Lisp interface to the Perl 5 API. It allows you to run a Perl interpreter embedded inside Lisp and evaluate Perl code. It does not require any C wrapper code — the API definitions are done with CFFI and the rest is pure ANSI Common Lisp.

In response to the obvious question, “Why on Earth would you want to do such a thing?” my best answer is “Why not?” I thought it would be fun. It ended up being more difficult than I expected — the Perl API is not for the faint of heart, nor for those unwilling to dig through source code. But it does work.

This was also an experiment to see if I could follow two “best practices” of software development — literate programming and unit testing — at the same time. It wasn’t always easy, and it tripled the amount of work I had to do, but the end result was definitely worth it. Thanks to the literate source, I understand what all of the code does. Thanks to the unit tests, I know that it works.

This is a beta release. It can evaluate strings of Perl code, call Perl functions, and convert between Lisp and Perl types. Callbacks from Perl to Lisp are not yet supported. Some Perl modules may not work, particularly if they depend on external C libraries.

See the project page for implementation compatibility notes, download links, and documentation.

Potentially, it could be very useful. CPAN has over ten thousand modules for doing all sorts of obscure things. Say you want to output an Excel spreadsheet from your CL application. Just use Spreadsheet::WriteExcel.

Jeremy Smith started a similar project for embedding Python: PythOnLisp.

Or, How the Lisp-n Shall Inherit the Earth

Humans like to name things. Like ourselves, Homo sapiens, Latin for “Primate that has taken leave of its senses.”

Then there are engineers. Engineers like to name things too. Like SCSI, pronounced “scuzzy.” Or WYSIWYG, pronounced “wizzy-wig.” Or TTY, pronounced (I couldn’t believe this at first) “titty.”

Then there are programmers, who are singularly uncreative when it comes to naming things. With Apache’s Gregor Samsa class as a brilliant exception, programmers tend to give their variables and functions dull, predictable names like string, number, or do_not_use_this_variable_ever.

Of course, in most programming languages a given name can refer to one thing and one thing only for ever and ever until your program crashes and dumps core Amen. To get around this sad limitation, programming boldly took advantage of the eighth-century’s greatest typographical innovation, lower case letters. Thus we have the Dada-esque beauty of case-sensitive code:

Widget* WIDGET = new Widget.widget();

As languages got more complex, adding first-class functions and first-class types, there were more and more things that needed to be called by the same name. Few programming languages picked up the idea of meaning based on context. So hierarchical namespaces were born:

java.awt.event.ActionEvent myEvent = new java.awt.event.ActionEvent();

My tendinitis starts acting up at the mere sight of that.

Common Lisp to the rescue! As many have pointed out, CL is not just a Lisp-2 (functions and variables in separate namespaces), but more of a Lisp-n. It has many overlapping namespaces — functions, variables, type specifiers, block names, tagbody tags. With a few macros and a hash table, one can easily add a new namespace to the language. For example, testing frameworks like FiveAM and LispUnit put test names in a separate namespace. A programmer using these libraries doesn’t have to think about the extra namespace. Just type symbols and Lisp will do the right thing.

I like to think of this approach as parallel namespaces. Everything is kept neatly separated, without endless qualifiers attached to every symbol. Macros determine how symbols will be evaluated — or not — in a block of code.

This isn’t perfect. For one thing, there’s no canonical way to add a new namespace to a language. Some macros require names to be quoted symbols, some not. Some use keywords. Sometimes an unquoted symbol will pollute the namespace of the current package; sometimes it won’t.

The solution, to my mind, would be something that lets us do this:


(define-namespace foo)
(defmacro-with-namespaces my-macro ((arg1 foo))
. . . )


Then my-macro would always treat its first argument as a symbol which is not evaluated, internally binding arg1 to whatever value the given symbol holds in the foo namespace. I’m not going to attempt to implement such a beast just now, but I’m sure an experienced macro-writer (i.e. someone else) could dash it off in half an hour.

Perl was the first programming language I really liked, the first language that made programming fun.

Perl has three basic types: “scalars” for atomic values, arrays for ordered sets, and hash tables for unordered sets. (Yes, there are others, but those are the popular ones.) I quickly discovered that these three types can be combined to produce most any data structure you might need. Need an ordered list of records? Use an array of hashes. Need a tree of named elements with attributes (e.g. XML)? Use nested arrays with hashes in them.

These basic types can also be conveniently mapped to external data. A CSV file can be represented as an array of hashes. A database table can be an array of arrays, an array of hashes, or a hash of hashes, whichever you prefer.

Python and Ruby both followed in Perl’s footsteps here. (Python calls them “lists” and “dictionaries.”) Lisp, predating all these new-fangled “scripting” languages, includes lists, arrays, hash tables, plus a whole raft of other built-in types. This is one of those areas that makes Common Lisp difficult for the beginner to grasp. When should you use a plist, an alist, or a hash table? When should you use arrays and when should you use lists? The answers to these questions delve into details of how the various structures are implemented. The only obvious criteria for choice is speed at handling a given data set, something a beginning programmer doesn’t want to worry about when designing a new piece of code.

At least one hacker has implemented generic get/set functions for all of Common Lisp’s data types, but to my knowledge no one has implemented abstract ordered/unordered set types that don’t care about their implementation. CL-Containers is a good foundation, but it further complicates the issue by adding a bunch of new data types.

What I want is a general-purpose “collection” class, of which instances can be declared ordered or unordered, numerically-indexed or key-indexed. Something like this:

(define-collection my-set
  :ordered t
  :index string)

Then, based on the data that I feed in to that class and the operations I perform on it, the compiler decides what sort of data structure to use for maximum efficiency. Or, if that’s too much magic to ask, at least let me change the underlying implementation without affecting any of the code that uses the collection:

(implement-collection my-set
  (array :resizable
         :elements (cons string object)))

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.

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.

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.