Specifying an arbitrary function and then using it in TLC

[Vic Putz]

In https://groups.google.com/u/1/g/tlaplus/c/jnlmYhh4jmo/m/HTGFDZimCAAJ, when asked about a generic hash function in TLA, Ron Pressler wrote:

> Unless what you're specifying is at the level of the hash function itself, you might be 

> thinking about this at too-low a level. If the algorithm you're specifying should work with 

> any hash function, make that a part of your specification: ∃ hash ∈ [Source → Bits].... If 

> there are other requirements on the hash, add them to the quantifier. 

Which is a lovely high-level way to specify that such a function exists.  I'm facing something similar in a toy spec I'm trying to write for a transpiler, where I can say there exists such a function mapping instructions on architecture A to those on Architecture B, something like ∃ TranslateFn ∈ [INSTRUCTIONS_A → INSTRUCTIONS_B].  Good so far.

I'd like to use that function in a TLC model, but just using the existential quantifier doesn't expose TranslateFn.  So the next thing that looks right is TranslateFn == CHOOSE f  ∈ [INSTRUCTIONS_A → INSTRUCTIONS_B] : TRUE , because I don't care what that function is, just that there is one and that I can use it.

But won't that ask TLC to (senselessly?) explore the whole space of possible mapping functions?  If so, is there a way around that?

Cheers; still learning (slowly...)

[Stephan Merz]

CHOOSE is arbitrary but deterministic choice. In other words, with your definition, TLC will generate one function (likely a very trivial one, perhaps mapping every instruction of A to the same instruction of B) and explore the spec for that particular function. If you want to explore the spec for every possible function, make the mapping a variable of your spec, add

translateFn \in [...]

to the initial condition and UNCHANGED translateFn to all actions. And if you want to play with different hand-picked functions, add a CONSTANT TranslateFn to your module and write

ASSUME TranslateFn \in [...]

then you define the particular function in the model. What is the right way to go depends on whether you want to explore if your transpiler works for some fixed function, for all functions or for some specific ones.

Stephan

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/df467f71-77d1-4bed-a83c-d126d5da226fn%40googlegroups.com.

[Markus Kuppe]

On 25.11.20 10:31, Stephan Merz wrote:
> CHOOSE is arbitrary but deterministic choice. In other words, with your
> definition, TLC will generate one function (likely a very trivial one,
> perhaps mapping every instruction of A to the same instruction of B) and
> explore the spec for that particular function. If you want to explore
> the spec for every possible function, make the mapping a variable of
> your spec, add
>
> translateFn \in [...]
>
> to the initial condition and UNCHANGED translateFn to all actions. And
> if you want to play with different hand-picked functions, add a CONSTANT
> TranslateFn to your module and write
>
> ASSUME TranslateFn \in [...]
>
> then you define the particular function in the model. What is the right
> way to go depends on whether you want to explore if your transpiler
> works for some fixed function, for all functions or for some specific ones.

With the new-ish Randomization module [1,2], you could trick TLC to
check a more "interesting" subset of all functions.

Markus

[1]
https://github.com/tlaplus/tlaplus/blob/master/tlatools/org.lamport.tlatools/src/tla2sany/StandardModules/Randomization.tla
[2] https://lamport.azurewebsites.net/tla/inductive-invariant.pdf

[Vic Putz]

Aha!  Thanks, Stephan; I had noticed when I evaluated CHOOSE in TLC it seemed to come up with the same function every time, but I had thought that in a "proper" simulation it behaved like \in and represented a state branch over all possibilities.  I should be set with whatever it picks, though (this is a bit of a toy problem in the sense that this round I'm mostly using TLA+ for the exercise of writing things down rather than exploring the state space, but your point on ASSUME is interesting; I hadn't thought of it and I confess don't think of using ASSUME much).

Hadn't noticed the randomization module, Markus.  Thanks very much!

Vic