4 ms·
In an ideal (?) world, a refactoring would come along with a machine proof that the refactored code is equivalent to the original code (because otherwise, how c
by layer8 3y ago
In an ideal (?) world, a refactoring would come along with a machine proof that the refactored code is equivalent to the original code (because otherwise, how can you be sure?). In that case, the compiler would also be able to prove that the code is still safe.
I believe that type checking should closely match the reasoning programmers do in their head, and thereby verify the correctness of that reasoning. Conversely, this means that programmers must express their reasoning through the type system. If something doesn’t typecheck, either the reasoning as expressed is wrong or incomplete, or the programmer has used some reasoning that cannot be expressed in the type system (meaning that the type system is lacking in that respect).
- waynecochran 3y agoProving that two programs are the same is not decidable either.
- scarmig 3y agoProving that two real numbers are the same is not decidable either. Despite that, there are some real numbers that we can prove are equal to each other (rarely).
- quickthrower2 3y ago“You can’t do it in general” is the bathwater.
- waynecochran 3y agoYeah I am not clever enough to come up with a baby worth throwing out. Restricted to lexical scope seems pretty reasonable. Maybe someday this will compile: let mut viridian = Colour(52, 161, 128); let x = &mut viridian; let y = &mut viridian; if find_counter_example_to_Reimann_Hypothesis { do something with x and y }
- pyrale 3y agoMore like you're arguing that there is no baby in the bath you want to throw out. Coming back to your previous comment: > This (i.e. proving a variable is never used) is impossible in general since it is equivalent to the halting problem. Many useful provers/programs don't suffer from the halting problem. Just because you're given a turing machine doesn't mean you can't use a subset of it with different properties.
- quickthrower2 3y agoOtherwise you’d give up having types and linters because god forbid they might prove a program will halt!
- andrewflnr 3y agoJust to make it explicit, checking an existing proof is very decidable, given a reasonable programming language. Now getting that proof does pose some practical difficulties, but it would doubtless be built up by fairly simple proofs derived from user-supplied editing steps; a bit of a pain, but not Halting-complete.
- layer8 3y agoBy that logic, one could never do a refactor and be confident it didn’t change program behavior. Luckily, a program and it’s refactored version aren’t two arbitrary, unrelated programs. You can generally prove if the transformations that convert one into the other keep the semantics unchanged. Conversely, one should only ever apply transformations for which this is true.
- lmm 3y ago> I believe that type checking should closely match the reasoning programmers do in their head, and thereby verify the correctness of that reasoning. Conversely, this means that programmers must express their reasoning through the type system. If something doesn’t typecheck, either the reasoning as expressed is wrong or incomplete, or the programmer has used some reasoning that cannot be expressed in the type system (meaning that the type system is lacking in that respect). Right. The (well, a) problem with NLL in Rust is that it isn't expressible; it creates lifetimes that don't correspond to anything in the syntax, and so can't be written explicitly into the program even if the programmer wants to. (As opposed to conventional type inference where you can always write the type explicitly if the code is confusing)
- Rusky 3y agoYou couldn't write explicit lifetimes before NLL, either. (Nor does conventional type inference mean you can always write the type! This is why people who design type systems care about "principal types.") NLL (and even moreso Polonius) brought the borrow checker closer to how programmers reason about lifetimes in their head than it was before, empirically speaking. The thing you described was a worry at the time but it never turned out to be accurate. If there is anything about the borrow check that does match your description, it is things like "borrow splitting" and mutable reborrows, which can be done locally but are not expressible in function signatures. These problems existed long before NLL, though, and don't have anything to do with syntax or lexical scope.
- lmm 3y ago> You couldn't write explicit lifetimes before NLL, either. Well, no, but you can write scopes explicitly, and all your lifetimes correspond to scopes, by definition. > NLL (and even moreso Polonius) brought the borrow checker closer to how programmers reason about lifetimes in their head than it was before, empirically speaking. The thing you described was a worry at the time but it never turned out to be accurate. It worked for how some programmers reason about lifetimes in their head. Not for me. Maybe I'm the minority.