Live data from Hacker News

Type-Safe Unions in C++ and Rust

genbattle.bitbucket.org

131–140 of 140 posts

Re: Type-Safe Unions in C++ and Rust

#131
post #110

Earlier quoted context omitted.

None of that looks like a formalisation or even a description of a data race, at least not in the modern sense.

Im not a concurrency expert. Just had basic explanations and training common with other developers. How it was explained to me was two or more tasks trying to simultaneously access a shared resource for reading or writing. These accesses might not happen in the desired order, causing incorrectness. Then there were lock-related issues on top of that. Hansens work formalized what I just described in terms of English, d…

I'm not looking for a formal mathematical model or anything, just a precise plain English description of a data race (not a race condition), e.g. like the following:

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.)

Re: Type-Safe Unions in C++ and Rust

#132

Earlier quoted context omitted.

Please don't tell others what not to do. 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++ comp…

> Please don't tell others what not to do. kind of paradox to say that

Is it?

Mine was worded as a polite request and his was worded as a command.

Re: Type-Safe Unions in C++ and Rust

#133
post #131

Earlier quoted context omitted.

Im not a concurrency expert. Just had basic explanations and training common with other developers. How it was explained to me was two or more tasks trying to simultaneously access a shared resource for reading or writing. These accesses might not happen in the desired order, causing incorrectness. Then there were lock-related issues on top of that. Hansens work formalized what I just described in terms of English, d…

I'm not looking for a formal mathematical model or anything, just a precise plain English description of a data race ( not a race condition), e.g. like the following: 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.)

Alright that's clear. It's also in the first paper I gave you in the first illustration. 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. Concurrency is broader than that: it can apply to processes, threads, systems, protocols, or even hardware circuits. All that is required is two or more active things working with a shared resource in a way where operations might get interleaved and out of order in a way that makes computation incorrect.

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. :)

Re: Type-Safe Unions in C++ and Rust

#134
post #131

Earlier quoted context omitted.

I'm not looking for a formal mathematical model or anything, just a precise plain English description of a data race ( not a race condition), e.g. like the following: 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.)

Alright that's clear. It's also in the first paper I gave you in the first illustration. 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. Concurrency is broader than that: it can apply to processes, threads, systems, protocols, or even hardware circuits. All that is required is two or mor…

[deleted]

Re: Type-Safe Unions in C++ and Rust

#135
post #71

Earlier quoted context omitted.

Like steveklabnik, I'm extremely curious to hear more about how Smalltalk's concurrency model is just like Rust's. The latter is a fairly flexible model to defend against data races (which seems to be a concept only really formalised in the late 80s) that puts most of the power in the programmer's hands (i.e. no need for compiler-inserted locks on every object, etc.) that comes from a finely balanced combination of t…

"which seems to be a concept only really formalised in the late 80s" 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…

> Just ignored by mainstream like a lot of good stuff for various reasons. ;)

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.

Re: Type-Safe Unions in C++ and Rust

#136

Earlier quoted context omitted.

"which seems to be a concept only really formalised in the late 80s" 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…

> Just ignored by mainstream like a lot of good stuff for various reasons. ;) 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.

Good point. I should qualify that statement better. Hansen's model was statically guaranteeing freedom from issues at compile time. There were projects aiming at that which could've implemented a similar model but didn't. More work could've gone into eliminating its limitations, etc. The Ada and Eiffel people carried the torch, though, with interesting progress. Now Rust is. Ada folks aren't resting, though, as ParaSail is pretty neat.

Re: Type-Safe Unions in C++ and Rust

#137
post #131

Earlier quoted context omitted.

I'm not looking for a formal mathematical model or anything, just a precise plain English description of a data race ( not a race condition), e.g. like the following: 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.)

Alright that's clear. It's also in the first paper I gave you in the first illustration. 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. Concurrency is broader than that: it can apply to processes, threads, systems, protocols, or even hardware circuits. All that is required is two or mor…

You're still talking about "race conditions" and "concurrency errors", whereas I am talking specifically about data races not arbitrary race conditions or concurrency errors. I don't see how the first illustration demonstrates anything about data races, nor how the rest of your comment applies to this: a data race isn't just plain old interleaving of executions/possible results.

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.

Re: Type-Safe Unions in C++ and Rust

#138
post #137

Earlier quoted context omitted.

Alright that's clear. It's also in the first paper I gave you in the first illustration. 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. Concurrency is broader than that: it can apply to processes, threads, systems, protocols, or even hardware circuits. All that is required is two or mor…

You're still talking about "race conditions" and "concurrency errors", whereas I am talking specifically about data races not arbitrary race conditions or concurrency errors . I don't see how the first illustration demonstrates anything about data races, nor how the rest of your comment applies to this: a data race isn't just plain old interleaving of executions/possible results. A data race is when a program may giv…

That is in fact where dispute came from: race conditions vs data races. I saw race and concurrency thinking you were talking about race conditions. My mistake.

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.

Re: Type-Safe Unions in C++ and Rust

#139

Earlier quoted context omitted.

IIRC Stroustrup mentions a desire for features such as these for versions of C++ after C++17.

C++11 c++14 c++17 does that mean that we might see a match statement in c++20? It would be a significant addition - similar in complexity to anonymous functions.

i remember that Bjarne Stroustrup held a talk in cppcon15 where he talked a lot about the GSL library [1] - it would add type annotations that can be checked by a tool, so as to check for potential memory problems (to me that sounds like a poor man's borrow checker).

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?

[1] https://www.youtube.com/watch?v=1OEu9C51K2A

[2] https://github.com/Microsoft/GSL

Re: Type-Safe Unions in C++ and Rust

#140

Earlier quoted context omitted.

C++11 c++14 c++17 does that mean that we might see a match statement in c++20? It would be a significant addition - similar in complexity to anonymous functions.

i remember that Bjarne Stroustrup held a talk in cppcon15 where he talked a lot about the GSL library [1] - it would add type annotations that can be checked by a tool, so as to check for potential memory problems (to me that sounds like a poor man's borrow checker). 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? [1] https://www.…

The tools are called clang tidy and Visual Studio 2015 Update 3.

Other vendors might eventually add support as well.

Post reply on HN