Caveat - The Name has Changed

After almost three years of blogging, I am changing the title and subtitle of my blog. It will no longer be called as lisp any more. Why? Of late I was not writing enough about (or on) lisp. It is more and more becoming my restless rants that I do out of desperate need to fulfill my alter-ego of creativity. I gave it a long thought and paused for several minutes before I changed it. I was thinking that some people who read this blog may feel that it has changed from what it was previously. Do not worry – it is impossible to change an opinion, let alone a personality.

My obligation was not only to my reader but also to the people who lands on my blog. They shouldn’t be misguided to a belief that it is a blog purely for Lisp. Hope this will clear some clouds – hope you will enjoy it as before.

Oh I almost forgot to mention! I will definitely write about lisp and lisp related articles in the future.

Loooopy

How Tortoise Taught Recursion to Achilles

---

This post was there with me for quite some time - but couldn't complete it for almost six months. At last its done! Hope you will enjoy it.


One should read the dialog in Lewis Carroll writing or Godel, Escher, Bach.
Here is the dialog that I have referred to from Wikipedia.

---

[Achilles and Tortoise meet at a coffee shop after a long break.]


Achilles: It has been long that we have met.


Tortoise: Yeah! But the good thing is that, here we are together; once again. So what have you been doing all these days?


Achilles: Nothing!


Tortoise: So it must have been boring for you.


Achilles: Oh no, no! It was not boring at all. I have learnt programming of late and I was playing with couple of programming languages. Like I was figuring out how I can model all that we have discussed previously. Especially the one that you and I got into endless thousand page ranting on with A, B, C … to prove Z. You remember?


Tortoise: Yes, I do in fact! That was a fun! I hope you understand that it is very difficult to prove that uh!


Achilles: You should learn programming and you will come to know that what you did was an infinite loop. You would have understood the loop will go on and on.


Tortoise: Loop?


Achilles: Yes my dear friend – loop.


Tortoise: So what is this “Loop” is all about?


[Achilles smiles and continues, after a sip of cappuccino]


Achilles: You see loops are very simple. If you want to do something repeatedly you just say that.


Tortoise: Elaborate please.


Achilles: Like say you want to add all the integers from 1 to 10. You start a loop, let x equals to 1 and sum equals 0. Add sum and x and assign the result to sum, after that you increase x by 1 and do this till x is less than 11; you see you want to add all integers till 10. Pretty simple, huh?

Code snippet:
  int sum = 0;
  for (int x = 0; x < 11 ; x++) {
   sum += x;
  }

 

Tortoise: Fine! But looks odd to me!


Achilles: Why? Is there anything wrong?


Tortoise: You know my friend; you have learnt a programming language but I am a little handicapped with that, i.e. “programming language”, but I feel I have a different way of understanding this one.


Achilles: How?


Tortoise: Do you know the mathematical concept of function? Like F(x, y) = x + y?


Achilles: Yes I do.


Tortoise: Great! We can represent the solution like the following function in mathematics:

       F(x, y) = y + x; if x = 10   … (RULE 1)
         = F(x+1, y+x); 1 <= x <= 9  … (RULE 2)

O mighty Achilles! How will you write this in your programming language?


Achilles: I see! Let me tell you how to do that in programming language. [Achilles shows the code snippet]

 public int sum(int x,int y) {
  if (x == 10) {
   return y+x;
  } else {
   return sum(x+1,y+x);
  }
 }

Achilles: I knew this from my advance classes in programming – it is called recursion. But how do you explain this.


Tortoise: Very simple my friend! The RULE 1 says that if the variable x is equal to 10 you are going to produce the summation of x and sum as result else it will keep on calling itself with an incremented value of x and summation of x and the y variables. It’s very basic math you see.


Achilles: But you need to have a termination rule to complete the task! How would you explain that A, B and Z proposition problem with recursion? It was an endless loop right? No terminating condition.


Tortoise: Really? But I knew that there was a terminating condition there too! It was your last proposition. If I would have accepted it – the so called loop was over. But I did not accept it I just kept on adding one more layer in between the final and penultimate statement. So the final statement was the terminating condition.


Achilles: But as you see now, in this example we have a terminating condition as 10…


Tortoise: That need not to be 10, we can introduce a third variable say z or we can call it terminator if you like it. We can rewrite the function definition as follows:

       F(x, y, z) = y + x; if x = z   … (RULE 1)
            = F(x+1, y+x, z); 1 <= x <= 9  … (RULE 2)

And this one should work for any integer value of z – isn’t it?


Achilles: Yes it would and the program would look like:

 public int sum(int x, int y, int z) {
  if (x == z) {
   return y+x;
  } else {
   return sum(x+1, y+x, z);
  }
 }

And we could invoke this with something like: sum(1, 0, 10) and it works. But, tortoise, it is still does not create an infinite loop like what you had created.


Tortoise: Yes, Achilles it can but needs a little imagination. I created something like this:

       F(x, y, z) = y + x; if x = z   … (RULE 1)
            = F(x+1, y+x, x+2); 1 <= x <= 9 … (RULE 2)

