Ownership and Borrowing in D
dlang.org
dlang.org
1. What should I do when I want to make a data structure like a doubly linked list or a graph - ie one where multiple pointers point to the same object?
2. Memory is only one kind of resource where ownership needs to be tracked. Others include file handles, network sockets etc. Can you comment on whether the OB mechanism solves the problem in general, or is mainly for memory tracking?
2. It's a general solution (not limited to memory).
https://rust-unofficial.github.io/too-many-lists/
I propose doing anything super hard and rare outside the general model. Make the doubly-linked list in whatever tool supports easy verification. Things like Why3 and solvers for separation logic. Run that object code through lots of testing with runtime checks for the specified behavior. If it passes, it's probably earned the right to be wrapped for use in the memory-safe code.
This use case is also why I prefer more research funding to go to verified solvers than to manually-verified algorithms. They'll get more real-world use on hard problems. Well, that and test generators. They complement each other. The testing tools are more cost-effective, too.
These languages are like horses running on a straight line towards maximum complexity. It is just that C++ is at the front right now, but no horse has any inclination of stopping.
The rest comes from Limbo (Inferno's userspace language).
Unfortunately it also left a couple of other nice things from those languages.
EDIT: Scheme too, at least up to R5RS.
It may not seem like a big difference, but it becomes more apparent when you consider how different all the Pascal dialects that are out there - some even from Niklaus Wirth himself - are.
Also IMO languages should not break backwards compatibility.
Also I doubt he would bother to any further updates to Oberon-07 (2016 rev). Most likely busy with other matters nowadays.
For a long time I've wanted a language that I could use with just a text editor and the command prompt or terminal.
I've been able to get programs to easily compile on both my Linux home and windows work machine without any complex install magic as it should be in my opinion. The programs produced were binary executables and tiny to boot (especially Windows where HelloWorld was ~367 KB iirc and ~1.1 MB on Ubuntu).
It is nice to not need an in-depth understanding of the JVM or CLR. The hardest part for me (I usually favor languages like Python) is not having a REPL, but I'll live.
The one place where I could use some help (similar to most of the advanced languages... although Rust is good here) is in the documentation which is more meant for power users than onboarding new folks. Compare and contrast the Nim section on types with D's classes/structs/unions. The D documentation is more like a reference manual and Nim is more tutorial. I think I'll try Andrei's book and see if that gets me far enough to where the technical doc becomes straightforward.
On another note, I see D has some functional programming support. If possible, I'd like to avoid having to model my own domain logic with OO classes. Is the proper way to do this with structs and the stdlib's map!, fold!, & filter! constructs.
Sorry for rambling!
- Zero-cost abstractions: Yes!
- Move semantics: Yes!
- Guaranteed memory safety: Yes! (in code marked with the appropriate annotations)
- Threads without data races: Yes!
- Trait-based generics: No!
- Pattern matching: No! (Although like C++, in can be done as a library: https://code.dlang.org/packages/sumtype)
- Type inference: Yes! (Plus unlike Rust, you can also mark function return types auto, and let them be inferred too).
- Minimal runtime: Yes! (the GC could be disabled if using exclusively borrow-checked code)
- Efficient C bindings: Yes!
D also brings some features of its own to the table that Rust doesn't yet match.
- Higher-kinded types (template template params): it's possible to implement Haskell-style monads etc. in D, if for some reason you felt the need.
- Pure functions: these allow you to statically guarantee that a piece of code doesn't perform any IO and is a completely deterministic function of its inputs. This makes reasoning about a large codebase much easier, compared to Rust where there's no way to statically guarantee a function isn't doing any IO.
- Fast compile times: the reference DMD compiler is almost as fast as the Go compiler, at least for code that doesn't do a bunch of compile-time calculation.
- Compile-time compute: Rust now has constfn, but that still only supports a limited subset of the language. D allows almost the entire language to be used at compile time.
- Variadic templates: Something C++ users might miss when coming to Rust, they allow for the creation of things like tensors of arbitrary dimension (myTensor<6, 3, 2, 5, 6, 20>) on which operations are checked at compile time to ensure sizes are compatible (so it's a compiler error if you try to multiply two tensors of the wrong size or wrong number of dimensions).
D’s concept of ownership (for now) doesn’t seem to have any plan to support partially moved structs, which are a major ergonomic feature.
D has organically grown just about every interesting feature ever conceived, but I would much rather use a purpose-built language, which is what Rust feels like.
I don’t want a C++ that’s better at being C++ than C++ is. I really enjoy how consistent and expressive Rust is. I also appreciate how intentional Go is about being Go.
A lot of people enjoy C++, and some people enjoy D. I enjoyed C++ back when Rust wasn’t an option... then something better came along. D and C++ try to be everything to everyone. I like D better than C++... but I have seen no compelling reason to trade Rust for D.
Variadic templates are much better expressed by either tuples or const generics. A fixed length array of a constant generic length is the Rustic solution to tensor-like problems, and it is being rigorously developed.
Arbitrary compile time computation should be separated from the body of the program. If you need to download files or read the file tree at compile time, that should happen in a build script. Rust provides build.rs for that. Precomputing values without I/O is conceptually just an advanced kind of compiler optimization, and that’s why Rust is basically seeking to make const fns only pure functions.
The fast compile times are a double edged sword, since those binaries are noticeably slower than Rust binaries, from what I’ve seen. I hope that Rust will one day have a much faster compiler for development builds.
I also think every sign is showing that Rust is starting to get some real traction, so I don’t think I’m alone in these opinions... but they are mostly just that: opinions. You’re welcome to your own.
In the article linked by this discussion, the author specifically mentions how fields can’t be moved out in D’s implementation.
Option is the correct approach for dealing with information that might be missing, but that’s not really related to partially moved structs.
Structs document what is available in a given value, to both the compiler and to you. If that’s not convincing, then I’m not going to try more here... it’s off topic. But I will say you can use maps in Rust or other statically typed languages. They’re just not meant to be an alternative to well-defined structs.
One thing with Rust is that it is really focused on performance and safety. It also cares about ergonomics, but not over performance and safety. Unfortunately, type explosion does make for faster code that can be validated more easily for safety by the compiler. That said, Rust has good support for vectors, those are used a lot, but are homogeneous. It also supports tuples with nice literal syntax and pattern matching on them. While it favours structs over maps, they are pretty lightweight compared to objects, so very small syntax to define them, you can create one out of another, and have a nice literal syntax to create them. Still, this is not the magical world of dynamic data-structures, so don't try and think you can just map/reduce over your structs and tuples, compose and restructure them freely, print out their content, or merge and split them, etc..
It seems "partial move" actually means "partial transfer".
Yup
In rust, you can move, copy or borrow a value.
Move - means that the responsibility of freeing the allocated memory is moving to someone else. Rust says the ownership has moved.
Copy - means that the full value is copied, and a copy is passed, thus now you have two instances of the value, and each can act independently.
Borrow - means that the access permissions to the value are temporarily transferred to something else, but will come back when done, and the responsibility of freeing the memory is still up to the owner (lender).
That's why it is called "partial move", cause it's using Rust's terminology. Transfer isn't in the Rust lexicon, so it wouldn't be as appropriate.
This is an area we'll have to agree to strongly disagree. For me having support directly in the language is a huge improvement in ergonomics, compared to having to run a separate script. Compare e.g. generics in Go1 (which can only be done with separate build scripts at compile time) vs in any other language that has built-in generics. Also consider F# type providers, which guarantee at compile time the correctness of code querying a database (generate the schema/structs by querying the database at compile time). Certainly the same thing could be achieved by running a separate script as part of the build process, but I've never seen a language actually implement that, probably because it'd be much more painful.
>The fast compile times are a double edged sword, since those binaries are noticeably slower than Rust binaries, from what I’ve seen.
Note that D also has an LLVM-based compiler backend that is slower to compile but produces much faster code, which can be used for release builds.
As far as your comment about databases, you should look at Diesel. It handles this very nicely in Rust, so... that’s not a problem at all.
> Note that D also has an LLVM-based compiler backend that is slower to compile but produces much faster code, which can be used for release builds.
Is it compatible with 100% of the code that the current DMD release is compatible with? That’s all I ask for in alternate compiler implementations... but it seems like a lot, sometimes.
Go actually has a built-in "Go generate" command that will look for magic "//go:generate <command>" comments in the code and automatically run code generation based on them, although I'm not sure how ergonomic it is.
>It just allows you to logically separate build time I/O from runtime I/O, which I find is nice for reproducibility of builds and maintainability of code.
This is a reasonable argument. For what it's worth, compile-time IO in D is more limited than in e.g. Haskell, as it seems the only compile-time IO D supports is reading files (or at least I can't find any documentation suggesting otherwise). Most of the power of its compile-time code execution comes from non-IO code (e.g. generating an optimal lookup table for a dictionary of values known at compile time, hard-coded in the code, or automatically generating fast JSON serialisation/deserialisation code for a struct without need for macros). While Rust also plans to support this, full support could be years away, while D supports it now.
>As far as your comment about databases, you should look at Diesel. It handles this very nicely in Rust, so... that’s not a problem at all.
Definitely shows it's possible to get the benefit of type providers without language support for them, hats off to the Diesel team!
>Is it compatible with 100% of the code that the current DMD release is compatible with? That’s all I ask for in alternate compiler implementations... but it seems like a lot, sometimes.
It's eventually compatible, sometimes lagging a few versions behind. Using LDC for release builds is somewhat comparable to only using stable Rust for release builds, except D has a slower pace of new feature additions than Rust since it already has so many features.
This is to prevent the use of the D compiler as a malware target by sending it specially crafted source code to compile.
But it's still not run automatically at build time, you have to go out of your way to run `go generate`, which isn't gonna happen if you, as is customary, fetch and build third-party code with `go get`.
Except that the convention is to check in the files generated by go generate, so in practice, it's not actually a problem.
You can get the same effect if you really need it with a pre-build command with dub (the package manager/build tool, and with other build tools such as reggae), but compilation is supposed to not change the state of the system other than produce build artefacts, you can read files at compile time with `import("filename")`, but you can't write to files, or open sockets etc.
Things like mixing in a data file is incredibly useful and not something I would want to use a rebuild step for at all.
> Is it compatible with 100% of the code that the current DMD release is compatible with? That’s all I ask for in alternate compiler implementations... but it seems like a lot, sometimes.
Not strictly.
It is usually pickier about what is deems valid (which is usually corner cases that DMD really ought to reject). They share the same frontend so there is very little difference.
It has some of its own bugs, though nothing too major.
It generally has way less bugs both due to its release cycle being based off of DMD stable and thus it lags one cycle behind (~six weeks), so new features aren't available immediately, and having all the backend and optimisation handled by LLVM, though we occasionally hit LLVM bugs that clang for some reason does not seem to trigger.
(I develop both DMD and LDC (the LLVM based D compiler))
It’s not directly part of the const function, but rust has compiler built-ins to import files as values as compile time, which makes it easy to declare global static variables that contain that data.
This is different from being able to walk a directory and read random files.
https://doc.rust-lang.org/std/macro.include_str.html
https://doc.rust-lang.org/std/macro.include_bytes.html
> They share the same frontend so there is very little difference.
That’s excellent.
D doesn't allow you to do that either. You have to specify what files you are importing via a compiler switch: https://dlang.org/spec/expression.html#import_expressions
For practical purposes: yes. We use DMD for development and LDC for release builds, and it works really well in tandem.
Well, the alternative is to learn an actual dozen of language - one for the high-performance simd part of your app, one for GUI layouts, one for writing parsers, one with strong typing semantics for your domain objects (but how are you going to keep them aboard in the interfaces with your other languages !), one for network communication...
I much prefer (as a C++ dev, but the same applies to D), the ability of the language to make eDSL adapted to each tasks.
> Well, the alternative is to learn an actual dozen of language
That’s a false dichotomy.
I personally find Rust macro system infinitely easier to use than D mixins as well. In D, I need to learn a new pseudo-language to work with mixins, but Rust macros are just normal Rust code that gets executed at compile-time on other Rust code, and this code can do anything that any running Rust program can do.
The structure of the 2 fundamental Rust libraries around Rust macros are super intuitive to me (maybe its the CS background?). `syn` is a Rust parser from tokens -> AST, and it supports doing AST->AST folds and other common operations. And `quote` gives you semi-quoting.
With `syn+quote` most macros end up as 10 liners. Tokens->AST->AST fold->Quote->Tokens.
Rust procedural macros are like external tools, manipulating the AST as a structure. In D, compile time code is seamlessly interleaved with other code – you just have `static if`, `static foreach` etc. in your code.
I'm not sure what you mean by "new pseudo-language to work with mixins". The term "mixin" is unfortunately overloaded: the `mixin()` call just splices a string into the code, while `template mixin` is a way to expand a template where you want it. Neither introduces new complex structures.
Isn't viewing them as like external tools just a C centric view, based on C's (and C++'s) capabilities? Didn't Lisp have macros that manipulated the language as an AST prior to C even existing, inside the language?
If you look at the API https://blog.rust-lang.org/2018/12/21/Procedural-Macros-in-R...
it works on the level of raw tokens, not even the AST. So you have to construct your own AST via the parser if you want to manipulate AST.
Common wisdom is to leave macros for conditional execution, legacy code and the few cases that still aren't fully designed, namely reflection and metaclasses.
I would say that this is actually almost always preferable, for two reasons:
1. I believe it's generally good for programmers to know multiple languages, to be exposed to different ideas, ecosystems etc. This broadens worldviews, makes you think outside the box more often, etc.
2. Each of those languages will probably be better at what they do than D's subset. For example, D's GC isn't really one of the best ones out there. Its pure isn't the same thing as FP pure. Its move semantics is crap compared to Rust (probably even C++ does them better). The quality of the borrow-checking remains to be seen but frankly I'm skeptical, it'll probably follow the same pattern as the other features.
Here's some code that initializes an array at compile time with a non-trivial computation:
https://github.com/dlang/dmd/blob/master/src/dmd/backend/var...
This used to be initialized by a separate program that generated some .d files. It was nice to get rid of that. Even better, if you check the generated object file, there's no trace of the code used to generate the array - just the data for the array.
I agree that generating an array at compile time is perfectly fine. I was saying that I/O should be restricted in compile-time computation, which the person I was responding to made me believe was entirely unrestricted in compile-time computation in D.
It is, from the very core, a way simpler language than C++. I'd argue it's simpler than Rust, even. IMO acknowledging a few function attributes is way simpler than learning all the flairs of ownership and lifetimes.
As for metaprogramming, I love D's introspection capabilities, while I kind of want Rust's ability to create unquoted DSL.
The only "non-uniform" part of D that I can think of is the oddness of `shared`, and a few outdated stdlib modules. Everything else (betterC, pure, live, etc.) is just a subset of a powerful, coherent multi-paradigm language.
Because the templates aren't typed at all. I'm not sure you can call untyped templates "Haskell-style".
Even without that, the key thing is it's still possible to implement monads in the C++ style (https://stackoverflow.com/a/2565191/2553416), whereas it's impossible to write code to do the same thing in current Rust. It just gives much worse compiler errors if you use it wrong compared to if the language had built in type-classes / traits.
Also, there is the "higher" crate for higher-kinded types if you need them, so it is possible to write a monad typeclass in Rust. It's not exactly something you'd want to use, though.
That would be less helpful in C++/D because their compilers don't do Hindley-Milner style bidirectional inference, so even if they had typed generics they wouldn't necessarily be able to do that inference. But I suppose that's an argument in favour of Rust, stronger type inference.
>It's not exactly something you'd want to use, though.
Ergonomic HKT can make writing various kinds of utilities easier. E.g. imagine I want to write a function Singleton that takes a collection C (vector, list, stream...) and an item of type T, and returns C<T>, a collection containing a single instance of that type. I can write that in Haskell, D or C++, but not in Rust. Or perhaps more usefully, a function Fill, that returns a container C containing n items of type T. For Rust it seems I'd need to write a separate implementation of Fill for each container type, I couldn't write one parameterised over any C?
Here is an implementation: https://play.rust-lang.org/?version=stable&mode=release&edit...
Fill is also possible, using the same trait and iterators.
It goes completely against the most (perhaps) fundamental part of C++ philosophy of overloading functions on argument types.
Really? So if a thread passes a pointer to an object to another thread which frees it, the sending thread can no longer reference it? Genuine qn.
Of course this assumes all code in these threads use the ownership+borrowing mode.
Is this actually true? As far as I know D's pure isn't the same as eg. Haskell pure, it only prevents modifications of global state, but you can still touch data referenced by arguments. I haven't done much D though so I'm not sure what the semantics really are...
Ironically, sometimes people complain that the purity checks are too stringent :-)
One thing interesting about pure functions in D is the purity restrictions can be relaxed by using a `debug` prefix:
pure int test(int i) {
printf("%d\n", i); // error, printf isn't pure
debug printf("%d\n", i); // ok
return i;
}
Two memory safety related things to consider. Rust needs unsafe code to do these things.
1) Backpointers. Rust's ownership system doesn't allow backpointers, at least not without reference counts. So some standard data structures, such as doubly linked lists and various types of trees, can't be coded in safe Rust.
A backpointer is defined by two objects which have an invariant locking them together. If you could talk about a backpointer in the language, and tell the compiler where its forward pointer is, you could enforce the necessary invariants. If A contains a pointer to B, B's backpointer must point to A. Any code which modifies either of those pointers must maintain the consistency of that relationship. That's checkable at compile time.
This fits well with ownership. A owns B. B's backpointer is a slave. All that's needed is type syntax which says "backpointer b.reff always points to my owner."
There are lots of interesting cases to be worked out, especially around destructors. Those are worth checking at compile time, because people get them wrong. It's really nice if you can be sure that a data structure always tears itself down cleanly when you drop the link to its root.
2) Partial initialization. Collection classes which allow growth are hard to do in safe code, because they require arrays which are partially initialized. It should be possible to talk about partially initialized arrays in the language. Maybe some predicate such as "valid(tab,n,m)" indicating that array tab is valid from n to m inclusive. You can't access an element outside the n..m range. The checker for this needs to know some simple theorems, like "valid(tab,n,m) and valid(tab,m+1,m+1) implies valid(tab,n,m+1)". Then it can track through a loop and verify that the array is initialized for the given range.
Somebody will complain that they want sparsely initialized arrays containing types that really need initialization. Tell them no.
I had to deal with this once writing a 3D collision detection system. Objects were convex hulls, with vertices, edges, and faces, all pointing to each other. I had an implementation in C to look at, and it was a mess. Ownership was so tangled that they couldn't delete objects.
So I rewrote it in C++, with each object having collections of vertices, edges, and faces. All links between them were indices, not pointers. Lots of asserts to validate all the consistency rules. Easy to delete, and much better cache coherence. Chasing pointers to tiny objects all over memory belongs to the era when cache misses didn't dominate performance.
So that's the answer. Some data structures are too complex for ownership semantics. So do them another way and have all the parts be owned by some master object.
That can be done with a Vec in Rust (n is vec.len() and m is vec.capacity()).
What in particular do you think would be impossible in C++ for legacy reasons?
From a very high level it seems to me that all the necessary ingredients of this solution are available in C++ (> C++11) as well. There are pointers, smart pointers, references, constness and move semantics for the ownership and borrowing. There are [[attributes]] for the method-selective opt-in.
There is of course always the argument of not making C++ compilers even more complex. But is there some actual technical limitation in fitting the same idea into C++?
So unless you get the buy-in from the whole team, it hardly works across big projects.
The problem, as I see it, is going against the grain of the scope, a problem faced by iterators. For example, consider
for (p = f(s); p; p = p.next) {}
In general, I am saying that returning a non-owned pointer from a function is common, and required. Am I wrong in this assumption? If not, is there an alternate architecture to get around this problem? Note that marking the pointer as const is not an option.
But with the (d) compiler helping enforce correctness?
I am a bit uncomfortable with not being able to move a pointer out of a structure, but it may be a restriction that's worth it; I can't think of a counterexample off the top of my head.
Speaking as someone who often chooses the bitter path (because that's how I like it), this is an honest look at the state of things that I rarely find in articles about programming.
For example, i would like to declare a buffer on the stack, read some data into it, make const pointers into the buffer, put those pointers in heap-allocated structs, put those structs in a vector, and do some manipulation. As long as all the heap-allocated structs expire before i return from the function where the buffer was declared, this is entirely safe, but if they escape, i'm in trouble.
It already does. If you compile with the -dip1000 switch, you'll be unable to escape references to the stack for @safe code.
One of the key points here:
> This means that [Ownership/Borrowing] can be added to D code incrementally, as needed, and as time and resources permit. It becomes possible to add OB while, and this is critical, keeping your project in a fully functioning, tested, and releasable state. It’s mechanically auditable how much of the project is memory safe in this manner.
You can't, you have to trust the user. That's why one tries to minimize calling non-@live code.
For example (pseudocode):
void f(shared_ptr<Foo> a, shared_ptr<Foo> b) {
g(&mut *a.field, &mut *b.field);
}
The short of it is that the compiler will enforce that the same pointer is not provided to function more then once at the call site.
Can any of the const pointers outlive the original mutable pointer?
I would guess not, because you're not allowed to let an owning pointer fall out of scope, and you can't pass the owning pointer to a freeing function while the const pointers are alive.
So is there any way to start with only a mutable pointer, and end up with only a const pointer? Say i am gradually building up some object, i want to use a mutable pointer to do that, but once i'm one, i want it effectively frozen, with only a const pointer to it.
I was coming from a Rust mindset, where ownership and mutability are somewhat separated. Although you can't own an object through an immutable reference, you can own one through an immutable binding. But i am slowly learning that D's model is sufficiently different that there isn't a useful comparison here.