29

In A Critique of Common Lisp written by Rodney A. Brooks and Richard P. Gabriel from Stanford in 1984, some design decisions retained by the normalizing committee of Common Lisp are discussed. While most of the discussion remains valid, there are two statements that refer to the technology available at the time and may be false today.

These two statements are:

Too many costs of the language were dismissed with the admonition that ‘any good compiler’ can take care of them. No one has yet written—nor is likely to without tremendous effort—a compiler that does a fraction of the tricks expected of it.

As I am a Common Lisp novice, or even an apprentice, I am not able to be more specific than the authors are. They seem to state that a great generality and flexibility has been built into several aspects of the language, which makes writing a good compiler quite difficult.

In COMMON LISP a little too much control was placed on floating-point arithmetic. And certainly, although the correct behavior of a floating-point-intensive program can be attained, the performance may vary wildly.

As far I understand, it seems that writing efficient numerical code in Common Lisp is possible but more challenging than it has to be.

This was thirty years ago. How should I regard these statement today if I am willing to write Common Lisp programs for one of the common free software implementations (CLISP, SBCL et al.)?

  • Great question! Would love to hear from somebody knowledgeable about Common Lisp on this topic. My fear is that they do still apply, based on the apparent relative popularity of Common Lisp nowadays. – user39685 Nov 27 '13 at 13:49
  • 1
    Floating-point is hard to get right. Some languages specify a strict model and suffer performance wise, others use a loose model and are hard to reason about. For example reasoning about even simple floating point programs in C# is too hard for me. So I tend to side with language designers who are strict with floating point, even if it costs performance. – CodesInChaos Nov 27 '13 at 15:44
  • 2
    On the other hand, modern hardware generally implements IEEE floating point, so it's probably far more predictable in its behavior than the implementations available in 1984. – microtherion Dec 4 '13 at 21:34
31
+100

The paper is interesting in many ways.

The most interesting part is this: the authors falsified the paper from 1984 just two years later in 1986 themselves. Brooks and Gabriel developed a highly optimizing Lisp compiler and sold it commercially very successful for several years: Lucid Common Lisp (PDF).

Maintenance for this Lisp compiler is still available from LispWorks: it is now called Liquid Common Lisp.

The compiler optimizations of Liquid CL are documented in Chapter 3 of the Advanced User's Guide: Optimizing Lisp Programs.

Several commercial applications have been written and deployed in Lucid CL. For example in my home town the first public transport information system for the HVV (Hamburger Verkehrsverbund) was deployed using Lucid CL on a SUN SPARCstation. It was available for the public in train stations using a large touch screen and in the call center.

Lucid CL was successful because its production mode compiler created fast Common Lisp applications, mainly for Unix / RISC platforms.

Brooks and Gabriel are writing about Lucid Common Lisp in 1986:

The dynamically retargetable compiler has been shown to be a means by which ease of compilation for a variety of Lisp implementations can be performed; a means of porting Lisp systems to a variety of computers; and a tool for producing high-quality, high-performance code for a variety of computers from a common source.

Thus they had just implemented what the A Critique of Common Lisp claimed to be difficult or impossible.

Nowadays the more advanced implementations are doing a lot of optimizations, but the hardware is also 1000+ times faster than what we had in 1984. A VAX 11/780 then had one MIPS (million instructions per second) and a Lisp Machine was also in that range. A Motorola 68000 had a clock rate of 8 MHz.

The criticism about floating point performance and generally varying performance is still valid, but this reflects implementors choice. Some implementations are not developed as high-performance compilers. Their main focus could be portability, compactness or something else and thus they have different implementation goals.

As a user/developer one is not forced to write portable code and use all of the ten+ currently supported Common Lisp systems. Use the implementation which is best suited to the application problem.

  • Your answer is very precise and detailed, it definitely deserves the bounty! – user40989 Dec 12 '13 at 9:22
  • 1
    "Highly optimised" doesn't necessarily mean the compiler is "sufficiently clever". The words "sufficiently clever" raise the question "for what purpose?". There are still applications (mainly for very limited embedded platforms) that you wouldn't write in Common Lisp because the optimization still cannot eliminate all the run-time overheads from dynamic typing, heap allocation and garbage collection. Of course Common Lisp is in no way unique in that "failing". No language has been observed in the wild yet that is genuinely suited to absolutely everything. – Steve314 Dec 12 '13 at 9:56
  • @Steve314: Lucid CL targets were the market for large Lisp-based AI systems, CAD systems, etc. on Unix workstations and servers. Lucid CL target was not embedded systems. Lucid CL addresses run-time overhead of dynamic typing, heap allocation and many other optimization areas - including a performant garbage collector. Still, GC is mostly needed. Typically application use special techniques to avoid consing and thus to reduce the GC rate, like 'resource' pools. – Rainer Joswig Dec 12 '13 at 11:03
21

When this paper was written in 1984, a computer having 1 megabyte of RAM and a 20 megabyte hard drive, capable of sitting on your desk, was a big deal. Naturally, disputes will arise over the practicality of a language as high-level as Lisp is on hardware that spartan. The advances in both hardware and compiler technology that have taken place since then have made Lisp programs much easier to write and execute, regardless of any numerical inefficiencies that might be present in the language.

Programmers often trade computational efficiency for programming efficiency. Lisp can be a slow language (in some implementations, but so can other languages), but it also has a well-deserved reputation for rapid development, and many programs do not require a highly-optimized infrastructure to exhibit adequate performance.

The choice of Lisp implementation can greatly affect the performance profile of your programs. For example, CLISP readily admits that "If your code is heavily numeric, you might prefer CMUCL." Several modern Lisp (and Scheme) implementations allow you to specify numeric type hints, which will increase numerical performance.

In short, the situation is much better today than it was then.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.