Traditional models of communication between devices, processes, and threads include message-passing, remote procedure calls, and shared memory. Here's a model I haven't seen before: shared game-playing. How it would work: • The rules for a "game" of some kind are expressed as a code library... or whatever representation works best. • A set of "players" (processes or threads) express interest in playing the game with each other. (somehow...) • The players communicate with each other by interacting with the game (in accordance with its rules), and receive information about each other's actions by observing how the game state has changed. The "game" could be an actual game like chess or Factorio (implemented via peer-to-peer communication), or it could be a standardized protocol like HTTP, FTP, or (most commonly) it could be an application-specific protocol that would normally be implemented via message-passing or RPC. Imagine if this were the only model of communication that a programming language exposes. What if it were the "building block" of communication — the only way to build concurrent systems? I think it's an intriguing thought 🤔. I'm surprised I haven't heard this model proposed before. (This post was inspired by Syndicate, which is an actor-based PL that eschews message-passing and RPC for the idea of a "data-space" that actors use to exchange information. But unlike my proposal above, Syndicate's data-spaces don't contain rules, and thus cannot be used to model video games or communication protocols.)

if you replace game for server, players for client and game rules for protocol or API, how is it different to client/server?

The difference is that the “game” isn’t a device. It’s just code that runs on each of the players’ machines such that each player can keep track of what has happened and what can be done next. It’s peer-to-peer communication.

Sounds like statemachine replication.

I think you might want to take a look at croquet.io . @yoshiki is a core developer and is sometimes active here.

Kind of sounds like a mix of session typing and tuple spaces. I like the idea, and I think it would be fun as an available option, but I'm not sure I'd try to make it a primitive. https://en.wikipedia.org/wiki/Session_type I guess Syndicate already references tuple spaces, but I'll toss that link here for completeness. https://en.wikipedia.org/wiki/Tuple_space

@ibdknox This communication model definitely involves replication, though when I google "state machine replication" it turns up unrelated stuff about fault-tolerant servers. Nothing about a communication model. @Tudor Girba Oh that's interesting! Croquet OS seems to be built upon replicated virtual machines (the things I'm calling "games") as well. But I suppose that's not surprising — Croquet is quite literally a platform for games (and other virtual worlds). I'll suss it out 🙂. @Andrew F Yes, this model is definitely somewhat reminiscent of session types and tuple spaces. The motivation for making it a primitive is the same as the motivation for putting session types into a programming language — to allow users to write programs against a known interface, and to allow the computer to check that the interface is being used correctly. RPC (in a statically-typed language) is an ultra-simplistic example of this — it models one action, followed by one response.

I just feel it ought to be possible to do it as a library given an adequately expressive type system, but I haven't thought about it that deeply. :) Also, re state machine replication: yeah, I'm guessing the fault tolerant server stuff is what Chris was referring to. Communication is a big part of fault tolerance. From the perspective of designing abstractions, it probably looks more like a potential implementation detail, but it will constrain what kinds of "games" can run over an unreliable (i.e. real) network.

Definitely any mechanism for fault-tolerance should be a library. I doubt it is possible to find "the ultimate answer" to fault-tolerance, and thus bake it into a PL. 😇 Type checking, on the other hand, is definitely the job of a PL! To make a "game" fault-tolerant, you'd just have to add corresponding rules to the game — e.g. allow clients to vote an unresponsive client out of the game.

yep, I did indeed mean that, though not for the fault tolerance, but because it almost exactly describes the model you mentioned. From the wikipedia article:

Ah, but the trick is that you don't have to choose an order 😉. Not in general. There exist data models that allow for much more loosely structured interaction. In fact, you're the one who introduced me to those data models Chris! My research project over the last few years has been based on Datalog, extended with a declarative model of time.

unless you’re only allowing monotone programs, you’ll need an ordering once there’s communication

Yes, a partial ordering. Real-time video games often do this by stratifying a game into "frames", and allowing players to simultaneously submit their actions for that frame. You'd do something similar. The key idea is that the rules for how inputs affect each other are specified as part of the game rules. This is a good alternative to forcing a global order upon all inputs, as Croquet seems to do!

Yep, that’ll work for some programs 🙂

