Friday, March 12, 2010

Well, Dog My Cats!

Well, Dog My Cats!

This program uses a Counter class to keep track of how many times each kind of house pet makes a noise. What does the program print?

class Counter {

private static int count;

public static void increment() { count++; }

public static int getCount() { return count; }

}



class Dog extends Counter {

public Dog() { }

public void woof() { increment(); }

}



class Cat extends Counter {

public Cat() { }

public void meow() { increment(); }

}



public class Ruckus {

public static void main(String[] args) {

Dog dogs[] = { new Dog(), new Dog() };

for (int i = 0; i < dogs.length; i++)

dogs[i].woof();

Cat cats[] = { new Cat(), new Cat(), new Cat() };

for (int i = 0; i < cats.length; i++)

cats[i].meow();

System.out.print(Dog.getCount() + " woofs and ");

System.out.println(Cat.getCount() + " meows");

}

}






Solution : Well, Dog My Cats!


We have two dogs woofing and three cats meowing—a ruckus, to be sure—so the program should print 2 woofs and 3 meows, no? No: It prints 5 woofs and 5 meows. Where is all the extra noise coming from, and what can we do to stop it?



The sum of the number of woofs and meows printed by the program is 10, fully twice what it should be. The problem is that Dog and Cat inherit the count field from a common superclass, and count is a static field. A single copy of each static field is shared among its declaring class and all subclasses, so Dog and Cat use the same count field. Each call to woof or meow increments this field, so it is incremented five times. The program reads it twice, by calling Dog.getCount and Cat.getCount. In each case, 5 is returned and printed.



We cannot fix the problem by making count an instance field. That would create one counter per pet rather than one counter per kind of pet. To fix the program, we must correct a fundamental design error.



When designing one class to build on the behavior of another, you have two options: inheritance, in which one class extends the other; or composition, in which one class contains an instance of the other. Choose based on whether each instance of one class is an instance of the other class or has an instance of the other. In the first case, use inheritance; in the second, use composition. When in doubt, favor composition over inheritance .



Neither a dog nor a cat is a kind of counter, so it was wrong to use inheritance. Instead of extending Counter, Dog and Cat should each have a counter field. One counter is required for each kind of pet, rather than for each individual pet, so these fields must be static. We needn't bother with a Counter class; an int will do fine. Here is the redesigned program, which prints 2 woofs, 3 meows as expected:




class Dog {

private static int woofCounter;

public Dog() { }

public static int woofCount() { return woofCounter; }

public void woof() { woofCounter++; }

}



class Cat {

private static int meowCounter;

public Cat() { }

public static int meowCount() { return meowCounter; }

public void meow() { meowCounter++; }

}



The Ruckus class is unchanged with the exception of the two print statements, which are modified to use the new method names to access the counts:




System.out.print(Dog.woofCount() + " woofs, ");

System.out.println(Cat.meowCount() + " meows");



In summary, static fields are shared by their declaring class and any subclasses. If you need a separate copy of a field for each subclass, you must declare a separate static field in each subclass. If you need a separate copy for each instance, declare a nonstatic field in the base class. Also, favor composition over inheritance unless the derived class really is a kind of the base class.

Saturday, March 6, 2010

What's the Point?

What's the Point?

This program has two immutable value classes, which are classes whose instances represent values. One class represents a point on the plane with integer coordinates, and the second class adds a bit of color to the puzzle. The main program creates and prints an instance of the second class. What does the program print?

class Point {

private final int x, y;

private final String name; // Cached at construction time



Point(int x, int y) {

this.x = x;

this.y = y;

name = makeName();

}



protected String makeName() {

return "[" + x + "," + y + "]";

}



public final String toString() {

return name;

}

}



public class ColorPoint extends Point {

private final String color;



ColorPoint(int x, int y, String color) {

super(x, y);

this.color = color;

}



protected String makeName() {

return super.makeName() + ":" + color;

}



public static void main(String[] args) {

System.out.println(new ColorPoint(4, 2, "purple"));

}

}



Solution :What’s The Point?


The main method creates and prints a ColorPoint instance. The println method invokes the toString method of the ColorPoint instance, which is defined in Point. The toString method simply returns the value of the name field, which is initialized in the Point constructor by calling the makeName method. For a Point instance, the makeName method returns a string of the form [x,y]. For a ColorPoint instance, makeName is overridden to return a string of the form [x,y]:color. In this case, x is 4, y is 2, and the color is purple, so the program prints [4,2]:purple, right? No. If you ran the program, you found that it prints [4,2]:null. What is the matter with the program?



The program suffers from a problem with the order of instance initialization. To understand the problem, we will trace the program execution in detail. Here is an annotated program listing to guide us:




class Point {

protected final int x, y;

private final String name;



Point(int x, int y) {

this.x = x;

this.y = y;

name = makeName(); // 3. Invoke subclass method

}



protected String makeName() {

return "[" + x + "," + y + "]";

}



public final String toString() {

return name;

}

}



public class ColorPoint extends Point {

private final String color;



ColorPoint(int x, int y, String color) {

super(x, y); // 2. Chain to Point constructor

this.color = color; // 5. Initialize blank final-Too late

}





protected String makeName() {

// 4. Executes before subclass constructor body!

return super.makeName() + ":" + color;

}



public static void main(String[] args) {

// 1. Invoke subclass constructor

System.out.println(new ColorPoint(4, 2, "purple"));

}

}



In the explanation that follows, the numbers in parentheses refer to the numbers in the comments in the annotated listing. First, the program creates a ColorPoint instance by invoking the ColorPoint constructor (1). This constructor starts by chaining to the superclass constructor, as all constructors do (2). The superclass constructor assigns 4 to the x field of the object under construction and 2 to its y field. Then the constructor invokes makeName, which is overridden by the subclass (3).



The makeName method in ColorPoint (4) executes before the body of the ColorPoint constructor, and therein lies the heart of the problem. The makeName method first invokes super.makeName, which returns [4,2] as expected. Then the method appends the string ":" and the value of the color field, converted to a string. But what is the value of the color field at this point? It has yet to be initialized, so it still contains its default value of null. Therefore, the makeName method returns the string "[4,2]:null". The superclass constructor assigns this value to the name field (3) and returns control to the subclass constructor.



The subclass constructor then assigns the value "purple" to the color field (5), but it is too late. The color field has already been used to initialize the name field in the superclass to an incorrect value. The subclass constructor returns, and the newly created ColorPoint instance is passed to the println method, which duly invokes its toString method. This method returns the contents of its name field, "[4,2]:null", so that is what the program prints.



This puzzle illustrates that it is possible to observe the value of a final instance field before its value has been assigned, when it still contains the default value for its type. In a sense, this puzzle is the instance analog of (Larger than life), which observed the value of a final static field before its value had been assigned. In both cases, the puzzle resulted from a circularity in initialization. In Larger than life, it was class initialization; in this puzzle, it is instance initialization. Both cases have the potential for enormous confusion. There is one point where the analogy breaks down: Circular class initialization is a necessary evil, but circular instance initialization can and should always be avoided.



The problem arises whenever a constructor calls a method that has been overridden in its subclass. A method invoked in this way always runs before the instance has been initialized, when its declared fields still have their default values. To avoid this problem, never call overridable methods from constructors, either directly or indirectly . This prohibition extends to instance initializers and the bodies of the pseudoconstructors readObject and clone. (These methods are called pseudoconstructors because they create objects without invoking a constructor.)



You can fix the problem by initializing the field name lazily, when it is first used, rather than eagerly, when the Point instance is created. With this change, the program prints [4,2]:purple as expected:




class Point {

protected final int x, y;

private String name; // Lazily initialized



Point(int x, int y) {

this.x = x;

this.y = y;

// name initialization removed

}



protected String makeName() {

return "[" + x + "," + y + "]";

}



// Lazily computes and caches name on first use

public final synchronized String toString() {

if (name == null)

name = makeName();

return name;

}

}



