Lisp: Tears of Joy, Part 1

“I am going to hate my job.” Those were my initial thoughts when I received an assignment at work, a few years ago. I had been asked to maintain and leverage a client module written in Lisp. My perception of Lisp was that of an ancient functional programming language with a cryptic syntax, used only by academicians and scientists to carry out experiments in the domain of Artificial Intelligence. And Lisp’s ever-present parentheses were enough to drive anyone crazy!

At that time, I believed that I was an ace at a cool, new-age, object-oriented programming language, which was the medium of my expression: I ate, drank, slept, and dreamt in that language. It made me the God of my machine universe. I also believed I was exceptionally attractive to women, and spent hours in front of the mirror doing my hair, and drove my sluggish and worn-out Kinetic Honda as if it was a 1340cc Suzuki Hayabusa.

I now know better…

Déjà vu

Those of us who witnessed the shift from the non-structured programming paradigm to procedural programming, and then towards object-oriented programming, will relate to what Paul Graham had to say in his book, “Hackers & Painters”. It is something to the effect of, “You can’t trust the opinion of others regarding which programming language will make you a better programmer. You’re satisfied with whatever programming language you happen to use, because it dictates the way you think about programs. I know this from my own experience, as a high-school kid writing programs in BASIC. That language didn’t even support recursion. It’s hard to imagine writing programs without using recursion, but I didn’t miss it at the time. I thought in BASIC. And I was a whiz at it. Master of all I surveyed.”

Three weeks into hacking Lisp, I had a feeling of déjà vu — the previous experience being when I first “progressed” from BASIC to C, and from C to C++ and Java. With each leap, I would be happily surprised with the growing power (of programming) at my fingertips. Time and again, I would wonder how I ever coded without objects, methods, encapsulation, polymorphism, inheritance, etcetera! One may say that it was syntactic sugar at work.

But not with Lisp, which is pure ecstasy. It’s not just beautiful, but strangely beautiful.

In his famous essay, “How to become a Hacker”, Eric Steven Raymond (author of many best sellers including “The Cathedral and the Bazaar”), writes: “Lisp is worth learning for the profound enlightenment experience you will have when you finally get it. That experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself, a lot.”

Lisp enlightens you as a hacker

So what’s so great about Lisp? How does it enlighten you as a hacker? Lisper Paul Graham explains this so proficiently and methodically that it will be inappropriate to answer this question in any other words than his. The five languages (Python, Java, C/C++, Perl, and Lisp) that Eric Raymond recommends to hackers fall at various points on the power continuum. Where they fall relative to one another is a sensitive topic, but I think Lisp is at the top. And to support this claim, I’ll tell you about one of the things I find missing when I look at the other four languages. How can you get anything done in them without macros?

Many languages have something called a macro. But Lisp macros are unique. 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, you’ll realise that what’s really going on is not so much that Lisp has a strange syntax (parentheses everywhere!), but that it has no syntax. You write programs in the parse trees 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. (If you ever were to enter “The Matrix”, you’d be happy that you were a Lisp maestro.)

We know that Java must be pretty good, because it is the cool programming language. Or is it? Within the hacker subculture, there is another language called Perl that is considered a lot cooler than Java. But there is yet another, Python, whose users tend to look down on Perl, and another called Ruby, that some see as the heir apparent to Python.

If you look at these languages in order, Java, Perl, Python and Ruby, you’ll notice an interesting pattern — at least, you’ll notice this pattern if you are a Lisp hacker. Each one is progressively more like Lisp. Python copies even those features that many Lisp hackers consider to be mistakes. And if you’d shown people Ruby in 1975 and described it as a dialect of Lisp with syntax, no one would have argued with you.

Programming languages have almost caught up with 1958! Lisp was first discovered by John McCarthy in 1958, and popular programming languages are only now catching up with the ideas he developed back then.

Lisp enlightens you as an individual

All married men would relate to Steven Levy when he illustrates an example of how hackers think, in his book, Hackers: Heroes of the Computer Revolution. Marge Saunders would drive back into the garage on a weekend morning, and would ask her husband, Bob, “Would you like to help me bring in the groceries?” He would reply, “No.”

Stunned, she would drag in the groceries herself. After the same thing occurred a few times, she exploded, hurling curses at him and demanding to know why he always said, “No” to her question. “That’s a stupid question to ask,” he said. “Of course I won’t like to help you bring in the groceries. If you ask me if I’ll help you bring them in, that’s another matter.”

