News for hackers. Stuff that matters.
Re:Correctness and composability bugs in the Julia ecosystem by pron on Monday May 16, 2022 @04:48PM (#31402970)
> People get along fine without this feature, therefore there’s no sense in implementing it.

As someone whose job is to add new features to a programming language, that's never been my argument.

> But it cuts the other way, or we’d all still be using assembly

High-level languages were satisfactorily shown to be more productive than Assembly. I don't claim that no innovation works, just that not all do, and certainly not to the same degree. That feature X is helpful is certainly no evidence that feature Y is helpful, and that Python is more productive than Assembly does not support the claim that programs in OCaml are more correct than programs in Clojure.

Also, my argument isn't "we got by without it" or that no idea could ever work. It's that a specific claim was tested and unconfirmed.

> Was the superiority of structured programming and avoiding GOTO ever empirically proven, or did we all just collectively realize it was a good idea?

I don't know about the former, but the latter is certainly true, and until we actually reach concensus you can't claim we have.

BTW, I certainly don't claim that types aren't useful or even that they're not better in some ways (I believe that they help a lot with tooling and organisation), but the particular claim that they universally help with correctness, and do so better than other approaches, was studied, and simply not confirmed. You can't come up with a claim, try and fail to support it time and again, and keep asserting it as if it's obviously true, despite the evidence.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Monday May 16, 2022 @05:11PM (#31403185)
> As someone whose job is to add new features to a programming language, that's never been my argument.

I’ve definitely seen you argue along the lines of “it hasn’t been implemented in Java, therefore nobody uses it and we can’t tell if it’s a good idea or not” before. Forgive me for assuming this followed from that.

> You can't come up with a claim, try and fail to support it time and again, and keep asserting it as if it's obviously true, despite the evidence.

But “correctness” of itself is pretty nebulous. If we define it as whether or not the program conforms to one’s intentions with writing it, I would expect static types alone not to show a significant difference in correctness. Probably formal methods do but they have much higher overhead.

However, in terms of eliminating patterns which are literally never correct, like dereferencing null pointers, violating resource lifetimes, or calling methods that don’t exist, static typing can in fact eliminate those patterns.

> the claim that programs in OCaml are more correct than programs in Clojure

My full-time job is Elixir so I know full well the consequences of maintaining large codebases in dynamic languages. I would switch to OCaml in a heartbeat if it ran on the BEAM! I want to know that I am calling functions correctly within a node when the module can be resolved at compile time. This is a really basic thing to want, and not one that dynamic languages can offer. The qualitative difference is similar to that between structured and unstructured programming: I can actually do local reasoning about a function without having to check all the call sites or write a lot of defensive tests.

This is an obvious advantage, and on some level I don’t really care if it contributes to formal correctness or not because it would make my job easier.

Re:Correctness and composability bugs in the Julia ecosystem by pron on Monday May 16, 2022 @05:44PM (#31403507)
> I’ve definitely seen you argue along the lines of “it hasn’t been implemented in Java, therefore nobody uses it and we can’t tell if it’s a good idea or not” before.

You have not seen me argue anything along those lines. I have, however, said the converse, that we try not to adopt features in Java until they've proven themselves elsewhere.

> However, in terms of eliminating patterns which are literally never correct, like dereferencing null pointers, violating resource lifetimes, or calling methods that don’t exist, static typing can in fact eliminate those patterns.

But the implication is reveresed! From A => B, i.e. types prevent certain bad things, you're concluding B => A, i.e. if you don't want those bad things then you should use types. That simply does not follow.

> This is an obvious advantage, and on some level I don’t really care if it contributes to formal correctness or not because it would make my job easier.

I wouldn't dare imply that types don't have certain important advantages, but that doesn't support the specific claim that types generally and significantly improve correctness — which many have tried to show and failed — and it certainly doesn't support the much stronger claim that if you want to improve correctness, the most effective way to do it is to use types.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Monday May 16, 2022 @07:58PM (#31404457)
> You have not seen me argue anything along those lines. I have, however, said the converse, that we try not to adopt features in Java until they've proven themselves elsewhere.

You’ve definitely argued that not enough software has been written in Haskell to know whether it’s the right tool for anything and whether strong types are actually a good idea.

> But the implication is reveresed! From A => B, i.e. types prevent certain bad things, you're concluding B => A, i.e. if you don't want those bad things then you should use types. That simply does not follow.

I really don’t know of a simpler way to do this than types. Do you? Honestly I would be using it if I did. All of the solutions I know to these problems involve types.

> that doesn't support the specific claim that types generally and significantly improve correctness — which many have tried to show and failed

What definition of correctness is being used here? Surely you’re not saying that optionals don’t eliminate null pointer dereferencing, are you?

Re:Correctness and composability bugs in the Julia ecosystem by pron on Tuesday May 17, 2022 @06:54AM (#31408597)
> to know whether it’s the right tool for anything and whether strong types are actually a good idea.

Nope. I don't know what you mean by "a good idea", and I prefer typed languages myself (mostly for tooling support), but I do often point out that the claim that types improve correctness — let alone the claim that they do that better than other approaches — is an empirical claim that is not supported by empirical evidence (which, in fact, appears to contradict it).

Also, that there have been few programs written in Haskell, and that Haskell has failed to demonstrate that it leads to better correctness are both pretty basic facts.

> All of the solutions I know to these problems involve types.

I don't know what you mean by "solutions to these problems", but while we've not found a correlation between types and more correct programs, we have found correlations between code reviews and tests and more correct programs. Types might well be the solution to many things (e.g. automatic refactoring and jump-to-definition), but the empirical evidence we have suggests that increased correctness isn't one of them.

> Surely you’re not saying that optionals don’t eliminate null pointer dereferencing, are you?

Types certainly eliminate various kinds of errors, yet studies did not find that they reduce bugs (except in specific circumstances; for example, there was one study that reported that TypeScript has 15% fewer bugs than JavaScript).

Just to give you a sense for one reason that happens, we can take your example of Maybe types. A null pointer exception occurs when code assumes a reference can't be null, but is wrong to make the assumption. A Maybe type would force a test somewhere. But the question then, is, what do you do when the value is empty? A brilliant study on software correctness [1] found that most catastrophic crashes in distributed systems occur not because programmers fail to consider certain exceptional situations — in fact, the language forces them to consider those situtations — but because they frequently do the wrong thing when those situations occur.

[1]: https://www.usenix.org/system/files/conference/osdi14/osdi14...

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Tuesday May 17, 2022 @10:39AM (#31411362)
> Types certainly eliminate various kinds of errors, yet studies did not find that they reduce bugs

Right, but this is why I asked about structured programming. These things are hard to study by their nature. I understand there’s not a consensus on this, but there are a lot of programmers who feel quite strongly that static types reduce bugs. Maybe that’s not good enough for you! But it’s clear that you accept other practices as beneficial on insufficient evidence. Or maybe you don’t — maybe you don’t think writing correct unstructured programs is harder.

> most catastrophic crashes in distributed systems occur not because programmers fail to consider certain exceptional situations

This is irrelevant though. The question is not whether static types prevent the most common types of bugs, or the most dangerous (it’s clear that memory safety is more important than static types in that regard.) If static types narrow the problem space to situations where you explicitly made the wrong decision, that’s significant. If there are any bugs caused by not handling exceptional conditions (and we both know that there are), then static type systems help reduce those.

Re:Correctness and composability bugs in the Julia ecosystem by pron on Tuesday May 17, 2022 @12:01PM (#31412611)
> These things are hard to study by their nature.

Small effects are hard to study by their nature. Big effects are usually easy to spot.

> there are a lot of programmers who feel quite strongly that static types reduce bugs

There are a lot of people who feel quite strongly that homeopathy cures all kinds of diseases, but they've failed to demonstrate that.

> But it’s clear that you accept other practices as beneficial on insufficient evidence

It's not about "accept." I myself practice typed programming without asserting the empirical claim that it reduces bugs, that seems not to be true (or at least, the effect does not seem to be big).

> The question is not whether static types prevent the most common types of bugs, or the most dangerous

So far, we've failed to show that static types reduce bugs, period. You're allowed to like them and promote them, but your feeling towards them does not make a specific empirical claim more or less true.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Tuesday May 17, 2022 @03:33PM (#31415351)
> There are a lot of people who feel quite strongly that homeopathy cures all kinds of diseases, but they've failed to demonstrate that.

This is a really poor comparison. How many people who know enough to judge these things believe that? I can understand that you’re rigorous in the empirical claims you accept here, but surely you can see that experienced software developers have somewhat more basis to make claims about type systems than random people do about homeopathy.

> or at least, the effect does not seem to be big

Fair enough! It’s probably not as big as testing or code review but I do think it exists. You mentioned the TypeScript study, it’s not like there’s no evidence for believing this like there is with homeopathy.

> So far, we've failed to show that static types reduce bugs, period.

I mean, how could they not? You still haven’t explained this part, except with vague allusions that the problems they catch are not the most common problems. I’ve explained how static types reduce bugs: by eliminating cases where you intend to handle a case and forget to. I’ll specify that I mean a type system with exhaustivity checking or narrowing with control flow (like TS or Kotlin). This is not an empirical argument, it’s a rational argument, and I still legitimately don’t understand what the flaw is. The way I see it, static type systems restrict operations on types to those known to be valid at compile time. In a sound type system and compiler, the resulting program is guaranteed not to make invalid operations on types at runtime. Dynamic programs are fully free to make invalid operations on types at runtime. Some number of bugs are caused by making invalid operations on types at runtime. Where are those bugs in a statically typed program, if they haven’t been eliminated?

Re:Correctness and composability bugs in the Julia ecosystem by adgjlsfhk1 on Tuesday May 17, 2022 @03:48PM (#31415521)
The extra bugs in a statically typed program go in the duplicated code that someone copied and changed the type names on because their type system wasn't flexible enough to let different types share the same code. This means that 3 years later when someone fixed a bug in part of the code, the bug remained in the other copy because the person writing the fix didn't know about the copy.

For a simple example, consider Arrow.jl vs the C++ implementation of the Arrow format. The Julia implementation is roughly 1/10th the lines of code (with more functionality), so even if there are 5x more bugs per line, the code still has fewer bugs.

Static types definitely reduce bugs per line, but they can still increase bugs per functionality.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Tuesday May 17, 2022 @04:30PM (#31415911)
But there are plenty of static type systems that let different types share the same code, the problem you describe only exists in nominal type systems (like C++) as far as I know. With structural types like in TypeScript or Go you can express this trivially.

For that matter you can do this with subtype polymorphism in most cases. In Rust you can do it with trait objects as long as you control either the type or the trait. Probably there’s a way to do it in C++ too.

Re:Correctness and composability bugs in the Julia ecosystem by pron on Tuesday May 17, 2022 @05:36PM (#31416576)
> but surely you can see that experienced software developers have somewhat more basis to make claims about type systems

But experienced software developers, more than "random people", should know that if they make a conjecture, it's tested and isn't verified, they should reconsider their conjecture.

> You mentioned the TypeScript study, it’s not like there’s no evidence for believing this like there is with homeopathy.

There is no evidence for believing this. If you believe the evidence for TS vs JS in particular, then you should also believe the failure to find a more general effect.

> I mean, how could they not?

That's an interesting question and there are many answers; I've been interested in the complex subject of software correctness for years, and have written a bit about it (https://pron.github.io/). The more you study software correctness, the more you learn how complicated it is and that there are no easy answers. In particular, you learn that it's not true that more soundness is always a good path toward more correctness. But if you accept your preconceived notions over empirical study, then there's little hope for making actual progress.

> Where are those bugs in a statically typed program, if they haven’t been eliminated?

I gave you an example of where they are. If you want to go down the path of thinking about the theory of software correctness, start by convincing yourself that for every JavaScript program there is a Haskell program (perhaps living entirely inside an Either monad) that behaves the same way.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Tuesday May 17, 2022 @06:59PM (#31417244)
I don’t think the subject of software correctness in practice is itself well-studied enough to say conclusively that my conjecture is false. I think what can be said conclusively is that at scale people cannot write memory-safe code in an unsafe language or type-safe code in a dynamic language, but obviously these are not the only kinds of correctness.

> In particular, you learn that it's not true that more soundness is always a good path toward more correctness.

I’m still curious what definition of “correctness” you’re using here. Formal correctness? Bugs per line of code? Generally I’m thinking in terms of formal correctness, in which case I think it’s basically a truism that more soundness leads to more correctness. At some cost, perhaps.

> I gave you an example of where they are.

Yes, but those bugs are not unique to static languages, and I’ve never claimed that static languages eliminate all kinds of bugs. As far as I could tell from reading the study, it’s not evidence that static languages encourage this sort of bug more.

To be blunt: I think the set of kinds of bugs that can be written in dynamic languages is a strict superset of the kinds of bugs that can be written in a static language. Maybe I’m completely wrong about this! But this is the root of my reasoning.

Re:Correctness and composability bugs in the Julia ecosystem by pron on Tuesday May 17, 2022 @07:33PM (#31417478)
> I don’t think the subject of software correctness in practice is itself well-studied enough to say conclusively that my conjecture is false.

I don't claim that. Given what we know, the likeliest explanation to the findings so far is that an effect, if it exists, is probably small.

> Formal correctness? Bugs per line of code?

Both would work.

> in which case I think it’s basically a truism that more soundness leads to more correctness. At some cost, perhaps.

And you'd be wrong, or, at least, the second part of your statement makes all the difference. What we want is the best correctness we can get for some given cost, or, given some effort, what should you do to get the most correct program? If you follow formal methods, some of the hottest lines of research right now are about reducing soundness to improve correctness.

> As far as I could tell from reading the study, it’s not evidence that static languages encourage this sort of bug more.

I didn't say they did. But you asked how we explain the observation that types don't improve correctness, and one explanation is that the kind of mistakes that types catch aren't the costliest bugs that make it to production, and perhaps the extra effort invested comes at the expense of other approaches that do uncover more serious bugs.

> But this is the root of my reasoning.

That's as good a conjecture to start with as any, but it needs to be revised with findings.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Tuesday May 17, 2022 @07:55PM (#31417625)
> perhaps the extra effort invested comes at the expense of other approaches that do uncover more serious bugs

I guess in my experience the effort invested programming in a static language is really not that much higher than dynamic, and in some ways I find it less effortful. For example: pattern matching on a sum type, being sure that I’ve handled all the cases I want to. Is there good empirical research on this?

> That's as good a conjecture to start with as any, but it needs to be revised with findings.

I was attempting to make a factual statement, not a conjecture. If it is true that static types eliminate a class of errors, then type errors must be really cheap for static types not to be worth it on those grounds. My prior is that compiler errors are cheaper than runtime errors here.

Re:Correctness and composability bugs in the Julia ecosystem by pron on Wednesday May 18, 2022 @05:10AM (#31420646)
Until it's been measured, a statement is a conjecture, not "factual." A conjecture that we've tried to verify yet failed to see a large effect is a problematic conjecture.

We don't have good empirical findings about many things, most likely because many effects are small at best. But it doesn't matter. You're can say that you still believe something despite failed attempts to measure it, but you can't see it's "factual." That is the difference between fact and conjecture.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Wednesday May 18, 2022 @11:18AM (#31423872)
> That is the difference between fact and conjecture.

Yes, but I'm trying to make a formal statement of fact here, not an empirical one.

> I think the set of kinds of bugs that can be written in dynamic languages is a strict superset of the kinds of bugs that can be written in a static language.

Here I am attempting to make a formal statement about the set of runtime behaviors that can be exhibited under static type systems. What I'm saying is that there is a set of incorrect runtime behaviors that can only be exhibited in a dynamic type system, that is, the set of type errors. I'm not aware of any runtime errors that can only be exhibited under a static type system. I'm not well educated enough in the relevant fields to be able to formalize this with notation (I would do so if I was, I think notation communicates these things much more clearly than words) but I do believe it has a formal representation.

> A conjecture that we've tried to verify yet failed to see a large effect is a problematic conjecture.

I think we're somewhat talking past each other here. What I'm saying is that the set of possible incorrect runtime behaviors is smaller in a static language. This can't really be empirically verified, it should have a formal answer in type theory or programming language theory. It's possible I'm wrong about what the formal answer is, but I haven't seen you address it yet. It's also possible that this is true but not strongly related to the way that bugs evolve in typical software engineering practice, I've speculated upthread that the total number of bugs might be similar because programmers make a higher number of repeated mistakes from the more narrow set while programming in static languages (though personally this seems unlikely). It's further possible that this is just not a very significant effect, as you have conjectured. However it is my belief that if there is an effect on bugs overall that it derives from what I understand to be a formal character of the runtime behavior of statically typed programs, that there are fewer ways for them to "go wrong."

Re:Correctness and composability bugs in the Julia ecosystem by pron on Tuesday May 31, 2022 @07:57AM (#31568527)
> What I'm saying is that there is a set of incorrect runtime behaviors that can only be exhibited in a dynamic type system, that is, the set of type errors. I'm not aware of any runtime errors that can only be exhibited under a static type system.

But that doesn't mean they have fewer bugs! They might well have more.

> What I'm saying is that the set of possible incorrect runtime behaviors is smaller in a static language.

Not exactly. For every program in an untyped language, you could write a typed program with the exact same behaviours.

The assertion that typed programs have fewer bugs is simply false in theory, and failed to be confirmed empirically.

> However it is my belief that if there is an effect on bugs overall that it derives from what I understand to be a formal character of the runtime behavior of statically typed programs, that there are fewer ways for them to "go wrong."

I understand that that is your belief, but it is supported by neither theory nor practice.

Re:Correctness and composability bugs in the Julia ecosystem by riwsky on Monday May 16, 2022 @09:37PM (#31405072)
“Want B” is not the same as “B”.

“Should do A” is not the same as “A”.

The reverse of “types prevent certain kinds of bugs” would be that “all code which doesn’t suffer from those kinds of bugs is typed”, not “if you don’t want those bugs, use types”. The parent does not assume B->A; your actual disagreement with them is over whether A -> B implies A -is-the-most-effective-way-to—> B.

I share your understanding of the evidence base around types, and I agree with your conclusions; my beef here is just with divorcing the language of formal logic from its substance.

Re:Correctness and composability bugs in the Julia ecosystem by jolux on Monday May 16, 2022 @09:54PM (#31405195)
Yeah, though I do actually think “all code which doesn’t suffer from those kinds of bugs is typed” is true to a first approximation, for what it's worth. That's a big part of the reason I prefer static types. Under a few thousand lines it's less true. It's really at scale that these things become a problem, and even so they're still manageable most of the time, they're just kind of a pain.
Re:Correctness and composability bugs in the Julia ecosystem by pron on Tuesday May 17, 2022 @06:40AM (#31408489)
Formalising natural language is tricky, but I believe "every PL that leads to more correct programs is typed" is either equivalent or stronger than "if you want a PL that leads to more correct programs it should be typed." It could be stronger if the latter phrasing takes measure into account (so a bit of fuzzy logic), meaning the possibility that other approaches also lead to more correct programs but not as well. Still, I contend that my formalisation is correct enough to demonstrate the logical error that even if types imply correctness (not substantiated by evidence), it does not follow that correctness implies types (even less supported by evidence).