I mean, it can work for all programs, because a total order is just a special case of a partial order 🦄. If your program needs a total order, you can always impose one. But it can happen at the "game" level, not the programming language level. For example, if you think your game needs the "relay" architecture that Croquet uses, you can implement that at the game level. Instead of writing a game that clients play with each other directly, you write a game that the clients play with the relay.

Sure, but at that point you’re right back at “present day.”

I think we're on the same page here — that's the solution I'm envisaging (and working on). I'm envisaging a programming language wherein you write these "games" using Datalog-style rules, which are partially ordered. Tuples would be stratified by timestamps similar to how it's done with Dedalus (I've been working on a generalization). Then, much of the explicit coordination logic is handled by the language runtime — e.g. the actual exchanging of messages between game-players. But there is always going to be some logic — such as fault-tolerance — which must be written into the game itself, because there is no blessed solution that will work for all games. For example, how to handle unresponsive players should be up to the game. Maybe the game waits indefinitely, maybe there's a timeout, or maybe the other players have to vote the unresponsive player out. (Standard mechanisms could be offered as libraries, but not as language-level constructs.)

I’ll be curious to see what it’s like programming with the time stratification. It led to a lot of unfortunate weirdness in Eve. It’d be awesome if you found something more natural 😄

I believe I have! I'm working towards a shareable prototype as we speak. The hardest part has actually been figuring out a good syntax for it. I've had to invent a wholly different syntax to standard Datalog — something that is easier for us humans to read. I should have something to share in February. At least, that's when I'll have the time to work on it. Stay tuned 🙂.

Hi Chris - can you elaborate on the "unfortunate weirdness"?

We found that people struggled dealing with the implications of stratified time so we tried to hide it to some degree. We made it so that

commit

which permanently added a fact into the world and

bind

which only adds a fact for as long as it was supported represented T+1 and T respectively. For many things that worked well, but it can be very hard in multi-step processes to understand why something may not behave correctly.

I'm leaning towards thinking that time is another domain or application level thing that the user or programmer deals with, but that they should be given engine support in that data should be both spatial /and/ temporal in its presentation to them. In other words, don't build in strict synchronisation because often best effort is good enough, but let them sew things together precisely temporally if their application needs it. Don't have always-reliable messaging, have best efforts and make it easy to define timeouts for important application protocols or interactions.

In the language semantics I’m working on, time is application-level as you suggest. What’s built-in is the notion of stratification by inductive types (think Haskell ADTs), of which the natural numbers are a special case. Stratifying by natural numbers allows you to model linear time, but you can also stratify by other structures, which allows you to model bottom-up (memoized) recursion, a.k.a. “dynamic programming”. So my proposed semantics for time is also a semantics for provably terminating (or productive) non-monotonic recursion — something Datalog is sorely missing 😇. Concretely: this means you can model any iterative or recursive computation that you’d perform in an imperative language, by defining a (possibly non-linear) “virtual machine” that executes it. The state of the machine can be observed by supplying “timestamps” for the steps you want to observe. (For a dynamic programming algorithm, these steps are the cells of the table.) The end result is a de facto Turing-complete programming language built upon Datalog semantics. De facto because it‘s impossible to crash or hang your program — unless you invoke a computation that takes a long-but-finite time to resolve. For any Haskellers reading this: the semantics is a generalization of “recursion schemes”. This may or may not make sense to anyone. I’ll be able to explain it properly once I’ve finished putting together the prototype. It might sound complicated, but I’ve been working on a syntax that (I hope) makes it feel simple. (And debuggers that visualize these dynamic processes are going to be important too.) This stratification scheme would be a very general way to drive the “games” I’ve been talking about 😇. It’s a means of specifying partially-ordered non-monotonic computations. (Apologies to readers who don't know what "monotonic" or "stratified" means. These are terms from the logic programming community. You'll encounter them in most Datalog tutorials.)

I get the feeling that bloom is related to this: Bloom is a language … … for disorderly distributed programming because order is expensive … with powerful consistency analysis CALM guidance on coordination … and concise, familiar syntax based on data-centric languages

Indeed it is! Bloom is based on Dedalus, which I briefly mentioned above. They were both developed at UC Berkeley 🙂.

This model also seems close to how DynamicLand's RealTalk system works. Pages (representing computational objects) don't communicate with each other, they just make claims and wishes and the runtime system resolves them (apparently at 60 times a second). In your description in the first post the RealTalk system provides the 'game rules'.