Monday, March 26, 2007

Crocodiles in denial!

http://www.cbc.ca/cp/Oddities/070326/K032606AU.html

JERUSALEM (AP) - A woman with three crocodiles strapped to her waist was stopped at the Gaza-Egypt border crossing after guards noticed that she looked "strangely fat," officials said Monday.

The woman's shape raised suspicions at the Rafah terminal in southern Gaza, and a body search by a female border guard turned up the animals, each about 50 centimetres long, concealed underneath her loose robe, according to Maria Telleria, spokeswoman for the European observers who run the crossing.

"The woman looked strangely fat. Even though she was veiled and covered, even with so many clothes on there was something strange," Telleria said.

The incident, which took place on Thursday, sparked panic at the crossing.

"The policewoman screamed and ran out of the room, and then women began screaming and panicking when they heard," Telleria said. But when the hysteria died down, she said, "everybody was admiring a woman who is able to tie crocodiles to her body."

In her defence, the woman said she "was asked" to carry the crocodiles, said Wael Dahab, a spokesman for the Palestinian guards at the crossing.

The reptiles, which had their jaws tied shut with string, were returned to the Egyptian side of the border.

Dahab said the animals were likely meant for sale to Gaza's small zoo or to private owners. The crocodiles would fetch "good money," even in the impoverished territory, he said. In Gaza, the animals can fetch about C$580 - roughly two months' salary for a low-ranking policeman.

The woman was not the first to try to smuggle exotic wildlife through the Rafah crossing, Dahab said: Another woman tried to bring in a monkey tied to her chest, and other travellers tried to smuggle in exotic birds and a tiger cub. Border guards more frequently confiscate cigarettes, prescription drugs and car parts.

The crossing is the only way in and out of Gaza for residents of the crowded coastal strip.

Since Israel pulled out of Gaza in 2005, the crossing has been subject to a complex system of control: Egypt and the Palestinians are responsible for the crossing, with European monitors are stationed at the terminal and Israeli inspectors watch from a distance over closed-circuit TV.

Israel retains final say over whether the crossing can open, and has kept it closed over 80 per cent of the time since an Israeli soldier was captured by Hamas-linked militants in Gaza nine months ago, charging that the crossing is being used to smuggle money and weapons to militants.

Thursday, March 22, 2007

Web 2.0 in A Nutshell

Monday, March 19, 2007

"You need the willingness to fail all the time"

http://www.nytimes.com/2007/03/20/business/20backus.html?hp

John W. Backus, who assembled and led the I.B.M. team that created Fortran, the first widely used programming language, which helped open the door to modern computing, died on Saturday at his home in Ashland, Ore. He was 82.

His daughter Karen Backus announced the death, saying the family did not know the cause, other than age.

Fortran, released in 1957, was “the turning point” in computer software, much as the microprocessor was a giant step forward in hardware, according to J.A.N. Lee, a leading computer historian.

Fortran changed the terms of communication between humans and computers, moving up a level to a language that was more comprehensible by humans. So Fortran, in computing vernacular, is considered the first successful higher-level language.

Mr. Backus and his youthful team, then all in their 20s and 30s, devised a programming language that resembled a combination of English shorthand and algebra. Fortran, short for Formula Translator, was very similar to the algebraic formulas that scientists and engineers used in their daily work. With some training, they were no longer dependent on a programming priesthood to translate their science and engineering problems into a language a computer would understand.

In an interview several years ago, Ken Thompson, who developed the Unix operating system at Bell Labs in 1969, observed that “95 percent of the people who programmed in the early years would never have done it without Fortran.”

He added: “It was a massive step.”

Fortran was also extremely efficient, running as fast as programs painstakingly hand-coded by the programming elite, who worked in arcane machine languages. This was a feat considered impossible before Fortran. It was achieved by the masterful design of the Fortran compiler, a program that captures the human intent of a program and recasts it in a way that a computer can process.

In the Fortran project, Mr. Backus tackled two fundamental problems in computing — how to make programming easier for humans, and how to structure the underlying code to make that possible. Mr. Backus continued to work on those challenges for much of his career, and he encouraged others as well.

“His contribution was immense, and it influenced the work of many, including me,” Frances Allen, a retired research fellow at I.B.M., said yesterday.

Mr. Backus was a bit of a maverick even as a teenager. He grew up in an affluent family in Wilmington, Del., the son of a stockbroker. He had a complicated, difficult relationship with his family, and he was a wayward student.

In a series of interviews in 2000 and 2001 in San Francisco, where he lived at the time, Mr. Backus recalled that his family had sent him to an exclusive private high school, the Hill School in Pennsylvania.

“The delight of that place was all the rules you could break,” he recalled.

After flunking out of the University of Virginia, Mr. Backus was drafted in 1943. But his scores on Army aptitude tests were so high that he was dispatched on government-financed programs to three universities, with his studies ranging from engineering to medicine.

After the war, Mr. Backus found his footing as a student at Columbia University and pursued an interest in mathematics, receiving his master’s degree in 1950. Shortly before he graduated, Mr. Backus wandered by the I.B.M. headquarters on Madison Avenue in New York, where one of its room-size electronic calculators was on display.

