And that's what I was referring to. BDDs inherently require Rc<T>/Arc<T> (as long as you want to be memory-safe, at least) and therefore incur significant overhead (reference counting is one of the most expensive forms of automatic memory management). I use BDDs as an example, because there's no way to work around the structural sharing, as it's a requirement for an implementation.
In addition, aiming for zero-cost abstractions is hardly a Rust-only thing. That's more of a Java problem because it only has polymorphic methods and no value types. Outside functional languages, lack of zero-cost abstractions is not a particularly common issue.
And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust.
So we come full circle to your claim that Rust is not "at all attractive", despite being able to express programs more compactly, more elegantly, and more safely than in C/C++, without losing the performance. So I still don't see the case for this claim.
> Outside functional languages, lack of zero-cost abstractions is not a particularly common issue.
Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphic elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system.
I'm frankly finding it hard to believe you think there are serious alternatives. Certainly MLTon if you want the same specialization done, but you then have the unavoidable GC cost, so you're still back to non-zero runtime overhead.
I'm not comparing to C/C++. I'm comparing to other memory-safe languages.
The more general problem is that Rust cannot offer zero-cost abstractions for shared ownership as a result of how it is designed. This is the really killer issue. It's a problem for pretty much any persistent data structure, for example.
> And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust.
The unsafe approach would be to do use an array representation, use indices instead of pointers, and roll your own garbage collector. Or manually remove unnecessary reference count updates whenever you can prove that they are unnecessary. Both of which cannot be easily hidden behind a safe zero-cost API.
> Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphica elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system.
The entire Wirth family of languages qualifies, too. Or Eiffel. Or Fortran. Or Modula-3. As do more recent languages such as Nim and D. Honestly, off the top of my head I can't think of an imperative language with native compilation that doesn't and isn't totally obscure, other than Swift and Go (and even they only some of the time). Note that zero-cost abstractions need to only exist, not that they have to be the only option. Languages can and do provide both expressive constructs that come with overhead and less expressive constructs that are overhead-free. 90:10 rule, premature optimization, and all that.
In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization).
I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard.
There are potentially many unsafe approaches, and possibly even some safe ones.
> The entire Wirth family of languages qualifies, too. Or Eiffel [1]. Or Fortran [2]. Or Modula-3 [3]. As do more recent languages such as Nim [4] and D [5].
[1] Doesn't support expressing stack allocation patterns, which are essentially to achieving true zero-cost abstractions.
[2] Oh yeah, that'll be easy and maintainable to program.
[3] Doesn't support 64-bit Windows. Verbose like Ada. Abstraction is weak compared to Rust. Also doesn't support expressing stack allocation.
[4] Nim requires a GC, so not zero cost. It also has surprising runtime semantics. For instance, fields that are are guarded by a clause raise runtime exceptions. These would require different cases which are checked for exhaustiveness statically in Rust.
[5] D is not memory safe for non-trivial programs if you're not using the GC.
Clearly you and I have a different understanding of zero-cost abstraction.
> In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization).
Code size is not a problem when discussing zero-cost abstractions. Honestly, it just seems like you're grasping for something to nitpick on.
> I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard.
I have no idea what you're talking about. Once they removed all the special syntax for pointer types years back, Rust is very readable to anyone from a brace-based language tradition.
Says someone that never wrote a single line of Eiffel.
That is what local variables defined as expanded classes are for.
local
array: expanded ARRAY[INTEGER];
do
array := <<1,3,2>>
sorter.sort(array)
....
end
Says someone that never wrote a single line of Modula-3.
TYPE
Time = RECORD
seconds: INTEGER;
milliseconds: [0..999]
END;
PROCEDURE MyProc =
VAR
t: Time; (* Stack Allocated *)
BEGIN
t.seconds := 0;
t.milliseconds := 0
END MyProc;
"Zero-cost abstraction" means "You couldn't have coded it any better yourself." If the problem requires a certain amount of overhead, than an implementation of that solution is considered zero-cost. Rust can't change the laws of math.
Maybe Bjarne should have called it the "Zero additional-cost abstraction" instead; I think it'd clear the principle up a lot.
His contention is that languages with GC don't require reference count updates, and so manipulating the BDD graph is much cheaper in these languages since the resource accounting overhead is deferred by some non-deterministic time.
To be clear, the "contention" is the well-known problem that reference counting (especially atomic reference counting) is one of the most expensive automatic memory management techniques in existence, and it takes pretty significant efforts to get it on par with a modern tracing collector. That's because reference counting has high overhead and poor cache locality (as it comes with a built-in pointer chasing requirement even when you assign a reference).
That the cost is deferred has nothing to do with it.
Second, the reason why I use the BDD example (or, more generally, persistent data structures) is that it's the simplest way for online discussions, because (unlike simpler examples), it's not amenable to pseudo-solutions that don't resolve the underlying problem and that you don't have the space and time for.
The underlying problem is that Rust doesn't really do safe zero-cost abstractions for multiple ownership, and multiple ownership crops up more often in actual Rust code than people like to admit (global caches and memoization often end up with using cloning). You have to deal with it either through Rc<T>, Arc<T>, or cloning, of which cloning is the most common solution, because you don't have the footprints of shared ownership all over your code.
As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means.
> As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means.
I'm going by Stroustrup's definition [1]? If your argument is – I'm not sure here – that "Rust gets zero-cost abstractions by limiting what you can do to beat its normal mechanisms", then that's not terribly convincing. What it boils down to is that multiple ownership is a weak spot of Rust, as for other languages that attempt the compile-time memory management thing, such as ParaSail. TANSTAAFL, "There ain't no such thing as a free lunch." No compile-time mechanism can solve the reachability problem for arbitrary runtime graphs without adding some overhead somewhere. Rust does zero overhead for certain kinds of graphs, but still needs overhead for others.
Yeah Bjane's definition doesn't say "no overhead", it says "no extra overhead." If your data structure requires a GC, then writing a GC for it is a zero-overhead abstraction. What I'm saying is "gotcha, you need some runtime support for this" is not contradictory to zero-cost abstractions.
There are two points to be made here.
1. The problem is not that a data structure needs GC; it's that reference counting (or worse, atomic reference counting) is about the highest-overhead garbage collection in existence. It's popular because it's easy to implement, has mostly predictable performance, and can be implemented as a library without compiler support, but performance is not one of its virtues. The cost really becomes absurd in the `Arc<T>` case, where you have an atomic operation for each reference count update. Nobody actually implements performance-sensitive data structures using naive atomic reference counting outside of C++ and Rust.
2. Persistent data structures (or anything with structural sharing) are, as I mentioned, just the simplest example. They are suitable for illustrating the problems Rust has with shared ownership, but shared ownership is not limited to those. Rust also has problems with shared ownership in a number of other scenarios (such as global caching or any scenario where object lifetime depends on the semantic state of a program).
The underlying problem is that whenever you approximate an undecidable predicate (pointer safety in this case) with a decidable subpredicate, then any zero-cost abstraction claim usually falls flat, because there are typically other decidable subpredicates (not even counting throwing a full theorem prover at the problem) that can handle cases without overhead that your approach can't. In the case of pointer safety, model-checking approaches would be an obvious and well-known example.
Obviously, these alternative approaches may carry different software engineering overhead, but a claim about an abstraction being zero-cost is independent of software engineering costs (not to mention that this is an area where Rust is hardly without its own issues).
So are you suggesting that claim in such a context is false, citing BDDs as some example, or are you taking my claim to be more broad than the context warrants, and so are arguing a strawman?