The Java Explorer

Tips and insights on Java

  • Subscribe

  • If you find this blog useful, please enter your email address to subscribe and receive notifications of new posts by email.

    Join 39 other followers

Archive for the ‘Language’ Category

Java Quiz

Posted by Eyal Schneider on September 17, 2009

This time I posted a 20 questions quiz, developed for testing general Java skills.
Most of the questions address fundamental topics in Java(5), but the test is not a trivial one.  The right answers plus their explanations can be found on the bottom. You are welcome to add your comments.

Enjoy, and good luck!

Question 1

public class CrazyCount {
    private static volatile int count = 0;

    public static void main(String[] args) {
        for(int i=0;i<1000;i++)
            new Thread(new Runnable(){
                public void run() {
	           count++;
                }
            }).start();

        //.....
    }
}

What will be the value of count after all 1000 threads finish their work?

(a) Garbage, because the writes are not synchronized
(b) A value between 1 and 1000
(c) Exactly 1000
(d) At least 1000
Answer

Question 2

Consider the following multi threaded producer/consumer model:

 public class ProducerConsumer {
    private Job currentJob = null;

    public synchronized void addJob(Job job) throws InterruptedException{
        while (currentJob!=null)
            this.wait();
        currentJob=job;
    }

    public synchronized Job consumeJob(){
        Job res = currentJob;
        res.process();
        currentJob=null;
        this.notify();
        return res;
    }
}

Which of the following is correct?

(a) addJob will wait till the current job is executed, but consumeJob will never block.
(b) Jobs will be executed in the exact order in which they are added with addJob.
(c) This code may not work because of deadlocks
(d) ‘while’ in addJob can be replaced by ‘if’, without changing the behavior.
Answer

Question 3

Consider the following Singleton design pattern implementation:

public class ConnectionsMgr {
    private static ConnectionsMgr instance = null;

    public static ConnectionsMgr getInstance(){
        if (instance==null){
	    synchronized(ConnectionsMgr.class){
		if (instance==null)
		    instance = new ConnectionsMgr();
	    }
    	}
	return instance;
    }

    //...
}

Why is this implementation problematic?

(a) An uninitialized ConnectionsMgr object may be returned
(b) Synchronizing on ConnectionsMgr.class is not allowed
(c) The instance may be created more than once
Answer

Question 4

Which of the following statements regarding the final reserved word is correct?

(a) A final method can not be overriden by subclasses, and a final class can not be subclassed
(b) A final data member must be given a value in its declaration line
(c) A local variable declared as final can still be mutated using setter methods
(d) (a) and (c) are correct
Answer

Question 5

public static void main(String[] args) {
    try{
	String s = null;
	s=s.substring(10);
    }
    catch(Exception e){
	System.out.println("Caught exception!");
    }
    catch(RuntimeException e){
	System.out.println("Caught a runtime exception!");
    }
}

This code:

(a) Displays “Caught exception!” when executed
(b) Displays “Caught runtime exception!” when executed
(c) Runs without throwing an exception
(d) Does not compile
Answer

Question 6

Which of the following statements regarding exceptions is correct?

(a) IOException can be thrown without the need to declare it in the method header
(b) catch(Exception) will catch OutOfMemoryError
(c) ClassCastException can be thrown without the need to declare it in the method header
(d) (b) and (c) are correct
Answer

Question 7

Which of the following is the preferred way to stop a thread?

(a) Calling the Thread’s interrupt() method
(b) Calling interrupt() and then stop()
(c) Calling the stop() method
(d) Calling join() to wait for the thread to end
Answer

Question 8

public class Swap {
    public static void swapStrings(String x, String y){
	String temp = x;
	x=y;
	y=temp;
    }

    public static void main(String[] args) {
	String a = "1";
	String b = "2";
	swapStrings(a, b);
	System.out.println("a="+a+" ,b="+b);
    }
}

What will be the output when executing this main?

(a) An exception will be thrown
(b) “a=2 ,b=1”
(c) “a=1 ,b=2” because strings are immutable
(d) “a=1 ,b=2” because Java passes parameters by value
Answer

