Monday, July 18, 2011

Programming Languages, Compilers, and Pigeons

Machine language is a set of instructions that specifies the lowest level of computer operations, such as moving data around or adding two numbers. Luckily, modern programming languages hide this low-level complexity from programmers, allowing the programmers to work with a higher level language. A compiler is a program that translates the high level language into machine language.

Ann had always wondered about the intelligence of pigeons. They appeared nearly brainless as they paced her window sill, bobbing their heads. She could never believe that they were smart enough to comprise the core of the kingdom’s pigeon carrier communication network. However, it was not until the summer after her tenth birthday that Ann learned the frustration of working with these birds.

The true difficulty of working with pigeons consisted of trying to give orders. The pigeons only understood a simple set of ultra-low level instructions, called the Binary Instruction and Reference Directives Set (or BIRDS for short). This instruction set contained such commands as “Fly X meters” and “Turn Y degrees”. It completely lacked any high level concepts at all.

To make matters worse, a pigeon could only keep two values in its head at the same time -- one in each side of its brain. This led to complex sequences of instructions, such as: “Store the value 10 in X. Fly X meters.” Every value had to be moved into either the left half of the brain (X) or the right half (Y) before it could be used. Not only did you have to work with these low-level instruction, but you also had to worry about where to put the values for those instructions.

As a result, an instruction such as “Fly to Perth” became a series of 113 instructions measured in meters and degrees. Half of these instructions simply moved data into one of the available slots. A mistake in any one of the instructions could send the pigeon to the wrong city.

In order to form an efficient pigeon communications network, the kingdom's head pigeon master employed hundreds of skilled compilers. These compilers would work day and night translating scrawled instructions from the king's servants into precise BIRDS code. It was a job that took years of training and an obsessive attention to detail.

Thus, it greatly shocked both Ann and the castle’s pigeon master when King Fredrick insisted that Ann learn the skill. Shortly after Ann’s tenth birthday, King Fredrick commanded the pigeon master to spend the summer tutoring Ann in the art of compiling pigeon instructions by hand. Both Ann and the pigeon master assumed that they were being punished.

“I don't understand why I am doing this,” protested Ann after her father left. The pigeon master nodded in agreement, but he was wise enough not to question the king.

“Learning to compile pigeon instructions is an important skill,” commented the pigeon master. “Its value should not be underestimated. Pigeon code is at the heart of the kingdom's entire communication network. The network carries reports from all territories, messages from advisors, and the king’s own commands. You could say that the fate of the kingdom depends on the correct and efficient compilation of BIRDS instructions!” The pigeon master obviously felt passionate about his job.

“But it is so boring,” Ann objected. “Why can't you simply tell the pigeon to fly to Paris, retrieve a message, and come home.”

The pigeon master sighed. He had been over this already. “How does the pigeon know where Paris is? And how does it know what message to pick up? And how does it know how to get back? You have to tell the pigeon exactly what to do. Otherwise it will just look at you blankly and bob its head.”

“I am telling it 'Go to Paris.' That should be enough.” argued Ann.

“It would be enough IF the pigeon had some internal concept of 'going to paris'. But, most unfortunately, that is not one of the skills with which a pigeon is born.”

“Why not?” asked Ann.

The pigeon master looked shocked, as though he could not believe the question. “I do not get to control the knowledge with which pigeons are born,” he finally answered. “I only train the pigeons.”

“You could teach them about Paris,” Ann suggested. “I learned about Paris in school when I was five.”

“What if you wanted the pigeon to go to Atlantis? Or North Saskatoon? Should the pigeons memorize every possible path?” questioned the pigeon master.

“I guess that would be a little much,” agreed Ann. “Especially for birds that can only remember two things at a time. They do not seem up to that sort of challenge.”

“Exactly,” agreed the pigeon master. “The BIRDS code provides a minimal set of instructions that every pigeon knows. It is a building block that can be used to create arbitrarily more complex programs. However, the king and his advisors do not write in BIRDS code. They write in higher level concepts, such as 'Fly to Perth'. As compilers, our job is to transform these high level concepts into simple instructions that a pigeon can understand.”

He put the BIRDS manual in front of Ann and showed her how to translate a simple flight around the castle. Each seemingly simple instruction morphed into a list of agonizingly low-level details. Move this data here, then use it to compute this turn here. Ann struggled to keep the relevant context in her head.

Ann studied each of the BIRDS instructions, trying to memorize them all. The instructions themselves were simple. However, using them to efficiently perform a desired task was an art form.

After a few hours, the pigeon master told her that she was done for the day. As Ann stood up to leave, she thought of another question.

“Don't you ever wish that pigeons were smart enough to just understand what you mean to say?” she asked.

The pigeon master gave a long sigh. “Every single day,” he replied sadly.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.