Effects system

[Jesper Nordenberg]

An effects system for Java could be implemented using annotations. For
example, one might tag a method with @LocalState if it reads/writes to
variables accessible from method parameters, @GlobalState if it reads/
writes to static variables or calls non-Java methods (IO).
Alternatively one can do the opposite and tag pure methods with @Pure,
@SemiPure etc. The side effects should be propagated through the call
chain, so a pure method can only call other pure methods etc.

Is this possible to implement in JSR-305, and if so how would it be
done?

[Aaron Greenhouse]

Yes, this is doable. Before I say more, let me state that part of my
dissertation describes an effects system for Java-like languages.
There is probably some value in having some coarse-grained
descriptions of effects: No effects, reads/writes local fields only,
reads/writes global state. Dealing with the in between becomes more
problematic. What do we say about method B.m() below?

class A {
private int x;

public void setX(int v) { x = v; }
}

class B {
private A f;

public void m() { f.setX(10); }
}

Method A.setX() only touches a field of primitive type. We could
annotate it is @WritesLocal, for example.

Method B.m() is more complicated. Yes, it reads a local field 'f'.
But it also writes the local state of an A object. But which one?
Well, the one referenced by 'f'. But that reference can change over
time.

There are also issues with preserving abstraction and data hiding.
There are solutions to these issues---we have one such solution in the
JSure tool, and there are other proposals from other researchers---but
they definitely complicate the annotations.

I think the question that needs to be answered before pursuing this
topic any further is what are the specific problems we want to solve
through the use of effects annotations. The answer to this will
influence at what granularity state needs to be identified in the
effects system.

--Aaron

[Jesper Nordenberg]

On Jul 1, 7:32 pm, Aaron Greenhouse <aar...@cs.cmu.edu> wrote:
> Yes, this is doable. Before I say more, let me state that part of my
> dissertation describes an effects system for Java-like languages.

Interesting. Is there something published on the net?

> I think the question that needs to be answered before pursuing this
> topic any further is what are the specific problems we want to solve
> through the use of effects annotations. The answer to this will
> influence at what granularity state needs to be identified in the
> effects system.

Yes. I think the most important areas where an effects system would be
helpful is in testing/verification and parallelization, where these
categories of effectfulness would be helpful:

- Pure functions/methods with no side effects. If you know a function/
method is pure it's easily verifiable and parallelizable. Note that a
pure function should be allowed to use state, as long as it's
contained in local variables/objects (for example, a sum function that
uses a local accumulator variable should be allowed to be marked as
pure).

- Functions/methods which reads/writes variables accessible from
parameters only (including the implicit "this" parameter). Both class
A.setX and B.m in your example would fall into this category. As long
as you call these functions with the same parameters you will always
get the same result, which makes them quite easily testable and
parallelizable.

- Functions/methods that reads/writes static variables and/or calls
native methods (like file system calls). These functions/methods are
inherently hard to test/parallelize.

There might be some use in subdividing these further, for example in
read/write categories.

[Aaron Greenhouse]

On Jul 2, 6:44 am, Jesper Nordenberg <megagu...@gmail.com> wrote:
> On Jul 1, 7:32 pm, Aaron Greenhouse <aar...@cs.cmu.edu> wrote:
>
> > Yes, this is doable.  Before I say more, let me state that part of my
> > dissertation describes an effects system for Java-like languages.
>
> Interesting. Is there something published on the net?

Search <http://www.fluid.cs.cmu.edu:8080/Fluid/annotation-
handout.html> for the section on Method Effects. This web page is out
of date, so the syntax is not current, but you should get the general
idea.

<http://www.fluid.cs.cmu.edu:8080/Fluid/fluid-publications> has a lot
of research publications on the topic of concurrency analysis, unique
pointer analysis, effect analysis, and program transformation.

> Yes. I think the most important areas where an effects system would be
> helpful is in testing/verification and parallelization, where these
> categories of effectfulness would be helpful:
>
> - Pure functions/methods with no side effects. If you know a function/
> method is pure it's easily verifiable and parallelizable. Note that a
> pure function should be allowed to use state, as long as it's
> contained in local variables/objects (for example, a sum function that
> uses a local accumulator variable should be allowed to be marked as
> pure).