Question 9

public static void main(String[] args) {
    ArrayList<Point> list = new ArrayList<Point>();
    list.add(new Point(100,200));

    ArrayList<Point> listCopy = (ArrayList<Point>) list.clone();

    listCopy.get(0).setLocation(150,250);

    System.out.println(list);
    System.out.println(listCopy);
}

What will be the output of this main?

(a) [java.awt.Point[x=100,y=200]]
[java.awt.Point[x=100,y=200]]

(b) [java.awt.Point[x=150,y=250]]
[java.awt.Point[x=100,y=200]]

(c) [java.awt.Point[x=100,y=200]]
[java.awt.Point[x=150,y=250]]

(d) [java.awt.Point[x=150,y=250]]
[java.awt.Point[x=150,y=250]]
Answer

Question 10

Assume that class B extends class A.
Consider a method that is declared as follows:  public void callMe(List<A> l)

Which of the following data types can be passed as parameters to callMe(..)?
(a) List<B>
(b) ArrayList<B>
(c) ArrayList<A>
(d) All answers are correct
Answer

Question 11

Assumes that class B extends class A.

public void callMe(List<? extends A> l){
    l.add(new A());
    l.add(new B());
}

This method:

(a) Compiles, but with a warning
(b) Does not compile
(c) Runs correctly
(d) May cause ClassCastException
Answer

Question 12

What will be the output of the following code?

class Base {
    int i = 10;

    public Base(){
        System.out.println(get());
    }

    public int get(){
        return i;
    }

}
public class Derived extends Base{
    int j = 20;

    public int get(){
        return j;
    }

    public static void main(String argv[]){
        Base b = new Derived();
    }
}

(a) 0
(b) 10
(c) 20
(d) None of the above
Answer

Question 13

What will be the output of the following code?

class Base {
    protected int i = 10;

    public int get(){
        return i;
    }
}

public class Derived extends Base{
    protected int i = 20;

    public int get(){
        return i;
    }

    public static void main(String argv[])
    {
        Base b = new Derived();
        System.out.println(b.i);
        System.out.println(b.get());
    }
}

(a) 10
10

(b) 10
20

(c) 20
10

(d)
20
20
Answer

Question 14

What is the output of the following code?

String s1 = new String("Test");
String s2 = "Test";
if (s1==s2)
    System.out.println("Same");
if (s1.equals(s2))
    System.out.println("Equals");

(a) Same
(b) Equals
(c) Same
Equals
(d) No output
Answer

Question 15

What is the output of the following code?

class Parent{
    private void f(){
        System.out.println("Parent.f()");
    }

    public void g(){
        System.out.println("Parent.g()");
        f();
    }
}

public class Child extends Parent{
    public void f(){
        System.out.println("Child.f()");
    }

    public static void main(String args[]){
        Parent p = new Child();
        p.g();
    }
}

(a) Parent.g()
Child.f()
(b) Parent.g()
Parent.f()
(c) The code does not compile
(d) An exception is thrown
Answer

Question 16

Consider the following overloading scenario:

public class Overloader{
    public static void read(String s){
        System.out.println("read(String)");
    }

    public static void read(Integer i){
        System.out.println("read(Integer)");
    }

    public static void read(Object o){
        System.out.println("read(Object)");
    }

    public static void main(String args[]){
        Object s = new String("Java");
        Integer i = 10;
//      Overloader.read(s);
//      Overloader.read(i);
//      Overloader.read(null);
    }
}

What would be the output of each of the 3 read commands in comment?

(a) read(s) prints “read(String)”
read(i) prints “read(Integer)”
read(null) prints “read(Object)”

(b) read(s) prints “read(Object)”
read(i) prints “read(Integer)”
read(null) prints “read(Object)”

(c) read(s) prints “read(Object)”
read(i) prints “read(Integer)”
read(null) does not compile

(d) None of the above
Answer

Question 17

Which of the following statements is correct?

(a) A daemon thread is terminated when all non-daemon threads terminate
(b) A thread is created as a daemon thread if and only if it is created by a daemon thread
(c) Non daemon threads may keep the application from shutting down, even if the main thread is terminated.
(d) All of the above are correct
Answer

