Expression Language Prototyping

[John Rose]

Thank you!  Decoding lambda body bytecodes is the best we can do now,
and it might be good enough for prototyping work.

Are you aware of JINQ?  I think they do something similar.

There was a talk by Ming-Yee Iu about these techniques at JVMLS 2015.
One effect of his talk was to confirm my opinion that we need a better
intermediate representation (in the class-file) for such expressions.
Decoding from bytecodes seems very hacky and error-prone.  What's
your experience with this?

— John

On Jun 25, 2017, at 3:52 AM, Radosław Smogura <mail at rsmogura.net> wrote:
> 
> Dear all,
> 
> I’m not very sure if below could be interesting for you, it’s my old ‘play' focusing on translation Java to (no) SQL and CUDA kernels.
> 
> I try to capture lambda expression to get them as expression tree during runtime. I’m able to do it for simple lambdas like (o) -> (var == var) && ((varX == varX) && (someField + 1 == 1)), so later user can use (missing) API to examine tree.
> 
> Right now tree can be accessed with code like this:
> 
>  Method m = BasicMatadataTest.class.getDeclaredMethod("lambda$meta0");
>  Expression e = (Expression) m.invoke(null);
>  BinaryExpression top = (BinaryExpression) e;
>  BinaryExpression vars = (BinaryExpression) top.getLefthandExpression(); // represents (var == var)
>  (VariableExpression) vars.getLefthandExpression() // represents first var, and it’s reference equal to vars.getRighthandExpression() as it’s same variable
> 
> Above is a part from BasicMatadataTest.java.
> 
> My approach is to build expression tree during Attribution phase of JavaC - for each lambda the expression builder method is created during compilation which builds tree on demand (LambdaMetaExpr.java). Generated method uses ExpressionFactory installed in java.base to create a trees and to add abstraction layer between compiler and JDK. As there is no API right now, caller has to know method name and use reflection.
> 
> I stopped work at it year ago, and just do fast merge so it’s still in proof-of-concept phase.
> 
> Below please find links to JDK and langtools (both repos should be public). I think the best way for browsing would be to do diff to default branch
> - https://bitbucket.org/radoslaw_smogura/java-lambda-metaexpression-jdk9-langtools/branch/metaexpr
> - https://bitbucket.org/radoslaw_smogura/java-lambda-metaexpresions-jdk/commits/branch/metaexpr
> 
> Best regards,
> Radek
> 
>> On 23 Jun 2017, at 14:53, 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.  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
>