3 ms·
Functional programming languages like Haskell, ML, and Lisps use linked lists very extensively and rarely have safety problems as a result. On the contrary, be
by kragen 4y ago
Functional programming languages like Haskell, ML, and Lisps use linked lists very extensively and rarely have safety problems as a result. On the contrary, because linked lists allow you to build a list up efficiently without mutation, they give you a good way to avoid all the safety problems that come from mutation. In general just about any kind of data structure in these languages is some sort of weird linked list.
This isn't the best solution for all cases! Sometimes performance is more important than safety, and there are things you can't do as efficiently without mutable data. And sometimes (especially for systems that are reactive rather than transformational, in Harel and Pnueli's terms, or for libraries) a garbage collector is an unacceptable cost.
And Rust is actually reasonably good at singly-linked lists; it's just doubly-linked lists (which inherently feature mutation) that are troublesome. Singly-linked lists with sharing through Arc are a little more expensive in Rust than in something like GHC, Ikarus Scheme, or OCaml, but that's hardly a damning criticism of Rust.
But you seem to be claiming that linked lists are unsafe in any language, and to anyone familiar with functional programming, that claim is obvious nonsense. Did you intend it?
- andrewflnr 4y agoI should have been more specific about doubly linked lists. And I think the implicit context for comparisons with Rust is usually pointer-heavy non-GC languages, especially given OP, but maybe I should have specified that, too. It's certainly true that DLL's are tricky to write, and tricky to mechanically prove correct, which is mainly what 'unsafe' actually means.
- kragen 4y agoThank you for clarifying! I would think that the implicit context for safety comparisons with Rust would be other languages designed with safety as a goal. Those languages are almost all GCed! ML, Haskell, Scheme, Oberon, Coq, Erlang — all GCed. That's because GC helps enormously with type- and memory-safety. In the example in question, it ensures that your doubly-linked list manipulation cannot cause undetected type errors, use-after-free errors, double-free errors, or memory leaks; this last guarantee goes beyond what Rust can offer in this case. In ML, Haskell, and Oberon, it even ensures that all type errors are detected at compile time instead of run time. There are a few languages designed with safety as a goal that do not normally use GC: Pascal, Ada, COBOL, and MISRA C. But they suffer enormously in expressivity, are not pointer-heavy, and are generally only viable alternatives in restricted domains. The usual pointer-heavy non-GC languages are C and C++, and these have no concern whatsoever for safety, so it seems like a weak-man argument to target linked-list manipulation in them as unsafe relative to Rust. The correctness criteria for doubly-linked lists are indeed not within the capability of Rust's (or Haskell's, or ML's, or Oberon's) static checking. That doesn't imply that it's impossible to statically verify doubly-linked-list manipulation code, and in fact I think Ada SPARK is capable of doing it. Certainly it's within the scope of what you can prove with Coq or Isabelle/HOL.
- andrewflnr 4y agoI did say tricky, not impossible. ;) IIRC proving pointer-pushing code is an active research area, but I could easily be out of date. Not cheap enough to be mainstream yet, anyway. We're deep into semantics territory with "what's the right context for comparing Rust", but I would strongly argue that yet another language safe via GC is not interesting for its safety. As you point out, it's been done a lot. Rust is interesting because it pushes safety into a new level of runtime performance and (to some extent) lower hardware abstraction. AIUI that's the motivation for Rust, where most of the marketing and enthusiasm is, etc. And if you don't need that speed/control, Rust isn't much of an improvement: just use a GC and have more fun (unless you just think Rust is neat, I guess, but whatever). So it's the languages already in that "low level" domain (broadly defined) that are its real competition IMO, C/C++, upstarts like Zig/Nim/Crystal, etc, languages where linked lists are on the cards. Especially for the problems where safety has previously been seen as too costly in either runtime or development time (no one is coding to fast moving web standards in Ada/SPARK, methinks). And I don't think I implied that those languages' list manipulation is less safe than Rust's, rather that Rust's isn't any worse, besides being uglier. I made almost the same point from the other direction in another sub-thread: there's no use denying that Rust code for DLL's is uglier for no safety benefit on that particular task. As others have pointed out, the whole question of linked lists in Rust is a huge distraction from its actual benefits and weaknesses.
- kragen 4y agoWell, Rust can offer some kinds of guarantees that GCed languages can't, in the cases where its type system applies. It can allow you to safely share mutable data between threads, for example, or to guarantee that opened files get closed in a timely way. So I don't think it's interesting only because it pushes safety into a new level of runtime performance, though often that is also true. I think it's noteworthy that, not only in the doubly-linked-list case but even in cases that use Arc (which doesn't require `unsafe`), Rust is less safe than mainstream GCed languages like Java (and arguably Haskell and OCaml). Rust can leak memory; those other languages can't. Its safety guarantees in those cases are a proper subset of theirs. Unless I'm misunderstanding the situation? I've only written very small amounts of Rust.