Question 18

class Parent{
    protected void x(){}
    public void y(){}
}

public class Child extends Parent{
    public void x(){}
    protected void y(){}
}

When compiling this code:
(a) It compiles successfully
(b) Compilation error – x can’t have its visibility increased
(c) Compilation error – y can not have its visibility reduced
(d) Compilation error – neither x nor y can have their visibility changed
Answer

Question 19

String s = new String("Wanna live forever!");
WeakReference<String> r1 = new WeakReference<String>(s);
SoftReference<String> r2 = new SoftReference<String>(s);
String s2 = r1.get();
s = null;

Assuming that no garbage collection took place, what is the reference strength of the string created at line #1, after these lines of code?
(a) Not referenced
(b) Weakly referenced
(c) Softly referenced
(d) Strongly referenced
Answer

Question 20

int x=0;
int y=0;
while(true){
    if ((++x==10) && (++y==10))
        return;
}

When executed, this code:
(a) Performs 10 iterations and ends
(b) Performs more than 10 iterations and ends
(c) Performs less than 10 iterations and ends
(d) Enters an infinite loop
Answer

Answers

1)  (b)
A race condition between threads may cause a a write to cancel other writes, thus multiple concurrent “incrementations” may result in a single incrementation.

2) (a)
(b) is incorrect, since there is no guarantee about the order in which waiting threads are awakened using Object.notify().
(d) is incorrect because when a producer thread is awakened, there is no guarantee that another producer thread was not awakened just before, setting the current job to another value.
Besides, Java documentation recommends always to use ‘while’ loops on wait() rather than ‘if’.

3) (a)
The line “instance=new ConnectionsMgr()” is not atomic. It results in multiple machine instructions, one of which is the reference assignment itself. Due to the Java memory model rules, this specific instruction is allowed to be reordered with respect to the other instructions. This reordering may cause the assignment to take effect before the object is initialized. Another thread calling getInstance() may therefore receive a non null reference to an uninitialized memory block.  See this article for more details.

4) (d)
An object data member or a local object variable declared as final can not change its address. However, the referenced object can be freely mutated.
(b) is not true because the member can be initialized in the constructor/s also.

5) (d)
RuntimeException derives from Exception, so the ordering of the catch blocks makes the second unreachable.

6) (c)
ClassCastException is an unchecked exception, so it does not need to be declared. IOException, however, is a checked exception, and you must either catch it or declare the method as “throws IOException”. OutOfMemoryError is a Throwable, but it derives from Error and not from Exception.

7)  (a)
Thread.stop() is a deprecated method that is not recommended for use. It stops a thread violently without guaranteeing anything about the integrity of the data manipulated by that thread. This may cause corrupt data to be viewed by other threads. Furthermore, there are some cases in which Thread.stop() will not terminate a thread.
Thread.interrupt() is preferred, but it relies on the code run by the thread to be friendly and react to the interruption.

8) (d)
Since Java passes parameters by value (not by reference!), there is no way to implement a swap method in Java. In C++ for example, it is possible, using references (&).

9) (d)
Collections such as java.util.ArrayList do not perform deep copying when cloned. Item references stay the same.

10) (c)
(a) and (b) are incorrect because if legal, they would have break the type safety. The method callMe could have added an instance of type A, and the caller now has a collection of both A’s and B’s, while it assumes that it has only elements of type B. See my previous post for more details.

11) (b)
Assume that C descends from B. The method callMe may receive as a parameter an object of type List<C>. If the additions were considered legal, this would result in a list defined as List<C> containing instances of super classes such as B and A. That breaks the generics type safety, since it will not protect the collection from an unexpected ClassCastException. See my previous post for more details.

12) (a)
Overriding methods that are called directly/indirectly by the superclass’ constructor should be done with care. If the overriden method uses data members belonging to the subclass, then they are still not initialized at that point! In this example, the data member is of type int, so the default initialization will give it a value 0.
For more explanations and a workaround for this problem, see posts 86 and 86b of the Java Specialists’ Newsletter.

