Re: Are there real use cases with the Java access modes?

It is not quite the halting problem.  The halting problem asks if the
computation ends.  The PMD rule asks if among the many branches inside the
loop's call tree if the exit variable is set.  It does not care if the
branch is never taken.

Consider this code...

private boolean quit;

while (!quit)
{
   createRandomAlgorithmInPforNP();

   if (doesAlgorithmWork())
   {
      quit = true;
   }
}

The method createRandomAlgorithmInPforNP() creates a random algorithm that
runs in polynomial time and hopefully solves a NP problem.  The method
doesAlgorithmWork() tests the created algorithm to see if it works.  This
is an example of a halting problem.  We don't 100% know if an algorithm
will ever be found and hence if the loop will run forever.

But, this does not matter for the PMD rule.  The PMD rule only cares that
there is a "quit = true" in the loop body (or in the call tree).  Why?  The
PMD rule is looking to see if "while (!quit)" can be hoisted out of the
loop thus creating an infinite loop.  It will execute the same logic that
JIT does to determine if "while (!quit)" can be hoisted.  We have working
code (i.e. JIT) that we can use to implement the PMD rule.

On Thu, Jul 22, 2021 at 2:35 AM Andrew Haley via Concurrency-interest <
[email protected]> wrote:

> On 7/21/21 4:50 PM, Nathan Reynolds via Concurrency-interest wrote:
>
> > Sounds like a job for a linter.  For easier cases, an easy PMD rule
> > will catch such a problem.  For harder cases, the PMD rule will need
> > to traverse the call tree to see if a thread executing the loop
> > could change the field.  If not, flag a problem to the programmer.
>
> I suspect that getting this right (no false positives or negatives) is
> equivalent to the halting problem, i.e. it's uncomputable. The best
> you can say is that if an expression used as the exit condition of a
> loop has a term hoisted from memory, the loop might not terminate.
>
> However, while linting for that provides some information to the naive
> programmer, it "solves" the problem of infinite loops but ignores
> silently returning false results.
>
> --
> Andrew Haley  (he/him)
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> https://keybase.io/andrewhaley
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>
> _______________________________________________
> Concurrency-interest mailing list
> [email protected]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[email protected]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest