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

I think the problem is still the halting problem. You only have the text of
the program, and you need to decide not only that quit=true exists, but
that it is reachable from the loop body.

There are trivial cases where you can do this, but the world is full of
nontrivial things. Say, createRandom...NP sets quit=true. Now what? Say, a
subclass overrides createRandom...NP. Now what? Say, you call someone that
has reference to this, and calls createRandom...NP. Now what? Is it the
same instance or not?

Etc, etc, etc

The bottom line is: often there is no simple answer to a complex problem,
and infinitely often there is no answer.

Alex


On Thu, 22 Jul 2021, 13:46 Nathan Reynolds via Concurrency-interest, <
[email protected]> wrote:

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

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