5 ms·
> By that definition then you could call any operational semantics "denotational" and the distinction between the two would be pointless. While there is some d
by pron 9y ago
> By that definition then you could call any operational semantics "denotational" and the distinction between the two would be pointless.
While there is some debate over what exactly can be called "denotational semantics", it is widely accepted that denotational semantics must display certain characteristics. Hoare logic does display those characteristics and is, AFAIK, considered denotational.
> in a well-factored functional-style program you can move the vast majority of program code/logic into those "least tricky parts", and have a machine-enforced separation between the two. So you can restrict the more expensive forms of analysis to a small subset of your code, and get a much better cost/benefit.
1. I know, but I don't find that approach appealing in the least.
2. Other approaches have the language and its theory cleanly deal with effects -- just as with computation -- and so don't require such a separation and actually help with the tricky effectful/concurrent bits because they were designed for that purpose. FP was designed for a different purpose.
> If you deliberately choose to use operations that are deliberately defined to not have a formal denotation then your code won't have a formal denotation.
But that is a feature of the functional formalism, not of all formalisms. All of these programs have the same hoare-logic denotation (in classical imperative languages), and the same behavioral denotation (say in TLA). A denotation is not a feature of an algorithm; it's a feature of the particular formalism used to express the algorithm (although some formalisms may possibly have more than one reasonable denotational semantics).
> IO is explicitly an "escape hatch" to be used as a last resort.
Yes, in the functional formalism. Not in every language. I wanted to show a particular property of functional languages that I find unappealing.
> E.g. if your model of IO follows our common-sense informal semantics (where we e.g. pretend concurrent access to the same file wouldn't happen - this is a choice you have to make when modelling, because in some contexts the ability of another process to interfere with fac.txt would be an important difference between fac1 and fac5 and we wouldn't actually want them to be equivalent)
Ah, but that's why I've specifically chosen this example. Other formalisms have no difficulty assigning simple and natural semantics in either case (and if we disallow concurrent writes but allow concurrent reads, all versions of the algorithm would have isomorphic denotations). The reason you run into any sort of difficulty here is because your chosen denotation is that of a function, and functions are not a good representation of interactive or concurrent processes. Other denotations used in other formalisms have no problem with that.
> So terminology aside, what's the problem?
There's no problem. I just want to point out why pure FP is not so well-designed for all circumstances, as, for example, its denotation is a bad fit in many circumstances. If you personally do find the aesthetics of FP appealing, and have no problem separating effects from computation, enjoying the benefits of pure FP for the pure computational part -- good for you! I was just trying to show why it is not a universally "better" formalism, and why there may be very good pragmatic and aesthetic reasons not to choose it.
- lmm 9y ago> But that is a feature of the functional formalism, not of all formalisms. > Yes, in the functional formalism. Not in every language. I wanted to show a particular property of functional languages that I find unappealing. I would expect any practical formalism to have escape hatches, just as I expect any practical type system to allow casting - and I find it absurd to see either as a downside for the language. > Other formalisms have no difficulty assigning simple and natural semantics in either case (and if we disallow concurrent writes but allow concurrent reads, all versions of the algorithm would have isomorphic denotations). If another program overwrites fac.txt then the semantics you gave in your ghost variables and assertions example would be simple, natural, and wrong (and wrong in a way that's a common source of security vulnerabilities). If your formalism makes fac1 and fac5 equivalent, as you've said it does, then there's no way to then make them un-equivalent. Really they're equivalent for the purposes of some kinds of analysis under certain constraints and they're not equivalent for other purposes. The functional formalism handles this essentially as well as possible: it allows you to do any analysis that doesn't depend on how you're modelling the filesystem interactions "ahead of time", but forces you to make an explicit choice of model when your analysis is fundamentally dependent on that model.
- pron 9y ago> I would expect any practical formalism to have escape hatches, just as I expect any practical type system to allow casting - and I find it absurd to see either as a downside for the language. Sure, but not every formalism needs the escape hatch to do IO. I don't see it as a downside. FP is beautifully adapted to sequential programs, perhaps more so than other formalisms. It's not the best fit for interactive/concurrent. Also, an unappealing property to one may not be a problem at all to another. You may not be bothered by this, but I am, and that's OK. I like Java, and I assume you like it less, and that's OK, too. > If another program overwrites fac.txt then the semantics you gave in your ghost variables and assertions example would be simple, natural, and wrong If another program overwrites fac.txt, I cannot assume `readFile` to return anything other than a string, if that. I.e., I have nondeterminism about the next state. That's fine, because the next-state relation need not be a function, but you're right that in that case the semantics would be different from the other programs. > Really they're equivalent for the purposes of some kinds of analysis under certain constraints and they're not equivalent for other purposes. No. A specific denotational semantics is either equivalent for those programs or not. I can either guarantee that the next state is deterministic, or I can't. However, you are right that using this kind of semantics can create a situation where one program is a refinement of another. For example, one program can say that the current and next values of the variable x are even integers. Another can say that they're always 2 or 4. This makes program 2 an instance of program 1. Just as in FP you have the notion of a cartesian-closed category (sort of) on types, where every program is an object in that category, in this other kind of formalism you have a lattice that relates all programs. It's just a different theory. > The functional formalism handles this essentially as well as possible Not really, because IO is essentially nondeterministic, and functions don't model nondeterminism well (but relations do!). That's exactly why you need to stuff IO, or anything else that doesn't quite fit the concept of a function, in a monad (which can express all forms of nondeterminism). It's a neat trick, but, like you say, it's sort of an escape hatch. That doesn't mean that all formalisms need to do this for IO, concurrency or other forms of nondeterminism. Functions aren't a great fit for nondeterminism, but other mathematical objects really have no problem with it.