126 karma · joined May 9, 2019
Other benefits of strong static type systems are compiler-enforced documentation (through types) and ease of refactoring. Of course, working in a typed system does constrain you, but I would argue that the cost/benefit ratio is usually quite good. I don’t typically feel very constrained when writing a program in Haskell, compared to Python. I do generally stick to “boring” Python code that would have passed a type checker if Python had one. It does depend a little on the type of application. For writing a compiler, I prefer Haskell, but for doing data-munging and one-off scripts, I prefer Python.
However, arguing about the cost/benefit ratio of programming language features is often difficult, since the benefits and costs are hard to quantify. I do think that it isn’t reasonable to measure the cost of a type system by porting a program from a dynamic language to it, since doing large scale rewrites from a different language is not a typical task. It’s also hard to tell which parts of the porting process are “extraneous” and which parts aren’t. If I port a program from Python to Lisp, I will also have to do some significant extra thinking to make it work, but it isn’t because of static typing of the target language. Porting between different languages is just inherently difficult, and will always involve non-trivial “extraneous” effort. Maybe it’s more work when going to statically typed languages, but it’s not a reasonable measure in any case.
How does this not qualify it as a language with practical applications? Frankly, your comment comes across as being based upon hearsay, instead of actual experience with the language and its community. You’re right that Haskell is not as popular as more mainstream languages, but that does not make it similar to Brainfuck.
[1] https://engineering.fb.com/security/fighting-spam-with-haske...
Moreover, our nature areas are generally smaller and closer to agriculture. Therefore, nitrogen output has (had) a lot more impact on nature here than in other countries.
More information can be found in this news article (Dutch): https://nos.nl/artikel/2307260-kan-de-ruime-duitse-stikstofn...
It's not just about what a program does and how quickly it does it. What matters at least as much is how easy it is to understand, modify and extend. Of course, that isn't necessarily language-dependent either, but I think some languages make it easier for you to design nice abstractions.
For example, C can make it more difficult to write nice abstractions since it forces you to worry about memory allocation and memory safety, and doesn't really offer facilities for generics.
Let's say speeding causes a harm of 500 dollars, and there's a 10% chance of getting caught. Then you would put the fine at 5000 dollars. However, it might be the case that a 500 dollar fine (with an expected payment of 50 dollars) is already enough to stop everyone from doing it, since nobody likes speeding so much that they would pay 50 dollars for it on average. In that case, setting a 5000 dollar fine would just be overkill, and it could hardly be called efficient.
Moreover, your answer assumes that utility can always be measured solely in terms of money. If we measure the utility of society in terms of the number of people speeding (lower is better), then no amount of money can compensate for an increase in the number of people speeding. Then the answer would be to set the fine such that the number of people who choose to speed is the lowest, and does not involve the "expected harm" to society at all.
Even if you do assume that there is a conversion factor between "number of speeders" and "money", then it might still be sufficient to set the fine at a much lower number than you would get using your formula. You cannot just take into account the utility of the society, you also have to take into account the preferences of individuals (which guide their actions).
This can also be used to justify individual fines: if a 100 dollar fine is enough to stop you from speeding, and a 200 dollar fine is necessary to stop someone else from doing it, then why should I set the fine for both at 200 dollars? How can this be called efficient? You could argue it's more fair, but that's more a question of what's moral and has little to do with simple calculations, which you seem to be advocating for.
Philosophically, I think it's also more interesting that Gödel's theorem would continue to produce such sentences, regardless of how large our universe happens to be. You could never have a universe that is so big that it could contain all Gödel sentences, even if our universe were bigger. This is a much more fundamental limitation.
Gödel's theorem gives you a sentence S where you can prove neither S nor its negation from the current axioms P. Of course, if you then add S (or its negation) as an axiom, then you CAN prove it. But then Gödel's theorem will just give you another sentence S', ad infinitum. You can never win this game.
If there were only a finite number of such "True, but unprovable using your current proof rules" sentences, then you could simply add those sentences to your list of proof rules and there would be nothing "True, but unprovable" anymore. For Gödel's theorem to work, you need at least an infinite supply of those kinds of sentences.
Also here there's no need to actually write down all of them exhaustively. It's just important to be able to find "yet another one" whenever you would like to, which requires an inexhaustible supply.
A lot of these ideas don’t require any actual “realized” infinity, however. For instance, there are infinitely many natural numbers, but natural numbers themselves are still finite. You can write a program that prints every number at some time in the nearby future (ignoring physical constraints), even though there is no point in time where it will have printed all numbers.
If you want to take away infinity, you have to draw an arbitrary upper bound somewhere, since unbounded things are infinite. Drawing that line is fairly arbitrary since there is no reason why things should no longer work if you add just one more.
Keeping a functional style, regardless of the language (although FP languages lend themselves better to this) can help in keeping code more decoupled, since you have to be explicit about side effects.
I think that both FP and imperative languages have places where they shine, and I freely switch between them depending on the project. Given how much some imperative languages have recently borrowed from FP languages, I think that this shows that functional programming has some significant merits.
Currently humans are much better at proofs that require this kind of deep thinking. Automated tools are better for proofs that are based on a simple structure, like a large enumeration of cases (as in SAT solving and model checking, oversimplifying things a bit). This is the very reason they are automated: the reasoning performed by them is so simple/well-structured that we are able to write a program to do it for us.
However, many proofs fall outside of this easy-to-automate subset, and require human assistance. Human intuition does consistently do better than automated tools, but there is no single easily recognizable "trick" or "method" to it, which makes it hard to implement in a tool.
In my view, the reason that theoretical results do not apply very directly to human reasoning is precisely that human reasoning is "intuitive" and hard to capture in a program. We are not really Turing machines in any practical sense. We are more adept at proving things (perhaps creating automated tools to help us along the way) than any known algorithm.
I absolutely agree that automated tools make much more sense for your average industry application, but if you want to be able to use the full power of human intuition, instead of restricting yourself to program properties that are easy to prove automatically, then there is no way around manual proofs.
That is, I don't think one can say that the reason why human-aided verification is unfeasible for some projects (say, the entire Linux kernel) is because of theoretical limitations. Yes, verifying the Linux kernel would take too much time, but not because of any specific theorem in theoretical computer science.
The reason why I am emphasizing this point is that I believe that referring to theoretical results in discussions like this makes it seems as though there is some kind of fundamental limitation that prevents people from verifying the Linux kernel in a proof assistant. Even though it is quite a jump to conclude that from theoretical results, especially when human intuition is involved.
I would say the reason that people haven't verified a program the size of the Linux kernel is that it's just too much work. Just like if I were to try to write the Linux kernel from scratch on my own, it would take me years and years. But not because of a mathematical theorem. Some things are just a lot of work without there being a deep reason behind it.
We can go much further with deductive verification combined with automated verification compared to automated verification alone, precisely because human intuition can be used to guide the automated tools.
EDIT: To give another example, I would have no problem with the following reasoning:
A SAT solver that is efficient for arbitrary SAT problems cannot be implemented, because SAT is NP-complete (assuming P =/= NP).
However, I would have a problem with the following line of reasoning:
Intel CPUs cannot be fully verified by people because SAT is NP-complete.
Humans regularly do "outperform Turing machines." Most of the complicated mathematical proofs that have been produced by humans, cannot currently be automatically produced using an algorithm in reasonable time. Pick almost any non-trivial mathematical theorem, and you would be hard pressed to write a program that could prove it in a reasonable amount of time given just a list of the axioms. In theory, humans might not be able to outperform TMs, but in practice they regularly do, as attested to by the large amounts of mathematical proofs that we have produced by hand.
Model checkers also outperform humans for some tasks, but then again this is because human intuition has been used to write the model checker in the first place. My point is that using theoretical computer science results to talk about the difficulty of finding mathematical proofs in real-world cases is a bit of a non-sequitur. Yes, the Linux kernel would be practically impossible to verify completely using semi-automated tools, because it would take too much time and effort. But is this because of some theoretical result about the model checking problem? I don't think so.
One difference between having a model checker call a proof assistant and using a proof assistant to implement a verified model checker is that if you write a verified model checker implementation, you can be almost 100% certain that it's bug-free, because it creates proof terms that can be independently checked by the (ideally small and simple) proof kernel of the proof assistant. You don't have to trust that the model checker has been implemented correctly. This difference does not matter that much in practice, however, since model checker implementations probably receive a lot of testing and are quite trustworthy.
You're right that I am mostly talking about Coq, and that a different style tends to be used in Haskell/Idris. Note that dependent Haskell is actually logically inconsistent for backwards-compatibility reasons anyway, so there's not much to lose there by cutting a few corners for pragmatic reasons. It is not necessary to verify every single part of the program. Dependent types in Haskell gives you the freedom to do more. You can choose not to use that freedom where it doesn't make sense.
Furthermore, you don't necessarily need to have an intuition about why the program you are working on is correct to formalize it using dependent types. You just need an intuition about a method for CHECKING that the program is correct.
The four-color theorem was proved in Coq, and it required considering over a thousand cases. No one can keep a proof of this magnitude in their head, but that didn't prevent it from being formalized in a proof assistant. What they did was they just formalized the method for checking and then used that. You can similarly formalize the kind of reasoning that a model checker (or any other automated method) does and then use it in your proof assistant.
One major benefit that proof assistants have over other formal methods is that they can be used to prove essentially arbitrary properties of programs, which is not true of any automated methods. Basically, if we as humans are able to convince ourselves that a program has a certain property, then we could also show this using a (dependently-typed) proof assistant.
(Yes, theoretically all proof systems have limitations due to Gödel’s incompleteness theorem, but this limitation applies just the same to ALL formal methods. Furthermore, you’re not that likely to run into it in practice unless you are doing metatheory, and even there many interesting statements CAN still be shown.)
Consider the formally verified C compiler CompCert, where the assembly output of the compiler has been proven to have the same behavior as the input source code. A proof like this simply cannot be done using automated methods currently, and requires human assistance. This kind of correctness proof is also highly non-compositional, since the correctness proof of a compiler does not mirror the structure of the compiler very closely. Hence this also invalidates your point about dependent types not being able to handle non-compositional properties very well. There are plenty of other examples, like the seL4 microkernel.
I also do not understand what bearing computational complexity results have on humans manually formalizing their informal intuitions about program correctness in a proof assistant. Humans do not work on arbitrary problems where they have no intuition at all about why a program is correct, hence referring to worst-case computational complexity results does not make much sense here. In fact, if you have no intuition about why a program works, then how did you manage to write it in the first place? You surely did not write random garbage in the hopes that you would get a working program.
You might say that there are programs you can check using a model checker, but which humans cannot reasonably keep in their heads or form an intuition about, and therefore these proofs cannot formalized in a proof assistant. But what you can do is implement a model checker in your proof assistant and then show that the model checker is correct. After you've done that, you can simply use the model checker to do your proofs for you. And of course it should be possible to formalize the model checker itself, since the people that wrote the model checker must have some intuition about why it works and produces the correct results. In this sense, proof assistants subsume all other formal methods, since they can be "scripted" to include them.
Furthermore, it is generally not the case that you have to rewrite your program in case you want to prove some more properties about it. You may be thinking of a programming style where the type of a program encodes all the properties you are interested in, but you can avoid this style where necessary, by separating your program and its correctness proof.
Even in the introduction there are statements which do not make sense, like the statement that you are required to show that A and B are true in order to conclude that A logically entails B. This is simply not the case, since it is very well possible for A to be a formula which is always false (unsatisfiable/inconsistent), in which case A entails ANY statement, including B.
Adding annotations requires more programmer effort and reduces the level of abstraction of your programming language. Rust takes this approach, but tries to keep the level of annotation somewhat reasonable, and provides the "unsafe" escape hatch for when you cannot convince the compiler that what you're doing makes sense. (Although I do believe that it would be possible for the Rust compiler to infer most/all lifetimes).
For instance, in a functional programming language, you are typically creating closures all over the place, like one of the other posters mentioned. It seems quite unlikely that there is any kind of reasonable lifetime annotation system that would capture all of the complex lifetime patterns that you would see in such a language.
One can say "Oh, but surely someone smarter than me must be able to come up with something that works for those situations", but I don't think that is a very constructive line of thought, since you could say that about pretty much everything. Rust is an example of a language where lifetimes work reasonably well, but Rust already makes some tradeoffs that reduce its level of abstraction to some degree. It doesn't provide the same level of abstraction that, say, Haskell does.
Program analysis would allow you to keep your level of abstraction and ideally not require only little annotations. However, since any non-trivial program property is undecidable, program analysis is fundamentally incomplete and it is again unlikely that it would be able to deal with all lifetime patterns that you see in practice.
Therefore, it seems to me that there is no free lunch here. Either you sacrifice abstraction by requiring annotations or you don't require any annotations but then you have an incomplete program analysis.
(Also, you seem to think 30 years of good research has been wasted on the "obviously bad idea" of garbage collection, but somehow none of these researchers were good enough to realize this and come up with the silver bullet that makes GC unnecessary? After all, people were already thinking about GC-less languages long before Rust was a thing)