The Simplicity of Prolog
98 comments
·January 26, 2025GregDavidson
upghost
Respectfully have to disagree. Prolog has the best features for abstraction of any language I've used, I suspect it may be near an optimal fixed point for metaprogramming expression[3]. I will say the other side of that wall is breathtaking.
Also not sure what you mean, CLP is a first class consideration in many Prologs, esp Scryer Prolog. Check these crazy demos out:
[1] https://youtu.be/h5Xy4YjCZxM
[2] https://youtu.be/5KUdEZTu06o
Just look at this Sudoku solver code (see [2] for explanation):
sudoku(Rows) :-
length(Rows, 9),
maplist(same_length(Rows), Rows),
append(Rows, Vs), Vs ins 1..9,
maplist(all_distinct, Rows),
transpose(Rows, Columns),
maplist(all_distinct, Columns),
Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
blocks(As, Bs, Cs),
blocks(Ds, Es, Fs),
blocks(Gs, Hs, Is).
blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
blocks(Ns1, Ns2, Ns3).
[3]: https://github.com/mthom/scryer-prolog/discussions/2347#disc...
GregDavidson
Prolog predicates are not first class values. Data structures are not abstract. Compare both with any modern lisp or better with functional languages. Mapping and filtering is awkward. Arithmetic is awkward. Indexing and search strategies are not under programmer control. Modes are awkward. Cut and dynamic assert of global facts are abominations which undermine logical reasoning. Prolog programmers often write metacircular interpreters to fix these problems which is wonderfully easy but kills efficiency. The CLP examples aren't integrated with Prolog's Horn clause resolution model, they're just libraries with strange semantics. I've been an enthusiastic Prolog programmer since the mid 1980s, attended lots of conferences, read lots of papers, etc. There have been many promising attempts to fix these problems but they've only shown up as non-standard features in specific implementations. It's similar to the "curse of Lisp" - everyone does their own thing and no consensus emerges to move the standard forward. But it could be worse if the standard were "feature oriented" rather than eliminating the limitations and flaws by cleanly generalizing the model. I study new logic programming languages avidly hoping to see a worthy successor to Prolog. So far none quite make it. Mercury might do it if it got more love.
upghost
A lot of these comments don't make any sense to me.
> Prolog predicates are not first class values.
Predicates are trivially called, even as variables, with the `call/N` metapredicate.
> Mapping and filtering is awkward
In what sense? The declarative semantics...?
> Arithmetic is awkward
In what sense...? Have you seen clpz?
> The CLP examples aren't integrated with Prolog's Horn clause resolution model
In what sense...? clpz and clpb do this magnificently.
> Indexing and search strategies are not under programmer control.
Most ship with SLG resolution or you can write your own resolution strategy with a simple metainterpreter as an intermediate exercise -- but SLD resolution is already pretty good. In general not needing to think about the indexing and search strategies are a highlight of the declarative semantics of Prolog, its odd to see someone with a "long standing love affair with Prolog" list this as a drawback.
> Modes are awkward.
Modal programming is a defining feature of Prolog. Tell me more about this "long standing love affair", again?
> I've been an enthusiastic Prolog programmer since the mid 1980s
If you are still struggling with mapping, filtering, arithmetic, `call/N`, and CLP in Prolog after nearly 45 years of "enthusiastic" programming, I'd highly recommend checking out Triska's Power of Prolog videos for some guidance, I think you will find them very illuminating.
bmacho
> There have been many promising attempts to fix these problems but they've only shown up as non-standard features in specific implementations. It's similar to the "curse of Lisp" - everyone does their own thing and no consensus emerges to move the standard forward.
> But it could be worse if the standard were "feature oriented" rather than eliminating the limitations and flaws by cleanly generalizing the model.
Why do you feel that "eliminating the limitations" is the way forward, and not standardizing common tasks instead, making them ergonomic, uniform, fast?
I don't think that more power can lead to those. Maybe ergonomics and uniformity can happen by accident if a library emerges as the default option for a task, but speed, I don't think it can.
billfruit
Not specifically aimed at this comment, but it looks like in most Prolog threads here, many commenters seems to plugging in Scryer Prolog, but perhaps, SWI is the most 'batteries included' and mature Prolog implementation for people not familiar with Prolog to try out .
rscho
There is a bit of... let's say friction between Markus Triska (Scryer) and Jan Wielemaker (SWI), I seem to remember. The SWI people are much less attached to ISO Prolog (i.e. prone to experiment with non-ISO syntax), and some things that are fixed in the SWI implementation impeded the realization of M. Triska's projects. Generally, people tend to like the new and shiny but there's also a significant philosophical gap between Scryer and SWI.
Now why would syntax be that important? It's because it directly enables homoiconicity, which is central to Prolog metaprogramming features: executing Prolog code returns a Prolog term, that can be read (just like Lisp). This is the distinctive characteristic of Prolog compared to more mainstream solvers, and what makes it 'a good programming language because it's a very dumb theorem prover'.
jodrellblank
SWI Prolog 7 added "X = Dict.key" syntax and that use of "." makes it fundamentally incompatible, ISO standard breaking, backwards incompatible to previous Prologs, sideways incompatible to other Prologs.
This is a worse sin in Prolog than it seems at a glance, because one of the strengths Prolog has is code-is-data / data-is-code metaprogramming. That includes exporting code as Prolog terms (use cases you might use CSV or JSON for in other languages), reading them back in as Prolog data (perhaps in a different Prolog system or different version) and executing the data as Prolog code. With that "." syntax change no other Prolog system can guarantee to read all SWI Prolog code, SWI 7 can't guarantee to read all SWI 6 code, and SWI 6 can't guarantee to read all SWI 7 code.
Code might say "connect_to_mongodb()" and you don't have mongodb in your system so you cannot run it, but you can read the code in as data and it will parse, just like reading in JSON which has a string mentioning some library you don't have; you can still introspect it and write reports like "what names does this data reference?", you can transform it and export it, or pass it through untouched. With SWI's new dot syntax the code might not parse at all, like an incompatible proprietary JSON syntax where you can't even import it. Code written 30 years ago which uses the dot in the old standard way might trigger SWI to try and read it in the Dict.key way and fail. Code exported from SWI 7 might include this syntax which other systems can't import.
I don't know how often it will come up in practise, but it seems that SWI could have done it with a slightly different syntax that would have been as convenient to use and also been a standard term and wouldn't have made this split at all. SWI has some other differences versus ISO Prolog, things inside error handling, for example, but none quite so fundamental as this. And it's annoying from the outside because you can wade into a big-ball-of-mud design-by-committee language, but if you want to look at an esoteric language and they're all arguing over who is most pure and virtuous you have to pick a religion before you can write Hello world.
Markus Triska's Power of Prolog series has been some of the best Prolog publicising material in years, something that isn't (totally) a dry academic text of "a --> a | a. a(A) :- a([a|As]) , a(As).", it must be a huge amount of work on his part. He uses and contributes to Scryer Prolog, and he is especially interested in Constraint Language Programming which he wrote/maintained in SWI[1], and has moved the newer versions to Scryer.
That said, I strongly agree with your comment, SWI is batteries included, it has lots of builtins, a packaging system to download and install modules, it has a debugger and graphical debugger and tracer and just a ton of decades of development and polish that Scryer hasn't had time to develop yet, and is much much friendlier for people not familiar with Prolog to try out. You have to be pretty hardcore to be writing Scryer Prolog in EMACS buffers with no predicate search, no help, limited libraries, limited documentation, limited debugging, very small online community even by Prolog standards which is already small.
When you could open https://swish.swi-prolog.org/ and click 'new Program' and as a beginner be able to write syntax highlighted code in browser with no download, no setup, no install, no account registration, but it's SWI Prolog.
Query "apropos(string)" in the query box in the lower right and see things like "string_lower/2" and "string_concat/3". That search is convenient and those predicates are SWI custom ones.
Query "help(format)" and see HTML styled, coloured, scrollable help for the text formatting domain specific language. That's enormously useful.
[1] https://www.swi-prolog.org/pldoc/man?section=clpfd "Author: Markus Triska"
javcasas
My little pet peeve with prolog is the lack of context parameters (which can be thought as a type of abstraction).
For example, imagine I'm writing a maze solver. The maze solver predicate receives obviously, but it has to pass as a parameter the maze again and again to all sub-predicates. There is no concept of "current maze", like in OO you would have with this.maze, or in Haskell you would do with a reader monad. As a result, all the "internal" predicates in a module get full of parameters all they do is pass around until some final predicate uses it to do some calculation.
Either that or you do the assert/retract dance and now you have bigger problems.
tannhaeuser
Quantum Prolog has this feature where you can query against a dynamic database, not just the global default database; ie. where in regular Prolog (and in Quantum Prolog as well of course since it's full ISO) you query
p(a).
p(b).
?- p(X)
KB = [ p(a), p(b) ],
KB ?- p(X)
In the description [1], this is used to avoid destructive database manipulation via assertz/retract builtins, and thus to allow much more complex combinatorial planning problems and action post-conditions to be solved/optimized without resorting to ad-hoc hacks. But you can also use this for mere convenience in large knowledge graphs, and a technique very similar to it, albeit implemented in Prolog itself and not provided with native speed, has been used as a historic extension to Prolog DCG parsing (cf. definite-clause translation grammars by Dahl et al).
[1]: https://quantumprolog.sgml.net/container-planning-demo/part2...
upghost
There are multiple ways to accomplish this, but the one that is the most straightforward is to simply make an object mapping of the type you are familiar with via AVL trees[1]. Easy way to get the "this.maze" semantics. You can get global context and local context via "blackboard"[2] semantics.
However quite frankly the most powerful way to do this is not obvious because it doesn't translate well to other languages: meta-interpreters[3].
[1]: https://www.scryer.pl/assoc
horsh1
You have "Rows" repeated eight times in this short snippet. You have all the rest of your variables as two letter names. It feels low level, almost like Fortran.
coliveira
Yes, the OP is probably unaware of the recent advancements in Prolog. There is a set of techniques using pure Prolog that have made the language incredibly powerful compared to the techniques of the 80s and 80s. The more we use the abstract features of Prolog, the more powerful it becomes.
Horffupolde
The thing with Prolog is that it’s beautiful for solving very specific and well-defined combinatoric problems. Steer away and you hit a wall.
humanfromearth9
And I have yet to understand this.
smarx007
Well, that's why language paradigms are a thing - if you are not familiar with any language in the logic paradigm but are an expert in the OO-paradigm, this could take a little bit to wrap your head around. Triska is an excellent teacher of Prolog, be sure to check out his videos linked.
fifilura
I am assuming it is a close relative to Norvigs solver https://norvig.com/sudoku.html
upghost
Maybe watch the second link I posted?
2-3-7-43-1807
The declarative expression of the problem is elegant but even if this toy example is successfully resolved, make it a little more complicated and you'll have the interpreter ping-pong between two states infinitely.
As I see it. Prolog as a language and idea is great but the existing solvers are useless for any real problem ... or you'll have to resort to cuts and memorizing states and at least partially implement an imperative solution that you yourself have to come up with. And that's totally killing the magic.
rscho
Well, I mean... Prolog is an implementation of 1st order logic with syntax sugar. So basically, Prolog is incredible if your problem can be expressed within the framework, but less so if it can't. That's pretty much why there were extension attempts such as lambda Prolog.
derdi
> Prolog has poor features for abstraction
That's actually what this article presents as its strength and simplicity. The straightforward choice in Prolog is to use global "who may do what" tables. In contrast, the author overengineers a Kotlin solution and then says "look, this is overengineered". I think global tables would make the Kotlin code half as long and much simpler too.
> Mercury and Curry fix some of these limitations
At the cost of introducing new ones. Mercury makes it effectively impossible to pass around partially instantiated structures.
rscho
How does MiniKanren fix some limitations? MiniKanren corresponds to the purely relational subset of Prolog.
GregDavidson
By allowing you to use the features of the host language to complement the features of miniKanren. Having good support for multiple programming paradigms is better than trying to make one paradigm fit all needs. Poplog[1] was an earlier attempt to provide such synergies but it failed to gain market share. It's now free software so take a look! The Racket ecosystem is another approach where each module can choose a language with some of them being Prolog-like[2]. [1] https://en.m.wikipedia.org/wiki/Poplog [2] https://racket-lang.org/languages.html
rscho
Ok, but MiniKanren isn't intrinsic to Scheme. I agree Racket makes it especially easy to embed sub languages, but you could embed core relational Prolog just as well as MiniKanren. My understanding of your statement is that Scheme and MiniKanren share sexp syntax, but the same applies: you could embed an sexp-based Prolog just as well. The only remaining MiniKanren advantage is then to have a complete search strategy, this I concede.
Pet_Ant
Doesn’t Mercury declare each form of a rule independently?
cess11
I take it you have some gripe with https://www.scryer.pl/clpz? Could you explain in more detail?
anonzzzies
In a long forgotten past a large part of my graduation was Prolog (I was as far ahead then as i'm behind now with the ol' AI thing; I worked on mixing neural nets, reasoning with uncertainty with Prolog at the time) and, after hallucinatory episodes living, sleeping, (day)dreaming in Prolog for months on end, when something was finished I was always so surprised how clean, readable and 'too little' the code looked for what it did. Once you really grok it, it's a magic tool. I replaced it with Common Lisp after (in my uni, there was no mention of Lisp; we didn't even know it existed basically besides some weird scribbles in papers which were easy enough to study so we didn't give it more thought) and have the same feelings/experiences there but CL is usable for basically anything, including logic programming.
ramses0
I really wish there was "regex for prolog", ie: when pounding away in JavaScript be able to do:
let options = { foo: 1, bar: 2, ... }
```prolog
$X :- fromJson( options )
Solution = Optimize( $X )
...
```
Avshalom
You might want http://tau-prolog.org/documentation#js
andrewflnr
It's been a while since I used it, but look at the miniKanren implementations for your favorite programming language (js in your case, but there are a lot). It's basically a stripped-down version of logic programming.
aktuel
I started learning prolog just a few months ago, when I stumbled upon https://linusakesson.net/dialog/ which is a spin on prolog optimized for writing interactive fiction.
As a sweet and short tutorial I can recommend these slides: https://www.cs.toronto.edu/~hojjat/384w10/
If you want to dive into how Prolog works under the hood I can recommend https://github.com/a-yiorgos/wambook
I terms of Prolog implementations I played a bit with https://www.scryer.pl but it still feels rough around the edges.
SWI-Prolog is the most popular and most batteries included Prolog: https://www.swi-prolog.org With its libraries and documentation it is a very practical language. What surprised me is, that you can easily produce amazingly small stand-alone binaries.
0x3444ac53
I read about dialog in another HN thread a few weeks ago. Between then and now I've had the itch to write some interactive fiction, but I could not for the life of me remember the name of that project.
Thanks!
brabel
> The reverse predicate from this section should not be used in practice - most Prolog implementations actually provide a built-in version which is a lot more performant than our implementation.
That feels like cheating. If you shouldn't use the implementation shown, then why do you even show it? Let us see the performant version!
That's like Haskell's quickSort implementation in a couple of lines... beautiful but horrendously non-performant as it doesn't actually implement the algorithm, it just implements the "idea" (while losing all the performance of the actual algorithm, which requires in-place mutation).
derdi
No built-in is needed for an efficient reverse. It's just one or two lines longer because you need to write a tail-recursive helper with an accumulator, same as in functional languages: https://stackoverflow.com/a/74777180
capitanazo77
FYI, composer 2 (the official PHP package manager) uses prolog to figure out if a package can be installed or not.
When it’s not possible, you get a detailed explanation why it’s not possible
upghost
I always enjoy reading positive pieces about Prolog but without touching on the implications of the principles on display, this article may do more harm than good.
You would ask reasonable questions like, "for God's sake, why?". It feels like you wouldn't use Prolog for anything besides an intellectual game.
Regarding the why:
Some of those reasons include Definite Clause Grammars, Meta-Interpreters, 1st class constraint logic programming, reified conditionals, and term/goal expansion.
There are a lot of exciting modern advances with Prolog, especially Scryer Prolog.
Check out Power of Prolog and get your mind blown: https://youtube.com/@thepowerofprolog
agumonkey
one example that changed my view of prolog was http://faculty.cooper.edu/smyth/cs225/ch7/prolog.htm (a toy compiler in prolog)
coliveira
And this is nothing new. People already knew how to write compilers in Prolog (easily) in the 90s. The problem with Prolog is that it requires a change in the way you think about problems, to a more declarative way. Programmers are in general not willing to do this since the result will be not as performant as what they can do with C. There must be a revolution in programming education and tools before people fully understand how Prolog works.
simplify
Something doesn't have to be new to be valuable (XKCD "Ten Thousand" et al). A revolution starts with inspiration.
agumonkey
yeah yeah i got that too after a while, which is also why i like non mainstream programming languages, after a while you're tired writing more versions of the same routines/procedures/methods that won't help you find better solutions
titanomachy
I liked the authorization example. I've encountered Prolog articles before, but showing the code alongside an OOP implementation was a nice demonstration of its expressive power.
As a follow-up, I'd love to learn how this auth system could be put into production. In this example, authorization rules are provided in the code (`user_role(mike, supervisor)`) and queried similarly. What if I wanted this system to expose authorization as an HTTP endpoint with REST semantics, and store authorization rules on disk? Would this be straightforward, involved, or impossible? Would I use another language for HTTP, and query a prolog "server" running on the same machine?
derdi
> What if I wanted this system to expose authorization as an HTTP endpoint with REST semantics, and store authorization rules on disk? Would this be straightforward, involved, or impossible?
Straightforward. Prolog supports self-modifying code. You can mark the user_role predicate as "dynamic", i.e., modifiable. At runtime you can then read rules from disk or receive them via HTTP or construct them based on some other form of input, and add them to the code, or remove them as needed.
The HTTP part is not standardized; you would need to use libraries specific to some concrete implementation. But the libraries exist.
lionkor
How can I use Prolog to actually get something done, other than academic tasks?
Say I want to use it as a database query language, presumably that's not going to happen, right?
tgamblin
> Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases.
2-3-7-43-1807
do you know what you are writing about? I mean have you actually done something with datalog? and then _which_ datalog? if yes, then you are probably someone working with it academically or the answer is no. because try to even set a toy project up with it (for the purpose of learning how to use it) and you'll quickly run into unmaintained interpreters, discussions of what datalog is and what not and you can choose between difficult to understand academic papers or simplistic introductions that lead you no where.
UltraSane
Have you tried Datomic?
YeGoblynQueenne
>> How can I use Prolog to actually get something done, other than academic tasks?
Choose the task, download Prolog and start coding. That's, generally, how you "get something done".
As to using Prolog as a database query language, I'd say that's like using a piano as a lawn ornament, but you can certainly replace a traditional relational DB with Prolog. The SWI-Prolog website does that and the developers explain how to do it in this article:
Can I replace a LAMP stack with SWI-Prolog?
https://www.swi-prolog.org/FAQ/PrologLAMP.md
And here's some more about using Prolog for good, old-fashioned, web development, in the sense of creating sites that run on the web and have visitors etc etc, particularly the SWI-Prolog website itself:
Eat Your Own Dog Food
upghost
No, unless you count cancer research[1], particle physics experiments[2], and government funding allocations[3].
[1]: https://dcnorris.github.io/precautionary/index.html
[2]: https://github.com/mthom/scryer-prolog/discussions/2441
[3]: https://link.springer.com/chapter/10.1007/978-981-97-2300-3_...
Regarding how, check out Power of Prolog on YouTube.
Twey
In a sense, Prolog _is_ a database query language. The base facts in Prolog are equivalent to the rows of a table. You can also ‘table’ predicates with variables (over a finite subset of values) by memoizing the results.
aktuel
There you go: https://github.com/aarroyoc/postgresql-prolog
null
kevindamm
Consider also checking out Datomic, though technically it's datalog not prolog, and not for connecting to your already-in-use SQL system, but it is a good example of taking the expressive power of logic programming to interface with a database.
kevindamm
EDIT: (too late to edit above)
s/logic programming/relational programming/
it isn't as expressive as LP or CLP and works best embedded in a functional-biased language
LoneGeek
For example: Void Linux installer implemented in GNU Prolog (https://github.com/sdbtools/void-pi).
fifilura
Having used Trino/Athena and BigQuery extensively, I am curious about the state of parallelism in the available prolog implementations.
Being able to push the calculations to CUDA or the google/AWS "cluster" feels like it could be the game changer for a system like this.
The declarative nature of the language should leave any imperative implementation far behind when it comes to complex calculations.
tannhaeuser
Indeed. Not using CUDA but Quantum Prolog has parallel maplist and co [1], and the article also contains a short overview and brief comparison with other approaches, including a short discussion of imperative implementations like SWI's (historic?) threading package. Discussion is necessarily limited to that particular workload since parallel Prolog has a long history dating back to the 1990s (the book "Past, Present, Parallel" was an early survey at the time and already contains tens of approaches/academic implementations).
[1]: https://quantumprolog.sgml.net/bioinformatics-demo/part2.htm...
axefrog
Fun fact: A large portion of TerminusDB's codebase is written in Prolog. https://github.com/terminusdb
llsf
I think Lambda Prolog, is the only language that physically hurt my brain... in a good way.
But damn, it felt like an extreme muscle stretching exercise. Painful when doing it, but you feel SO good after :)
ParticlesRWaves
Am I the only who finds this article to be inaccessible due to color choices and implementation?
I'm really interested in Prolog, but my eyes feel the strain after a few sentences. The reason is that the contrast ratio of some parts is very low, of others excessively high. The constant alternations between these extremes intensifies the effect.
The page looks shredded in Safaris reader mode, so that's no help either.
I have a long standing love affair with Prolog and frustration for its failure to grow. Prolog has poor features for abstraction and is actually not declarative enough!
Prolog's limitations can be great for starting to get the paradigm but then you hit a wall. (Kind of like standard Pascal!)
Mercury and Curry fix some of these limitations as does miniKanren. Integrating CLP is important yet so far always clumsy as standard Prolog provides no way to reify the environment.
Some LP resources:
https://minikanren.org/ https://mercurylang.org/ https://www.curry-lang.org/ https://en.m.wikipedia.org/wiki/Constraint_logic_programming https://logtalk.org/