First draft of translation document
Howard Lovatt
howard.lovatt at gmail.com
Tue May 18 01:43:41 PDT 2010
It is good to see a draft of how lambdas might be implemented, I think
that it makes it easier to discuss some issues and also clarifies some
parts of the specification.
An alternative to using MethodHandles is to use a Callable interface
and then use inner classes to capture the 'frame'; see runnable code
below. I suspect that the Callable implementation will be:
1. Faster execution in most cases: avoids boxing, binding of
arguments, and interface injection.
2. Simpler: always the same pattern of transformation, no need to
bind arguments, and no need to inject interfaces.
Like any system that doesn't reify the types, including using
MethodHandles, the code below has the normal erasure problems of:
can't have two methods with the same erased signature, can't create an
array, boxing of array elements, no generic static fields, etc.
However in both the code below, see Callable2VL, and in the proposed
MethodHandle translation there is partial reification (for primitive
types and for SAM types), this may well eliminate the boxing of array
elements problem.
In the above comments I said "faster execution in most cases", this
need to be qualified on two fronts:
A. It is hard to be certain, since optimizing JVMs with
MethodHandles aren't available.
B. A case where the alternate translation might well be slower, is
if no variables are captured and no interfaces are injected.
Expanding point B further; the Callable implementation loads one class
per lambda and creates one object per lambda, whereas the MethodHandle
implementation creates multiple objects per lambda (one for the
lambda, others for the capture, others for the binding, and others for
the interface injection) but can avoid a class load if there is no
interface injection (it may also be able to inject interfaces more
efficiently than you can load classes and the number of extra objects
created may be able to be minimized).
As I said; good to see some implementation ideas,
-- Howard.
=================================================================================
/*
* This file is part of Howard Lovatt's PhD Thesis:
* "A Pattern Enforcing Compiler (PEC) for Java".
* Copyright (C) 2003-2010 Howard Lovatt
* PEC is trademarked by Howard Lovatt and Java is trademarked by Sun
Microsystems
* More info: pec.dev.java.net
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* You can contact Howard Lovatt at howard.lovatt at iee.org
* or at 12 Roseberry St., Balmain, NSW, Australia, 2041.
*/
package erasedlambdas;
/**
* Exmples of lambda translation using Callable instead of MethodHandle. It is
* an alternative to {@link
* http://cr.openjdk.java.net/~mcimadamore/lambda_trans.pdf}. Notes:
*
* <ol>
* <li>Main examples shown below only use generic parameters, however
* technique can be extended to use primitives by defining version of
* Callable for boolean, double, long, and void (an example primitive
* Callable is given along with some niotes below - see Callable2VL). Also
* see section 8 of referenced PDF.</li>
* <li>Examples only show up to two arguments, suggest a logirithmic scale be
* used in practice and arguments 0, 1, 2, 5, 10, and 20 supported. Above 20
* is an error (Scala goes to 22 in steps of 1 but does not support
* primitives). Also see section 8 of referenced PDF.</li>
* <li>Like the referenced PDF, any single abstract method (SAM) types must be
* an interface (this restrictiuon could be lifted).</li>
* <li>Like the referenced PDF, has the normal erasure problems of can't have
* two methods with the same erased signature, can't create an
array, etc.</li>
* <li>The examples use _ in names instead of $ so that they will compile</li>
* <li>The concept is to always use an inner class, similar to referenced PDF
* section 6.2, that captures variables and is the lambda that is passed
* round. These inner classes are termed frames.</li>
* <li>If no access to the classes fields are required then the inner class,
* frame, is static.</li>
* <li>If there is a nested scope then there are nested frames.</li>
* <li>If a variable is required in two frames then it is captured in the
* first frame and the first frame is captured in the second frame.</li>
* <li>Instead of a MethodHandle a Callable interface is used</li>
* <li>The advantage are:
*
* <ol>
* <li>Faster execution in most cases: avoids boxing, binding of
* arguments, and interface injection.</li>
* <li>Simpler: always the same patern of transformation, no need to bind
* arguments, and no need to inject interfaces.</li>
* </ol>
* </li>
* </ol>
*
* @author Howard Lovatt
* @version 1 (2010-05-18)
*/
public class Main {
public static void main( final String[] notUsed ) {
new A().foo();
new B().foo();
new C().foo();
new D().foo();
}
}
// Examples
/**
* <pre>
class A {
public void foo() {
List<String> list = ...
list.forEach( #(String s) { System.out.println(s); } );
}
}
* </pre>
*/
class A {
private static final Block<String> frame_1 = new Frame_1(); //
Lifted to outer scope
public void foo() {
List<String> list = new List<String>( String.class, "A", "B", "C" );
list.forEach( frame_1 );
}
private static class Frame_1 // No need to extend a FrameN class
implements Callable1<Void, String>, Block<String> {
public Void _call( String a1 ) {
call( a1 );
return null;
}
public void call( String s ) { System.out.println( s ); }
}
}
/**
* <pre>
class B {
public void foo() {
List>Person< list = ...
final int bottom = ..., top = ...;
List inRange = list.filter(
#(Person p) { p.size >= bottom && p.size <= top } );
System.out.println( inRange );
}
}
* </pre>
*/
class B {
public void foo() {
List<Person> list =
new List<Person>(
Person.class, new Person(), new Person(), new Person() );
final int bottom = 1;
final int top = 1;
final Frame_1 frame_1 = new Frame_1( bottom, top );
List inRange = list.filter( frame_1 );
System.out.println( inRange );
}
private static class Frame_1 extends Frame2<Integer, Integer>
implements Callable1<Boolean, Person>, Filter<Person> {
Frame_1( final Integer e1, final Integer e2 ) { super( e1, e2 ); }
public Boolean _call( Person a1 ) { return filter( a1 ); }
public boolean filter( Person p ) {
return ( p.size >= _e1 ) && ( p.size <= _e2 );
}
}
}
/**
* <pre>
class C {
public void foo() {
List<String> list = ...
shared int totalSize = 0;
list.forEach( #(String s) { totalSize += s.length() } );
System.out.println(totalSize);
}
}
* </pre>
*/
class C {
public void foo() {
List<String> list = new List<String>( String.class, "a", "aa", "aaa" );
final Frame_1 frame_1 = new Frame_1( 0 );
list.forEach( frame_1 );
System.out.println( frame_1._e1 );
}
private static class Frame_1 extends Frame1<Integer>
implements Callable1<Void, String>, Block<String> {
Frame_1( final Integer e1 ) { super( e1 ); }
public Void _call( String a1 ) {
call( a1 );
return null;
}
public void call( String s ) { _e1 += s.length(); }
}
}
/**
* <pre>
class D {
public void foo() {
shared int grandTotal = 0;
List<Department> departments = ...
List<Employee> employees = ...
departments.forEach( #(Department d) {
shared int deptTotal = 0;
employees
.filter(#(Employee e) { e.dept == d })
.forEach(#(Employee e) {
deptTotal += e.salary;
grandTotal += e.salary;
});
System.out.printf("Total for dept %s = %d\n",
d, deptTotal);
});
System.out.printf("Grand total = %d\n", grandTotal);
}
}
* </pre>
*/
class D {
public void foo() {
List<Department> departments =
new List<Department>(
Department.class, new Department(),
new Department() );
final List<Employee> employees =
new List<Employee>(
Employee.class,
new Employee( departments.get( 0 ), 100 ),
new Employee( departments.get( 1 ), 10 ),
new Employee( departments.get( 1 ), 20 ) );
final Frame_1 frame_1 = new Frame_1( 0, employees );
departments.forEach( frame_1 );
System.out.printf( "Grand total = %d\n", frame_1._e1 );
}
private static class Frame_1 extends Frame2<Integer, List<Employee>>
implements Callable1<Void, Department>, Block<Department> {
Frame_1( final Integer e1, final List<Employee> e2 ) { super( e1, e2 ); }
public Void _call( Department a1 ) {
call( a1 );
return null;
}
public void call( Department d ) {
final Frame_2 frame_2 = new Frame_2( d );
final Frame_3 frame_3 = new Frame_3( 0 );
_e2.filter( frame_2 ).forEach( frame_3 );
System.out.printf( "Total for dept %s = %d\n", d, frame_3._e1 );
}
private static class Frame_2 extends Frame1<Department>
implements Callable1<Boolean, Employee>, Filter<Employee> {
Frame_2( final Department e1 ) { super( e1 ); }
public Boolean _call( Employee a1 ) { return filter( a1 ); }
public boolean filter( Employee e ) { return e.dept == _e1; }
}
private class Frame_3 extends Frame1<Integer>
implements Callable1<Void, Employee>, Block<Employee> {
Frame_3( final Integer e1 ) { super( e1 ); }
public Void _call( Employee a1 ) {
call( a1 );
return null;
}
public void call( Employee e ) {
_e1 += e.salary;
Frame_1.this._e1 += e.salary;
}
}
}
}
// Classes needed by examples
class List<T> {
private final T[] ts;
private final Class<T> c;
public List( final Class<T> c, final T... ts ) {
this.c = c;
this.ts = ts;
}
public void forEach( final Block<T> b ) {
for ( final T t : ts ) {
b.call( t );
}
}
public List<T> filter( final Filter<T> f ) {
final boolean[] bs = new boolean[ ts.length ];
int l = 0;
for ( int i = 0; i < bs.length; i++ ) {
if ( f.filter( ts[ i ] ) ) {
bs[ i ] = true;
l++;
} else { bs[ i ] = false; }
}
final T[] newTs = (T[]) java.lang.reflect.Array.newInstance( c, l );
for ( int i = bs.length - 1; i >= 0; i-- ) {
if ( bs[ i ] ) {
l--;
newTs[ l ] = ts[ i ];
}
}
return new List<T>( c, newTs );
}
public T get( final int i ) { return ts[ i ]; }
public String toString() { return java.util.Arrays.toString( ts ); }
}
interface Block<T> {
void call( T t );
}
interface Filter<T> {
boolean filter( T a );
}
class Person {
private static int last = 0;
public final int size = last++;
public String toString() { return "P(" + size + ")"; }
}
class Department {
private static int last = 0;
public final int num = last++;
public String toString() { return "D(" + num + ")"; }
}
class Employee {
private static int last = 0;
public final int num = last++;
public final Department dept;
public int salary;
public Employee( final Department dept, final int salary ) {
this.dept = dept;
this.salary = salary;
}
public String toString() {
return "E(" + num + ", " + dept + ", " + salary + ")";
}
}
// Callables
interface Callable0<R> {
R _call();
}
interface Callable1<R, A1> {
R _call( A1 a1 );
}
interface Callable2<R, A1, A2> {
R _call( A1 a1, A2 a2 );
}
/**
* Example of a Callable that uses primitives. Primitives boolean (B), double
* (D), long (L), and void (V) could be supported. Naming convention is:
*
* <ol>
* <li>Callable</li>
* <li>Followed by the number of arguments, n</li>
* <li>Followed by the return type, if it is a primitive, represented by B, D,
* L, or V, and</li>
* <li>Finally the primitive arguments, also reresented by B, D, L, or V, but
* in alphabetic order</li>
* <li>If the Callable has more than one primitive argument then multiple
* letters are used, e.g. LL represents 2 longs</li>
* <li>If the Callable has a mixture of primitive and reference arguments then
* the reference arguments go first in the _call method</li>
* <li>The alphabetic sorting of the argument order reduces the number of
* Callables; e.g. a Callable with a double and a long argument returning
* void is the same as a Callable with a long and a double argument
* returning void, both are Callable2VDL</li>
* </ol>
*
* <p>The example below is a Callable with a void return type and a long
* argument and a reference argument</p>
*/
interface Callable2VL<A1> extends Callable2<Void, A1, Long> {
void _call2VL( A1 a1, long a2 );
}
// Frames
abstract class Frame1<E1> {
public E1 _e1;
public Frame1( final E1 e1 ) { _e1 = e1; }
}
abstract class Frame2<E1, E2> extends Frame1<E1> {
public E2 _e2;
public Frame2( final E1 e1, final E2 e2 ) {
super( e1 );
_e2 = e2;
}
}
More information about the lambda-dev
mailing list