Although lazy initialization fixes the problem, it is a bad idea to have one value class extend another, adding a field that affects equals comparisons. You can't provide value-based equals methods on both the superclass and subclass without violating the general contract for Object.equals or eliminating the possibility of meaningful comparisons between superclass and subclass instances .



The circular instance initialization problem is a can of worms for language designers. C++ addresses the problem by changing the type of the object from the superclass type to the subclass type during construction. With this solution, the original program in this puzzle would print [4,2]. We're not aware of any popular language that addresses this issue satisfactorily. Perhaps it is worth considering making circular instance initialization illegal by throwing an unchecked exception when a superclass constructor calls a subclass method.



To summarize, you must never call an overridable method from a constructor under any circumstances. The resulting circularities in instance initialization can be fatal. The solution to this problem is lazy initialization .

Larger Than Life

Larger Than Life

Lest you think that this book is going entirely to the dogs, this puzzle concerns royalty. If the tabloids are to be believed, the King of Rock 'n' Roll is still alive. Not one of his many impersonators but the one true Elvis. This program estimates his current belt size by projecting the trend observed during his public performances. The program uses the idiom Calendar.getInstance().get(Calendar.YEAR), which returns the current calendar year. What does the program print?

public class Elvis {

public static final Elvis INSTANCE = new Elvis();

private final int beltSize;

private static final int CURRENT_YEAR =

Calendar.getInstance().get(Calendar.YEAR);



private Elvis() {

beltSize = CURRENT_YEAR - 1930;

}



public int beltSize() {

return beltSize;

}



public static void main(String[] args) {

System.out.println("Elvis wears a size " +

INSTANCE.beltSize() + " belt.");

}

}






Solution : Larger Than Life


At first glance, this program appears to compute the current year minus 1930. If that were correct, in the year 2006, the program would print Elvis wears a size 76 belt. If you tried running the program, you learned that the tabloids were wrong, proving that you can't believe everything you read in the papers. It prints Elvis wears a size -1930 belt. Perhaps the King has gone on to inhabit an anti-matter universe?



This program suffers a problem caused by a circularity in the order of class initialization . Let's follow it in detail. Initialization of the class Elvis is triggered by the VM's call to its main method. First, static fields are set to their default values . The field INSTANCE is set to null, and CURRENT_YEAR is set to 0. Next, static field initializers are executed in order of appearance. The first static field is INSTANCE. Its value is computed by invoking the Elvis() constructor.



The constructor initializes beltSize to an expression involving the static field CURRENT_YEAR. Normally, reading a static field is one of the things that causes a class to be initialized, but we are already initializing the class Elvis. Recursive initialization attempts are simply ignored . Consequently, the value of CURRENT_YEAR still has its default value of 0. That is why Elvis's belt size turns out to be -1930.



Finally, returning from the constructor to complete the class initialization of Elvis, we initialize the static field CURRENT_YEAR to 2006, assuming you're running the program in 2006. Unfortunately, it is too late for the now correct value of this field to affect the computation of Elvis.INSTANCE.beltSize, which already has the value -1930. This is the value that will be returned by all subsequent calls to Elvis.INSTANCE.beltSize().



This program shows that it is possible to observe a final static field before it is initialized, when it still contains the default value for its type. That is counterintuitive, because we usually think of final fields as constants. Final fields are constants only if the initializing expression is a constant expression .



Problems arising from cycles in class initialization are difficult to diagnose but once diagnosed are usually easy to fix. To fix a class initialization cycle, reorder the static field initializers so that each initializer appears before any initializers that depend on it. In this program, the declaration for CURRENT_YEAR belongs before the declaration for INSTANCE, because the creation of an Elvis instance requires that CURRENT_YEAR be initialized. Once the declaration for CURRENT_YEAR has been moved, Elvis will indeed be larger than life.



Some common design patterns are naturally subject to initialization cycles, notably the Singleton , which is illustrated in this puzzle, and the Service Provider Framework . The Typesafe Enum pattern also causes class initialization cycles. Release 5.0 adds linguistic support for this pattern with enum types. To reduce the likelihood of problems, there are some restrictions on static initializers in enum types .



In summary, be careful of class initialization cycles. The simplest ones involve only a single class, but they can also involve multiple classes. It isn't always wrong to have class initialization cycles, but they may result in constructor invocation before static fields are initialized. Static fields, even final static fields, may be observed with their default value before they are initialized.

Wednesday, March 3, 2010

Big Problem

Big Problem

As a warm-up, test your knowledge of BigInteger. What does this program print?

import java.math.BigInteger;

public class BigProblem {

public static void main(String[] args) {

BigInteger fiveThousand = new BigInteger("5000");

BigInteger fiftyThousand = new BigInteger("50000");

BigInteger fiveHundredThousand

= new BigInteger("500000");

BigInteger total = BigInteger.ZERO;

total.add(fiveThousand);

total.add(fiftyThousand);

total.add(fiveHundredThousand);

System.out.println(total);

}

}



Solution : Big Problem


You might think that this program prints 555000. After all, it sets total to the BigInteger representation for 0 and then adds 5,000, 50,000, and 500,000. If you ran the program, you found that it doesn't print 555000 but 0. Apparently all that addition has no effect on total.



There is a good reason for this: BigInteger instances are immutable. So are instances of String, BigDecimal, and the wrapper types: Integer, Long, Short, Byte, Character, Boolean, Float, and Double. You can't change their values. Instead of modifying existing instances, operations on these types return new instances. At first, immutable types might seem unnatural, but they have many advantages over their mutable counterparts. Immutable types are easier to design, implement, and use; they are less error prone and more secure .



To perform a computation on a variable containing a reference to an immutable object, assign the result of the computation to the variable. Doing this yields the following program, which prints the expected result of 555000:




import java.math.BigInteger;



public class BigProblem {

public static void main(String [] args) throws Exception {

BigInteger fiveThousand = new BigInteger("5000");

BigInteger fiftyThousand = new BigInteger("50000");

BigInteger fiveHundredThousand

= new BigInteger("500000");



BigInteger total = BigInteger.ZERO;

total = total.add(fiveThousand);

total = total.add(fiftyThousand);

total = total.add(fiveHundredThousand);

System.out.println(total);

}

}



The lesson of this puzzle is: Do not be misled into thinking that immutable types are mutable. This is a common error among beginning Java programmers. In fairness, the names of some methods in Java's immutable types help to lead them astray. Names like add, subtract, and negate suggest that these methods mutate the instance on which they're invoked. Better names would be plus, minus, and negation.



A lesson for API designers, then, is: When naming methods for immutable types, prefer prepositions and nouns to verbs. Prepositions are appropriate for methods with parameters and nouns for parameterless methods. A lesson for language designers is, as in Problem of change, that it might be worth offering limited support for operator overloading so that arithmetic operators can be made to work with numerical reference types, such as BigInteger. Not even a beginner would think that evaluating the expression total + fiveThousand would have any effect on the value of total.

All I Get Is Static

All I Get Is Static

The following program models the behavioral difference between Basenjis and other dogs. In case you didn't know, the Basenji is a breed of small, curly-tailed dogs of African origin that do not bark. What does the program print?

class Dog {

public static void bark() {

System.out.print("woof ");

}

}



class Basenji extends Dog {

public static void bark() { }

}



public class Bark {

public static void main(String args[]) {

Dog woofer = new Dog();

Dog nipper = new Basenji();

woofer.bark();

nipper.bark();

}

}



Solution: All I Get Is Static


On casual inspection, it would appear that this program should just print woof. After all, Basenji extends Dog and defines its bark method to do nothing. The main method invokes the bark method, first on woofer the Dog and again on nipper the Basenji. Basenjis don't bark, but apparently this one does. If you ran the program, you found that it prints woof woof. What is the matter with poor Nipper?



