4 ms·
A side point since the author pointed to Agda as being more pure than Haskell: In many practical situations, computations have deadlines, which may either be a
by skybrian 8y ago
A side point since the author pointed to Agda as being more pure than Haskell:
In many practical situations, computations have deadlines, which may either be a timeout or the user giving up and cancelling. Languages that guarantee that functions terminate aren't as useful as you might guess, because they don't say anything about how long it will take. (It could be millions of years.)
A guarantee that a function will terminate is useful when you can avoid evaluating the function at all, while relying on a function call's existence (without compile errors) as a proof that the result exists.
It's not too often that you want to know that an answer exists without knowing the answer. This mostly comes up in mathematics when proving things.
- lmm 8y ago> Languages that guarantee that functions terminate aren't as useful as you might guess, because they don't say anything about how long it will take. (It could be millions of years.) That's a theoretical problem, but is it one that comes up in practice? In my experience those languages eliminate the overwhelming majority of long-running functions, so are about as useful as you might think.
- skybrian 8y agoI don't think it comes up much in practice because bugs due to non-terminating code don't actually happen much to begin with (compared to all bugs that cause hangs or timeouts), and when they do they are often found via testing. We know that a function terminates for any inputs it was tested with. But I have little experience with these languages (I've mostly read about them) so I'd be interesting to hear about your experiences.
- lmm 8y agoThe "testing will catch it" argument is used as a rationale for avoiding types at all. Of course testing does work, but I find it's more costly and less reliable (e.g. I remember one infinite-loop bug that was missed because it was an overloaded function and the test was invoking another variant). I wouldn't start porting production systems to Idris just yet, but I do think it's worth adopting the same kinds of techniques: avoiding loops entirely, and making sure that when you do recursion it's very clear from the code what parameter is getting smaller in what sense.
- joel_ms 8y ago>I don't think it comes up much in practice because bugs due to non-terminating code don't actually happen much to begin with (compared to all bugs that cause hangs or timeouts), and when they do they are often found via testing. We know that a function terminates for any inputs it was tested with. None of these are acceptable in Agda actually, since they would all be partial functions (i.e. functions that are not defined for some inputs.) The simplest, intuitive explanation is that since Agda has dependent types it needs to be able to evaluate functions during typechecking, and if you allow partial functions (e.g. infinite loops, halting functions, functions that timeout, or functions that are undefined for untested input) the typechecking would be undecidable. Instead Agda has a bunch of built-in tools to help the compiler figure out if a function is total (the opposite of a partial function, meaning it's defined for all possible inputs). Things like the termination checker can detect a subset of all terminating functions, and sized types let the programmer aid the compiler in figuring this out. There are also language pragmas to overide this totality check on a per function basis. I've implemented an algorithm, that I knew on paper terminated, and had it rejected by Agda, although I'm not experienced enough to know how easily these things are solved in general.
- skybrian 8y agoYes, static analysis is very useful for understanding what the source code will do for inputs you didn't test. Testing is rarely exhaustive. However, testing will find performance issues where static analysis won't. To quibble with "none of these are acceptable in Agda": it seems unlikely that Agda or anything like it would detect hangs or timeouts due to code not meeting its deadline. Deadlines and performance constraints are not part of any type system I've ever heard of. Furthermore, performance is dependent on the compile toolchain, the runtime, and what else is running on the same machine, so it's not even well-defined for static analysis unless you make a bunch of deployment-specific assumptions. A language may guarantee that a function is total in a theoretical sense, but you might not be able to calculate its value for some inputs in practice. (Consider something like "a ↑↑↑ b".) So this guarantee is subtly different from what most users of computer systems would actually want. Of course, as a another commenter pointed out, this sort of practical bug-finding is not actually what the termination guarantee is for.
- theaeolist 8y agoThe reason for banning nonterminating functions is different, logical not computational. If you want a programming language to work as a proof checker then you want its type system to be a consistent logic, so that a program P of type A can be used as a witness that proposition A is true. Using non-terminating computation you can create such witnesses for any type, including whatever you may want to represent "False". So you have an inconsistent (useless) logic.