13) (b)
Methods are invoked virtually – the exact method to be executed is determined at runtime according to the actual class of the object on which it was called. Data members, however, do not really override each other. Each class has its member i, and the one to be retrieved is determines at compile time, according to the declared class of the reference (in this case Base).

14) (b)
Using new String(…) forces Java to actually create a new instance of a string. Strings defined as literals (e.g. String x=”hello”), however, will always be represented by the same object reference at runtime.

15) (b)

16) (c)
The method signature to be invoked is determined at compile time. Therefore, it depends on the declared type and not the runtime type of the argument/s.
Regarding the null parameter – the compiler can not determine which signature is the correct one, since all the three reads are legitimate.

17) (d)

18) (c)
Reducing visibility of methods when overriding is not permitted.

19) (d)
s2 still hard-references the string.

20) (b)
Tricky thing… The Java language specification specifies that the second operand of && is never evaluated when the first operand evaluates to false (See this section). Consequently, only when x reaches 10 y will become 1. Later, x will overflow and reach 10 again, and so on; until both counters reach 10 and the loop will stop.

Posted in java, Language | Tagged: , , | 10 Comments »

Understanding Generics limitations

Posted by Eyal Schneider on August 14, 2009

Generics were introduced to Java in version 5 (JSR 14), and since then they became standard and very popular. Although there has been a great demand by developers for this feature, many are unsatisfied regarding HOW it was implemented. The design that was adopted has a huge impact on the syntax and semantics of this feature.

Java generics provides the following benefits:

  • Type safety
  • Less explicit casts
  • More declarative APIs

In this post I list some of the limitations of Generics. All of them are derived from two fundamental principles of the Java Generics design:

1) Erasure

Type parameters (e.g. String in  List<String>) are completely removed by the compiler. Formal type parameters (e.g. E in the source code of List) are replaced by their bound (usually Object). As a result, the bytecode has no generic information at all, consequently it is not available at runtime. Unlike C++, at runtime Java shares the same class for different parameterized instantiations of it. These facts have three interesting benefits:

1) JVM implementations prior to version 5 can theoretically stay unchanged in order to support Generics
2) When declaring a parameterized version of a class C, we don’t need the source code of the generic type C
3) The volume of the bytecode does not increase as we add more parameterized types of the same generic class

2) Type safety guarantee
According to Gilad Bracha, the Java Generics lead designer, if your entire application has been compiled without unchecked warnings, it is type safe. “Type safe” in this case means that there will be no unexpected class cast exception, i.e. if a ClassCastException occurs, then it must be caused by an explicit cast in the code. This principle is very important – we don’t want the implicit casts added when compiling generic code to raise runtime exceptions, since they would be hard to understand and fix. 

 

Formal type parameters usage

You can’t expect the formal type parameter to be used wherever a type name can fit. For example, instantiating an object from a formal type parameter is not allowed:

public class NonSense <T>{
    T obj = new T() ; //Illegal
}

Due to erasure, the compiler must generate code for NonSense class to be shared among all instantiations, but it doesn’t know anything about T at this point, and can’t assume anything.
The equivalent code in C++ IS allowed, since the compiler creates a dedicated class per parameterized type of NonSense.
Note that replacing the line above with List<T> obj = new ArrayList<T>() would compile, since the compiler generates code for creating an ArrayList, and the formal type parameter is erased.

For the same reasons, the following code does not compile:

public class Something <T> extends T{
}
 

Hierarchy of parameterized types

Two different instantiations (with different type parameter) of the same parameterized type don’t have any hierarchy relation. For example,  List<String> is not a List<Object>. The following code snippet illustrates what would have happened if this were allowed:

List<String> ls = new ArrayList<String>();
ls.add("one");
ls.add("two");
List<Object> lo = ls; //Illegal
lo.add(new Integer(3)); //The list ls is not homogeneous anymore!
 

Arrays

According to the intuition, arrays should follow similar rules as collections (such as ArrayList) do, when it comes to Generics. The reality is a little painful, however. It is not allowed to create arrays of elements which are parameterized types (e.g. new ArrayList<Strings>[10]). If it were allowed by the compiler, we could have done something like:
 