Yes, this is very easy to verify with a static analysis. And I agree,
it does have a number of useful applications.

> - Functions/methods which reads/writes variables accessible from
> parameters only (including the implicit "this" parameter). Both class
> A.setX and B.m in your example would fall into this category. As long
> as you call these functions with the same parameters you will always
> get the same result, which makes them quite easily testable and
> parallelizable.

I'm not sure I agree with this. When the parameters are primitive,
this is certainly true. But for object parameters, it requires that
the parameters be equal (in the sense of Object.equals()). How often
does this occur? Is there a particular application domain you are
thinking of?

The aliasing problem that I wrote of earlier makes it difficult to
limit the effects to parameters in cases when the object used as an
argument references other objects. Containing these effects requires
using some kind of uniqueness/ownership/containment/universe
annotation and analysis, and these are still more complicated and
generally have far-reaching consequences for the annotated code. (See
the @Unique annotation in the above link.)

> - Functions/methods that reads/writes static variables and/or calls
> native methods (like file system calls). These functions/methods are
> inherently hard to test/parallelize.

Some kind of category of global effect could be useful.

> There might be some use in subdividing these further, for example in
> read/write categories.

Adding read/write categories is trivial.


My concerns about adding effects, I think, can be boiled down to this:
It is easy to come up with annotations that concisely express the
extremes: no effects (pure), could write any object. It is also easy
to make some course generalizations: does/does not affect global
(static) state. The in between case of trying to specify which
objects are affected, and possibly which portion of an object is
affected, is much more difficult. In particular, I think that trying
to solve this problem is going to tie the annotations to particular
analysis. That is, it is not going to be approachable by many
different analysis styles. For example, the object-oriented effects
system developed by Dave Clarke and Sophia Drossopoulou <http://
homepages.cwi.nl/~dave/writing/papers/oedte.ps.gz> is quite different
from the one that John Boyland and I came up with.

--Aaron

[Jesper Nordenberg]

Thanks for the links.

On Jul 8, 3:44 pm, Aaron Greenhouse <aar...@cs.cmu.edu> wrote:
> On Jul 2, 6:44 am, Jesper Nordenberg <megagu...@gmail.com> wrote:
> > - Functions/methods which reads/writes variables accessible from
> > parameters only (including the implicit "this" parameter). Both class
> > A.setX and B.m in your example would fall into this category. As long
> > as you call these functions with the same parameters you will always
> > get the same result, which makes them quite easily testable and
> > parallelizable.
>
> I'm not sure I agree with this. When the parameters are primitive,
> this is certainly true. But for object parameters, it requires that
> the parameters be equal (in the sense of Object.equals()). How often
> does this occur? Is there a particular application domain you are
> thinking of?

The usability is mainly for (unit) testing and for "purifying"
methods. Consider this example:

bool runTest() {
MyClass c = new MyClass();
MyClass2 c2 = new MyClass2();
c.methodA(c2, 10);
c.methodB(c2, 23);
return c.getZ() == c2.getX();
}

If all methods (including class constructors) called in runTests() are
tagged with the category "only accesses variables reachable from
parameters", it's easy to infer that runTests() is a pure function
even though it calls non-pure methods. The stateful method calls are
totally encapsulated and are not exposed outside runTest(). Obviously
this would not be possible if a method called non-Java methods or
accessed static variables. This is similar, I believe, to the state
monad in Haskell.

> My concerns about adding effects, I think, can be boiled down to this:
> It is easy to come up with annotations that concisely express the
> extremes: no effects (pure), could write any object. It is also easy
> to make some course generalizations: does/does not affect global
> (static) state. The in between case of trying to specify which
> objects are affected, and possibly which portion of an object is
> affected, is much more difficult.

I think it would be very valuable to just have an effects system of
the same granularity as the one in Haskell (basically IO and state
monads). Something more advanced might be useful as well, but
Haskellers seems quite content with what they have.

[Bill Pugh]

Although I think this is an interesting topic to work on, my feeling
it is too much of a research problem for current consideration in
JSR-305.

I'm willing to hear from others who think otherwise.

Bill