The title of this puzzle gives a big hint. The problem is that bark is a static method, and there is no dynamic dispatch on static methods [JLS 15.12.4.4]. When a program calls a static method, the method to be invoked is selected at compile time, based on the compile-time type of the qualifier, which is the name we give to the part of the method invocation expression to the left of the dot. In this case, the qualifiers of the two method invocations are the variables woofer and nipper, both of which are declared to be of type Dog. Because they have the same compile-time type, the compiler causes the same method to be invoked: Dog.bark. This explains why the program prints woof woof. It doesn't matter that the runtime type of nipper is Basenji; only its compile-time type is considered.



To fix this program, simply remove the static modifier from the two bark method declarations. Then the bark method in Basenji will override rather than hide the bark method in Dog, and the program will print woof instead of woof woof. With overriding, you get dynamic dispatch; with hiding, you don't.



When you invoke a static method, you typically qualify it with a class rather than an expression: for example Dog.bark or Basenji.bark. When you read a Java program, you expect classes to be used as the qualifiers for static methods, which are statically dispatched, and expressions to be used as the qualifiers for instance methods, which are dynamically dispatched. Coupled with the different naming conventions for classes and variables, this provides a strong visual cue as to whether a given method invocation is static or dynamic. The program in this puzzle uses an expression as the qualifier for a static method invocation, which is misleading. Never qualify a static method invocation with an expression.



The confusion is compounded by the appearance of overriding. The bark method in Basenji has the same signature as the one in Dog. That is the usual formula for overriding, which suggests dynamic dispatch. In this case, however, the methods are declared static. Static methods cannot be overridden; they can only be hidden, and just because you can doesn't mean you should. To avoid confusion, do not hide static methods. There is nothing to gain, and much to lose, from reusing the name of a superclass's static method in a subclass.



The lesson for language designers is that invocations of class and instance methods should look different from each other. One way to further this goal is to disallow the use of expressions as qualifiers for static methods. A second way to distinguish static and instance method invocations is to use different operators, as C++ does. A third alternative is to finesse the issue by dispensing with the concept of static methods altogether, as Smalltalk does.



In summary, qualify static methods invocations with a class name, or don't qualify them at all if you're invoking them from within their own class, but never qualify them with an expression. Also, avoid hiding static methods. Together, these guidelines help eliminate the misleading appearance of overriding with dynamic dispatch for static methods.

Not Your Type

Not Your Type

This puzzle tests your understanding of Java's two classiest operators: instanceof and cast. What does each of the following three programs do?

public class Type1 {

public static void main(String[] args) {

String s = null;

System.out.println(s instanceof String);

}

}



public class Type2 {

public static void main(String[] args) {

System.out.println(new Type2() instanceof String);

}

}



public class Type3 {

public static void main(String args[]) {

Type3 t3 = (Type3) new Object();

}

}






Solution : Not Your Type


The first program, Type1, illustrates the behavior of the instanceof operator when applied to a null object reference. Although null is a subtype of every reference type, the instanceof operator is defined to return false when its left operand is null. Therefore, Type1 prints false. This turns out be the most useful behavior in practice. If instanceof tells you that an object reference is an instance of a particular type, you are assured that you can cast it to that type and invoke methods of the type without fear of a ClassCastException or a NullPointerException.



The second program, Type2, illustrates the behavior of the instanceof operator when testing an instance of one class to see whether it is an instance of an unrelated class. You might expect this program to print false. After all, an instance of Type2 isn't an instance of String, so the test should fail, right? No. The instanceof test fails at compile time with an error message like this:




Type2.java: inconvertible types

found: Type2, required: java.lang.String

System.out.println(new Type2() instanceof String);

^



The program fails to compile because the instanceof operator requires that if both operands are class types, one must be a subtype of the other . Neither Type2 nor String is a subtype of the other, so the instanceof test results in a compile-time error. This error helps alert you to instanceof tests that probably don't do what you want.



The third program, Type3, illustrates the behavior of the cast operator when the static type of the expression to be cast is a superclass of the cast type. Like the instanceof operation, if both types in a cast operation are class types, one must be a subtype of the other. Although it is obvious to us that this cast will fail, the type system is not powerful enough to know that the run-time type of the expression new Object() cannot be a subtype of Type3. Therefore, the program throws a ClassCastException at run time. This is a bit counterintuitive: The second program makes perfect sense but doesn't compile; this one makes no sense but does.



In summary, the first program illustrates a useful corner case in the run-time behavior of instanceof. The second program illustrates a useful corner case in its compile-time behavior. The third program illustrates a corner case in the behavior of the cast operator where the compiler fails to save you from your folly, and the VM is left to take up the slack at run time.

Cutting Class

Cutting Class

Consider these two classes:

public class Strange1 {

public static void main(String[] args) {

try {

Missing m = new Missing();

} catch (java.lang.NoClassDefFoundError ex) {

System.out.println("Got it!");

}

}

}



public class Strange2 {

public static void main(String[] args) {

Missing m;

try {

m = new Missing();

} catch (java.lang.NoClassDefFoundError ex) {

System.out.println("Got it!");

}

}

}



Both Strange1 and Strange2 use this class:




class Missing {

Missing() { }

}



If you were to compile all three classes and then delete the file Missing.class before running Strange1 and Strange2, you'd find that the two programs behave differently. One throws an uncaught NoClassDefFoundError, whereas the other prints Got it! Which is which, and how can you explain the difference in behavior?



 



Solution :Cutting Glass



The Strange1 program mentions the missing type only within its try block, so you might expect it to catch the NoClassDefFoundError and print Got it! The Strange2 program, on the other hand, declares a variable of the missing type outside the try block, so you might expect the NoClassDefFoundError generated there to be uncaught. If you tried running the programs, you saw exactly the opposite behavior: Strange1 tHRows an uncaught NoClassDefFoundError, and Strange2 prints Got it! What could explain this strange behavior?



If you look to the Java language specification to find out where the NoClassDefFoundError should be thrown, you don't get much guidance. It says that the error may be thrown "at any point in the program that (directly or indirectly) uses the type" . When the VM invokes the main method of Strange1 or Strange2, the program is using class Missing indirectly, so either program would be within its rights to throw the error at this point.



The answer to the puzzle, then, is that either program may exhibit either behavior, depending on the implementation. But that doesn't explain why in practice these programs behave exactly opposite to what you would naturally expect, on all Java implementations we know of. To find out why this is so, we need to study the compiler-generated bytecode for these programs.



If you compare the bytecode for Strange1 and Strange2, you'll find them nearly identical. Aside from the class name, the only difference is the mapping of the catch parameter ex to a VM local variable. Although the details of which program variables are assigned to which VM variables can vary from compiler to compiler, they are unlikely to vary much for programs as simple as these. Here is the code for Strange1.main as displayed by javap -c Strange1:




 0: new            #2; // class Missing

3: dup

4: invokespecial #3; // Method Missing."<init>":()V

7: astore_1

8: goto 20

11: astore_1

12: getstatic #5; // Field System.out:Ljava/io/PrintStream;

15: ldc #6; // String "Got it!"

17: invokevirtual #7; // Method PrintStream.println:(String;)V

20: return

Exception table:

from to target type

0 8 11 Class java/lang/NoClassDefFoundError



The corresponding code for Strange2.main differs in only one instruction:




11: astore_2



This is the instruction that stores the caught exception of the catch block into the catch parameter ex. In Strange1, this parameter is stored in VM variable 1; in Strange2, it is stored in VM variable 2. That is the only difference between these two classes, but what a difference it makes in their behavior!



To run a program, the VM loads and initializes the class containing its main method. In between loading and initialization, the VM must link the class . The first phase of linking is verification. Verification ensures that a class is well formed and obeys the semantic requirements of the language. Verification is critical to maintaining the guarantees that distinguish a safe language like Java from an unsafe language like C or C++.