When I used to program in my favourite OO programming language, my response was no different. Luckily for me, I discovered Lisp. It gave me a holistic view of the self, the cosmos, and also taught me that there are better responses to a question than a simple Yes/No.

From then on, I have learned that the right answer to a Marge Saunder-like question would be “Sure, dear! Do you need me to do anything else for you?” Needless to say, my wife is a happier person, and we celebrated our seventh anniversary last month.

The functional programming edge

In his famous paper, “Why Functional Programming Matters”, computer scientist R John M Hughes says that conventional languages place conceptual limits on the way problems can be modularised. Functional languages push those limits back.

Two features of functional languages in particular — higher-order functions and lazy evaluation, can contribute greatly to modularity. As an example, Lisp allows us to manipulate lists and trees, program several numerical algorithms, and implement the alpha-beta heuristic (an algorithm from Artificial Intelligence used in game-playing programs). Since modularity is the key to successful programming, functional languages like Lisp are vitally important to the real world.

Getting started

Any language that obeys the central principles of Lisp is considered a Lisp dialect. However, the vast majority of the Lisp community uses two Lisps: ANSI Common Lisp (often abbreviated CL) and Scheme. Here, I will be exclusively talking about the ANSI Common Lisp dialect, the slightly more popular of the two.

Many great Lisp compilers are available, but one in particular is the easiest to get started with: CLISP, an open source Common Lisp compiler. It is simple to install, and runs on any operating system — Windows platforms, Macs, and Linux variants. Mac users may want to consider LispWorks, which will be easier to get running on their machines.

Installing CLISP

You can download a CLISP installer from its official website. On Windows, you simply run an installed program. On a Mac, there are some additional steps, which are detailed on the website. On a Debian-based Linux machine, you should find that CLISP already exists in your standard software repositories. Just run apt-get install clisp at the command line and you’ll have CLISP installed automatically. For other Linux distributions (Fedora, openSUSE, etc), you can use the standard packages listed under “Linux packages” on the CLISP website (if it’s not available on the distro repository).

Starting it up

To start CLISP, run clisp at your command line. If all goes according to plan, you’ll see the prompt shown in Figure 1.

Like all Common Lisp environments, CLISP will automatically place you into a read-eval-print-loop (REPL) after you start it up. This means that you can immediately start typing in Lisp code. Try it out by typing (* 7 (+ 4 3)). You’ll see the result printed below the expression:

> (* 7 (+ 4 3))
49

In the expression (* 7 (+ 4 3)), the * and the + are called the operator, and the numbers 7, 4, and 3 are called the arguments.

In everyday life, we would write this expression as ((4 + 3) * 7), but in Lisp, we put the operators first, followed by the arguments, with the whole expression enclosed in parentheses. This is called prefix notation, because the operator comes first.

By the way, if you make a mistake and CLISP starts acting crazy, just type :q and it’ll fix everything. When you want to shut down CLISP, just type (quit).

What’s under the hood?

Let’s not go down the traditional route of starting with the ABCs (learning the syntax of the language, its core features, etc). Sometimes, the promise of what lies beneath is more tantalising than baring it all. Conrad Barski gets you excited about Lisp by showing you how to write a game in it. Let’s adopt his method, and write a simple command-line interface game using a Binary Search algorithm.

We know that the Binary Search technique continually divides the data in half, progressively narrowing down the search space, until it finds a match, or there are no more items to process. It’s the classic guess-my-number game. Ask your friend (or better, your non-technical boss, who yelled at you the last time you fell asleep at a meeting) to pick a number between 1 and 100 (in his head) and your Lisp program would guess it in no more than 7 iterations.

This is how Barski explains the game:

To create this game, we need to write three functions: guess-my-number, smaller, and bigger. The player simply calls these functions from the REPL. To call a function in Lisp, you put parentheses around it, along with any parameters you wish to give the function. Since these particular functions don’t require any parameters, we simply surround their names in parentheses when we enter them.

Here’s the strategy behind the game:

1. Determine the upper and lower (big and small) limit of the player’s number. In our case, the smallest possible number would be 1, and the biggest would be 100.
2. Guess a number in between these two numbers.
3. If the player says the number is smaller, lower the big limit.
4. If the player says the number is bigger, raise the small limit.
5. We’ll also need a mechanism to start over with a different number.

