Friday, February 1, 2008

Boolean Confusion

A big part of learning to program is building up effective mental models for how various logical structures work. A big part of learning to teach programming is learning how to diagnose broken or ineffective mental models by reading someone's code. One common confusion that shows up very clearly in the code of novice programmers is thinking of booleans and control expressions as being somehow two separate things.

By “control expressions”, I mean the expressions that are used in if-statements and while-loops. For example, in

   while (i < 100) {
      ...
   }
the control expression is “i < 100”. Of course, the value of the control expression is a boolean. Novices can even tell you that, but they haven't quite internalized it yet.

Suppose you wanted a function to test whether an integer is positive. An experienced programmer might write

   boolean isPositive(int n) {
      return n > 0;
   }
but a novice programmer would be more likely to write
   boolean isPositive(int n) {
      if (n > 0) {
         return true;
      }
      else {
         return false;
      }
   }
Why? Because the function is supposed to return a boolean, but the novice doesn't quite believe that n > 0 is a boolean—it's a control expression!

On the flip side, suppose you have a loop being controlled by a boolean variable named flag. An experienced programmer might write

   while (flag) {
      ...
   }
but a novice programmer would be more likely to write
   while (flag == true) {
      ...
   }
Why? Because the while-loop needs a control expression, and the novice doesn't quite believe that flag is a control expression—it's a boolean! The novice uses the == operator to convert the boolean into a control expression.

In extreme cases, you can even see both cases simultaneously, such as this gem where a public method is checking the state of a private variable

   public boolean isReady() {
      if (ready == true) {
         return true;
      }
      else {
         return false;
      }
   }
What are some programming idioms you've seen that help you diagnose confusions like these?

31 comments:

Raoul Duke said...

I'm guilty. I do the verbose thing. I think it is because I don't like how C and Perl treat any old thing as castable to boolean?

Chris Okasaki said...

Oh, yes, there can definitely be reasons to prefer the more verbose constructions in situations and/or languages when you can't be certain the object in question is a boolean, especially if the interpretation of potential non-boolean values isn't quite the one you want.

Greg D said...

Yeah, I think I've developed a bad verbosity habit for the same reason Raoul stated. I'm trying to wean myself off of it.

Actually, I'm considering the purchase of your book right now as I've started looking at functional approach a little more with the stabilization of F#. It looks like it'd be a good, and interesting, primer for me.

Tim Sweeney said...

A language doesn't have to associate control expressions and booleans. Often, there is an advantage to keeping them distinct. For example, in Java, write a function that takes an Object. Inside it, you might try casting it to an Integer in a control expression. Then inside the condition, if you want to access it again, you need to cast it again! Or you could say:

Int i = Int(MyObject)
if(i) {
...
}

It would be more concise to say:

if(Int i = Int(Object)) {
...
}

In this view, there are many possible success conditions (one for each possible integer), but only one flavor of failure. The Icon language goes pretty far with this approach. You get a nice correspondence with proofs-as-programs: "false" is the uninhabited type, "true" is the set of all inhabited types, arrays mean "and", unions mean "or".

Anthony said...

While I agree that being comfortable with the fact that expressions such as n > 10 are, in fact, booleans is important, I consciously shy away from encouraging terseness regarding that duality. Tim says it well, I think; the list of values that are equal to false in any given language is always a crap shoot.

John "Z-Bo" Zabroski said...

Of course, there is this priceless gem:

boolean result = condition ? true : false;

...where condition is just another boolean expression.

This mistake occurs more often than you might think.

Brian said...

I'd also like to second that this isn't necessarily a sign of confusion. I tend to do it when I'm doing something "unexpected"- it's easy (for me, at least) to miss a ! negation- both in writing the code and in reading or modifying the code. As such, I've gotten into the habit of going, for example, if (foo(x) == FALSE) rather than if (!foo(x)), to make it more obvious what I'm doing. Replace foo(x) with some complicated expression and it becomes a lot more important.

Chris Okasaki said...

Obviously, I didn't make my point very clearly! I'm talking about novice programmers here (and, although I didn't say it in the original post, in the context of a language like Java where control expressions are limited to booleans). Experienced programmers might write code like the verbose examples for any number of perfectly legitimate reasons. But when I see code like that written by novice programmers, it sets off alarm bells that this person does not really understand booleans. It is certainly not conclusive evidence, but it is strongly suggestive. I'm especially interested in examples like this, where the code is correct yet still helps me identify potential misconceptions in novice programmers.

John "Z-Bo" Zabroski said...

Chris,

I think my example was solid, if a little similar to the one you provided at the bottom of your blog entry.

However, your complaint made me think harder, so that is good :-)

I recommend "Intention-Based Diagnosis of Novice Programming Errors" by W. Lewis Johnson. http://books.google.com/books?id=dIPE6MQF3uEC

