Expression Language Prototyping

[Graves, Ian L]

All,

I have just committed a prototype for expression builders that are backed by MethodHandles.  The purpose of the expression builder is to allow a programmer to describe vectorized kernels in a more idiomatic style.  This approach is similar to template-style programming, but the template is executed at runtime.  Programmers construct an expression tree in a statement-like way and then return the tree to be traversed by a builder that constructs a MethodHandle that executes the computation described by the tree.  This approach is similar in spirit to invokebinder[1] in that it approaches the MethodHandle construction problem from a more familiar way, but is different in that it focuses on constructing terms instead of being a fluent API for MethodHandles.


An Expression builder centers around a Builder object that is instantiated with two type arguments that describe its vectorized return type (Element x Shape/Length).  Then, parameters to the constructed MethodHandle are described in subsequent binding operations to the builder.  Each binding operation takes a lambda argument that binds an expression of the type described by the binding operation as well as the builder object itself for internal use inside the lambda.  Expressions are an interface that remains opaque and can only be used inside a builder lambda.  Operations can be sequenced using the builder argument to alias the result of an intermediate computation in the resulting MethodHandle (result re-use).

An addition example follows:

    public static final MethodHandle addKernel = Builder.builder(Float.class,Shapes.L8)
            .bind(Float.class,Shapes.L8,Float.class,Shapes.L8, (a, b, builder) ->builder.return_(a.add(b)))
            .build(TestOps.instance); //Instantiate with a methodhandle map


In the above, we construct an addition expression templated to 8-element float bectors.  The resulting MethodHandle is constructed by the build() method which takes an map of Methodhandle operations and uses them to fill in the expression described by the tree.

One can also nest bindings:

    public static final MethodHandle kern = Builder.builder(Float.class,Shapes.L8).bind(Integer.class, Shapes.L1, Float.class,Shapes.L8, Float.class,Shapes.L8, (i,left,right,b) ->
        b.bindFloatIndexable(Shapes.L8,(arr,bIn) -> {
          Expression<Float,Shapes.LENGTH8> r = arr.get(i);
          Expression<Float,Shapes.LENGTH8> res = left.add(right.mul(r));
          return b.return_(res);
        })
    ).build(TestOps.instance);

In the above (contrived example), we construct a MethodHandle of type (int,Float256Vector,float[])Float256Vector that loads a vector from a given array at an index specified by the int argument, multiplies that by the right argument, then adds it to the left argument.  Currently the prototype is structured such that array bindings are only doable in the above way, but we can flatten them out so they can be done like a regular vector argument.  Notice also that the bind() routine has similarities to LISP-like binding.

Also included are some experiments with loop-level combinators.  These borrow from more functional paradigms.  We can also look at loops themselves inside the expression builder:

//(float[])Float256Vector reduce
public static final MethodHandle mh = Builder.reduce(Shapes.L8,(acc,next, builder) -> builder.return_(acc.add(next)));

These are all highly experimental and assume things like data sources sizes multiples of the vector length,etc.

Also included are experiments with masking:

    public static final MethodHandle mask1 = Builder.builder(Float.class,Shapes.L8).bind(Float.class,Shapes.L8,Float.class,Shapes.L8,(left,right,b) -> {
        Expression<Float,Shapes.LENGTH8> masked = Expressions.mask(Expressions.eq(left,right),left.add(right),left.mul(right));
        return b.return_(masked);
    }).build(TestOps.instance);

The above describes a lane-wise ternary-style masked operation that is executed lanewise using the boolean result of Expressions.eq() to encode a mask.  Masking here is data-oriented and not control-flow oriented.

There are some additional tests and examples in the commit.  I emphasize again that all of this is quite experimental!  The work demonstrates an approach for constructing Expressions in Java in a non-MethodHandle way, but still getting MethodHandles as a result.  I think in areas where we might be constrained to MethodHandles, an approach like this one could be very useful because it reduces the problem back to a more familiar place while decoupling the programmer from having to worry about the underlying implementation details that come with using Code Snippets and MVT.

Any and all feedback is very much appreciated.

Thanks!

Ian


[1] https://github.com/headius/invokebinder