6 ms·
> It sounds like that's only achieved by weakening the formalism so far that its guarantees are no stronger than what you have when using the "escape hatch" in
by pron 9y ago
> It sounds like that's only achieved by weakening the formalism so far that its guarantees are no stronger than what you have when using the "escape hatch" in the functional world.
This is where the aesthetics and pragmatics come into play. In terms of program analysis, the language doesn't really matter (there are actual theorems that prove that no language structure can be exploited to make proving things easier), so in a sense you are right (but this also means that proving general propositions about Haskell is no easier than proving them about assembly code -- which is, unfortunately, true). However, there are questions of convenience. Just as Haskell is easier to analyze than C for sequential code, those other formalisms are easier to analyze and work with than Haskell for interactive and/or concurrent programs.
> I don't think that contradicts what I said at all. Certainly when analysing these programs we would want to be able to talk about whether they are equivalent, and we would want to consider them as equivalent in certain senses and as inequivalent in other senses. A formalism that can't accommodate that would be less useful (other things being equal) than one that can.
If you read part 4 of my post series on TLA+[1], you'll see that a formalism like TLA allows you to rigorously, mathematically and formally define the "sense" of equivalence that you're interested in. This is not quite possible in functional formalisms. The reason is as follows: computations simply cannot be fully described by functions (unless you describe them essentially as state machines using a monad). Bubble-sort and mergesort compute the same function, but they use different computation. A formalism that allows you to describe arbitrary computations precisely can then allow you to pick your "level of detail". TLA places all computations in a nice Boolean algebra, where all algorithms are neatly organized in a Boolean lattice. You can then define (in two lines) a operator, `ExtensionallyEquivalent(_, _)`, that captures the functional equivalence, but also define other forms of equivalence, down to the most detailed ones. It is completely flexible in the forms of equivalence it can describe.
Nevertheless, you won't hear me say that TLA is "better" than functional formalisms, because that extreme flexibility comes at a cost. Simple sequential compositions are more cumbersome in TLA, and since most of the time, when writing sequential programs like compilers, we're not interested in reasoning about interaction or concurrency, functional programming is more convenient. It was mostly designed to write compilers and similarly sequential programs, and I think it is hard to beat in that domain. Because of that it also excels at symbol manipulation (e.g., it is so convenient to define expression types using algebraic data types) -- that is what it was invented for.
[1]: https://pron.github.io/posts/tlaplus_part4 https://pron.github.io/posts/tlaplus_part4 it probably requires reading at least part 3 first.
- lmm 9y ago> you'll see that a formalism like TLA allows you to rigorously, mathematically and formally define the "sense" of equivalence that you're interested in. This is not quite possible in functional formalisms. The reason is as follows: computations simply cannot be fully described by functions (unless you describe them essentially as state machines using a monad). Bubble-sort and mergesort compute the same function, but they use different computation. A formalism that allows you to describe arbitrary computations precisely can then allow you to pick your "level of detail". Yes and no. Fundamentally no formalism will ever allow you to use more detail than the formalism has; even if the formalism lets you refine existing descriptions, adding those refinements will break symmetries that previously existed, so there's no way to get away from having to redo your analysis. TLA sets that baseline level of detail at a lower level (or equivalently is more precise), 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 (e.g. as an extreme example, if you wanted to analyse vulnerability to rowhammer-like issues). We can choose a more or less detailed model, trading off how much detail we can talk about versus how complex our description space is and how many or few symmetries we have, but there will always be finer details not captured in our model. > If you read part 4 of my post series on TLA+[1], you'll see that a formalism like TLA allows you to rigorously, mathematically and formally define the "sense" of equivalence that you're interested in. This is not quite possible in functional formalisms. The reason is as follows: computations simply cannot be fully described by functions (unless you describe them essentially as state machines using a monad). Bubble-sort and mergesort compute the same function, but they use different computation. A formalism that allows you to describe arbitrary computations precisely can then allow you to pick your "level of detail". TLA places all computations in a nice Boolean algebra, where all algorithms are neatly organized in a Boolean lattice. You can then define (in two lines) a operator, `ExtensionallyEquivalent(_, _)`, that captures the functional equivalence, but also define other forms of equivalence, down to the most detailed ones. It is completely flexible in the forms of equivalence it can describe. 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. A lot of the time we are analysing only in terms of denotation (sorted list) rather than operation (bubble sort or merge sort); I'd certainly expect to be able to recover that kind of equivalence as you say, and it's good that the formalism makes it easy. But in that case then surely, even if I were working in something like TLA, 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. I'd still want to cheaply compare functions for equivalence "up to" fiddlier aspects that I could separately analyse in more detail. I'd still want monads.