In classes Strange1 and Strange2, the local variable m happens to be stored in VM variable 1. Both versions of main also have a join point, where the flow of control from two different places converge. The join point is instruction 20, which is the instruction to return from main. Instruction 20 can be reached either by completing the TRy block normally, in which case we goto 20 at instruction 8, or by completing the catch block and falling through from instruction 17 to instruction 20.



The existence of the join point causes an exception during the verification of class Strange1 but not class Strange2. When it performs flow analysis [JLS 12.3.1] of Strange1.main, the verifier must merge the types contained in variable 1 when instruction 20 is reached by the two different paths. Two types are merged by computing their first common superclass [JVMS 4.9.2]. The first common superclass of two classes is the most specific superclass they share.



The state of VM variable 1 when instruction 20 is reached from instruction 8 in Strange1.main is that it contains an instance of the class Missing. When reached from instruction 17, it contains an instance of the class NoClassDefFoundError. In order to compute the first common superclass, the verifier must load the class Missing to determine its superclass. Because Missing.class has been deleted, the verifier can't load it and throws a NoClassDefFoundError. Note that this exception is thrown during verification, before class initialization and long before the main method begins execution. This explains why there is no stack trace printed for the uncaught exception.



To write a program that can detect when a class is missing, use reflection to refer to the class rather than the usual language constructs . Here is how the program looks when rewritten to use this technique:




public class Strange {

public static void main(String[] args) throws Exception {

try {

Object m = Class.forName("Missing").newInstance();

} catch (ClassNotFoundException ex) {

System.err.println("Got it!");

}

}

}



In summary, do not depend on catching NoClassDefFoundError. The language specification carefully describes when class initialization occurs , but class loading is far less predictable. More generally, it is rarely appropriate to catch Error or its subclasses. These exceptions are reserved for failures from which recovery is not feasible.

Tuesday, March 2, 2010

Confusing Constructor

Confusing Constructor

This puzzle presents you with two Confusing constructors. The main method invokes a constructor, but which one? The program's output depends on the answer. What does the program print, or is it even legal?

public class Confusing {

private Confusing(Object o) {

System.out.println("Object");

}



private Confusing(double[] dArray) {

System.out.println("double array");

}



public static void main(String[] args) {

new Confusing(null);

}

}






Solution : Confusing Constructor


The parameter passed to the constructor is the null object reference, so at first glance, it seems that the program should invoke the Object overloading and print Object. On the other hand, arrays are reference types too, so null could just as well apply to the double[] overloading. You might therefore conclude that the call is ambiguous, which suggests that the program shouldn't compile. If you tried running the program, you found that neither of these intuitions is correct: The program prints double array. This behavior may seem perverse, but there is a good reason for it.



Java's overload resolution process operates in two phases. The first phase selects all the methods or constructors that are accessible and applicable. The second phase selects the most specific of the methods or constructors selected in the first phase. One method or constructor is less specific than another if it can accept any parameters passed to the other [JLS 15.12.2.5].



In our program, both constructors are accessible and applicable. The constructor Confusing(Object) accepts any parameter passed to Confusing(double[]), so Confusing(Object) is less specific. (Every double array is an Object, but not every Object is a double array.) The most specific constructor is therefore Confusing(double[]), which explains the program's output.



This behavior makes sense if you pass a value of type double[]; it is counterintuitive if you pass null. The key to understanding this puzzle is that the test for which method or constructor is most specific does not use the actual parameters: the parameters appearing in the invocation. They are used only to determine which overloadings are applicable. Once the compiler determines which overloadings are applicable and accessible, it selects the most specific overloading, using only the formal parameters: the parameters appearing in the declaration.



To invoke the Confusing(Object) constructor with a null parameter, write new Confusing((Object)null). This ensures that only Confusing(Object) is applicable. More generally, to force the compiler to select a specific overloading, cast actual parameters to the declared types of the formal parameters.



Selecting among overloadings in this fashion is unpleasant. In your APIs, ensure that clients aren't forced to go to these extremes. Ideally, you should avoid overloading: Use different names for different methods. Sometimes, this is not possible. Constructors don't have names, so they can't be given different names. You can, however, alleviate the problem by making constructors private and providing public static factories . If constructors have many parameters, you can reduce the need for overloading with the Builder pattern .



If you do overload, ensure that all overloadings accept mutually incompatible parameter types, so that no two are applicable at the same time. Failing that, ensure that all applicable overloadings have the same behavior .



In summary, overload resolution can be confusing. Avoid overloading where possible. If you must overload, obey the guidelines outlined here to minimize confusion. If a poorly designed API forces you to select among overloadings, cast actual parameters to the types of the formal parameters of the desired overloading.

Hello, Goodbye

Hello, Goodbye

This program adds an unusual twist to the usual Hello world program. What does it print?

public class HelloGoodbye {

public static void main(String[] args) {

try {

System.out.println("Hello world");

System.exit(0);

} finally {

System.out.println("Goodbye world");

}

}

}






Solution : Hello, Goodbye


The program contains two println statements: one in a try block and the other in the corresponding finally block. The TRy block executes its println and finishes execution prematurely by calling System.exit. At this point, you might expect control to transfer to the finally block. If you tried the program, though, you found that it never can say goodbye: It prints only Hello world. Doesn't this violate the principle explained in Indecision?



It is true that a finally block is executed when a try block completes execution whether normally or abruptly. In this program, however, the try block does not complete execution at all. The System.exit method halts the execution of the current thread and all others dead in their tracks. The presence of a finally clause does not give a thread special permission to continue executing.



When System.exit is called, the virtual machine performs two cleanup tasks before shutting down. First, it executes all shutdown hooks that have been registered with Runtime.addShutdownHook. This is useful to release resources external to the VM. Use shutdown hooks for behavior that must occur before the VM exits. The following version of the program demonstrates this technique, printing both Hello world and Goodbye world, as expected:




public class HelloGoodbye {

public static void main(String[] args) {

System.out.println("Hello world");

Runtime.getRuntime().addShutdownHook(

new Thread() {

public void run() {

System.out.println("Goodbye world");

}

});

System.exit(0);

}

}



The second cleanup task performed by the VM when System.exit is called concerns finalizers. If either System.runFinalizersOnExit or its evil twin Runtime.runFinalizersOnExit has been called, the VM runs the finalizers on all objects that have not yet been finalized. These methods were deprecated a long time ago and with good reason. Never call System.runFinalizersOnExit or Runtime.runFinalizersOnExit for any reason: They are among the most dangerous methods in the Java libraries [ThreadStop]. Calling these methods can result in finalizers being run on live objects while other threads are concurrently manipulating them, resulting in erratic behavior or deadlock.



In summary, System.exit stops all program threads immediately; it does not cause finally blocks to execute, but it does run shutdown hooks before halting the VM. Use shutdown hooks to terminate external resources when the VM shuts down. It is possible to halt the VM without executing shutdown hooks by calling System.halt, but this method is rarely used.

Indecision

Indecision

This poor little program can't quite make up its mind. The decision method returns true. But it also returns false. What does it print? Is it even legal?

public class Indecisive {

public static void main(String[] args) {

System.out.println(decision());

}



static boolean decision() {

try {

return true;

} finally {

return false;

}

}

}






Solution : Indecision


You might think that this program is illegal. After all, the decision method can't return both TRue and false. If you tried it, you found that it compiles without error and prints false. Why?



The reason is that in a try-finally statement, the finally block is always executed when control leaves the try block [JLS 14.20.2]. This is true whether the try block completes normally or abruptly. Abrupt completion of a statement or block occurs when it throws an exception, executes a break or continue to an enclosing statement, or executes a return from the method as in this program. These are called abrupt completions because they prevent the program from executing the next statement in sequence.



When both the TRy block and the finally block complete abruptly, the reason for the abrupt completion in the try block is discarded, and the whole TRy-finally statement completes abruptly for the same reason as the finally block. In this program, the abrupt completion caused by the return statement in the TRy block is discarded, and the TRy-finally statement completes abruptly because of the return statement in the finally block. Simply put, the program tries to return true but finally it returns false.



