Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Introduce support for recursive functions #84

Closed
Kukovec opened this issue Dec 12, 2019 · 4 comments
Closed

Introduce support for recursive functions #84

Kukovec opened this issue Dec 12, 2019 · 4 comments
Assignees
Labels
help wanted new New issue to be triaged.
Milestone

Comments

@Kukovec
Copy link
Collaborator

Kukovec commented Dec 12, 2019

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

@Kukovec Kukovec added the new New issue to be triaged. label Dec 12, 2019
@konnov konnov added this to the BMCMT-0.9-release-ux milestone Dec 12, 2019
@konnov
Copy link
Collaborator

konnov commented Dec 12, 2019

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

@konnov konnov removed this from the v1.0-release-ux milestone Apr 7, 2020
@konnov
Copy link
Collaborator

konnov commented Apr 7, 2020

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

  • We have to know the function co-domain, in order to define the function first and then constrain it with the function definition. Essentially, a function definition f[x \in S] == body becomes CHOOSE f \in S -> T: \A x \in S: body.
  • Another problem is that it is way too easy to define a recursive function of an infinite domain, e.g., Fact[n \in Int] == (* factorial *). Although this function would terminate on every argument, it would require a quantified encoding.

@konnov
Copy link
Collaborator

konnov commented Apr 12, 2020

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
Copy link
Collaborator

konnov commented Apr 17, 2020

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

@konnov konnov closed this as completed Apr 17, 2020
@konnov konnov added this to the backlog2020 milestone Dec 11, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted new New issue to be triaged.
Projects
None yet
Development

No branches or pull requests

2 participants