Alpha Bravo Charlie

Adeel Suleman visited me this weekend. He has been in Copenhagen (Denmark) for the last 3 months for a project on behalf of his company.

I met him first time in 1991 when we moved from Lahore to Rawalpindi and I got admission in F.G. Sir Syed Boys' Secondary School, The Mall. That was 7th grade (I was 11 then) and we studied together till matriculation.

FG Sir Syed (as we used to call it) was one hell of a school. There were about 3500 students and being an FG school the fee was minimal - we used to pay Rs. 26.75 a month (and I actually paid a reduced fee, perhaps Rs. 16/-, as my elder brother was also studying there). As you can expect, the standard of education was horrible. But the competition was enough to keep us giving our best. There were about 400 students in 10th grade divided into 5 sections. Our section had 80 students and about 60 chairs, which meant some of us had to stand the whole day (or had to sit on the floor). We used to steal chairs from neighboring sections and then they used to come to us in search for their chairs.

Not only there was shortage of furniture, there was shortage of drinking water as well. There was only one water tank for 3500 students and on top of that they had this PTI who used to beat us with a stick if we drank water after recess. Of course, the water tank and the water itself were unhygienic.

One of the other regular features of our school was that some students bunked classes and used to go to video game shops or to a cinema in Pindi Saddar. The principal had a Suzuki Bolan in which he used to go and bring them back. Our teacher of Biology, for example, hadn't studied Biology himself. He had done FA and was preparing for BSc. There were countless other amusing things: I still believe that if you recorded a day's proceedings of the school, it would have been a hit TV serial.

Despite all of this, the fee as well as the location of the school were very attractive. Almost every middle-class family in Rawalpindi wanted to send their children to this school. This meant too much competition for us. In our section only, there were 5 students who competed for 1st position and an equal number for the later positions. Some of us were very jealous of others. We studied day and night to get more and more marks. Not only we had to compete amongst ourselves, a few students were sons of teachers and they used to get much more marks than they deserved.

There was Kamran Ashar Siddiqui who had got 1st position in Federal Board exams of 5th class and later got 2nd position in Federal Board in 8th class. He later joined PAF Academy Risalpur and became an Aeronautical Engineer - the most brilliant guy I know.

There was Usman who got 1st position in FSc exams in the entire Federal Board (which comprises of all the colleges in Islamabad, some in Rawalpindi, all Pakistan embassy colleges, all Fauji Foundation, Army Public, Bahria and PAF colleges anywhere in Pakistan and many other colleges). He was awarded a Gold Medal then. He later topped UET Taxilla as an Electrical Engineer.

Zubair Khalid got Gold Medal in Matric. He is now with Army Signals. Then there was yours truly who got 2nd position in Federal Board in FSc. General Science and later topped FAST ICS, Karachi.

And in this race was Adeel Suleman who graduated from FAST ICS, Islamabad and is now working in Pisigma.

Then there was a second lot who competed for the position after these 5: Abdus Sammad who is son of Col. Ashfaq Hussain (who wrote Gentleman Bismillah, Gentleman Alhumdo Lillah, Fatih-e-Suboona and he was the man behind Sunehray Din and Alpha Bravo Charlie with Shoaib Mansoor). He joined Army and last time I heard of him, he was fighting in Siachin. And then my elder brother, Akbar, who got medals and scholarship in BBA and MBA. He graduated from IBA and is now Sales Category Manager at Reckitt Benckiser. Salman Iqbal, Saqib Gillani; the list goes on and on...

We were all class mates!


Adeel and Me

I wonder how Adeel would have reacted if the professional jealousy were still between us. We discussed at length what we had been doing and what we plan to do next.

Are we still running for something without knowing where we will end up? Or do we see life in a bigger perspective?

آنکھیں دیکھتی رہ جاتی ہیں
سپنے دور نکل جاتے ہیں
اور سپنوں کا پیچھا کرنے والے
اپنے نام گنوا دیتے ہیں۔
کبھی الفا، کبھی براو، کبھی چارلی۔

(Theme Song of Alpha Bravo Charlie by Shoaib Mansoor)

Summer Time

I'm done with the exams. The result will be announced within two weeks. The only thing left is my thesis work and the final presentation. This will take at the least three months. Following is a hypothesized conversation:

You mean you will be holding a Masters degree in a few months?
Yups, baby!

But you don't know the ABC of computing!
That's a separate issue. And if I learn everything now, what good would be a PhD degree? (psst...that's only to impress you, I don't have any plans to become a PhD)

What do you plan to do next?
Same old coding...what I was doing before coming here.

Then why did you take all this pain to pursuit a graduate degree? It would have been better to do a certification in a programming language, perhaps C#.
Can't you see, I'm a changed man? I've studied in one of the very good universities of Europe and I've topped most of the courses in my program. I've secured the maximum possible grade in all the courses. I know what exactly the difference is between ours and their education; what exactly we are doing wrong; how academia helps industry; what is true research; how to read research papers; etc.