According to Google Books, it is the first book to use the phrase "bug pattern". I stumbled across it after reading Eric Allen's book, Bug Patterns in Java. Allen stated that as far as he knew, he was the first to coin the phrase. I wanted to verify this claim, so I scoured all of Google's primary search services (web, groups, books, scholar). It proved to be a worthwhile excursion!

Chris Okasaki said...

John,

That book sounds very interesting. I'll have to track down a copy.

Your example with the ?: operator certainly falls into the same category, but I don't think I've ever seen it in the wild, probably because most novices don't have a clue about what the ?: operator does!

John "Z-Bo" Zabroski said...

Chris,

I understand your skepticism about whether my example can be found "in the wild". :-)

Traditionally, hunters had to go into the wild to find the beast. These days, Google Code Search sends you a postcard:
http://www.google.com/codesearch?q=%22%3F+true+%3A+false%3B%22

Cheers. :-)

cartoon camels said...

One common mistake is constants that name their value, such as:

const int three = 3;

This clearly signifies a novice who doesn't understand the principle underlying the oft-quoted rule: "Don't use magic values!"

For a more concrete example, I've actually seen the following in production code:

const string select = " SELECT ";
const string from = " FROM ";
const string where = " WHERE ";
const string groupby = " GROUP BY ";
...
string query = select + "*" + from + "mytable" + where + ...;

Only, in the real code the variable names followed a rather heavyweight naming convention, something like SYS_CONST_STRING_SELECT.

uncial said...

Chris, while I agree that the examples you offered indicate a lack of fluency with booleans (and that kind of thing is as unpleasant as chewing on aluminum foil), I've also observed some programmers who routinely work in multiple languages and seem to have evolved a personal least-common-denominator set of idioms that they use across languages. This indicates (to me) a kind of jack-of-all-trades, master-of-none approach which may be a different kind of non-fluency than that of the pure novice.

MAG said...

Hi Chris, I had to laugh at your next post as your book is on top of a stack next to my bed. Anyway, interestingly I found the if-else boolean construct in the Lucene.Net (Search Engine) port from Java. I struggled not to rewrite large chunks of code on seeing it! Especially with such beauties as the one below, which is a mixture of both concepts!!!

bool tmpBool;
if (System.IO.File.Exists(file.FullName))
tmpBool = true;
else
tmpBool = System.IO.Directory.Exists(file.FullName);

Chris Okasaki said...

MAG, that example is hilarious!

John "Z-Bo" Zabroski said...

Chris,

Just wondering (and trying to be genuinely helpful), have you ever read Bill Pugh's blog? You know, the creator of FindBugs?

remcoder said...

the other day I saw a novice programmer at work code something like this:

void setText(object o, string text, bool hasInnerHtml)
{
if (hasInnerHtml)
o.innerHtml = text;
else
o.text = text;
}

To the novice this fuction apparently seems to capture enough functionality to justify it being a separate function. After all, it sets the text of two kinds of objects, ones that have an innerHtml property and ones that have a Text property.

However, the novice fails to notice that using this function is actually worse than not using it because:

1) it does either this, either that but never both at the same time AND when calling the function you'll explicitly have to tell it which of the 2 behaviors to pick. In other words, nothing is gained.

2) setText(myLabel, "hello there", false);
this is actually more verbose than:
myLabel.Text = "hello there!";
it's also hides the fact that there is an assignment done. Assignments are much easier to read than function calls.

How would you explain the flaw in the programmer's mental model in this case?

KSM said...

