Hackeython: ADTs in JML

Drodt commented 5 months ago

Intended Change

Based on #3420. Changes the JML pareser to accept definitions of ADTs. Datatypes have a list of constructors separated by |, and a body of functions.

class Test {
    /*@ datatype List {
      @     Nil()
      @ | Cons(\any head, List tail);
      @
      @     int size() {
      @     return 0;
      @     }
      @ }
      @*/
}

Currently, ADTs can only be defined on class-level, not inside methods or outside of classes.

There also is no semantics for these ADTs. KeY simply ignores them. Ideally, we want to use the defined types and functions in specification and translate them to KeY ADTs.

We also want to use the new Java switch expressions to allow pattern matching on ADTs, i.e,:

switch (list) {
  case Nil -> 0;
  case Cons(_, xs) -> 1 + xs.size();
}

Open questions are:

How are JML ADTs translated to KeY?
How are switch expressions with pattern matching translated?
Can we define a shorthand infix notation for ADT function, e.g., l1 + l2 for l1.append(l2)?
How do we resolve ADT function calls in specification?
What happens if we already have a List class/interface?

OpenJML has a similar concept of ADTs and pattern matching. For demonstration, there is a list example.

Type of pull request

[ ] Bug fix (non-breaking change which fixes an issue)
[ ] Refactoring (behaviour should not change or only minimally change)
[x] New feature (non-breaking change which adds functionality)
[ ] Breaking change (fix or feature that would cause existing functionality to change)
[ ] There are changes to the (Java) code
[ ] There are changes to the taclet rule base
[ ] There are changes to the deployment/CI infrastructure (gradle, github, ...)
[x] Other: Changes to ANLTR grammars

Ensuring quality

[ ] I made sure that introduced/changed code is well documented (javadoc and inline comments).
[ ] I made sure that new/changed end-user features are well documented (https://github.com/KeYProject/key-docs).
[ ] I added new test case(s) for new functionality.
[ ] I have tested the feature as follows: ...
[ ] I have checked that runtime performance has not deteriorated.

Additional information and contact(s)

The contributions within this pull request are licensed under GPLv2 (only) for inclusion in KeY.

codecov[bot] commented 5 months ago

Codecov Report

Attention: 71 lines in your changes are missing coverage. Please review.

Comparison is base (1fb0c10) 37.77% compared to head (c6bc033) 37.75%.

Files	Patch %	Lines
...e/uka/ilkd/key/nparser/builder/TacletPBuilder.java	0.00%	56 Missing :warning:
.../key/nparser/builder/FunctionPredicateBuilder.java	0.00%	14 Missing :warning:
...a/ilkd/key/nparser/builder/DeclarationBuilder.java	0.00%	1 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #3427 +/- ## ============================================ - Coverage 37.77% 37.75% -0.03% + Complexity 17031 17030 -1 ============================================ Files 2076 2076 Lines 126950 127017 +67 Branches 21381 21388 +7 ============================================ - Hits 47952 47951 -1 - Misses 73092 73159 +67 - Partials 5906 5907 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

wadoon commented 5 months ago

One of the primary todos might be to prepare a proposal for JMLref.

KeYProject / key