Type-Safe Unions in C++ and Rust
genbattle.bitbucket.org
genbattle.bitbucket.org
It is a feature of ALGOL68, Pascal, Ada and quite some newer languages:
Rust has just managed to take all these features and put them together well, and strive to be more than a research language by working on things that would make others actually use the language.
(Of course, this particular feature is common in many, many languages)
Ha! I didn't know that. Thanks :)
I would probably restate it though. What is research vs. a product. I just read about 1nm transistors, but we're probably looking at 10 years before Intel, et al, have built all the infrastructure to reliably deliver a CPU based on it.
In the case of a language, I would say it's similar, do you have the support infrastructure in place? Rust is amazing in this regard: Cargo, crates.io, docs.rs, rustup, etc. on top of that you have at least one large company and many others pushing the language in a large and distributed product.
I would classify Rust as a production ready coding platform.
It seems very obvious now. I was thinking the purpose of the language was for performing research, but that didn't make much sense. I see now that it's the language itself that is the subject of research, not the tool. English is fun.
If you hear the term used disparagingly it's because they tend to have issues you generally wouldn't want to put up with when you're on the clock: compiler bugs, lack of error messages, large missing pieces in the standard lib, spectacularly bad performance, etc because those weren't the problems the language was meant to explore.
Writing proper and safe concurrent code in Rust still looks horrible compared to languages which supports it natively in the type system, e.g. ponylang type capabilities. You still have to manually maintain locks, and it's also much slower.
There's a safety model, but it's only best practice, not enforced by the language nor the compiler. So calling it "safe" and "truly unique" is way off. Even parrot has a better, safe and lockless threading model, which guarantees safety.
And of course the means to get rid of any abstraction and safety when required.
edit: accidentally a word
LISP-strength macros give you most of this capability.
It works fine in Ada.
Edit: Why am I downvoted for this? A language-defined concurrency model is indispensable for having safe and deadlock-free concurrency in the language (rather than in arbitrary utility libraries). That's why concurrency was explicitly included into Ada and into the additional Ravenscar profile. The rationale for this has always convinced me and it also works fine in Ada, so anybody care to elaborate what's wrong with it?
http://brinch-hansen.net/papers/
I agree it's better to have mechanisms that can be turned into a proper model. A good default, though, greatly improves consistency and reliability in real-world systems.
You ... don't. That's just the concurrency model that the abstractions in the stdlib expose, but Rust's safety is generic enough that you can use different abstractions (e.g. lockfree ones). See crossbeam for some alternative models. There are also transactional memeory impls in Rust. They still use Send and Sync for safety though. Manually maintaining locks is a feature of the concurrency library used, not the safety model.
Pony's system is actually pretty close to that of Rust. Sync is "immutable", Send is "isolated" (sort of). Of course, capabilities are different from auto traits, but the idea behind using these two capabilities for concurrency safety is similar.
(So I was wrong that Rust's concurrency safety system is unique, since Pony has something based on the same concepts)
> There's a safety model, but it's only best practice, not enforced by the language nor the compiler.
Yeah, Send and Sync are technically a part of the stdlib (and can be reimplemented outside of it, aside from a small interaction with statics -- Send/Sync are treated as special by the compiler when it comes to statics). However, it is enforced by the compiler in the sense that if you avoid best practice (using Send and Sync), you can't write parallel code without dropping to `unsafe`. If you do that you can design safe abstractions around that and use whatever concurrency enforcement you wish, though pretty much everyone sticks to Send and Sync since it works well with the rest of the language.
(Because of the statics thing, "not part of the language" is debatable, anyway)
What? How is it not enforced?
> You still have to manually maintain locks, and it's also much slower.
Slower? I don't think it can be any faster even in theory!
Smalltalk has had that since the early 1980s
how would it statically enforce the equivalent of Send and Sync constraints?
In some Smalltalks, normal execution is synchronous. Many of them also use read and write boundaries for various purposes. The former gives you Send and Sync constraints for free. The latter can be used in difficult edge cases. (Like when you're calling out to the OS.)
Uh, no, it gives you thread safety for free.
When my comment was talking about Send and Sync I was talking about the specific way Rust's typesystem enforces thread safety. I'm not saying that other languages don't, I'm saying that Rust's method of enforcing it might be one of the few unique things it does
It would be great to see how other languages have achieved a similar balance, and my impression is that Smalltalk (and like most languages) does not put nearly as much effort into controlling mutability, but maybe I'm wrong. Could you post some links/a description that explores how Smalltalk achieves a similar level of safety?
http://brinch-hansen.net/papers/1975a.pdf
http://brinch-hansen.net/papers/
His first, concurrent OS was RC 4000 in 1969. It had many mechanisms in place. He got the key parts of the safety problem figured out by 1972. His language to handle much of it statically at compile-time was done in 1975. His Boss 2 system same year used coroutines + similar concepts to run 100 activities at a time with a proof of deadlock freedom. Finally, he used Concurrent Pascal to implement Solo system which ran its processes safely without using physical, memory protection. These summaries came from "Evolution of Operating Systems" on 2nd link.
So, the stuff was well-established by the mid-70's with operating systems using it in production. Just ignored by mainstream like a lot of good stuff for various reasons. ;)
"A disk buÆer is a data structure shared by two concurrent processes. The details of how such a buÆer is constructed are irrelevant to its users. All the processes need to know is that they can send and receive data through it. If they try to operate on the buÆer in any other way it is probably either a programming mistake or an example of tricky programming. In both cases, one would like a compiler to detect such misuse of a shared data structure."
"To make this possible, we must introduce a language construct that will enable a programmer to tell a compiler how a shared data structure can be used by processes. This kind of system component is called a monitor. A monitor can synchronize concurrent processes and transmit data between them. It can also control the order in which competing processes use shared, physical resources."
Sounds like he understands the problem is concurrent processes stepping on each others toes using a shared, data structure. He has nice drawings and charts to go with it. Plus, an early model to solve it statically at compile time. Jweb_Guru noted some limitations of his method but it understands and solves the fundamental problem. Hansen's own work improved on it later plus it was obsoleted by things like Ravenscar, SCOOP and now Rust's method. Nice that he had a whole OS protected from concurrency errors at compile time in the 70's, though. :)
Hansens work formalized what I just described in terms of English, diagrams, and compiler checks. He started with sequential operations on private data in modules. He says if two or more share thd same private data they might not execute in desired order. The monitor pattern enforced user-specified order on function calls to shared data. Built-in to language & compiler.
If my description of race conditions is inaccurate or insufficient, I'd appreciate a link to one that you think is more accurate that I could use as a comparison point against the Hansen paper. Otherwise, his description of problems implementing concurrency sounds exactly like what I learned in books on multithreading, supercomputing, etc. Shared resource used in incorrect order due to concurrency.
Note: Also, his colleagues Dijkstra and Hoare were still inventing and developing formal verification at the time. Tooling sucked. Standard practice, like he did with Algol and COBOL compilers, was writing things like this in precise English with code examples or diagrams. Not sure if you were expecting a HOL model or something when you said "modern" but I figured Id mention stuff was primitive then.
A data race is when
- two threads access a single memory location,
- at least one of which is a write, and
- at least one of which has no synchronisation^
(^ synchronisation in the sense of things like atomic instructions, not necessarily full locks.)
Knowing that, Hansen starts on problem with RC4000 (1969) describing protecting communication between "processes" via message buffers, message queues, and checks performed on them to ensure validity. That and Dijkstra's critical regions are where the foundations were laid. His next step was the formalization the problem in 1972:
http://brinch-hansen.net/papers/1972a.pdf
Section's 1 and 2 cover basics of concurrent operation + race conditions. It was clear to me by the abstract but should be extra clear he's talking about them by this statement about Algorithm 1:
"The copying, output, and input of a record can now be executed concurrently. To simplify the argument, we will only consider cases in which these processes are arbitrarily interleaved but not overlapped in time. The erroneous concurrent statement can then be executed in six different ways with three possible results."
That's definitely a concurrency error. He then talks about mutual exclusion and synchronization with an await primitive. Closer to modern language but the focus on operating systems in the early 1970's means he says processes instead of threads and things like disk buffers or message queues instead of shared memory. Although his examples in 1972 paper are clearly shared memory since it's at algorithm level.
So, they discovered the problem around late 60's, implemented an early solution for sharing resources among processes in 1969, fully described race conditions + some other stuff by 1972, had a safer-by-design language to catch it at compile time by 1975, and applied that to implement a concurrent, production OS (Solo) for day-to-day use by academics by 1976.
So, race conditions were both formalized and initially solved in early to mid 1970's. I don't know how much more you need given they had an OS running 100 jobs/users at once interacting on shared resources without visible failures using their concurrency model. Mainstream OS's and apps are still having race conditions pop up on occasion. Clearly, what they were doing was addressing root cause if no race conditions occurred after a successful compile of "multiprogrammed" apps. :)
A data race is when a program may give undefined results (in the sense of undefined behaviour in C) because you've violated core language semantics. Solving "all" concurrency problems is a much broader and far more restrictive paradigm than just ensuring that a program has defined behaviour, and not having restrictions is key to systems programming. (In fact, it's not even clear to me how one can "solve" race conditions at a language level without tying into some sort of machine-readable product specification or without just removing concurrency entirely: a single piece of non-determinism may be fine in one program but bad, i.e. a race condition, in another.)
> The problem you're having is you've constrained the definition of concurrency or race conditions to only be about the language common among application programmers, esp threading
No, I'm not having any problem here: you said yourself that you're not an expert. A data race (not arbitrary race condition) only makes sense if there's shared memory and thus thread is a perfectly reasonable description (although "thread" is also often used to just mean thread of execution, not literal pthread thread). It's becoming clear that we're talking about different things since you're not in-tune with the jargon/subtle terminology.
Hmm. Ill have to look into the old stuff further to see about whether any of it, including Hansen, covers the accepted definition of data races. There's potential that Hansen's does but Im holding off until I think on it more.
Some relevant lines:
> A Concurrent Pascal compiler will check that the private data of a process only are accessed by that process. It will also check that the data structure of a class or monitor only is accessed by its procedures
is significantly less than what Rust provides, because:
> Processes cannot operate directly on shared data. They can only call monitor procedures that have access to shared data. A monitor procedure is executed as part of a calling process (just like any other procedure).
> If concurrent processes simultaneously call monitor procedures that operate on the same shared data these procedures will be executed strictly one at a time. Otherwise, the results of monitor calls would be unpredictable. This means that the machine must be able to delay processes for short periods of time until it is their turn to execute monitor procedures. We will not be concerned with how this is done, but will just notice that a monitor procedure has exclusive access to shared data while it is being executed.
Rust allows shared access to immutable data and does not require either serialization or the invocation of a virtual machine; it also allows nondeterministic operation to be used as long as it cannot cause memory unsafety.
Additionally, there are other, more basic things that the system is not capable of. For instance:
> (Strictly speaking, a compiler can only check that single monitor calls are made correctly; it cannot check sequences of monitor calls, for example whether a resource is always reserved before it is released. So one can only hope for compile time assurance of partial correctness.)
A major part of what Rust brings to the table is the ability to statically avoid problems like use after free and double free even in a concurrent setting. How would I avoid resource leaks in a system like this without a per-thread allocator (which would likely prevent sending across threads)?
Of course, it's not clear to me that this matters anyway, since I can't destroy a thread or shared data structure!
> Dynamic process deletion will certainly complicate the semantics and implementation of a programming language considerably. And since it appears to be unnecessary for a large class of real-time applications, it seems wise to exclude it altogether. So an operating system written in Concurrent Pascal will consist of a fixed number of processes, monitors, and classes. These components and their data structures will exist forever after system initialization.
I agree that people have a strong tendency to not know what past work has been done, and Concurrent Pascal is admirable, but what Rust does is not the same thing. Rust specifically tackles a lot of hard problems in concurrency that simply do not exist as long as you (1) assume away deallocation for shared data structures, and (2) serialize all access to those data structures.
(There are lots of other specific points I could go into; for instance, Concurrent Pascal apparently lacks facilities for generic programming, so I probably couldn't combine two correct concurrent data structures and expect a third correct concurrent data structure to come out. But that stuff isn't directly related to concurrency).
I'm not saying it does. The claim I replied to said preventing things like data races was done till well into the 80's. I showed systematic investigations of the problem plus a production solution had been done by mid-70's. You've nicely showed how far ahead methods like Rust got. ;)
No, it definitely didn't: it said data races as a concept seemed to not be formalised until the late 80's.
This paper introduced Monitors. It was of course hugely influential.
Mutex and condition variables, the building blocks of monitors made their way into posix threads and from there into C++11.
I believe Java is a much closer realization of Hansen model as every java object is a Monitor.
VisualWorks got the ability to make certain objects immutable sometime in the early 2000's. The VM engineers were particularly proud of that one.
That really depends on which Smalltalk you're talking about, I think. Various implementations really had different concurrency models. Some implementations used native OS threads. Others ran synchronously "inside the image" but spawned threads to interact with the OS.
Just look at the dominance of Javascript in the programming landscape, you're seeing decades of high quality executions of the language(I include community in the "execution" definition) despite it being far from the best technical language.
Eh, that's underselling Rust's contributions. Rust is more flexible than anything I know of when it comes to enforcing aliasing-xor-mutability. Cyclone for example was much more restrictive in disallowing aliasing (see Grossman's "Existential Types for Imperative Languages").
The key feature that Rust has is flow-sensitive permissions on unique loan paths, which is actually pretty novel as far as I'm aware.
> The key feature that Rust has is flow-sensitive permissions on unique loan paths, which is actually pretty novel as far as I'm aware.
Huh, right.
It is however a fine way to encourage sensible use of unions. But it's mostly just a suggestion.
Of course I implemented them in Virgil, too. (shameless plug: https://github.com/titzer/virgil)
Algebraic datatypes with (even just basic) pattern matching (preferably with compile-time exhaustiveness checking) are things I've wanted in C++ ten years ago. This gets me part of the way there, at least. :)
> I’m aware the idea for type-safe unions isn’t unique or original to Rust, but it’s the first language I’ve experimented with that has made them a first-class feature.
boost::variant however lacks a nice visit method that takes lambdas, instead requiring the user to create visitor classes. This verbosity may be part of the reason it wasn't adopted in mass, in spite of its advantages in terms of type safety.
I have a big project that uses boost::variant. The runtime performance may be fine, but I swear that just compiling the header took about 5 seconds.
Pre-C++-11 fake variadic templates are just painful.
(IMHO two of the major missing features in Rust that are really need are integer generics and varidic generics. Without integer generics, arrays over 32 elements don't work correctly, and that's really annoying sometimes.)
Sometimes C++ feels like the high level languages assembler.
The bad thing is that they suck.
In the next 10 years C++ might even grow another leg and incorporate them in the basic language (together with proper pattern matching).
It's good that C++ has this, but it hinders some programming patterns. Of course, C++ has other programming patterns that it's great at to compensate :)
One year later: i see the template library [1] but i don't see the analysis tool. Does anybody know what happened with this initiative?
Other vendors might eventually add support as well.
If you don't want to wait, want to experiment with something else, learn a new language, etc., Rust is awesome.
Obviously the counter argument to this is, "but there's 30+ years of C++ in production", but be honest, who actually wants to work on a 30 year old codebase?
It's certainly pleasing to be able to sit down and write something from scratch or nearly from scratch. But it can be equally pleasing to extend a multi-million line codebase to do something new, or to enable the codebase as a whole to do something new/better.
Why do I have to wait for every compiler on every system I want to build on to update to some future standard when things could be done now across the board in many cases?
Don't compile to C.
First, there are cases where compiling other languages to C or C++ is better than via LLVM; interoperability and portability are two (yes, C and C++ are more portable than LLVM).
Second, I'm not really talking about compiling some wildly different language to C++. I'm talking about some simple syntactic sugar. The same syntactic sugar that would be in an existing C or C++ compiler's front end, except instead of adding it to all the frontends in the world and waiting years, I'd like to implement it just once and now.
People bring up obscure platforms (though, interestingly, I can't recall anybody actually naming one of those platforms) all the time as motivation for compiling to C. But if you really need to do that, you can always revive the LLVM C backend. The fact that nobody has bothered to revive it and keep it up to date enough to be merged into LLVM proper, to me, is a strong indication that few people need support for these obscure platforms.
In your opinion. This isn't a fact. For example, I know first hand of code that has to compile with compilers that are not in the set { gcc, clang, msvc }. What do I do then? (Oh, and those compilers are closed-source).
> You'll end up wanting to just use clang's front end to help you
Probably, although there are other options too
> and at that point why not just modify clang itself?
The changes I make, if useful to the community, would probably end up back in clang. But they would also remain a separate tool, because of all those other pesky compilers I work with.
> you can always revive the LLVM C backend
I'm not sure how that helps me; not only does it seem a terribly roundabout way to get what I'm looking for (instead of sugar -> c++ -> my c++ compiler, you are proposing sugar -> clang -> llvm -> c -> my c compiler), but I don't think objects produced by that pipeline would link with C++ objects produced from my native compilers, among other issues.
> The fact that nobody has bothered to revive it and keep it up to date enough to be merged into LLVM proper, to me, is a strong indication that few people need support for these obscure platforms.
Or, is it evidence that people using more obscure platforms (we're talking fortune 500 companies here) stick to languages that exist on their platforms for various reasons?
C and C++ are more portable then their own compiler's backend? LLVM is clang/clang++'s assembler
I get what your saying if you compile to C it can be more portable. But then you need to compile to some C standard.
K&R C? ANSI C? C90? C99? C11? Why not have a compiler flag for each? What about embedded C? What companies embedded C?
I can repeat this for C++
Compiling to C/C++ in a platform and standard agnostic way is impossible.
Lots of languages can give you a dump in 1 standard of C. You can't specify what C standard, or what platform to output outside of ARM/x64. NIM, Cython, C++ (via clang), [Ada/Cobalt/Fortran]-GCC, Perl, Agol, Oracle PL/SQL only support x86_64 and ARM.
Your argument was
interoperability and portability
2) You have no portability gain as you have 3 choices x86, x64, and ARM. All of which Rust already supports.
Also your main request
$ rustc your_program.rs --emit llvm-ir
$ llc -march=c -o your_program.c your_program.ll
$ rustc your_program.rs --emit llvm-ir
$ llc -march=cpp -o your_program.cpp your_program.llRust is not interoperable with C++ as far as I know, and even if it was, I'm not interested in Rust for this discussion for reasons I've mentioned elsewhere.
The LLVM C backend was removed. Julia devs have a version that supports the LLVM bit code that they require, but I believe it is not everything LLVM can produce.
I was under the impression that march=cpp output C++ code that rebuilt the IR, not implemented the source program.
Thanks for the advice, although none of it really applies to what I'm suggesting.
kind of paradox to say that
Mine was worded as a polite request and his was worded as a command.
(I want it to compile to C++ so I can use the compilers I use and it can interoperate with the C++ code it has to interoperate with and C++ programmers that work on this code wouldn't have to learn more than a few extras that might make their lives easier).
You can define Swift enumerations to store associated values of any given type, and the value types can be different for each case of the enumeration if needed. Enumerations similar to these are known as discriminated unions, tagged unions, or variants in other programming languages. [1]
Haskell and other ML family languages also have similar constructs, although these are usually modelled using "Algebraic Data Types", or "sum types". [2] [3]
[1]: https://developer.apple.com/library/content/documentation/Sw...
[2]: https://wiki.haskell.org/Algebraic_data_type
[3]: https://www.schoolofhaskell.com/school/to-infinity-and-beyon...
In this case, when I first encountered Rust's enums the first thing that came to mind is the fact that C and C++ both offer the ability to support tagged-unions, but certainly not as a first-class entity and definitely with a lot more cruft, with or without safety checks.
For me the jury is still out on where the best "fit" for Rust is. I really appreciate the enforced safety of Rust for higher-level systems applications programming. I'm not convinced yet it won't just get in the way pointlessly for much lower level programming (especially embedded). Perhaps that's just my relative novice understanding of Rust, though.
Even after more than a year of learning the language I do find that some things take me longer to build, but the end product is far better.
What I said is that it might take you longer to write it in Rust, than something similar in C/C++, but you won't have some of the guarantees you get from the Rust semantics. So the tradeoff is up to you; write code faster, or write code safer.
The real tragedy of being human is that no amount of intelligence can save you from being religious.
For example:
class State { ... }; class Connected : public State { ... };
std::unique_ptr<State> state;
Apparently the majority of CS degrees don't teach history of programming languages.
On my language design lectures in the mid-90's we had to learn all major ones, all the way back to Fortran.
Tagged unions are prevalent in so many languages that the designers of both C++17 and Rust are bound to know about them. This is "borrowing" (or "stealing" :p).
The original Rust was ML-like and had an OCaml compiler, so Rust's enums definitely descended from those. I can't talk for C++ for sure, but like I said it's common in so many languages that they're bound to have derived inspiration from them.
Maybe this has been built into one of the newer Pascal descendants, but it hasn't been around for years and years. And embedded C programmers have been using these kinds of "unsafe" discriminated unions for years.
That said, I do think Ada has had these kinds of actually typesafe variant records for quite a while. But again, Rust isn't making any claims to innovation. Even the language name ("Rust"), is a reference to the language being based on rusty old best practices.