Not sure about Prolog itself but Datalog really needs to overtake SQL, it's just so much better.
Related areas like constraint programming are still very relevant.
Not sure about Prolog itself but Datalog really needs to overtake SQL, it's just so much better.
Related areas like constraint programming are still very relevant.
Prolog has reached an exciting new milestone with Scryer prolog. It is the first highly performant open source iso-compliant Prolog.
I would check out Markus Triska's work to have your mind blown:
I interviewed and helped hire Mark Thom, the original author of Scryer. I also follow Scryer with interest, even though most of my limited Prolog use has been with SWI Prolog (and one large project with ExperProlog in the 1980s).
One thing to check out: Prolog plays fairly well with Python, providing opportunities for hybrid projects.
To playing well with Python, this was on a front page some time ago: https://arxiv.org/abs/2308.15893
"The Janus System: Multi-paradigm Programming in Prolog and Python"
I am quite pleased with the ability to easily use prolog from within python and vice versa. It makes it now one of the easiest and most expressive solvers to plug into for my tastes. I'm starting to accumulate useful solvers here https://github.com/philzook58/prologsolvers/tree/164297d87f6...
You need to install swi prolog https://www.swi-prolog.org/download/stable and pip install janus_swi
A simple example to get started: https://www.swi-prolog.org/pldoc/doc_for?object=section(%27p...
import janus_swi as janus
janus.consult("path", """
edge(a,b).
edge(b,c).
edge(c,d).
:- table path/2.
path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).
""")
list(janus.query("path(a,Y)."))
On the topic of multi-paradigm programming, including logic programming, Oz/Mozart is an obligatory mention. See CTM and http://mozart2.org/mozart-v1/doc-1.4.0/tutorial/index.html.
The authors were fairly prominent Prolog researchers. It's sad Van Roy is retiring and nobody is taking this forward. AliceML, a StandardML dialect inspired by Oz is also abandonware.
Hey, thanks! That looks cool.
How do you normally use Prolog and Python together? I had looked into embedding logic programming within Python in the past, and found a lack of satisfying options, but maybe I didn't know where to look.
I have two short examples in one of my books that I am currently re-writing. Here is a link directly to the Python+ Prolog interop examples https://leanpub.com/pythonai/read#use-predicate-logic-by-cal...
Thanks for the link. I have played with PySwip (https://github.com/yuce/pyswip), and the MQI looks like a more maintainable approach to integrating SWI-Prolog with Python (https://github.com/SWI-Prolog/packages-mqi).
The biggest source of friction I noticed when playing with PySwip was that because Prolog code was represented as strings, you avoided generating it on the fly. It would be nice to have an embedded DSL for Prolog in Python. (I am thinking something like SymPy or the Pony ORM—https://github.com/ponyorm/pony.)
Do you have any papers comparing Scryer with other prolog systems (like SWI-prolog or SICStus prolog) performance-wise ?
There are some benchmarks here of SWI Prolog's benchmark suite on diffrent Prolog systems by Jan Wielemaker the SWI Prolog author:
https://swi-prolog.discourse.group/t/porting-the-swi-prolog-...
He finds Scryer performs worse, which he does comment on, he also explains some tradeoffs and historic choices in SWI's design which affects its performance. I think I have seen the author of Scryer saying that's not surprising and Scryer is still building up core functionality where SWI has had 30+ years to optimise, but I don't remember where I read that.
SWI has a document explaining some strengths and weaknesses regarding performance: https://www.swi-prolog.org/pldoc/man?section=swiorother
Edit: some discussion on Scryer previously on HN: https://news.ycombinator.com/item?id=28966133
So SWI appears to be more performant, it has an open license, so as per the GGP's claim regarding Scryer in the post above, it must not be ISO-compliant?
That's right; comedian Emo Phillips had a bit about it:
"Once I saw this guy on a bridge about to jump. I said, "Don't do it!" He said, "Nobody understand me." I said, "What's so special about you?"
He said, "I'm a computer guy." I said, "Me too! Desktop, tablet, console, smartphone?" He said "Desktop, mostly", I said "Me, too! Mac, Linux or Windows?" He said, "Any, I'm a programmer." I said, "Me, too! which style? OOP, Imperative, Functional, Logic, Array, Stack" He said, "Logic." I said, "Me, too! What subset? Answer Set Programming, Abductive Programming, Prolog, Datalog?" He said, "Prolog." I said, "Me, too! Conformant with the ISO/IEC 13211-1:1995 (core) standard term syntax for the period character or non-conformant extention decried by members of the ISO/IEC JTC1 SC22 WG17 working group?"
He said, "SWI Prolog 7" I said, "Die, heretic!" And I pushed him over."
- https://news.ycombinator.com/item?id=26624442
or read more seriously here:
- https://www.complang.tuwien.ac.at/ulrich/iso-prolog/SWI7_and...
I can't help.
"Once I saw this guy on a bridge about to jump. I said, "Don't do it!" He said, "Nobody understand me." I said, "What's so special about you?"
He said: "I don't want to jump".
Or maybe the GGP was wrong about performance?
Some default settings in SWI are not ISO-compliant (for example, it uses a string type that does not exist in ISO). But these are minor things that won't usually trip you up when feeding it ISO code. You can set flags to get it to conform in the way you want. And you should set flags whenever you want your ISO Prolog programs to be portable, because the standard is very lax and leaves a lot of things implementation-defined. But it specifies the flags to get implementations into the state you want.
Another table (in the same thread) comparing more systems: https://swi-prolog.discourse.group/t/porting-the-swi-prolog-...
Definitive reference: https://www.urbanautomaton.com/blog/2015/08/10/the-pledge-to...
Prolog is not suitable for any problem domain, although this is more readily apparent for some domains than others.
Fuckin' A.
what does that mean?
It's an except from the article. Getting an explanation out of context is worthless.
Looks fun :D, i think that if i ask my manager to build something out of Prolog i would probably get stab... i mean fired since most of us work in OOP. I would love to be that insane one asking for that :D.
You can use https://logtalk.org for oop in Prolog, use it on top of SWI and you have bidirectional bridges to Python an Java
https://www.swi-prolog.org/FAQ/Python.md
https://www.swi-prolog.org/pldoc/doc_for?object=section(%27p...
Dang, substitute Lisp for Prolog and this describes me. Seriously though - Prolog is an awesome tool to have in your toolbox. I've implemented Prolog-like logic programming solutions in several places in my 40+ years of programming. Like rules for assigning molecular mechanics force field atom types.
Like rules for assigning molecular mechanics force field atom types.
Can you describe a bit more how prolog helped you here? Thanks!
If it's an official production system you want, then use OPS-5, not Prolog!
https://en.wikipedia.org/wiki/OPS5
OPS5 is a rule-based or production system computer language, notable as the first such language to be used in a successful expert system, the R1/XCON system used to configure VAX computers.
The OPS (said to be short for "Official Production System") family was developed in the late 1970s by Charles Forgy while at Carnegie Mellon University. Allen Newell's research group in artificial intelligence had been working on production systems for some time, but Forgy's implementation, based on his Rete algorithm, was especially efficient, sufficiently so that it was possible to scale up to larger problems involving hundreds or thousands of rules.
I used DEC's VAX OPS5 for a couple years about around 1990. I quite liked it, and the later versions had some really nice extensions over Forgy's original design.
Then we discovered that our particular rule base could easily be ported into C using a sequence of nested if/thens that ran much faster, and we stopped using OPS5. It was a great tool for doing the initial development, though.
I only have one thing to say to this man, “hey! Quit stealing my moves!”
Prolog, and Constraint Programming especially are great to have in your toolbox. I’ve done research in the field for years, and my job in the industry today is writing Prolog. There are real issues with Prolog:
- no proper module nor package system in the modern sense.
- in large code bases extra-logical constructs (like cuts) are unavoidable and turn Prolog code into an untenable mess. SWI prolog has single-sided unification guards which tackle this to a degree.
- lack of static and strong types makes it harder to write robust code. At least some strong typing would have been nice. See Mercury as an example of this.
All being said, Prolog is amazing, has a place in the future of programming, and gives you a level-up understanding of programming when you get how the types in every OO program is a Prolog program itself.
I'd advise to not use Prolog as general-purpose programming language, but as an embedded DSL or as a service for the part it's really suited for (if your app involves exploration and search over a large combinatorical space in the first place, such as in discrete optimization in industry, logistics, and finance). You really don't need yet another package manager and pointless premature modularization for modelling your business domains in optimization.
I concur, Prolog particularly excels at being an advanced configuration, embeddable DSL that allows one to express system configurations that would otherwise be not easily possible using a bespoke configuration language or a format. I have used an embedded Prolog core to express complex installation configurations in the past with a great success, and I would do it again for the right problem space.
The cluster autoscaler in Kubernetes uses a constraint solver. It's translating configuration against dynamic, and changing state within the cluster.
Using something like an embedded Prolog or miniKenran as the core of a Kubernetes operator is something I've wanted to try my hands on.
To me this makes Prolog sound like a tool to reach for similar to SQL. Specialized language for asking specific kinds of search or query over your data.
Maybe it's just me but I see a lack of a package manager as a massive, massive pro. I can't stand how seemingly every language has a package manager which requires it's own installation and you have to learn how to use THAT thing and then you need some library off github that does some minor task really well but you can't just download the fucking code, you have to import it via, idk, the Fork-Lyft manager which requires Python 3.3 and the PillJump framework and it's just like, I just want a fucking function to parse JSON, I don't want to saddle my system with 600 MB of shit I don't need.
Old_man_yells_at_cloud.jpg
don't confuse "module system" with "package manager"
You can always just download the code, nobody's forcing you to use a package manager. It just turns out that unless you want to spend most of your life building and fixing other people's code, it's much easier to use the package manager. The inefficiency is the price we pay, but it's worth it.
You write Prolog code for a living? Where? Do you happen to have a story to share? I'm very curious.
> when you get how the types in every OO program is a Prolog program itself
"Any sufficiently complicated type system contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Prolog."
There are a lot of problems that Prolog / Constrain programming will solve very elegantly, and much more easily than imperative languages. I think constraint based programming is seriously under used in the industry, and too many programmers are unaware or unable to write constraint based code. I have always hoped to have just a constrain based programming subsystem in a lot of languages, for those niche cases.
What is it like? 50 years of historic cruft. Questionable whether there are more trip hazards than usefulness for ordinary coding. A fractured community which feels like there are more Prolog systems than Prolog code. Learning Prolog is less "how do I do things in Prolog" and more "how do I contort my things to avoid tripping over Prolog?".
A few dedicated clever people and idealists and dreamers talking about ontologies and building things I don't understand, e.g. the link in https://news.ycombinator.com/item?id=40994780 that could either be genuinely "Prolog is suitable for things no other language is" or "Fusion is 10 years away" or "Perpetual motion is here and so is cold fusion!", I can't tell. But I suspect from the lack of visible activity out in the wider world, closer to the latter than the former. Or perhaps the people able to make use of its strengths are few and far between.
There's a saying about driving to a town which has been hollowed out and is now a road through some empty store fronts and car parks: "there's no there there". The soul of a place is missing, it's no longer a destination, just some buildings on some land. Prolog has the opposite of that, a main road straight past it, few buildings or people, but there is a there there - an attractor, spark of something interesting and fun. Buried in years of cruft. Might be a Siren's call though, a trap - but if it is it appears less dangerous than the LISP one.
What do you mean by LISP as a siren call?
I’ve just started learning clojure and besides the lack of static types (which is pretty harsh for me), it seems like a fun and practical language.
Clojure is probably the most beautiful language I've ever worked with. Nothing is perfect, but Clojure is very simple and elegant.
Only downside is I don't know Java, so some things that should be obvious are opaque to me.
core.logic is pretty neat, too. Especially as it applies to this thread and the ancestor comments.
A few dedicated clever people and idealists and dreamers talking about ontologies and building things I don't understand
I was briefly deeply interested in ontologies via OWL and I suspect Prolog has the same issues that I think plague ontologies in general.
They are a fantastic tool for a system complex enough to be nearly useless. Modelling an ontology for a reasonably complex domain is unreasonably difficult. Not because the tools are bad, but because trying to define concrete boundaries around abstract ideas is hard.
What is a camera? A naive attempt would say an item that takes pictures, but that would include X-rays. Are deep-space radio telescopes cameras? Trying to fix those issues then causes second order issues; you can say it’s something that takes images from the visible light spectrum, but then night vision cameras aren’t cameras anymore.
The reasoning systems work well, they just don’t solve the hard part of designing the model.
Yes, I think that is the experience, for example, in what we called (or call) data science: most of the time is spent in ETLs rather than using ML methods. In a real company linking data difficulty is not technical but time and resource consuming.
your camera example demonstrates that human knowledge is loosely structured and formalized in general, so you can't create strict onthology. One way to work around is to assign some confidence score on statements, so you will have something like that Nikon device is likely camera, and x-ray machine is unlikely camera based on current world model.
Who still has nightmares of infinitely nested parenthesis?
The "magic" of Prolog is built upon two interesting concepts : Unification ( https://en.wikipedia.org/wiki/Unification_(computer_science)... ) and Backtracking ( https://en.wikipedia.org/wiki/Backtracking ).
Often bad teachers only present the declarative aspect of the language.
By virtue of being declarative, it allows to express inverse problems in a dangerously simple fashion, but doesn't provide any clue for a solution. And you are then using a declarative language to provide clues to guide the bad engine toward a solution. Making the whole code an awful mashup of declarative and imperative.
Rules :
- N integer, a integer > 1, b integer > 1
- N := a * b
Goal :
N = 2744977
You can embed such a simple problem easily but solving it is another thing.
The real surge of Prolog and other declarative constraint programming type of language will be when the solving engines will be better.
Unification is limited to the first order logic, high-order logic unification is undecidable in the general case. So we probably will have to rely on heuristics. By rewriting prolog goal solving as a game, you can use deep learning algorithms like alphago (Montecarlo tree search).
This engine internally adds intermediate logical rules to your simply defined problem, based on similar problems it has encountered in its training set. And then solve them like LLM, by picking the heuristically picking the right rule from intuition.
The continuous equivalent in a sort of unification is Rao-Blackwellisation (done automagically by deep-learning from its training experience) which allows to pick the right associations efficiently kind of the same way that a "most general unification algorithm" allows to pick the right variable to unify the terms.
A unique property of Prolog is that, given an answer, it can arrive at the original question (or, a set of questions – speaking more broadly).
Or, using layman terms, a Prolog programme can be run backward.
To be precise, a small number of very small Prolog programs can be run backwards.
There are essentially no significant Prolog programs that are reversible with acceptable efficiency.
the bidirectional (relational) aspect of prolog is what got me into this. I love symmetries so it was a natural appeal even before I learned about logic programming (Sean Parent made a google talk about similar ideas implemented in cpp). That said it's very limited. But I wonder how far it could go. (the kanren guys might have more clues)
Do you see a good way to include backtracking in an imperative programming language?
I can imagine how unification would work, since the ubiquitous "pattern matching" is a special case of Prolog's unification. But I've never seen how backtracking could be useful...
backtracking is perilous in general; logic programming languages have really nice abilities for such but I don't know how to avoid pathological inefficiency.
The continuous equivalent in a sort of unification is Rao-Blackwellisation (done automagically by deep-learning from its training experience) which allows to pick the right associations efficiently kind of the same way that a "most general unification algorithm" allows to pick the right variable to unify the terms.
I don't know how to reconcile this statement about deep learning with my understanding of Rao-Blackwell. Can you explain:
- what is the value being estimated?
- what is the sufficient statistic?
- what is the crude estimator? what is the improved estimator?
Roughly, I think sufficient statistics don't really do anything useful in deep learning. If they did, they would give a recipe for embarassingly parallel training that would be assured to reach exactly the same value a fully sequential training. And from an information geometry perspective, because sufficient statistics are geodesics, the exploratory (hand-waving) and slow nature of SGD could be skipped.
Once you view prolog goal reaching as a game. You can apply Reinforcement Learning methodologies. The goal is writing a valid proof, aka a sequence of picking valid rules and variables assignment.
Value being estimated : The expected discounted reward of reaching the goal. The shorted the proof the better.
The sufficient statistic : The embedding representation of the current solving state (the inner state of your LLM (or any other model) that you use to make your choices). You make sure it's sufficient by being able to regenerate the state from the representation (using an auto-encoder or vae does the trick). You build this statistic across various instances of problems. This tells you what is a judicious choice of variable based on experience. Similar problems yield similar choices.
The crude estimator : All choices of have the same value therefore a random choice, The improved estimator : The choice value is conditioned on the current embedding representation of the state using a Neural Network.
You can apply Rao-Blackwell once again, based by also conditioning one-step look-ahead. (Or at the limit applying it infinitely many times by solving the bellman equation.)
(You can alternatively view each update step of your model, as an application of Rao-Blackwell theorem on your previous estimator. You have to make sure though that there is no mode collapse.)
You don't have to do it explicitly, it happens under the hood by your choice of modelisation in how to pick the decision.
The problem with Prolog is that it's based on unification, and small unification engines can be expressed in a few lines in any functional programming language.
That narrows down the already small niche where one would choose Prolog by probably a few orders.
Is this in the same sense that "one could write lisp in 99 lines of c"?
In my opinion, this does not imply that proper lisp (and correspondingly prolog) implementations are useless, just because a simple implementation can be written in a different, "more expressive" language.
No, not really. A lisp in 99 lines of C would barely be useful. In contrast, Prolog mostly shines where you need reasoning/unification over a database of facts -happens pretty often,- but that's just too easily expressed in any proper functional language. And with a bit more pain in an imperative/OO language.
There is a very practical embedable logic-programming engine called miniKanren for many programming languages that can be used to add the logic-programming techniques of Prolog to other languages.
https://en.wikipedia.org/wiki/MiniKanren
There's a great book in the same series as the "Little Lisper"/"Little Schemer" books called "The Reasoned Schemer" that uses MiniKanren with Scheme.
I've been using Prolog daily for the past 1.5 years. I've also implemented and used a Kanren in Elm, and there is simply a world of practical difference.
expressed in a few lines in any functional programming language
I don't think that performs like a proper Prolog engine on larger problem.
Real Prologs work by compiling to something called the WAM (Warren Abstract Machine).
For some, how a language is implemented seems to be the paramount thing.
For many, how the language faces the user, how its paradigms fit the problems at hand and the user's mode of seeing the world, that is more important.
These days, with the terabytes the petaflops and the megajoules, it might be even less relevant how the gears are turning inside the black box.
Prolog itself is still developed and used in various settings (mostly swi-prolog?), but other languages and logic engines solve domain specific but similar problems better (rule engines, formal proof verifiers, etc). For exploratory work it can be useful.
I have tried to use it in combination will LLMs unsuccessfully, partly because the domain was not specific enough. Otherwise you need a lot of real world knowledge and a large fact database.
Logic engines for first order logic in RDF/OWL also have interesting logical inference abilities, like graphdbs.
Any programming language can do "logic" and the work at MIT/CSAIL in probabilistic programming may turn out to be a better way to combine fuzzy logic and formal proofs.
Not sure this answers your question, but maybe this points towards some interesting directions.
Any answer here is a good one since the question is soooo unspecific :D. My professor is a staunch advocate for RDF/OWL, inference engines and stuff like that (hence why i also mentioned ontologies :D).
The thing is that i think that the language itself has so much untapped potential and the world that i dived into with my studies is so vast, so full of stuff that it left me kind of dazed to be fair!
I got some papers in regards to knowledge representation (that to be fair i still have to read... exams and work got in the midst of all :/) but still it seems so... odd: when we were studying OOP in my bachelor we went over the usual examples that made you understand "this is not an imperative paradigm but there are object abstractions" while, in my studies, prolog and logic programming in general was seen as a tool of sorts for reaching an objective like "hey we have a MAS system, let's sprinkle some prolog in it for fun :D" (maybe i am exaggerating but it feels like this lol). I feel it can do much much more
You are definitely on to something here. OOP has some common roots with formal ontologies and knowledge representation (not so much the programming languages, but object oriented modeling). OO fails at this for various reasons, whereas logic is tailored for this specific purpose. Check out ErgoAI (formerly Flora-2), it's the most advanced Prolog flavor for representing and reasoning over knowledge. https://github.com/ErgoAI
you guys are giving me so much to read thanks <3 i'll give this a check when i have some time out of exams/work. I will surely check ErgoAI
If you want to see something truly fascinating, take apart https://logtalk.org/ - it implements an OO system for prolog which gives you all sorts of advantages (the least of which being a not-terrible way of getting namespaces).
Reading "The Art of Prolog" and "The Craft of Prolog" was fun for me, as was learning how the Warren Abstract Machine works.
(I am not at all a prolog expert, merely a programmer who happens to be fascinated by it, so this is all dabbling on my end but hopefully provides some stuff that's fun to learn for you as well)
Hi! Are you Jim Hendler (or related to him), my Reagan-era AI professor from UMD?
https://en.wikipedia.org/wiki/James_Hendler
My Prolog programming assignment #4, a Prolog "nehcihsahA" detector (maternal uncle: a mother's brother, or any equivalent relative) seemed designed to make me hate Prolog with a passion, involving bending over backwards by defining ridiculous predicates like siblish, sibloid, relatoid, sistoid, brothoid, mothoid, and fathoid.
https://www.donhopkins.com/home/code/nehcihsaha.prolog.txt
I much more enjoyed the OPS-5 programming assignment #6, for which I made a worm simulation that hacked into Ollie North's Intimus-007s ("the ace of security paper shredders") in the White House basement, via Professor Hendler's Sun workstation dormouse, rms's account with password rms on prep, and Casper Weinberger's account on UMD's Vax 11/780 mimsy and NSA's PDP-11/70 tycho, connected via the NSA's MILNET IMP 57 at Fort Mead, then posted Ollie North's secret diary and notes it found in the paper shredder to talk.rumors via the UCB-Vax usenet gateway.
https://www.donhopkins.com/home/code/crack-ollie.ops5.txt
https://news.ycombinator.com/item?id=18376750
At the University of Maryland, our network access was through the NSA's "secret" MILNET IMP 57 at Fort Mead. It was pretty obvious that UMD got their network access via NSA, because mimsy.umd.edu had a similar "*.57" IP address as dockmaster, tycho and coins. [...]
My Prolog programming assignment #4, a Prolog "nehcihsahA" detector (maternal uncle: a mother's brother, or any equivalent relative) seemed designed to make me hate Prolog with a passion, involving bending over backwards by defining ridiculous predicates
Your attempt at a solution definitely defines ridiculous predicates, but you should not blame that on your teacher or the language. For example, there is no way that defining "a mother's brother" would need to refer to a "same sex" predicate in any way. You took a wrong turn somewhere with your approach, but again it's neither the language nor your teacher that forced you down that path.
Not quite what you asked for, but as someone using it quite a lot back in the late '80s during a CS&AI degree, Prolog has its interesting features and I'm glad I used it, but I haven't missed it since. I do like declarative stuff, eg CSS!, and that remains a good memory.
could you please expand on it? i would love to read more
Many many languages that you will encounter and use in live projects are primarily imperative, eg: C, C++, JavaScript. The describe the "how" and "in what order".
While I was an undergrad I was exposed to Standard ML and Prolog, both of which were/are much more about declarative "what", though they could only practically interact with the actual world by side-effects and some imposed ordering (SML's 'ref', Prolog's cut).
I am still waiting for some of the amazing stuff that was in SML to materialise in C++ and Java for example, less so anything from Prolog. For example, to search a state space I might use an off-the-shelf solver with good heuristics and an objective function written in something imperative rather than use Prolog.
But it it really is over 30Y since I touched Prolog, so life in it may be very different now.
Pretty interesting stuff, thanks for sharing :D
I'm not the commenter you're replying to, but in my case, I really enjoy the promise of "you write down the problem, not the solution".
In an introductory prolog course you will soon find that when a prolog program is written to solve some problem like 'whats-the-next-chess-move' it's actually doing a depth first (and if you use the ! cut-operator, it will stop looking for any more solutions).
But in principle, it's up to the interpreter/compiler to decide how to find solutions. In the same way that a C compiler might say "ah, you're doing tail-recursion, let me make a loop out of that", a prolog compiler might say "gee, this problem looks like it would be much more efficient to use simulated annealing to find some answers in a shorter time". That's perhaps a bit far-fetched, but a great example is Datalog which has solvers that parallelize the search. You don't write a parallel algorithm, it's just that a parallel algorithm is used to solve your problem.
A specific feature I miss in other programming approaches is that if you can find the answer to the question "is A a child of B?", the very same code is also the function to find out all of A's children, or all of B's parents. No need to explicitly code a loop, or to create the inverse function.
Speaking of CSS, :has() [https://developer.mozilla.org/en-US/docs/Web/CSS/:has] brings it closer to the glory of Prolog. I cannot wait to abuse it in avant-garde Logic-Driven-Development.
Shameless plug: you should check out my podcast The Search Space for a view of the broader landscape of Prolog and logic programming: https://thesearch.space/
I don't publish episodes often but I have a lot of good interviewees lined up :)
In general, I would advice you to look beyond Prolog and explore Answer Set Programming, the Picat language, and the connections between logic programming and databases (SQL, RDF or otherwise). Not instead of Prolog, but in parallel. Prolog is awesome!
ASP is in another uni course of mine ;). I'll check the podcast, thanks
Good to know there is further content lined up! I’m subscribed and eagerly waiting for it!
I'll second the plug: it's an excellent podcast
thanks for the thread for allowing to find you and you for making the interviews
With compliments to your prof ;), interest in Prolog just now is recovering from a year-long focus on W3C's RDF/SPARQL. TBL surely had an itch to scratch with regards to logical knowledge representation dating back even longer than the web [1]. But Prolog has broader applicability not only in logical/knowledge graph querying, but also in solving all kinds of discrete combinatorical optimization problems. Or, as the Quantum Prolog site [2] puts it, "planning, optimization, diagnostics, and complex configuration." The site demos logistics optimization (in-browser demo) and reports initial optimization (parallelization) of Inductive Logic Programming and other ML tasks for partially auto-generating Prolog code from existing solutions.
Edit: ... and on performance vs SWI Prolog, too
The problem w/ OWL is that everybody wants to work with first-order logic + math, but Gödel proved it isn't decidable.
For instance if I wanted to express financial regulations or business rules inside a bank or other business I'd need to use math: for instance to express the conditions for reserve requirements or approving a loan.
OWL is best thought of as a set of templates for generating first-order logic rules that are decidable and also (in theory) quick to evaluate with the Tableau algorithm.
In certain domains you might tolerate tools that are imperfect, like it isn't fair to expect a SMT solver to figure out this one
x^N + y^N = z^N
where x,y,z and N are all positive integers with N>2. For that one it would try to find solutions and probably time out. For some similar problems (a different polynomial) it might give you an answer.OWL doesn't want to go there which is a big reason people say "Nein Danke!"
Gödel proved it isn't decidable.
He did no such thing. He proved undecidable problems exist in any system powerful enough to be useful. That doesn’t make those systems useless, though.
The trouble is the creators of OWL wanted to have performance and reliability bounds. That is, they want to make systems that act like more like a conventional database server than an SMT solver.
I think they could have made a more expressive standard and something like that might have had more appeal to people but been less consistent in terms of performance.
My professor swapped Prolog out for Rust at the last minute. I don't know whether he did us a disservice or a favor.
What a curious swap. May I ask which course he taught?
It was a whirlwind "survey of languages" course. After blowing our minds with functional programming via OCaml, the last segment was traditionally logical programming via Prolog. But he decided to spare us, I guess, and made me fall in love with Rust for a few years. :p (Or he sadistically meant to inflict the trauma of knowing how much better C and C++ could be but never will be, which stays with you even after you stop using Rust and return to those.)
That is my point, i think that prolog isn't just a simple tool to solve stuff, i think that it's potential can still be explored (even if, to be fair, Rust can run on a functional paradigm setting)
Girard has some commentary scattered about his writing.
The search algorithms for logic programming are simply slow, it's a very interesting idea in programming languages, but there's a reason it's not widely used.
PROLOG, its misery. Logic programming was bound to failure, not be- cause of a want of quality, but because of its exaggerations. Indeed, the slogan was something like « pose the question, PROLOG will do the rest ». This paradigm of declarative programming, based on a « generic » algorithmics, is a sort of all-terrain vehicle, capable of doing everything and therefore doing everything badly. It would have been more reasonable to confine PROLOG to tasks for which it is well-adapted, e.g., the maintenance of data bases.
On the contrary, attempts were made to improve its efficiency. Thus, as systematic search was too costly, « control » primitives, of the style « don’t try this possibility if... » were introduced. And this slogan « logic + control13 », which forgets that the starting point was the logical soundness of the deduction. What can be said of this control which plays against logic14? One recognises the sectarian attitude that we exposed several times: the logic of the idea kills the idea.
The result is the most inefficient language ever designed; thus, PROLOG is very sensitive to the order in which the clauses (axioms) have been written.
This is a great quote and sadly true. What text is this from?
"The Blind Spot: Lectures on Logic" by Jean-Yves Girard
Though i only know Prolog cursorily it is in my todo list of languages to study. I think it has great value in that it teaches you a different paradigm for programming.
You might also want to look at Erlang which is used in the Industry and would be helpful for your future. Joe Armstrong was originally inspired by Prolog and he conceived Erlang as Prolog-Ideas+Functional/Procedural+Concurrency+Fault-Tolerance. Hence you might find a lot of commonalities here. Here is a recent HN thread on a comparison - https://news.ycombinator.com/item?id=40521585
There is also "Erlog" (by Robert Virding, one of the co-creators of Erlang) which is described as, Erlog is a Prolog interpreter implemented in Erlang and integrated with the Erlang runtime system. It is a subset of the Prolog standard. An Erlog shell (REPL) is also included. It also says, If you want to pass data between Erlang and Prolog it is pretty easy to do so. Data types map pretty cleanly between the two languages due to the fact that Erlang evolved from Prolog. - https://github.com/rvirding/erlog
Sure, Erlang was prototyped on Prolog because Prolog has excellent built-in facilities for domain-specific languages: you can define new unary or binary operators along with priorities and associativity rules (you can use this to implement JSON or other expression parsing in like two lines of code, which is kindof shocking for newcomers, but is very handy for integrating Prolog "microservices" in backend stacks), and you get recursive-decent parsing with backtracking for free as a trivial specialization of Prolog evaluation with a built-in short syntax (definite clause grammars) even.
But apart from syntax, Erlang has quite different goals as a backend language for interruption-free telco equipment compared to Prolog.
Ha! That explains a lot. I've started looking into Prolog recently, and there were some... familiar echoes in there, reminiscent of Erlang.
But of course, the submarine is like a cigar, not cigar like a submarine.
No idea, but it might be worth looking into Mercury and {mini,micro}Kanren/core.logic as more practical iterations on it (either by adding things to Prolog or extracting the interesting to stuff to use in more general purpose languages).
At the end of the day "practical" means library support and community knowledge, by which measure Prolog and more specifically SWI and Sicstus are far more practical than any of the other logic languages or implementation options
Well if your problem does not require a solution that’s 100% written in prolog, then any relational/CLP system that can be hosted or work as a library is going to win in terms of library support and community knowledge, at solution level.
So e.g. a core.logic solution can make extensive use of the jvm ecosystem.
I would say in the open source world, SWI Prolog is still the king implementation, in regards to tooling, language features beyond ISO Prolog, and toolchains.
i've been aware of that for a while, it seems to be the state of the art at least in my university (to the point that to this day the researchers are trying to convert old prolog projects to this implementation)
There are certain (academic) problems for which Prolog is simply the best tool for the job, see e.g., https://github.com/hbrouwer/dfs-tools
(academic)
Ah, for a second I thought someone just found a way to make Prolog useful for something. What a terrifying thought indeed, luckily the crisis has been averted, the natural order is restored and all is well.
You might be interested in reading about the Japanese "Fifth Generation Computer Systems" project from 1982, which revolved around PROLOG.
https://en.wikipedia.org/wiki/Fifth_Generation_Computer_Syst...
The Fifth Generation Computer Systems (FGCS; Japanese: 第五世代コンピュータ, romanized: daigosedai konpyūta) was a 10-year initiative begun in 1982 by Japan's Ministry of International Trade and Industry (MITI) to create computers using massively parallel computing and logic programming. It aimed to create an "epoch-making computer" with supercomputer-like performance and to provide a platform for future developments in artificial intelligence. FGCS was ahead of its time, and its excessive ambitions led to commercial failure. However, on a theoretical level, the project spurred the development of concurrent logic programming.
The term "fifth generation" was intended to convey the system as being advanced. In the history of computing hardware, there were four "generations" of computers. Computers using vacuum tubes were called the first generation; transistors and diodes, the second; integrated circuits, the third; and those using microprocessors, the fourth. Whereas previous computer generations had focused on increasing the number of logic elements in a single CPU, the fifth generation, it was widely believed at the time, would instead turn to massive numbers of CPUs to gain performance.
[...]
Concurrent logic programming
In 1982, during a visit to the ICOT, Ehud Shapiro invented Concurrent Prolog, a novel programming language that integrated logic programming and concurrent programming. Concurrent Prolog is a process oriented language, which embodies dataflow synchronization and guarded-command indeterminacy as its basic control mechanisms. Shapiro described the language in a Report marked as ICOT Technical Report 003,[7] which presented a Concurrent Prolog interpreter written in Prolog. Shapiro's work on Concurrent Prolog inspired a change in the direction of the FGCS from focusing on parallel implementation of Prolog to the focus on concurrent logic programming as the software foundation for the project.[3] It also inspired the concurrent logic programming language Guarded Horn Clauses (GHC) by Ueda, which was the basis of KL1, the programming language that was finally designed and implemented by the FGCS project as its core programming language.
The FGCS project and its findings contributed greatly to the development of the concurrent logic programming field. The project produced a new generation of promising Japanese researchers.
https://www.sjsu.edu/faculty/watkins/5thgen.htm
The Japanese Fifth Generation project was a collaborative effort of the Japanese computer industry coordinated by the Japanese Government that intended not only to update the hardware technology of computers but alleviate the problems of programming by creating AI operating systems that would ferret out what the user wanted and then do it. The Project chose to use PROLOG as the computer language for the AI programming instead of the LISP-based programming of the American AI researchers.
The Japanese National Fifth Generation Project: Introduction, survey, and evaluation:
https://stacks.stanford.edu/file/druid:kv359wz9060/kv359wz90...
Abstract:
Projecting a great vision of intelligent systems in the service of the economy and society, the Japanese government in 1982 launched the national Fifth Generation Computer Systems (FGCS) project. The project was carried out by a central research institute, ICOT, with personnel from its member-owners, the Japanese computer manufacturers (JCMs) and other electronics industry firms. The project was planned for ten years, but continues through year eleven and beyond. ICOT chose to focus its efforts on language issues and programming methods for logic programming, supported by special hardware. Sequential 'inference machines' (PSI) and parallel 'inference machines' (PIM) were built. Performances of the hardware-software hybrid was measured in the range planned (150 million logical inferences per second). An excellent system for logic programming on parallel machines was constructed (XLI). However, applicationswere done in demonstration form only (not deployed). The lack of a stream of applications that computer customers found effective and the sole use of a language outside the mainstream, Prolog, led to disenchantment among the JCMs.
Japan's Fifth Generation Computer Systems: Success or Failure?
https://www.reddit.com/r/prolog/comments/owb0xg/japans_fifth...
https://instadeq.com/blog/posts/japans-fifth-generation-comp...
This post is a summary of content from papers covering the topic, it's mostly quotes from the papers from 1983, 1993 and 1997 with some edition, references to the present and future depend on the paper but should be easy to deduce. See the Sources section at the end.
[...]
Prolog vs LISP
Achieving such revolutionary goals would seem to require revolutionary techniques. Conventional programming languages, particularly those common in the late 1970s and early 1980s offered little leverage.
The requirements clearly suggested the use of a rich, symbolic programming language capable of supporting a broad spectrum of programming styles.
Two candidates existed: LISP which was the mainstream language of the US Artificial Intelligence community and Prolog which had a dedicated following in Europe.
LISP had been used extensively as a systems programming language and had a tradition of carrying with it a featureful programming environment; it also had already become a large and somewhat messy system. Prolog, in contrast, was small and clean, but lacked any experience as an implementation language for operating systems or programming environments. [...]
Fun Trivia
The one commercial use we saw of the PSI machines was at Japan Air Lines, where the PSI-II machines were employed; ironically, they were remicrocoded as Lisp Machines.
See also here for an actively maintained and relatively portable implementation of Flat GHC, Strand and PCN for UNIX systems:
http://www.call-with-current-continuation.org/fleng/fleng.ht...
Eclipse CLP still seems slightly active: https://eclipseclp.org/. I used it for some process scheduling research in the early 2000s but I've never had the chance to apply it in the non-academic world
There is still academic work on Prolog, and more broadly deductive / logic programming. If you are looking at things with a more industrial bent, I would look to Datalog which trades generality in Prolog for performance and predictability. Alternatively, you can go the other way and look at lambdaProlog which adds real abstractions / HOFs to Prolog.
What I've seen in practice is that while Prolog may be good at describing a solution, its performance is often too lackluster and brittle for actual deployment: it probably fits more as a prototyping language before you do a classic implementation of the solution in a more traditional language.
There are a few magical algorithms/systems which give you superpowers if you can find the right application for them. At least in the pre-LLM era, they were some of the magical tools we had, for just solving declaratively specified difficult problems without us explicitly writing code, while (unlike certain AI techniques which shall remain nameless) providing correctness guarantees and often being deterministic and stable.
Prolog and logic programming is one, together with its relative, constraint logic programming, and its relative mixed integer programming, which in turn is part of the broader linear and convex programming family.
What else should we put in that category?
To piggyback onto OP to ask about something very loosely related: what about miniKanren? Are there any active projects or work being done here, either in academia or industry? Most of the ones listed on minikanren.org appear to be dead -- although I haven't gone through them all since last year
You may find this paper interesting: https://www.cambridge.org/core/journals/theory-and-practice-...
title: Fifty Years of Prolog and Beyond (2022)
The most recent prolog news I've come across in recent years is some updates to SWIprolog (can't find a good link) and some talk of Scryer-prolog[0] which is a more recent implementation of Prolog in Rust.
One interesting development recently is a load of research into, reverse engineering of and emulation of the 1986 Sega AI Computer[1], which used prolog under the hood for mostly educational software. Unfortunately it does not seem there is a way to actually write some prolog for the thing today :(
It's a powerhouse, an even bigger secret than Lisp at beating the average.
If you are interested in small fun stuff, SWI-Prolog has network libraries. Just recently, I implemented a network gomoku (5-in-a-row) game in it for my school project: https://gitlab.mff.cuni.cz/volfmat1/prolog-network-gomoku. Turns out you can also write quite imperative-style code with it :D
I have been interested in Prolog since my time at the University, and I loved the idea of logic programming.
For "proper" Prolog, in 2024 it is a niche language alive in specific constraint solving applications, but not really used outside of that. I haven't seen anyone attempting at using prolog as a general purpose language since the 90'.
Datalog and logic-inspired languages tend to pop up here and there as domain-specific languages.
Rego is a recent incarnation which had good adoption for k8s and other "modern" systems. However, when trying to get people in my org to adopt it in practice, I saw engineers struggle with the paradigm when complexity grows to more than toy problems.
It's great to hear new people are interested in the language! I was enlightened a couple years ago and fell in love.
Currently I'm focusing on creating easy-to-use embeddings of Trealla Prolog using Wasm. You can find my TypeScript library here: https://github.com/guregu/trealla-js and Go library here: https://github.com/trealla-prolog/go. The goal is to make the libraries as painless as possible. Trealla is a portable and lightweight Prolog written in C that supports CLP(Z) and is broadly compatible with Scryer. It's quite fast! I'm currently using it for some expert system stuff at $work and as an internet forum embedded scripting language for $fun.
Speaking of Scryer, they recently got their WebAssembly build working and I hope to contribute a JS library for them in the future as their API stabilizes. Scryer and Trealla are both aiming for ISO compatibility, so it's my hope that we can foster an ecosystem for modern ISO Prolog and provide more embeddings in the future. It's super convenient to get logic programmer superpowers in your favorite language. Also check out Scryer's new website: https://www.scryer.pl/
For something on the silly side, check out https://php.energy. Prolog Home Page, it's web scale :-). It's proof that you can integrate Prolog with bleeding edge stuff like Spin (server-side wasm ecosystem).
I think of Prolog as a general purpose logic programming language and Datalog to be logic programming more focused on data analysis. Data analysis is a very large area, so boundary might get blurry at times.
If your data is in a relational database consider Logica - a Datalog family language that compiles to SQL and runs naturally on SQLite, Postgres, DuckDB and Google BigQuery.
Easy to install, easy to play with in CoLab or any other Jupyter notebook.
Works for data analysis (aggregation, filtering etc) that is commonly associated with SQL, as well as recursive logical querries commonly associalted with Logic programming per-se.
Here is what it looks like for a data-analysis-ish query of finding popular baby names over time:
# Count babies per year.
NameCountByYear(name:, year:) += number :- BabyNames(name:, year:, number:);
# For each year pick the most popular.
TopNameByYear(year) ArgMax= name -> NameCountByYear(name:, year:);
# Accumulate most popular name into a table, dropping the year.
PopularName(name: TopNameByYear());
The classic grand-parent rule looks as usual:
Grandparent(a, c) :- Parent(a, b), Parent(b, c);
Here is a recursive program for finidng distances in a directed graph:
D(a, b) Min= 1 :- Edge(a, b);
D(a, b) Min= D(a, x) + D(x, b);
Links to CoLabs:
Grandparent, ancestor: https://colab.research.google.com/drive/1lujnnUOXsF6VrC9__jV...
Distance in graph:
https://colab.research.google.com/drive/1sOCODHqN0ruxZSx_L-V...
Github repo: https://github.com/EvgSkv/logica
Tangent to Prolog, perhaps check Flix, which includes logic programming features [1], and is discussed here from time to time [2].
--
1: https://doc.flix.dev/fixpoints.html
2: https://news.ycombinator.com/item?id=25513397
Not exactly a prolog, but Verse, a logical (and functional, or functional logic) programming language developed at Epic Games by Simon Peyton Jones of Haskell fame and Tim Sweeney. You can already use it to build mods for fortnite or something like that not really sure. But there's no open source compiler available yet.
The CLP (constraint logic programming) systems available in some Prologs take it to the next level: https://us.swi-prolog.org/pldoc/man?section=clp
I've actually been thinking about this quite a bit. I remember a foray into prolog when I was a younger pup in 2004-6. With the Advent of llms, I think that perhaps we could use llms to extract triples from large corpuses of text and then use that to build our prolog stores or ontologies and work on them. I haven't really experimented much with it but you saying this has reminded me that I should dig that back up again.
Don't forget the Datalog subset!
In the 2000s I was interested in inference over RDF and wanted something a bit more than RDFS and OWL and found out about Datalog:
https://en.wikipedia.org/wiki/Datalog
There wasn't a lot of literature on it or implementations then but a few years later people realized it's a great query language for complex queries that does a great job on transitive closures, can do math (unlike OWL which won't do it because Gödel proved first order logic + math is a hot mess)
I took a comparative programming languages course circa 1993, the instructor thought that that Prolog was a taste of the future of programming. At first I thought the way you can implement ordinary procedural code in Prolog was really clever but if you write very much of it I think it is awkward; for instance it is common to treat procedural success as a logical failure because that gets the behavior you want.
It's counterintuitive that you could write a reasonably fast interpreter for Prolog but Warren figured out how to do it and it really is a neat trick. In the 1980s the Japanese Fifth Generation project dreamed about parallel Prolog on a machine with 100s of CPUs but it was discovered pretty quickly that you couldn't really parallelize Prolog execution so they came up with the less expressive language
https://en.wikipedia.org/wiki/KL1
I am amused to see papers today where people are working on tasks similar to what they worked on in that project, parallelizing them with commodity hardware, and get scaling curves that look very similar to what was done with KL1. (In the end the 5GP settled on the same message-passing architecture that everybody else did until the GPU revolution came)
One of the nicest examples in Prolog is writing a parser by just writing the productions which works because Prolog's resolver is quite similar to a common parsing algorithm. In the large however, you can add a library to a normal programming language like Python or Java where you write the same grammar in a DSL and it is handled by the library.
See also production rules systems which use "forward chaining" with the RETE algorithm and variants for an approach which looks like Prolog in some ways but works in the reverse direction. My favorite example of this now is
I built a prototype of a stream processing engine where the control plane was implemented as a set of production rules that would build a processing pipeline of reactive operators, key-value and triple stores and then tear it down. Unlike another stream processing engine I worked on, mine always got the right answers. I think a production rule system could be the target of a "low code" system. I'm a little disappointed that I've never seen a Javascript framework that uses production rules because they are a great answer to asynchronous communication choreography. (See complex event processing)
I've brushed up against it in the form of datalog as the query language for databases like datomic and xtdb, so it's soul is alive and well!
I'm also considering a prolog like domain specific language to make a state syncing engine with pure declarations of how the state in system A is reflected in System B, etc.
Prolog itself may not be mainstream, but it is an answer to a the universal problem space of constraint solution, so comp sci will always be in its long shadow.
I chose to use prolog to essentially build an expert system across and heterogeneous data ecosystem.
Prolog could certainly use some serious improvements to its tooling. But the language is simple enough that it doesn't prove too much of an issue. You can get some much out of language it can be very powerful. In the system we've built it makes up a purely logical core that is completely referentially transparent, we leave all the ecky side effecting to a host program.
My honest opinion is to avoid Prolog for most enterprise needs in favor of a regular general purpose programming language that calls out to a mathematical or constraint solver via API when the need arises. This way you get a language that is easier to learn with a strong ecosystem of libraries along with a solver that is built for your particular problem.
Prolog may excel in some niche cases that are documented out there which is fine. For the majority of cases I can think of...it is too esoteric.
Prolog is SUPER cool though as is it's history. You should definitely play with it a bit.
With ChatGPT it is a great time to learn new programming languages.
Questions such as "give me table with a glossary of basic Prolog terminology with examples" as well as others can be helpful.
Could you explain more or point out some interesting references? I'm currently trying to understand how Datalog compares to SQL and, potentially GraphDBs
Prolog and Datalog example (they are identical in this case)
The Prolog code looks identical to Datalog but the execution model is different. Prolog uses depth-first search and backtracking, which can lead to infinite loops if the rules are not carefully ordered.Datalog starts by evaluating all possible combinations of facts and rules. It builds a bottom-up derivation of all possible facts:
a. First, it derives all direct parent relationships.
b. Then, it applies the ancestor rules iteratively until no new facts can be derived.
For the query ancestor(john, X):
It returns all X that satisfy the ancestor relationship with john. This includes mary, ann, and tom. The order of rules doesn't affect the result or termination. Datalog guarantees termination because it operates on a finite set of possible facts.
Prolog uses a top-down, depth-first search strategy with backtracking.
For the query ancestor(john, X):
a. It first tries to satisfy parent(john, X). This succeeds with X = mary.
b. It then backtracks and tries the second rule: It satisfies parent(john, Y) with Y = mary. Then recursively calls ancestor(mary, X).
c. This process continues, exploring the tree depth-first.
Prolog will find solutions in this order: mary, ann, tom.
The order of clauses can affect both the order of results and termination: If the recursive rule were listed first, Prolog could enter an infinite loop. Prolog doesn't guarantee termination, especially with recursive rules.
SQL is more verbose. The equivalent of the Datalog/Prolog example above is:
This is a more interesting example of how one might use Datalog on a large dataset: The equivalent Postgres example would be: Full example you can run yourself: https://onecompiler.com/postgresql/42khbswatIs this an issue in practice? Most languages can create programs with infinite loops, but it's easy to spot in code reviews. It's been over a decade since I encountered an infinite loop in production in the backend. Just wondering if the same is true for Prolog.
Take the infinite loop as just an example of an issue with depth-first search and backtracking. To be more general, I'd say that the issue is that the overall performance of a Prolog program can be very dependent on the ordering of its rules.
As an anecdote, a long time ago for a toy project switching two rules order got the runtime to finding all solutions from ~15mn to a around the second (long time, memory fuzzy...). The difference was going into a "wrong" path and wasting a lot of time evaluating failing possibilities, vs. taking the right path and getting to the solutions very quickly.
So in practice even if Prolog is declarative to get good results you need to understand how the search is done, and organize the rules so that this search is done in the most efficient way. The runtime search is a leaky abstraction in a way ;)
It's not an issue limited to Prolog, many solvers can be helped by steering the search in the "right" way. A declarative language for constraint problem like MiniZinc provides way to pass to the solver some indication on how to best search for example.
Also, most modern Prolog support tabling, which departs from strict DFS+backtracking and can help in some cases. But here too, to get the best results may require understanding how the engine will search, including tabling.
Infinite loops in Prolog can appear with very subtle changes in the use of code.
One of the core problems is related to the reversible nature of Prolog. Not only are some programs reversible and some are, practically speaking, not, there are many gradations on this.
The result is that programs that look equivalent and whose tests appear equivalent may exhibit non-termination in surprising ways. This is, in my experience, the rule rather than the exception with Prolog.
Here's an infinite loop in Prolog, getting the length of a list:
Oops, List_of_animals hasn't been bound to any value, so length/2 will backtrack forever making it a longer and longer list of empty placeholders. Nothing will warn you that the variable wasn't declared because that's also a normal thing to do. Here's another, checking if something is in a list: same problem, if the list isn't grounded to a fixed length list by the time this line executes, backtracking will generate longer and longer lists with `cat` in them and lots of placeholders: forever. It's not just that you can accidentally write an infinite for(;;) loop by typoing the exit condition, it's that a lot of things in Prolog can be used in ways which finish deterministically or in ways that act a bit like Python generators yielding endless answers. So it's about the context in which you call them, and the surrounding code. e.g. one reason you're using Prolog is that you want it to generate List_of_animals for you (making up fictional animal names, or something), so you can't look for a missing `List_of_animals = [...]` because there might not be one anywhere.There are classes of infinite loops that are harder to spot for beginners, it takes a while to really understand the execution model.
Prolog variables can have two states at runtime: unbound or bound. A bound variable refers to some value, while an unbound variable is a "hole" to be filled in at a later time. It's common to pass an unbound variable into some call and expect the callee to bind it to a value. This can cause problems with infinite recursion where you intend to write a call that binds some variable, but the way you've structured your program, it will not actually bind it. So the callee ends up in the same state as the caller, makes a recursive call hoping its callee will bind the variable, and down the infinite recursion you go. With experience you can definitely spot this in code review. You'll also catch it in testing, if you test properly. But it's different enough from other languages that learners struggle with it at first.
Another source of (seeming) nontermination is when you ask Prolog's backtracking search to find an answer to some query in a search space that is too large and may not contain an answer at all, or only an answer that is impracticably far away. This is also sort of Prolog-specific since in other languages you rarely write the same kind of optimistic recursive search. This is harder to spot in code review since it's really application-specific what the search space looks like. But again, you test. And when in doubt, you direct and limit the search appropriately.
Yes.
It is trivially easy to create loops of rules when describing abstract properties.
Concrete properties tend to have "levels" to them, but many human concepts are self-referential.
In this way, its possible to spot that there may be an issue now or in the future, because the presence or lack of a loop depends on the specific choice of dependencies of a concept. However spotting the potential for a loop doesn't do a lot to help remove its potential existence, or show that it is there or not there.
How does the Datalog approach compare with RETE?
The big deal about Datalog is that it is equivalent to SQL-with-recursion. Thus, it can compile to database queries.
Don't have any interesting references, sorry. My reasoning is mainly one of simplicity and power. In SQL you need to think in terms of tables, inner joins, outer joins, foreign keys etc. whereas datalog you do everything with relations as in prolog.
Not only is it conceptually much simpler, it's also a "pit of success" situation as thinking in terms of relations instead of tables leads you towards normal forms by default.
Add the ability to automatically derive new facts based on rules and it just wins by a country mile. I recommend giving Soufflé a try.
I haven't worked with GraphDBs enough to comment on that.
TypeDb is a practical Datalog-based database system [1] (with a different syntax). TerminusDb is a project in a similar vein [2], but actually an RDF store at its core. If you want to experiment with the connections between Datalog, relational algebra, and SQL, check out the Datalog Educational System. And if you want to jump into the theory, Foundations of Databases (the "Alice book") is very thorough but relatively readable [4]! Oh, and there's a Google project, Logica, to do Datalog over Postgres databases [5].
[1]: https://typedb.com/ [2]: https://terminusdb.com/ [3]: http://www.fdi.ucm.es/profesor/fernan/des/ [4]: http://webdam.inria.fr/Alice/ [5]: https://github.com/evgskv/logica
Mangle is a language that includes "textbook datalog" as a subset https://github.com/google/mangle ; like any real-world datalog language, it extends datalog with various facilities to make it practical.
It was discussed on HN https://news.ycombinator.com/item?id=33756800 and is implemented in go. There is the beginnings of a Rust implementation meanwhile.
If you are looking for datalog in the textbooks, here are some references: https://github.com/google/mangle/blob/main/docs/bibliography...
A graph DBs short intro to datalog: just like the edges of a graph could be represented as a simple table (src, target), you could consider a database tuple or a datalog or prolog fact foo(x1, ..., xN) as a "generalized edge." The nice thing about datalog is then that as one is able to express a connections in an elegant way as "foo(...X...), bar(...X...)" (a conjunction, X being a "node"), whereas in the SQL world one has to deal with a clumsy JOIN statement to express the same thing.
Are there any production ready open source databases using it?
Datomic uses Datalog with a weird clojure syntax instead of the usual prolog-like syntax.
Not open source though?
Hmm open source I'm not sure, there are many SQLite equivalents listed on wikipedia though, if that counts.
No. It's only free as in beer. There's some weird mention about the Apache 2 license, but it only applies to the binaries, for some odd reason.
Compiling Datalog to SQL with Logica is possibly the easiest path if you need a production ready open source Datalog setup (i.e. choose your favourite managed Postgres provider): https://logica.dev/
DataScript, Datahike, Datalevin, and XTDB 1.x are open-source. (XTDB 2.x is also open-source but has switched from Datalog to its own query language and SQL.) DataScript, Datalevin, and XTDB have been used in production; not sure about Datahike. All of these databases come from the Clojure community and target Clojure as the primary language. The XTDB team has published a comparison matrix at https://clojurelog.github.io/.
Aside: I write a lot more Python than Clojure, and I wish someone ported Datalevin/Datahike/persistent DataScript to Python. I'd try it as an alternative to SQLite. I suspect with thoughtful API design, an embedded Datalog could feel organic in Python. It might be easier to prototype with than SQLite. There are Datalog and miniKanren implementations for Python, but they are not designed as an on-disk database. PyCozo might be the closest thing that exists. (A sibling comment https://news.ycombinator.com/item?id=40995652 already mentions Cozo.)
Not sure if "production ready" but it's worth looking at Cozo:
https://github.com/cozodb/cozo
Has a dialect of Datalog + some vector support. Multiple storage engines for backend including SQLite, so if your concern is data stability that seems like a reasonable, proven option.