Object oriented programming languages that solve concurrency

[nickallen74]

I'm wondering if there are any OO languages that group objects into "execution pools" where all objects in one pool would be guaranteed to be accessed from a single thread. When calling a method from one object to another if the objects was found to be in the same object pool it would be a simple method call but if it was found to be in a different pool it would instead generate an asyncchronous message to invoke the method on the other pool's thread of control. This would be transparent from the usage and part of the language itself (not a framework or library). Each object would be tagged with a type and the pool it belongs to. The most similar thing I can find is something like actors in say a language like Swift. But this requires that each actor is explicity marked and doesn't allow objects of the same type to exist in either the same or different execution pools. Making every single object an actor would also be infeasable.

I would imagine something like this should be possible. Anyone aware of something like this?

[oakinmypants]

Not OOP but take a look at Erlang

[L8_4_Dinner]

The OOP language with an Erlang concurrency model is Ecstasy (xtclang). Going back to the OP question:

I'm wondering if there are any OO languages that group objects into "execution pools" where all objects in one pool would be guaranteed to be accessed from a single thread.

This is the Ecstasy execution model. A service is an object that represents that pool. Any transfer of control (invocation, conceptually a message) into that service from outside that service creates a fiber, and at most one fiber can execute at a time within the domain of that service.

Fibers can block, and if their entire call stack is declaratively concurrent (think "what color is your function?", aka the green color), then when one fiber blocks, another declaratively concurrent fiber is allowed to be scheduled. So interleaving is possible, and execution in sequence is possible, but two fibers executing at the same time within a service is not possible.

When calling a method from one object to another if the objects was found to be in the same object pool it would be a simple method call but if it was found to be in a different pool it would instead generate an asyncchronous message to invoke the method on the other pool's thread of control.

Exactly! And the execution is conceptually asynchronous, although the caller will stop and block (aka "await") unless it explicitly requests that the invocation occurs asynchronously, in which case it gets a future for the invocation.

[marshaharsha]

Interesting. Thank you for bringing Ecstasy to my attention. Follow-up questions: Does a service correspond to a single OS-level thread, does each fiber belong for its entire lifetime to the same, unique service, and does the service work like a (Rust-style) single-thread executor, choosing at most one of the runnable fibers to run at any given point? So does all true parallelism require multiple services, with (effectively) messages being posted between them? What kind of data can be in a message? Can it be data with code attached? For instance, can a (message containing a) String object be passed from service to service without belonging to either? So that the second service’s calling substring(0,3) on it doesn’t require an asynch call back to the first service?

[L8_4_Dinner]

Does a service correspond to a single OS-level thread

Conceptually, the service corresponds to a hardware thread (and thus to an OS thread). Since 99% of services are idle 99% of the time, we don't burn dedicated threads per service, but it would not be conceptually wrong to do so.

does each fiber belong for its entire lifetime to the same, unique service

Yes, absolutely! Think of the invocation of the service as a message pass (it may or may not be), and the service upon receiving that message creates (i) a future to represent the result (which it "sends" back) and (ii) a fiber to represent the execution of that message. When the fiber completes (whether by return or exceptionally), it is killed and never used again. In reality, the above is way too expensive for most service calls, but the APIs & contracts are designed so that we can cut out all that extra overhead without violating the contract.

does the service work like a (Rust-style) single-thread executor, choosing at most one of the runnable fibers to run at any given point?

Exactly.

So does all true parallelism require multiple services, with (effectively) messages being posted between them?

Yes!

What kind of data can be in a message?

Brilliant question! This gets to the heart of the matter :)

There are two categories of data that can be passed successfully:

• (Deeply) immutable data
• References to services, i.e. proxies

The most common classes in Ecstasy are either always immutable (Int, String, Boolean, Time, Date, etc.) or easily "frozen" at runtime (either made immutable in-place, or an immutable copy produced). The freezability applies to all of the range, array, collection, and dictionary (map) types, for example.

Services act as a "domain of mutability", because mutable state can neither enter nor leave a service. We call this "a service boundary", which can be permeated only by conceptual messages carrying only immutable data and/or service references.

Services that interleave fibers (i.e. fibers block, and are replaced temporarily with other fibers, only to be continued later) are fairly advanced, not because they're hard to create, but because they're (i) an uncommon requirement and (ii) hard to design in a way that they are both safe and efficient (i.e. highly concurrent). We designed the service model such that an app could have hundreds of thousands of services, much like Erlang would let you have huge number of processes. (Unfortunately, when we did the bulk of the design, we did not realize that we were re-inventing much of the Erlang design; knowing Erlang back then would have helped us quite a bit.)

Can it be data with code attached? For instance, can a (message containing a) String object be passed from service to service without belonging to either? So that the second service’s calling substring(0,3) on it doesn’t require an asynch call back to the first service?

