A Few Easy Ones from Raymond Smullyan Many of you are familiar with the canonical ‘liar and truth teller’ puzzle. Raymond Smullyan is a logician who has taken the basic idea and expanded it to produce an immense variety of challenging puzzles. He has even used variations on the theme to illustrate Incompleteness Theory and other logic esoterica.

Here are a few easy ones to give you a taste of his sumptuous banquet:

Dr. Tarr is a psychologist with the Department of Health. Her job is to inspect asylums to determine whether they are in compliance with the law. Asylums have Doctors and Patients. In a compliant asylum, all the doctors are sane and all the patients are insane. Clearly, an asylum with an insane doctor or a sane patient is Not A Good Thing.

Sane persons are correct in all of their beliefs. Insane persons are incorrect in all of their beliefs. Both sane and insane persons are scrupulously honest: they always state what they believe to be the case. Unfortunately, the asylums are very modern and do not use identifying devices such as uniforms, ID tags, or other devices to show which persons are doctors and which are patients. Nor is it possible to know whether a person is sane or insane by any means other than questioning them.

One day, after inspecting a number of asylums, Dr. Tarr was having a drink and cigar with her good friend Professor Feather. The professor found her work interesting and asked her to recount some of her findings.

“Well,” said Dr. Tarr, “at the first asylum I visited, I met an inhabitant who made a single statement. I immediately took steps to have them released.”

“Wait,” interjected the professor, “so you’re saying this person was not an insane patient?”

“Of course,” replied Dr. Tarr.

Professor Feather thought for a moment, then asked “How is that possible? This sounds like the old Liar and Truth Teller puzzle. This person either told the truth or they lied. But there are four possibilities for any person in an asylum: Sane Doctor, Insane Patient, Insane Doctor, or Sane Patient.

“Even if you knew whether they were lying or telling the truth, that would only narrow the matter down to two possibilities. For example, if they told a truth such as ‘two plus two equals four’, you would know that they were Sane. But how would you know that they were a Patient, not a Doctor?”

Dr. Tarr replied with a chuckle “I agree that I could not have deduced what to do based on an inhabitant saying ‘two plus two equals four’. But in this case, the patient was quite intelligent and thought of a single statement which could establish the fact that only a Sane Patient could make that statement.

“I’m sure if you think about it, you could construct such a statement. Name a statement which could only be uttered by a Sane Patient.”

…

Dr. Tarr and Professor Feather shared a chuckle over that one. Then the professor took a more serious tone. “But have you ever had to remove a Doctor from an asylum?”

“Yes,” said Dr. Tarr sadly, “it has happened. Doctors do go insane once in a while. Recently I had just such a case. As it happened, I was visiting an asylum for the very first time and the first inhabitant I met made a single statement. I immediately had the inhabitant transferred to a special institution for former Doctors.”

“Don’t say it!” exclaimed the professor, “I want to work it out for myself…”

…

“Another time,” continued Dr. Tarr, “I was visiting an asylum which had been placed on probation for irregularities such as Insane Doctors and Sane Patients. I asked an inhabitant ‘Are you a patient’, and she said ‘yes’.”

“What did you do next?” asked Professor Feather. “Did you need to do any more investigating?”

…

“I’m glad you worked that out. Another asylum was on probation and I decided to ask the very same question of the first inhabitant I met. This time, when I asked ‘Are you a patient,’ he replied ‘I believe so…’.” Do you think I knew enough to close the asylum?

Professor Feather thought about this one for a very long time.  ¶ 5:00 AM 2 comments

  Off Topic: 1977 was an interesting year I often think back to 1977. It seemed like such an amazing year to me at the time. In retrospect, that isn’t really surprising, because in 1977 I turned fifteen and fifteen year-olds have a large capacity for amazement and wonder.

I just ran across another interesting thing from 1977, a speech by then-President of the United States, Jimmy Carter:

Tonight I want to have an unpleasant talk with you about a problem unprecedented in our history. With the exception of preventing war, this is the greatest challenge our country will face during our lifetimes. The energy crisis has not yet overwhelmed us, but it will if we do not act quickly.

It is a problem we will not solve in the next few years, and it is likely to get progressively worse through the rest of this century.

We must not be selfish or timid if we hope to have a decent world for our children and grandchildren.

We simply must balance our demand for energy with our rapidly shrinking resources. By acting now, we can control our future instead of letting the future control us.



Two days from now, I will present my energy proposals to the Congress. Its members will be my partners and they have already given me a great deal of valuable advice. Many of these proposals will be unpopular. Some will cause you to put up with inconveniences and to make sacrifices.

