4 ms·
> What you're forced to do is distinguish pure from impure computations somehow. Imperative languages can do that very, very easily. The definition of PFP, tho
by pron 11y ago
> What you're forced to do is distinguish pure from impure computations somehow.
Imperative languages can do that very, very easily. The definition of PFP, though, is that it is referentially transparent, i.e. no effects whatsoever (other than monads that are returned to the runtime at the top level).
> I need a purely functional algorithm.
Good luck finding one with the same performance... But the imperative one is now proven to be correct with no need for PFP. Writing a similar provably correct PFP one would have been harder (so it seems to me at least).
> but equational reasoning is so simple that programmers can do it manually anyway.
That's a nice claim. What we know for a fact is that programmers are able to write programs that are as correct as they're required to be with imperative reasoning.
> IT's too complicated for humans to verify too. If it weren't, more people would be doing it casually.
I don't understand exactly what you're referring to, but most programs as correct as people want them to be. The correctness crisis is over, mostly thanks to automated testing.
> If you give me a proof
Who says we want correction proofs to begin with? Most projects require some evidence of some measure of correctness. Certainly not proof of total correctness or even proof of partial correctness.
- catnaroek 11y ago> Imperative languages can do that [distinguish pure from impure computations] very, very easily. In an imperative language, can I write a map or filter whose argument is guaranteed to be pure? [Note that my notion of "pure" is stronger than Haskell's: I consider nontermination an effect.] Can you easily convince the type system that an imperative loop will indeed terminate? [Without supplying anything even vaguely resembling a proof.] With pattern matching and recursion, the compiler can check whether recursive calls are always passed smaller arguments. > Good luck finding one with the same performance... I'm pretty sure that, with substructural types, it's possible to update a single array element in O(1) in a referentially transparent manner. Conceptually, you're destroying the old array, and creating a new one with the same contents, except for the updated element. But, because the old array won't be used anymore, this can be done in-place. As far as I can tell, no other imperative facilities are needed to sort an array. > as correct as they're required to be What does this even mean?
- pron 11y ago> In an imperative language, can I write a map or filter whose argument is guaranteed to be pure? Of course. See, e.g. Java's checked exceptions. If you marked every effectful function as throwing a checked exception, the compiler can enforce which effects are allowed. > Can you easily convince the type system that an imperative loop will indeed terminate? [Without supplying anything even vaguely resembling a proof.] With pattern matching and recursion, the compiler can check whether recursive calls are always passed smaller arguments. Model checkers can do this just as well. > What does this even mean? That programs aren't required to be 100% correct, just as they aren't required to be as fast as possible. It is perfectly acceptable for most programs to fail on rare edge cases. If there is an inverse relationship between the manifestation of the bug in the frequency of the circumstances that causes it, then you're fine (put simply: it's OK to fail with ever higher probability on ever rarer cases).
- tel 11y agoEquational reasoning extends to mutation as long as you track the monad. It also smoothly devolves into Hoare Logic. It's the same tool, just applied in either different (monadic) contexts. Mutation is not disallowed in PFP, by the way! You can write a perfectly great Timsort that's pure. You just can't pretend that your mutation effects are not observable when they are. (And you can use monads as type cues when that occurs).
- catnaroek 11y agoIn all fairness, Hoare logic just happens to be something I want to avoid doing as much as I can. Also, you can have a pure Timsort with linearly or affinely typed arrays. Only action-at-a-distance truly requires some framework (monads, algebraic effects, whatever) for embedding an effectul language.
- tel 11y agoYup, that's another way to do it so long as you're interested in paying the explicitness tax to introduce substructural types. My point about Hoare logic is not to promote it but instead to note that it's not categorically different from equational reasoning except in that it operates over more complex languages. And then that exactly is your tradeoff.
- pron 11y ago> You can write a perfectly great Timsort that's pure. I would be interested to learn how (with the same space complexity?), but anyway my point is that writing a provably correct Timsort using CH is harder than simply proving the imperative algorithm with a model checker.
- tel 11y agoHave a pure model of memory which is implemented directly. Associate this with a proof that the extensional side of it is pure (copying mechanics of substructural types) and you're done.
- 11y ago