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).

56 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. Having read this I believed it was really enlightening. I appreciate you spending some time and energy to put this content together. 경마


    ReplyDelete
  7. 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
  8. 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
  9. I used to be checking continuously this weblog and I am impressed! Appreciate it for your efforts. Feel free to visit my website; 카지노사이트링크

    ReplyDelete
  10. 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
  11. 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
  12. Уour blog providеd us useful information to work on. Үou have done a marvelous job! 파칭코사이트인포

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

    ReplyDelete
  14. 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
  15. Thanks for the information keep sharing such informative post keep suggesting such post. 경마

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

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


    ReplyDelete
  18. 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
  19. 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
  20. 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
  21. Appreciate it for this post, I am a big fan of this internet site would like to keep updated. 경마사이트

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

    ReplyDelete
  23. 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
  24. Its a great pleasure reading your post.Its full of information I am looking for and I love to post a comment that 메이저사이트

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

    ReplyDelete
  26. 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
  27. 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
  28. This comment has been removed by the author.

    ReplyDelete
  29. 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
  30. Congratulations on your article, it was very helpful and successful. acd820943a8ac48ab792b627b8229500
    website kurma
    website kurma
    numara onay

    ReplyDelete
  31. Thank you for your explanation, very good content. deed57f4a1109d4199112cbb71ceeeb9
    altın dedektörü

    ReplyDelete
  32. Nice informative article. Thanks for sharing this article. Keep sharing more related blogs. Abogado DUI Rockingham VA

    ReplyDelete
  33. youtube to mp3 iphone app no jailbreak
    youtube to mp3 alan cave
    mp3 to youtube 320 kbps
    download youtube link to mp3 online
    change a youtube video to mp3
    https://yttomp3.pro/
    download youtube playlist to mp3 reddit
    youtube to mp3 vidto
    telecharger youtube to mp3 en ligne
    safe youtube to mp3 reddit 2023

    ReplyDelete
  34. We specialize in guiding you through wavlink wifi extender setup. Count on our expert assistance to optimize your extender, ensuring wider coverage and smoother performance. Experience seamless connectivity with our dedicated support.




    ReplyDelete
  35. Elevate your social media game with DP images from dp imags via dpwalay. See for yourself!

    ReplyDelete
  36. I recently completed my first scarf, and I couldn't be more proud of it! With each stitch, I felt a sense of accomplishment and creativity.
    New Jersey Federal Criminal Lawyer
    Federal Criminal Defense Lawyer

    ReplyDelete
  37. Another good blog from the author. Like the Previous blog this blog also is too interesting to read. Keep posting more informative blogs. Virginia Government Contracts Fraud Lawyer

    ReplyDelete
  38. Java 5.0's type inference topic is quite intriguing. It's essential to explore and understand the intricacies of type inference in programming languages, especially in Java. The fact that it's considered underspecified highlights the need for further research and clarity in this domain. This is a crucial aspect of programming that impacts how code is written and maintained. Kudos to those delving into the depths of Java type inference! 👩‍💻🧐🚀

    How to Get Uncontested Divorce in New York
    How to File an Uncontested Divorce in New York

    ReplyDelete
  39. can reckless driving be expunged in virginia
    The "Java 5.0 type inference is underspecified" review addresses a critical issue within Java's type inference system, providing in-depth insights for developers. The review provides a detailed analysis of the problem, highlighting its impact on developers and its practical implications. Real-world examples and scenarios are provided to enhance readers' comprehension of the problem's real-life implications. Comparisons with solutions implemented in later versions or other programming languages are provided for a comparative perspective. The review's educational value is highlighted, as it aids developers, students, or educators in understanding a complex aspect of Java programming. The review encourages discussion and calls for improvements in Java's type inference system, advocating for progress within the programming language. Developer awareness is emphasized, as understanding these issues empowers developers to write more robust and error-free code, contributing to the overall advancement of the software industry. The review encourages further research on Java's type inference, as a continuous quest for knowledge and understanding is essential for the growth and evolution of programming practices.

    ReplyDelete
  40. You wrote a beautiful content. I am really enjoying the blog. Abogado Tráfico Chesterfield Virginia

    ReplyDelete
  41. Java's type inference feature, introduced in Java 5, simplifies code and improves readability by automatically deducing variable data types based on usage. This feature reduces code verbosity, enhances expressiveness, and frees up programmers' time for more complex tasks. It also helps in error detection and prevention, identifying potential errors early in the development process. Type inference is adaptable to changes in variable usage and context, automatically updating the inferred type. It aligns with Java's generics feature, ensuring a consistent approach to type handling. Overall, type inference is a valuable addition to Java programming practices. a dispute over a contract between

    ReplyDelete
  42. virginia beach personal injury attorney
    The article highlights the underspecification of Java 5.0 type inference, providing a clear and concise explanation of its limitations. It is a must-read for Java developers, as it raises important considerations and prompts thoughtful reflection on the language's design. The critical analysis and examples provided by the article provide valuable insights for developers grappling with these nuances. The article is a commendable deep dive into Java 5.0 type inference, identifying the issue and offering a clear understanding of its implications for developers.

    ReplyDelete
  43. Amazing, Your blogs are really good and informative. I got a lots of useful information in your blogs. 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 Attorney near me. It is very great and useful to all. Keeps sharing more useful blogs...

    ReplyDelete
  44. New York State Divorce Forms include the Summons with Notice or Summons and Verified Complaint, which initiate the divorce process, and other documents required for various stages of the proceedings.

    ReplyDelete
  45. fauquier traffic lawyer
    Java 5.0 introduced generics and annotations, but did not include type inference as a language feature. Type inference was introduced in Java 7 with the "diamond operator" for generic types. Although Java's type inference capabilities were expanded in later versions, they remain limited compared to other modern programming languages like Kotlin or Swift.

    ReplyDelete