The Power of Lisp

A few years ago, I discovered Lisp (and Common Lisp in particular) and while reading upon it to see what made it tick, a certain pattern arose on its description. All the programmers who preferred Lisp (which, it turns out, is every Lisper, myself included) wrote about how it was the most powerful programming language, how it changed the way you thought about coding and how it never mattered if you actually programmed in Lisp, just “getting it” was enough to awaken the hacker in you.

Safe to say, I found all that hard to believe, and while I am a believer now, the lack of concrete examples really was the true reason it took me a while to really “get” Lisp. Thus, I hope to provide you with that concrete example.

A Little Background

Lisp code is written in the Polish Notation and as such has a very peculiar syntax for those indoctrinated in the way of C. This syntax, while confusing at first, actually proves to be quite easy and very natural from a mathematical standpoint. For example, if I want to add 3 numbers {3, 10, 26}, then I can easily write


(+ 3 10 26)

Notice that I only use the + operator once. While this may seem trivial, it proves to be very powerful when going into advance Lisping. In terms of actual running, Lisp evaluates each of the arguments first in order recursively before evaluating the final function (the arguments in Lisp functions can be functions themselves, a neat trick called First Class Functions).

Also, when you define variables in Lisp, all variables end up being pointers to the values they stand for (some implementations of Lisp prefer storing the values that are really small in the variables themselves). Lisp automatically handles these pointers so don’t worry about it too much like you do in C.

The Example

I was asked this question a few days ago and after struggling for a minute, it simply dawned to use Lisp and think in that manner. Safe to say, I got the answer immediately


i = 5

j = ++i + ++i + ++i

print i, j

j = ++i + (++i + ++i)

print i, j

What is the value of i and j at each of the print statements?

Now many of you might say that this is either compiler or language dependent, but this is just plain math and does not quite depend on anything other than the Abstract Syntax Tree that the compiler constructs, which is general in terms of technique.

If you’re done banging your head against the wall, the solution can easily be inferred using the Lisp way. First I write the Lisp equivalent of the first statement of the above code (I use the assignment for j rather than setf to keep this example beginner friendly):


j = (+ (+ (++ i) (++ i) ) (++ i) )

Now for the entire dry run:


j = (+ (+ (++ i) (++ i) ) (++ i) )      ; i = 5
j = (+ (+ i (++ i) ) (++ i) )      ; i = 6
j = (+ (+ i i ) (++ i) )      ; i = 7
j = (+ (+ 7 7 ) (++ i) )      ; i = 7
j = (+ 14 (++ i) )      ; i = 7
j = (+ 14 i )      ; i = 8
j = (+ 14 8 )      ; i = 8
j = 22      ; i = 8

Now notice how the form of the Lisp code matches the exact way the syntax tree is constructed in a very natural way. This is inherent of all Lisp programs by the design of the language.

Now for the second statement:

j = (+ (++ i) (+ (++ i) (++ i) ) )      ; i = 5
j = (+ i (+ (++ i) (++ i) ) )      ; i = 6
j = (+ i (+ i (++ i) ) )      ; i = 7
j = (+ i (+ i i ) )      ; i = 8
j = (+ i (+ 8 8 ) )      ; i = 8
j = (+ i 16 )      ; i = 8
j = (+ 8 16 )      ; i = 8
j = 24      ; i = 8

There you have it. Easy to comprehend and zero ambiguity present. If you try running the original code in C or any other language, you will see that the answer is  the exact same.  While a solid understanding of Parse Trees will also get you the same answer, thinking in the Lisp way is always easier.

I hope you now understand what I mean by “getting Lisp”. It is this kind of clear, precise thinking that Lisp propagates and inculcates in all the people who invest their valuable time in learning the language without regard for the immediate benefits, like money. Lisp truly is a language powerful beyond anything and this fact comes to light with every generation of programming languages that introduce features that have existed for years in Lisp. For more arguments why Lisp rocks, read this.

Hope you are a neophyte now.

Eviva!

Advertisements

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