How does it effect you, your life or your future?
hm...I don't know. But you see, I have found out my own limitations! I've learnt to live alone! I've learnt to cook! I got time for silent meditation!

Have you learnt how to drive?
You ask too many questions. I'm off.

Alas, I couldn't find work for summer; nor do I have money to visit back home. This means that I'll have lots and lots of time to kill at my hands. You'll find some interesting things over here in the coming days.

For now, check these out: Urdu Word and I've Learned.

Alice in Wonderland

There are good chances that you already know about Alice and her Wonderland. Perhaps, you saw the cartoon movie or read the book itself. Or perhaps you were made to read an excerpt from it as part of your textbook.

I read some part of the story during my school days (perhaps in 6th grade). I found it very stupid as it made no sense to me. There was no "moral of the story" that you learn at the end, like other stories for children. But years later I came to know about the author: Lewis Carroll (pen name). He was a mathematician!

I couldn't believe that somebody good at logic could write a story like this. More years passed and I happened to come across a few passages from the story. Here is one for your reading pleasure:

"Would you tell me, please, which way I ought to go from here?"

"That depends a good deal on where you want to get to," said the Cat.

"I don't much care where --" said Alice.

"Then it doesn't much matter which way you go," said the Cat.

"--- so long as I get somewhere," Alice added as an explanation.

"Oh, you're sure to do that," said the Cat, "if only you walk long enough."

I think this is a very well written anecdote. Some more years passed and I faced an interesting question in my Software Engineering Using Formal Methods course:

Given that

Some pillows are soft.
No sticks are soft.

Which one of these can you conclude?
(a) Some pillows are not sticks.
(b) Some sticks are not pillows.

It's a slightly modified form of a puzzle by Lewis Carroll. It's a very interesting exercise to solve this puzzle. I'll tell the answer in comments and some hints on how to solve such things.

Now, I was pretty sure that though Alice's Adventures in Wonderland (that's the original name) is for children but it's not that stupid. Fortunately, the complete work is available as part of Project Gotenburg.

Lastly, here is another excerpt from the story:

"I couldn't afford to learn it." said the Mock Turtle with a sigh. "I only took the regular course."

"What was that?" inquired Alice.

"Reeling and Writhing, of course, to begin with," the Mock Turtle replied; "and then the different branches of Arithmetic-- Ambition, Distraction, Uglification, and Derision."

"I never heard of Uglification," Alice ventured to say. "What is it?"

The Gryphon lifted up both its paws in surprise. "What! Never heard of uglifying!" it exclaimed. "You know what to beautify is, I suppose?"

What baffles me is, "how on earth do children enjoy this story?" It's really for grown up people who can understand the satire, the logic and the paradox referred to. Now, I really want to meet those kids who like this story and ask them what's interesting in it for them.

Or perhaps, it's the parents who don't understand anything out of it and then think that it might be very funny for their children.

Lambda Calculus and Mathematical Foundations of Programming Languages

[This has been written as informal introduction to Lambda Calculus. If you are a student of Programming Languages, consider a formal introduction instead. Beyond the second para, this post may not be suitable for kids. Rating: PG13.]

Turing Machine is a well known concept in computer science. It's an abstract machine, capable of implementing any computable function. It's impressive because the machine itself is extremely simple, having only a few instructions. But Turing Machine is more like hardware (a machine) and less like a programming language.

Lambda Calculus is a similar concept (that is, you can define any computable function in it) proposed by Alonzo Church in 1930. The difference form Turing Machine is that it is a programming language; an extremely simple one. There are only two constructs: function definition and function application. The functions themselves are anonymous (i.e., no names are given to functions) but the parameters are named.

Since nothing exists other than these two constructs, everything is represented as a function, even natural numbers. For example, the number 0 can be a function that takes a parameter (actually another function) and returns it. The number 1 can be represented by a function that takes a function and applies the given function to a parameter once. The function for the number 2 can apply the given function to the result of applying the same function to an argument. Obviously, the results of computations are also functions.

[Sideline: Though this definition of natural numbers may seem weird but what exactly is a number, say 1? 1 is something which is different from 0 and 2 (and other numbers as well). There is no other definition. I tried to do a search on this claim of mine and found this excellent piece of argument: What is a number? that quotes Bertrand Russell as, "A number is the class of all classes similar to a given class."]


As you can probably guess, much of the power of Lambda Calculus comes from recursion and our ability to think abstractly. Why is lambda calculus important? Firstly, it is extremely mathematical in nature (why is that a desirable property is discussed next). Secondly, it has resulted in the development of functional programming languages like Lisp, ML, Scheme and later Haskell. Why functional programming is important isn't discussed here (see, Von Neumann Bottleneck, a term coined by John Backus in his Turing award lecture in favor of Functional Programming.)

