15. Events, Continued Again

Part of CS:2820 Object Oriented Software Development Notes, Fall 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

A Small Matter of Efficiency, continued

We discussed using the following interface to implement "call by value" parameter passing:

interface ByName {
        /** Framework to fake up Call by Name parameter passing.
         */
        String s();
                /** object of class ByName can return a string.
                 */
}

In the context of this interface, we used this verbose bit of code to defer the concatenation of of the error message string until it is needed:

                class MyString implements ByName { // example of an inner class
                        public String s() {
                                return "Intersection '" + name + "'";
                        }
                }
                MyString msg = new MyString();
                SyntaxCheck.lineEnd( sc, msg );

This is verbose enough that Java allows a shorthand: Java allows a shorthand. First, we need not name the string msg; we can, instead, create it on the fly in the parameter list of lineEnd():

                SyntaxCheck.lineEnd( sc, new MyString() );

Second, we need not name the class MyString. In fact, in general, if a class is used exactly once, Java allows you to build that class as an anonymous class by placing the class definition directly in the new clause that constructs the only instance of that class. Here, this leads us to the following code:

                SyntaxCheck.lineEnd(
                        sc,
                        new ByName() {
                                public String s() {
                                        return "Intersection '" + name + "'";
                                }
                        }
                }

The above code creates an anonymous instance of an anonymous implementation of the interface ByName in order to embed a definition of the method s in the new class.

Note that, in the definition of SyntaxCheck, the second parameter is declared as an instance of class ByName. Therefore, saying new ByName() here is a bit redundant, since the Java compiler already knows that this parameter will be from that class.

Furthermore, saying public String s() here is also a bit redundant, since the Java compiler already knows, from the definition of class ByName that implementations of this class will only have one method. Therefore, Java permits the following even shorter notation for this:

                SyntaxCheck.lineEnd( sc, () -> "Intersection '" + name + "'" )

The object constructor (p) -> e is called a lambda expression, since it is exactly analogous to the expression λ p. e in conventional lambda calculus. Lambda calculus (look it up in Wikipedia) is a notation developed in the 1930s before its relationship to modern computers and programming was understood. The central idea of lambda calculus it to think of functions (in the strict mathematical sense) as values that can be assigned to variables or passed as parameters. The Greek letter λ (lambda) in this calculus is used as a name of an operator that takes an argument list and a function body (separated by a dot) and returns an anonymous function with that argument list and body. Thus, instead of writing:

f(x) = x + 1

Lambda notation allows us to write this as the assignment of an anonomous function to the variable f.

f = λ x. x + 1

Java allows lambda expressions only to create instances of single-method interfaces. This is a strange special case that was introduced late in the history of Java, but it is a very convenient mechanism where call-by-name semantics is what we really want.

Back to the Pending Event Set

Java priority queues are generic, that is, we can declare: for example:

PriorityQueue <Event> eventSet = new PriorityQueue <Event> ();

But this is not the definition we want, because it will order events by their "natural comparator", while we want them to be ordered on their time field. That means that we need to override the default comparator using a different version of the initializer. Sadly, like many of the more complex classes in the Java library, there are too many alternate initializers offered for priority queues, so it can take considerable time to figure out how to use them.

In Java, the interface Comparator is implemented by any class that offers a method compare(x,y) to compare two elements of the class, returning an integer that is zero if x equal to y (for the purpose of comparison), negative if x < y, and positive if x > y. The caveat for the purpose of comparison is to emphasize that the relationship we have called greater than, equal to or less than need not relate to any intuitive sense of magnitude. All that matters is that this relationship establishes an ordering over the possible values of events. The class comparitor is designed to provided as a lambda abstraction, so you can write this when you create a priority queue:

PriorityQueue <Event> eventSet = new PriorityQueue <Event> (
        (Event e1, Event e2) -> Float.compare( e1.time, e2.time )
);

A Note on Java Architecture

The standard libraries in Java and C++ have taken very different approaches to their queue and priority queue implementations.

In C++, there the library implementations of queues provide a class called queueable. Any object of class queueable may be included in a queue. If you want to enqueue some more complex class, you declare that class as an extension of queueable, adding your application dependent fields and methods. The basic queueable object in a linked list queue, for example, might contain just one field, next, the link to the next field in the list.

In Java, queues are part of the collections framework. Queues and other collections hide the existence of any objects involved in implementing the queue. Instead, you declare the queue to be a queue of some class, and then you can add and remove elements of that class to the queue. Internally, queues may involve other objects, such as a queue node object containing a next field.

In general, for collections implemented by list or tree nodes, Java's approach uses two objects per item in the collection, while C++ will use just one object. Java objects are fairly heavy, with tools for inter-thread synchronization and other material that makes the Java collections framework potentially significantly slower than the equivalent C++ classes.

The Java collections framework is, however, rather elegant, and once you are familiar with it, it can make your programming much more facile. Think of all the lists we have created in our little simulator and how they might have been more difficult to organize if we had to think ahead, when declaring any classes that get put into lists, so that they were declared as extensions to some listable base class.

In effect, the designers of Java have decided that their priority should be to value the programmer's time more than the computer's time, while C++ is more sensitive to computer time. Both have their value. For many applications, development cost is everything, and programmers are the most valuable resource. On the other hand, if you are trying to forecast next week's weather, you need all the performance you can get, and if you are running a Google-scale server farm that draws as much power as a small town, small performance improvements can make huge differences in your electric bill.

In many cases, it may pay to write a large application in a language like Python or Java first, and then, if the application is successful enough that you discover that performance matters, rewrite it in a language like C++. In general, writing new code to solve a problem that has not been solved before is quite expensive, but rewriting that code in a different language, once you understand the problem and once you understand what the program is supposed to do might cost only 1/10 of the original development cost -- so long as you have well documented workign code in hand, preferably with many of the programmers who developed the first version available to answer questions.