Lisp: Tears of Joy, Part 4

“……..
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 God Lives on Terra by Julia Ecklar.

I would like to think these lines speak to all of you out there reading this article — the ones who’ve fallen in love with Lisp, the ones who still don’t get what all the fuss is about, and those 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 categories, I’ve answered a few of your questions below, which might help you along the path to enlightenment. I am standing on the shoulders of giants. Some text snippets are quoted from these two URLs:

1. http://c2.com/cgi/wiki?InterpretedLanguage
2. http://www.catalysoft.com/articles/goodAboutLisp.html

Lisp is slow because it is interpreted

Common Lisp is not an interpreted language. In fact, there is not even a reasonable definition of an “interpreted language”. The only two reasonable definitions of an “interpreted language” that I can think of, are:

1. A language that can be implemented with an interpreter.
2. 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 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, very fast code. Obtaining fast code may require the hacker to add declarations that assist the compiler in optimising 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, etc. It is not true that maximum speed is always required.

Lisp is not used in the industry

..or, “I’ve not seen Lisp in advertisements 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 universities 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 in demand at the moment, should quit 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 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 the first time”, an approach that demanded upfront effort on careful system specifications, and did not allow for changes in specifications during later stages of the software development life-cycle. In AI, software development needed to be much more agile, so that inevitable changes in specifications 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 the industry depends a lot more on the individual student than on industry. There is a widespread myth among students that the industry is this monolithic entity whose tools and methods cannot be altered. In reality, the industry consists of people. Whatever the industry uses is whatever the people working there use. Instead of refusing to learn sophisticated tools and techniques, the student can resolve to try and become one of the forerunners in the industry, after graduation.

Recursive or iterative?

Unlike some other functional programming languages, Lisp provides for both recursive and iterative programming styles. As an example, consider writing a function to compute the factorial of a positive integer n. The factorial, written n!, is the product of all integers between 1 and n; i.e., n! = n×(n-1)×(n-2)×…×2×1. A function to compute this number can be written in a recursive style as follows:

(defun fac(n)
  (if (= n 0) 1
     (* n (fac (- n 1)))))

You should read the definition of the function as follows. If n is zero, then return 1; otherwise return the product of n and the factorial of n-1. The same function can be written in an iterative style as follows:

(defun fac(n)
  (let ((result 1))
    (dotimes (i n)
      (setq result (* result (+ i 1))))
   result))

This function uses let to set up a local variable called result with an initial value of 1. It then performs n iterations of a central loop that each time multiplies the result by the loop’s counter variable (one must be added to this counter, as dotimes counts from zero). Finally, the value of the result variable is returned as the result of the function.

Object-oriented

Like many other modern programming languages, Common Lisp is object-oriented. In fact, it was the first ANSI-standard object-oriented language, incorporating CLOS (the Common Lisp Object System). CLOS provides a set of functions that enable the definition of classes, their inheritance hierarchies and their associated methods.

A class defines slots whose values carry information about object instances. The class definition can also specify default values for slots, and additional non-trivial behavioural mechanisms (such as integrity checking) performed at object creation time. As an example of object-orientation in Lisp, consider the definition of some shapes, which can be either circles or rectangles. A shape’s position is given by x and y coordinates. Further, a circle has a radius, whereas a rectangle has a width and a height. It should be possible to compute the area of circles and rectangles. A working set of definitions is given below:

(defclass shape ()
   (x y))

(defclass rectangle (shape)
   ((width :initarg :width)
   (height :initarg :height)))

(defclass circle (shape)
   ((radius :initarg :radius)))

