Two years ago I landed a job at ITA Software, which Paul Graham called one of the “ten or twenty places where hackers most want to work,” along with Google. And one of the interesting things about ITA is that the majority of their software is written in Lisp.
Now before starting there, my experience with Lisp was about the same as most CS grads. I’d used it as an undergrad in a programming languages course, as well as an AI course on natural language processing. And my thoughts about it were pretty standard: it’s a functional language, so if you’re going to use it you’re best off doing recursion and avoiding assignment statements; and dynamic typing and garbage collection make it slow.
Boy, was I wrong. It turns out, Lisp is a lot more practical than that, and we use it for the search engine that powers Orbitz.com, Kayak.com, and most of the U.S. airline websites, among others. The main things I’ve learned are:
- It’s not a functional language, it’s a multi-paradigm language. You don’t need Monads to sequence instructions, and a lot of forms automatically sequence their bodies (“implicit progn”). Our code is mostly imperative, we use lots of state and assignments, and we only use recursion rarely, where it’s clearly better than iteration. G_Morgan put it very well.
- Lisp is the only dynamic language (that I’m aware of) that has optional typing for efficiency. You can tell it the type of any expression, and it will assume the result is that type, thus skipping a potentially expensive check and branch. Sprinkling a few type declarations here and there, along with Lisp’s type inference, can result in compiled code equivalent to optimized C code.
- Lisp’s macros are great. They can do arbitrary computation at compile time. The C++ crowd has rediscovered this with template metaprogramming in the last few years, but the C++ version is awkward. It’s Turing complete, but the syntax is reallyawkward. Not only is it a pure functional language, but it doesn’t even have loops. No loops! Can you imagine programming without a loop? If you’ve done template metaprogramming, you don’t have to imagine, you’ve lived it.
But macros are useful for a lot more. You can use them to bind variables, to provide clean, easy access to values, much in the way that
eachXXXwithXXXclosures are used in Groovy. And they can even be used to develop little languages.
So why hasn’t Lisp caught on more? Well, in a way it has: a lot of the innovation in programming languages has come out of Lisp. Dynamic typing, syntax support for useful data types (only Lists in Lisp), automatic garbage collection, hell, even the if statement appeared in Lisp first, and only made it into other languages once found to be useful. Object Oriented programming is the only major exception that I can think of, mostly because when you have macros, you don’t really need it.
But Lisp’s syntax is a little off-putting. On computers of the ’50s, ’60s, ’70s and ’80s (yes, Lisp has been around that long), Lisp was big and slow. But more importantly, most people’s exposure to Lisp is as an example of a functional language. And functional programming requires you to think like a mathematician, which is unnatural for a lot of people.
I’m waiting for other languages to discover the second and third points above: a dynamic language that cares about efficiency, and a macro capability that’s as powerful as Lisp’s. When I first discovered Groovy, with it’s Java compatibility and optional typing, I thought it was the holy grail of an efficient dynamic language. But sadly it’s creators subscribe to the mainstream view of “dynamically typed languages should be slow, statically typed are fast.” Which is a shame, as it has a lot to recommend it, the syntax and semantics are pretty close to my ideal language. But they seem to have a mental block on annotations or keywords for optional typing or for turning off Groovy’s extreme dynamism when the programmer doesn’t want it anyway.
But Cython looks promising. It has optional typing for efficiency, makes it easy to integrate/recode in C, and there’s currently a lot of debate about compile time transforms and code execution that is a step towards Lisp macros. Let’s hope…
Martin C. Martin 
Its kinda awkward to read that C++ syntax is awkward but later see Lisp syntax is not so awkward, and even later see that you also say Lisp syntax is a little bit strange 🙂
Maybe syntax really matters more than people are willing to admit.
Hmm, I see your point. I’m saying that C++ template syntax is more awkward than Lisp macro syntax, not that C++’s normal syntax is more awkward. But that’s not very clear in the post.
And you’re also right about syntax. I used to think that, when you’ve used a language for a long time, you just get used to the syntax and it becomes second nature. But now I really see how it can make some things more difficult. Anonymous functions in Lisp are actually kind of verbose, at least compared to Ruby and Groovy, and so it’s awkward to use them for really short snippets. Ironic, given that Lisp is where that style took off, but there you go.
And syntax matters even more when people are first learning a language. Lisp’s prefix notation takes some getting used to, at least for arithmetic expressions, since infix has been driven into our heads in all math classes.
“lisp” (which implementation) is around for quite a long time and had time to grow. Efficient implementations didn’t just fall out of the sky. I agree though that it still has several advantages over most other recent dynamic languages. Unfortunately the lisp community seems quite fragmented. Maybe some kind of lisp-forge would help. (And a good free win32 implementation.)
I’m not sure what you are trying to say about OOP. Lisp has CLOS, which supports multiple inheritance / multiple dispatch. It’s a more powerful mechanism than what C++ has and just as efficient. I kind of like the message passing paradigm, but then that would slow things down, and I can code this if I really wanted it anyway, so CLOS is good enough.
A few other advantages:
Lisp also supports reflection (MOP), which some people find quite attractive.
Lisp allows you to recompile a single function and re-run your code immediately. You no longer have to recompile your entire program after making a small change!
BigNumbers for free. Great if you’re a scientist, mathematician, economist, etc.
And Lisp is now as fast as C++/STL, which I find amazing.
Nice post.
All I’m saying about OOP is that it wasn’t invented in Lisp. Simula and Smalltalk had it before Lisp does. You’re right that Common Lisp has it, and a good implementation at that. It’s just that Lisp got it from other languages, not the other way around.
tom: “a good free win32 implementation.”
Ever tried Clisp?
martin: And one guess as to which language Smalltalk was initially implemented in.
But I see your point.
Nice post – it’s always good to have someone with recent “real-world” experience in Lisp share his story.
Just one nitpick – your comment about “Can you imagine programming without a loop?” APL-ers (and descendent languages like A+, J, K/Q) might have a bone to pick with this statement. They do everything possible (and quite successfully) to eliminate explicit loops.
There’s even a website http://www.nsl.com where nsl stands for “No Stinking Loops”… 😉
You really need to check out Clojure, which is a Lispy language with a REPL that compiles (using a compiling reader) to JVM bytecode, and is thus *extremely* fast, yet still has macros, dynamic typing.
Rich Hickey has built a ton of cool things in there, including STM and concurrency, agent/actor support, and he is responsive to requests.
There’s really too much to mention, but being cross platform across all three main platforms with strong Java interop is fantastic.
“Object Oriented programming is the only major exception that I can think of, mostly because when you have macros, you don’t really need it.”
I would love to read an article with examples of the same code written with OOP or macros to show how macros can do what OOP can do.
I am always fascinated by how a relatively smart programmer/analyst can produce a stream of thought about his or her ideal language. I started programming when I was 11, and didn’t stop caring about syntax until I was 21. I’m turning 24 in a couple of months.
My opinion on Groovy has always been that it provides effective scaffolding for most scripting tasks. One “feature” you missed was the built-in support for the GoF Builder pattern.
As for trying to match (Common) Lisp’s macro system: Have you read Walid Taha’s Ph.D. dissertation on multi-stage programming, his “gentle introduction” paper on the topic, or used MetaOCaml?
C++’s template metaprogramming suffers from a harsh drawback: lack of debugging tools. Taha uses the notion of gradual typing to describe how to achieve robust support for writing correct code, like device drivers. The other practical disadvantage is that a lot of that C++ code is written and packaged as a third party library, and cannot be used in a project without a project manager’s approval (particularly on government contracts).
All of this is really politics, though. I guess that is why it amuses me so much when a programmer/analyst steps up with yet another opinion on this debate topic; a fair number of programmers are politically naive and far more attracted to technical details.
Ted, check out Paul Graham’s books ANSI Common LISP (a beginner book) and On LISP, for an advanced treatment of macros. You can also download On Lisp for free.
vanekl, I didn’t know Smalltalk was originally implemented in Lisp. Thanks!
And evorationalist, I hadn’t seen nsl.com, that’s fun. 🙂
Jonathan, I haven’t checked out Clojure, I really should give it a try.
Martin,
Telling someone to check out a book to get an answer to a simple question only sends one message: “It’s complicated.”
However, it is not complicated.
Ted:
Object-oriented programming is really just a way of thinking. Over the years, mainstream thought has developed various principles to identify what OOP is. As an example, many programmers were taught that encapsulation is fundamental to OOP, and therefore believe that a foundation of OOP is the Abstract Data Type. However, the big question really is, “What is it you are encapsulating?” Furthermore, “Why are you encapsulating it?” The latter question reveals a lot: The reason you encapsulate is to provide data independence.
If you encapsulate to provide data independence, then encapsulation might not actually be fundamental, but instead just a mechanism for controlling visibility of state. How you see that state is what data independence is; there can be multiple representations of one state. For instance, state adjusted by units of measurement. Thus, if you want to ensure a correct units calculation, what matters to you is data independence and knowledge of what multiple representations of the data should look like, not encapsulation.
I forgot to say that comparing macros to OOP is somewhat silly, and explain why.
Macros are just a way to expand an expression. There are other “patterns” for expression expansion, and, more generally, expression transformation. For instance, a GoF Adapter pattern is really just a way to treat a data type as an expression and transform it by augmenting the visibility of state by redefining an interface. This is typically a very naive transformation, where nothing really changes except that you can now have two components speak the same interface language.
John,
That dissertation sounds very interesting, I’ll have to pick it up, and play with MetaOCaml. Thanks for the tips.
Martin,
You may have heard Alan Kay’s definition of OOP, where he says that “extreme late-binding of all things” is essential. All multi-stage programming does is reject that and instead say, “Bind only as late as necessary, and no later.” This lets you blur the notions of compile-time and run-time and simply say declaratively when things are binded.
John,
I know you didn’t say it but I’m left thinking “what does ‘extreme late-binding’ have to do with OOP?”
Martin,
I was hoping to get your take on how macros and OOP somehow cover the same need.
Ted,
The main point is that, for any OOP feature you want to try, you can implement it yourself using macros. For example, suppose you’re using Lisp before CLOS existed, and you’re reading about this C++ thing called virtual functions, and want to give it a try. Basically, virtual functions are syntactic sugar for a function pointer.
So you create a macro called something like deftedclass, which has the same syntax as a defstruct, except you have some way to indicate a virtual function. Your deftedclass macro turns most of its argument into the equivalent defstruct, with an extra field called “virtual-function-table.” It also strips out all the virtual function indications, and when creating the accessors for the virtual functions, instead of the normal dispatch, indexes into the virtual function table.
That’s more or less how C++ virtual functions work. The point is, with macros, you can define your own syntactic sugar. When doing OO programming in C, the programmers need to have a discipline about e.g. always going through a virtual function table to dispatch whatever they want to treat as virtual functions, and the compiler can’t warn them when they mess up. In Lisp, you implement the syntax and the sugar as well.
You wrote: “Lisp is the only dynamic language (that I’m aware of) that has optional typing for efficiency.”
ActionScript, the language of Adobe Flash, also has this. From “Programming AS3” (http://www.adobe.com/go/programmingAS3_pdf): “In ActionScript 3.0, type information is preserved at run time, and used for a number of purposes. Flash Player 9 performs run-time type checking, improving the system’s type safety. Type information is also used to represent variables in native machine representations, improving performance and reducing memory usage.”
Extreme late binding is an artifact from the idea that objects send messages in order to communicate with other objects. An individual object is very much like an individual program with a Single Responsibility. Sending these messages is called method dispatch or message dispatch.
Refactoring a run-time if statement into a run-time polymorphic function call takes advantage of *dynamic* message dispatch. What message is sent and who is sending it should only be determined when there is enough information to know exactly what the message should say. In other words, the correct information should be binded into some message “template” as late as possible. The notion of template here is important: In other words, you need a well-specified interface. “Extreme late binding” is really just a confusing way to say objects should be able to send well-formed and valid messages to each other, regardless of whether the receiving party understands the content of the message.
In languages like C, there are preprocessor macros like #ifdef and #if and so forth. These are compile-time if statements. A fully-featured multi-stage programming language would allow you to refactor these if statements into compile-time polymorphic function calls. Most people talk about refactoring to improve the readability of code, but it can also help simplify the specification of invariants by defining a polymorphic function call in place of cascading if statements.
Similarly, all a switch statement really provides is a map construct that filters input based on keywords, and “selects” the most appropriate action to take. Such a Selection pattern can be done at compile-time, so why not be allowed to do it at that time? Going back to the idea that extreme late binding is a confusing way to say: A “default” case statement in a switch clause could very well indicate that the receiving party does not know what to do based on the input information. It’s *almost* generic way to say, “I don’t want to touch this message.”
Finally, in Lisp, the most important thing to understand with regard to macros is where they fit in the REPL (Read-Eval-Print Loop), because REPL is how Lisp blurs compile-time and run-time stages.
Liked your post. I think you put your finger on something I’ve “felt” about Lisp for a while, that it’s a multi-paradigm language. I’ve thought of it more broadly as a symbolic computing system. It represents a different computing model from the traditional 3-address code “op-code operand operand” way of doing it that we’re used to, from working with a CPU. It’s basically a different kind of computer in software. It’s a model that works with symbols, not bits, bytes, and words (though I’m sure you can work with that stuff in Lisp).
Something I’ve felt bad about is that universities have insisted that Lisp is an AI language, and indeed it was classified that way very early on. It deserves to be thought of as a general-purpose language, one that can be used for all sorts of things.
To answer something Martin said, no Smalltalk was not first implemented in Lisp. Believe it or not, the first implementation, Smalltalk-72, was written in Basic by Dan Ingalls! Alan Kay wrote the definitive history of it in The Early History of Smalltalk. I haven’t gotten all the way through it, but I have heard him say that they bootstrapped each subsequent version of Smalltalk, all the way through ST-80, from each previous version of Smalltalk, though I’m pretty sure the object language for the subsequent versions was something else (not Basic).
Meant to add:
When I was taught Lisp in college it was taught in the functional style. We were not allowed to use any of the “set” operators (setq, etc), nor any function/macro that used it (I think). This made things odd, because just about any time you wanted to implement a loop, you had to write two functions: an initializer function that would get the loop going, and then another one that had the general case, which you would call recursively. The one thing I couldn’t get through my head was how in functional programming every variable was like a const variable. I wondered how the heck you’d ever write a coherent program that way. Anyway, I eventually figured it out.
Alan Kay, the designer of Smalltalk, was an admirer of Lisp. Next to Simula and Logo, it was one of the first languages he worked with, besides some of his own he designed. He’s been quoted as saying, “It’s the most beautiful language I’ve seen”, or something like that.
I personally like Smalltalk and Lisp, both. 🙂
Interesting notes but not new.
You’re working in a lisp sphere, you’re using lisp as your main language at work. So I’d like to ask you(professional lisper) why is lisp so unpopular? I mean the main reasons.
For all time I’ve been working in IT sphere I’ve never seen any vacancies for lispers or any company using languages from lisp family in my country.
p/s: yes, I’ve already read what Paul Graham wrote about it, but I want to know other’s opinions.
thanks.
Dan,
I came across this site the other day:
http://lispjobs.wordpress.com/
I don’t know what country you’re from, but you might find something there.
I’m not quite sure why Lisp is so unpopular, you’d have to ask a non-Lisp user why they don’t use it. But my guess is that, thanks to it’s use in programming language courses, its probably seen as a functional language; plus, people can be put off by the syntax when they first use it; plus, I got a reputation for being slow back when it was slow. Java has done a lot to dispel some myths, e.g. that garbage collection is necessarily slow.
But I’ll bet the main reason is just that it “feels” so different from existing popular languages. If people can’t be productive within an afternoon, they tend to drop any new technology. I suspect those are the people you hear complaining about “all those parentheses.”
But that’s just speculation, based on why I didn’t use it for the longest time.
See, this is why you don’t ask a programmer a political question like, “Why is lisp so unpopular?” The politics really don’t matter at all to people who use and enjoy a language.
Martin, a simple catch phrase that side steps this question is: “Well, I can only tell you what’s technologically possible. I know nothing of costs and politics…” You are simultaneously telling people how they can solve a problem while letting them know the grim reality that political games can prevent something from entering an enterprise.
Pingback: Sp3w » Blog Archive » Linkage 2007.02.15
Visual Basic, VBA, and VB.NET also all have optional typing for efficiency.
In VB.NET, for example, you can program entirely statically, or go loose and provide as much typing as you fancy. It will early-bind whenever it can.
It’s controlled by the ‘option explicit’ command, if you fancy googling for it.
John,
Ease up a little on the condescension, eh? It’s possible to contribute your thoughts to a conversation without implying (or saying directly) that the other participants are amusingly foolish and naive. Not that anyone was complaining, but it’s off-putting to read.
Why is Lisp not popular?
Emacs. Anybody can learn Lisp. It’s not that difficult. But only the hardened few can climb the emacs learning curve that makes Lisp’s simple syntax transparent.
Yes, there are alternatives. None of them are as widely used as emacs. Emacs is the best, but it’s a huge hurdle for a Lisp learner.
As to why Lisp is unpopular, I think it has a lot to do with “feel”. I think people new to programming like the popular languages, because when they’re first introduced to them they look more like English. It just makes sense to them. There also is a popular paradigm that’s taught, that the way to program is in the imperative style: tell the computer what to do. Give commands. Work linearly, like in a flowchart. Lisp works on a completely different mental model. It feels more like math, something most people hate.
I think it’s further hindered by the fact that for decades Lisp was deliberately kept in a corner, in the AI camp, along with Prolog. Universities encouraged the notion that if you’re not into AI, “don’t bother learning this.” You know, “What you want to learn is Fortran, C, C++, etc.” They’d steer you in that direction. Once the “AI Winter” came along in the late 1980s, Lisp went down with it. Paul Graham used that to his advantage, recognizing what most people didn’t know, that you really can do anything with it, not just AI stuff. Once he made his money, he let the secret out. Since then he’s been one of only a couple noticeable champions for the language. I’d include Peter Seibel in there, too. I was very impressed with PG’s “Beating the Averages” essay. It really changed my view of Lisp.
Sorry. I did not mean to be a jerk, but accept full responsibility for my words. If I came across poorly, then history will remember it forever. Nothing escapes the Internet.
Pingback: Martin C. Martin » Where are the fast dynamic languages?
Thanks for a great rread