Reasons to learn ANSI Common Lisp

Lisp has been hailed as the world’s most powerful programming language. But only few programmers use Lisp because of its cryptic syntax and academic reputation, which is rather unfortunate since Lisp isn’t that hard to grasp. Only the top percentile of programmers use Lisp. If you want to be among the crème de la crème, read on…

This sucks!

“I am gonna hate my job!” Those were my initial thoughts when I received an assignment at work a few years ago. I had been asked to leverage a module written in Lisp. My perception of Lisp was that of an ancient functional programming language with a cryptic syntax used only by academicians & scientists to conduct experiments in the domain of Artificial Intelligence. And those parentheses in the syntax were enough to drive anyone crazy! LISP – Lots of Irritating Superfluous Parentheses?

At that time, I believed that I was an ace at a cool, new age Object Oriented programming language. This programming language was the medium of my expression: I ate, drank, and dreamt in that language. Because I could produce high magic with it, I was revered as the exalted canonical wizard among the confrere developer community. It made me the God of my machine universe. Through it’s syntax I would say when it’s sunny and when it rains. And my machine universe would comply. I ruled over the entities of my creation with an iron first without the consequence of defiance or the fear of yet another Jasmine Revolution.

I also believed I was someone exceptionally attractive to women, spent hours in-front of the mirror doing my hair, and drove my sluggish & 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 non-structured programming paradigm to procedural programming and then towards object-oriented programming will relate to Paul Graham when he says in his book ‘Hackers & Painters’ something to the tune of “You can’t trust the opinion of others about 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 did I code without Objects, Methods, Encapsulation, Polymorphism, Inheritance, etcetera? One may say that it was ‘syntactic sugar’ at work.

But not with Lisp. Lisp 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

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 questions 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, I think, 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, 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. (If you ever were to enter The Matrix, you’d be happy that you are 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 another, Python, whose users tend to look down on Perl, and another called Ruby that some see as the heir apparent of Python. If you look at these languages in order, Java, Perl, Python, Ruby, you notice an interesting pattern. At least, you notice this pattern if you are a Lisp hacker. Each one is progressively more like Lisp. Python copies even 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 then.

Lisp enlightens you as a individual

All the married men would relate to Steven Levy when he illustrates an example of how hackers think in his book ‘Hackers: Heros of the Computer Revolution’. Marge Saunders would drive into the garage one of the weekend mornings and upon her return 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 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 favorite 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 that there are better responses to a question than a simple Yes/No. From then on, I learnt that the right answer to a question like that 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 week.

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 modularized. 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 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 easiest to get started with: CLISP, an open source Common Lisp. It is simple to install and runs on any operating system. 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 http://clisp.cons.org/. It will run on Windows platform, Macs, and Linux variants. 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 sources. Just type apt-get install clisp at the command line, and you’ll have CLISP installed automatically.

For other Linux distributions (Fedora, SUSE, etcetera), you can use standard packages listed under “Linux packages” on the CLISP website.

Starting it up

To run CLISP, type clisp from your command line. If all goes according to plan, you’ll see the following prompt:

Starting CLISP

Like all Common Lisp environments, CLISP will automatically place you into a read-eval-print-loop (REPL) after you start it up. This means 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:

[1]> (* 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 a pair of parenthesis. 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 A B C’s (learning the syntax of the language, it’s core features, etcetera). Sometimes, the promise of what lies beneath is more tantalizing than baring it all.

Conrad Barski (author of Land of Lisp, a great book on Lisp programming for beginners) 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 Binary Search algorithm. We know that Binary Search technique continually divide 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 in the 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 players’ 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, like this:

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 later 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 function uses the values of the *big* and *small* variables to generate a guess of the player’s number. The definition looks like this:

> (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 we’ll 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, we use defun to start the definition of a new global function smaller. Next, we 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 one 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 that 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, we’ll 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.

Here’s our game in action, with the number 74 as our guess:

The game in action

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

Advertisements
Reasons to learn ANSI Common Lisp

One thought on “Reasons to learn ANSI Common Lisp

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s