(defmethod area ((obj circle))
   (let ((r (slot-value obj 'radius)))
      (* pi r r)))

(defmethod area ((obj rectangle))
   (* (slot-value obj 'width)
      (slot-value obj 'height)))

Using these definitions, a rectangle (instance) can be created with make-instance, for example, with a width of 3 and a height of 4:

> (setq my-rect (make-instance 'rectangle :width 3 :height 4))
#<RECTANGLE @ #x8aee2f2>

Its area can be computed by calling the method area:

> (area my-rect)
12

Below, I’ve attempted to address in my clever-yet-so-simple manner of explaining concepts (I hope that’s not laughter I hear) some of the topics my very-soon-to-be fellow Lispers have had trouble understanding from books.

Quote

Lisp evaluates everything. Sometimes you don’t want Lisp to do that; in situations like these, quote is used to override Lisp’s normal evaluation rules. This quote is a special operator. It has a distinct evaluation rule of its own, which is to evaluate nothing. It takes a single argument, and returns it verbatim.

> (quote (+ 7 2))
(+ 7 2)

This may seem to be a mundane function, since it does nothing. But, the need to prevent Lisp evaluating something arises so often that a shorthand notation is provided for quoting expressions. Common Lisp defines ' (a single quote or apostrophe) as an abbreviation for quote. Be careful not to substitute quote with ` (backquote character). ` (referred to as backquote by Common Lisp programmers, and quasiquote by Scheme programmers) has a different interpretation, which I will cover in forthcoming articles.

> ('(the list (+ 2 3 5) sums 3 elements))
(THE LIST (+ 2 3 5) SUMS 3 ELEMENTS)

Lisp programs are expressed as lists. This means that Lisp programs can generate Lisp code. Lisp programmers often write programs to write programs for them (such programs are called macros). The quote function is crucial to engineer this functionality. If a list is quoted, evaluation returns the list itself; if it is not quoted, the list is treated as Lisp code, and evaluation returns its value.

> (list '(+ 0 1 1 2 3 5)  (+ 0 1 1 2 3 5))
((+ 0 1 1 2 3 5) 12)

Atom, list, and predicates

Things inside a list — things that are not themselves lists, but words and numbers (in our examples so far) — are called atoms. Atoms are separated by white space or parenthesis. You may use the term atom to refer to just about any Lisp object that is not viewed as having parts. Atoms like 2.718 and 42 are called numeric atoms, or just numbers.

Atoms like foo, bar, and + are called symbolic atoms, or just symbols. Both atoms and lists are called symbolic expressions, or more succinctly, expressions. Symbolic expressions are also referred to as s-expressions, s being short for symbolic, to distinguish them from m-expressions, m being short for meta. Symbols are sometimes referred to as literal atoms.

You can check if an s-expression is an atom or not by using predicates — functions that return true or false when testing a value for a particular property. In Lisp, false is indicated by NIL, and true is often signalled by the special symbol T, but anything other than NIL is considered to indicate true. Similarly, the function listp determines whether something is a list.

> (atom '(functional)
T
> (atom '(a b c))
T
> (listp '(a b c))
T
> (listp 2.718)
NIL

setq

Most programming languages provide a special notation for assignment. Lisp does no such thing. Instead, Lisp uses its routine workhorse, the function. Lisp has a special function, called setq, that assigns the value of one of its arguments to the other argument. To accomplish the equivalent of x <-- 47 in Lisp, we write the following:

> (setq x 47)
47
> (setq y (+ 4 7))
11
> (+ 3 (setq z (* 3 7)))
24
>z
21
> (setq my-medium-of-expression "Lisp")
"Lisp"

setq gives each variable symbol the value of the corresponding value expression. The setq form can take any even number of arguments, which should be alternating symbols and values. It returns the value of its last value.

> (setq month "August" day 04 year 2011)
2011
> day
04
> month
"August"

Lisp tries to evaluate arguments before applying a function. When we evaluate a setq, the symbol (in our example, x, y, and z) may not be defined. This should cause an error — the only reason it does not is because setq is an instance of a special function. Lisp may handle the argument of each special function idiosyncratically. setq does not cause its first argument to be evaluated; and the second argument is subject to normal treatment. Fortunately, there are only a small number of special functions in Lisp.

What’s next? Drum-roll… (and if this were a television series, there would be fireworks going off now)… Macros. After weeks of reading about the power of macros, you will finally learn how to write them. For those of you who don’t know what I’m talking about, think Agent Smith (the dark-glasses-wearing AI program in the movie Matrix) turning into a self-replicating computer virus. If, for a second, you ignore the fact that he was the antagonist in the movie, and that nobody likes computer viruses, and focus instead on the concept of programs that can actually write programs, I am sure the start of next month will see you parked at a newsstand waiting for the next edition of LFY. And I look forward to it as well, as that will take us one step closer to our plans of world domination.