CINXE.COM

<!DOCTYPE html> <html xmlns='http://www.w3.org/1999/xhtml' xmlns:b='http://www.google.com/2005/gml/b' xmlns:data='http://www.google.com/2005/gml/data' xmlns:expr='http://www.google.com/2005/gml/expr'> <head> <link href='https://www.blogger.com/static/v1/widgets/55013136-widget_css_bundle.css' rel='stylesheet' type='text/css'/> <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'/> <meta content='blogger' name='generator'/> <link href='https://gafter.blogspot.com/favicon.ico' rel='icon' type='image/x-icon'/> <link href='http://gafter.blogspot.com/2006/' rel='canonical'/> <link rel="alternate" type="application/atom+xml" title="Neal Gafter's blog - Atom" href="https://gafter.blogspot.com/feeds/posts/default" /> <link rel="alternate" type="application/rss+xml" title="Neal Gafter's blog - RSS" href="https://gafter.blogspot.com/feeds/posts/default?alt=rss" /> <link rel="service.post" type="application/atom+xml" title="Neal Gafter's blog - Atom" href="https://www.blogger.com/feeds/7803021/posts/default" />  <meta content='http://gafter.blogspot.com/2006/' property='og:url'/> <meta content='Neal Gafter's blog' property='og:title'/> <meta content='Thoughts about Programming Languages, Science and Philosophy.' property='og:description'/> <title>Neal Gafter's blog: 2006</title> <style id='page-skin-1' type='text/css'></style> <link href='https://www.blogger.com/dyn-css/authorization.css?targetBlogID=7803021&zx=6d23975f-4198-4953-9a5d-026e1a0b11bc' media='none' onload='if(media!='all')media='all'' rel='stylesheet'/><noscript><link href='https://www.blogger.com/dyn-css/authorization.css?targetBlogID=7803021&zx=6d23975f-4198-4953-9a5d-026e1a0b11bc' rel='stylesheet'/></noscript> <meta name='google-adsense-platform-account' content='ca-host-pub-1556223355139109'/> <meta name='google-adsense-platform-domain' content='blogspot.com'/> </head> <body> <div class='navbar section' id='navbar'><div class='widget Navbar' data-version='1' id='Navbar1'><script type="text/javascript"> function setAttributeOnload(object, attribute, val) { if(window.addEventListener) { window.addEventListener('load', function(){ object[attribute] = val; }, false); } else { window.attachEvent('onload', function(){ object[attribute] = val; }); } } </script> <div id="navbar-iframe-container"></div> <script type="text/javascript" src="https://apis.google.com/js/platform.js"></script> <script type="text/javascript"> gapi.load("gapi.iframes:gapi.iframes.style.bubble", function() { if (gapi.iframes && gapi.iframes.getContext) { gapi.iframes.getContext().openChild({ url: 'https://www.blogger.com/navbar/7803021?origin\x3dhttps://gafter.blogspot.com', where: document.getElementById("navbar-iframe-container"), id: "navbar-iframe" }); } }); </script><script type="text/javascript"> (function() { var script = document.createElement('script'); script.type = 'text/javascript'; script.src = '//pagead2.googlesyndication.com/pagead/js/google_top_exp.js'; var head = document.getElementsByTagName('head')[0]; if (head) { head.appendChild(script); }})(); </script> </div></div> <div id='outer-wrapper'><div id='wrap2'>  <span id='skiplinks' style='display:none;'> <a href='#main'>skip to main </a> | <a href='#sidebar'>skip to sidebar</a> </span> <div id='header-wrapper'> <div class='header section' id='header'><div class='widget Header' data-version='1' id='Header1'> <div id='header-inner'> <div class='titlewrapper'> <h1 class='title'> <a href='https://gafter.blogspot.com/'> Neal Gafter's blog </a> </h1> </div> <div class='descriptionwrapper'> <p class='description'><span>Thoughts about Programming Languages, Science and Philosophy.</span></p> </div> </div> </div></div> </div> <div id='content-wrapper'> <div id='main-wrapper'> <div class='main section' id='main'><div class='widget Blog' data-version='1' id='Blog1'> <div class='blog-posts hfeed'> <div class="date-outer"> <h2 class='date-header'><span>Monday, December 18, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='3235073068503710147'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/12/closures-talk-and-spec-update.html'>Closures Talk and Spec Update</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><span style="font-style:italic;">This post discusses a draft proposal for adding support for closures to the Java programming language for the Dolphin (JDK 7) release. It was carefully designed to interoperate with the current idiom of one-method interfaces. The latest version of the proposal and a prototype can be found at <a href="http://www.javac.info/">http://www.javac.info/</a>.</span> <p>My 2006 JavaPolis talk<em> Closures for Java</em> has now been published - slides synchronized with a soundtrack - and can be viewed <a href="http://www.bejug.org/confluenceBeJUG/display/PARLEYS/Closures+for+Java">online at the new Javapolis website, Parleys.com</a>. If you're still wondering why all the fuss about closures, I recommend you listen to the talk.</p> <p>We've also just published an <a href="http://www.javac.info/closures-v04.html">update to the specification, version 0.4 </a>. The specification seems to be setling down quite a bit, as the changes are minor:</p> <ul> <li>The <span class="Java">throws</span> clause of a function type is now placed between the curly braces.</li> <li>The description of function types has been rewritten to emphasize more clearly that function types <em>are interface types</em> rather than a separate extension to the type system. </li> <li>The closure conversion can now convert a closure that has no result expression to an interface type whose function returns <span class="Java">java.lang.Void</span>. This change helps support <em>completion transparency</em>. A <em>completion transparent</em> method is one written such that the compiler can infer that an invocation completes normally iff the closure passed to it completes normally. </li> <li>Some examples have been modified to be completion transparent. </li> <li><span class="Java">null</span> is now a subtype of <span class="Java">Unreachable</span>, and a number of small related changes. Thanks to Rémi Forax for pointing out the issues. </li> </ul> <p>I hope the talk, which is less technical than the specification, makes it easier for you to evaluate the proposal and compare it to the alternatives. </p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/3235073068503710147' onclick=''>46 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Friday, December 15, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='3067423850465703862'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/12/javapolis-2006.html'>Javapolis 2006</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>I'm on my way back from Javapolis 2006, unfortunately missing the third day of the conference. One of the innovations this year was a bank of ten whiteboards where people brainstormed about the future of the Java language and platform. I had a camera with me but I realized too late that I should have taken snapshots of the contents of all those boards before I left. I hope someone else will. The only snapshots I took were the vote tallies that I discuss below. </p> <p>There were three issues discussed on those boards that I'd like to share with you.</p> <h2>Closures</h2> <p>The first board contained a discussion of closures, including an informal vote of people "in favor of" and "against" adding support for closures. I gave a talk about closures yesterday afternoon, which explained the goals and design criteria, showed how they fit quite smoothly into the existing language and APIs, and more importantly explained in detail why anonymous instance creation expressions do not solve the problems closures were designed to solve. Before my talk about closures, the vote was about 55% in favor and 45% against. After my talk the vote was 71% in favor and 29% against. I don't think any "against" votes were added to the tally after my talk. There was also a <em>BOF</em> (Birds-Of-a-Feather) session in the evening discussing closures. Of the 20 or so attendees none admitted being against adding closures. I'm sure the fact that the BOF was scheduled opposite a free showing of Casino Royale didn't help, but I had hoped to hear from opponents more about their concerns. We discussed a number of issues and concerns, most of which had been discussed on my blog at one time or another. </p> <p>One issue that I discussed with a few individuals earlier and then at the BOF was the idea of adding a statement whose purpose is to yield a result from the surrounding closure, which you could use instead of or in addition to providing a result as the last expression in the closure. It turns out that adding this feature make closures no longer suitable for expressing control abstractions. In other words, <em>adding</em> this feature to the language would make closures <em>less</em> useful! This is a very counterintuitive result. I first understood the issue by analyzing the construct using Tennent's Correspondence Principle, but it is much easier for most people to understand when the result is presented as specific examples that fail to work as expected. For now I'll leave this as an exercise to the reader, but I'll probably write more about it later. Incidentally, I believe the folks who designed Groovy got closures wrong for exactly this reason. </p> <p>There was a video made of my talk that will be posted to the Javapolis website. Ted Neward also interviewed me on video, and Bill Venners interviewed me on audio. As soon as these are available on the web I'll blog pointers to them. </p> <h2>Native XML Support</h2> <p>Mark Reinhold gave a talk on adding native (i.e. language-level) support for XML into Java. Though they were not presented as such, some people prefer to think of the proposal as separable into a <em>language extension</em> part and an <em>API</em> part. The proposed APIs appear to be an improvement over the existing alternatives. However, the language extension for writing XML literals appears to be only marginally more convenient than the XML construction techniques provided by <a href="http://www.jdom.org/">libraries in JDOM</a>. I personally would like to see the new APIs pursued but XML creation provided in the JDOM way. Mark took a vote by show of hands on how people felt about the two issues, but I couldn't see the tally. There was also an informal tally about adding native XML support on one of the whiteboards. The result was 29% in favor and 71% against. </p> <h2>Constructor Invocation for Generics</h2> <p>Another much-discussed issue appeared on one of the whiteboards: the verbosity of creating instances of generic types. This is typical:</p> <blockquote> <pre>Map<Pair<String,Integer>,Node> map = new HashMap<Pair<String,Integer>,Node>();</pre> </blockquote> <p>The problem here is that the type parameters have to be repeated twice. One common "workaround" to this problem is to always create your generic objects using static factories, but the language should not force you to do that. A number of different syntax forms have been suggested for fixing this:</p> <blockquote> <pre>var map = new HashMap<Pair<String,Integer>,Node>();</pre> </blockquote> <p>This unfortuately requires the addition of a new keyword. Another: </p> <blockquote> <pre>final map = new HashMap<Pair<String,Integer>,Node>();</pre> </blockquote> <p>This reuses an existing keyword, but at the same time it also makes the variable final. Another variation on this idea:</p> <blockquote> <pre>map := new HashMap<Pair<String,Integer>,Node>();</pre> </blockquote> <p>In my opinion these three forms all suffer the same flaw: they place the type parameters in the wrong place. Since the variable is to be used later in the program, the programmer presumably wants control over its type and the reader wants the type to be clear from the variable declaration. In this case you probably want the variable to be a <code>Map</code> and not a <code>HashMap</code>. An idea that addresses my concern is: </p> <blockquote> <pre>Map<Pair<String,Integer>,Node> map = new HashMap();</pre> </blockquote> <p>Unfortunately, this is currently legal syntax that creates a <em>raw</em> <code>HashMap</code>. I don't know if it is possible to change the meaning of this construct without breaking backward compatibility. Another possibility: </p> <blockquote> <pre>Map<Pair<String,Integer>,Node> map = new HashMap<>();</pre> </blockquote> <p>You can see clearly by the presence of the empty angle brackets that the type parameters have been omitted where the compiler is asked to infer them. Of the alternatives, this is my favorite. I don't think it will be too hard to implement in javac using the same techniques that work for static factories of generic types. </p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/3067423850465703862' onclick=''>20 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Tuesday, December 05, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='7433479707202598913'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/12/type-literals.html'>Type Literals</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>Yesterday I wrote about <em><a href="http://gafter.blogspot.com/2006/12/super-type-tokens.html">super type tokens</a></em>, which is an API that acts like class literals but with two advantages over class literals: they work with generic types, and they provide full generic type information. The disadvantages are that they are more verbose than class literals, and (being a different type than <tt>java.lang.Class</tt>) they are incompatible with APIs that use type tokens. It turns out that it is possible to get the best of both worlds by adding super type tokens to the language. I would call the resulting construct <em>type literals</em>. </p> <p>The basic idea would be to retrofit <tt>java.lang.reflect.Type</tt> with generics, in the same way that <tt>java.lang.Class</tt> was retrofitted with generics in JDK5. Then the type of <tt>List<String>.class</tt> would be <tt>Type<List<String>></tt>, and the structure of the resulting object would contain all of the generic type information that a <tt>Type</tt> is capable of expressing. The code generated by javac could very well use the trick outlined in my <a href="http://gafter.blogspot.com/2006/12/super-type-tokens.html">previous blog post</a>, though I expect there are much more efficient ways of doing it. You would then be able to write</p> <blockquote> <p> <pre>Type<List<String>> x = List<String>.class; </pre> </p> </blockquote> <p>The "type literal" on the right is currently a syntax error, but this language extension would give meaning to the syntax. How does this fit with the existing meaning of class literals? Very nicely. The type <tt>java.lang.Class</tt> already extends <tt>java.lang.reflect.Type</tt>, so a class literal of type <tt>Class<String></tt> could be assigned to a variable of type <tt>Type<String></tt>. In other words, the following would be legal:</p> <blockquote> <p> <pre>Type<String> x = String.class; </pre> </p> </blockquote> <p>Adding support for type literals to the language and retrofitting <tt>java.lang.reflect.Type</tt> would simplify the use of the <a href="http://developers.sun.com/learning/javaoneonline/2006/coreplatform/TS-1512.pdf">THC pattern</a> with generic types and make existing type-token-based APIs interoperate nicely with the pattern. </p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/7433479707202598913' onclick=''>2 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Monday, December 04, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='3085325539025155770'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/12/super-type-tokens.html'>Super Type Tokens</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>When we added generics to Java in JDK5, I changed the class <tt>java.lang.Class</tt> to become a generic type. For example, the type of <tt>String.class</tt> is now <tt>Class<String></tt>. <a href="http://bracha.org/Site/Home.html">Gilad Bracha</a> coined the term <em><a href="http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf">type tokens</a></em> for this. My intent was to enable a particular style of API, which Joshua Bloch calls the <a href="http://developers.sun.com/learning/javaoneonline/2006/coreplatform/TS-1512.pdf"><em>THC</em>, or <em>Typesafe Heterogenous Container</em></a> pattern. For some examples of where this is used see the APIs for annotations:</p> <blockquote> <pre>public <A extends <a href="http://java.sun.com/j2se/1.5.0/docs/api/java/lang/annotation/Annotation.html" title="interface in java.lang.annotation">Annotation</a>> A <a href="http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Class.html">java.lang.Class</a>.<strong>getAnnotation</strong>(<a href="http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Class.html" title="class in java.lang">Class</a><A> annotationClass)</pre> </blockquote> <p>My earliest use of this feature (like my earliest use of all recent Java language features) appears in the compiler for the Java programming language (javac), in this case as a utility called Context, and you can <a href="https://openjdk.dev.java.net/source/browse/openjdk/compiler/trunk/src/share/classes/com/sun/tools/javac/util/Context.java?rev=HEAD"> find the code</a> in the open source version. It was a utility that allowed the compiler to be written as a bunch of separate classes that all refer to each other, and solved the hard problem of getting all the parts created in an order such that they can be initialized with references to each other. The utility is also used to replace pieces of the compiler, for example to make related tools like <a href="http://java.sun.com/j2se/javadoc/">javadoc</a> and <a href="http://java.sun.com/j2se/1.5.0/docs/guide/apt/index.html">apt, the Annotation Processing Tool</a>, and for testing. Today I would describe the utility as a simple <em>dependency injection</em> framework, but that wasn't a popular buzzword at the time.</p> <p>Here is a simple but complete example of an API that uses type tokens in the THC pattern, from <a href="http://developers.sun.com/learning/javaoneonline/2006/coreplatform/TS-1512.pdf">Josh's 2006 JavaOne talk</a>:</p> <blockquote> <pre> public class Favorites { private Map<Class<?>, Object> favorites = new HashMap<Class<?>, Object>(); public <T> void setFavorite(Class<T> klass, T thing) { favorites.put(klass, thing); } public <T> T getFavorite(Class<T> klass) { return klass.cast(favorites.get(klass)); } public static void main(String[] args) { Favorites f = new Favorites(); f.setFavorite(String.class, "Java"); f.setFavorite(Integer.class, 0xcafebabe); String s = f.getFavorite(String.class); int i = f.getFavorite(Integer.class); } }</pre> </blockquote> <p>A <tt>Favorites</tt> object acts as a typesafe map from type tokens to instances of the type. The main program in this snippet adds a favorite <tt>String</tt> and a favorite <tt>Integer</tt>, which are later taken out. The interesting thing about this pattern is that a single <tt>Favorites</tt> object can be used to hold things of many (i.e. heterogenous) types but in a typesafe way, in contrast to the usual kind of map in which the values are all of the same static type (i.e. homogenous). When you get your favorite <tt>String</tt>, it is of type <tt>String</tt> and you don't have to cast it. </p> <p>There is a limitation to this pattern. <a href="http://gafter.blogspot.com/2004/09/puzzling-through-erasure-answer.html">Erasure</a> rears its ugly head: </p> <blockquote> <pre>Favorites:15: illegal start of expression f.setFavorite(List<String>.class, Collections.emptyList()); ^</pre> </blockquote> <p>You can't add your favorite <tt>List<String></tt> to a <tt>Favorites</tt> because you simply can't make a type token for a generic type. This design limitation is one that a number of people have been running into lately, most recently <a href="http://blogs.tedneward.com/default.aspx#aeb09cffb-9962-461b-b732-c33d36f96170">Ted Neward</a>. <a href="http://crazybob.org/">"Crazy" Bob Lee</a> also asked me how to solve a related problem in a dependency injection framework he is developing. The short answer is that you can't do it using type tokens.</p> <p>On Friday I realized you can solve these problems without using type tokens at all, using a library. I wish I had realized this three years ago; perhaps there was no need to put support for type tokens directly in the language. I call the new idea <em>super type tokens</em>. In its simplest form it looks like this:</p> <blockquote> <pre>public abstract class TypeReference<T> {}</pre> </blockquote> <p>The <tt>abstract</tt> qualifier is intentional. It forces clients to subclass this in order to create a new instance of <tt>TypeReference</tt>. You make a super type token for <tt>List<String></tt> like this: </p> <blockquote> <pre>TypeReference<List<String>> x = new TypeReference<List<String>>() {};</pre> </blockquote> <p>Not quite as convenient as writing <tt>List<String>.class</tt>, but this isn't too bad. It turns out that you can use a super type token to do nearly everything you can do with a type token, and more. The object that is created on the right-hand-side is an anonymous class, and using reflection you can get its interface type, including generic type parameters. Josh calls this pattern "Gafter's Gadget". <a href="http://crazybob.org/">Bob Lee</a> elaborated on this idea as follows:</p> <blockquote> <pre>import java.lang.reflect.Constructor; import java.lang.reflect.InvocationTargetException; import java.lang.reflect.ParameterizedType; import java.lang.reflect.Type; import java.util.ArrayList; import java.util.List; /** * References a generic type. * * @author crazybob@google.com (Bob Lee) */ public abstract class TypeReference<T> { private final Type type; private volatile Constructor<?> constructor; protected TypeReference() { Type superclass = getClass().getGenericSuperclass(); if (superclass instanceof Class) { throw new RuntimeException("Missing type parameter."); } this.type = ((ParameterizedType) superclass).getActualTypeArguments()[0]; } /** * Instantiates a new instance of {@code T} using the default, no-arg * constructor. */ @SuppressWarnings("unchecked") public T newInstance() throws NoSuchMethodException, IllegalAccessException, InvocationTargetException, InstantiationException { if (constructor == null) { Class<?> rawType = type instanceof Class<?> ? (Class<?>) type : (Class<?>) ((ParameterizedType) type).getRawType(); constructor = rawType.getConstructor(); } return (T) constructor.newInstance(); } /** * Gets the referenced type. */ public Type getType() { return this.type; } public static void main(String[] args) throws Exception { List<String> l1 = new TypeReference<ArrayList<String>>() {}.newInstance(); List l2 = new TypeReference<ArrayList>() {}.newInstance(); } } </pre> </blockquote> <p>This pattern can be used to solve <a href="http://blogs.tedneward.com/default.aspx#aeb09cffb-9962-461b-b732-c33d36f96170">Ted Neward's</a> problem, and most problems where you would otherwise use type tokens but you need to support generic types as well as <a href="http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html#4.7">reifiable</a> types. Although this isn't much more than a <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6192554">generic factory interface</a>, the automatic hook into the rich generic reflection system is more than you can get with simple class literals. With a few more bells and whistles (<tt>toString</tt>, <tt>hashCode</tt>, <tt>equals</tt>, etc) I think this is a worthy candidate for inclusion in the JDK. </p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/3085325539025155770' onclick=''>21 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Wednesday, November 22, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='7515625649324994183'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/11/linear-time-sort-puzzler.html'>Linear Time Sort Puzzler</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>Interviewing for an engineering position at Google can be grueling and humbling. You get less than an hour with each interviewer, and may get one technical problem after another to solve. If you have performance anxiety you may have a hard time focusing on the problem. The best approach, if you can do it, is to think of the interview as a technically challenging but friendly brainstorming session. If you get hired, that's what your life will be like.</p> <p>My friend, Jim Davis, told me about someone he interviewed earlier this week. The candidate thought the interview wasn't going well and hoped to impress Jim by sharing an idea he had: a new algorithm for sorting in linear time. It isn't a sort based exclusively on comparisons; it can be proven that any such sort must perform O(<em>n</em> log <em>n</em>) comparisons. It isn't a bucket sort, which is a standard algorithm for this problem (assuming certain characteristics of the input set). But the candidate's algorithm helped Jim understand the candidate's capabilities. </p> <p>The algorithm works like this: you start by making a linear scan through the <em>n</em> numbers to be sorted and note the largest and smallest of the elements. Using that, you compute a linear function <em>f(x)</em> that will map the smallest input element to zero and the largest to <em>n</em>. Then, for each input element <em>x<sub>i</sub></em>, you fork a task that waits <em>f(x<sub>i</sub>)</em> milliseconds and then outputs <em>x<sub>i</sub></em>. After <em>n</em> milliseconds the output contains the input elements in sorted order. </p> <p>There may be problems when two tasks attempt to output their data at nearly the same time, but let's ignore that for a moment and assume an "ideal" system. If you have a truly concurrent computer, this may run in O(<em>n</em>) time using O(<em>n</em>) processors, thereby consuming a total of O(<em>n<sup>2</sup></em>) processing time. There are far better concurrent sorting algorithms around. Much more interesting is the idea of running this algorithm on a sequential computer with a non-preemptive scheduler. The non-preemptive scheduler avoids the problem of two tasks producing data at the same time. The scheduler can also ensure that the tasks run in their proper order, even if the running time of some tasks causes others to start slightly "too late". </p> <p>Jim explained the problem with the algorithm, concluding "so you've reduced the problem of sorting in linear time to a different linear time sorting algorithm." After Jim explained this remark, the candidate replied "well, the idea isn't really very well thought out." Here is the puzzle: what was Jim talking about?</p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/7515625649324994183' onclick=''>16 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Monday, November 20, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='3676452317612924752'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/11/thread-pool-puzzler.html'>A Thread Pool Puzzler</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>I participated in the design and development of a couple of concurrency libraries for shared-memory multiprocessors long before such machines were popular. So when I started using <tt>java.util.concurrent</tt> I was already somewhat comfortable with the concepts. But when I used it more intensely for production work in the <a href="//www.google.com/calendar/">Google Calendar</a> server, I ran into a couple of "gotcha" situations. I'd like to tell you about one in particular, in part because it might help you avoid the problem yourself, and in part because I believe this issue exposes some missing functionality in the concurrency framework. </p> <p>Many parallel programming problems can be expressed using <em>fork-join</em> parallelism, in which tasks spawn, or "fork", a number of subtasks that can be executed in parallel. The caller then waits for these subtasks to complete by "join"ing with them. Consider the following sequential program. It is an abstract model of some larger program that has three logical layers.</p> <blockquote> <pre> class Program { static final int N = 3; public static void main(String[] args) { doSomeWork(); loopNtimes(N, new Runnable() { public void run() { doLayerOne(); } }); System.out.println(); } static void doLayerOne() { doSomeWork(); loopNtimes(N, new Runnable() { public void run() { doLayerTwo(); } }); } static void doLayerTwo() { doSomeWork(); loopNtimes(N, new Runnable() { public void run() { doLayerThree(); } }); } static void doLayerThree() { doSomeWork(); } static void loopNtimes(int n, Runnable runnable) { for (int i=0; i<n; i++) runnable.run(); } static void doSomeWork() { System.out.print("."); try { Thread.sleep(500L); } catch (InterruptedException _) {} } }</pre> </blockquote> <p>This program prints 40 dots, taking a half second for each one. It runs to completion in about 20 seconds. Let's rewrite the loops as concurrent (instead of sequential) loops, using an idiom recommended by Martin Buchholz. To do that we replace the method loopNtimes with the following: </p> <blockquote> <pre> static ExecutorService threadPool = Executors.newCachedThreadPool(); static void loopNtimes(int n, Runnable runnable) { Collection<Callable<Object>> c = new ArrayList<Callable<Object>>(); for (int i=0; i<n; i++) c.add(Executors.callable(runnable)); Collection<Future<Object>> futures = null; try { futures = threadPool.invokeAll(c); } catch (InterruptedException _) {} if (futures != null) for (Future<Object> f : futures) { try { f.get(); } catch (InterruptedException ex) {} catch (ExecutionException ex) { ex.printStackTrace(); System.exit(1); } } }</pre> </blockquote> <p>This requires a couple of other minor changes to the program (two import statements and <tt>System.exit(0)</tt> at the end of <tt>main</tt>), but the program now runs in two seconds instead of twenty. So far so good, but if <tt>N</tt> is larger, say a hundred, this program fails. It throws <tt>OutOfMemoryError</tt> becuase it tries to allocate too many threads. My first attempt to fix this replaced the thread pool by one containing a fixed number of threads:</p> <blockquote><pre> static ExecutorService threadPool = Executors.newFixedThreadPool(100);</pre> </blockquote> <p>This version of the program works and runs in 2 seconds. But why should we use 100 threads? If we imagine that the <tt>Thread.sleep</tt> statements represent computationally intensive parts of the program, it might make more sense to have a number of threads approximately the same as the number of physical processors. I'm running this on a machine with an Intel Cetrino Duo processor, which acts roughly like 2 processors. Let's be generous, however, and make ten threads. So we modify this version of the program by changing 100 to 10. That won't be as fast as the version with 100 threads, but just how fast will it be?</p> <p>If you haven't guessed the punch line by now, I'll tell you: with ten threads in the pool the program prints 11 periods and then <em>deadlocks</em>! If you use a debugger to examine the state of the program to figure out what's going on, you'll find the main thread waiting for <tt>invokeAll</tt>, three threads in <tt>doLayerOne</tt> waiting for <tt>invokeAll</tt>, seven threads in <tt>doLayerTwo</tt> waiting for <tt>invokeAll</tt>, and <em>there are no threads left</em> to do any of the work of calling <tt>doLayerThree</tt>. This is a classic <a href="http://www.amazon.com/exec/obidos/ASIN/0321349601/wwwgaftercom-20"> thread starvation deadlock</a>. </p> <p> If you're just trying out this program to see what happens, you might be slightly annoyed and finally give up and hit control-C to quit the Java program, but when our program (<a href="//www.google.com/calendar">Google Calendar</a>) encounters this kind of problem our customers get annoyed, give up, and sign up for a competitor like <a href="http://calendar.yahoo.com/">Yahoo Calendar</a> or <a href="http://30boxes.com/">30Boxes</a>. Hey, don't click those links; trust me, you really want <a href="//www.google.com/calendar">Google Calendar</a>. My point is that we can't leave this to chance.</p> <p>What can or should we do about this problem? The first idea is to change the 10 back into 100, but those numbers are pulled out of thin air. Without analyzing the behavior and interaction of all the places where the thread pool is used, understanding the dynamic performance of the application under real loads, and placing bounds on the number of tasks that will be used at each level in the program's hierarchy, it is difficult or impossible to pick a number that will always avoid this kind of deadlock. Another idea is to use unbounded thread pools, but as we've seen under high load situations those can cause an explosion in the number of threads, resulting in the program failing by running out of memory. </p> <p>What we did to address this issue is avoid the single monolithic thread pool altogether. Instead, we use a separate thread pool at every level in the hierarchy. In terms of this example, we would have a thread pool for use in <tt>main</tt>, one for use in <tt>doLayerOne</tt>, and one for use in <tt>doLayerTwo</tt>. Every subsystem that requires concurrency gets its own personal thread pool. That way every layer that uses concurrency is guaranteed to make progress when it has work to do, so this kind of deadlock cannot occur. But there is a cost to this as well: balancing the sizes of these thread pools is a black art. During operation we have hundreds of threads, most of which are sitting around doing nothing. Besides being a waste of resources, the generous surplus of "extra" threads make debugging more difficult than it should be. If the system doesn't break down so neatly into layers (perhaps because there are recursive loops in the call cycle of the subsystems) then even this solution can break down and result in thread starvation. </p> <p>The situation is not entirely hopeless. In my opinion, this kind of thread starvation should never occur because there is <em>always</em> one thread that can contribute processing power toward execution the subtasks: the thread that is waiting for the subtasks to complete. Here's <a href="http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/AbstractExecutorService.java?rev=HEAD&content-type=text/vnd.viewcvs-markup"> the implementation</a> of <tt>invokeAll</tt> as it appears in the JDK: </p> <blockquote> <pre> public <T> List<Future<T>> invokeAll(Collection<Callable<T>> tasks) throws InterruptedException { if (tasks == null) throw new NullPointerException(); List<Future<T>> futures = new ArrayList<Future<T>>(tasks.size()); boolean done = false; try { for (Callable<T> t : tasks) { FutureTask<T> f = new FutureTask<T>(t); futures.add(f); execute(f); } for (Future<T> f : futures) { if (!f.isDone()) { try { f.get(); } catch(CancellationException ignore) { } catch(ExecutionException ignore) { } } } done = true; return futures; } finally { if (!done) for (Future<T> f : futures) f.cancel(true); } }</pre></blockquote> <p>This code does not use the <em>current</em> thread to do any of the work of invoking the callables. Below is a slightly modified version (I've added a line to the original and refactored it to make it a static method that we can put in the program) that uses the current thread to do any work that another thread hasn't already started. I've highlighted the newly added code: </p> <blockquote> <pre> public static <T> List<Future<T>> invokeAll( ExecutorService threadPool, Collection<Callable<T>> tasks) throws InterruptedException { if (tasks == null) throw new NullPointerException(); List<Future<T>> futures = new ArrayList<Future<T>>(tasks.size()); boolean done = false; try { for (Callable<T> t : tasks) { FutureTask<T> f = new FutureTask<T>(t); futures.add(f); threadPool.execute(f); } <span style="color: #FF0000;font-weight: bold;">// force unstarted futures to execute using the current thread for (Future<T> f : futures) ((FutureTask)f).run();</span> for (Future<T> f : futures) { if (!f.isDone()) { try { f.get(); } catch(CancellationException ignore) { } catch(ExecutionException ignore) { } } } done = true; return futures; } finally { if (!done) for (Future<T> f : futures) f.cancel(true); } }</pre> </blockquote> <p>Using this version of <tt>invokeAll</tt>, the program does not experience thread starvation. If the thread pool is reduced in size to just one thread, the program runs to completion in about 11 seconds, because two threads are contributing to doing the work (the main thread and the thread from the pool). </p> <p>I discussed this issue with Doug Lea, and he warned me that selecting tasks for efficient scheduling in a fork-join concurrency framework is not trivial; the standard solution is to have a double-ended queue for each worker task where it enqueues its subtasks. The worker removes the most recently generated task from this queue for itself to process, thereby simulating a depth-first execution strategy in the single-thread case. When a worker finds itself without any work to do, it steals work from the other end of the queue of another task. That is, it should steal one of the least-recently created (course-grained) subtasks. In addition, it is beneficial to have a mechanism to avoid the queue altogether for the bottom of the call chain. Doug told me that this strategy was pioneered by <a href="http://citeseer.ist.psu.edu/frigo98implementation.html">the Cilk work</a>, but I first learned about this strategy 10 years earlier reading <a href="http://portal.acm.org/citation.cfm?id=65864.65866"><em>WorkCrews: An Abstraction for Controlling Parallelism</em> by Mark T. Vandervoorde and Eric S. Roberts</a>. My implementation provides exactly this behavior but with a much simpler implementation. The invocation of <tt>run</tt> executes one of the tasks most recently generated by the current thread. When a thread has no more work to do, it removes work from the queue of the underlying <tt>ExecutorService</tt>, which is a FIFO queue, and so it takes the least-recently generated task of all workers. On the other hand, because this implementation shares a single queue among all worker threads, there may be additional synchronization overhead compared to the WorkCrews/Cilk solution. </p> <p>It is possible to use the existing concurrency utilities to work around the problem, if you don't mind the task scheduling being far from optimal. You can do that by setting <tt>CallerRuns</tt> policy on a <tt>ThreadPoolExecutor</tt>, and using a synchronous queue:</p> <blockquote> <pre>static ThreadPoolExecutor threadPool = new ThreadPoolExecutor(0, 10, 60L, TimeUnit.SECONDS, new SynchronousQueue<Runnable>()); static { threadPool.setRejectedExecutionHandler( new ThreadPoolExecutor.CallerRunsPolicy()); }</pre> </blockquote> <p>Doug explained to me that the <a href="http://gee.cs.oswego.edu/dl/papers/fj.pdf">earlier public-domain version of the concurrency utilities had a full implementation of a framework for fork-join parallelism</a>, but they didn't get included in JDK5: </p> <p> <blockquote>"... The vast majority of such usages are nicest to support as "loop parallelism" utilities. And it is not so much that utilities based on FJ tasks are inconvenient to use that has kept them out, but instead uncertainty about basic APIs until closures are settled. All of the methods for aggregate operations on collections and arrays (applyToAll, map, reduce, mapReduce, findAny, findAll, etc) require function-type arguments (perhaps along with some sort of purity annotation as might be introduced via JSR305) that, depending on how things work out otherwise, would need to be introduced more generally."</blockquote> </p> <p>Did you think I would get through an entire blog post without mentioning <a href="http://www.javac.info/">Closures</a>?</p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/3676452317612924752' onclick=''>13 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Monday, November 13, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='658007273777465170'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/11/closures-esoterica-completion.html'>Closures Esoterica: completion transparency</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>The <a href="http://www.javac.info/">Closures for Java</a> draft specifiation (currently at v0.3) is the product of a lot of work. Everything in the spec has been discussed and scrutinized before being placed into the specification, and is there for a reason. From your point of view, you have seen snapshots of our specification, with very little explanation of why things are the way they are. Changes from one revision to another may seem arbitrary. I am not writing detailed notes on the progress and evolution of the specification and its prototype, because there is too much to explain and too little time would be left for me to work on the specification and prototype. I am, after all, working on this on my own time. I suspect few people would care for that level of detail anyway. Much of the work on the specification takes place during face-to-face meetings, after which I update the specification to reflect our decisions. Some issues get resolved through email discussions. We've been keeping an eye on the comments on this blog, various message boards, mailing lists, and elsewhere for input, and meeting with interested folks, and that has been a very useful part of the process. Thank you for your help!</p> <p>I'm preparing the next revision of the specification, and we just resolved an issue by email. Unless you know what the issue is, the change in the upcoming version of the specification will appear totally arbitrary. Because the issue was resolved by email, I have a nice record of the problem and its resolution. Here is an edited excerpt of the the start of our discussion:</p> <blockquote> <p>We'd like programmers to be able to define their own control constructs. One thing that would make this easier would be if programmer-defined control constructs act like built-in ones for the purposes of handling reachability of statements (and "can complete normally"). That's why we added the <em>bottom</em> type <tt>java.lang.Unreachable</tt> to the specification. But just having that isn't enough. Watch as I try to define a <tt>withLock</tt> method that is <em>completion transparent</em>.</p> <p> First, ignoring reachability, the library writer might define</p> <pre style="margin-left: 0.5in;"><throws E> void withLock(Lock lock, {=>void throws E} block) throws E { ... }</pre> <p>this achieves exception transparency, but not completion transparency. If the block returns a value, this would work:</p> <pre style="margin-left: 0.5in;"><T, throws E> T withLock(Lock lock, {=>T throws E} block) throws E { ... }</pre> <p>this works because a closure that can't complete normally can be converted, via the closure conversion, to <tt>{=>Unreachable}</tt>. In practice, any specific invocation of <tt>withLock</tt> will either have a block that doesn't return anything (i.e. <tt>=>void</tt>) or can't complete normally (i.e. <tt>=>Unreachable</tt>}. You might think, therefore, that the library writer need only write these two overloaded methods to achieve completion transparency, and let overload resolution take care of the rest.</p> <p>Unfortunately it isn't that simple. With these two methods, an invocation of <tt>withLock</tt> using a closure that can't complete normally can be an invocation of either of these methods. That's because the closure conversion can convert a closure that results in <tt>Unreachable</tt> to an interface whose method returns <tt>void</tt>. Since both are applicable, the compiler must select the most specific. Neither of these methods is more specific than the other (the closures are unrelated, given our scheme of mapping function types to interfaces), so the invocation is ambiguous.</p> <p> I don't propose that we mess with the specification for "most specific". I'm afraid that would be a disaster, though maybe you can reassure me that it isn't. Instead, I propose that the closure conversion be allowed to convert a closure that results in <tt>void</tt> to an interface whose method's return type is <tt>java.lang.Void</tt>. The generated code would naturally return a <tt>null</tt> value. Then the library writer would write only the second version, above, and it would work both for the <tt>void</tt>-returning case and the <tt>Unreachable</tt>-returning case. I think being able to write control abstractions as a single method (instead of two overloadings) is a significant advantage. Additionally, this API is more flexible because it can be used by programmers to pass a value back through from the closure to the caller.</p> </blockquote> <p>We discussed this issue and found the proposed resolution our best option. The next version of the proposal will include in the closure conversion a provision allowing conversion of a closure that returns <tt>void</tt> to an interface type whose method returns <tt>java.lang.Void</tt>. You can see hints in this email thread that the syntax of a function type has changed slightly (the <tt>throws</tt> clause has moved inside the curly braces), and that a function type is now specified to be an interface type, rather than having its own type rules. The specification is getting simpler, which is definitely a move in the right direction!</p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/658007273777465170' onclick=''>5 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Sunday, November 05, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='5594504437517228574'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/11/reified-generics-for-java.html'>Reified Generics for Java</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>Many people are unsatisfied with the restrictions caused by the way generics are implemented in Java. Specifically, they are unhappy that generic type parameters are not <em>reified</em>: they are not available at runtime. Generics are implemented using <em>erasure</em>, in which generic type parameters are simply removed at runtime. That doesn't render generics useless, because you get typechecking at compile-time based on the generic type parameters, and also because the compiler inserts casts in the code (so that you don't have to) based on the type parameters.</p> <p>Generics are implemented using erasure as a response to the design requirement that they support <em>migration compatibility</em>: it should be possible to add generic type parameters to existing classes without breaking source or binary compatibility with existing clients. <a href="http://gafter.blogspot.com/2004/09/puzzling-through-erasure-answer.html">I wrote about this two years ago.</a> Migration compatibility is exploited widely in JDK5; all of the collection classes and interfaces use generics, yet existing code using collections continues to work. Without migration compatibility, the collection APIs could not be retrofitted use generics; we would probably have added a separate, new set of collection APIs that use generics. That was the approach used by C# when generics were introduced, but Java did not take this approach because of the huge amount of pre-existing Java code using collections. </p> <p>While solving one set of problems, erasure adds a set of its own problems. For a type parameter <tt>T</tt>, you can't write a class literal <tt>T.class</tt>. You can't use <tt>instanceof</tt> to test if an object is of type <tt>T</tt>. And you can't create an array of <tt>T</tt>. But it gets worse. You also can't write class literals for generic types like <tt>List<String>.class</tt>, or test if an object is an <tt>instanceof List<String></tt>, or create an array of <tt>List<String></tt>. The implementation of generics using erasure also causes Java to have <em>unchecked</em> operations, which are operations that would normally check something at runtime but can't do so because not enough information is available. For example, a cast to the type <tt>List<String></tt> is an unchecked cast, because the generated code checks that the object is a <tt>List</tt> but doesn't check whether it is the right kind of list. </p> <p>It isn't too late to add reified generics to Java. There are two basic approaches. The first uses the language as it exists today but adds the generic type information at runtime. In the ideal world, we wait until every bit of Java code in the world has been modified to use generics <em>safely</em>, and then go through a transition in which we start recording type parameters at runtime by using a new javac and VM. There are two main difficulties with this approach. First, it is not compatible. It is not source compatible because you would no longer be allowed to use raw types (i.e., it is impractical to wait until <em>all</em> code has been generified); it is not binary compatible because new clients would invoke new kinds of constructors for generic classes that also record the type parameters, but existing classes do not have those constructors. (A hybrid approach is being investigated in which the system records type parameters only when they are available, but I haven't yet seen a workable proposal along these lines.) The second problem is more insidious: lots of existing code uses generics but uses them in an <em>unsafe</em> way. For example, I have seen code that creates an <tt>ArrayList<Object></tt>, but later casts it to a <tt>List<String></tt> where the author knows that it only contains objects of type <tt>String</tt>. I would not be surprised to find such code in the JDK. Such code must fail at runtime when generics are reified, so some existing (but working) code would be broken. </p> <p>The other approach modifies the language so that the declaration of a generic parameter distinguishes reified type parameters from erased ones. It is a pure extension of the language. The existing syntax for generics would continue to designate generics by type erasure, but a newly introduced syntax would be used to declare reified type parameters. Perhaps something like this:</p> <pre style="margin-left:0.5in">class NewCollection<<span style="color:#FF3300;font-weight:bold;font-size:larger">class</span> E> extends Collection<E> { ... } class NewList<<span style="color:#FF3300;font-weight:bold;font-size:larger">class</span> E> extends NewCollection<E>, List<E> { ... } </pre> <p>The rules for these reified type parameters are straightforward. When using a reified generic class, the type argument has to be a reified type. You would not be allowed to create a <tt>NewCollection</tt> in its raw form. Code that uses only reified types would never get an <em>unchecked</em> warning from the compiler, because the compiler can always generate the correct checking code. If you have a reference of type <tt>Collection</tt> that refers to a <tt>NewCollection<String></tt>, you would get a runtime error if you attempt to put anything other than a <tt>String</tt> into it. In this sense reified collections are like <tt>java.util.Collections.checkedCollection</tt>, only better because the element type can itself be generic and the guarantees are stronger. You can even create an array of <tt>E</tt> inside an implementation of this type. But there is a disadvantage: the strategy requires a new set of reified Collections APIs parallel to the existing erasure-based ones. This is why C# introduced new collections APIs when they introduced generics. </p> <p>As the above declaration illustrates, the new reified collection interfaces could be extensions of the existing collection interfaces. Consequently, existing APIs that receive old collections can be passed new collections. For example, you could pass a <tt>NewCollection<String></tt> to an API that is declared to receive a <tt>Collection<String></tt>. In addition, the new reified collection classes (that is, the implementations) could be extensions of the existing collection classes. That allows the implementation of the old and new collection classes to be shared, and provides a nice migration path. Existing APIs that return old collections can be modified to return new collections. Over time, most libraries can be migrated to use the new APIs without breaking backward compatibility (though it would break unsafe clients). In this way we can have a more gradual migration than would be possible with the first approach.</p> <p>I don't mean to trivialize the work involved: this requires a significant revision of the VM and language specifications and a significant effort from the teams who implement VMs, java compilers (i.e. javac and Hotspot), and the core JDK libraries. From the programmer's point of view, however, the language change is small and mostly involves removing restrictions. </p> <p>Approaching the problem this way has a secondary benefit. Because the new reified collection interfaces don't exist yet, it is possible for methods to be added to them when they are introduced. Perhaps sorting methods belong in <tt>NewList</tt>? If reified generics are added at the same time as (or after) closures, a number of useful methods could be added to take advantage of closures. Filters, mappers, reducers, and visitors are just some of the ideas.</p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/5594504437517228574' onclick=''>58 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Sunday, October 22, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='4088507463105488790'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/10/closures-for-java-v03.html'>Closures for Java (v0.3)</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><span style="font-style:italic;">This post discusses a draft proposal for adding support for closures to the Java programming language for the Dolphin (JDK 7) release. It was carefully designed to interoperate with the current idiom of one-method interfaces. The latest version of the proposal and a prototype can be found at <a href="http://www.javac.info/">http://www.javac.info/</a>.</span> <p>We've just completed a major revision and simplification of the Closures for Java specification. Rather than post the specification on this blog, it is <a href="http://www.javac.info/closures-v03.html">on its own web page, here</a>. There are two versions of the specification: one with function types and one without. There is a pulldown menu at the top of the specification that makes it display only the text relevant to the version of the specification you want to see. Keeping the specification in this form will allow us to more easily maintain the two parallel specifications so we can compare them and delay a decision on this issue until later. These specifications are the starting point for our prototype. </p> <p>There are two significant changes in this revision. First, there is a completely new syntax for closures and function types. Using the new syntax, with functon types, you can write</p> <blockquote> <pre>{int,int => int} plus = {int x, int y => x+y};</pre> </blockquote> <p>As you can see, we're proposing to add the new "arrow" token => to the syntax. Just to be perfectly clear, this code declares a variable of function type </p> <blockquote> <pre>{int,int => int}</pre> </blockquote> <p>which is a function that takes two ints and yields an int. The variable is named "plus" and it is assigned the closure value </p> <blockquote> <pre>{int x, int y => x+y}</pre> </blockquote> <p>which is a closure that receives two ints (named x and y) and yields their sum. </p> <p>The second major change has to do with the treatment of "restricted" closures. We've done away with the "synchronized" parameters from the previous revision of the specification. Instead, you can inherit from a marker interface to restrict the closure conversion. If you don't use the marker interface, then closures are not restricted when converted to that type. </p> <p>Another important change is to the meaning of a function type. It is now defined to be a system-provided interface type, and it is provided in a way that gives the required subtype relations among function types. That means that in order to invoke a value of function type, instead of simply placing arguments in parens after the function value, you use its "invoke" method. This significantly simplifies the name lookup rules for variables of function type. In fact, now there are no special rules at all. </p> <p>As always, your feedback and ideas are welcome. </p></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/4088507463105488790' onclick=''>20 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Friday, October 13, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='116076072063501958'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/10/concurrent-loops-using-java-closures.html'>Concurrent Loops Using Java Closures</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p>The <span style="FONT-FAMILY:Courier New">java.util.concurrent</span> package has very nice support for writing concurrent loops. I used it recently to improve the performance of some code in the <a href="//www.google.com/calendar" target="blank_" title="Google Calendar">Google Calendar</a> Server. In the Calendar Server, we have a class representing an event on a calendar. The following method on an event computed the set of attendees to the event. The old code looked something like this:<br/> <br/> <div style="MARGIN-LEFT:40px"> <span style="FONT-FAMILY:Courier New">public Collection<Principal> getAttendees() {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    List<Principal> result = new ArrayList<Principal>();</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    for (EventResponse r : getResponses()) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New"></span><span style="FONT-FAMILY:Courier New">        </span><span style="FONT-FAMILY:Courier New">if (r.mayAttend()) {<br/>             </span><span style="FONT-FAMILY:Courier New">result.add(r.getAttendee());<br/>         }</span><span style="FONT-FAMILY:Courier New"></span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    }</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    return result;</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">}</span><br/> </div> <br/> The problem with this code, it turned out, was that <span style="FONT-FAMILY:Courier New">getAttendee()</span> has to talk to a remote server to look up the <span style="FONT-FAMILY:Courier New">Principal</span> in a database, and although the remote server is very fast, it is far enough away that there is some latency. Since this loop is sequential, when there are many responses it spends most of its time waiting for a response from the remote server, over and over again. Consequently the call to <span style="FONT-FAMILY:Courier New">getAttendees()</span> was very slow for events with many attendees. One solution to this kind of problem would be to send a single batch request, and that is probably the best long-term solution to the problem, but the server in this case doesn't yet know how to handle batch requests. So our fix to the immediate performance problem was to use <span style="FONT-FAMILY:Courier New">java.util.concurrent</span> and make the requests in parallel; this did speed things up significantly:<br/> <br/> <div style="MARGIN-LEFT:40px"> <span style="FONT-FAMILY:Courier New">public Collection<Principal> getAttendees() {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    final List<Principal> result = new ArrayList<Principal>();</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    CompletionService<Void> ecs =</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">        new ExecutorCompletionService<Void>(threadPool);</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    for (final EventResponse r : getResponses()) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">        ecs.submit(new Callable<Void>() {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">            public Void call() {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                if (r.mayAttend()) {<br/>                     try {</span><span style="FONT-FAMILY:Courier New"></span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                        Principal attendee = r.getAttendee();</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                        synchronized (result) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                            result.add(attendee);</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                        }</span><span style="FONT-FAMILY:Courier New"></span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                    } catch (Throwable ex) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                        LOGGER.log(Level.SEVERE, "Uncaught Exception", ex);<br/>                     }<br style="FONT-FAMILY:Courier New"/> </span> <span style="FONT-FAMILY:Courier New">                }</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                return null;</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">            }</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">        });</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    }</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    // wait for the tasks to complete</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    for (final EventResponse r : getResponses()) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">        try {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">            /*discard*/ ecs.take().get();</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">        } catch (InterruptedException ex) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">            throw new AssertionError(ex); // shouldn't happen</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">        } catch (ExecutionException ex) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">            LOGGER.log(Level.SEVERE, "Uncaught Exception", ex);</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">        }</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    }</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    return result;</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">}</span><br/> </div> <br/> When I find code like this I have a few reactions. First, my eyes glaze over at the complexity. Then, if I'm interested, I look carefully at the code to try to understand it. After all, I'm likely to want to do something like this again someday. Finally, I bookmark it so I can add it to my bag of tricks.<br/> I don't think writing a concurrent loop should have to be so complex. Here is what I would like to have written:<br/> <br/> <div style="MARGIN-LEFT:40px"> <span style="FONT-FAMILY:Courier New">public Collection<Principal> getAttendees() {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    List<Principal> result = new ArrayList<Principal>();</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    for eachConcurrently(EventResponse r : getResponses(), threadPool) {<br/>         if (r.mayAttend()) {<br style="FONT-FAMILY:Courier New"/> </span> <span style="FONT-FAMILY:Courier New"></span><span style="FONT-FAMILY:Courier New">            Principal attendee = r.getAttendee();</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">            synchronized (result) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                result.add(attendee);<br/>             }<br style="FONT-FAMILY:Courier New"/> </span> <span style="FONT-FAMILY:Courier New">        }</span><span style="FONT-FAMILY:Courier New"></span><span style="FONT-FAMILY:Courier New"></span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    }</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">    return result;</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">}</span><br/> </div> <br/> You might think that in order to do this kind of thing we would need to add a concurrent looping statement to the language. Actually, it is possible to add the concurrent looping construct as a library method if you have closures in the language! It isn't trivial to write, but that's why we have people like Doug Lea in the world. An API like this "<span style="FONT-FAMILY:Courier New">for eachConcurrently</span>" thing should be written once by an expert and placed into the JDK for everyone to use.<br/> <br/> What should happen if you use <span style="FONT-FAMILY:Courier New">continue</span>, <span style="FONT-FAMILY:Courier New">break</span>, or <span style="FONT-FAMILY:Courier New">return</span> within the body of this loop, or <span style="FONT-FAMILY:Courier New">throw</span> an exception? The <span style="FONT-FAMILY:Courier New">continue</span> case is easy: it just completes execution of that one iteration, and the other iterations proceed on their merry way. The semantics of <span style="FONT-FAMILY:Courier New">break</span> are a bit subtle, but obvious once you realize this is supposed to act like a loop: it completes the current iteration and cancels any other iterations that have not completed, and control returns to the caller of <span style="FONT-FAMILY:Courier New">for eachConcurrently</span>. Handling a <span style="FONT-FAMILY:Courier New">return</span> statement is similar: it cancels any uncompleted iterations and returns from the enclosing method, which in this case would be <span style="FONT-FAMILY:Courier New">getAttendees</span>. Finally, any exception that propagates out of a loop iteration cancels uncompleted iterations and propagates from the loop.<br/> <br/> p.s.: Martin Buchholz offered the follow improved version of the code using <span style="FONT-FAMILY:Courier New">java.util.concurrent</span>:<br/> <br/> <div style="MARGIN-LEFT:40px"> <span style="FONT-FAMILY:Courier New"> public Collection<Principal> getAttendees() {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">     final Collection<Principal> result</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">         = new ConcurrentLinkedQueue<Principal>();</span><br style="FONT-FAMILY:Courier New"/> <div style="direction:ltr"> <p><span style="FONT-FAMILY:Courier New">    final Collection<Callable<Object>> tasks</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">         = new ArrayList<Callable<Object>>();</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">     for (final EventResponse r : getResponses())</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">         tasks.add(Executors.callable(new Runnable() { public void run() {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">             try {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                 if (r.mayAttend())</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                     result.add(r.getAttendee());</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">             } catch (Throwable ex) {</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">                 LOGGER.log(Level.SEVERE, "Uncaught Exception", ex);</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">             }}}));</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">     try {<br style="FONT-FAMILY:Courier New"/> </span><span style="FONT-FAMILY:Courier New">        threadpool.invokeAll(tasks);</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New">     } catch (InterruptedException ex) {}<br style="FONT-FAMILY:Courier New"/>     return new ArrayList<Principal>(result);</span><br style="FONT-FAMILY:Courier New"/> <span style="FONT-FAMILY:Courier New"> </span> }<br/> </p> </div> </div></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/116076072063501958' onclick=''>20 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Monday, October 02, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='115985043889128988'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/10/iterative-control-abstraction-user.html'>Iterative control abstraction: user-defined loops</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p>A couple of people have written about using Java closures to write methods that act as looping constructs. For example, iterating through a map is currently an ugly exercise in boilerplate:<br/> <br/> <div style="MARGIN-LEFT: 40px"> <span style="FONT-FAMILY: courier new,monospace">Droid seekDroid(Map<String,Droid> map) {</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">    <span style="COLOR: #cc0000">for (Map.Entry<String,Droid> entry : map.entrySet()) {</span></span><br style="FONT-FAMILY: courier new,monospace; COLOR: #cc0000"/> <span style="FONT-FAMILY: courier new,monospace; COLOR: #cc0000">        String droidName = entry.getKey();</span><br style="FONT-FAMILY: courier new,monospace; COLOR: #cc0000"/> <span style="FONT-FAMILY: courier new,monospace; COLOR: #cc0000">         Droid droid = entry.getValue();</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">        if (droid.isSought()) {</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">            System.out.printf("'%s' is the droid we seek.%n", droidName);</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">             return droid;</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">        }</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">     }</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">}</span><br/> </div> <br/> It has been proposed that we add looping methods to <span style="FONT-FAMILY: courier new,monospace"> Collection</span> and <span style="FONT-FAMILY: courier new,monospace">Map</span> that take advantage of closures, but it would be incompatible to add methods to an existing interface. We can accomplish the same thing using static methods. With one small additional twist to the closures proposal, we could make it even easier to write a method that iterates over maps. Here is what we want our client to look like:<br/> <br/> <div style="MARGIN-LEFT: 40px"> <span style="FONT-FAMILY: Courier New">import static </span><span style="FONT-FAMILY: Courier New">java.util.Collections.eachEntry;</span><br/> ...<br/> <span style="FONT-FAMILY: courier new,monospace"></span><span style="FONT-FAMILY: courier new,monospace">Droid seekDroid(Map<String,Droid> map) { </span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace; COLOR: #009900">     <span style="FONT-WEIGHT: bold">for</span> eachEntry(String droidName, Droid droid : map) {</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">         if (droid.isSought()) {</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">             System.out.printf("'%s' is the droid we seek.%n", droidName);</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">             return droid;</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">         }</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">     }</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace"> }</span><br/> </div> <br/> To enable this, the following would be added to <span style="FONT-FAMILY: Courier New">java.util.Collections</span>:<br/> <br/> <div style="MARGIN-LEFT: 40px"> <span style="FONT-FAMILY: courier new,monospace">public interface Block2<K,V,throws E> {</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">    void invoke(K k, V v) throws E;</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">}</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">public static <K,V,throws E><br/> void <span style="COLOR: #009900; FONT-WEIGHT: bold">for</span> eachEntry(Map<K,V> map, Block2<K,V,E> block) throws E { </span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">     for (Map.Entry<K,V> entry : map.entrySet()) {</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">        block.invoke(entry.getKey(), entry.getValue());</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">    }</span><br style="FONT-FAMILY: courier new,monospace"/> <span style="FONT-FAMILY: courier new,monospace">}</span><br/> </div> <span style="FONT-FAMILY: courier new,monospace"></span><br/> Notice <a></a>the "<span style="FONT-FAMILY: courier new,monospace">for</span>" qualifier on the declaration of <span style="FONT-FAMILY: courier new,monospace">eachEntry</span>, and the <span style="FONT-FAMILY: courier new,monospace"> for</span> keyword on its invocation. Methods defined this way and then invoked using the control abstraction syntax would require the use of the <span style="FONT-FAMILY: courier new,monospace">for</span> keyword on the invocation. The compiler arranges such control abstractions to act like loops, by properly interpreting <span style="FONT-FAMILY: courier new,monospace">break</span> and <span style="FONT-FAMILY: courier new,monospace">continue</span> statements within the body of the closure. Although this example doesn't use <span style="FONT-FAMILY: courier new,monospace">break</span> or <span style="FONT-FAMILY: courier new,monospace">continue</span> statements, the mere presence of the <span style="FONT-FAMILY: courier new,monospace"> for</span> keyword on the invocation helps the reader understand the code. In this way user-defined control constructs could be written that appear and act as loops.<br/> <br/></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/115985043889128988' onclick=''>26 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Sunday, September 17, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='115850029098253266'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/09/failure-of-imagination-in-language_17.html'>Failure of Imagination in Language Design</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><p>Failure of imagination - that is, failure to make language constructs orthogonal because you aren't quite sure how people will need to use them together - is one of the most common and severe errors you can make in programming language design. It is an error that is often impossible to correct after the fact. There is an approach to programming language design that you can take to maximize your opportunities to err in this way: consider the interactions of individual language features and decide on a case-by-case basis if the interaction will be allowed or not (or even what the semantics should be) based on whether or not you can find use cases and which semantics best fit those use cases. <p>This is an approach favored by expert API designers, because the domain of API design is best suited to this approach and these designers expect their expertise to carry from one domain to the other. In an API, the components of the API fit together in particular and well-defined patterns due to the typing and subtyping relationships between the elements; the job of the API designer is to ensure that the patterns you can build with the API elements satisfy a set of use cases. <p>In a programming language, on the other hand, the elements that are used to assemble programs are ideally orthogonal and independent. Programmers can assemble the elements in arbitrary ways, often unexpected but surprisingly useful ways. The "patterns" movement for example records some of these ideas by creating a common terminology for newly discovered ways of assembling programs from primitives. <p>To be sure, use cases also play a very important role in language design, but that role is a completely different one than the kind of role that they play in API design. In API design, satisfying the requirements of the use cases is a <em>sufficient</em> condition for completeness. In language design, it is a <em>necessary</em> condition.</p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/115850029098253266' onclick=''>4 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Wednesday, September 13, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='115821034131743710'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/09/nominal-closures-for-java-version-02.html'>Nominal Closures for Java (version 0.2)</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><span style="font-style:italic;">This post describes a draft proposal for adding support for closures to the Java programming language for the Dolphin (JDK 7) release. It was carefully designed to interoperate with the current idiom of one-method interfaces. The latest version of the proposal and a prototype can be found at <a href="http://www.javac.info/">http://www.javac.info/</a>.</span> <p> <em>This revision of the closures proposal eliminates function types, introduces the Unreachable type, and gives related reachability rules. A closure's "return" type is now called its result type. The abbreviated invocation syntax now takes any statement, not just a block, to make nesting work nicely.</em> </p> <p style="TEXT-ALIGN: right"> <em>Gilad Bracha, Neal Gafter, James Gosling, Peter von der Ah茅</em> </p> <p> Modern programming languages provide a mixture of primitives for composing programs. C#, Javascript, Ruby, Scala, and Smalltalk (to name just a few) have direct language support for delayed-execution blocks of code, called <em>closures</em>. A proposal for closures is working its way through the C++ standards committees as well. Closures provide a natural way to express some kinds of abstraction that are currently quite awkward to express in Java. For programming in the small, closures allow one to abstract an algorithm over a piece of code; that is, they allow one to more easily extract the common parts of two almost-identical pieces of code. For programming in the large, closures support APIs that express an algorithm abstracted over some computational aspect of the algorithm. This proposal outlines a specification of closures for Java without introducing function types. </p> <h2> 1. Closure Literals </h2> <p> We introduce a syntactic form for constructing a closure value: </p> <blockquote> <dl> <dt><em>Expression3</em></dt><dd><em>Closure</em></dd><dt><em>Closure</em></dt><dd><em>FormalParameters</em> { <em>BlockStatements<sub>opt</sub></em> <em>Expression<sub>opt</sub></em> }</dd> </dl> </blockquote> <h3> Example </h3> <p> We can write a closure that adds two to its argument like this: </p> <blockquote> <pre>interface IntFunction {<br/> int invoke(int i);<br/>}<br/>IntFunction plus2 = (int x){ x+2 };</pre> </blockquote> <h2> 2. The type of a closure </h2> <p> A closure literal has a "closure type" that exists transiently at compile time. It is converted to some object type at compile-time; See <span style="FONT-STYLE: italic">Closure Conversion</span> for details. It is a compile-time error if a closure is not subject to a closure conversion. </p> <p> The type of a closure is inferred from its form as follows: </p> <p> The argument types of a closure are the types of the declared arguments. </p> <p> If the body of the closure ends with an expression, the result type of the closure is the type of that expression; otherwise if the closure can complete normally, the result type is <code>void</code>; otherwise the result type is <code>Unreachable</code>. </p> <p> The set of thrown types of a closure are those checked exception types thrown by the body.<br/> </p> <h3> Example </h3> <p> The following illustrates a closure being assigned to a variable of a compatible object type.<br/> </p> <blockquote> <pre>interface VoidIntBlock<throws E> {<br/> void invoke(int i) throws E;<br/>}<br/>VoidIntBlock<InterruptedException> sleeper = (int t) { Thread.sleep(t); };</pre> </blockquote> <h2> 3. <code>synchronized</code> parameters </h2> <p> We allow the qualifier <tt>synchronized</tt> <a></a>to be used on formal method arguments. When a closure is passed to such a parameter, the closure conversion (see<em> Closure Conversion</em>) is allowed to close over its context: the closure may use non-final local variables from enclosing scopes, and may use control-transfer statements such as <tt>break</tt>, <tt>continue</tt>, and <tt>return</tt> that transfer control outside of the body of the closure. An overriding method declaration may only add (i.e. may not remove) the <tt>synchronized</tt> qualfier to formal parameters compared to a method it overrides; an abstract method that overrides one whose parameter is declared <tt>synchronized</tt> must itself declare the parameter <tt>synchronized</tt>. If a closure is passed to a parameter that is not declared <tt>synchronized</tt>, then the only local variables from enclosing scopes it may access are those that are marked <tt>final</tt>. </p> <blockquote> Note: this qualifier is necessary to enable API writers to distinguish <em>synchronous </em>from <em>asynchronous</em> receivers of closures. For compatibility with existing APIs, most of which are asynchronous, the default is not allowing closing over the context. The constraint on overriders preserves the substitutability of subtypes: if a closure is allowed when passed to the superclass method, it must be allowed when passed to the subclass method. A consequence of the overriding constraint is that no existing overridable method can be retrofitted to accept synchronous closures without breaking source compatibility. Static methods such as <tt>AccessController.doPrivileged</tt> can be retrofitted. The <tt>synchronized</tt> keyword isn't an ideal choice, but it is the best we've found so far. </blockquote> <p> Names that are in scope where a closure is defined may be referenced within the closure. It is a compile-time error to access a local variable declared outside the closure from within a closure unless the closure is passed to a parameter that is declared <tt>synchronized</tt> or the variable was declared final.<br/> </p> <blockquote> Note: a local variable that is referenced within a closure is in scope in the body of the closure. Consequently the lifetime of objects referenced by such variables may extend beyond the time that the block containing the local declaration completes. </blockquote> <h2> 4. Closure conversion </h2> <p> A closure literal may be assigned to a variable or parameter of any compatible object type by the <span style="FONT-STYLE: italic">closure conversion</span>: </p> <p> There is a <em>closure conversion</em> from every closure of type T to every interface type that has a single method <span style="FONT-STYLE: italic">m</span> with signature U such that T is <span style="FONT-STYLE: italic">compatible with </span>U. A closure of type <em>T</em> is <span style="FONT-STYLE: italic">compatible with</span> a method <em>U</em> iff all of the following hold: </p> <ul> <li> Either <ul> <li> The result type of <em>T</em> is either the same as the return type of <em>U</em> or</li> <li> There is an assignment conversion from the result type of <em>T</em> to the return type of <em>U</em>; or</li> <li> the result type of <em>T</em> is <code>Unreachable</code>.<br/></li> </ul></li> <li> <em>T</em> and <em>U</em> have the same number of arguments.</li> <li> For each corresponding argument position in the argument list of <em>T</em> and <em>U</em>, both argument types are the same.<span style="FONT-STYLE: italic"></span></li> <li> Every exception type in the throws of <em>T</em> is a subtype of some exception type in the throws of <em>U</em>.</li> </ul> <p style="MARGIN-LEFT: 40px"> </p> <p> If the closure is not passed to a parameter that was declared <tt>synchronized</tt> then </p> <ul> <li> it is a compile-time error if the closure being converted contains a break, continue <a></a>or return statement whose execution would result in a transfer of control outside the closure</li> <li> it is a compile-time error if the closure being converted refers to a non-final local variable or parameter declared in an enclosing scope.</li> </ul> <p> The closure conversion to a non-<tt>synchronized</tt> parameter applies only to closures that obey the same restrictions that apply to local and anonymous classes. The motivation for this is to help catch inadvertent use of non-local control flow in situations where it would be inappropriate. Examples would be when the closure is passed to another thread, or stored in a data structure to be invoked at a later time when the method invocation in which the closure originated no longer exists. </p> <p style="MARGIN-LEFT: 40px"> Note: The closure conversion occurs at compile-time, not at runtime. This enables javac to allocate only one object, rather than both a closure and an anonymous class instance.<br/> </p> <p style="MARGIN-LEFT: 40px"> We are considering an additional qualifier on non-final local variables that allows a closure to access the variable.<br/> </p> <h3> Example </h3> <p> <a></a> We can use the existing <code>Executor</code> framework to run a closure in the background: </p> <blockquote> <pre> void sayHello(java.util.concurrent.Executor ex) {<br/> ex.execute((){ System.out.println("hello"); });<br/> }</pre> </blockquote> <h2> 5. Exception type parameters </h2> <p> To support exception transparency, we add a new type of generic formal type argument to receive a set of thrown types. <em>[This deserves a more formal treatment]</em> What follows is an example of how the proposal would be used to write an exception-transparent version of a method that locks and then unlocks a <tt>java.util.concurrent.Lock</tt>, before and after a user-provided block of code: </p> <blockquote> <pre>interface Block<throws E> {<br/> void invoke() throws E;<br/>}<br/>public static <throws E extends Exception><br/>void withLock(Lock lock, Block<E> block) throws E {<br/> try {<br/> lock.lock();<br/> block.invoke();<br/> } finally {<br/> lock.unlock();<br/> }<br/>}</pre> </blockquote> <p> This can be used as follows: </p> <blockquote> <pre>withLock(lock, (){<br/> System.out.println("hello");<br/>});</pre> </blockquote> <p> <a></a> This uses a newly introduced form of generic type parameter. The type parameters <tt>E</tt> are declared to be used in throws clauses. If the <tt>extends</tt> clause is omitted, a type parameter declared with the <tt>throws</tt> keyword is considered to extend <tt>Exception</tt> (instead of <tt>Object</tt>, which is the default for other type parameters). This type parameter accepts multiple exception types. For example, if you invoke it with a block that can throw <tt>IOException</tt> or <tt>NumberFormatException</tt> the type parameter <tt>E</tt> would be <tt>IOException|NumberFormatException</tt>. In those rare cases that you want to use explicit type parameters with multiple thrown types, the keyword <tt>throws</tt> is required in the invocation, like this: </p> <blockquote> <pre>Locks.<throws IOException|NumberFormatException>withLock(lock) {<br/> whatever();<br/>}</pre> </blockquote> <p> You can think of this kind of type parameter accepting disjunction, "or" types. That is to allow it to match the exception signature of a closure that throws any number of different checked exceptions. If the block throws no exceptions, the type parameter would be the type <tt>null</tt>. </p> <p> Type parameters declared this way can be used only in a <tt>throws</tt> clause or as a type argument to a generic method, interface, or class whose type argument was declared this way too. </p> <h2> 6. Non-local control flow </h2> <p> One purpose for closures is to allow a programmer to refactor common code into a shared utility, with the difference between the use sites being abstracted into a closure. The code to be abstracted sometimes contains a <code>break</code>, <code>continue</code>, or <code>return</code> statement. This need not be an obstacle to the transformation. A <code>break</code> or <code>continue</code> statement appearing within a closure may transfer to any matching enclosing statement provided the target of the transfer is in the same innermost <em>ClassBody</em>. </p> <p> A <code>return</code> statement always returns from the nearest enclosing method or constructor. </p> <p> If a <code>break</code> statement is executed that would transfer control out of a statement that is no longer executing, or is executing in another thread, the VM throws a new unchecked exception, <code>UnmatchedNonlocalTransfer</code>. Similarly, an <code>UnmatchedNonlocalTransfer</code> is thrown when a <code>continue</code> statement attempts to complete a loop iteration that is not executing in the current thread. Finally, an <code>UnmatchedNonlocalTransfer</code> is thrown when a return statement is executed if the method invocation to which the return statement would transfer control is not on the stack of the current thread. </p> <h2> 7. Definite assignment </h2> <p> The body of a closure may not assign to a final variable declared outside the closure. </p> <p> A closure expression does not affect the DA/DU status of any variables it names.<br/> </p> <h2> 8. The type <code>Unreachable</code> </h2> <p> We add the non-instantiable type <code>java.lang.Unreachable</code>, corresponding to the standard type-theoretic <span style="FONT-STYLE: italic">bottom</span>. Values of this type appear only at points in the program that are formally unreachable. This is necessary to allow transparency for closures that do not return normally.<code></code> <code>Unreachable</code> is a subtype of every type (even primitive types). No other type is a subtype of <code>Unreachable</code>. It is a compile-time error to convert <code>null</code> to <code>Unreachable</code>. It is an error to cast to the type <code>Unreachable</code>.<span style="FONT-STYLE: italic"></span><br/> </p> <h3> Example </h3> <p> The following illustrates a closure being assigned to a variable of the correct type. </p> <blockquote> <pre>interface NullaryFunction<T, throws E> {<br/> T invoke() throws E;<br/>}<br/>NullaryFunction<Unreachable,null> thrower = () { throw new AssertionError(); };</pre> </blockquote> <h2>8. Unreachable statements </h2><p>An expression statement in which the expression is of type <code>Unreachable</code> cannot complete normally. </p><h2>10. Abbreviated invocation syntax. </h2> <p> A new invocation statement syntax is added to make closures usable for control abstraction: </p> <blockquote> <dl><dt><em>AbbreviatedInvocationStatement</em> </dt><dd><em>Primary</em> ( <em>ExpressionList</em> ) <em>Statement</em> </dd><dt><em>AbbreviatedInvocationStatement</em> </dt><dd><em>Primary</em> ( <em>Formals</em> ) <em>Statement</em> </dd><dt><em>AbbreviatedInvocationStatement</em> </dt><dd><em>Primary</em> ( <em>Formals</em> : <em>ExpressionList</em> ) <em>Statement</em> </dd></dl> </blockquote> <p> This syntax is a shorthand for the following statement: </p> <blockquote> <em>Primary</em> ( <em>ExpressionList</em>, ( <em>Formals</em> ) { <em>Statement</em> } ); </blockquote> <p>This syntax makes some kinds of closure-receiving APIs more convenient to use to compose statements. </p> <blockquote>Note: There is some question of the correct order in the rewriting. On the one hand, the closure seems most natural in the last position when not using the abbreviated syntax. On the other hand, that doesn't work well with varargs methods. Which is best remains an open issue. </blockquote> <p> We could use the shorthand to write our previous example this way </p> <blockquote> <pre>withLock(lock) {<br/> System.out.println("hello");<br/>}<br/></pre> </blockquote> <p> This is not an expression form for a very good reason: it looks like a statement, and we expect it to be used most commonly as a statement for the purpose of writing APIs that abstract patterns of control. If it were an expression form, an invocation like this would require a trailing semicolon after the close curly brace of a controlled block. Forgetting the semicolon would probably be a common source of error. The convenience of this abbreviated syntax is evident for both synchronous (e.g. <tt>withLock</tt>) and asynchronous (e.g. <tt>Executor.execute</tt>) use cases. Another example of its use would be a an API that closes a <span style="FONT-FAMILY: monospace">java.io.Closeable</span> after a user-supplied block of code:</p><blockquote>class OneArgBlock<T, throws E> {<br/>    void invoke(T t) throws E;<br/>}<br/><T extends java.io.Closeable, throws E><br/>void closeAtEnd(OneArgBlock<? super T,E> block, T t) throws E {<br/>    try {<br/>        block.invoke();<br/>    } finally {<br/>        try { t.close(); } catch (IOException ex) {}<br/>    }<br/>}<br/> </blockquote> <p> We could use the shorthand with this API to close a number of streams at the end of a block of code:<br/> </p> <blockquote> <pre>closeAtEnd(FileReader in : makeReader()) closeAtEnd(FileWriter out : makeWriter()) {<br/> // code using in and out<br/>}</pre> </blockquote> <h2> Acknowledgments </h2> <p> The authors would like to thank the following people whose discussions and insight have helped us craft, refine, and improve this proposal: </p> <blockquote><em>Lars Bak</em>, <em>Cedric Beust</em>, <em>Joshua Bloch</em>, <em>Martin Buchholz</em>, <em>Danny Coward</em>, <em>Erik Ernst</em>, <em>Christian Plesner Hansen, Kohsuke Kawaguchi, </em><span class="q"></span><em>Doug Lea</em>, <em>"crazy" Bob Lee</em>, <em>Martin Odersky</em>, <em>Tim Peierls</em>, <em>John Rose</em>, <em>Ken Russell</em>, <em>Mads Torgersen</em>, <em>Jan Vitek</em>, and <em>Dave Yost</em>.</blockquote></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/115821034131743710' onclick=''>33 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> <div class="date-outer"> <h2 class='date-header'><span>Thursday, September 07, 2006</span></h2> <div class="date-posts"> <div class='post-outer'> <div class='post'> <a name='115768977974943416'></a> <h3 class='post-title'> <a href='https://gafter.blogspot.com/2006/09/closures-for-java-version-01.html'>Closures for Java (version 0.1)</a> </h3> <div class='post-header-line-1'></div> <div class='post-body'> <p><span style="font-style:italic;">This post describes a draft proposal for adding support for closures to the Java programming language for the Dolphin (JDK 7) release. It was carefully designed to interoperate with the current idiom of one-method interfaces. The latest version of the proposal and a prototype can be found at <a href="http://www.javac.info/">http://www.javac.info/</a>.</span> <p> <em>This revision of the proposal drops local functions and the special nonlocal return syntax, adds support for generic type parameters that can be used to represent thrown exceptions, and has only one form of closure literal. It also adds an abbreviated invocation statement that supports very convenient control abstraction. Soon I'll present a parallel proposal based on interfaces (that is, without function types) and contrast the two proposals.</em> </p><p style="text-align: right;"> <em>Gilad <a></a>Bracha<a></a>, Neal Gafter, James Gosling, Peter von der Ah茅</em> </p> <p> Modern programming languages provide a mixture of primitives for composing programs. C#, Javascript, Ruby, Scala, and Smalltalk (to name just a few) have direct language support for <em>function types</em> and inline function-valued expression, called <em>closures</em>. A proposal for closures is working its way through the C++ standards committees as well. Function types provide a natural way to express some kinds of abstraction that are currently quite awkward to express in Java. For programming in the small, closures allow one to abstract an algorithm over a piece of code; that is, they allow one to more easily extract the common parts of two almost-identical pieces of code. For programming in the large, closures support APIs that express an algorithm abstracted over some computational aspect of the algorithm. We propose to add function types and closures to Java. We anticipate that the additional expressiveness of the language will simplify the use of existing APIs and enable new kinds of APIs that are currently too awkward to express using the best current idiom: interfaces and anonymous classes. </p> <h2>1. Function Types </h2> <p> We introduce a new syntactic form: </p> <blockquote> <dl> <dt><em>Type</em></dt><dd><em>Type</em> ( <em>TypeList</em><sub><em>opt</em></sub> ) <em>FunctionThrows<sub>opt</sub></em></dd><dt><em>FunctionThrows</em></dt><dd><em></em><code>throws</code> <em>ThrowsTypeList</em><br> </dd><dt><em>ThrowsTypeList</em></dt><dd><em>Type</em></dd><dt><em>ThrowsTypeList</em></dt><dd><em>ThrowsTypeList</em> VBAR <em>Type</em></dd><dt>VBAR</dt><dd>|</dd> </dl> </blockquote> <p> These syntactic forms designate <em>function types</em>. A function type is a kind of reference type. A function type consists of a return type, a list of argument types, and a set of thrown exception types. </p> <p style="margin-left: 40px;"> Note: the existing syntax for the throws clause in a method declaration uses a comma to separate elements of the <em>ThrowsTypeList</em>. For backward compatibility we continue to allow commas to separate these elements in methods and constructors, but in function types we require the use of the '<code>|</code>' (vertical-bar) character as a separator to resolve a true ambiguity that would arise when a function type is used in a type list. </p> <h2>2. Namespaces and name lookup </h2> <p> The Java programming language currently maintains a strict separation between <em>expression names</em> and <em>method names</em>. These two separate namespaces allow a programmer to use the same name for a variable and for methods. Variables of closure type necessarily blur the distinction between these two namespaces, because they can be used in an expression and they can be invoked. </p> <p> When searching a scope for a method name, if no methods exist with the given name then variables of the given name that are of function type are considered candidates. If more than one exists (for example, function-typed variable declarations are inherited from separate supertypes), the reference is considered ambiguous. </p> <p> We allow a function to be invoked from an arbitrary (for example, parenthesized) expression: </p> <blockquote> <dl> <dt><em>Primary</em></dt><dd><em>Primary</em> <em>Arguments</em></dd> </dl> </blockquote> <h2>3. Closure Literals </h2> <p> We also introduce a syntactic form for constructing a value of function type: </p> <blockquote> <dl> <dt><em>Expression3</em></dt><dd><em>Closure</em></dd><dt><em>Closure</em></dt><dd><em>FormalParameters</em> { <em>BlockStatements<sub>opt</sub></em> <em>Expression<sub>opt</sub></em> }</dd> </dl> </blockquote> <h3> Example </h3> <p> We can write a function that adds two to its argument like this: </p> <blockquote> <pre> int(int) plus2 = (int x){ x+2 };</pre> </blockquote> <h2>4. The type of a closure </h2> <p> The type of a closure is inferred from its form as follows: </p> <p> The argument types of a closure are the types of the declared arguments. </p> <p> If the body of the closure ends with an expression, the return type of the closure is the type of that expression; otherwise if the closure can complete normally, the return type is <code>void</code>; otherwise the return type is <code>null</code>. </p> <p> The set of thrown types of a closure are those checked exception types thrown by the body. </p> <h3> Example </h3> <p> The following illustrates a closure being assigned to a variable with precisely the type of the closure. </p> <blockquote> <pre>void(int) throws InterruptedException sleeper = (int t) { Thread.sleep(t); };</pre> </blockquote> <h2>5. Subtyping </h2> <p> A function type <em>T</em> is a subtype of function type <em>U</em> iff all of the following hold: </p> <ul> <li> Either <ul> <li> The return type of <em>T</em> is either the same as the return type of <em>U</em> or</li> <li> Both return types are reference types and the return type of <em>T</em> is a subtype of the return type of <em>U</em>, or</li> <li> the return type of <em>U</em> is <code>void</code>.</li> </ul></li> <li> <em>T</em> and <em>U</em> have the same number of declared arguments.</li> <li> For each corresponding argument position in the argument list of <em>T</em> and <em>U</em>, either both argument types are the same or both are reference types and the type of the argument to <em>U</em> is a subtype of the corresponding argument to <em>T</em>.</li> <li> Every exception type in the throws of <em>T</em> is a subtype of some exception type in the throws of <em>U</em>.</li> </ul> <h2>6. Exception checking </h2> <p> The invocation of a function throws every checked exception type in the function's type. </p> <h2>7. Reflection </h2> <p> A function type inherits all the non-private methods from <code>Object</code>. The following methods are added to <code>java.lang.Class</code> to support function types: </p> <blockquote> <pre> public final class java.lang.Class ... {<br> public boolean isFunction();<br> public java.lang.reflect.FunctionType functionType();<br> public Object invokeFunction(Object function, Object ... args)<br> throws IllegalArgumentException | InvocationTargetException;<br> }<br> public interface java.lang.reflect.FunctionType {<br> public Type returnType();<br> public Type[] argumentTypes();<br> public Type[] throwsTypes();<br> }</pre> </blockquote> <p style="margin-left: 40px;"> Note: unlike <code>java.lang.reflect.Method.invoke</code>, <code>Class.invokeFunction</code> cannot throw <code>IllegalAccessException</code>, because there is no access control to enforce; the function value designates a closure, which does not have access modifiers. Access to function values is controlled at compile-time by their <em>scope,</em> and at runtime by controlling the function value. </p> <h2>8. The type of <code>null</code> </h2> <p> We add support for <code>null</code> and the type of <code>null</code> in function types. We introduce a meaning for the keyword <code>null</code> as a type name; it designates the type of the expression <code>null</code>. A class literal for the type of <code>null</code> is <code>null.class</code>. These are necessary to allow reflection, type inference, and closure literals to work for functions that do not return normally. We also add the non-instantiable class <code>java.lang.Null</code> as a placeholder, and its static member field <code>TYPE</code> as a synonym for <code>null.class</code>. </p> <h2>9. Referencing names from the enclosing scope </h2> <p> Names that are in scope where a closure is defined may be referenced within the closure. We do not propose a rule that requires referenced variables be final, as is currently required for anonymous class instances. </p> <blockquote> Note: a local variable that is referenced within a closure is in scope in the body of the closure. Consequently the lifetime of objects referenced by such variables may extend beyond the time that the block containing the local declaration completes. </blockquote> <h2>10. Non-local control flow </h2> One purpose for closures is to allow a programmer to refactor common code into a shared utility, with the difference between the use sites being abstracted into a closure. The code to be abstracted sometimes contains a <code>break</code>, <code>continue</code>, or <code>return</code> statement. This need not be an obstacle to the transformation. A <code>break</code> or <code>continue</code> statement appearing within a closure may transfer to any matching enclosing statement provided the target of the transfer is in the same innermost <em>ClassBody</em>. <p> A <code>return</code> statement always returns from the nearest enclosing method or constructor. </p> <p> If a <code>break</code> statement is executed that would transfer control out of a statement that is no longer executing, or is executing in another thread, the VM throws a new unchecked exception, <code>UnmatchedNonlocalTransfer</code>. (I suspect we can come up with a better name). Similarly, an <code>UnmatchedNonlocalTransfer</code> is thrown when a <code>continue</code> statement attempts to complete a loop iteration that is not executing in the current thread. Finally, an <code>UnmatchedNonlocalTransfer</code> is thrown when a <em>NamedReturnStatement</em> attempts to return from a function or method invocation that is not pending in the current thread. Likewise, an <code>UnmatchedNonlocalTransfer</code> is thrown when a return statement is executed if the method invocation to which the return statement would transfer control is not on the stack of the current thread. </p> <h2>11. Closure conversion </h2> <p> We propose the following closure conversion, to be applied only in those contexts where boxing currently occurs: </p> <p style="margin-left: 40px;"> There is a <em>closure conversion</em> from every closure of type T to every interface type that has a single method with signature U such that T is a subtype of the function type corresponding to U. </p> <p style="margin-left: 40px;"> It is a compile-time error if the closure being converted contains a break, continue or return statement whose execution could result in a transfer of control outside the closure. It is a compile-time error if the closure being converted refers to a non-final local variable or parameter declared in an enclosing scope. </p> <p> We will want to generalize this rule slightly to allow the conversion when boxing or unboxing of the return type is required, e.g. to allow assigning a closure that returns <code>int</code> to an interface whose method returns <code>Integer</code> or vice versa. </p> <p style="margin-left: 40px;"> Note: the closure conversion is applied only to closures (i.e. function literals), not to arbitrary expressions of function type. This enables javac to allocate only one object, rather than both a closure and an anonymous class instance. The conversion avoids hidden overhead at runtime. As a practical matter, javac will automatically generate code equivalent to our original client, creating an anonymous class instance in which the body of the lone method corresponds to the body of the closure. </p> <p> Closure conversion applies only to closures that obey the same restrictions that apply to local and anonymous classes. The motivation for this is to help catch inadvertent use of non-local control flow in situations where it would be inappropriate. Examples would be when the closure is passed to another thread, or stored in a data structure to be invoked at a later time when the method invocation in which the closure originated no longer exists. </p> <h3> Examples </h3> <p> We can use the existing <code>Executor</code> framework to run a closure in the background: </p> <blockquote> <pre> void sayHello(java.util.concurrent.Executor ex) {<br> ex.execute((){ System.out.println("hello"); });<br> }</pre> </blockquote> <p>Here is a definition of an API that locks and then unlocks a <tt>java.util.concurrent.Lock</tt>, before and after a user-provided block of code:</p> <blockquote><pre>public static <E extends Exception><br>void withLock(Lock lock, void() throws E block) throws E {<br> try {<br> lock.lock();<br> block();<br> } finally {<br> lock.unlock();<br> }<br>}</pre> </blockquote> <p>This can be used as follows: </p><blockquote> <pre>withLock(lock, (){<br> System.out.println("hello");<br>});</pre> </blockquote> <p>You might find this syntax a bit tedious. Not to worry - see below. </p><h2>12. Abbreviated invocation syntax. </h2> <p>A new invocation statement syntax is added to make closures usable for control abstraction: </p><blockquote> <dl> <dt><em>AbbreviatedInvocationStatement</em> </dt><dd><em>Primary</em> ( <em>ExpressionList</em> ) <em>Block</em> </dd><dt><em>AbbreviatedInvocationStatement</em> </dt><dd><em>Primary</em> ( <em>Formals</em> ) <em>Block</em> </dd><dt><em>AbbreviatedInvocationStatement</em> </dt><dd><em>Primary</em> ( <em>Formals</em> : <em>ExpressionList</em> ) <em>Block</em> </dd> </dl> </blockquote> <p> This syntax is a shorthand for the following statement: </p> <blockquote> <em>Primary</em> ( <em>ExpressionList</em>, ( <em>Formals</em> ) <em>Block</em> ); </blockquote> <p> Note that this syntax is only a convenience to make some kinds of closure-receiving APIs more convenient to use to compose statements. </p> <p> We could use the shorthand to write our previous example this way </p> <blockquote> <pre>withLock(lock) {<br> System.out.println("hello");<br>}</pre> </blockquote> <p> This is not an expression form for a very good reason: it looks like a statement, and we expect it to be used most commonly as a statement for the purpose of writing APIs that abstract patterns of control. If it were an expression form, an invocation like this would require a trailing semicolon after the close curly brace. Forgetting the semicolon would probably be a common source of error. The convenience of this abbreviated syntax is evident for both synchronous (e.g. <tt>withLock</tt>) and asynchronous (e.g. <tt>Executor.execute</tt>) use cases. </p> <h2>13. Definite assignment </h2> <p>The body of a closure may not assign to a final variable declared outside the closure. </p><p>A closure expression does not affect the DA/DU status of any variables it names.<br> </p><h2>14. Exception type parameters </h2> <p> To support exception transparency, we add a new type of generic formal type argument to receive a set of thrown types. <em>[This deserves a more formal treatment]</em> What follows is an example of how the proposal would be used to write an exception-transparent version of the withLock() example we've been using. The syntax is quite tentative at this point (ideas are welcome). </p> <blockquote> <pre>public static <throws E extends Exception><br>void withLock(Lock lock, void() throws E block) throws E {<br> try {<br> lock.lock();<br> block();<br> } finally {<br> lock.unlock();<br> }<br>}</pre> </blockquote> <p> This method uses a newly introduced form of generic type parameter. The type parameter <tt>E</tt> is declared to be used in throws clauses. If the <tt>extends</tt> clause is omitted, a type parameter declared with the <tt>throws</tt> keyword is considered to extend <tt>Exception</tt> (instead of <tt>Object</tt>, which is the default for other type parameters). This type parameter accepts multiple exception types. For example, if you invoke it with a block that can throw <tt>IOException</tt> or <tt>NumberFormatException</tt> the type parameter <tt>E</tt> would be <tt>IOException|NumberFormatException</tt>. In those rare cases that you want to use explicit type parameters, the keyword <tt>throws</tt> is required in the invocation, like this: </p> <blockquote> <pre>Locks.<throws IOException|NumberFormatException>withLock(lock) {<br> whatever();<br>}</pre> </blockquote> <p> You can think of this kind of type parameter accepting disjunction, "or" types. That is to allow it to match the exception signature of a closure that throws any number of different checked exceptions. If the block throws no exceptions, the type parameter would be the type <tt>null</tt>. </p> <p> Type parameters declared this way can be used only in a <tt>throws</tt> clause or as a type argument to a generic method, interface, or class whose type argument was declared this way too. </p> <h2>15. Implementing a Function Type </h2> <p> A programmer may write a class that implements a function type. The implementation is written as a public method with the keyword <tt>do</tt> in place of the method's identifier. For example </p> <blockquote> <pre>class MyBlock implements void() {<br> public void do() {<br> // implementation of the function<br> }<br>}<br></pre> </blockquote> <p> In this way programmers can, for example, create implementations of function types that are serializable. </p> <h2> Acknowledgments </h2> <p> The authors would like to thank the following people whose discussions and insight have helped us craft, refine, and improve this proposal: </p> <blockquote><em>Lars Bak</em>, <em>Cedric Beust</em>, <em>Joshua Bloch</em>, <em>Martin Buchholz</em>, <em>Danny Coward</em>, <em>Erik Ernst</em>, <em>Christian Plesner Hansen</em>, <em>Doug Lea</em>, <em>"crazy" Bob Lee</em>, <em>Martin Odersky</em>, <em>Tim Peierls</em>, <em>John Rose</em>, <em>Ken Russell</em>, <em>Mads Torgersen</em>, <em>Jan Vitek</em>, and <em>Dave Yost</em>.</blockquote></p> <div style='clear: both;'></div> </div> <div class='post-footer'> <p class='post-footer-line post-footer-line-1'><span class='post-comment-link'> <a class='comment-link' href='https://www.blogger.com/comment/fullpage/post/7803021/115768977974943416' onclick=''>11 comments</a> </span> <span class='post-icons'> </span> <span class='post-backlinks post-comment-link'> </span> </p> <p class='post-footer-line post-footer-line-2'></p> <p class='post-footer-line post-footer-line-3'></p> </div> </div> </div> </div></div> </div> <div class='blog-pager' id='blog-pager'> <span id='blog-pager-newer-link'> <a class='blog-pager-newer-link' href='https://gafter.blogspot.com/search?updated-max=2007-01-19T14:46:00-08:00&max-results=2&reverse-paginate=true' id='Blog1_blog-pager-newer-link' title='Newer Posts'>Newer Posts</a> </span> <span id='blog-pager-older-link'> <a class='blog-pager-older-link' href='https://gafter.blogspot.com/search?updated-max=2006-09-07T21:29:00-07:00&max-results=2' id='Blog1_blog-pager-older-link' title='Older Posts'>Older Posts</a> </span> <a class='home-link' href='https://gafter.blogspot.com/'>Home</a> </div> <div class='clear'></div> <div class='blog-feeds'> <div class='feed-links'> Subscribe to: <a class='feed-link' href='https://gafter.blogspot.com/feeds/posts/default' target='_blank' type='application/atom+xml'>Posts (Atom)</a> </div> </div> </div></div> </div> <div id='sidebar-wrapper'> <div class='sidebar section' id='sidebar'><div class='widget BlogArchive' data-version='1' id='BlogArchive1'> <h2>Blog Archive</h2> <div class='widget-content'> <div id='ArchiveList'> <div id='BlogArchive1_ArchiveList'> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2024/'> 2024 </a> <span class='post-count' dir='ltr'>(1)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2024/09/'> September </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2023/'> 2023 </a> <span class='post-count' dir='ltr'>(1)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2023/08/'> August </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2020/'> 2020 </a> <span class='post-count' dir='ltr'>(1)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2020/12/'> December </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2019/'> 2019 </a> <span class='post-count' dir='ltr'>(2)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2019/11/'> November </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2019/08/'> August </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2017/'> 2017 </a> <span class='post-count' dir='ltr'>(1)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2017/06/'> June </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2016/'> 2016 </a> <span class='post-count' dir='ltr'>(7)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2016/02/'> February </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2016/01/'> January </a> <span class='post-count' dir='ltr'>(6)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2015/'> 2015 </a> <span class='post-count' dir='ltr'>(1)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2015/12/'> December </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2014/'> 2014 </a> <span class='post-count' dir='ltr'>(1)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2014/11/'> November </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2010/'> 2010 </a> <span class='post-count' dir='ltr'>(2)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2010/08/'> August </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2010/02/'> February </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2009/'> 2009 </a> <span class='post-count' dir='ltr'>(2)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2009/03/'> March </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2009/02/'> February </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2008/'> 2008 </a> <span class='post-count' dir='ltr'>(4)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2008/08/'> August </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2008/03/'> March </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2008/02/'> February </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2008/01/'> January </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/'> 2007 </a> <span class='post-count' dir='ltr'>(18)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/12/'> December </a> <span class='post-count' dir='ltr'>(2)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/11/'> November </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/10/'> October </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/07/'> July </a> <span class='post-count' dir='ltr'>(2)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/05/'> May </a> <span class='post-count' dir='ltr'>(2)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/04/'> April </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/03/'> March </a> <span class='post-count' dir='ltr'>(4)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/02/'> February </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2007/01/'> January </a> <span class='post-count' dir='ltr'>(4)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate expanded'> <a class='toggle' href='javascript:void(0)'> <span class='zippy toggle-open'> ▼  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2006/'> 2006 </a> <span class='post-count' dir='ltr'>(20)</span> <ul class='hierarchy'> <li class='archivedate expanded'> <a class='toggle' href='javascript:void(0)'> <span class='zippy toggle-open'> ▼  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2006/12/'> December </a> <span class='post-count' dir='ltr'>(4)</span> <ul class='posts'> <li><a href='https://gafter.blogspot.com/2006/12/closures-talk-and-spec-update.html'>Closures Talk and Spec Update</a></li> <li><a href='https://gafter.blogspot.com/2006/12/javapolis-2006.html'>Javapolis 2006</a></li> <li><a href='https://gafter.blogspot.com/2006/12/type-literals.html'>Type Literals</a></li> <li><a href='https://gafter.blogspot.com/2006/12/super-type-tokens.html'>Super Type Tokens</a></li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2006/11/'> November </a> <span class='post-count' dir='ltr'>(4)</span> <ul class='posts'> <li><a href='https://gafter.blogspot.com/2006/11/linear-time-sort-puzzler.html'>Linear Time Sort Puzzler</a></li> <li><a href='https://gafter.blogspot.com/2006/11/thread-pool-puzzler.html'>A Thread Pool Puzzler</a></li> <li><a href='https://gafter.blogspot.com/2006/11/closures-esoterica-completion.html'>Closures Esoterica: completion transparency</a></li> <li><a href='https://gafter.blogspot.com/2006/11/reified-generics-for-java.html'>Reified Generics for Java</a></li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2006/10/'> October </a> <span class='post-count' dir='ltr'>(3)</span> <ul class='posts'> <li><a href='https://gafter.blogspot.com/2006/10/closures-for-java-v03.html'>Closures for Java (v0.3)</a></li> <li><a href='https://gafter.blogspot.com/2006/10/concurrent-loops-using-java-closures.html'>Concurrent Loops Using Java Closures</a></li> <li><a href='https://gafter.blogspot.com/2006/10/iterative-control-abstraction-user.html'>Iterative control abstraction: user-defined loops</a></li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2006/09/'> September </a> <span class='post-count' dir='ltr'>(5)</span> <ul class='posts'> <li><a href='https://gafter.blogspot.com/2006/09/failure-of-imagination-in-language_17.html'>Failure of Imagination in Language Design</a></li> <li><a href='https://gafter.blogspot.com/2006/09/nominal-closures-for-java-version-02.html'>Nominal Closures for Java (version 0.2)</a></li> <li><a href='https://gafter.blogspot.com/2006/09/closures-for-java-version-01.html'>Closures for Java (version 0.1)</a></li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2006/08/'> August </a> <span class='post-count' dir='ltr'>(4)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2005/'> 2005 </a> <span class='post-count' dir='ltr'>(2)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2005/02/'> February </a> <span class='post-count' dir='ltr'>(2)</span> </li> </ul> </li> </ul> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2004/'> 2004 </a> <span class='post-count' dir='ltr'>(1)</span> <ul class='hierarchy'> <li class='archivedate collapsed'> <a class='toggle' href='javascript:void(0)'> <span class='zippy'> ►  </span> </a> <a class='post-count-link' href='https://gafter.blogspot.com/2004/09/'> September </a> <span class='post-count' dir='ltr'>(1)</span> </li> </ul> </li> </ul> </div> </div> <div class='clear'></div> </div> </div><div class='widget Profile' data-version='1' id='Profile1'> <h2>About Me</h2> <div class='widget-content'> <dl class='profile-datablock'> <dt class='profile-data'> <a class='profile-name-link g-profile' href='https://www.blogger.com/profile/08579466817032124881' rel='author' style='background-image: url(//www.blogger.com/img/logo-16.png);'> Neal Gafter </a> </dt> <dd class='profile-textblock'>Neal Gafter is a Computer Programming Language Designer and Implementer, Amateur Scientist and Philosopher. He works on the Rel compiler at Relational.AI. He previously worked for Microsoft on C#, for Google on Calendar, and for Sun Microsystems on Java. Neal was granted an OpenJDK Community Innovators' Challenge award for his design and implementation of lambda expressions for Java. He is coauthor of <em>Java Puzzlers: Traps, Pitfalls, and Corner Cases</em> (Addison Wesley, 2005). He was a member of the C++ Standards Committee and led the development of C and C++ compilers at Sun Microsystems, Microtec Research, and Texas Instruments. He holds a Ph.D. in computer science from the University of Rochester.</dd> </dl> <a class='profile-link' href='https://www.blogger.com/profile/08579466817032124881' rel='author'>View my complete profile</a> <div class='clear'></div> </div> </div></div> </div>  <div class='clear'> </div> </div>  <div id='footer-wrapper'> <div class='footer no-items section' id='footer'></div> </div> </div></div>  <script src="//www.google-analytics.com/urchin.js" type="text/javascript"> </script> <script type='text/javascript'> _uacct = "UA-605497-1"; urchinTracker(); </script> <script type="text/javascript" src="https://www.blogger.com/static/v1/widgets/4071838938-widgets.js"></script> <script type='text/javascript'> window['__wavt'] = 'AOuZoY4fcQHqNK-HEEYUnZsrZFLMaMhY_g:1745282633675';_WidgetManager._Init('//www.blogger.com/rearrange?blogID\x3d7803021','//gafter.blogspot.com/2006/','7803021'); _WidgetManager._SetDataContext([{'name': 'blog', 'data': {'blogId': '7803021', 'title': 'Neal Gafter\x27s blog', 'url': 'https://gafter.blogspot.com/2006/', 'canonicalUrl': 'http://gafter.blogspot.com/2006/', 'homepageUrl': 'https://gafter.blogspot.com/', 'searchUrl': 'https://gafter.blogspot.com/search', 'canonicalHomepageUrl': 'http://gafter.blogspot.com/', 'blogspotFaviconUrl': 'https://gafter.blogspot.com/favicon.ico', 'bloggerUrl': 'https://www.blogger.com', 'hasCustomDomain': false, 'httpsEnabled': true, 'enabledCommentProfileImages': true, 'gPlusViewType': 'FILTERED_POSTMOD', 'adultContent': false, 'analyticsAccountNumber': '', 'encoding': 'UTF-8', 'locale': 'en', 'localeUnderscoreDelimited': 'en', 'languageDirection': 'ltr', 'isPrivate': false, 'isMobile': false, 'isMobileRequest': false, 'mobileClass': '', 'isPrivateBlog': false, 'isDynamicViewsAvailable': false, 'feedLinks': '\x3clink rel\x3d\x22alternate\x22 type\x3d\x22application/atom+xml\x22 title\x3d\x22Neal Gafter\x26#39;s blog - Atom\x22 href\x3d\x22https://gafter.blogspot.com/feeds/posts/default\x22 /\x3e\n\x3clink rel\x3d\x22alternate\x22 type\x3d\x22application/rss+xml\x22 title\x3d\x22Neal Gafter\x26#39;s blog - RSS\x22 href\x3d\x22https://gafter.blogspot.com/feeds/posts/default?alt\x3drss\x22 /\x3e\n\x3clink rel\x3d\x22service.post\x22 type\x3d\x22application/atom+xml\x22 title\x3d\x22Neal Gafter\x26#39;s blog - Atom\x22 href\x3d\x22https://www.blogger.com/feeds/7803021/posts/default\x22 /\x3e\n', 'meTag': '', 'adsenseHostId': 'ca-host-pub-1556223355139109', 'adsenseHasAds': false, 'adsenseAutoAds': false, 'boqCommentIframeForm': true, 'loginRedirectParam': '', 'view': '', 'dynamicViewsCommentsSrc': '//www.blogblog.com/dynamicviews/4224c15c4e7c9321/js/comments.js', 'dynamicViewsScriptSrc': '//www.blogblog.com/dynamicviews/11e6ba02c47cab30', 'plusOneApiSrc': 'https://apis.google.com/js/platform.js', 'disableGComments': true, 'interstitialAccepted': false, 'sharing': {'platforms': [{'name': 'Get link', 'key': 'link', 'shareMessage': 'Get link', 'target': ''}, {'name': 'Facebook', 'key': 'facebook', 'shareMessage': 'Share to Facebook', 'target': 'facebook'}, {'name': 'BlogThis!', 'key': 'blogThis', 'shareMessage': 'BlogThis!', 'target': 'blog'}, {'name': 'X', 'key': 'twitter', 'shareMessage': 'Share to X', 'target': 'twitter'}, {'name': 'Pinterest', 'key': 'pinterest', 'shareMessage': 'Share to Pinterest', 'target': 'pinterest'}, {'name': 'Email', 'key': 'email', 'shareMessage': 'Email', 'target': 'email'}], 'disableGooglePlus': true, 'googlePlusShareButtonWidth': 0, 'googlePlusBootstrap': '\x3cscript type\x3d\x22text/javascript\x22\x3ewindow.___gcfg \x3d {\x27lang\x27: \x27en\x27};\x3c/script\x3e'}, 'hasCustomJumpLinkMessage': false, 'jumpLinkMessage': 'Read more', 'pageType': 'archive', 'pageName': '2006', 'pageTitle': 'Neal Gafter\x27s blog: 2006'}}, {'name': 'features', 'data': {}}, {'name': 'messages', 'data': {'edit': 'Edit', 'linkCopiedToClipboard': 'Link copied to clipboard!', 'ok': 'Ok', 'postLink': 'Post Link'}}, {'name': 'template', 'data': {'name': 'custom', 'localizedName': 'Custom', 'isResponsive': false, 'isAlternateRendering': false, 'isCustom': true}}, {'name': 'view', 'data': {'classic': {'name': 'classic', 'url': '?view\x3dclassic'}, 'flipcard': {'name': 'flipcard', 'url': '?view\x3dflipcard'}, 'magazine': {'name': 'magazine', 'url': '?view\x3dmagazine'}, 'mosaic': {'name': 'mosaic', 'url': '?view\x3dmosaic'}, 'sidebar': {'name': 'sidebar', 'url': '?view\x3dsidebar'}, 'snapshot': {'name': 'snapshot', 'url': '?view\x3dsnapshot'}, 'timeslide': {'name': 'timeslide', 'url': '?view\x3dtimeslide'}, 'isMobile': false, 'title': 'Neal Gafter\x27s blog', 'description': 'Thoughts about Programming Languages, Science and Philosophy.', 'url': 'https://gafter.blogspot.com/2006/', 'type': 'feed', 'isSingleItem': false, 'isMultipleItems': true, 'isError': false, 'isPage': false, 'isPost': false, 'isHomepage': false, 'isArchive': true, 'isLabelSearch': false, 'archive': {'year': 2006, 'rangeMessage': 'Showing posts from 2006'}}}]); _WidgetManager._RegisterWidget('_NavbarView', new _WidgetInfo('Navbar1', 'navbar', document.getElementById('Navbar1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HeaderView', new _WidgetInfo('Header1', 'header', document.getElementById('Header1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogView', new _WidgetInfo('Blog1', 'main', document.getElementById('Blog1'), {'cmtInteractionsEnabled': false, 'lightboxEnabled': true, 'lightboxModuleUrl': 'https://www.blogger.com/static/v1/jsbin/2820493333-lbx.js', 'lightboxCssUrl': 'https://www.blogger.com/static/v1/v-css/3681588378-lightbox_bundle.css'}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogArchiveView', new _WidgetInfo('BlogArchive1', 'sidebar', document.getElementById('BlogArchive1'), {'languageDirection': 'ltr', 'loadingMessage': 'Loading\x26hellip;'}, 'displayModeFull')); _WidgetManager._RegisterWidget('_ProfileView', new _WidgetInfo('Profile1', 'sidebar', document.getElementById('Profile1'), {}, 'displayModeFull')); </script> </body> </html>