2008-11-08

Java 5.0 type inference is underspecified

Here's a program that will make your brain hurt:

class C<E> { }
class G<X,Y,Z> { }
class P { }
class Q { }

public class Test {
   static void foo(Object o) {
      System.out.print("Object ");
   }
   static <T> void foo(G<? extends T, ? extends T, ? extends T> g) {
      System.out.print("G ");
   }
   static public void main(String[] args) {
      foo(new G<C<? super P>, C<P>, C<Q>>());
      foo(new G<C<? super P>, C<Q>, C<P>>());
      foo(new G<C<P>, C<? super P>, C<Q>>());
      foo(new G<C<Q>, C<? super P>, C<P>>());
      foo(new G<C<P>, C<Q>, C<? super P>>());
      foo(new G<C<Q>, C<P>, C<? super P>>());
      System.out.println();
   }
}

Quick, what does it print? No cheating!

For what it's worth, Sun's reference javac, version 1.5.007 produces a .class file that prints

G G G G G G 

whereas Eclipse SDK 3.2.1 creates one that prints

Object Object G G Object Object 

Normally this would lead one to point at one of the compilers and shout BUG! – but after several hours of close reading the Java Language Specification I have come to the conclusion that both behaviors adhere to the letter of the specification. In other words, it is entirely up to the whims of the compiler which of the foos gets called in each of the six calls.

This is somewhat remarkable. Sun has otherwise gone to great pains specifying exactly what a Java program is supposed to mean, modulo the a few clearly defined areas where the virtual machine – not the compiler! – is explicitly given discretion. But here is a completely straightforward single-threaded program where (so I assert) the language underspecifies which method is supposed to be called.

Such nondeterminism makes it hard to do static analysis of Java source code. What happens?

Broadly speaking, generics happen. The half of generics that gets all of the press is parameterized types, but the really hairy stuff only begins to happen when we consider parameterized methods, too. The reason for this is the the programmer always needs to write down the type parameter explicitly in order to instantiate a generic type – but the designers of Java's generics decided that explicit type arguments should not be necessary for calling a generic method. It is possible to give type parameters explicitly in the code, but in the common case, the compiler must try to infer appropriate type arguments given the types of the ordinary arguments.

And this is fairly hard. In fact, because subtyping gets into play, it is so hard that the language makes no claim that the compiler can always find appropriate type arguments when you want to call a parameterized method. The language specification itself remarks, in the middle of the 16 pages of extremely technical definition of how the type inference works:

[...] type inference does not affect soundness in any way. If the types inferred are nonsensical, the invocation will yield a type error. The type inference algorithm should be viewed as a heuristic, designed to perfdorm well in practice. If it fails to infer the desired result, explicit type paramneters may be used instead.

Still, however, one would expect the inference to be deterministic such that one would not risk changing the behavior of a program just by recompiling with a new version of the compiler. But perhaps "perfdorm" and "paramneters" is a hint that this section has not received the most thorough of proofreadings before it went to press.

In the example program above, the type inference eventually computes that T should be instantiated to the "least containing invocation" of an unordered set of the three types C<? super P>, C<P>, and C<Q>. I now quote:

[...] lci, the least containing invocation is defined

lci(S) = lci(e1, ..., en) where ei in S, 1≤in
lci(e1, ..., en) = lci(lci(e1, e2), e3, ..., en)
lci(G<X1, ..., Xn>, G<Y1, ..., Yn>) = G<lcta(X1, Y1),..., lcta(Xn, Yn)>

where lcta() is the the least containing type argument function defined (assuming U and V are type expressions) as:

lcta(U, V) = U if U = V, ? extends lub(U, V) otherwise
lcta(U, ? extends V) = ? extends lub(U, V)
lcta(U, ? super V) = ? super glb(U, V)
lcta(? extends U, ? extends V) = ? extends lub(U, V)
lcta(? extends U, ? super V) = U if U = V, ? otherwise
lcta(? super U, ? super V) = ? super glb(U, V)

[The Java Language Specification, third edition, p. 465]. Read the definition of lci carefully. The first line says that we arrange our three types in some unspecified order. The second line says to combine two types at a time using a two-argument version of lci. And the two-argument lci in the third line just distribute lcta over all the type arguments. (We know from earlier in the type inference that all arguments to lci are instances of the same parameterized type).

