6 ms·
> Fundamentally no formalism will ever allow you to use more detail than the formalism has No, because TLA is not a programming language. It's a way to describ
by pron 9y ago
> Fundamentally no formalism will ever allow you to use more detail than the formalism has
No, because TLA is not a programming language. It's a way to describe computation using math. What you're saying is analogous to saying that there is no way math would allow us to describe physics at arbitrary levels of detail.
> adding those refinements will break symmetries that previously existed
The very definition of refinement is that this can't happen. Formally, if A refines B, then A => B. And so, every feature C of B, i.e., B => C, is also a feature of A, because A => C, due to the transitivity of implication.
> but I think you'd still encounter the same kind of problems if you wanted to model the machine state at a lower level of detail
No, because of universal computation. Once your logic can talk about a single computational step, and thanks to TLA's logical time that then allows you to break that step down further, you really can talk about arbitrary detail. Of course, while true, this is a theoretical possibility. No one is going to actually specify the program at the level of the electrons in the CPU. If someone does, they will encounter a difficulty that isn't about a theoretical limit of formalisms, but one specific to TLA, which is that the logic does not currently allow making probabilistic statements about programs.
> but there will always be finer details not captured in our model.
Sure, in our model -- yes. But not necessarily in our formalism.
> So what I don't see is why you would ever not want the higher-level tools, even if working in a lower-level formalism.
TLA is not a lower-level formalism, although it may sometimes be less convenient for some sequential computations. But because its denotation fully captures the notion of computation, it allows arbitrary levels of detail. Functions are a fundamentally lossy way of speaking about computations; sequences are not. Indeed, sometimes functions are very convenient, but they become not so convenient when concurrency/interaction is involved.
> A lot of the time we are analysing only in terms of denotation (sorted list) rather than operation (bubble sort or merge sort)
Again, you mean in terms of a functional denotation, i.e. the denotation of a function. The denotation of TLA is behavior (a sequence of steps), and while you can easily define an "extensional equivalence" operator on behaviors, one that looks only on the first step (input) and last step (output), the essential denotation in TLA does differentiate between bubble- and merge-sort.
> I'd still want to be able to talk about whether two procedures implemented the same function if the filesystem operated in a certain way.
That's very easy:
ExtensionallyEquivalent(A, B) ≜
∀ x : ∃ y : (A ∧ (input = x) ⇒ ◇□(output = y)) ≣ (B ∧ (input = x) ⇒ ◇□(output = y))
Which means that algorithms A and B are extensionally equivalence if for every input x, A terminates and produces the output y iff B does the same.
> I'd still want monads.
You wouldn't, because, as you've seen, while you can define a weaker equivalence on sequences, there is no need for a special construct to define different kinds of computation. The only reason monads are used in the first place is that functions cannot describe arbitrary non-sequential computation. Monads aren't a "real" feature of computation; they're a tool of a formalism used to describe computation.
It is very important to me to point out that TLA+ is not a programming language. Synchronous languages like Eve, however, do share many of its properties.
- lmm 9y ago> The very definition of refinement is that this can't happen. Formally, if A refines B, then A => B. And so, every feature C of B, i.e., B => C, is also a feature of A, because A => C, due to the transitivity of implication. Then these refinements evidently can't model distinctions that are sometimes important. > The denotation of TLA is behavior (a sequence of steps) Again, that's operation rather than denotation. Terminology isn't that important, but why not use the standard terms? > The only reason monads are used in the first place is that functions cannot describe arbitrary non-sequential computation. They're useful because they allow us to decompose a program into fragments that can be reasoned about separately. That's a useful capability when you want to reason about a computation that is inconvenient to model as a function, sure, but that's by no means the only reason. States really and truly are functions, Writers really and truly are plain values, there is no difficulty at all in describing those things in functional terms. But it's still convenient to use the monad constructs. > Monads aren't a "real" feature of computation; they're a tool of a formalism used to describe computation. They are a real feature: computation genuinely conforms to the monad laws, and so results about monads will be true about computation. We don't have to make use of these facts if we don't want to, but they remain true.
- pron 9y ago> Then these refinements evidently can't model distinctions that are sometimes important. I don't understand. A refinement is a description at a lower level of detail. It may be a little hard to imagine if you're not used to formalisms that allow for nondeterminism, but it works like this: the high level description, say, does not describe the precise state of the stack. In the TLA theory, this means that the state of the stack can be anything, and the formula describes an infinite set of behaviors for arbitrary states of the stack. A refinement that does describe the state of the stack would denote a subset of those behaviors. > Again, that's operation rather than denotation. Terminology isn't that important, but why not use the standard terms? Because that's just not true. The denotational semantics of the first-order logic statement over the natural numbers `x > 4 ∧ x < 8` is the set {5,6,7}. The operational semantics of, say `⊦ x > 2 ⇒ x > 1` in Peano arithmetic is the proof of that theorem. In lambda calculus, the denotational semantics of `λ x . x + 1` is the function `f(x) = x + 1`. Its operational semantics is the sequence of reductions. Your denotation and operation are dependent on the formalism, not on what it describes. The denotation of a TLA formula is, like all first-order logics, a set (actually, a class) of models that satisfy it, which, in the case of TLA is a set of infinite sequences with some equality relation over them. The operational semantics of TLA are more similar to that of formal logic, and are basically proofs. Operation and denotation are formalism-dependent. > They're useful because they allow us to decompose a program into fragments that can be reasoned about separately. ... with functions! If your primitive building block isn't functions but sequences, then your compositions are different, your reasoning is different, your denotation is different, and you don't need monads. > States really and truly are functions, Writers really and truly are plain values, there is no difficulty at all in describing those things in functional terms. Computation is an abstraction of some physical process. I don't know what it means for a physical process to be "really and truly a function". Mathematics are a description of that process. You can describe the same process using different mathematical means. So maybe state is really and truly a function, but it's also really and truly a sequence. It then becomes an aesthetic and pragmatic question as to which you would choose. > They are a real feature: computation genuinely conforms to the monad laws, and so results about monads will be true about computation. We don't have to make use of these facts if we don't want to, but they remain true. See my paragraph above. These monad laws are true once you describe computation using functions and monads. I don't know what it means for them to be "really" true. It's really a philosophical question. In any event, once you describe computation as sequences rather than functions, monads are unnecessary. I guess the most accurate thing to say is that if one describes computation with functions, then the monad laws necessarily hold etc. This, BTW, is one of the things Lamport always like pointing out when explaining what math is, and he always warns about confusing language, or a description, with reality. The main thing I'm trying to do in this discussion is not to claim that another approach is universally "better" than FP, but just to dispel the false notion that the functional approach is the "right", "mathematical" way of describing computation. It is one mathematical approach, with its pros and cons, and there are others (classical imperative, process calculi, TLA etc.), with their respective pros and cons. None can be said to be universally better than the others. They can be more or less convenient depending on what it is that you want to do and your personal aesthetic preferences.