Discarding the reason for abrupt completion is almost never what you want, because the original reason for abrupt completion might be important to the behavior of a program. It is especially difficult to understand the behavior of a program that executes a break, continue, or return statement in a TRy block only to have the statement's behavior vetoed by a finally block.



In summary, every finally block should complete normally, barring an unchecked exception. Never exit a finally block with a return, break, continue, or tHRow, and never allow a checked exception to propagate out of a finally block.



For language designers, finally blocks should perhaps be required to complete normally in the absence of unchecked exceptions. Toward this end, a TRy-finally construct would require that the finally block can complete normally [JLS 14.21]. A return, break, or continue statement that transfers control out of a finally block would be disallowed, as would any statement that could cause a checked exception to propagate out of the finally block.

Son of Looper

Son of Looper

Provide a declaration for i that turns this loop into an infinite loop:

while (i != i + 0) {

}



Unlike previous loopers, you must not use floating-point in your answer. In other words, you must not declare i to be of type double or float.



 



Solution : Son of Looper


Like the previous puzzle, this one seems impossible at first glance. After all, a number is always equal to itself plus 0, and you were forbidden from using floating-point, so you can't use NaN. There is no NaN equivalent for the integral types. What gives?



The inescapable conclusion is that the type of i must be non-numeric, and therein lies the solution. The only non-numeric type for which the + operator is defined is String. The + operator is overloaded: For the String type, it performs not addition but string concatenation. If one operand in the concatenation is of some type other than String, that operand is converted to a string prior to concatenation [JLS 15.18.1].



In fact, i can be initialized to any value so long as it is of type String; for example:




String i = "Buy seventeen copies of Effective Java!";



The int value 0 is converted to the String value "0" and appended to the blatant plug. The resulting string is not equal to the original as computed by the equals method, so it certainly can't be identical, as computed by the == operator. Therefore, the boolean expression (i != i + 0) evaluates to TRue and the loop never terminates.



In summary, operator overloading can be very misleading. The plus sign in the puzzle looks like addition, but it is made to perform string concatenation by choosing the correct type for the variable i, which is String. The puzzle is made even more misleading because the variable is named i, a name that is usually reserved for integer variables. Good variable, method, and class names are at least as important to program readability as good comments.

Bride of Looper

Bride of Looper

Provide a declaration for i that turns this loop into an infinite loop:

while (i != i) {

}






Solution : Bride of Looper


This looper is perhaps even more puzzling than the previous one. It really seems that it ought to terminate immediately, no matter what declaration precedes it. A number is always equal to itself, right?



Right, but IEEE 754 floating-point arithmetic reserves a special value to represent a quantity that is not a number [IEEE-754]. This value, known as NaN (short for "Not a Number"), is the value of all floating-point computations that do not have well-defined numeric values, such as 0.0 / 0.0. The specification says that NaN is not equal to any floating-point value, including itself [JLS 15.21.1]. Therefore, if i is initialized to NaN before the loop starts, the termination test (i != i) evaluates to TRue, and the loop never terminates. Strange but true.



You can initialize i with any floating-point arithmetic expression that evaluates to NaN; for example:




double i = 0.0 / 0.0;



Once again, you can add clarity by using a constant that is provided for you by the standard libraries:




double i = Double.NaN;



NaN holds other similar surprises. Any floating-point operation evaluates to NaN if one or more of its operands are NaN. This rule is perfectly reasonable, but it has strange consequences. For example, this program prints false:




class Test {

public static void main(String[] args) {

double i = 0.0 / 0.0;

System.out.println(i - i == 0);

}

}



The principle underlying the rules for computing with NaN is that once it generates NaN, a computation is damaged, and no further computation can repair the damage. The NaN value is intended to allow a damaged computation to proceed to a point where it is convenient to deal with the situation.



In summary, the float and double types have a special NaN value to represent a quantity that is not a number. The rules for computations involving NaN are simple and sensible, but the consequences of these rules can be counterintuitive.

Looper

Looper

This puzzle and the five that follow turn the tables on you. Instead of showing some code and asking what it does, they make you write the code, albeit in small amounts. These puzzles are called loopers. You will be shown a loop that looks as though it ought to terminate quickly, and it will be your job to come up with a variable declaration that makes it loop indefinitely, when placed immediately above the loop. For example, consider this for loop:

for (int i = start; i <= start + 1; i++) {

}



It looks as though it should run for only two iterations, but it can be made to loop indefinitely by taking advantage of the overflow behavior illustrated in (in the loop). The following declaration does the trick:




int start = Integer.MAX_VALUE - 1;



Now it's your turn. What declaration turns this loop into an infinite loop?




while (i == i + 1) {

}






Solution : Looper


Looking at the while loop, it really seems as though it ought to terminate immediately. A number is never equal to itself plus 1, right? Well, what if the number is infinity? Java mandates the use of IEEE 754 floating-point arithmetic [IEEE-754], which lets you represent infinity as a double or float. As we learned in school, infinity plus 1 is still infinity. If i is initialized to infinity before the loop starts, the termination test (i == i + 1) evaluates to true, and the loop never terminates.



You can initialize i with any floating-point arithmetic expression that evaluates to infinity; for example:




double i = 1.0 / 0.0;



Better yet, you can take advantage of a constant that is provided for you by the standard libraries:




double i = Double.POSITIVE_INFINITY;



In fact, you don't have to initialize i to infinity to make the loop spin forever. Any sufficiently large floating-point value will do; for example:



double i = 1.0e40;


This works because the larger a floating-point value, the larger the distance between the value and its successor. This distribution of floating-point values is a consequence of their representation with a fixed number of significant bits. Adding 1 to a floating-point value that is sufficiently large will not change the value, because it doesn't "bridge the gap" to its successor.



Floating-point operations return the floating-point value that is closest to their exact mathematical result. Once the distance between adjacent floating-point values is greater than 2, adding 1 to a floating-point value will have no effect, because the half-way point between values won't be reached. For the float type, the least magnitude beyond which adding 1 will have no effect is 225, or 33,554,432; for the double type, it is 254, or approximately 1.8 x 1016.



The distance between adjacent floating-point values is called an ulp, which is an acronym for unit in the last place. In release 5.0, the Math.ulp method was introduced to calculate the ulp of a float or double value.



In summary, it is possible to represent infinity as a double or a float. Most people find this somewhat surprising the first time they hear of it, perhaps because you can't represent infinity by using any of the integral types. Second, adding a small floating-point value to a large one will not change the large value. This too may be counterintuitive, as it isn't true for the real numbers. It is worth remembering that binary floating-point arithmetic is only an approximation to real arithmetic.

Shifty i's

Shifty i's

Like the program in the (In the loop), this one contains a loop that keeps track of how many iterations it takes to terminate. Unlike that program, this one uses the left-shift operator (<<). As usual, your job is to figure out what the program prints. When you read it, remember that Java uses two's-complement binary arithmetic, so the representation of -1 in any signed integral type (byte, short, int, or long) has all its bits set:


public class Shifty {

public static void main(String[] args) {

int i = 0;

while (-1 << i != 0)

i++;

System.out.println(i);

}

}



Solution : Shifty i's

The constant -1 is the int value with all 32 bits set (0xffffffff). The left-shift operator shifts zeroes in from the right to fill the low-order bits vacated by the shift, so the expression (-1 << i) has its rightmost i bits set to 0 and the remaining 32 - i bits set to 1. Clearly, the loop completes 32 iterations, as -1 << i is unequal to 0 for any i less than 32. You might expect the termination test to return false when i is 32, causing the program to print 32, but it doesn't print 32. In fact, it doesn't print anything but goes into an infinite loop.

