I think that it’s extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free prefect use of these machines. I don’t think we are. I think we’re responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don’t become missionaries. Don’t feel as if you’re Bible salesman. The world has too many of those already. What you know about computing other people will learn. Don’t feel as if the key to successful computing is only in your hands. What’s in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.
– Alan J. Perlis (The first recipient of the Turing Award)
Those who read my previous scholarly article on Lisp would experience resonance of familiarity with Alan J. Perlis’s words above. Lisp, after all is all about having fun and stretching the capabilities of the computer and the programming language itself. One of the ways Lisp does that is because it is designed to be extensible. Read on for more.
There was a joke back in the 80s when Reagan’s SDI (Strategic Defense Initiative) program was in full swing that someone stole the Lisp source code to the missile interceptor program and to prove it he showed the last page of code…
No, LISP does not stand for Lots of Irritating Superfluous Parentheses.
Lisp, whose name is an acronym for LISt Processing, was designed to provide symbol-manipulating capabilities for attacking programming problems such as symbolic differentiation and integration of algebraic expression. Despite its inception as a mathematical formalism, Lisp is a practical programming language. The basic elements of Lisp includes it’s primary data structure, called the s-expression. They also include the Lisp interpreter, which is the heart of any Lisp system and is basically a machine that carries out processes described in the Lisp language. The Lisp interpreter performs computations on s-expressions through a process called evaluation. Since its earliest days, Lisp implementations have been variously interpreted or compiled, and often both. No modern commercial Lisp is without a compiler. The fact that modern Lisps often come with an interpreter as well is simply a convenience for some implementations to encourage late-binding semantics and promote flexibility, including interactive debugging.
Guy L. Steele Jr. and Richard P. Gabriel in their paper ‘The Evolution of Lisp’¹ say that the origin of Lisp was guided more by institutional rivalry, one-upsmanship, and the glee born of technical cleverness that is characteristic of the “hacker culture” than by sober assessments of technical requirements.
How did it all start? Early thoughts about a language that eventually became Lisp started in 1956 when John McCarthy attended the Dartmouth Summer Research Project on Artificial Intelligence. Actual implementation began in the fall of 1958. These are excerpts from the essay ‘Revenge of the Nerds’² by Paul Graham:
Lisp was not really designed to be a programming language, at least not in the sense we mean today. What we mean by a programming language is something we use to tell a computer what to do. McCarthy did eventually intend to develop a programming language in this sense, but the Lisp that we actually ended up with was based on something separate that he did as a theoretical exercise– an effort to define a more convenient alternative to the Turing Machine. As McCarthy said later, “Another way to show that Lisp was neater than Turing machines was to write a universal Lisp function and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the Lisp function
eval…, which computes the value of a Lisp expression…. Writing
eval required inventing a notation representing Lisp functions as Lisp data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express Lisp programs in practice.”
What happened next was that, some time in late 1958, Steve Russell, one of McCarthy’s grad students, looked at this definition of
eval and realized that if he translated it into machine language, the result would be a Lisp interpreter.
This was a big surprise at the time. Here is what McCarthy said about it later in an interview:
“Steve Russell said, look, why don’t I program this eval…, and I said to him, ho, ho, you’re confusing theory with practice, this
eval is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the
eval in my paper into [IBM] 704 machine code, fixing bugs, and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today….”
Suddenly, in a matter of weeks I think, McCarthy found his theoretical exercise transformed into an actual programming language – and a more powerful one than he had intended.
Lisp is designed to be extensible: it lets you define new operators yourself. This is possible because the Lisp language is made out of the same functions and macros as your own programs. So it’s no more difficult to extend Lisp than to write a program in it. In fact, it’s so easy (and so useful) that extending the language is standard practice. As you’re writing your program down toward the language, you build the language up toward your program. You work bottom-up, as well as top-down.
Almost any program can benefit from having the language tailored to suit its needs, but the more complex the program, the more valuable bottom-up programming becomes. A bottom-up program can be written as a series of layers, each one acting as a sort of programming language for the one above. TEX was one of the earliest programs to be written this way. You can write programs bottom-up in any language, but Lisp is far the most natural vehicle for this style.
Bottom-up programming leads naturally to extensible software. if you take the principle of bottom-up programming all the way to the topmost layer of your program, then that layer becomes a programming language for the user. Because the idea of extensibility is so deeply rooted in Lisp, it makes the ideal language for writing extensible software.
Working bottom-up is also the best way to get reusable software. The essence of writing reusable software is to separate the general from the specific, bottom-up programming inherently creates such a separation.
Instead of devoting all your effort to writing a single, monolithic application, you devote part of your effort to building a language, and part to writing a (proportionately smaller) application on top of it. What’s specific to this application will be concentrated in the topmost layer. The layers beneath will form a language for writing applications like this one – and what could be more reusable than a programming language?
Lisp allows you not just to write more sophisticated programs, but to write them faster. Lisp programs tend to be short – the language gives you bigger concepts, so you don’t have to use as many. As Frederick Brooks (best-known for his book ‘The Mythical Man-Month’) has pointed out, the time it takes to write a program depends mostly on its length. So this fact alone means that Lisp programs take less time to write.The effect is amplified by Lisp’s dynamic character: in Lisp the edit-compile-test cycle is so short that programming is real time.
Bigger abstractions and an iterative environment can change the way organizations develop software. The phrase rapid prototyping describes a kind of programming that began with Lisp: in Lisp, you can often write a prototype in less time than it would take to write the spec for one. What’s more, such a prototype can be so abstract that it makes a better spec than one written in English. And Lisp allows you to make a smooth transition from prototype to production software. When Common Lisp programs are written with an eye to speed and compiled by modern compilers, they run as fast as programs written in any other high-level language.
All of this obviously means that you can now spend less time working and finally take your family out for that dinner you’ve been promising for the last three years – happy boss, happy family.
Macros may be the single most important feature why Lispers put up with all those annoying parentheses in their code. These very parentheses enable this powerful macro system in Lisp. Paul Graham, who is as near to some “Lisp missionary” as possible, points out that Lisp code is made out of Lisp data objects. And not in the trivial sense that the source files contain characters, and strings are one of the data types supported by the language. Lisp code, after it’s read by the parser, is made of data structures that you can traverse.
If you understand how compilers work, what’s really going on is not so much that Lisp has a strange syntax (parentheses everywhere!) as that Lisp has no syntax. You write programs in the parse tress that get generated within the compiler when other languages are parsed. But these parse trees are fully accessible to your programs. You can write programs that manipulate them. In Lisp, these programs are called macros. They are programs that write programs.
Doug Hoyte, author of the book ‘Let Over Lambda’³ gives a lot of credit to macros for efficient Lisp performance. He says that while other languages give you small, square tiles, Lisp lets you pick tiles of any size and of any shape. With C, programmers use a language that is directly tied to the capabilities of a fancy
fixnum adder. Aside from procedures and structures, little abstraction is possible in C. By contrast, Lisp was not designed around the capabilities and limitations of the machines. But surely other languages can be written in less efficient, more convenient ways.
Instead of inquiring what makes a program fast, it’s better to ask what makes a program slow. The root causes can be roughly classified into three broad categories:
- Bad algorithms
- Bad data-structures, and
- General code
All language implementations need good algorithms. An algorithm is a presumably well-researched procedural description of how to execute a programming task. Because the investment required in coming up with an algorithm is so much larger than that of implementing one, the use of algorithms is ubiquitous throughout all of computer science. Somebody has already figured out how, and why, and how quickly, an algorithms works; all you have to do to use an algorithm is translate its pseudo-code into something that your system can understand. Because Common Lisp implementations have typically been well implemented and continuously improved upon for decades, they generally employ some of the best and quickest algorithms around for most common tasks.
Good data structures are also necessary for any decent programming language. Data structures are so important that ignoring them will cause any language implementations to slow to a crawl. Optimizing data structures essentially comes down to a concept called locality – which basically says that data that is accessed most frequently should be the fastest to access. Data structures and locality can be observed clearly at almost every level of computing, where performance gains have been sought: large sets of CPU registers, memory caches, databases, and caching network proxies to name a few. Lisp offers a huge set of standard data structures and they are generally implemented very well.
If Lisp provides such good algorithms and data-structures, how is it even possible that Lisp code can be slower than code in other languages? The explanation is based on the most important design decision of Lisp: general code, a concept otherwise familiar to us as duality of syntax. When we write Lisp code, we use as many dualities as possible. The very structure of the language encourages us to. Past of the reason why Lisp programs are usually much shorter than programs in other programming languages is because any given piece of Lisp code can be used for so much more than can a corresponding piece of code in the other language such that you can re-use it more often. Coming from another programming language perspective, it can feel unusual to have to write more to get less, but this is an important Lisp design decision – duality of syntax. The more dualities attached to each expression, the shorter a program seems to be.
Does this mean that to achieve or exceed C’s performance we need to make our Lisp programs as long and dangerous as their corresponding C programs? No, Lisp has macros.
A great medium to express Recursion
Recursion is the act of defining an object or solving a problem in terms of itself. Properly used, recursion is a powerful problem solving technique, both in artificial domains like mathematics and computer programming, and in real life.
The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.4
Lisp is the best programming language to use when working with recursive problems. Daniel P. Friedman and Matthias Felleisen demonstrate this case for Lisp in their book ‘The Little Lisper’5. Lisp is inherently symbolic – the programmer does not have to make an explicit mapping between the symbols of his own language and the representations in the computer. Recursion is Lisp’s natural computational mechanism; the primary programming activity is the creation of (potentially) recursive definitions.
Functional vs. Object Oriented
In rare moments of self-reflection, when I allow myself to doubt my skills as a Lisp evangelist, I sometimes wonder if I have left behind some of my fellow programmers who favor Object Oriented style of programming. Just because I have been focusing on Lisp as a functional programming paradigm, doesn’t mean we don’t have a role for you in our plans of world domination. Here’s where you fit in.
With a OO approach, a programmer writes code that describes in exacting detail the steps that the computer must take to accomplish the goal. She focuses on how to perform tasks and how to track changes in state. She would use loops, conditions, and method calls as her primary flow control and instances of structures or classes as primary manipulation unit. OO tries to control state behind object interfaces.
In contrast, FP involves composing the problem as a set of functions to be executed. An FP programmer focuses on what information is desired and what transformations are required by carefully defining the input to each function, and what each function returns. She would use function calls including recursion as her primary flow control and functions as first-class objects and data collection as primary manipulation units. FP tries to minimize state by using pure functions as much as possible.
OO makes code understandable by encapsulating moving parts.
FP makes code understandable by minimizing moving parts.6
Functional Programming is the art of writing programs that work by returning values, instead of modifying things. Functional Programming also enables you to create fabulously powerful and very efficient abstract programs. Functional Programming is a mathematical approach to programming. In math, for at least the last four hundred years, functions have played a much more central role. Functions express the connection between parameters (the “input”) and the result (the “output”) of certain processes. In each computation the result depends in a certain way on the parameters. Therefore a function is a good way of specifying a computation. This is the basis of the functional programming style. A ‘program’ consists of the definition of one or more functions. With the ‘execution’ of a program the function is provided with parameters, and the result must be calculated. Writing code in a functional style guarantees that a function does only one thing (returns a value) and is dependent on one thing (the parameters passed to it). This equips you to control side effects.
Conard Barski, author of ‘Land of Lisp’7, points out that the critics of OO programming style may complain that object-oriented techniques force data to be hidden away in lot of disparate places by requiring them to live inside many different objects. Having data located in disparate places can make programs difficult to understand, especially if that data changes over time. Therefore, many Lispers prefer to use functional techniques over object-oriented techniques, though the two can often be used together with some care. Nonetheless, there are still many domains in which object-oriented techniques are invaluable, such as in user interface programming or simulation programming.
However, some side effects are almost always necessary for a program to actually do something. This means that you can’t write a useful program that has the entirety of its code written in the functional style. James Hague in his assessment of functional programming argues that “100% pure functional programming doesn’t work. Even 98% pure functional programming doesn’t work. But if the slider between functional purity and 1980s BASIC-style imperative messiness is kicked down a few notches – say to 85% – then it really does work. You get all the advantages of functional programming, but without the extreme mental effort and unmaintainability that increases as you get closer and closer to perfectly pure.”
So, if OO is what gets you going, Common Lisp offers the most sophisticated object-oriented programming framework of any major programming language. It’s called Common Lisp Object System (CLOS). It is customizable at a fundamental level using the Metaobject Protocol (MOP). It’s claimed that there’s really nothing like it anywhere else in programming. It lets you control incredibly complex software without losing control over the code.
Two common Lisp myths shattered
Myth 1: Lisp is slow because it is interpreted
Common Lisp is not an interpreted language. In fact, there is not even a reasonable definition of “interpreted language”. The only two reasonable definitions of “interpreted language” that I can think of:
A language that can be implemented with an interpreter,
A language that must be implemented with an interpreter.
In the first case, all languages are interpreted. In the second case, no language is interpreted.
Sometimes, we confuse interpreted and interactive. We tend to think that whenever there is an interactive loop such as the Lisp’s read-eval-print-loop, there must also be an interpreter. That is false. The
eval part can very well be implemented with a compiler. Sometimes, the belief is that even though it is possible to implement Common Lisp with a compiler, it is usually done with an interpreter, and hence most implementations are slow. This might be the case for programs written by amateurs, but is seldom the case with systems written by hackers. Almost every Common Lisp system in existence uses a compiler. Most Common Lisp compilers are capable of generating very good, vary fast code. Obtaining fast code may require the hacker to add declarations that assist the compiler in optimizing the code, such that fast object code is not derived out of naïve source code.
Also, mortals have a tendency to exaggerate the importance of speed. There are quite a number of applications that use very slow systems, such as Perl, Shell, Tcl/Tk, Awk, etcetera. It is not true that maximum speed is always required.
Myth 2: Lisp is not used in industry (I’ve not seen Lisp in advertisement for employment)
Lisp is used. Several major commercial software packages are written in Common Lisp or some other Lisp variant. It is hard to know in what language commercial software is written (since the user should not have to care), but there are a few that are well known. Interleaf, a documentation system, is written in Lisp. So is AutoCAD, a system for computer-aided design. Both are major applications in their domains. While not a commercial software system, Emacs is an important system written in Lisp.
But even if Common Lisp were not used at all in industry, this would not be a good argument. The level of sophistication of the software industry is quite low with respect to programming languages, tools, and methods. The university should teach advanced languages, tools and methods with the hope of having industry use them one day, as opposed to teaching bad ones that happen to be used today. Students who want training in particular tools that happen to be demanded at the moment, should quit the university and apply for more specific training programs.
Lisp was and is one of the dominant languages for Artificial Intelligence (AI) programming, but should not be seen as a language that it is exclusive to the AI world. The AI community embraced the language in the 1980s because it enabled rapid development of software in a way that was not possible with other mainstream languages of the time, such as C. In the 1980s and early 1990s, the emphasis of mainstream software development methodologies was on ‘getting it right first time’, an approach that demanded up-front effort on careful system specification and did not allow for changes in specification during later stages of the software development lifecycle. In AI, software development needed to be much more agile, so that inevitable changes in specification could more easily be accommodated by iterative development cycles. Lisp is ideal for this, as it can be tested interactively and provides for concise, quick coding using powerful high-level constructs such as list processing and generic functions. In other words, Lisp was ahead of its time because it enabled agile software development before it became respectable in mainstream software.
Besides, whether a language such as Common Lisp is used in industry depends a lot more on the individual student than on industry. There is a widespread myth among students that industry is this monolithic entity whose tools and methods cannot be altered. In reality, industry consists of people. Whatever industry uses is whatever the people working there use. Instead of refusing to learn sophisticated tools and techniques, the student can resolve to try to become one of the forerunners in industry after graduation.
Lisp: God’s own programming language
I would like to think that this article and it’s precursor strikes a chord with all of you – the ones who’ve fallen in love with lisp, the ones who still don’t get what all the fuss is about and the ones who need some more nudging to fall off the fence (onto the right: lisp-loving-side). For those of you in the second and third category, here’s your final push:
For God wrote in Lisp code
When He filled the leaves with green.
The fractal flowers and recursive roots:
The most lovely hack I’ve seen.
And when I ponder snowflakes,
never finding two the same,
I know God likes a language
with its own four-letter name.
- Partial lyrics of the song “Eternal Flame” (http://www.gnu.org/fun/jokes/eternal-flame.html)
- ‘The Evolution of Lisp’ by Guy L. Steele Jr. and Richard P. Gabriel available here
- Revenge of the Nerds, Paul Graham
- Let Over Lambda, Doug Hoyte
- Algorithms + Data Structures = Programs. Wirth, Niklaus (1976). Prentice-Hall
- The Little Lisper, Daniel P. Friedman and Matthias Felleisen
- From Michael Feathers (http://twitter.com/#!/mfeathers/status/29581296216)
- Land of Lisp, Conrad Barski