> Yes; in the course of time, men will certainly travel to the moon. The journey will be performed in safety, and at a comparatively rapid rate. Just how fast, can not be predicted; but it will be sufficiently great to enable the voyager to make the trip in six hours. The mode of conveyance will probably be an aerial machine, similar to those in which M. Santos Dumont lately accomplished such wonderful feats at Paris. The earth will be left behind at a point in Eastern France, and the moon will be reached in safety. The return journey will be accomplished in five hours. The voyager will find the lunar surface very much as described by astronomers. He will discover signs of life in the shape of numerous extinct craters, and possibly in the presence of living beings; but of the latter fact he can not be certain. The moon’s atmosphere will be found to have an extent of about five miles. Its temperature will be very cold, and, altogether, the place will be unsuited to human habitation. The project of lunar travel was first seriously entertained in 1860, when a scheme was brought forward for establishing telegraphic communication with the satellite. Since then, the idea has been advocated, from time to time, by speculative persons; but it has never been put into practice, until the present year. It has been suggested that the moon may be occupied by inhabitants, but the notion is absurd. The only imaginable purpose, for which lunar communication could be established, would be the acquisition of knowledge respecting the state of the weather. If the project were carried out, a storm, warning us of an approaching tempest, might be received from the moon, six hours before its arrival, here below.
Something I’ve wondered about Datalog is whether integers can be added to the language without losing guarantees about termination of query evaluation. It seems like as soon as we add integers with successor() or strings with concat() then we can potentially create infinite relations. Is there a way to add integers or strings (well, really basic scalar operations on integer or string values) while preserving termination guarantees?
This bit at the end of the article seems to imply it’s possible, maybe with some tricks?
> We could also add support for arithmetic and composite atoms (like lists), which introduce some challenges if we wish to stay “Turing-incomplete”.
Not without a termination checker. Take a look at Twelf, it is a logic programming language and proof assistant based on the dependently typed LF logical framework. You can use general algebraic types in relations, and in general queries can be non-terminating. However, the system has a fairly simple way of checking termination using moded relations and checking that recursive calls have structurally smaller terms in all arguments.
Twelf is quite elegant, although not as powerful as other proof assistants such as Coq. Proofs in Twelf are simply logic programs which have been checked to be total and terminating.
The syntax of Twelf is a bit different from other logic languages, but just note that every rule must have a name and that instead of writing `head :- subgoal1, subgoal2, ..., subgoaln` you write `ruleName : head <- subgoal1 <- subgoal2 <- ... <- subgoaln`.
Also note that this approach only works for top-down evaluation because it still allows you to define infinite relations (e.g. the successor relation for natural numbers is infinite). Bottom-up evaluation will fail to terminate unless restricted to only derive facts that contribute to some ground query. I don't know if anyone have looked into that problem, but that seems interesting. It is probably related to the "magic sets" transformation for optimizing bottom-up queries, but as far as I understand that does not give any hard guarantees to performance, and I don't know how it would apply to this problem.
By total coincidence, today I've been looking at Datalog implementations. The Datalog(-adjacent) Soufflé tutorial says this right near the start:
> For practical usage, Soufflé extends Datalog to make it Turing-equivalent through arithmetic functors. This results in the ability of the programmer to write programs that may never terminate.
> In this article, we study the convergence of datalog when it is interpreted over an arbitrary semiring. We consider an ordered semiring, define the semantics of a datalog program as a least fixpoint in this semiring, and study the number of steps required to reach that fixpoint, if ever. We identify algebraic properties of the semiring that correspond to certain convergence properties of datalog programs. Finally, we describe a class of ordered semirings on which one can use the semi-naïve evaluation algorithm on any datalog program.
It’s quite neat since this allows them to represent linear regression, gradient decent, shortest path (APSP) within a very similar framework as regular Datalog.
They have a whole section on the necessary condition for convergence (i.e. termination).
Hey, author here. The one time I go straight to bed after posting on hackernews is the one time I get a bunch of comments hahaha.
Yes you can add support for integers in various ways where termination is still guaranteed. The simplest trick is to distinguish predicates (like pred(X, 42)) from constraints (like X > 7). Predicates have facts, constraints do not. When checking that every variable in the head of a rule appears in the body, add the condition that it appears in a predicate in the body.
So if you have a predicate like age(X:symbol, Y:int), you can use its facts to limit the set of integers under consideration. Then, if you write:
age(X, A), A + 1 >= 18.
You'd get everyone that becomes an adult next year. Fancier solutions are also possible, for example by employing techniques from finite domain constraint solving.
> Prolog is honestly kind of jank, and I’m not talking about good vintage jank like C.
Respectfully I would encourage you to consider this comment is confusing bad Prolog with all Prolog, and you are really missing out on some elegant and powerful concepts if you believe Prolog stops here.
I would love this to be an invitation for you to reevaluate modern Prolog and see what the language is really capable of.
I'll throw you right in the deep end with Prolog Definite Clause Grammars[1] and meta-interpreters[2].
There are a few things which are very special and magical to Prolog which are quite mind expanding. I hope you enjoy the resources.
DCGs are cute, I like that writing something that looks like a grammar allows you to very easily generate sentences for that grammar. That's amazing for things like property-based testing.
But why wouldn't you use Mercury instead? No extra-logical nonsense like cuts, IO done properly with linear types, much better performance, etc. DCGs aren't exclusive to Prolog, why suffer the janky bits?
And while they're not built-in to it, Soufflé Datalog supports algebraic datatypes (so you can model difference lists), and you could preprocess a DCG into the native clause form plus a length tracking argument to prevent it from creating an infinitely sized database.
I've never worked with meta-interpreters so I can't comment on those, but I will try to watch the video you posted later.
That's a great question. The answer to "why wouldn't you use Mercury instead?" should hopefully be more clear when you watch the meta-interpeter video. The syntax of Prolog is not accidental, and this is a case where it really matters. You sacrifice a lot of power by introducing things like dot access notation.
Additionally, there is nothing stopping you from writing pure monotonic Prolog, which does not involve cuts and uses pure IO.
Circling back to DCGs, the combination of DCGs plus interpreters, which can be expressed in a handful of lines of code, allows for powerful language crafting.
While constraint solvers are not unique to Prolog, CS+DCG+MI is a killer combination I've only ever seen in Prolog that when combined allow you to solve some wicked problems rather elegantly.
That being said, thanks for the reminder about Mercury, that looks like it could come in handy on some Java-only projects.
This is DCG+CS only, still quite powerful and I have adapted it for GOAP and Hierarchical Task Networks quite successfully:
https://www.metalevel.at/zurg/
Finally, I will agree with you that there is a LOT of jank Prolog, but not ALL Prolog is jank, and some Prolog is truly exquisite-- I hope you will keep an eye out for it.
Don't know if you're still reading this thread but just in case I finally got around to watching the meta-interpreter video. I can definitely see why Prolog shines for this.
Though even in that video we see a display of "jank", e.g., needing to ensure that rules don't overlap, being careful with introducing redundant choicepoints, permission errors, the trick with +, etc. in the vanilla meta-interpreter and the workarounds to get efficient tail recursion in the list-based meta-interpreter.
However, I don't think there's any way to avoid such "jank" when implementing something this powerful. The "jank" is the price to be able to do this. So fair point that this is something Prolog, and only Prolog, can do.
You made my day. I am a long time lisp developer who held a similar view of Prolog for a very long time until for various reasons I stumbled on these videos, and then realized there was a whole aspect to the language I was unaware of that went beyond the logic. Really great community developing around this stuff particularly with Scryer and Trealla that are very active if you are interested in discussing any of this further.
The fact that we were able to have this exchange was great. I appreciate your points and look forward to incorporating your work into mine!
Yes, for some kinds of operations on some kinds of data structures. The keyword/property is "monotonicity". Monotonic functions are guaranteed to terminate under fixed-point semantics.
Look into Datafun: A total functional language that generalizes Datalog. Also be sure to watch Datafun author Michael Arntzenius's Strangeloop talk.
It’s all about the terms. As soon as rules can create an infinite sequence of new terms for a single relation, e.g. by addition, you’ve got non-termination.
> If that is a team level, it should be in the team table, not the player table.
It's all contrived, of course, but the reason I would consider skill level to be a player attribute rather than a team attribute is that there could be free agents with a skill level but no team:
INSERT INTO player VALUES (10, 'Pavlo', 'AAA', NULL);
Then with enough free agents, you could imagine building a new team out of free agents that are all at the same skill level:
UPDATE player SET team = 'Otters' WHERE level = 'AAA' AND team IS NULL ORDER BY id LIMIT 3;
PG only uses EvalPlanQual under read committed isolation. Under repeatable read the first update fails with a "could not serialize" error, just as it does under serializable.
It's a good question. For simple UPDATEs, CockroachDB always executes in a deterministic, serial order and so it's likely the rows will be locked in the same order by any competing updates. (This can be confirmed by looking at the query plans.) Complex UPDATEs using joins and subqueries will need explicit ORDER BY to always lock in the same order.
If an UPDATE has to retry halfway through, locks are held across the retry to help the system make progress. But as you point out, this could cause lock acquisition to happen in an unexpected order if new rows qualify during a retry. So far we haven't run into this, but we might need to provide an option for an UPDATE to drop locks on retry if deadlock turns into a bigger problem than livelock. It depends on the workload.
> So far we haven't run into this, but we might need to provide an option for an UPDATE to drop locks on retry if deadlock turns into a bigger problem than livelock.
I'm not sure what you mean by that: the design can deadlock but you just have not seen it happening yet?
Edit: oh i see in a comment bellow that deadlocks are detected and abort the transaction.
> Yes; in the course of time, men will certainly travel to the moon. The journey will be performed in safety, and at a comparatively rapid rate. Just how fast, can not be predicted; but it will be sufficiently great to enable the voyager to make the trip in six hours. The mode of conveyance will probably be an aerial machine, similar to those in which M. Santos Dumont lately accomplished such wonderful feats at Paris. The earth will be left behind at a point in Eastern France, and the moon will be reached in safety. The return journey will be accomplished in five hours. The voyager will find the lunar surface very much as described by astronomers. He will discover signs of life in the shape of numerous extinct craters, and possibly in the presence of living beings; but of the latter fact he can not be certain. The moon’s atmosphere will be found to have an extent of about five miles. Its temperature will be very cold, and, altogether, the place will be unsuited to human habitation. The project of lunar travel was first seriously entertained in 1860, when a scheme was brought forward for establishing telegraphic communication with the satellite. Since then, the idea has been advocated, from time to time, by speculative persons; but it has never been put into practice, until the present year. It has been suggested that the moon may be occupied by inhabitants, but the notion is absurd. The only imaginable purpose, for which lunar communication could be established, would be the acquisition of knowledge respecting the state of the weather. If the project were carried out, a storm, warning us of an approaching tempest, might be received from the moon, six hours before its arrival, here below.
reply