apalache-mc / apalache

APALACHE: symbolic model checker for TLA+ and Quint
https://apalache-mc.org/
Apache License 2.0
440 stars 40 forks source link

Introduce support for recursive functions #84

Closed Kukovec closed 4 years ago

Kukovec commented 4 years ago

Currently, a at.forsyte.apalache.tla.lir.UnexpectedLanguageError is thrown if a recursive function is used. See #83 for an example specification.

konnov commented 4 years ago

It should be easy to do, as recursive functions -- in contrast to recursive operators -- do not require fixpoint computation.

konnov commented 4 years ago

Recursive functions seem to be harder to encode than we expected. There are a few problems to think about:

konnov commented 4 years ago

To handle recursive functions differently from recursive operators, we have changed the intermediate representation of recursive functions. From now on, a recursive function is defined with a nullary operator whose body consists of the application of the operator TlaFunOper.recFunDef. The arguments of recFunDef are similar to those of a normal function constructor funDef, that is, the constructor for [x \in S |-> e]. The only difference is that the recursive function definition may refer to the function by applying the operator TlaFunOper.recFunRef.

Details to be added in #125.

konnov commented 4 years ago

We have added limited support for recursive functions, see the manual.