The problem is that (-1 << 32) is equal to -1 rather than 0, because shift operators use only the five low-order bits of their right operand as the shift distance, or six bits if the left operand is a long [JLS 15.19]. This applies to all three shift operators: <<, >>, and >>>. The shift distance is always between 0 and 31, or 0 and 63 if the left operand is a long. It is calculated mod 32, or mod 64 if the left operand is a long. Attempting to shift an int value 32 bits or a long value 64 bits just returns the value itself. There is no shift distance that discards all 32 bits of an int value or all 64 bits of a long value.

Luckily, there is an easy way to fix the problem. Instead of repeatedly shifting -1 by a different shift distance, save the result of the previous shift operation and shift it one more bit to the left on each iteration. This version of the program prints 32 as expected:

public class Shifty {

public static void main(String[] args) {

int distance = 0;

for (int val = -1; val != 0; val <<= 1)

distance++;

System.out.println(distance);

}

}


The fixed program illustrates a general principle: Shift distances should, if possible, be constants. If the shift distance is staring you in the face, you are much less likely to exceed 31 or, if the left operand is a long, 63. Of course, it isn't always possible to use a constant shift distance. When you must use a nonconstant shift distance, make sure that your program can cope with this problematic case or does not encounter it.

There is another surprising consequence of the aforementioned behavior of shift operators. Many programmers expect a right-shift operator with a negative shift distance to function as a left shift and vice-versa. This is not the case. A right shift always functions as a right shift, and a left shift always functions as a left shift. Negative shift distances are made positive by lopping off all but the five low-order bits—six bits if the left operand is a long. So, for example, shifting an int to the left with a shift distance of -1 has the effect of shifting it 31 bits to the left.

In summary, shift distances are calculated mod 32 or, if the left operand is a long, mod 64. It is therefore impossible to shift away an entire value by using any shift operator or distance. Also, it is impossible to perform a left shift with a right-shift operator or vice-versa. Use a constant shift distance if possible, and exercise care if the shift distance can't be made constant.

Language designers should perhaps consider restricting shift distances to the range from 0 to the type size in bits and changing the semantics of shifting a value by the type size to return 0. Although this would avoid the confusion illustrated by this puzzle, it could have negative performance consequences; Java's semantics for the shift operators are those of the shift instructions on many processors.

In the Loop

In the Loop

The following program counts the number of iterations of a loop and prints the count when the loop terminates. What does it print?

public class InTheLoop {

public static final int END = Integer.MAX_VALUE;

public static final int START = END - 100;



public static void main(String[] args) {

int count = 0;

for (int i = START; i <= END; i++)

count++;

System.out.println(count);

}

}



Solution : In the Loop


If you don't look at the program very carefully, you might think that it prints 100; after all, END is 100 more than START. If you look a bit more carefully, you will see that the program doesn't use the typical loop idiom. Most loops continue as long as the loop index is less than the end value, but this one continues as long as the index is less than or equal to the end value. So it prints 101, right? Well, no. If you ran the program, you found that it prints nothing at all. Worse, it keeps running until you kill it. It never gets a chance to print count, because it's stuck in an infinite loop.



The problem is that the loop continues as long as the loop index (i) is less than or equal to Integer.MAX_VALUE, but all int variables are always less than or equal to Integer.MAX_VALUE. It is, after all, defined to be the highest int value in existence. When i gets to Integer.MAX_VALUE and is incremented, it silently wraps around to Integer.MIN_VALUE.



If you need a loop that iterates near the boundaries of the int values, you are better off using a long variable as the loop index. Simply changing the type of the loop index from int to long solves the problem, causing the program to print 101 as expected:




for (long i = START; i <= END; i++)



More generally, the lesson here is that ints are not integers. Whenever you use an integral type, be aware of the boundary conditions. What happens if the value underflows or overflows? Often it is best to use a larger type. (The integral types are byte, char, short, int, and long.)



It is possible to solve this problem without resorting to a long index variable, but it's not pretty:




int i = START;

do {

count++;

} while (i++ != END);



Given the paramount importance of clarity and simplicity, it is almost always better to use a long index under these circumstances, with perhaps one exception: If you are iterating over all (or nearly all) the int values, it's about twice as fast to stick with an int. Here is an idiom to apply a function f to all four billion int values:




// Apply the function f to all four billion int values

int i = Integer.MIN_VALUE;

do {

f(i);

} while (i++ != Integer.MAX_VALUE);



 


The lesson for language designers is : It may be worth considering support for arithmetic that does not overflow silently. Also, it may be worth providing support for loops designed specifically to iterate over ranges of integral values, as many languages do.

Monday, March 1, 2010

Inclement Increment

Inclement Increment

This program increments a variable repeatedly and then prints its value. What is it?

public class Increment {

public static void main(String[] args) {

int j = 0;

for (int i = 0; i < 100; i++)

j = j++;

System.out.println(j);

}

}



Solution : Inclement Increment

At first glance, the program might appear to print 100. After all, it does increment j 100 times. Perhaps surprisingly, it does not print 100 but 0. All that incrementing gets us nowhere. Why?

As the puzzle's title suggests, the problem lies in the statement that does the increment:

j = j++;


Presumably, the author of the statement meant for it to add 1 to the value of j, which is what the expression j++ does. Unfortunately, the author inadvertently assigned the value of this expression back to j. When placed after a variable, the ++ operator functions as the postfix increment operator [JLS 15.14.2]: The value of the expression j++ is the original value of j before it was incremented. Therefore, the preceding assignment first saves the value of j, then sets j to its value plus 1, and, finally, resets j back to its original value. In other words, the assignment is equivalent to this sequence of statements:

int tmp = j;

j = j + 1;

j = tmp;


The program repeats this process 100 times, after which the value of j is exactly what it was before the loop, or 0.

Fixing the program is as simple as removing the extraneous assignment from the loop, leaving:

for (int i = 0; i < 100; i++)

j++;


With this modification, the program prints 100 as expected.

The lesson is this the same as in Swap Meat: Do not assign to the same variable more than once in a single expression. An expression containing multiple assignments to the same variable is confusing and seldom does what you want.

A Big Delight in Every Byte

A Big Delight in Every Byte

This program loops through the byte values, looking for a certain value. What does the program print?

public class BigDelight {

public static void main(String[] args) {

for (byte b = Byte.MIN_VALUE; b < Byte.MAX_VALUE; b++) {

if (b == 0x90)

System.out.print("Joy!");

}

}

}






Solution : A Big Delight in Every Byte


The loop iterates over all the byte values except Byte.MAX_VALUE, looking for Ox90. This value fits in a byte and is not equal to Byte.MAX_VALUE, so you might think that the loop would hit it once and print Joy! on that iteration. Looks can be deceiving. If you ran the program, you found that it prints nothing. What happened?



Simply put, Ox90 is an int constant that is outside the range of byte values. This is counterintuitive because Ox90 is a two-digit hexadecimal literal. Each hex digit takes up 4 bits, so the entire value takes up 8 bits, or 1 byte. The problem is that byte is a signed type. The constant 0x90 is a positive int value of 8 bits with the highest bit set. Legal byte values range from -128 to +127, but the int constant 0x90 is equal to +144.



The comparison of a byte to an int is a mixed-type comparison. If you think of byte values as apples and int values as oranges, the program is comparing apples to oranges. Consider the expression ((byte)0x90 == 0x90). Appearances notwithstanding, it evaluates to false. To compare the byte value (byte)0x90 to the int value 0x90, Java promotes the byte to an int with a widening primitive conversion [JLS 5.1.2] and compares the two int values. Because byte is a signed type, the conversion performs sign extension, promoting negative byte values to numerically equal int values. In this case, the conversion promotes (byte)0x90 to the int value -112, which is unequal to the int value 0x90, or +144.



Mixed-type comparisons are always confusing because the system is forced to promote one operand to match the type of the other. The conversion is invisible and may not yield the results that you expect. There are several ways to avoid mixed-type comparisons. To pursue our fruit metaphor, you can choose to compare apples to apples or oranges to oranges. You can cast the int to a byte, after which you will be comparing one byte value to another:




if (b == (byte)0x90)

