Type inference heuristics (was: Enhancing expressions with mutability?)

[B. Blaser]

A common use of mutable expressions is for implementing evolutionary
heuristics which typically might be helpful to solve performance
issues like JDK-8152289. So, I tried to write such an algorithm using
the quotation operator ` to infer the following similar example:

class Point<P extends Number> {
    Point(P label) {}
}

class Graph<G extends Number> {
    public Graph(Point<G>... vertices) {}
}

class Test {
    Test() {
        new Graph<>( new Point<>(1), ..., new Point<>(200) );
    }
}

The attached dedicated evolutionary heuristic [3] infers all variables
in no more than one second whereas javac takes currently between one
and two minutes on my machine. It assumes the following initial bound
set:

G  <: Number
   =  P1 ... Pn

Pn <: Number
   :> Integer
   =  G

The set of potential solutions is deduced from the initial bound set
including combinations of them (intersection types):

+    private final Class<?>[] classes = new Class<?>[] {
+        Integer.class, Number.class, Object.class
+    };
+
+    private final Class<?>[] interfs = new Class<?>[] {
+        Serializable.class, Comparable.class,
+        Constable.class, ConstantDesc.class
+    };

The evolutionary algorithm traditionally starts with creating
individuals and then iteratively chooses the best ones to perform
cross-over and mutations until the prefect one is found. The
interesting part is, of course, how their ADN is encoded. Each gene is
dedicated to one inference variable and represents the individual
ability to solve it, which can be expressed by the following formula:

+            adn[i] = (`able).link(`p, `type());

where `able is a function that checks all the bounds of the inference
variable `p against the potential instantiation `type().

The evaluation of an individual, which is also the function to
minimize, is the sum of all bad genes not able to solve their
inference variable, the perfect individual having only good genes.

However, this heuristic is only designed to infer this particular
example. So, it might be interesting to generalize it as much as
possible to solve a wider range of performance issues in this area.

What do you think?

Thanks,
Bernard

[3] heuristic.patch (attached)

On Thu, 12 Mar 2020 at 18:36, B. Blaser <bsrbnd at gmail.com> wrote:
>
> To go a bit further, it'd be also possible to add another field to the
> 'Term' class representing the name of any quoted identifier, which can
> concretely be made in 'Lower' by adding a couple of lines like
> 'makeLit(syms.stringType, ((JCIdent _or_
> JCFieldAccess)arg).name.toString())' (I can share the full diff with
> the previous 'quote.patch' if requested). We can then use it like '(`d
> _or_ `this.d).name.equals("d")' in our initial example.
>
> So, not to misunderstand me, this isn't a meta-programming facility by
> itself but a fortunate consequence of the quotation operator which
> might be used to considerably reduce the amount of code in certain
> situations like persistence frameworks. And note also that mutable
> expressions might be used to build queries using a more declarative
> fashion, for example.
>
> Isn't that still a direction which is worth exploring?
>
> Thanks,
> Bernard
>
> On Tue, 10 Mar 2020 at 22:03, B. Blaser <bsrbnd at gmail.com> wrote:
> >
> > Hi,
> >
> > Taking back the essential idea of the original publication on Lisp
> > [1], I did the attached syntactic experiment [2] trying to bring some
> > kind of mutability to expressions and thus giving more flexibility to
> > the language. I hope this subject hasn't been covered too many times,
> > otherwise I'd apologize for any disturbance.
> >
> > To build such mutable expressions, I've specified a new unary operator
> > ` along with its resulting class 'java.lang.Term'. The quotation
> > operator creates a 'Term' from any reference which can then be linked
> > to other terms to finally be evaluated to the result of a function
> > call for lambdas or the reference itself otherwise.
> >
> > Let's take some examples from the attached patch:
> >
> > +    interface Get {
> > +        int op();
> > +    }
> > +
> > +    interface Sum {
> > +        int op(int i, int j);
> > +    }
> >
> > +    int a = 0, b = 0;
> > +    Sum s = (x, y) -> x + y;
> >
> > +    public void run() {
> > +        Get a = () -> this.a;
> > +        Get b = () -> this.b;
> > +
> > +        Term e1 = (`s).link(`a, `b);
> > +        this.a = 1; this.b = 2;
> >
> > The above lines create a mutable expression e1 from the sum lambda s
> > of the getter a and b which can then be evaluated to:
> >
> >     (Integer)e1.value() == 3
> >
> > or visualized as:
> >
> >     e1.toString().equals("Sum( Get( ) Get( ) )")
> >
> > An interesting application similar to §3.g from [1] is the computation
> > of the partial derivative of a sum involving the mutation of the
> > initial expression to produce a new resulting one:
> >
> > +    // Derivative of sum e with respect to r
> > +    Term derivative(Term e, Term r) {
> > +        if (e.terms.isEmpty()) {
> > +            return `Integer.valueOf(e.that == r.that ? 1 : 0);
> > +        }
> > +        else if(e.that == (`s).that) {
> > +            return (`s).link(derivative(e.terms.get(0), r),
> > derivative(e.terms.get(1), r));
> > +        }
> > +        else throw new AssertionError();
> > +    }
> >
> > Invoking the above method like this:
> >
> > +        Term e2 = derivative(e1, `a);
> >
> > creates the resulting derivative expression e2 which can then be evaluated to:
> >
> >     (Integer)e2.value() == 1
> >
> > or visualized as:
> >
> >     e2.toString().equals("Sum( `1 `0 )")
> >
> > Finally, we note that any term may be quoted to prevent its
> > evaluation, for example:
> >
> > +    Derivative d = this::derivative;
> >
> > +        Term e3 = (`d).link(`e1, ``a);
> >
> > can be evaluated to:
> >
> >     (Integer)((Term)e3.value()).value() == 1
> >
> > or visualized as:
> >
> >     e3.toString().equals("Derivative( `Sum( Get( ) Get( ) ) `Get( ) )")
> >
> > Of course, one of our main concern is how much do we need this and a
> > reasonable answer would probably be as much as we need Lisp's
> > S-expressions but with similar or maybe better performance than
> > external interpreters and a more homogeneous integration to the
> > language.
> >
> > Any feedback about this experiment would be welcome!
> >
> > Thanks,
> > Bernard
> >
> > [1] http://www-formal.stanford.edu/jmc/recursive.html
> > [2] quote.patch
-------------- next part --------------
A non-text attachment was scrubbed...
Name: heuristic.patch
Type: text/x-patch
Size: 6452 bytes
Desc: not available
URL: <https://mail.openjdk.java.net/pipermail/discuss/attachments/20200320/9390e68a/heuristic.patch>