1.    ArrayList<Integer>[] arrOfIntLists = new ArrayList<Integer>[10]; //Illegal
2.    Object[] arrOfObj = arrOfIntLists;

3.    ArrayList<String> listOfStrings = new ArrayList<String>();
4.    listOfStrings.add("hello");
5.    arrOfObj[0] = listOfStrings;

6.    ArrayList<Integer> list = arrOfIntLists[0];
7.    Integer num = list.get(0);

What happens here?

1) An array of ArrayList of Integers is created.
2) arrOfObj now points to the same array. This is a legal up-cast, since any array is also an Object array. There is no warning in this line.
3,4,5) A list of Strings is created and added to arrOfObj. Note that the addition does not produce an ArrayStoreException, since the runtime type of the array components is simply ArrayList (Due to erasure), and that’s exactly what we are storing.
6) We retrieve the list at position 0 in arrOfIntLists. There is no ClassCastException yet because the implicit runtime cast is a cast to ArrayList, which is the correct class.
7) When trying to retrieve the first item of the list of integers, we fail with a ClassCastException, caused by the implicit cast to Integer.

If this code were legal, it means that the type safety guarantee is broken. The code compiles with no warnings, but at runtime it results in an unexpected ClassCastException in the last line. This happens because we managed to store a string list in an array of integer lists. 

So now we know why creating an ArrayList<Integer>[] is illegal.  But why does the compiler allow creating an instance of ArrayList<ArrayList<Integer>>? Shouldn’t it lead to the same type safety problem? The answer is no. If we convert the example above to the analogical version that uses ArrayList instead of arrays, the second line will not pass compilation, since ArrayList<ArrayList<Integer>> is not a subtype of ArrayList<Object> (See “Hierarchy of parameterized types” above).

The same phenomenon may occur with generic methods that receive generic arrays:

public class MyUtils{ 
    public static <T> void fill(T[] arr, T value){
        for(int i=0;i<arr.length;i++)
            arr[i]=value;
    } 
}

This mini-utility looks type safe, but it isn’t. Surprisingly, the following code compiles with no errors/warnings:

String[] strArr = new String[10];
fill(strArr,3);

Why does this happen? When a generic method is called this way, the compiler performs type inference for determining what type T stands for. In our case, this is done by inspecting the parameter types, and finding the lowest common type shared by them in the class hierarchy. With fill(strArr,”hi”), the type is obviously String. However, in the example above the most specific type shared by strArr and 3 (which is converted to an Integer) is Object. This causes the code to be legal, but to fail with ArrayStoreException on runtime. Technically, this is not a violation of the type safety guarantee explained in the introduction, because the guarantee deals only with ClassCastException.

There are two simple ways to avoid this problem. The first is to be more specific with the call:

MyUtils.<String>(strArr,3) //Now it does not compile

The second is to fix the method’s signature as follows:

public static <T,S extends T> void fill(T[] arr, S value) 
 

Latent Typing

In C++, the implementation of a parameterized type can assume anything about the type parameter/s. For example, the implementation of MyList<E> may call any method on E, and the availability of this method is checked against the actual type parameters of the different instantiations at compile time.  Java does not allow it.  Due to the generics design, the compiler has to generate the full bytecode of the generic class, regardless of the instantiations, so calls to methods that are not bound to any class/interface can not be compiled.

Therefore, in Java you are encouraged to declare explicitly all your assumptions on a type parameter. This is done using bounds. For example:

class DrawableSortedSet<T extends Comparable<T>,Drawable>{
....
}

This clearly makes the code more declarative, but proponents of Latent Typing argue that the extra declarations are not really needed for runtime type safety (C++ approach proves this), and also that the declarative approach may limit the programmer and force him to define new artificial interfaces containing the desired methods.  

 

Bounds restrictions

As explained before, bounds allow us to specify constraints on the type parameters being used, both in a generic class or a generic method. These prerequisites give us more freedom. For example, assume that we want a method that manipulates a list of numbers.  We start by the following generic method:

public void manipulate(List<Number> list){
  ....
}

The problem here is that List<Integer> can not be passed as parameter. Only List<Number> is allowed (see “Hierarchy of parameterized types” above). If we want to pass lists of any descendant class of Number, we should use bounds:

public <T extends Number> void manipulate(List<T> list){ 
    ....
}

Now we can pass List<Integer>, List<Float> and so on,  but we face a new limitation. While in the previous version of the method we could call list.add(new Integer(10)) or list.add(new Double(3.2)), now the compiler will not accept it, because it can’t guarantee that the addition maintains the type homogeneousness in the list. If addition of Integers were allowed, then calling the method with a variable declared as List<Float> may result with a new non Float item in the list, and this is a violation of the type safety guarantee.

 

Static data members

Generic classes are not allowed to have references to their type parameters from their static data members or methods. For example, the following is illegal:

public MyClass<T>{
    private static T value; //Illegal

    public static void analyze(List<T> list){ //Illegal
        ....
    }
}

C++ programmers who learn Java may be tempted to do it, because in C++ this is legal. Remember that unlike C++, Java uses the same class at runtime for MyClass<Integer>, MyClass<String> etc. Static members, by definition, are bound to the class rather than to the instance. It follows from these 2 facts that static members are actually shared by all instances of all generic instantiation of the same generic type. If the code above were allowed, type safety could not be guaranteed anymore. Imagine for example what happens when an instance of MyClass<Integer> stores an Integer in value, and then an instance of MyClass<String> retrieves it as a String.

 

Generic information at runtime 

Because of erasure, there is no sense in checking generic information at runtime. For example, the following is illegal:

if (list instanceof List<String>){ ....}

 

Primitive types as parameter types

Unlike C++, Java does not allow primitive types to be type parameters. This limitation is not so significant, since we can always replace the primitive type with the corresponding wrapper, and we can also use auto-boxing/auto-unboxing in the access methods to simplify the code. However, boxing/unboxing can lead to a performance penalty. In order to eliminate it there is no choice but to code a new, dedicated version of the class for the specific primitive type.

 

Generic exceptions

It is not allowed to define a generic type that extends (directly/indirectly) some Throwable. Trying to do so implies that the programmer wishes to handle different parameterized versions of the same exception at runtime, such as in the following example:

try{
    ....
}catch(MyException<Byte>){
    ....
}catch(MyException<Integer>){
    ....
} 

The problem is that erasure does not allow it.  There is no way for the JVM to distinguish at runtime between MyException<Byte> and MyException<Integer>. They are both simply MyException at runtime. Therefore there is no sense in having generic exceptions.

 

Generic enums

Defining generic enums is not allowed: 

enum State <T>{ //Illegal
    STANDING,WALKING,RUNNING;

     private T attribute;
     public void setAttribute(T attribute){
         this.attribute=attribute;
     }

     public T getAttribute(){
        return attribute;
    }
}

The reason for this to be illegal is related to the static members limitation (see “Static data members” above). Enums are implemented according to the “Type Safe Enum” design pattern, where the enum values are static data members of the class. Therefore, they are not allowed to have any reference to the class’ type parameter in their declarations.

 

Conclusion

Generics are a big step forward for Java, making it support a popular programming style common to Ada, C++, C# and other languages. However, simple intuition is not enough for really understanding Java generics. Sometimes one has to go under the hood of the compiler in order to understand its limitations and use it correctly. There has been a proposal of re-working the design by canceling erasure (“Reified Generics”), but it seems like this idea is no longer in the feature list of Java 7 (see http://tech.puredanger.com/java7).

 

Links

http://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.html
http://www.angelikalanger.com/GenericsFAQ/FAQSections/Fundamentals.html
http://mindview.net/WebLog/log-0051
http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf
http://www.ibm.com/developerworks/java/library/j-jtp01255.html
http://www.devarticles.com/c/a/Java/Generics-and-Limitations-in-Java/
http://java.sun.com/developer/technicalArticles/J2SE/generics/#TJVM

Posted in java, Language | Tagged: , , , , , , , , , , , , , , , , | 3 Comments »