System.out.println("Joy!");



Alternatively, you can convert the byte to an int, suppressing sign extension with a mask, after which you will be comparing one int value to another:




if ((b & 0xff) == 0x90)

System.out.println("Joy!");



Either of these solutions works, but the best way to avoid this kind of problem is to move the constant value outside the loop and into a constant declaration.



Here is a first attempt:




public class BigDelight {

private static final byte TARGET = 0x90; // Broken!

public static void main(String[] args) {

for (byte b = Byte.MIN_VALUE; b < Byte.MAX_VALUE; b++)

if (b == TARGET)

System.out.print("Joy!");

}

}



Unfortunately, it doesn't compile. The constant declaration is broken, and the compiler will tell you the problem: 0x90 is not a valid value for the type byte. If you fix the declaration as follows, the program will work fine:




private static final byte TARGET = (byte)0x90;



To summarize: Avoid mixed-type comparisons, because they are inherently confusing (The Joy of Hex). To help achieve this goal, use declared constants in place of "magic numbers." You already knew that this was a good idea; it documents the meanings of constants, centralizes their definitions, and eliminates duplicate definitions. Now you know that it also forces you to give each constant a type appropriate for its use, eliminating one source of mixed-type comparisons.



The lesson for language designers is that sign extension of byte values is a common source of bugs and confusion. The masking that is required in order to suppress sign extension clutters programs, making them less readable. Therefore, the byte type should be unsigned. Also, consider providing literals for all primitive types, reducing the need for error-prone type conversions

Tweedledee

Tweedledee

Contrariwise, provide declarations for the variables x and i such that this is a legal statement:

x = x + i;



but this is not:




x += i;



At first glance, this puzzle might appear to be the same as the previous one. Rest assured, it's different. The two puzzles are opposite in terms of which statement must be legal and which must be illegal.





Solution : Tweedledee


Like the previous puzzle, this one depends on the details of the specification for compound assignment operators. That is where the similarity ends. Based on the previous puzzle, you might think that compound assignment operators are less restrictive than the simple assignment operator. This is generally true, but the simple assignment operator is more permissive in one area.



Compound assignment operators require both operands to be primitives, such as int, or boxed primitives, such as Integer, with one exception: The += operator allows its right-hand operand to be of any type if the variable on the left-hand side is of type String, in which case the operator performs string concatenation [JLS 15.26.2]. The simple assignment operator (=) is much less picky when it comes to allowing object reference types on the left-hand side: You can use them to your heart's content so long as the expression on the right-hand side is assignment compatible with the variable on the left [JLS 5.2].



You can exploit this difference to solve the puzzle. To perform string concatenation with the += operator, you must declare the variable on its left-hand side to be of type String. Using the simple assignment operator, the results of a string concatenation can be stored in a variable of type Object.



To make this concrete and to provide a solution to the puzzle, suppose that we precede the puzzle's two assignment expressions with these declarations:




Object x = "Buy ";

String i = "Effective Java!";



The simple assignment is legal because x + i is of type String, and String is assignment compatible with Object:




x = x + i;



The compound assignment is illegal because the left-hand side has an object reference type other than String:




x += i;



This puzzle has little in the way of a lesson for programmers. For language designers, the compound assignment operator for addition could allow the left-hand side to be of type Object if the right-hand side were of type String. This change would eliminate the counterintuitive behavior illustrated by this puzzle.

Tweedledum

Tweedledum

Now it's your turn to write some code. On the bright side, you have to write only two lines for this puzzle and two lines for the next. How hard could that be? Provide declarations for the variables x and i such that this is a legal statement:

x += i;


but this is not:



x = x + i;






Solution : Tweedledum


Many programmers think that the first statement in this puzzle (x += i) is simply a shorthand for the second (x = x + i). This isn't quite true. Both of these statements are assignment expressions [JLS 15.26]. The second statement uses the simple assignment operator (=), whereas the first uses a compound assignment operator. (The compound assignment operators are +=, -=, *=, /=, %=, <<=, >>=, >>>=, &=, ^=, and |=.) The Java language specification says that the compound assignment E1 op= E2 is equivalent to the simple assignment E1 = (T) ((E1) op (E2)), where T is the type of E1, except that E1 is evaluated only once [JLS 15.26.2].



In other words, compound assignment expressions automatically cast the result of the computation they perform to the type of the variable on their left-hand side. If the type of the result is identical to the type of the variable, the cast has no effect. If, however, the type of the result is wider than that of the variable, the compound assignment operator performs a silent narrowing primitive conversion [JLS 5.1.3]. Attempting to perform the equivalent simple assignment would generate a compilation error, with good reason.



To make this concrete and to provide a solution to the puzzle, suppose that we precede the puzzle's two assignment expressions with these declarations:




short x = 0;

int i = 123456;



The compound assignment compiles without error:




x += i; // Contains a hidden cast!



You might expect the value of x to be 123,456 after this statement executes, but it isn't; it's –7,616. The int value 123456 is too big to fit in a short. The automatically generated cast silently lops off the two high-order bytes of the int value, which is probably not what you want.



The corresponding simple assignment is illegal because it attempts to assign an int value to a short variable, which requires an explicit cast:




x = x + i; // Won't compile - "possible loss of precision"



It should be apparent that compound assignment expressions can be dangerous. To avoid unpleasant surprises, do not use compound assignment operators on variables of type byte, short, or char. When using compound assignment operators on variables of type int, ensure that the expression on the right-hand side is not of type long, float, or double. When using compound assignment operators on variables of type float, ensure that the expression on the right-hand side is not of type double. These rules are sufficient to prevent the compiler from generating dangerous narrowing casts.



In summary, compound assignment operators silently generate a cast. If the type of the result of the computation is wider than that of the variable, the generated cast is a dangerous narrowing cast. Such casts can silently discard precision or magnitude. For language designers, it is probably a mistake for compound assignment operators to generate invisible casts; compound assignments where the variable has a narrower type than the result of the computation should probably be illegal.

Dos Equis

Dos Equis

This puzzle tests your knowledge of the conditional operator, better known as the "question mark colon operator." What does the following program print?

public class DosEquis {

public static void main(String[] args) {

char x = 'X';

int i = 0;

System.out.print(true ? x : 0);

System.out.print(false ? i : x);

}

}






Solution : Dos Equis


The program consists of two variable declarations and two print statements. The first print statement evaluates the conditional expression (true ? x : 0) and prints the result. The result is the value of the char variable x, which is 'X'. The second print statement evaluates the conditional expression (false ? i : x) and prints the result. Again the result is the value of x, which is still 'X', so the program ought to print XX. If you ran the program, however, you found that it prints X88. This behavior seems strange. The first print statement prints X and the second prints 88. What accounts for their different behavior?



The answer lies in a dark corner of the specification for the conditional operator [JLS 15.25]. Note that the types of the second and third operands are different from each other in both of the conditional expressions: x is of type char, whereas 0 and i are both of type int. As mentioned in the solution to The joy of hex, mixed-type computation can be confusing. Nowhere is this more apparent than in conditional expressions. You might think that the result types of the two conditional expressions in this program would be identical, as their operand types are identical, though reversed, but it isn't so.



The rules for determining the result type of a conditional expression are too long and complex to reproduce in their entirety, but here are three key points.





  1. If the second and third operands have the same type, that is the type of the conditional expression. In other words, you can avoid the whole mess by steering clear of mixed-type computation.





  2. If one of the operands is of type T where T is byte, short, or char and the other operand is a constant expression of type int whose value is representable in type T, the type of the conditional expression is T.





  3. Otherwise, binary numeric promotion is applied to the operand types, and the type of the conditional expression is the promoted type of the second and third operands.





Points 2 and 3 are the key to this puzzle. In both of the two conditional expressions in the program, one operand is of type char and the other is of type int. In both expressions, the value of the int operand is 0, which is representable as a char. Only the int operand in the first expression, however, is constant (0); the int operand in the second expression is variable (i). Therefore, point 2 applies to the first expression and its return type is char. Point 3 applies to the second conditional expression, and its return type is the result of applying binary numeric promotion to int and char, which is int [JLS 5.6.2].