Look closely, warrior; I have introduced a never reaching fallacy in the RULE 2 function. Instead of z I am passing x+2 as the last argument. This will prevent the condition for RULE 1 and it will remain like that illusive last statement.


[Tortoise paused for a moment]


Tortoise: Now you see it!


Achilles: Yes.


Tortoise: I am going home – would you like to join?


Achilles: No!


[Tortoise leaves slowly. Achilles looks at the paper and nods his head in disbelieve.]


Achilles: Waiter! Get me a java green please.

---

The java code for this never ending recursion would look like:

public class Recursionist {

 /**
  * @param args
  */
 public static void main(String[] args) {
  Recursionist r = new Recursionist();
  System.out.println(r.sum(1,0,100));
 }

 public int sum(int x,int sum,int termination) {
  if (x == termination) {
   return sum+x;
  } else {
   return sum(x+1,sum+x,x+2);
  }
 }
}

OUTPUT: A stack overflow exception - at some point of time I gusse.


Moreover you do not do all these for Arithmetic Progression you just use the formula.

Weekend Programming Excursion - 1

So I have joined a new company on 30th December 2009. I am now working for Thomson-Reuters. As always the blog that I write here will not represent in any manner what so ever my new employer’s views, these are just my technological rants that I always write. I do not even know whether these are read or not, but just in case you are among those people who surf around and read this blog (either occasionally or regularly) be assured that I will eventually write something in here.

So, gosh what new year it was – leaving one company and joining another, I didn’t even got a chance to work on anything (other than all the pending items that I had on my plate with my previous employer, writing a good-bye mail, meeting people who wanted to wish me luck for my new venture and of course the team send off dinner) significant to write. It was all work and no play with my laptop.

As some of you may have noticed in this blogs that Lisp is not the programming language that I am working now. I am no longer in those fortunate few who get paid for learning Lisp, working with Lisp and writing Lisp codes. But that said nobody stopped me from learning a new programming language – but as you can guess from my worthless rants that I have not even scratched the surface of it.

On a boring weekend you usually start the day with your home stuff like laundry. However, if you are a programmer who cannot live without coding something or the other in a day, you also code. That kind of coding I call a “weekend excursion into programming”. Most of the times one tends to lose all the code that you have built over the time. This is especially true for me. So before I forget what I did I would like to put it in here.

So what was that I did?

A class and an interface in Java! Yes you heard it correct just a class and an interface - an interface with one method signature and a class with one method (as of now). That’s it!

You must be wondering what the heck! 1 interface, 1 class and 1 method for each of them!

You may tell me, “Dude! You are not working hard.”

Point taken! No more blah, blah….

So here it is what I did.

The One Interface

I bad at naming but I knew that the word “lambda” has to be there for this interface name. So in the kingdom of noun (i.e. Java) I have to use adjective for interfaces so the name of the interface is LambdaService.

So what is there in this interface? Here is the code for you:

import java.util.List;
public interface LambdaService {

 T lambda(List params );
}

Pretty simple, huh! It takes a list of arguments of type T and returns an object of type T. If you are from some functional programming background, you already know this stuff. But for people who do not know how I am going to use it – hold on, you are in for a ride.

The One Class

Let me give you the class definition code also.

import java.util.ArrayList;
import java.util.List;

/**
 * @author samikc
 *
 */
public class Functional {

 public static   List map(LambdaService lambda,
           List... list) {
  List retList = new ArrayList(); 
  List params = new ArrayList();
  int iterCount = getShortestListSize(list);
  for (int i = 0;i < iterCount;i++) {
    int paramCounter = 0;
    for (List l : list) {
      params.add(paramCounter, l.get(i));
      paramCounter++;
    }
    retList.add((T) lambda.lambda(params));
  }
  return retList;
 }

 private static  int 
                getShortestListSize(List... list) {
  List retList = list[0];
  for (List l : list) {
    if (l.size() < retList.size()) {
      retList = l;
    }
  }
  return retList.size();
 }

}

So what this method map is doing here. Let me try to explain.

In map you provide a lambda service (which is a method at the end of the day) and a list. The lambda service is nothing but a strategy pattern, I am allowing others to provide an option to provide an algorithm which will be applied to each member of the list provided and result will be collated in a different list.
Notice that I have made “different list” bold. Why? As I am applying the algorithm provided I am not changing the anything inside the actual list passed on. So it does not have a side-effect.

The main is given below without any comments; I feel it’s very simple and intuitive.

The *main* Story

import java.util.ArrayList;
import java.util.List;

public class Main {
  public static void main(String[] args) {
        ArrayList il1 = new ArrayList();
        il1.add(10);
 il1.add(20);
 il1.add(30);
 ArrayList il2 = new ArrayList();
 il2.add(10);
 il2.add(20);
 il2.add(30);
 il2.add(40);
 List li = Functional.map(new LambdaService() {
  @Override
  public Integer lambda(List params) {
    Integer i1 = params.get(0);
    Integer i2 = params.get(1);
    Integer ret = i1 + i2;
    return ret;
  }
 }, il1, il2);
  
 for (Object o : li) {
  System.out.println(o);
 }
    }
}

Sample output:
20
40
60