The most important thing about these proposals is that the alternative may be a national catastrophe. Further delay can affect our strength and our power as a nation.

Our decision about energy will test the character of the American people and the ability of the President and the Congress to govern. This difficult effort will be the “moral equivalent of war” — except that we will be uniting our efforts to build and not destroy.

I know that some of you may doubt that we face real energy shortages. The 1973 gasoline lines are gone, and our homes are warm again. But our energy problem is worse tonight than it was in 1973 or a few weeks ago in the dead of winter. It is worse because more waste has occurred, and more time has passed by without our planning for the future. And it will get worse every day until we act.

The oil and natural gas we rely on for 75 percent of our energy are running out. In spite of increased effort, domestic production has been dropping steadily at about six percent a year. Imports have doubled in the last five years. Our nation’s independence of economic and political action is becoming increasingly constrained. Unless profound changes are made to lower oil consumption, we now believe that early in the 1980s the world will be demanding more oil that it can produce.

The world now uses about 60 million barrels of oil a day and demand increases each year about 5 percent. This means that just to stay even we need the production of a new Texas every year, an Alaskan North Slope every nine months, or a new Saudi Arabia every three years. Obviously, this cannot continue.

We must look back in history to understand our energy problem. Twice in the last several hundred years there has been a transition in the way people use energy.

The first was about 200 years ago, away from wood — which had provided about 90 percent of all fuel — to coal, which was more efficient. This change became the basis of the Industrial Revolution.

The second change took place in this century, with the growing use of oil and natural gas. They were more convenient and cheaper than coal, and the supply seemed to be almost without limit. They made possible the age of automobile and airplane travel. Nearly everyone who is alive today grew up during this age and we have never known anything different.

Because we are now running out of gas and oil, we must prepare quickly for a third change, to strict conservation and to the use of coal and permanent renewable energy sources, like solar power.

The world has not prepared for the future. During the 1950s, people used twice as much oil as during the 1940s. During the 1960s, we used twice as much as during the 1950s. And in each of those decades, more oil was consumed than in all of mankind’s previous history.

World consumption of oil is still going up. If it were possible to keep it rising during the 1970s and 1980s by 5 percent a year as it has in the past, we could use up all the proven reserves of oil in the entire world by the end of the next decade.

I know that many of you have suspected that some supplies of oil and gas are being withheld. You may be right, but suspicions about oil companies cannot change the fact that we are running out of petroleum.

All of us have heard about the large oil fields on Alaska’s North Slope. In a few years when the North Slope is producing fully, its total output will be just about equal to two years’ increase in our nation’s energy demand.

Each new inventory of world oil reserves has been more disturbing than the last. World oil production can probably keep going up for another six or eight years. But some time in the 1980s it can’t go up much more. Demand will overtake production. We have no choice about that.

But we do have a choice about how we will spend the next few years. Each American uses the energy equivalent of 60 barrels of oil per person each year. Ours is the most wasteful nation on earth. We waste more energy than we import. With about the same standard of living, we use twice as much energy per person as do other countries like Germany, Japan and Sweden.

One choice is to continue doing what we have been doing before. We can drift along for a few more years.

Our consumption of oil would keep going up every year. Our cars would continue to be too large and inefficient. Three-quarters of them would continue to carry only one person — the driver — while our public transportation system continues to decline. We can delay insulating our houses, and they will continue to lose about 50 percent of their heat in waste.

We can continue using scarce oil and natural to generate electricity, and continue wasting two-thirds of their fuel value in the process.

If we do not act, then by 1985 we will be using 33 percent more energy than we do today.

We can’t substantially increase our domestic production, so we would need to import twice as much oil as we do now. Supplies will be uncertain. The cost will keep going up. Six years ago, we paid $3.7 billion for imported oil. Last year we spent $37 billion — nearly ten times as much — and this year we may spend over $45 billion.

Unless we act, we will spend more than $550 billion for imported oil by 1985 — more than $2,500 a year for every man, woman, and child in America. Along with that money we will continue losing American jobs and becoming increasingly vulnerable to supply interruptions.

Now we have a choice. But if we wait, we will live in fear of embargoes. We could endanger our freedom as a sovereign nation to act in foreign affairs. Within ten years we would not be able to import enough oil — from any country, at any acceptable price.

If we wait, and do not act, then our factories will not be able to keep our people on the job with reduced supplies of fuel. Too few of our utilities will have switched to coal, our most abundant energy source.

We will not be ready to keep our transportation system running with smaller, more efficient cars and a better network of buses, trains and public transportation.