The type of the conditional expression determines which overloading of the print method is invoked. For the first expression, PrintStream.print(char) is invoked; for the second, PrintStream.print(int). The former overloading prints the value of the variable x as a Unicode character (X), whereas the latter prints it as a decimal integer (88). The mystery is solved.



Putting the final modifier on the declaration for i would turn i into a constant expression, causing the program to print XX, but it would still be confusing. To eliminate the confusion, it is best to change the type of i from int to char, avoiding the mixed-type computation.



In summary, it is generally best to use the same type for the second and third operands in conditional expressions. Otherwise, you and the readers of your program must have a thorough understanding of the complex specification for the behavior of these expressions.



For language designers, perhaps it is possible to design a conditional operator that sacrifices some flexibility for increased simplicity. For example, it might be reasonable to demand that the second and third operands be of the same type. Alternatively, the conditional operator could be defined without special treatment for constants. To make these alternatives more palatable to programmers, a syntax could be provided for expressing literals of all primitive types. This may be a good idea in its own right, as it adds to the consistency and completeness of the language and reduces the need for casts.

Swap Meat

Swap Meat

This program uses the compound assignment operator for exclusive OR. The technique that it illustrates is part of the programming folklore. What does it print?

public class CleverSwap {

public static void main(String[] args) {

int x = 1984; // (0x7c0)

int y = 2001; // (0x7d1)

x ^= y ^= x ^= y;

System.out.println("x = " + x + "; y = " + y);

}

}






Solution : Swap Meat


As its name implies, this program is supposed to swap the values of the variables x and y. It you ran it, you found that it fails miserably, printing x = 0; y = 1984.



The obvious way to swap two variables is to use a temporary variable:




int tmp = x;

x = y;

y = tmp;



Long ago, when central processing units had few registers, it was discovered that one could avoid the use of a temporary variable by taking advantage of the property of the exclusive OR operator (^) that (x ^ y ^ x) == y:




// Swaps variables without a temporary - Don't do this!

x = x ^ y;

y = y ^ x;

x = y ^ x;



Even back in those days, this technique was seldom justified. Now that CPUs have many registers, it is never justified. Like most "clever" code, it is far less clear than its naive counterpart and far slower. Still, some programmers persist in using it. Worse, they complicate matters by using the idiom illustrated in this puzzle, which combines the three exclusive OR operations into a single statement.



This idiom was used in the C programming language and from there made its way into C++ but is not guaranteed to work in either of these languages. It is guaranteed not to work in Java. The Java language specification says that operands of operators are evaluated from left to right [JLS 15.7]. To evaluate the expression x ^= expr, the value of x is sampled before expr is evaluated, and the exclusive OR of these two values is assigned to the variable x [JLS 15.26.2]. In the CleverSwap program, the variable x is sampled twice—once for each appearance in the expression—but both samplings occur before any assignments.



The following code snippet describes the behavior of the broken swap idiom in more detail and explains the output that we observed:




// The actual behavior of x ^= y ^= x ^= y in Java

int tmp1 = x; // First appearance of x in the expression

int tmp2 = y; // First appearance of y

int tmp3 = x ^ y; // Compute x ^ y

x = tmp3; // Last assignment: Store x ^ y in x

y = tmp2 ^ tmp3; // 2nd assignment: Store original x value in y

x = tmp1 ^ y; // First assignment: Store 0 in x



In C and C++, the order of expression evaluation is not specified. When compiling the expression x ^= expr, many C and C++ compilers sample the value of x after evaluating expr, which makes the idiom work. Although it may work, it runs afoul of the C/C++ rule that you must not modify a variable repeatedly between successive sequence points. Therefore, the behavior of this idiom is undefined even in C and C++.



For what it's worth, it is possible to write a Java expression that swaps the contents of two variables without using a temporary. It is both ugly and useless:




// Rube Goldberg would approve, but don't ever do this!

y = (x ^= (y ^= x)) ^ y;



The lesson is simple: Do not assign to the same variable more than once in a single expression. Expressions containing multiple assignments to the same variable are confusing and seldom do what you want. Even expressions that assign to multiple variables are suspect. More generally, avoid clever programming tricks. They are bug-prone, difficult to maintain, and often run more slowly than the straightforward code they replace [EJ Item 37].



Language designers might consider prohibiting multiple assignments to the same variable in one expression, but it would not be feasible to enforce this prohibition in the general case, because of aliasing. For example, consider the expression x = a[i]++ - a[j]++. Does it increment the same variable twice? That depends on the values of i and j at the time the expression is evaluated, and there is no way for the compiler to determine this in general.

Multicast

Multicast

Casts are used to convert a value from one type to another. This program uses three casts in succession. What does it print?

public class Multicast {

public static void main(String[] args) {

System.out.println((int) (char) (byte) -1);

}

}






Solution : Multicast


This program is confusing any way you slice it. It starts with the int value -1, then casts the int to a byte, then to a char, and finally back to an int. The first cast narrows the value from 32 bits down to 8, the second widens it from 8 bits to 16, and the final cast widens it from 16 bits back to 32. Does the value end up back where it started? If you ran the program, you found that it does not. It prints 65535, but why?



The program's behavior depends critically on the sign extension behavior of casts. Java uses two's-complement binary arithmetic, so the int value -1 has all 32 bits set. The cast from int to byte is straightforward. It performs a narrowing primitive conversion [JLS 5.1.3], which simply lops off all but the low-order 8 bits. This leaves a byte value with all 8 bits set, which (still) represents –1.



The cast from byte to char is trickier because byte is a signed type and char unsigned. It is usually possible to convert from one integral type to a wider one while preserving numerical value, but it is impossible to represent a negative byte value as a char. Therefore, the conversion from byte to char is not considered a widening primitive conversion [JLS 5.1.2], but a widening and narrowing primitive conversion [JLS 5.1.4]: The byte is converted to an int and the int to a char.



All of this may sound a bit complicated. Luckily, there is a simple rule that describes the sign extension behavior when converting from narrower integral types to wider: Sign extension is performed if the type of the original value is signed; zero extension if it is a char, regardless of the type to which it is being converted. Knowing this rule makes it easy to solve the puzzle.



Because byte is a signed type, sign extension occurs when converting the byte value –1 to a char. The resulting char value has all 16 bits set, so it is equal to 216 – 1, or 65,535. The cast from char to int is also a widening primitive conversion, so the rule tells us that zero extension is performed rather than sign extension. The resulting int value is 65535, which is just what the program prints.



Although there is a simple rule describing the sign extension behavior of widening primitive conversions between signed and unsigned integral types, it is best not to write programs that depend on it. If you are doing a widening conversion to or from a char, which is the only unsigned integral type, it is best to make your intentions explicit.



If you are converting from a char value c to a wider type and you don't want sign extension, consider using a bit mask for clarity, even though it isn't required:




int i = c & 0xffff;



Alternatively, write a comment describing the behavior of the conversion:




int i = c; // Sign extension is not performed



If you are converting from a char value c to a wider integral type and you want sign extension, cast the char to a short, which is the same width as a char but signed. Given the subtlety of this code, you should also write a comment:




int i = (short) c; // Cast causes sign extension



If you are converting from a byte value b to a char and you don't want sign extension, you must use a bit mask to suppress it. This is a common idiom, so no comment is necessary:




char c = (char) (b & 0xff);



If you are converting from a byte to a char and you want sign extension, write a comment:




char c = (char) b; // Sign extension is performed



The lesson is simple: If you can't tell what a program does by looking at it, it probably doesn't do what you want. Strive for clarity. Although a simple rule describes the sign extension behavior of widening conversions involving signed and unsigned integral types, most programmers don't know it. If your program depends on it, make your intentions clear.