Expression Language Prototyping

[John Rose]

On Jun 23, 2017, at 2:53 PM, Graves, Ian L <ian.l.graves at intel.com> wrote:
> 
> All,
> 
> I have just committed a prototype for expression builders that are backed by MethodHandles.

It's a week or two early for fireworks but I'm mentally setting them off in celebration.

> 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.

This looks really good.  It has some boiler-platey parts, but they don't feel
to me like architectural limitations, rather temporary compromises that can
be improved later.  The need to type shape names on temps can be removed
very soon by LVTI ("var x = complicated(expr);").  The need to use fluent
syntax instead of fortran syntax can be removed later by some kind of
liftable lambda mechanism (of which there is at least one concrete proposal
on the way).

> 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).

This is a good compromise between generality (not quite Expression<Element> with subtypes)
and practicality (the Shape argument is enough to keep the vector machinery happy).

> 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
> 

I suppose this could be coded with shape abstraction as:

    public static MethodHandle addKernel(Shape shape) {
        return Builder.builder(Float.class,shape)
           .bind(Float.class,shape,Float.class,shape, (a, b, builder) ->builder.return_(a.add(b)))
           .build(TestOps.instance); //Instantiate with a methodhandle map
    }

(…so somebody other than the end user could select the shape or shapes to use.)

That abstraction could in turn could be handled via a lambda:

some.vector.api( s -> my(mh, expression, forMyKernel) );
some.vector.api( My::addKernel );

> 
> 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);

This is where LVTI (local variable type inference) will quickly add value:

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) -> {
         var r = arr.get(i);
         var res = left.add(right.mul(r));
         return b.return_(res);
       })
   ).build(TestOps.instance);

With liftable lambdas that might turn into something vaguely like:

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.bindLiftFloatIndexable(Shapes.L8,
       (left, right, arr) -> {  //?? (float left, float right, float[] arr)
         var r = arr[i];
         var res = left + right * r;
         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.

With shape abstraction we can code post-loop and pre-loop code to handle stuff like that.

I think that maskability is logically part of a vector's shape, in which case ISAs with masking
can handle loop cleanups with masked versions of ops, while the main loop is non-masking.

For non-masking ISAs with intermediate sized vectors, the cleanup code can use the lgN
pattern which decays the vector size by powers of two.  Or it can just do a size N-1 loop.
All the cleanup code can be hidden away from the user, if the user wishes to trust the
library's loop shaper to handle those details.

> 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.

Using lifted lambdas the user would probably be able to say something like:


   public static final MethodHandle mask1 = Builder.builder(Float.class,Shapes.L8)
     .bindLift(Float.class,Shapes.L8,Float.class,Shapes.L8, (left,right) -> {
       var masked = left == right ? left + right : left * right;
       return masked;
   }).build(TestOps.instance);

(Suggest renaming "mask" as "if_" or "choose", since in lanewise terms it's just "x?y:z".
Seems to me that the EL ignores the lane context when it can, right?  With scalars
you choose, not mask.)

> 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.

Here's a dumb question:  How do I activate Expressions/pom.xml?
Do I point IntelliJ at it somehow?  Or what's the shell command to
get Maven to notice it?  Better yet, just point me that the Maven
cheat sheet which tells how to run a pom, if you know a better one
than this:

https://maven.apache.org/guides/getting-started/maven-in-five-minutes.html

— John