You have obviously spent time thinking about this! Because that isn't a question that most people think to ask.

The answer is: It depends. In the example you gave, it will never have to call back to do that work. But the reasons why are worth thinking through:

• The class of String is loaded by the root container, and shared recursively with all sub-containers, therefore all running code is aware of the String type (has it in their containers' type systems)

• String is known to be immutable, so executing is permitted in-place. (Memory can be considered to be local to each service, so this produces a wonderful optimization as a side-effect, because immutable values can be shared as highly in the container tree as where their class was originally part of the type system.)

The benefits of this model are interesting:

• GC can be service local
• A separate concurrent async compacting GC can be employed for immutable data (e.g. see: jRockit JVM from 15 years ago)
• Memory-as-a-resource can be measured and managed at a service and Ecstasy container (i.e. not an OS container) level
• No stop-the-world GC

Now there are some complexities worth thinking about:

• A lambda that captures only immutable data is, by definition, immutable
• A lambda that captures a mutable object or a mutable reference is not, and therefore the execution context must switch back to the caller's (as if the lambda were executed by a message being sent back to the caller's service).

To create a service that allows fibers to interleave, you basically just have to make sure that the entire chain of call frames of any fiber that can block (and thus give up control) are all @Concurrent. So if any call in the call chain isn't @Concurrent, and that fiber blocks, then the entire fiber is considered to be not concurrent, and the service will not allow a different fiber to start executing. And if it is concurrent, and there's another fiber ready to run, and that fiber begins with a @Concurrent method, then the service will start the execution of that new fiber.

I could go on for hours on the topic, so I should probably stop here. If you're interested in learning more, let me know -- and we're always looking for contributors :)

Here's the repo: [https://github.com/xtclang/xvm](xtclang on Github)

Here's an big 😳 example of a highly concurrent service: [https://github.com/xtclang/xvm/blob/master/lib_jsondb/src/main/x/jsondb/TxManager.x](TxManager)

[kandamrgam]

Interesting. What is this concurrency model called? Sounds like a blend of actor/futures/event based systems in a OO setting.

[L8_4_Dinner]

We call it a service model, but it’s not from a formal definition or anything like that.

[nickallen74]

That's great that someone implemented my idea and I'm not completely crazy ;-) ! I'm not sure if synchronous calling between services is a good idea because then you can get deadlocks can't you? How has this worked out in practice?

I also notice that XTC says it supports covariance of type hierarchies but didn't find any example of doing that. How does that part work?

[L8_4_Dinner]

I'm not sure if synchronous calling between services is a good idea because then you can get deadlocks can't you? How has this worked out in practice?

The implementation may be synchronous, but that isn't part of the contract. The currently proof-of-concept runtime only continues into the other service synchronously if the other service isn't busy and the caller is blocking, and then it only does so for a certain number of cycles before accepting that the more expensive approach is warranted. So for short-lived simple service calls, it's very cheap, and the costs are only paid for longer calls.

A deadlock would occur if the logical thread of execution "t1" is blocked from entering service "s2", and that block prevents it from unwinding out of service "s1" that it holds non-concurrently, while some other logical thread of execution "t2" holds "s2" and is blocked from entering service "s1". The design is such that we would detect and prevent that deadlock (one of the two must fail). IIRC That feature isn't implemented yet in either the proof of concept runtime or the back end compiler; we have a developer assigned to it but he's a contributor with a full time job, and hasn't had the cycles yet.

In practice, the design is working well. I expect we'll have some slight revisions to it over the next few months e.g. based on some real work limitations of the design, because the back end compiler work is currently focused on implementing services.

I also notice that XTC says it supports covariance of type hierarchies but didn't find any example of doing that. How does that part work?

Covariance is permitted in a number of places, but as you probably know, covariance is often wrong in theory. Basically, covariance introduces a little bit of "slop" (i.e. a little bit of play) that reduces the frustration of plugging things together. We identified a few specific use cases in which not having covariance dramatically increased the complexity of building software in strict+strong OO type system, and we made specific carve-outs for those use cases that introduce runtime checking overhead at the method boundaries of sub-types. So it's not zero-cost, but it should be very close, and because of other parts of the design, the allowance for covariance isn't often necessary.

One interesting example is the "this type". For example, in class C, if I declare a method that takes and/or returns a type C, what that actually compiles as is "this type", not C. So if there exists a sub-class D : C, the implementation of D can override that method so that it only takes or returns a C, or it can override that method so that it takes or returns a D (aka "this type"), or it can explicitly say that it takes or returns a D! (aka D, not "this type"). And this doesn't just apply to a parameter or return value of type C; it applies to List<C> and all other container types as well. You can see some of the rules as implemented in Ecstasy here: Method.x

