C Plus Prolog
51 comments
·March 13, 2025tannhaeuser
xlii
> Prolog is for indeterministically…
One side note here. Yes you can do indeterministic search but it’s not a property in Prolog. In fact, Prolog execution is completely deterministic without use of randomization.
But I guess that in some domains (e.g. optimization) people would rather shuffle numbers than do a boring 1…1000000000 loops.
bux93
The search order is neither indeterministic, nor deterministic; it is undefined. Some implementations do depth-first search, others go random.
If your code is logically correct, it doesn't matter in the end - except if you use the cut-operator which essentially says 'don't look any further, just go with the first match', which will behave (in)deterministically based on the implementation.
null
YeGoblynQueenne
>> Prolog is really for indeterministically searching a large/infinite space such as in planning (and yes it can be used for theorem proving and program verification as well).
I'd say theorem proving is what Prolog "is really for", in the sense that it's a language whose interpreter is an automated theorem prover.
It just so happens that a (first-order) theorem prover is the best tool to explore an infinite space, if it's worth its salt, because that's what it has to do in order to find a proof in the first place.
And of course you can cast all sorts of combinatorial problems like planning and verification as proofs (this sequence of actions reaches this goal state from this starting state).
Edit: incidentally, it's so dumb that the standard for pattern matching in the industry is regexes, with their insufferable, cryptic pandemonium of notations, rather than Prolog, which has got to be the language with the simplest possible syntax in all of computer science this side of Brainfuck. When I was doing my NLP homerwork during my MSc I kept writing small ad-hoc parsers that were all balls of mud around a bunch of regex scripts, and I longed for the simplicity of Prolog and its DCGs (I couldn't use Prolog because the homework was in Python and at the time there was no Janus). Why do programmers do that to themselves?
johnisgood
Does anyone know if Prolog is useful for creating a schedule for workers with many constraints? I have a comment somewhere where I included the constraints but I have forgotten most of it by now. Constraints like minimum of 2 workers for both morning and night shifts, all workers must have 2 days off at least in a week, so no consecutive 3 days work, etc. The number of workers would be defined with names as well, etc. The goal would be to create a monthly schedule. I tried to come up with one but I may have messed up the constraints because it took too long (it got stuck, actually), maybe the constraints were too tight, I don't remember. If not Prolog, then what would be the best way to do this? I am interested in FOSS.
I wish there was a way to search for my comments, it sucks that I would have to paginate. I left a lot of comments.
upghost
yes[1][2]. You can write Prolog schedulers with arbitrary constraints.
[1]: https://www.metalevel.at/prolog/timetabling/
[2]: https://github.com/mthom/scryer-prolog/discussions/2519
Entze
You could have a look at the potassco suite[0]. It is a grounder and solver for Answer Set Programming (ASP). ASP is a form of Logic Programming.
johnisgood
I will take a look at it. Are you familiar with it, an example or a snippet would come in handy, but I may just ask Claude (if it even knows about Potassco).
Entze
ASP is optimized for combinatorial problems. Basically, you list the parts that are variable, and the constraints, the answers are given by the solver. Have a look at the documentation[0]. Here is an example:
% Each shift needs a nurse).
1 { shift_nurse(Shift, Nurse): nurse(Nurse) } 1 :- shift(shift).
% It cannot be that a nurse does two shifts in a row.
:- nurse(Nurse), shift_nurse(Shift1,Nurse),shift_nurse(Shift2,Nurse), Shift1 + 1 = Shift2.
cess11
Yes, you could do this and it's likely it'll turn out as rather nice and decently performant code. You would, however, most likely run into the problem of finding people to maintain it that are willing to learn. Most Prolog teaching material is quite abstract in the sense that it mainly teaches the language and its tricks, not so much applications, though there are of course a lot of FOSS and example applications to look at.
In practice you would have to write documentation that basically turns into a course on constraint solving in Prolog. There are footguns and somewhat advanced techniques involving control over the execution strategy that are going to trip up newcomers. You'll also have to figure out how to interface with a Prolog implementation.
A compromise might be to use bindings for Z3 or something like the Timefold solver, https://timefold.ai/open-source-solver. Either way it's a good idea to spend some time playing around with Scryer, https://www.scryer.pl/, and Markus Triska's crash course, https://www.metalevel.at/prolog. SWI-Prolog has more conveniences that might make it more suitable for practical applications, but being used to them might make it harder to adapt to e.g. Scryer, Tau or some other implementation.
There's also the Mercury language, it's weirder but also very interesting, https://mercurylang.org/.
Edit: Some people swear by Picat but I have very little experience with it, http://picat-lang.org/.
nurettin
Prolog is definitely the tool for this. I created an entire year's schedule for teachers a decade ago without a sweat. Maybe remove some constraints and try to debug which one is causing the problem.
johnisgood
Is it open source? Is the code available anywhere?
nurettin
Oh no, it is in an undergrad thesis probably rotting in some library.
Q6T46nT668w6i3m
Try Z3
null
xonix
Long time ago I was obsessed with Prolog. I found that if you bend it enough you could implement imperative code (a-la JavaScript) evaluation, still being valid Prolog:
https://github.com/xonixx/prolog-experiments/blob/main/Prolo...
This was super funny, but obviously absolutely useless
convolvatron
Why do you say that? Imagine you wrote a language that looked procedural but was actually relational underneath? We could get rid of so much glue and use unification when it made sense and ignore it otherwise. That’s a great idea
winwang
Sounds similar to Haskell "do" notation where it can look procedural, but backed by FP principles and tools.
(Something something monads are sequentialness)
c-smile
Interesting timing...
I've just made something similar but with JS: C modules in JS.
import * as CModule from "./module.c";
tombert
I really need to learn Prolog. It looks interesting and powerful, but it's different enough form most languages that I'd need to actually sit down and learn it and how to write useful stuff with it.
At a superficial level, it looks a bit like Z3, which I do have some experience with, but I suspect that there's a lot of intricacies to Prolog that don't apply to Z3.
teruakohatu
Prolog feels like magic, and it well worth learning. It is a general purpose programming language rather than a very specific purpose tool like Z3.
Sadly non-'pure' logical programming is required to get real-world performance (eg. cuts that prune the search tree) which kind of feel like, or is, a leaky abstraction that breaks the magic.
I have had good success in solving logical problems by asking o1 to produce prolog programs.
YeGoblynQueenne
There's nothing wrong with the cut, or with getting more control over the execution of your program, which is what the cut gives you.
You only get in trouble with the cut when you're just starting out and don't know what you're doing, and write your code in a way that it keeps entering infinite recursion or backtracking until the cows come home. At that point, because you don't yet know how to control those behaviours, you start sowing your code with cuts all over the place, which maybe stops the backtracking and infinite recursion (but maybe not) but it makes it an incomprehensible mess that still doesn't do what you want it to do.
As you grow and learn, you figure out how to control backtracking and recursion by ordering your program clauses and your clause literals in a sensible manner. At that point the use of the cut becomes so regular and formulaic that it might as well be added in by a pre-procesor.
For instance, you want a program that walks over a list and modifies an element if a condition holds, otherwise it continues, until the list is empty. You write:
% Program "skeleton" not meant to be executed but to expose a pattern
modify_list([],Xs,Xs):-
! % We're done, stop trying
modify_list([X|Xs],[Y|Acc],Bind):-
modify_element(X,Y)
,! Don't re-process X!
,modify_list(Xs,Acc,Bind).
modify_list([_X|Xs],Acc,Bind):-
modify_list(Xs,Acc,Bind).
lproven
I wonder if it is still the case that the most widely-used Prolog app in the world was the solver for network stack configurations in Windows NT?
https://web.archive.org/web/20040603192757/research.microsof...
johnisgood
I have solved some logic problems using Prolog, but Prolog is neat for text-based adventure games, too.
SWI Prolog has great libraries, BTW.
xlii
> Sadly non-'pure' logical programming is required to get real-world performance (eg. cuts that prune the search tree) which kind of feel like, or is, a leaky abstraction that breaks the magic.
They aren’t required but are convenient. Excuse brutalizing syntax and formatting but in Prolog you can do:
A(X) :- between(1,3,X).
B(X) :- between(1,1000,X).
?- A(X), B(X).
?- B(X), A(X).
Also cuts and pruning long time ago felt like bloated terms (when I didn’t get Prolog) whereas it’s a simple break equivalent in imperative languages loops.
coliveira
If you learn modern prolog techniques, cuts have become less and less necessary.
sriram_malhar
Can you point to some resources that show this? Are there new facilities that make cuts fewer? Are there more accepted idiomatic ways published for different kinds of problems?
I learnt Prolog a long time ago and would like to start from scratch.
quesomaster9000
Z3 is entirely different IMHO, once you get into solvers the question becomes not just 'is this satisfied' but 'what is the minimum sequence of steps necessary to arrive at the result'.
I have relied heavily on both Z3 and Alloy for ad-hoc jobs, and Prolog doesn't even come close to the inference power, and that's along-side Macsyma and Sage.
rscho
The big advantage of prolog vs solvers is the logic programming aspect. If you can express parts of your program in a logically pure way, Prolog code will be much more concise than the Z3 equivalent, although probably slower. Another advantage is that Prolog outputs and reads Prolog terms, which makes it very good for metaprogramming. It's like lisp: incredible if you're solo prototyping, not so much if you're part of a team of corporate cogs.
Karrot_Kream
What problem domain are you working in? I find usage of solvers and Prolog to be very domain specific.
rurban
Most better prologs now include solvers already.
gatlin
Have you tried sCASP?
baq
My first thought was 'why invent templates when you can use prolog' and turns out the author has similar observations.
I've been thinking over the years how to make prolog more useful. The primary constraint I have is not syntax or expertise, it's how to embed a useful prolog in a 'modern saas microservice' if you will. From what I can gather, this is not being done in the open; perhaps some closed products do it. It's telling that it's much easier to embed Z3 than prolog...
mhitza
> it's how to embed a useful prolog in a 'modern saas microservice' if you will.
Incidentally this is something I've looked at long time ago and things pointed at SWI Prolog https://www.swi-prolog.org/pldoc/man?section=embedded
The target language for my case was embedding within PHP, that would have meant enough expertise to embed the interpreter, hook it into the PHP runtime, and expose it in the language through some interface. Way over my skill level. Should be certainly doable with any language that can interface at the C language level.
elteto
> I call it, “C Plus Prolog”, or “C+P” for short.
Missed the chance to call it CPP.
hnlmorg
That was likely intentional because CPP is one of the many terms used for C++.
lproven
[GIF] That's the joke. [/GIF]
LordShredda
Would confuse it with the Canadian pension plan :^)
sinuhe69
Is that not what Picat is all about? Imperative + Declarative Constraint Programming
pjmlp
> Unfortunately, C is the only useful programming language.
Not really, plety of software has been written decades before it came to be, and plenty more has not been written in it, after it came to be.
Plus better reach out to something like SICStus if Prolog and performance is something one cares about in the same sentence.
chillpenguin
I took that as hyperbole. Hard to tell how intentional it was, whether it was a joke or not... But yeah, obviously it is not true at all.
coliveira
The main advantage of Prolog is that it forces you to think in different ways to solve problems. The main weakness of Prolog is that it forces you to think in different ways to solve problems. Especially because most existing libraries are written in procedural style, so they don't work well with prolog. In the end you'll have some difficulty to integrate with existing code.
HdS84
I always felt that Prolog is a super valuable dsl that I would wish to be embedded like a reflex for certain problems, but is I'll suited for most programming tasks. I.e. have the GUI, Io etc. in language better suited to that.
Karrot_Kream
This looks like it's using Prolog to be a rewriting engine into C? It reminds me a bit of M4 but seems like something better suited to something like Maude [1]?
fithisux
Mercury is not mentioned.
If you like this stuff, consider how to "implement" JSON in Prolog:
Basically, you don't ;) all we did here is declaring ':' as an infix operator. The next lines bind/unify a term to the var JSON, and the last line is again unification in action (basically destructuring on steroids), binding the vars X, Y, and Z to the respective value 1, "a string", and "a compound" from the previously bound JSON var.You can paste this snippet into [1] and execute it right in your browser to check that indeed X, Y, and Z are bound as described if you wish.
Not that it matters that much. Prolog is really for indeterministically searching a large/infinite space such as in planning (and yes it can be used for theorem proving and program verification as well). It's always fun to see newcomers trying to implement pointless low-level stuff such as list primitives when coming from a functional programming background or even getters/setters.
[1]: https://quantumprolog.sgml.net/browser-demo/browser-demo.htm...