0

I'm trying to see if the template expression pattern can be imitated in Java, to do optimizations like loop fusion.

As an example, I port the c++ classes found in this expression template example to java classes: https://en.wikipedia.org/wiki/Expression_templates#Motivation_and_example

First, a template class VecExpression<E> representing a vector expression. It uses a template parameter E and takes the class type of E as a constructor parameter. It then creates a private variable thisAsE set to this cast to the class type of E

public abstract class VecExpression <E> {
    private VecExpression thisAsE;

    public VecExpression(Class<E> type) throws Exception {
        if(type.isInstance(this)) {
            thisAsE = (VecExpression)type.cast(this);   
        }
        else {
            throw new Exception("Class type must extend VecExpression");
        }
    }

    public double get(int i) {
        return thisAsE.get(i);
    }

    public int size() {
        return thisAsE.size();
    }
}

Second, a class Vec extending VecExpression<Vec> which passes Vec.class into the super constructor and implements the get() and size() methods called in the VecExpression<E> class.

public class Vec extends VecExpression<Vec> {

    private double[] elems;

    public <E> Vec(VecExpression<E> expression) throws Exception {
        super(Vec.class);
        for(int i = 0; i < expression.size(); ++i) {
            elems[i] = expression.get(i);
        }
    }

    public Vec(double[] elems) throws Exception {
        super(Vec.class);
        this.elems = elems;
    }

    public double get(int i) {
        return elems[i];
    }
}

And third, a template class VecSum<E1, E2> which extends VecExpression<VecSum<E1, E2>, and uses its get() method to return the sum of two VecExpression<E>s. The type is passed as an explicit parameter Class<VecSum<E1, E2>> type.

public class VecSum <E1, E2> extends VecExpression<VecSum<E1, E2>> {

    private VecExpression u;
    private VecExpression v;

    public VecSum(Class<VecSum<E1, E2>> type, VecExpression<E1> u, VecExpression<E2> v) throws Exception {
        super(type);
        if(u.size() != v.size()) {
            throw new Exception("Vectors must be of the same size");
        }
        this.u = u;
        this.v = v;
    }

    public double get(int i) {
        return u.get(i) + v.get(i);
    }

    public int size() {
        return v.size();
    }
}

Finally, we use the expression template to generate a class that can add three vectors with a single pass through memory.

public class Main {
    public static void main(String[] args) throws Exception {
        Vec a = new Vec(new double[] {1, 2, 3});
        Vec b = new Vec(new double[] {1, 2, 3});
        Vec c = new Vec(new double[] {1, 2, 3});

        VecSum<Vec, Vec> ab = new VecSum<Vec, Vec>(VecSum<Vec, Vec>.class, a, b);
        VecSum<VecSum<Vec, Vec>, Vec> abc = new VecSum<>(VecSum<VecSum<Vec, Vec>, Vec>.class, ab, c);
    }
}

EDITED as per Louis Wasserman's comment

However, the class types passed into the VecSum constructor don't work because the expression is trying to get a class from a parameterized type. Louis pointed out that implementations of a generic class don't compile to different classes like they do in c++. How would you pass their type, or is there another approach to the expression template pattern?

4
  • 4
    "shouldn't SomeClass<AClass>, SomeClass<BClass>, etc... compile to different classes?" Nope, they don't in Java. Commented Nov 1, 2016 at 21:07
  • "shouldn't ... compile to different classes?" Nope. See type erasure Commented Nov 1, 2016 at 21:08
  • Search for 'type erasure' : docs.oracle.com/javase/tutorial/java/generics/erasure.html Commented Nov 1, 2016 at 21:08
  • 1
    There are no templates in Java. You seem to be letting the similarity in syntax between C++ template and Java generics fool you. The Java compiler will do some type checking and insert some implicit casts for you with generics, but after that it throws the generic information away completely. As others noted, you should search for "erasure" to learn more. Earlier versions of Java did not have generics at all, but it still had many of the now-generic utility classes like ArrayList. It just legacy code you don't get this checking and you had to explicitly cast the result of things like get. Commented Nov 2, 2016 at 1:46

1 Answer 1

2

What you're trying to do won't work in Java, at least insofar as you're trying to use to get a compile-time optimization through the use of a Java generic. The reason is that, unlike a C++ template, the Java generic does not get resolved at compile-time. Since the compiler is not resolving the type at compile-time it cannot use anything about it to make a compile-time optimization. The byte code created by the Java compiler, in some sense, goes the other way "erasing" the generic information completely. If your Java class is class C<A> then everywhere the type A appears in your code, it is replaced by the class Object. If your Java class is class D<E extends F> then everywhere that E appears in your code is replaced by F.

In that case, you might ask why the generics at all. The answer is that before the complier throws away the parameter, it does do type-safe checking on inputs and it implicitly inserts a cast on method returns. That's a convenience that was added to Java a few versions back, but the Java container classes like ArrayList existed. It's just that you didn't have type-safety in the same way that you do now since the inputs were explicitly Object (letting you put in any object even if you knew it was supposed to only contain, say, String objects and forcing you to cast the result of get to, say, a String explicitly).

This is in contrast to a C++ template where the compiler creates a class definition from the template and compiles that class. That class can then be compiled as any other class, including potentially using optimizations that are specific to the value of the template parameter. Moreover, template specialization in C++ allows for template metaprogramming more generally since it allows you to create a base case for recursion in the template parameters.

(You cannot have "generic specialization" in any analogous sense in Java for the reason noted above - The Java compiler is throwing out the generic parameter already, so your "specialized" class - if you tried to define such a thing - would be the same as the "generic" class.)

Finally, as regards your examples, keep in mind that Class with a capital 'C' in Java is a class like any other, including that it derives from Object. This isn't going to get you around the compile-time vs. runtime differences between the C++ templates and the Java generics.

Sign up to request clarification or add additional context in comments.

2 Comments

That's good to know. So, metaprogramming optimization in Java is restricted to reflection, then?
I would not call reflection metaprogramming because that still happens at runtime. This may be semantics though. There is no metaprogramming in Java in the sense that I understand the term "metaprogramming."

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.