tlaplus / tlaplus/CommunityModules
More efficient evaluation of SequencesExt!BoundedSeq when e.g. checking refinement
Nobody has claimed this yet.
- Dominant language
- TLA
- Stars
- 315
- Forks
- 48
- Avg merge
- 13h 27m
- Merged PRs (30d)
- 2
Description
The module Foo models a system where -at every step- the log is extended by a subsequence of up to length C from the set S. It is straightforward to see that the module Bar refines Foo. However, TLC fails to verify the refinement because it cannot enumerate the set of all subsequences SeqOf(S, 42).
----- MODULE Foo ------
EXTENDS Naturals, Sequences, SequencesExt
CONSTANT S, C
VARIABLE log
Init ==
log = <<>>
Next ==
\E suffix \in SeqOf(S, C) :
log' = log \o suffix
NextRefine ==
/\ log' \in Seq(S)
/\ IsPrefix(log, log')
/\ Len(log') <= Len(log) + C
Spec == Init /\ [][Next]_log
=====
----- MODULE Bar -----
EXTENDS Sequences
VARIABLE log
Spec == log = <<>> /\ [][log' = log \o <<"a">>]_log
Foo == INSTANCE Foo WITH C <- 42, S <- {"a"}
THEOREM Spec => Foo!Spec
\* .cfg files do not accept the ! in Foo!NextRefine
FooNextRefine == Foo!NextRefine
=====
Clearly, when verifying refinement, it's conceptually unnecessary for TLC to enumerate SeqOf(S, 42). Instead, it would be sufficient to check something like NextRefine, which TLC will check if we redefine Next with NextRefine:
CONSTANT Next <- [Foo]FooNextRefine
However, SeqOf could be enhanced to symbolically check ... \in SeqOf(S, C), similar to how TLC checks Seq(S):
Additionally, this new tlc2.value.impl.Value implementation should properly implement tlc2.value.impl.Enumerable#elements to lazily enumerate the elements of SeqOf when evaluating the existential quantification\E s \in SeqOf(S,C): log' = ....
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with tlc2/module/Sequences.java around the linked Seq(S) membership implementation, then inspect tlc2.value.impl.Value and Enumerable#elements. Implement symbolic membership for SeqOf(S,C) without enumerating all sequences, while preserving lazy element enumeration for existential quantification over SeqOf; verify the refinement example no longer requires exhaustive enumeration.
Written by the indexing model from the issue text.
Assessment
- Domain
- devtools
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100