In Common Lisp, functions are defined with defun, as follows:

defun function_name(arguments)
...)

As the player calls the functions that make up our game, the program will need to track the small and big limits. In order to do this, we’ll need to create two global variables called *small* and *big*. A variable that is defined globally in Lisp is called a top-level definition. We can create new top-level definitions with the defparameter function.

> (defparameter *small* 1)
*SMALL*
> (defparameter *big* 100)
*BIG*

The asterisks surrounding the names *big* and *small* — affectionately called earmuffs — are completely arbitrary and optional. Lisp sees the asterisks as part of the variable names, and ignores them. Lispers like to mark all their global variables in this way as a convention, to make them easy to distinguish from local variables, which we’ll discuss in subsequent articles. Also, spaces and line breaks are completely ignored when Lisp reads in your code.

Now, the first function we’ll define is guess-my-number. This uses the values of the *big* and *small* variables to generate a guess of the player’s number. The definition looks like what follows:

> (defun guess-my-number()
        (ash (+ *small* *big*) -1))
GUESS-MY-NUMBER

Whenever we run a piece of code like this in the REPL, the resulting value of the entered expression will be printed. Every command in ANSI Common Lisp generates a return value. The defun command, for instance, simply returns the name of the newly created function. This is why we see the name of the function parroted back to us in the REPL after we call defun.

What does this function do? As discussed earlier, the computer’s best guess in this game will be a number in between the two limits. To accomplish this, we choose the average of the two limits. However, if the average number ends up being a fraction, we’ll want to use a near-average number, since we’re guessing only whole numbers.

We implement this in the guess-my-number function by first adding the numbers that represent the high and low limits, then using the arithmetic shift function, ash, to halve the sum of the limits and shorten the results. The built-in Lisp function ash looks at a number in binary form, and then shifts its binary bits to the left or right, dropping any bits lost in the process. For example, the number 11 written in binary is 1011. We can move the bits in this number to the left with ash by using 1 as the second argument:

> (ash 11 1)
22

We can move the bits to the right (and lop off the bit on the end) by passing in -1 as the second argument:

> (ash 11 -1)
5

Let’s see what happens when we call our new function:

> (guess-my-number)
50

Since this is our first guess, the output we see when calling this function tells us that everything is working as planned: the program picked the number 50, right between 1 and 100. Now, let’s write our smaller and bigger functions. Like guess-my-number, these are global functions defined with defun:

> (defun smaller()
      (setf *big* (1- (guess-my-number)))
      (guess-my-number))
SMALLER

> (defun bigger()
      (setf *small* (1+ (guess-my-number)))
      (guess-my-number))
BIGGER

First, let’s use defun to start the definition of a new global function, smaller. Next, use the setf function to change the value of our global variable *big*. Since we know the number must be smaller than the last guess, the biggest it can now be is 1 less than that guess.

The code (1- (guess-my-number)) calculates this: It first calls our guess-my-number function to get the most recent guess, and then it uses the function 1-, which subtracts 1 from the result.

Finally, we want our smaller function to show us a new guess. We do this by putting a call to guess-my-number as the final line in the function body. This time, guess-my-number will use the updated value of *big*, causing it to calculate the next guess. The final value of our function will be returned automatically, causing our new guess (generated by guess-my-number) to be returned by the smaller function.

The bigger function works in exactly the same manner, except that it raises the *small* value instead. After all, if you call the bigger function, you are saying your number is bigger than the previous guess, so the smallest it can now be (which is what the *small* variable represents) is one more than the previous guess. The function 1+ simply adds 1 to the value returned by guess-my-number.

To complete our game, let’s add a function start-over, to reset our global variables:

> (defun start-over()
      (defparameter *small* 1)
      (defparameter *big* 100)
      (guess-my-number))

As you can see, the start-over function resets the values of *small* and *big* and then calls guess-my-number again to return a new starting guess. Whenever you want to start a brand-new game with a different number, you can call this function to reset the game.

Figure 2 shows our game in action, with the number 74 as our guess.

In forthcoming articles, we’ll go the ABC way, starting with the basic syntax and semantics of the language.

Power corrupts. Lisp is power. Study it hard. Be evil. And let’s plan for world domination!