Java Memory – Why the Overhead When Allocating Objects/Arrays?

It sounds like the authors are referring to complex data structures. In object-oriented languages, like Java, the data structure would be an object that contains a number of fields. In a language like C, the structure would probably be a struct. When you sort, you might only care about sorting by a particular field. The other fields are satellite data - they are part of the structure, but aren't relevant to the sorting algorithms.

When you sort, you can't break the structure. If you have a collection of people with the attributes of a name, a current address, a social security number, and an age and you want to sort them by age, you can't change the association between the four fields. You just need to sort them within the structure based on the value of a field. In this example, age is the key and the satellite data is the name, address, and social security number.

The SAM approach is actually somewhat similar to what Scala (and C++11) do with anonymous functions (created with Scala's => operator or C++11's []() (lambda) syntax).

The first question to answer on the Java side is whether to have the return type of a lambda statement be a new primitve type, like int or byte, or an object type of some sort. In Scala, there are no primitive types -- even an integer is an object of class Int -- and functions are no different, being objects of class Function1, Function2, and so forth, depending on the number of arguments the function takes.

C++11, ruby and python similarly have lambda expressions which return an object which is callable in explicit or implicit way. The returned object has some standard method (such as #call which can be used to call it as a function. C++11, for instance, uses a std::function type which overloads operator() so that calls of the object's call method even look like function calls, textually. :-)

Where the new proposal for Java gets messy is in the use of structural typing to allow assigning such a method to another object, such as a Comparator which has a single main method with a different name. While this is conceptually icky in some ways, it does mean that the resulting object can be passed to existing functions which take an object to represent a callback, a comparator, and so on, and expect to be able to call a well-defined single method such as #compare or #callback. C++'s trick of overriding operator() neatly dodged this issue even before C++11, since all such callback options were callable the same way, and thus the STL required no adjustment to allow C++11 lambdas to be used with sort and so on. Java, not having used a standard naming for such objects in the past (perhaps because no trick like operator overloading made a single approach obvious), isn't so lucky, so this hack prevents them from having to change a whole lot of existing APIs.