I’ve actually written some non-trivial quantities of Prolog and I have a strong bias towards the language. I’m one of the people who liked Erlang in part because of the Prolog-style syntax. In spite of that bias, there are a lot of rough edges in Prolog and as soon as you need to write a cut you realise that the language has significant problems.
I was originally taught Prolog as an example of a family of logic-programming languages. I prefer to think of it as an ancestor of proof-assistant tools. The big change that most later systems provided was pluggable tactics. Prolog uses SLD derivation which means that your encoding of the problem is tightly coupled to the mechanism that the Prolog interpreter will use to explore the space. In contrast, with pluggable tactics, you can write the logic cleanly and then separately describe how to avoid hitting pathological cases in exploration. Even something fairly trivial like ‘do a breadth-first search here’ requires cuts in prolog that make the predicates much harder to read.
I did put Prolog on my list of languages that everyone should learn (though not necessarily use) a decade or so ago but these days I’d recommend learning something like Z3 instead.
Interesting points. Although the selection of SMT solvers has become rather difficult, as e.g. http://www.satcompetition.org/ demonstrates; what still makes the case for Z3 today compared to the others?
what still makes the case for Z3 today compared to the others?
I honestly haven’t looked at most of the others. Z3 is permissively licensed, easy to embed, and has worked for everything I’ve needed it to do. If there’s something better, I’d be happy to use it!
Any opinions/experience with Datalog-family stuff? A year or two ago people seemed pretty bullish on it, but it doesn’t seem to have taken off much since then.
It’s sufficiently expressive for many analyses and it can reduce development time dramatically. I was able to reimplement a static analyzer that took me 50 weeks to code (using Ocaml) in approximately 2 (using Datalog), with no major performance hit. The caveat is that you are not able to express some advanced analyses. Still, it’s a great tradeoff.
Answer-set programming (ASP) offers a saner (less brittle) semantics for Prolog-like programs: https://en.wikipedia.org/wiki/Stable_model_semantics. ASP is also very interesting as a high-level interface to SAT/SMT solvers.
My university used to teach Prolog as the first programming language to incoming students. It was really forward-thinking, I think, as it exposed students to a non-procedural paradigm very early. However, things got quite confusing when you had to use impure features like cuts. As you also noted, some of the abstractions in Prolog are leaky. ASP is a nice alternative for some of the kinds of problems Prolog excels at.
I think it was Bruce Eckel who mentioned having a “Prolog moment” when it clicked for him. I never managed to find detail on that moment - does anyone know?
Prolog tutorials all start with logic demos. I’ve looked around and found things like HTTP clients, so it’s clearly not just a deduction engine. Is the deduction just an additional feature of the language, or the entire paradigm so that if one were writing a business service, or cli tool, whatever, would it have to be represented as a space search problem? Or is Prolog best not used for general programming?
Bob Kowalski, one of Prolog authors, once said that the success of Prolog is that it was a proof engine so stupid that you could do everything with it (or something along that).
Now, as I’m the author of that HTTP library (the one that ships with Scryer Prolog), obviously my answer is going to be that Prolog can be used for general programming. And in fact, I encourage people to use it for that! IMHO the basic key concepts that Prolog has are unification and non-determinism. Unification allows you to have logic variables. Just unification and logic variables itself make Prolog an interesting language (other languages have these things too, but they’re even more unpopular!). Nondeterminism is what gives you space search capabilities but it’s not something mandatory. There are lots of predicates that are deterministic and things like the HTTP library are going to be determinism, because it makes no sense to use it there. But the language itself has that capabilities builtin.
In my opinion, as much as Common Lisp can be used for general programming, Prolog is too, although the community is much smaller due to some factors. For example, most part of the Prolog community is in Europe.
The key insight you need for doing this is to understand a metainterpreter. The OP does explain this really well: https://www.metalevel.at/acomip
In a nutshell, a metainterpreter allows you to borrow as many features from the original language as you like, and change (reify in metainterpreter jargon) those that are not useful.
This is one of the best sources of modern Prolog. Most Prolog books and tutorials focus on certain aspects of the original Prolog systems. However, new Prolog developments were often ignored and thus, underutilized. This, and the YouTube videos, are one of the few sources that explain the features that improve Prolog, making it more declarative and more expressive.
There’s a sibling comment here that talks about Prolog and SLD as things that are unsplittable between each other. However, modern Prolog systems (and this book talks about it) show that there’s for example SLG resolution. Then there are also constraint systems like clp(Z) (which allows for declarative arithmetic on integers) or clp(B) (a SAT solver inside Prolog). New constructs like dif/2, freeze/2, when/2, allow coroutining and delaying goals. And there are a lot of things yet to be discovered for the curious mind!
I’ve actually written some non-trivial quantities of Prolog and I have a strong bias towards the language. I’m one of the people who liked Erlang in part because of the Prolog-style syntax. In spite of that bias, there are a lot of rough edges in Prolog and as soon as you need to write a cut you realise that the language has significant problems.
I was originally taught Prolog as an example of a family of logic-programming languages. I prefer to think of it as an ancestor of proof-assistant tools. The big change that most later systems provided was pluggable tactics. Prolog uses SLD derivation which means that your encoding of the problem is tightly coupled to the mechanism that the Prolog interpreter will use to explore the space. In contrast, with pluggable tactics, you can write the logic cleanly and then separately describe how to avoid hitting pathological cases in exploration. Even something fairly trivial like ‘do a breadth-first search here’ requires cuts in prolog that make the predicates much harder to read.
I did put Prolog on my list of languages that everyone should learn (though not necessarily use) a decade or so ago but these days I’d recommend learning something like Z3 instead.
When I worked at DVLabs, I introduced Erlang into the code base (this would’ve been in 2008 or so).
Coworker: What’s Erlang?
Me: Think of it like a concurrent, declarative Lisp.
Coworker: I hate Lisp. All those parentheses.
Me: Good news, then, this has syntax closer to Prolog’s!
Coworker: That’s even worse!
Interesting points. Although the selection of SMT solvers has become rather difficult, as e.g. http://www.satcompetition.org/ demonstrates; what still makes the case for Z3 today compared to the others?
I honestly haven’t looked at most of the others. Z3 is permissively licensed, easy to embed, and has worked for everything I’ve needed it to do. If there’s something better, I’d be happy to use it!
Any opinions/experience with Datalog-family stuff? A year or two ago people seemed pretty bullish on it, but it doesn’t seem to have taken off much since then.
Datalog is heavily used for (static) program analysis these days. E.g., see chapter 8 in: https://arxiv.org/abs/2012.10086.
It’s sufficiently expressive for many analyses and it can reduce development time dramatically. I was able to reimplement a static analyzer that took me 50 weeks to code (using Ocaml) in approximately 2 (using Datalog), with no major performance hit. The caveat is that you are not able to express some advanced analyses. Still, it’s a great tradeoff.
Answer-set programming (ASP) offers a saner (less brittle) semantics for Prolog-like programs: https://en.wikipedia.org/wiki/Stable_model_semantics. ASP is also very interesting as a high-level interface to SAT/SMT solvers.
My university used to teach Prolog as the first programming language to incoming students. It was really forward-thinking, I think, as it exposed students to a non-procedural paradigm very early. However, things got quite confusing when you had to use impure features like cuts. As you also noted, some of the abstractions in Prolog are leaky. ASP is a nice alternative for some of the kinds of problems Prolog excels at.
A couple of questions.
I think it was Bruce Eckel who mentioned having a “Prolog moment” when it clicked for him. I never managed to find detail on that moment - does anyone know?
Prolog tutorials all start with logic demos. I’ve looked around and found things like HTTP clients, so it’s clearly not just a deduction engine. Is the deduction just an additional feature of the language, or the entire paradigm so that if one were writing a business service, or cli tool, whatever, would it have to be represented as a space search problem? Or is Prolog best not used for general programming?
Bob Kowalski, one of Prolog authors, once said that the success of Prolog is that it was a proof engine so stupid that you could do everything with it (or something along that).
Now, as I’m the author of that HTTP library (the one that ships with Scryer Prolog), obviously my answer is going to be that Prolog can be used for general programming. And in fact, I encourage people to use it for that! IMHO the basic key concepts that Prolog has are unification and non-determinism. Unification allows you to have logic variables. Just unification and logic variables itself make Prolog an interesting language (other languages have these things too, but they’re even more unpopular!). Nondeterminism is what gives you space search capabilities but it’s not something mandatory. There are lots of predicates that are deterministic and things like the HTTP library are going to be determinism, because it makes no sense to use it there. But the language itself has that capabilities builtin.
In my opinion, as much as Common Lisp can be used for general programming, Prolog is too, although the community is much smaller due to some factors. For example, most part of the Prolog community is in Europe.
Erlang was originally implemented in Prolog.
The key insight you need for doing this is to understand a metainterpreter. The OP does explain this really well: https://www.metalevel.at/acomip
In a nutshell, a metainterpreter allows you to borrow as many features from the original language as you like, and change (reify in metainterpreter jargon) those that are not useful.
This article discusses some similar ideas in the context of education: https://ep.liu.se/ecp/012/004/ecp012004.pdf
This is one of the best sources of modern Prolog. Most Prolog books and tutorials focus on certain aspects of the original Prolog systems. However, new Prolog developments were often ignored and thus, underutilized. This, and the YouTube videos, are one of the few sources that explain the features that improve Prolog, making it more declarative and more expressive.
There’s a sibling comment here that talks about Prolog and SLD as things that are unsplittable between each other. However, modern Prolog systems (and this book talks about it) show that there’s for example SLG resolution. Then there are also constraint systems like clp(Z) (which allows for declarative arithmetic on integers) or clp(B) (a SAT solver inside Prolog). New constructs like dif/2, freeze/2, when/2, allow coroutining and delaying goals. And there are a lot of things yet to be discovered for the curious mind!