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!

Project Euler 58 : The Ulam Spiral

Alrighty! Back to Project Euler after a really long time and the difference is pretty noticeable, both in PE as well as my thinking.

PE’s got a new interface and an awesome new badge system for would-be Eulerians. However the cooler thing is that I was able to solve a problem that initially gave me many a sleepless night.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37   36   35   34   33   32   31
38   17   16   15   14   13  30
39   18     5    4     3   12  29
40   19     6    1     2   11  28
41   20    7     8    9   10   27
42   21   22   23  24   25   26
43  44   45   46  47   48   49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Pretty harrowing at first glance, but the solution is really straightforward. 🙂

This spiral is nothing but the Ulam Spiral and it has some interesting properties. Notice the left-down diagonal has all squares? The square value is simply twice the spiral layer plus 1 squared. So the first layer i.e. 1 gives (2*1 + 1)^2 = 9. Then the other 4 values are obtained by subtracting the previous even number’s 3 multiples from the square.

E.g. Take 49. That is the square of 7, 6 is the even number before it. So to get the other diagonal elements, all I do is 49 – 6, = 43, 49 – 12 = 37 and 49 – 18 = 31. This simple pattern works all the time for every layer, feel free to check!

Now, the code to solve this is even simpler. C++ can do this, but finding the range of prime numbers is a big hassle and I couldn’t find a good enough upper bound to apply The Sieve without getting a Segmentation fault, and too large values just can’t be accommodated.

Thankfully, I learnt Python this last semester while doing the coursework of an online Robotics class by Prof. Thrun. So, I decided to write a terse program to achieve the solution. Here it is:

from math import *

def isprime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    for x in range(3, int(n**0.5)+1):
       if n % x == 0:
           return False

    return True;

def calculate():
    primes = 3
    count = 5
    layer = 1

    while float(primes)/count >= 0.1:
        layer += 1
        m = 2*layer + 1

        for i in range(4):
            if isprime(m*m - i*(m-1)):
                primes += 1
            count += 1

    return 2*layer + 1

print calculate()

So I hope you understand what I am trying to do. The code is short and sweet and pretty self-explanatory, except, for the sake of the while loop, I am starting from the first layer rather than the zeroth layer which only has 1.  Now I better get back to my other programs!

Eviva!