2013-01-10

Common Lisp is just Lisp

There's this perpetual confusion about Lisp: everyone will call a language with prefix notation and parenthesis a Lisp or a Lisp-dialect. This is one of the popular urban legends about Lisp, which I'd like to dissolve.

So, let's look at the language familiar to most of the programmers: C. Would anyone call C++ a C? Maybe, but only someone very inexperienced in these languages. On the contrary, many of the experienced people will often say: I would only program in C, but not in C++, because it's such a mess. For instance. Let's go further: would anyone call Java a C? I very much doubt it. What unites those languages is a common syntax: braces, basic keywords and operators, and more. A common root. And although the gap between C and Java is pretty big, it can be said, that they also have a somewhat similar semantics. And they are often used in similar scenarios. That's why all these languages are attributed to the C family. As well as Objective-C. Indeed, it would be much easier for a C programmer to switch to C++ or Java, that to, say, Lua or Haskell.

Now, the difference between 3 popular Lisp-family languages: Common Lisp, Scheme and Clojure — is just as big, as between C, C++ and Java. Conceptually and syntactically, Common Lisp is as far (or even further) from Clojure as C is from Java.

The language is not just superficial syntax — it's about syntax, semantics and pragmatics. And about community. The Lisp community has split at several points in time, and the main sprouts were Scheme and Clojure. It's not a coincidence, that these languages don't have Lisp in their name. And, what's most important is that each language's community cares about different things.

So, when someone asks you again "Which Lisp?", the answer is very simple: for good or for worse, the only Lisp currently is Common Lisp. It's like, say, the C99 standard of C. There were other standards and variants, like ZetaLisp or ISLISP, but they aren't in use now. Every other Lisp-like language isn't a Lisp, it's just similar to some extent.

submit

2013-01-03

Lisp Hackers: John Fremlin

John Fremlin has created a couple of very performant Common Lisp programs beating on some microbenchmarks the fastest similar software written in any other language, including C: the teepeedee2 dynamic webserver, that managed to break the c10k record on a single core machine, and cl-irregex regex library. Working at MSI in Japan he also had written an object persistence DB for CL manardb. Besides, he writes interesting blogs on topics of software optimization, programming languages and technology in general.
Tell us something interesting about yourself.

I've been to more than eighty countries; I want to go everywhere!

What's your job? Tell us about your company.

I work at Facebook on the growth team, on data-driven improvements to the sign-up flows.

Do you use Lisp at work? If yes, how you've made it happen? If not, why?

I used to at msi.co.jp. It is a Japanese consultancy based in Tokyo called originally Mathematical Systems Institute. Mr Kuroda leads the Lisp group there and I think it has hovered around five or six people over many years. He's done a great many very interesting projects for a range of companies over the years: for example a crash-test data inspection tool for a big Japanese car company, text mining, graph visualisation and so on. I worked primarily on building up a visualisation and mapping of a very large set of routers for the world's biggest telecoms, which led to the creation of manardb.

I really enjoyed working for Mr Kuroda and I'm sorry I had to leave for personal reasons. There were always many very fascinating problems around — with great people to discuss them and find solutions. It was a very stimulating workplace!
At Facebook, I use PHP, Python, C++, Java and miscellaneous things. I think we would all be better off if we hadn't balkanised the different systems that we program for — and Lisp is one of the few programming languages with the flexibility to serve in all these roles.

What brought you to Lisp? What holds you?

My initial programming was following Michael Abrash's graphics books and building on his ideas, by doing things like runtime native code generation for drawing dynamically generated bitmaps efficiently. This is not so interesting for modern processors as they have good branch prediction but the idea of code generation stuck with me and Lisp is one of the few programing languages that makes this easy and efficient.

I appreciate the intellectual coherence of Lisp, and its sensible approach to numeric computations. In terms of using it today, I feel that Common Lisp has an advantage over many other programming languages in that it has multiple mature independent implementations. Running on multiple compilers tends to greatly increase the quality of a program in my opinion, as the code is exposed to different static analyses.

What's the most exciting use of Lisp you had?

I helped someone use Lisp for an automated trading project.

What you dislike the most about Lisp?

In trying to make efficient code one ends up fighting against the compiler and the runtime system and most of the time is spent in coming up with clever ways to circumvent and outwit both. This is not a good use of resources, and means that it usually makes more sense to start with C++.

Tell us about your approach(es) to optimizing Common Lisp code (and maybe code optimization in general)?

The most important thing is to try to hold in your head an understanding of where the program is going to spend time. Profilers can be misleading and inaccurate, and it is sometimes difficult to get representative workloads to profile. I think their main utility is in confirming that there is no sloppy mistake (in Lisp, typically, consing accidentally) that prevents you from achieving the natural performance of your approach.

Complexity analysis in terms of computation, network usage, disk accesses and memory accesses is a first step as obviously if you can improve the asymptotic usage of a bottlenecked resource, you will very likely do much better than trying to tweak some little detail. The second step is to try to characterize interactions with caches and, in Lisp, garbage collection, which is pretty tricky.

Among the software projects you've participated in what's your favorite?

I think the one I enjoyed most was an embedded H.264 decoder in 2005. This was for the VideoCore, a really wonderful CPU architecture that could deal with parallelizable problems incredibly efficiently if programmed correctly. It would have been awesome to use Lisp for it!

If you had all the time in the world for a Lisp project, what would it be?

I wish there were Lisp bridges to other runtime systems (Java, Android, Objective C, Perl, Python, C++, R, etc.) so that the libraries and tools for each could be leveraged efficiently in Lisp and vice versa. That would mean being able to call Java code and handle Java objects in Lisp, for example -- perhaps initially by spinning up a Java implementation in a separate process running a CL-SWANK style interface.

I really don't think this would be that difficult and it would make a huge difference to the convenience of building programs in Common Lisp!

Describe your workflow, give some productivity tips to fellow programmers.

I use emacs and I have a bunch of elisp code that I keep meaning to publish!
submit

2013-01-02

"Real" List Comprehensions in 24 Lines of Lisp

I've just come across a post on Hackernews titled List Comprehensions in Eight Lines of Clojure. It's definitely a nice little example. But it also feels kind of unreal, even cheating ;) Because who would really use such kinds of list comprehensions? It seems to me, that the whole purpose of this construct is to make the code be concise and resemble a set-theoretic notation for sets. But here we need to use them inside a list-comp macro. This actually looks more like just another iteration construct.

What you really want from a list comprehension syntax is for it to be able to "comprehend" something like this:

{x|x ∊ some set}
or like this:
{x|x ∊ some set|x < 10}
Just like math.

But, surely, it's impossible to implement such syntax in Clojure or any other language without an extensible reader. The only route you can go is what Python does — to implement it as part of the language itself.

But you can do more, if you have control of the reader. This is one of the many cases, when Lisp's reader macros prove indispensable.

So here's an implementation of "real" (i.e. really resembling mathematical notation, no cheating) list comprehensions in 24 lines of Lisp (if you don't count a utility function group):

Unfortunetely, I had to use || instead of |, because on its own the | is used to escape charfactes in symbols, and also <- instead of for ease of typing, obviously. And as for the filter part, there's an implicit and, so you can write several conditions, and they should all hold. Otherwise, I think, this can be considered a literal implementation of the idea.

PS. And using named-readtables instead of plain set-macro-character this syntax can be used on a per-file basis, just like in-package forms.

PPS. I won't discuss here the issues of list vs. sets or lists vs. sequences. They are an implementation detail, worth another post.

submit