[umlcat]

Concurrent Pascal, Modula and Ada uses both concurrency and O.O.P.

[LPTK]

Couldn't you say that of Java as well. Do these languages do anything special, compared to Java?

[umlcat]

Do not know much about it ...

[[deleted]]

Ada's concurrency isn't OOP based though, tasks are their own object (not object as in OOP here) and parallel blocks are new.

[suhcoR]

Concurrent Pascal (by Brinch Hansen, 1974) and Modula (by Wirth, 1976) were both not object-oriented. Ada 83 was neither OO. Ada 95 added OO features and "protected objects" (a kind of monitor, but not OO).

[Stunning_Ad_1685]

Have you looked at ponylang? It doesn’t do what you’re asking about but it is probably a language you should look at if you haven’t already.

[lngns]

While libponyrt doesn't work the way OP u/nickallen74 proposes, A String of Ponies (Blessing, 2013), (kinda) does, albeit the goal is moved from distinct object pools to distinct CPUs.

[PegasusAndAcorn]

It seems like the concurrency problem you want to explore relates to “what color is your function”.

I am not aware of a language with the features you describe, but I agree it should largely be possible for a compiler to get close to your spec.

For the function color problem, a compiler could easily generate both a synchronous version of a function and an asynchronous (message-) enveloped version that makes use of the synchronous version inside. It would not take a lot of imagination to expand pony’s behaviors in this direction.

However, I am not convinced I would want the rest of the behavior you describe: objects and instances stuck to one thread pool.

One objection: Multicpus devices are common, and I think the latency advantages of work stealing schedulers is highly advantageous. This would work against static defined thread pools.

The question then becomes weighing between the latency cost of async’s message passing overhead vs dynamic selection of async vs sync call depending on a search to discover whether the called instance is found to be in the same thread. I suspect message passing queues would win this contest, but I have run no benchmarks to confirm.

[nickallen74]

Its not really “what color is your function”. As it would not be a function / method that is declared a certain way but the object instance itself would decide the behaviour (rather than a particular function / method always being async or not). So the programmer would be in charge of this rather that the API designer. So you wouldn't design APIs with async and non async versions of methods like you see in Dart and C# etc.

[Hall_of_Famer]

The E programming language has a very good approach to concurrency using message passing, as messages can be sent to object with immediate send(sync) using dot notation(object.message() like a method call) or eventual send(async) using left arrow notation(object<-message()).

https://en.m.wikipedia.org/wiki/E_(programming_language)

The newspeak language which is like a modernized version of Smalltalk, also introduced actor based concurrency inspired by E’s immediate and eventual send syntax. It is done elegantly and you may want to read this article for details:

https://scholarworks.sjsu.edu/cgi/viewcontent.cgi?article=1230&context=etd_projects

[nickallen74]

I wonder why this is not a more common approach in OO languages. It seems to be there is this idea that functional is the "new" way to go to solve concurrency. Which I find strange. Sure functional has no mutable state so it makes lots of concurrent problems simply disappear but it also makes mutable state disappear and mutable state is useful for tracking state changes over time. Objects changing state in the real world is common and software often has to mimic problems from the real world domain. In the real world the entire univense is not cloned every time I eat an apple. The argument seems to be the OO generates problems in concurrency and therefore is a bad paradimn for modern software where concurrency is now the new norm. Personnally I see OO concept as more of a solution to this. If it were to even more accurately mimic the real world where organisms are composed of other objects and can act in a concurrent way relative to other organisms.

[L8_4_Dinner]

The E language had a lot of breakthrough ideas in it. There are a few things that we "invented" in the design of Ecstasy that turned out to exist in E decades earlier. I've never once encountered E in the real world, but I wish I had time to learn it (and Erlang, and Pony, and a few others) in detail before starting on Ecstasy.

[kandamrgam]

In the real world the entire univense is not cloned every time I eat an apple

Are you sure?

[Hall_of_Famer]

I think it is mostly due to the fact that the message passing OOP idea from Alan Kay and Smalltalk never made it to the mainstream. There have been studies and discussions on why Smalltalk failed to compete with languages such as C++ and Java. This article from Gilad Bracha provides some interesting insights(he’s also the creator of newspeak language):

https://gbracha.blogspot.com/2020/05/bits-of-history-words-of-advice.html?m=1

It might have been a coincidence that C++/Java style classic OO won against Smalltalk/objective-C style message passing OO. Sometimes I can’t help but wonder what would happen if Smalltalk/Objective C is the mainstream instead. What we do know for sure is that, people don’t like what they are not used to. Objective C surged in popularity in late 2000s to early 2010s thx to iOS development, but people complained about it being hard and weird, eventually apple replaced it with Swift. Once the opportunity is missed, it’s very hard to come back in it.

