The Power of Prolog
metalevel.at
metalevel.at
I hope you are all doing reasonably well. Please take care!
This book was most recently discussed here in May 2018:
https://news.ycombinator.com/item?id=17121028
Since then, I have added a new chapter, Logical Foundations of Prolog:
https://www.metalevel.at/prolog/logic
Also, I have made several other additions and improvements. You can see most of the changes since the last discussion in a public git repository:
https://github.com/triska/the-power-of-prolog/compare/8a94ed...
Currently, I am working on several videos that will eventually form the core of the book. Here are a few previews:
https://www.metalevel.at/prolog/videos/logic
https://www.metalevel.at/prolog/videos/timetabling
https://www.metalevel.at/prolog/videos/sparrows_on_eagles
These videos are all work in progress, and they may be replaced by better versions at any time. Hence, if possible, please use the links above to refer to them: They will always point to the latest versions.
Alternatively, please use the following overview page that shows all videos:
https://www.metalevel.at/prolog/videos/
Also, I have published a comprehensive journal paper about my CLP(B) system, i.e., a SAT solver with some nice algebraic properties, seamlessly integrated into Prolog as a specialized form of unification:
https://www.metalevel.at/boolean.pdf
For Prolog application programmers and system implementors, the paper's appendices may be especially interesting. They formalize a few important concepts that are also a major theme in the book.
As of October 2019, the CLP(B) system is also available in Mark Thom's Scryer Prolog. Scryer is a Rust-based Prolog implementation that is freely available, conforms to the Prolog ISO standard, represents strings efficiently as lists of characters, and includes important features for implementing Prolog-based constraint solvers:
https://github.com/mthom/scryer-prolog
As of a few days ago, Scryer Prolog also ships with my implementation of CLP(ℤ), Constraint Logic Programming over integers. This is a very useful declarative paradigm for solving combinatorial tasks, in some ways superior to SAT solving because it allows more convenient modeling, easier experimentation with different formulations, and reasoning at a higher conceptual level. The chapter on declarative integer arithmetic contains more information, and further pointers:
https://www.metalevel.at/prolog/clpz
For illustration, here is an example page where you can solve timetabling instances with this approach:
https://www.metalevel.at/prolog/timetabling/
I welcome all comments and suggestions about the book, these videos, and Prolog in general. Also, I would like to take this opportunity to thank all readers for your thoughtful comments and endorsements. Your feedback and encouragement are making this work especially worthwhile.
Enjoy!
I greatly enjoy all your postings about your Prolog-based interpreter for Joy:
https://osdn.net/projects/joypy/scm/hg/Joypy/blobs/tip/thun/...
I impulsively upvote this every time I see it. Thank you for sharing such an interesting project!
Your advice to use CLP(FD) for the semantics of integer math operations was fantastic!
I typically use SWI Prolog but I hope the code is mostly portable. The parser uses a couple of DCGs from the "basics" lib but I think those are also portable or at least simple to re-implement.
The tricky bit might be the semantics of math (and comparison) ops. I've tried two other sets of semantics, one that attempts to perform math operations (and catch the errors if e.g. an arg is a logic var rather than an int) as you go, and another that just builds expression trees (evaluation is delayed) like so:
func(+, [int(A), int(B)|S], [int(A + B)|S]).
!
As well as an exclamation I suppose that's the cut on my "write a prolog to learn rust" predicate, backtracking to finding out more about this, especially since I just came across a little puzzle for which integer constraint programming is perfect this week.
One of my goals with this specific form of presentation is to counteract "skimming" by making it unrewarding: When readers are tempted to "skim" a chapter, they usually find out that they were already almost at the end of the chapter, so reading the entire chapter and thinking about the content becomes the preferred strategy.
One potential drawback of this approach is that readers who do not want to think about the content, or do not read the material with the required focus may come to the conclusion that it is too terse.
In my opinion, what matters here, maybe more than in other texts, is the strategy of reading that is required to best absorb the material. I am doing my best to ensure that it is all there. Yet, the full potential is only realized with active cooperation from the reader. I think it would be possible to convey some of the points also with lengthier explanations, though at the substantial cost of sacrificing peak impact potential. I am very glad to hear that this approach is working well for you, thank you a lot for your feedback!
:- use_module(library(clpfd)).
:- use_module(library(clpz)).
- Automatic detection and compilation of partial strings
- Streams, including sockets
- Garbage collection in anticipation of very fast yet logically pure I/O
- Improvements to the instruction dispatch loop (many opportunities for enhancement there, probably a good place to start for a beginning contributor)
In the past few months, we've added delimited continuations, tabling, partial strings, and Markus' CLP(B), CLP(ℤ) and format libraries. For a hobbyist project I'd say we're moving at a fairly quick pace!
Longer term, we're interested in:
- JIT compilation to native code (Cranelift seems a good candidate?)
- Low-level integration with Common Lisp environments
I'd love to have system-level contributors, although library contributions are always very welcome!
In the hope to attract further contributors to Scryer Prolog, especially with interest in Rust, I have now created a GitHub issue that collects a few self-contained features that could be interesting to look into for Rust programmers:
https://github.com/mthom/scryer-prolog/issues/319
I hope that's OK, and I invite everyone who is interested in these topics to contribute to this very innovative new Prolog system! Already in this early stage, it provides several important features that no other system currently has. Thank you again!
Sounds interesting, do you have a link or something else to share regarding your conception of logically pure I/O?
https://github.com/SWI-Prolog/swipl-devel/blob/master/librar...
this (I assume) is the library(pio) mentioned in the github issue
Also, there is now ample room for input that SWI once almost offered.
As someone with only fleeting knowledge of Prolog, this was by far the best introduction I've come across.
The standard ensures portability of Prolog programs between conforming systems, and significantly simplifies legal disputes in case a system does not conform.
As I see it, this is one of the advantages one loses when using a Prolog-like implementation as opposed to an actual Prolog system, and especially in commercial settings, this may be a significant drawback of using libraries that lack the strong formal backing and guarantees that an ISO standard ensures.
Other advantages of using an actual Prolog system are speed and reliabiliy, and dedicated features such as constraints and built-in grammar mechanisms (DCGs). The availability of expressive and efficient constraints is often an important reason for buying and using a commercial Prolog system. Another important reason is that Prolog syntax and semantics enable declarative debugging approaches such as failure slicing and selective reading. These approaches may not translate to libraries, and also not to other syntactic formalisms.
I suppose most people who, in production, have to solve the sort of problems that Prolog is really good at are using some sort of logic programming library (or, more realistically, are implementing their own ad hoc, informally-specified, bug-ridden, slow implementation of half of Prolog). I don't think Prolog is a great language for shipping an actual product. But for me the alternatives are just not as satisfying. Choosing Prolog for a random little personal project (that fits what Prolog wants to do) is a good time.
But regardless, if one needs some of the basic features of Prolog and a good library exists for your language/environment of choice (core.logic for Clojure is probably one of the most solid ones at the moment), then I think it's good common sense not to add one more language to your system (assuming this is in a production context, of course). But modern Prolog systems have a lot more functionality than the unification and backtracking semantics that at the core of Prolog. Among them are the constraint solving capabilities that The Power of Prolog describe, and tabling in some form, which allows for efficient execution of programs that in early Prolog systems would lead to non-terminating search.
Not only are these features available, but in many cases they are tightly integrated with the language, optimized and fine-tuned over many years. So the answer is similar to if someone asks "Why choose Erlang when there are actor-based concurrency libraries in so many languages?" (or any number of similar questions): it might not make sense for the simpler use cases, but you won't get the full experience unless you take the plunge.
Last time I had to write a rule-learning-inspired [1] algorithm with a custom hypothesis language. Prolog has the advantage that you can experiment with different search strategies (depth-first search, breadth-first search, informed search, ...) very quickly. Also, given that SWI Prolog can be used without a build system, it is as quick to bootstrap as to write a BASH script. Not even unit tests need a library nor dependencies...
So my use-case for Prolog is: - prototyping, - that involves some kind of searching, - first-order logic, or at least some kind of pattern matching involved and - no fancy I/O (parsing binary data), because this is IMHO Prolog's weak point.
and 2017: https://news.ycombinator.com/item?id=14045987
(Links are for the curious. Reposts are ok after a year: https://news.ycombinator.com/newsfaq.html)
"Cyc failed to understand a story about a person named Fred shaving in the morning... Its inference engine detected an inconsistency in the story: it knew people do not have electrical parts, but because Fred was holding an electric razor, it believed the entity 'FredWhileShaving' contained electrical parts. It therefore asked whether Fred was still a person while shaving."
From "Deep Learning" by Ian Goodfellow, Yoshua Bengio, Aaron Courville.
They worked on it in isolation for decades, building new frames laboriously by hand, and made a few corporate sales I guess, but withdrew OpenCyc and that's about the last we heard from them. Major bummer.
I feel like an open source business model would have allowed the public to use and extend the frames, propelling Cyc to mainstream, while Cycorp would consult and advocate and curate.
Some things are hard, yet have no pay-off or are even detrimental. On the other hand, things that pay off are often proportionally hard.
It is not may goal to make it hard, in fact I am doing everything I can to make it as easy as possible. I am very interested in didactic approaches, and always welcome feedback! I would like to make it worth the effort for viewers, and — beyond that — exceed the required effort in value.
Now that I know your handle, I'll ping you when I have some news :)
There is significant interest in applying logical reasoning and logic programming in the context of legislation and application of laws, in fact especially in Austria, for several reasons both historic and current, and also throughout Europe, for instance to implement cross-border use cases that are mandated by the Single Digital Gateway Regulation (SDG).
As one contact point, see for example the Vienna Legal Hackers:
http://vie-legalhackers.at/en/home-en/
A few weeks ago, I gave a presentation about Logic in the Public Sector in the form of a RuleML webinar, maybe these slides are interesting for your use case, or in future projects in LegalTech:
http://ruleml.org/talks/MarkusTriska-LogicInThePublicSector-...
See also ruleml.org for more information about RuleML, and further potential opportunities for cooperation!
One thing I can say for certain, after discussing this topic with lawyers who are interested in Prolog: In Vienna, opportunities for applying Prolog in concrete projects in LegalTech abound. If you want to use Prolog in a job in the legal sector and are reasonably skilled in the language, you can start working immediately, for instance in the context of EU projects.
pre-answered your own question really. Prolog 'died' in the AI winter, so no one knows it and no one knows anyone who knows it. Every time you think "huh I bet this is like 100 lines in Prolog" it doesn't matter because writing 2000 lines of Java (or whatever you know) is still going to be faster than learning Prolog.
This is also the problem with literally any comment about "using the right tool for the job" with regards to programming languages.
We may see analogous developments with Prolog when our current hardware gets better or changes its characteristics, and when Prolog implementations get better and use better approaches that are now becoming available.
I think one difficulty we are facing when judging developments in this area is that complex software projects such as implementing a Prolog system happen on time scales we are not yet used to.
* I mean seriously it's fantastically expressive: parsing, constraint logic, expert systems, database interaction-- all look and feel completely native, it's beautiful.
In fact, I think precisely due to this elementary difference, it is reasonable to expect it to take longer for Prolog implementations to reach the practical applicability we are now seeing in neural networks after a few decades of research and improvements.
a) You would never train staff or hire experts on Prolog for such few problems and...
b) You could probably do much better with a heuristic algorithm anyway. Especially on hardware of the day when Prolog came out, but even today I imagine this holds true.
Prolog may be useful for quick exploration of a problem space. But for code that needs to run frequently, there just isn't a great need for what Prolog has to offer.
I've been teaching myself Prolog, and it's sufficiently different that I feel like I'm learning to program all over again. You can sort of pretend that predicates are just funny functions, where you have to put the return value's container into the argument list, but that's not really what's going on. I loved reading the docs for SWI-Prolog, where most of the predicate docstrings start: "True if...". You can say that the length predicate returns the length of a list, but really it returns true if the given list has a length equal to the given integer. It will tell you the length of a list, sure, but it will also do the reverse:
?- length(List, 5) -> List = [_,_,_,_,_]
Nuts!
? evalo(e, 6)
(+ 3 3)Is that just to distinguish them from normal "eval" (in this case), or is there a deeper meaning?
So yeah, it's just to distinguish from the usual semantics.
- historical inertia, i.e., SQL being better known, being taught to a lot more people, already used everywhere; even if every new project started Datalog, we would "still have SQL databases" for many decades, see the recent publicity for Cobol
- aggregate functions, sorting of results
- syntax: "select foo, bar from table_with_many_many_columns" is easier to get right than "table_with_many_many_columns(_, _, _, _, Bar, _, _, _, _, Foo, _, _, _)" (though in most other aspects Datalog syntax is indeed superior)
That's where Machine Learning and Neural Networks are much better : they can organize enormous amount of arbitrary data (not only text and words) way more faster that a programmer or an expert, given a sufficiently big enough dataset.
In other terms, prolog "doesn't scale" with the diversity and ambiguity of humans knowledge.
There are some modern Prolog versions that try to use some better searching algorithms, but the language hinders that change.
Whether or not this is true, Prolog is so much more than just "searching". Unification gives you all the powers of pattern matching in functional languages, but adds a lot of extra power on top of that. For anything working with tree-shaped or even DAG-shaped data, Prolog is an excellent choice.
I have spent much more time looking for unexpected exponential runtime than the time it takes to implement the code without unification. That's the main reason I abandoned the language.
The one thing I never got past was its difficulty in dealing with large, mutable sets of data. So, for example, given an array of a million or billion elements that are being rapidly modified, even the most trivial sorts of backtracking become infeasable. Maybe there's some elegant way to do it, but I never got it.
(And difference lists need to die.)
Im just finishing a class using Prolog and CLP(FD) and I've really enjoyed using the language. And while lots of things in programming aren't easy at first, I'm just saying its hard to see wide adoption of prolog for that reason.
Datalog is still a good idea imho!
which is a chapter of the book