https://futureofcoding.org/ logo
Title
n

Nick Smith

12/31/2022, 7:20 AM
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. • 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.)
m

Mariano Guerra

12/31/2022, 10:27 AM
if you replace game for server, players for client and game rules for protocol or API, how is it different to client/server?
n

Nick Smith

12/31/2022, 10:30 AM
The difference is that “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.
(Peer-to-peer communication is more general than client-server. The former can be used to model the latter, but the converse isn’t true.)
The network topology isn't the interesting thing here though. The interesting thing is the proposal that in order to engage in communication with someone, you have to specify a "game" that you are going to play with them. Nobody can communicate without first specifying the rules of the game. 😯
i

ibdknox

12/31/2022, 1:09 PM
Sounds like statemachine replication.
t

Tudor Girba

12/31/2022, 2:24 PM
I think you might want to take a look at croquet.io . @yoshiki is a core developer and is sometimes active here.
a

Andrew F

12/31/2022, 10:09 PM
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
n

Nick Smith

01/01/2023, 3:30 AM
@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.
a

Andrew F

01/01/2023, 3:44 AM
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.
n

Nick Smith

01/01/2023, 3:52 AM
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!
i

ibdknox

01/01/2023, 3:54 AM
your “game” is a state machine, which defines the only valid inputs and transitions that any peer in the system can take
the crux is #3. Choosing an order is very hard. Croquet solves that by using relays as timestamp providers.
n

Nick Smith

01/01/2023, 3:57 AM
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.
i

ibdknox

01/01/2023, 3:58 AM
unless you’re only allowing monotone programs, you’ll need an ordering once there’s communication
e.g. I don’t think it’s possible to guarantee a limited number of terms in one of your games without it
n

Nick Smith

01/01/2023, 4:01 AM
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 though 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!
That's pretty much the Datalog philosophy: order emerges from the structure of rules. There is no total order imposed upon everything.
i

ibdknox

01/01/2023, 4:04 AM
Yep, that’ll work for some programs 🙂
Peter Bailis’s IConfluence work explains exactly which ones
n

Nick Smith

01/01/2023, 4:07 AM
I mean, it can work for all programs, because a total order is just a special case of a total order 🦄. If your program needs a total order, you can always impose one. But it happens at the "game" level, not the programming language level.
i

ibdknox

01/01/2023, 4:12 AM
Sure, but at that point you’re right back at “present day.”
In some sense, we’re saying you could relax #3 from the description of state machine replication and still have something useful, which is definitely true depending on the shape of the state machine
if the state machine happened to be IConfluent, then it’s guaranteed to be safely eventually consistent and we can just broadcast inputs everywhere and be good to go
an interesting take on all of this, is rather than just leaving this “up to the game” why couldn’t the programming system determine where this type of coordination is necessary and have it handle these topological concerns for me?
we know programmers are pretty terrible at this stuff, so pushing it into the application layer is likely going to end up in something analogous to toda
n

Nick Smith

01/01/2023, 4:22 AM
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.
i

ibdknox

01/01/2023, 4:24 AM
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 😄
n

Nick Smith

01/01/2023, 4:28 AM
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. Stay tuned 🙂.
d

Duncan Cragg

01/01/2023, 1:22 PM
Hi Chris - can you elaborate on the "unfortunate weirdness"?
i

ibdknox

01/01/2023, 2:03 PM
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.
More generally stratified time adds another dimension to the call graph, which is already a difficult thing to piece together
unlike in imperative programs, there’s no “starting” place so now not only do you have to consider the dependency graph of all the assertions in your program you now have to model an invisible timeline that indicates “when” those assertions happen
you might be able to paper over that with tooling, but it’s going to be complex either way
d

Duncan Cragg

01/01/2023, 9:49 PM
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.
n

Nick Smith

01/01/2023, 10:30 PM
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. 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. This stratification scheme is what would drive the “games” I’ve been talking about 😇.
m

Mariano Guerra

01/02/2023, 11:48 AM
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
n

Nick Smith

01/02/2023, 12:25 PM
Indeed it is! Bloom is based on Dedalus, which I briefly mentioned above. It’s all work done at UC Berkeley 🙂.
n

Naveen Michaud-Agrawal

01/02/2023, 1:39 PM
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'.