We will feel mounting pressure to plunder the environment. We will have a crash program to build more nuclear plants, strip-mine and burn more coal, and drill more offshore wells than we will need if we begin to conserve now. Inflation will soar, production will go down, people will lose their jobs. Intense competition will build up among nations and among the different regions within our own country.

If we fail to act soon, we will face an economic, social and political crisis that will threaten our free institutions.

But we still have another choice. We can begin to prepare right now. We can decide to act while there is time.

That is the concept of the energy policy we will present on Wednesday. Our national energy plan is based on ten fundamental principles.

The first principle is that we can have an effective and comprehensive energy policy only if the government takes responsibility for it and if the people understand the seriousness of the challenge and are willing to make sacrifices.

The second principle is that healthy economic growth must continue. Only by saving energy can we maintain our standard of living and keep our people at work. An effective conservation program will create hundreds of thousands of new jobs.

The third principle is that we must protect the environment. Our energy problems have the same cause as our environmental problems — wasteful use of resources. Conservation helps us solve both at once.

The fourth principle is that we must reduce our vulnerability to potentially devastating embargoes. We can protect ourselves from uncertain supplies by reducing our demand for oil, making the most of our abundant resources such as coal, and developing a strategic petroleum reserve.

The fifth principle is that we must be fair. Our solutions must ask equal sacrifices from every region, every class of people, every interest group. Industry will have to do its part to conserve, just as the consumers will. The energy producers deserve fair treatment, but we will not let the oil companies profiteer.

The sixth principle, and the cornerstone of our policy, is to reduce the demand through conservation. Our emphasis on conservation is a clear difference between this plan and others which merely encouraged crash production efforts. Conservation is the quickest, cheapest, most practical source of energy. Conservation is the only way we can buy a barrel of oil for a few dollars. It costs about $13 to waste it.

The seventh principle is that prices should generally reflect the true replacement costs of energy. We are only cheating ourselves if we make energy artificially cheap and use more than we can really afford.

The eighth principle is that government policies must be predictable and certain. Both consumers and producers need policies they can count on so they can plan ahead. This is one reason I am working with the Congress to create a new Department of Energy, to replace more than 50 different agencies that now have some control over energy.

The ninth principle is that we must conserve the fuels that are scarcest and make the most of those that are more plentiful. We can’t continue to use oil and gas for 75 percent of our consumption when they make up seven percent of our domestic reserves. We need to shift to plentiful coal while taking care to protect the environment, and to apply stricter safety standards to nuclear energy.

The tenth principle is that we must start now to develop the new, unconventional sources of energy we will rely on in the next century.

These ten principles have guided the development of the policy I would describe to you and the Congress on Wednesday.

Our energy plan will also include a number of specific goals, to measure our progress toward a stable energy system.

These are the goals we set for 1985:

—Reduce the annual growth rate in our energy demand to less than two percent.

—Reduce gasoline consumption by ten percent below its current level.

—Cut in half the portion of United States oil which is imported, from a potential level of 16 million barrels to six million barrels a day.

—Establish a strategic petroleum reserve of one billion barrels, more than six months’ supply.

—Increase our coal production by about two thirds to more than 1 billion tons a year.

—Insulate 90 percent of American homes and all new buildings.

—Use solar energy in more than two and one-half million houses.

We will monitor our progress toward these goals year by year. Our plan will call for stricter conservation measures if we fall behind.

I cant tell you that these measures will be easy, nor will they be popular. But I think most of you realize that a policy which does not ask for changes or sacrifices would not be an effective policy.

This plan is essential to protect our jobs, our environment, our standard of living, and our future.

Whether this plan truly makes a difference will be decided not here in Washington, but in every town and every factory, in every home an don every highway and every farm.

I believe this can be a positive challenge. There is something especially American in the kinds of changes we have to make. We have been proud, through our history of being efficient people.

We have been proud of our leadership in the world. Now we have a chance again to give the world a positive example.

And we have been proud of our vision of the future. We have always wanted to give our children and grandchildren a world richer in possibilities than we’ve had. They are the ones we must provide for now. They are the ones who will suffer most if we don’t act.

I’ve given you some of the principles of the plan.

I am sure each of you will find something you don’t like about the specifics of our proposal. It will demand that we make sacrifices and changes in our lives. To some degree, the sacrifices will be painful — but so is any meaningful sacrifice. It will lead to some higher costs, and to some greater inconveniences for everyone.

But the sacrifices will be gradual, realistic and necessary. Above all, they will be fair. No one will gain an unfair advantage through this plan. No one will be asked to bear an unfair burden. We will monitor the accuracy of data from the oil and natural gas companies, so that we will know their true production, supplies, reserves, and profits.

