Yes! Another example: ~_*range{start.inclusive, end.exclusive, domain is int{0..30}, end=start+length, midpoint?, length?}*_~ ; By using constraints to define relations, and invertable/full on algebraic operations; an expression could be automatically reworked to isolate different set of variables; and provide ability to change them. Eg, here, changing the length will lead to an ambiguous case (>1 free variable), but with a structural editor, it may show all possible interpretations for you to select (eg. keep end or start fixed, or scale track around certain point, or add custom interpretation logic (eg. using non-linear scaling)). Integrating this system deeply with the UI would allow pretty much auto-generation of it just from the expression/range concept, auto supporting all interaction (drag track, endpoints, scale around scalepoint, etc), which would otherwise have been pages of code in eg. current web development...

(Instead of generating function... why not just keep everything declarative at its core? :)) )

See, also, PROLOG, miniKanren, constraints, unification.

My quickie tutorial youtube.com/watch?v=QOYAHoLiyg0 includes converting a query result to JSON.

You might enjoy dl.acm.org/doi/10.1145/3397537.3397546

But I’ll also just mention term rewriting in case you aren’t familiar. It’s how Mathematica is able to do the sorts of things you listed. It’s a shame there is no mainstream, non-proprietary language based on it.

seems to me exactly what oo systems do, having different constructors, and providing methods on the objects?

An OO system won't just casually reconstruct a side of a rectangle from the other side and the diagonal, no. TBH I'm leery of that sort of thing from a performance standpoint. I don't want to have to think too hard to know when my code is doing sqrt's. Logic programming is cool, but I definitely don't want it all the time.

aside: If you need to steal/get-ideas-from code: the yawningly easiest-to-understand implementation of PROLOG is Nils Holm’s t3x.org/bits/prolog6.html (it’s so easy, that I ported it to 2 other languages - JavaScript and CL). If you want to dig in and make an optimized PROLOG, look at WAM (Warren Abstract Machine). Ait Kaci’s tutorial is helpful en.wikipedia.org/wiki/Warren_Abstract_Machine (I had found a $0 download, but can’t find it at this moment). Gprolog is implemented with WAM and can be forced to show what WAM it generates. MiniKanren is relational programming done without backtracking minikanren.org.

This issue is quite serious in scientific computing. A mathematical equation is a lot more than a piece of code that implements a particular evaluation based on it. And yet, we see equations disappear, to be replaced by less valuable code.

My attempt to fix this is to move from programming to specification languages. You'd write equations defining the relations for a rectangle in the specification languages, and then either read them into your program, or derive your program from them.

Details: blog.khinsen.net/posts/2020/12/10/the-structure-and-interpretation-of-scientific-models

Relatedly, most if not all validation concerns arise from data dependencies. Take, for instance, an Event with a start_date and an end_date . Naturally, we should have start_date ≤ end_date in the end, but for a UI, it can be nice to choose them in either order or to have an InconsistentEvent that then gets fixed by the time you use it. But some operations over regular events still sense for inconsistent events.

Also thinking about scheduling dependencies from assembling LEGO with my son and his friend yesterday. Friend's mind was blown to see son and I concurrently working on different steps.

Earlier this year, concurrency concerns lead me down a path to radically improving the expressivity of my software's model layer because being explicit about data-dependencies allowed for context-based resolution of references.

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.

(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. Or put another way: a “peer” can act as a server if it wants/needs to, but it’s entirely optional.)

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.
• There is no ability to send unstructured "messages". There is only the ability to make "game moves". 😯

And ideally, your programming language has a type system capable of verifying that your program only makes valid game moves. But that's a whole different discussion.

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. en.wikipedia.org/wiki/Session_type I guess Syndicate already references tuple spaces, but I'll toss that link here for completeness. en.wikipedia.org/wiki/Tuple_space

Chris Granger 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:

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.

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

e.g. I don’t think it’s possible to guarantee a limited number of turns in one of your games without it

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!

That's pretty much the Datalog philosophy: order emerges from the structure of rules. There is no total order imposed upon everything.

(This is also the philosophy required to develop distributed systems. If you want your distributed system to be scalable and responsive, it's often not possible to impose a total order on all events.)

Yep, that’ll work for some programs 🙂

Peter Bailis’s IConfluence work explains exactly which ones

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

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 today

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.

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

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