This would be a nice and standard construction if only lcta (and by extension the two-argument lci) were commutative and associative. It is indeed commutative – it has to be, for the cases given in the definition only make sense if we understand implicitly that we are to take their commutative closure. But it is manifestly not associative. To wit:

(? super P) lcta (P lcta Q) = (? super P) lcta (? extends Object) = ?

whereas

((? super P) lcta P) lcta Q = (? super P) lcta Q = (? super P & Q)

In the former case, the parameterized foo is not applicable to the call with T = C<?>. Therefore, compile-time overload resolution decides on the less specific but viable foo(Object) instead. But when T is C<? super P & Q>, the parameterized call is applicable.

How clever of javac always to choose the evaluation order that reaches the better result! In fact, I suspect it of cheating and using a smarter multi-argument lcta computation for each type-argument position, instead of selecting on a common order of all lci arguments. Extending the example program to test this hypothesis is left an exercise for the reader.

(Also left for the reader is to figure out the exact meaning and properties of ? super P & Q, a possibility not hinted at anywhere in the JLS except for the two occurrences of "? super glb(U,B)" in the definition of lcta).

66 comments:

  1. So, isn't this a bug in the specification, actually? Shouldn't it be reported somewhere?

    I'm not sure I understand why they didn't specify complete type inference. I know it can get exponential in bad cases, but they could have said “either complete the inference or stop with an error”, i.e. if it's too hard and it takes too long.

    That would have the same effect of having to specify types manually sometimes, but if a program is compiled, the result would be deterministic.

    I also encountered a case where neither javac nor Eclipse can figure out the correct type. Based on their error messages, they seem to reach different conclusions, but I can't tell if the Java specification would allow inferring the correct types.

    Given:

    <T extends Comparable<? super T>,
      V extends Iterable<T>>
    Comparator<V> iterableComparator() { ... }

    <T> boolean isOrdered(
      Iterable<T> values,
      Comparator<? super T> comparator) { ... }

    Then the following is valid:

    void main() {
      List<List<Integer>> list = null;
      isOrdered(list,
        this.<Integer, List<Integer>>
        iterableComparator());
    }

    However, if the explicit type arguments to iterableComparator are not given, neither compiler accepts the call.

    javac infers T,V = java.lang.Comparable<? super T>,java.lang.Object
    Both Eclipse and gcj infer V = Iterable<Comparable<? super T>>, but don't mention T.

    ReplyDelete
  2. Wow that looks super complicated. I'd never be able to do program like this by myself. Well done and thanks for sharing.

    ReplyDelete
  3. So, this is a dumbed down way to explain this, there is an ordered sequence of rational exponet resolution....even more plain: there is a order preference for the example scripts resolutions, Sun will not share since only one or two people know what we are talking about.

    Great find, please consider that this script is not needed - it is a way to exploit a un named trait of the software. See JavaScript 1.0Beta to learn about other un named traits.

    :)

    ReplyDelete
  4. شركتنا من المتميزون في اعمال الاصلاح بدون هدم او تكسير من خلال شركة ركن البيت التي تقدم الكثير والكثير في عمل اللازم وتصحيح الاخطاء التي تسببها تسريبات المياه فنحن مثلا

    شركة كشف تسربات المياه بجدة تقدم خدمة لعمل الاصلاح بدون اي خراب ونقدم النصيحة للعملاء بالابتعاد عن الاعمال التي تؤدي الي هذا الخراب فتعاملك مع شركة كشف تسربات بجدة لديها الخبرة الكافية تساعدك في الحفاظ علي منزلك كما اننا نتمكن في اننا سوف نرتقي بخدمة لاننا نقوم بالعمل السليم لها كما يوجد لدينا خدمات العوازل التي تمنع التسريبات من الاسقف لكم والحوائط والخزانات من خلال شركة تسمي الاولي في مجالها لذلك نحن نقدم شركة عزل خزانات بالرياض التي تعتبر في عل الخزانات الارضية من الداخل بواسطة مواد متميزة كما نقدم لكم شركة عزل اسطح بالرياض لعمل العوازل التي تمنع جميع التسريبات في الاسقف

    ReplyDelete

  5. شركة عوازل فوم has left a new comment on the post "Reproduction poterie at its best":

    https://ibdaealshrq.com/
    https://ibdaealshrq.com/2021/05/02/%d9%81%d9%88%d8%a7%d8%a6%d8%af-%d8%b9%d8%b2%d9%84-%d8%a7%d9%84%d9%81%d9%88%d9%85/
    https://ibdaealshrq.com/2021/05/02/%d9%81%d9%88%d8%a7%d8%a6%d8%af-%d8%b9%d8%b2%d9%84-%d8%a7%d9%84%d9%81%d9%88%d9%85/
    https://ibdaealshrq.com/2021/04/29/%d8%a7%d9%86%d9%88%d8%a7%d8%b9-%d8%b9%d8%b2%d9%84-%d8%a7%d9%84%d8%a7%d8%b3%d8%b7%d8%ad
    https://ibdaealshrq.com/2021/05/04/%d9%83%d8%b4%d9%81-%d8%aa%d8%b3%d8%b1%d8%a8%d8%a7%d8%aa-%d8%a7%d9%84%d9%85%d9%8a%d8%a7%d9%87/
    https://ibdaealshrq.com/2021/05/04/%d9%85%d9%83%d8%a7%d9%81%d8%ad%d8%a9-%d8%a7%d9%84%d8%ad%d8%b4%d8%b1%d8%a7%d8%aa/
    https://ibdaealshrq.com/2021/05/04/%d8%b9%d8%b2%d9%84-%d8%a7%d9%84%d8%ae%d8%b2%d8%a7%d9%86%d8%a7%d8%aa/
    https://ibdaealshrq.com/2021/05/08/%d8%aa%d8%b1%d9%85%d9%8a%d9%85-%d8%a7%d9%84%d9%85%d9%86%d8%a7%d8%b2%d9%84/

    Post a comment.

    Unsubscribe to comments on this post.

    Posted by شركة عوازل فوم to 18thC Cuisine at 8:44 AM

    ReplyDelete
  6. Remarkable! Its really amazing post, I have got much clear idea regarding from
    this piece of writing. 파워볼

    ReplyDelete
  7. Having read this I believed it was really enlightening. I appreciate you spending some time and energy to put this content together. 경마


    ReplyDelete
  8. Hello there! This post could not be written any better! 릴게임

    ReplyDelete
  9. People should know these tips because you have great content! Thanks anyway! 토토

    ReplyDelete
  10. I can read all the opinions of others as well as i gained information to each and everyone here on your site. Just keep on going dude. Check over here:
    경마사이트
    경마

    ReplyDelete
  11. I am very grateful that I have crossed your site. Your content was very great that I cant stop reading each post that you have. I hope for the best outcome of your site. Thanks 카지노사이트

    ReplyDelete
  12. Searching for a great site. I was so impressed to yours. This will probably give me ideas for my work. Thank you 토토

    ReplyDelete
  13. The information you provided is very useful, thank you very much for sharing useful information with us. You can apply for an online Turkish visa - If you are Planning a Trip to Turkey for tourism, business purposes. You can fill the e visa of Turkey application form in less than 5 to 10 minutes.

    ReplyDelete
  14. I think this is one of the most significant information for me. And i’m glad reading your article. But should remark on some general things, The web site style is perfect, the articles is really great. Feel free to visit my website; 먹튀검증가이드

    ReplyDelete
  15. I used to be checking continuously this weblog and I am impressed! Appreciate it for your efforts. Feel free to visit my website; 카지노사이트링크

    ReplyDelete
  16. Such a valuable post. I like it very much and I like your choice words also. I am waiting for your next valuable post. Feel free to visit my website; 온라인카지노사이트넷

    ReplyDelete
  17. Nice to be visiting your blog again. it has been months for me. Well this article that i’ve been waited for so long. I need this article to complete my assignment in the college. and it has same topic with your article. Thanks. great share Feel free to visit my website; 배트맨토토프로

    ReplyDelete
  18. This is a topic that’s near to my heart… Many thanks! Where are your contact details though? E Visa for India is you can obtain online without the need of visiting the Indian Embassy and Consulate. India business visa cost depends on your country, you can check india visa site online. You can apply for india business visa registration via mobile phone, computer or desk.

    ReplyDelete
  19. This is a wonderful inspiring article. I am practically satisfied with your great work. You have really put together extremely helpful data. Keep it up.. Are you planning to visit Kenya?For this, you need to fill the Kenya Visa Application Form and pay the kenya e visa fees online.

    ReplyDelete
  20. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    온라인카지노

    ReplyDelete
  21. Уour blog providеd us useful information to work on. Үou have done a marvelous job! 파칭코사이트인포

    ReplyDelete
  22. This web site truly has all the information. 카지노

    ReplyDelete
  23. It’s perfect time to make a few plans for the future and it is time to be happy. I’ve read this post and if I may I want to suggest you some attention-grabbing things or suggestions. Perhaps you could write next articles referring to this article. I wish to learn even more things approximately it! Feel free to visit my website; 카지노사이트위키

    ReplyDelete
  24. Nice blog here! Also your web site loads up fast! 스포츠토토

    ReplyDelete
  25. Thanks for the information keep sharing such informative post keep suggesting such post. 경마

    ReplyDelete
  26. When your website or blog goes live for the first time, it is exciting.
    파친코사이트

    ReplyDelete
  27. Your blog post is very impressive, I almost read all the articles you wrote. Contains a lot of useful information. Thank you! 스포츠토토


    ReplyDelete
  28. You absolutely come with really good articles and reviews. Regards for sharing with us your blog. 슬롯머신사이트

    ReplyDelete
  29. From some point on, I am preparing to build my site while browsing various sites. It is now somewhat completed. 바카라사이트 If you are interested, please come to play with

    ReplyDelete
  30. I want you to thank for your time of this wonderful read!!! 카지노사이트 I definately enjoy every little bit of it and I have you bookmarked to check out new stuff of your blog a must read blog!

    ReplyDelete
  31. Very nice article and straight to the point. I don't know if this is truly the best place to ask but do you folks have any idea where to get some professional writers? 토토 Thank you. Feel free to visit my website;

    ReplyDelete
  32. Awesome post.Thanks for sharing.This is so nice. 토토사이트

    ReplyDelete
  33. Appreciate it for this post, I am a big fan of this internet site would like to keep updated. 경마사이트

    ReplyDelete
  34. The details mentioned within the write-up are a number of the top accessible 슬롯머신

    ReplyDelete
  35. Great content material and great layout. Your website deserves all of the positive feedback it’s been getting. 스포츠토토

    ReplyDelete
  36. I think this is a real great blog article. enjoy reading this. 카지노

    ReplyDelete
  37. Just desire to say your article is as surprising. The clearness in your post is simply great and i can assume you are an expert on this subject. 카지노사이트

    ReplyDelete
  38. I am sure this piece of writing has touched all the internet visitors, its really really pleasant post on building up new webpage. great blog article. Really looking forward to read more. 바둑이사이트넷

    ReplyDelete
  39. Wow.. Very informative article thanks for sharing please keep it up.. visa for Pakistan, you can easily apply for a Pakistan visit visa and get your Pakistan visa.

    ReplyDelete
  40. Its a great pleasure reading your post.Its full of information I am looking for and I love to post a comment that 메이저사이트

    ReplyDelete
  41. I enjoy it. I come back again. This blog is a really useful blog. 먹튀검증업체

    ReplyDelete
  42. This blog is a really useful blog. I enjoy it. I be back. 메이저사이트

    ReplyDelete
  43. Thank you for the information provided! Maintain the good performance of your site. You can also check my article 메이저검증업체

    ReplyDelete
  44. Attractive portion of content. I simply stumbled upon your web site and in accession capital to assert that I get actually enjoyed account your weblog.
    Feel free to visit my website 안전사이트

    ReplyDelete
  45. You made some good points there. I did a Google search about the topic and found most people will believe your blog 토토

    ReplyDelete
  46. I am enjoying every bit of it. It is a good site, as well as the stock is well-chosen. Thank you.. Indian e visa photo, photo requirements for Indian visa, you can read online India e visa photo requirements through the India evisa website.

    ReplyDelete
  47. It is a good site,Thank you.. Obtain the Indian e-Medical visa online via Indian visa website. Indian Medical Visa is a travel permit approved by the Government of India for persons who wish to come to India for medical treatment. Indian e-Medical visa cost depends on your nationality.

    ReplyDelete
  48. Superb blog! This gives a lot of information... Now I am telling you the information which is needed to know you. After covid19 Indian tourist visa open for all international travelers. Check out for more information before traveling.

    ReplyDelete
  49. This comment has been removed by the author.

    ReplyDelete
  50. Wonderful article! Thanks for sharing this article with us... I hope you will continue in the future... The application for an electronic visa Turkey is easy to fill out for everyone, if you want to apply for a Turkish Visit Visa check out the page for more information.

    ReplyDelete