So I said that Mathematical basis is an important property of any programming language. When we think of something, our thought is unbounded. But when we say the same thing, we have to filter out ambiguity and inconsistency from our thought. Next, when we write the same thing, we have to follow some rules of grammar and (due non-interactive nature of discussion and also because of lack of body language) we have to be even more prcise. Inspite of that, natural language is ambiguous. Consider this sentence, "I can't dance." Does this mean you can't dance now or does it mean that you don't know how to dance?

Mathematics is the most precise language we know to describe things. Programming languages that have foundations in Mathematics are more precise and more importantly, we can argue about their properties formally (e.g., we could try to prove that a given program always terminates). Proving properties of non-formal languages is an extremely daunting task.


You can read more about Lambda Calculus and Formal Semantics of Programming Languages, both on Wikipedia. But don't overdo it - if you are a regular programmer, it's important to know that these things are there; learn and use them when you need them. Hopefully never :)

ragamuffin v4.0 aka the jaywalker

Almost a decade ago, a friend asked what the best time (as in age) in a person's life was. I replied, "25." He was surprised that I didn't say childhood. My opinion is that only those kids enjoy their childhood who are boisterous and have the previlige to act rude - they do what pleases them without caring what the elders say. But I was a "nice" kid. And I have always felt that being a kid is very hard; everybody is your boss.

As a teenager I used to think that being 25 would be the most enjoyable part of my life. After all, it's an age when one has finished his education; has a job; owns a car and perhaps even a house of his own, and above all he is independent - he could be a support for his parents!

Today I turn 25. But I have none of these. And after spending my savings, now I am shamelessly spending my father's pension in one of the most expensive countries of the world. My total assets are

• a laptop
  
• a few dozen books
  
• a few dozen CDs+DVDs
  
• 46 USD
  

Happy Birthday to me!

---

Too bad that you couldn't see, see the man that boy could be
There is more than meets the eye
I see the soul that is inside
(Sk8er Boy by Avril Lavigne)

Ensemble

Group Communication is a complex topic. If you ask software developers about it, they will say that it's just making two entities communicate and thus, isn't more difficult than deciding upon a protocol and writing the code. But solid group communication is hard to build and there is considerable theory involved. Take example of a serious chat application where the order of messages as well as failure to receive them is to be taken care of.

First of all, in the presence of message lost, you face the Two Generals' Problem, which says that it's impossible to achieve agreement on a message if arbitrary number of messages can be lost. In the presence of message lost, if you send an acknowledgment for guaranteeing message delivery, the acknowledgement itself may get lost and thus you need to acknowledge the acknowledgement. But then this will continue forever. Thus, Two Generals' Problem is not solvable. You can read in detail here.

Next, in order to achieve fault tolerance, you have to consider Byzantine Faults which are based on Byzantine Generals' Problem (why distributed systems people always think of army and generals is beyond me). Byzantine Faults occur when a faulty node says different things to different nodes - it may say that I have received the message successfully to one node and report the opposite to some other node, causing confusion and inconsistency in the system. Unlike the Two Generals' problem, it's solvable but with some upper bounds on the number of faulty nodes and with lots of communication overhead.

So, we ignore fault tolerance for now. Consider, ordering of messages instead. In a serious chat application the ordering can matter a lot. If different members in a conversation get messages in different order, it can cause confusion. TCP/IP provides ordering within packets of a single message (where packets are formed at lower layers of the network protocol) that is sent via a single TCP/IP socket. But what about different sockets (different members in the conversation) or different messages sent on the same socket? There is nothing in TCP/IP which guarantees that when you send "Hello"; close the socket; open it again and then send "Goodbye", they will be received in the same order. So, what's the solution? Number the messages yourself! And on the receiving end, hold messages if they are received earlier than their predecessors.

Then comes the issue of Group Membership. Does your rock-solid chat application allow a member to join in between a conversation? If yes, what happens when somebody has sent a message but it hasn't been received by all yet, and a new member joins the group. Should he be delivered the message or should it be held back? If you deliver the message to him as well, some of the members (who received the message before the new member joined) will think that he didn't get that message, while others will think the opposite. More confusion and inconsistency.

Some of you might think that considering all these issues is an overkill for a chat application. What about a distributed group of servers trying to synchronize their end-of-day activity?


As I said in the beginning, there is more to group communication than we casually think of. Ensemble is a library written in Objective Caml that handles most of the theoretical issues involved with Group Communication. It provides simple to use api for Java, C, C# and ML. It's highly modular and reconfigurable. Do check out the features it provides if you are interested in group communication. You can get an idea of the research involved with this library by looking at the list of publications.