One I've seen is that novice programmers tend to think of `expression' as a synonym for `simple', so they reflexively name anything that seems too complicated to them.

Button b = new Button("OK"):
container.add(b);

rather than:

container.add(new Button("OK"));

Or:

Thread t = new Thread(...);
t.run();

rathern than:

new Thread(...).run();

Or:

List keys = map.keys();
return keys;

The faulty model seems to be a (possibly healthy) distinction between values and computations where no such distinction really exists.

Greg D said...

remcoder:

The flaw in the novice's mental model may be related to a failure to distinguish between semantic and syntactic type.

The novice apparently believes that the function should do one thing, as evidenced by the function's name. That's a good thing. The novice may not draw the distinction between InnerHtml and Text being different semantic types, though, even though they have the same syntactic type. InnerHtml may be a string, but it isn't Text and shouldn't be treated as, or referred to as, Text. (The original dev of the production code I'm maintaining right now had a similar flaw in their mental model. Xml isn't plaintext, and probably shouldn't be munged together as though it were.)

If the novice understood that distinction, they might try to add a separate InnerHtml parameter to avoid overloading the "text" parameter. If they tried that, they would (hopefully!) see that the function is now obviously doing two independent things, not one cohesive thing. That would lead to setText being split into setText and setInnerHtml. Each of those functions has a single line, though, and may as well not exist, leading the novice to realize that it's best (in this case) to simply call the appropriate methods.

I probably wouldn't focus too much on #2 that you listed there. Some Lispers may very well prefer the parenthetical approach. ;)

Chris Okasaki said...

John: Thanks for the pointer.

remcoder: There are two separate issues here--why it's one method instead of two, and why it's a method at all. I don't have a good answer for the former, but I've got a good guess for the latter. There's a vocal faction of the OO community that believes that you should never have public fields, but should always have private fields with getters/setters if needed. So this kind of setter is quite common (even in languages that don't have the same public/private distinction).

ksm: This sort of thing doesn't bother me too much, although it certainly can be funny when taken to an extreme. The opposite approach of never naming intermediate values can easily get out of hand when you have one line doing 27 things. One pretty reasonable explanation I heard once from somebody who was naming small expressions like this is that it made it easier to watch those values in the debugger.

cartoon camels said...

While I agree with the point that temp variables are easier to work with inside a debugger, I think this suggests that most debuggers are missing a feature. Some debuggers report returned values, and I've found that this markedly improves the size and clarity of my code. I've found myself creating more and more temporaries in otherwise clean, simple code when using debuggers that lack this ability.

James Iry said...

My favorite of all time was this Java where the programmer was taking very seriously the rule that equals should be reflexive. In the process I think it showed a deep misunderstanding about the magic of "this."

boolean equals(Object other) {
if (this == other)
return true;

if (other == null)
return false;

if (this == null)
return false;

...

google said...

For some beautiful pearls of (not only) novice programmer blunders have a look at http://thedailywtf.com/, but be prepared to waste a few hours!

Stan Switzer said...

I sometimes write the more verbose logic so that there are good places to place breakpoints.

Its not just a question of paranoid programming (which I _do not_ support). Nevertheless, I want to do a bit of ad-hoc coverage analysis during development and it can surely come in handy later as well.

Antti said...

One of my favourite pet peeves with Java is that it occasionally forces me to write

if (true)
  return true;

if I want to leave dead code after dummy code that simply returns true.

John "Z-Bo" Zabroski said...

Funny thing made me think of this blog post... I was reading the Spring 2008 issue of Crossroads, the ACM Student Journal (Vol. 14, No. 3). Page 13, peer reviewed PHP code sample that passed by the editors and peer reviewers:

$is_logged_in = ($user->isLoggedIn()) ? true : false;

I am sorry if this makes you weep. I know it made me weep, and I came across it as some pre-bedtime reading. :(

rgrig said...

I have recently read the following code, for which I have no explanation. Snippets:

import java.util.LinkedList;
[...]
LinkedList<Link> initial_list = new LinkedList<Link<();
[...]
class Link {
..public int dData;
..public Link next;
..[...]
}
[...]
public Link Min(LinkedList<Link> list){
..Link temp = list.getFirst();
..for(int a = 0; a<(list.size()-1);a++){
....for(int b = 0;b<(list.size());b++){
......if(list.get(a).dData > list.get(b).dData){
........temp = list.get(b);
......}
....}
..return temp;
}
[...]

mtrimpe said...

Just a few days ago I had to debug the following JavaScript-code made by a quite brilliant front-end designer:

onChange:
setCookie('on', this.value) ;

onLoad:
if (getCookie('on')) do_stuff() ;

What do you expect them to learn when I tell them that it doesn't work because 'false' is true!

Jared said...

I think another explanation for:

public boolean isReady() {
if (ready == true) {
return true;
}
else {
return false;
}
}

is the confusion caused by return: return changes flow control by returning a value, so I have to have the value ready to be returned before I can return something, right? Won't it escape from my function the moment it hits return?

I've seen respectable, capable (advanced) programmers that do this sort of thing (var = expr; return var;), forgetting that you can just return an expression and the compiler will generate code that FIRST computes the expression and THEN return the value computed. I think idiomatically, imperative programmers are a lot more likely to save return statements for the very end of functions than functional programmers, who better grok the idea of using an expression to compute a return value, with said computation sometimes being its own type of flow control.

As Dijkstra said, BASIC programmers are mentally mutilated beyond hope of regeneration. Luckily newer generations of programmers have better programming languages to learn as a first language, so there is hope after all.

Raoul Duke said...

[wow, this thread will live and grow for ever]

@KSM: I quite often do create an extra variable because then I can use a debugger more effectively (most don't let you set break points inside some sub-part of a line of code).

Raoul Duke said...

@Jared

similarly, i mostly dislike the use of multiple returns in functions: it makes it a lot harder to debug later when i have to learn, maintain, and extend that questionable code.

but i'm not bitter! ;-)