The citizens who insist on driving large, unnecessarily powerful cars must expect to pay more for that luxury.

We can be sure that all the special interest groups in the country will attack the part of this plan that affects them directly. They will say that sacrifice is fine, as long as other people do it, but that their sacrifice is unreasonable, or unfair, or harmful to the country. If they succeed, then the burden on the ordinary citizen, who is not organized into an interest group, would be crushing.

There should be only one test for this program: whether it will help our country.

Other generation of Americans have faced and mastered great challenges. I have faith that meeting this challenge will make our own lives even richer. If you will join me so that we can work together with patriotism and courage, we will again prove that our great nation can lead the world into an age of peace, independence and freedom.

  ¶ 1:19 PM 5 comments

  The Narcissism of Small Code Differences

def formatted_zip_code(digits)
  case digits.size 
  when 4 then "0#{digits}" 
  when 3 then "00#{digits}" 
  else digits 
  end
end

This code reads pretty much as the author would have explained how to handle the “digits” variable: If it only has four digits, pre-pend it with a zero. If it only has three digits, prepend it with two zeros. Simple and to the point and move on. Save the clever code for something that matters.

The author of this code was an Agnostic. He didn’t mind using a case statement instead of if-elsif-elsif, he paid attention to the features of his chosen programming language, but he didn’t have strong convictions about there being One True Way to express every set of choices.

His code “Just Worked.”

Donning The Hair Shirt

The Agnostic’s code carried on, quietly working, until one day another programmer chanced upon it. Our second programmer was an Ascetic. Ascetics believe in code that can do powerful things with a small set of core axioms, like recursion and first-class functions.

The Ascetic spotted a bug: What if “digits” only had two digits? The objective of the code was clearly to have at least five digits, with leading zeros. The Ascetic cracked his knuckles and went to work.

Given his favourite library function:

def y(&f)
    lambda { |x| x[x] } [ 
        lambda { |yf| lambda { |*args| f[yf[yf]][*args] } } ]
end

He rewrote the Agnostic’s code as:

def formatted_zip_code(digits)
  y { |rec|
    lambda { |str| 
      str =~ /....(.)+/ && str || rec["0#{str}"] } }[digits]
end

And all was well for a short time.

Toiling in the Stacks

The Ascetic checked his code in, where another programmer, a Librarian, reviewed it. She saw immediately that it could and should be re-written:

def formatted_zip_code(digits)
  digits.rjust(5,'0')
end

Librarians believe that there is a library for everything, and good languages have huge libraries providing lots of built-in functionality. Programming is the art of searching the libraries for the one magic incantation that does exactly what you want.

And for a short time, all continued to be well.

Purity of Essence

One day, management hired a senior programmer with much experience working in the bowels of BigCo. He was brought in to provide “Adult Supervision” for the programming team. He went right to work, reviewing the code base and compiling a list of sins against his religious convictions. He was an OO Purist.

I am told that a cathedral built by Purists is beautiful to behold, constructed lovingly of small bricks, no more than 50 lines per class, no more than 10 classes per package, no more than two instance variables per class, no more than one level of indentation per method, no more than one dot per line, and absolutely no else clauses.

The Purist considered ifs, cases, and even shortcut booleans to be deficiencies in code, places where the proper approach—and indeed to only approach—is to use polymorphism and dependent types.

The Purist seized upon the twice-rewritten code as an opportunity to show how such a thing ought to be written:

def formatted_zip_code(digits)
  ZipCodeDigitFactory.new(digits).to_formatted_string
end

Alas, space does not permit me to show you all of the subclasses of Digits he composed, one for each possible length of string. For example:

class FourZipCodeDigits < BaseZipCodeDigits
  def to_formatted_string
    "0#{self.to_s}"
  end
end

I have also omitted his ZipCodeFactory that would take a normal string and figure out which particular subclass of BaseZipCodeDigits to construct.

(I am told that a cathedral built by Purists is beautiful to behold, constructed lovingly of small bricks, no more than 50 lines per class, no more than 10 classes per package, no more than two instance variables per class, no more than one level of indentation per method, no more than one dot per line, and absolutely no else clauses.)

Of course, the Librarian, Ascetic and the Purist hated each other with a passion fueled by the narcissism of small differences into a raging fire of religious cleansing. Much politicking and fighting broke out over the code.

Meanwhile, the Agnostic carried on, quietly coding while the others bickered over how to properly rewrite what he would write. One day, he noticed that some unit tests were failing and raised the issue in Campfire.

The Return of the Agnostic