When a tour guide inquired, Mr. Backus mentioned that he was a graduate student in math; he was whisked upstairs and asked a series of questions Mr. Backus described as math “brain teasers.” It was an informal oral exam, with no recorded score.

He was hired on the spot. As what? “As a programmer,” Mr. Backus replied, shrugging. “That was the way it was done in those days.”

Back then, there was no field of computer science, no courses or schools. The first written reference to “software” as a computer term, as something distinct from hardware, did not come until 1958.

In 1953, frustrated by his experience of “hand-to-hand combat with the machine,” Mr. Backus was eager to somehow simplify programming. He wrote a brief note to his superior, asking to be allowed to head a research project with that goal. “I figured there had to be a better way,” he said.

Mr. Backus got approval and began hiring, one by one, until the team reached 10. It was an eclectic bunch that included a crystallographer, a cryptographer, a chess wizard, an employee on loan from United Aircraft, a researcher from the Massachusetts Institute of Technology and a young woman who joined the project straight out of Vassar College.

“They took anyone who seemed to have an aptitude for problem-solving skills — bridge players, chess players, even women,” Lois Haibt, the Vassar graduate, recalled in an interview in 2000.

Mr. Backus, colleagues said, managed the research team with a light hand. The hours were long but informal. Snowball fights relieved lengthy days of work in winter. I.B.M. had a system of rigid yearly performance reviews, which Mr. Backus deemed ill-suited for his programmers, so he ignored it. “We were the hackers of those days,” Richard Goldberg, a member of the Fortran team, recalled in an interview in 2000.

After Fortran, Mr. Backus developed, with Peter Naur, a Danish computer scientist, a notation for describing the structure of programming languages, much like grammar for natural languages. It became known as Backus-Naur form.

Later, Mr. Backus worked for years with a group at I.B.M. in an area called functional programming. The notion, Mr. Backus said, was to develop a system of programming that would focus more on describing the problem a person wanted the computer to solve and less on giving the computer step-by-step instructions.

“That field owes a lot to John Backus and his early efforts to promote it,” said Alex Aiken, a former researcher at I.B.M. who is now a professor at Stanford University.

In addition to his daughter Karen, of New York, Mr. Backus is survived by another daughter, Paula Backus, of Ashland, Ore.; and a brother, Cecil Backus, of Easton, Md.

His second wife, Barbara Stannard, died in 2004. His first marriage, to Marjorie Jamison, ended in divorce.

It was Mr. Backus who set the tone for the Fortran team. Yet if the style was informal, the work was intense, a four-year venture with no guarantee of success and many small setbacks along the way.

Innovation, Mr. Backus said, was a constant process of trial and error.

“You need the willingness to fail all the time,” he said. “You have to generate many ideas and then you have to work very hard only to discover that they don’t work. And you keep doing that over and over until you find one that does work.”

Saturday, March 17, 2007

Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

Freaky! It makes me afraid of writing any code...

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html



I remember vividly Jon Bentley's first Algorithms lecture at CMU, where he asked all of us incoming Ph.D. students to write a binary search, and then dissected one of our implementations in front of the class. Of course it was broken, as were most of our implementations. This made a real impression on me, as did the treatment of this material in his wonderful Programming Pearls (Addison-Wesley, 1986; Second Edition, 2000). The key lesson was to carefully consider the invariants in your programs.

Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what it is, you will understand why it escaped detection for two decades. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.

So what's the bug? Here's a standard binary search, in Java. (It's one that I wrote for the java.util.Arrays):

1:     public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal < key)
10: low = mid + 1;
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }

The bug is in this line:
 6:             int mid =(low + high) / 2;

In Programming Pearls Bentley says that the analogous line "sets m to the average of l and u, truncated down to the nearest integer." On the face of it, this assertion might appear correct, but it fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231 - 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException.

This bug can manifest itself for arrays whose length (in elements) is 230 or greater (roughly a billion elements). This was inconceivable back in the '80s, when Programming Pearls was written, but it is common these days at Google and other places. In Programming Pearls, Bentley says "While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962." The truth is, very few correct versions have ever been published, at least in mainstream programming languages.

So what's the best way to fix the bug? Here's one way:
 6:             int mid = low + ((high - low) / 2);

Probably faster, and arguably as clear is:
 6:             int mid = (low + high) >>> 1;

In C and C++ (where you don't have the >>> operator), you can do this:
 6:             mid = ((unsigned) (low + high)) >> 1;

And now we know the binary search is bug-free, right? Well, we strongly suspect so, but we don't know. It is not sufficient merely to prove a program correct; you have to test it too. Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible. With concurrent programs, it's even worse: You have to test for all internal states, which is, for all practical purposes, impossible.

The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms. If you have any code that implements one of these algorithms, fix it now before it blows up. The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code.

We programmers need all the help we can get, and we should never assume otherwise. Careful design is great. Testing is great. Formal methods are great. Code reviews are great. Static analysis is great. But none of these things alone are sufficient to eliminate bugs: They will always be with us. A bug can exist for half a century despite our best efforts to exterminate it. We must program carefully, defensively, and remain ever vigilant.

Monday, March 05, 2007

Tough Life


Saturday, March 03, 2007

Math Genius Two