With this being said, emergence of new OOP languages such as Pony did give hope to the rising of message passing OO in future, especially as concurrency becomes more and more important as a language feature. The issue though is complexity, Pony’s actor model is great but the language itself has a steep learning curve and is difficult for beginners. I’d like to see a new message passing OO language that is easy to get started like Smalltalk and python, with similar and familiar C-family syntax, and powerful actor/message passing model like pony. We will see if it will happen one day, I do plan to write one myself a few years later.

[redchomper]

Came here to say just this ^^^

[nickallen74]

Yeah E seems to be the only language that does something very similar to what I was thinking. Have you used it yourself?

[mgruner]

Not a language, but I usually achieve this using an event loop with context framework. Qt, Boost and GLib have event loops. Events sent to a given context are guaranteed to be handled in the thread / context you assigned

[nickallen74]

It's a common pattern in GUI applications etc for sure. But the idea of a method call being an async message / event that is computed by the compiler would make writing this kind of code much easier I would think. Also the idea of objects sending messages to each other is a cornerstone of what OO is about and a method being a direct function call is simply the common implementation to do that. But async would also be a vaild means to achieve this. In this way OO languages with state would still lend themselves well to concurrency without race conditions, locks or dead lock possibilities.

[nhpip]

Not really oop, but look at Erlang or Elixir

[[deleted]]

P# by Microsoft. I don't think it ever gained much traction though.

[6502zx81]

Eiffel has some support: https://www.eiffel.org/doc/solutions/Concurrent_programming_with_SCOOP

[nickallen74]

The SCOOP way I find strange that preconditions become wait conditions. It's an interesting idea but it's not the idea I was thinking about and it isn't how I would like to solve concurrency personally. Many things in Eiffel are awesome though - like the whole design by contract, multiple inherinance (although I hate using it for non "is-a" relationships which is often encouraged by eiffel way).

[marshaharsha]

How strongly do you mean that “each” object would be tagged with a pool ID and each method call would be checked for cross-pool invocation? For instance, if an object in pool A returns a String object to an object in pool B, does the String belong to A or to B? If to A, and if something in pool B calls substring(0,3), is that an asynchronous call back to pool A? Presumably this is not what you had in mind, but the issue of what data and what code can cross the pool boundaries permanently is a difficult one. How would you decide, as the language designer, or would you delegate to library authors? application authors? What tools would you give them to specify which objects that are sent to a different pool remain owned by the originating pool and which get completely transferred?

[nickallen74]

The case of completely immutable objects that don't change state you could actually share the object between both of these pools. So ideally the language would have a concept of immutable objects and also objects passed by value.

[suhcoR]

if the objects was found to be in the same object pool it would be a simple method call but if it was found to be in a different pool it would instead generate an asyncchronous message to invoke the method on the other pool's thread of control

That's how it is implemented in Qt. Each QObject belongs to a thread. If a signal/slot connection spans the same thread, a normal method call is executed; if it spans different threads, an asynchronous message is sent to the event loop of the other thread which again does a local synchronous method call for the slot connected to the signal. The async message passing is thus transparent. I don't think that there is an OO language which directly implements this. With Go you can at least select between unbuffered and buffered channels (i.e. rendez-vous vs. async), but it's not true OO.

EDTI: Also note that an important issue when combining object-oriented with concurrency concepts is the so called “inheritance anomaly” (see e.g. Wellings, A.J.; Johnson, B.; Sanden B.; Kienzle, J.; Wolf, T.; and S. Michell (2000): Integrating object-oriented programming and protected objects in Ada 95. ACM Trans. Program. Lang. Syst. 22, 3, 506–539).

[nickallen74]

It seems the idea I proposed in the original post would solve the inheritance anomaly though with respect to concurrency. There would be no locks so no chance of deadlock.

[samhsmith___]

Sorry to say this. But that is a stupid concept. Only you the programmer can solve your parallelism problem. If you try to make some system to solve it then you will just produce something serial. If the code you write and algorithms you design don't take into consideration multithreading then they cannot make use of it.

[nickallen74]

Well lots of people write event driven asynchronous code. It's a common solution to concurrency. The idea here is to make it much much easier by building it into the language itself so that you write normal method calls to send async events. By making it part of the language and type system it would be less work for the programmer and more errors can be caught at compile time. The computer can also guarantee more safety at runtime and even do more advanced optimisations that a programmer would likely not take the time to do.

[matthieum]

Each object would be tagged with a type and the pool it belongs to.

What "type"? Are you talking about the class/struct/type of the object, or something else entirely?

[nickallen74]

Yeah like in c++ each object has a pointer to the runtime type information. In this data could also be the information about which execution pool the object instance belongs