“Hey,” he asked, “What happened to that piece of code? It was for zip codes, it was only supposed to pre-pend one or two zeros when importing zip codes from CSV files. Anything with fewer than three digits is supposed to be an invalid code. Empty strings shouldn’t be converted to five zeros, as far as I know.”

“What’s up with that?”

The Librarian, Ascetic, and Purist were silent for a moment, and then immediately resumed arguing, this time over whether #rjust should have another parameter, whether the regular expression in a recursive routine should be changed, or whether the simplest thing was to simply change the method for the EmptyDigits, OneDigit, and TwoDigits classes.

The Agnostic listened for a moment, tried to interject a few times, then sighed and reached for his text editor.

---

Update: Reviewing the comments made elsewhere, I see that this post fell into the Fizzbuzz Trap: By quoting a programming problem—no matter how banal and contrived—the article was bound to provoke a huge amount of dicussion around the correct way to solve the problem, while ignoring the point of the post. This is my fault, I should have known better than to post a snippet of code. As many of you have noted, the post is not about the Agnostic or his code, it’s about the dynamic of programmers eager to rewrite code in their own image, and the hypothesis that our (I am equally guilty of this behaviour) motivation for doing so is to emphasize the small differences between ourselves and others.

For no matter how good or bad the Agnostic’s code is, why did the Librarian rewrite the Ascetic’s code? Why did the Purist rewrite it again? When they discovered that the Agnostic’s code actually met some requirement, why weren’t they talking about documentation, or the process around tests? Why were they all—includingteh agnostic—eager to rewrite it one more time?

Seriously, the post is not about whether the Agnostic should have documented his code, or where the zip code validation should live. However, I should have known that the moment I included a piece of code to provide local colour, the resulting debate over its fitness was inevitable.  ¶ 11:31 AM 38 comments

  Show, Don't Tell Jeff Atwood is so right, I practically shouted “Slamma-lamma-ding-dong” when I read this line:

So what, then, are the alternatives to XML? One popular choice is YAML. I could explain it, but it's easier to show you. Which, I think, is entirely the point.

Now, I don’t mean, “Jeff Atwood is right that YAML is better than XML.” Well, I believe it is better than XML for a lot of things, but which things and how often and he didn’t exactly say that any ways.

What I actually mean is that Jeff is absolutely right that some things should not be explained, they should be directly experienced. It’s better to show them than to try to explain them.

Things that involve changes to human behaviour do not lend themselves to explanation. You have to try things. Or observe people trying things. Trying to explain it just doesn’t work, even though we humans have a huge and futile desire to try—including writing weblogs just like this.

Think about user interfaces. Imagine yourself traveling back in time to the eighties—last century!—and trying to “explain” Excel to someone who was a master of Lotus 1-2-3. They have seen a mouse in the computer store—it came with its own card and you configured jumpers to set the interrupt so it wouldn’t conflict with their extended memory.

Now you are going to explain why they will be more productive pushing a plastic bar of soap around their desk instead of banging out slash commands at high speed? Are you crazy?

The only way this person will consider Excel is if you show them Excel. And I speak as a man who was there. At one time, Excel was so good that people would switch from their PCs with 1-2-3 to Excel on a Macintosh just to get Excel. Until, for some mysterious reason, Microsoft brought out Excel on Windows and the Windows version could use 8MB of RAM while the Macintosh version was limited to 1MB of RAM. Dunno why.

Or how about software development. What do you mean releasing software every two weeks or every month? It takes three to four months just to plan a release around here! And hey, that “better search” thingie you were droning on and on about? How much better can searching the Internet really be? Why would anyone care?

But when people see iterative development in action, when people use the Internet, and when people watch Google’s stock price… they get it, immediately.

The interesting thing is this: things that are easy to explain are things that fit with our incomplete and wrong mental models of how the world works. We have built a whole UI industry around trying to match our guesses of how people think, like imagining that an icon of a pair of scissors will tell people that clicking there will cause whatever they have selected to vanish and be held in some invisible suspension, waiting for them to click the icon that looks like a bottle of Kindergarten glue.

Whereas things that break those models are impossible to explain, because they aren’t just like whatever we already believe. So? So those are the things that have a shot at doing something new, at disrupting our behaviour. Like making CRUD web applications easy to build or a mobile web browser that doesn’t suck.

You recall that Apple—know know a thing or two about disrupting human behaviour—introduced the iPhone with advertisements that simply showed them in action. I wonder why?

I am going to stop trying to explain that you should not try to explain some things to people. You don’t have to trust my word on the subject: Open your eyes and observe for yourself. When things involve human behaviour, it’s better to show than to tell.  ¶ 10:05 AM 10 comments