Hacker News new | past | comments | ask | show | jobs | submit login
The Power of Prolog (metalevel.at)
381 points by fogus on April 8, 2020 | hide | past | favorite | 82 comments



Thank you very much for your interest, I greatly appreciate it!

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!


Some coming features of Scryer Prolog for those interested:

- 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!


I'm fairly new to programming in Prolog - how does Scryer Prolog compare to more common implementations like Swi Prolog?


Scryer is not yet as fast or feature-rich as SWI. SWI has been in business for about 30 years longer, so that shouldn't surprise anyone. Also, Scryer is committed to strict conformance to the ISO Prolog standard, which SWI has disregarded for a while now.


Thank you a lot Mark for participating in this discussion, and for all your work on Scryer Prolog during the last few years!

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!


Yes, thank you for the Power of Prolog! Scryer was and is being written under its influence.


> very fast yet logically pure I/O

Sounds interesting, do you have a link or something else to share regarding your conception of logically pure I/O?



From the interface (mostly yes, that, is apart from the impure extensions added later, and that chars are used and not codes) it is the same. But from the implementation behind it´s different. In particular from the space requirements. A text of n characters requires 3 * 8 * n bytes in SWI, but n + 2 * 8 bytes in Scryer. So there is a factor 24 in space requirements (on 64bit).

Also, there is now ample room for input that SWI once almost offered.



How usable is Scryer Prolog? Is it a single executable, or does it have a complex install?


Decently, I'd say. It is a single executable that you have to build yourself. If you want a recent build, there are a few extra steps, but they're nbd. There are build instructions in the README ("Installing Scryer Prolog") at:

http://github.com/mthom/scryer-prolog


> Scryer is a Rust-based Prolog implementation that is freely available

!

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.


While I'm not interested in learning Prolog at this time, I skimmed through both your book and site and find it really easy to understand. The writing is simple (I bet it takes a lot of effort to produce simple to undestand writing) and what seems to be lower-than-usual text/information density of the page both helps with reading and makes the text beautiful - a joy to read. Thank you, I hope to revisit this bookmark once I have free time again.


Thank you a lot, it is really encouraging to hear this!

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!


I want to say thank you, for your book and for all the work you're doing promoting and improving Prolog.


You are very welcome!

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!


You're very kind. It's unfinished, and I doubt whether it will ever be useful for anything (other than just being kinda neat in and of itself.) I need to deal with compiling loops/recursion/fixpoints. But thanks! I appreciate it.

Your advice to use CLP(FD) for the semantics of integer math operations was fantastic!


You don't mind if I port Thun to Scryer Prolog, do you? With full credit to you, of course. I'd like to include it as an example.


Not at all, that would be awesome. It's GPL'd, have at it. (^_^)

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]).
Just to point out, in SWI Prolog the ints are "BigNums" while in GNU Prolog they're machine words (so modular arithmetic, mod 2^32). You could use Rationals or make up some other semantics. This all gets into Categorical paradigm programming. http://conal.net/papers/compiling-to-categories/ The same (point-free) expression can be used to develop concrete programs over various categories: Hardware circuits, partial evaluation, differentiation, dataflow graphs, and so on.


Hadn't seen this before. How nice that you called it Thun! Warms my heart.


Cheers! Manfred von Thun seems like he was a pretty great guy. I wanted to honor him.


Great article and thank you very much!

As someone with only fleeting knowledge of Prolog, this was by far the best introduction I've come across.


It would help if you could point users to a Prolog implementation that is compatible with your examples. I couldn't find any in the book, but going up to your home page I found a couple of references to SWI-Prolog, and installed that, but the first two examples in the book resulted in syntax errors regarding the "#>" and "#=" operators.


I can't remember exactly where it is mentioned (it is somewhere) but in SWI-Prolog you need to put

  :- use_module(library(clpfd)).
at the top of your file (or just use_module(library(clpfd)). at the console)


Or

    :- use_module(library(clpz)).
for its successor which runs with SICStus and Scryer.


Is there a reason why anyone would choose prolog today instead of a library? Like racklog [https://docs.racket-lang.org/racklog/]. All the benefits of prolog, with none of the cost of using a new language and integrating it into your project.


Prolog is fun. It's fantastically fun. It's maybe one of the most fun programming languages in existence.

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.


I think you have a point, but not sure your example illustrates it very well - is Racket really any less niche than Prolog? On the contrary, I would say.

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.


I was using racklog as an example of a library you would use if your app was programmed in Racket; I wasn't suggesting that you would decide to use racklog in a C project or something over prolog.


I use it. Not regularly, not for production, but it's cute for rapid prototyping.

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.

[1] https://en.wikipedia.org/wiki/Association_rule_learning


This is an interesting question, and I hope someone with experiences on both sides could chime in. I would expect an prolog-like implementation in any mature language a possibility and retain language native syntax while garnering all the advantages of prolog.


One of the advantages of Prolog is that there is an ISO standard for it: The standard prescribes, in many ways, which syntax is acceptable, which errors must be generated in which cases, and which results must be produced.

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.


Earlier versions were discussed in 2018: https://news.ycombinator.com/item?id=17121028

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)


Prolog reminds me of Cyc.

"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.


I think that's a valid point. Cyc consisted of a set of frames/predicates with real world relations and concepts. And then the logic part on top would try to find inconsistencies, generate new predicates, and of course some kind of unification to answer questions over predicates.

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.


I've found this channel a few months ago and my wife thinks I'm crazy when I'm watching it. "This looks like work, but harder!!". Awesome content! Thanks for posting it :)


Thank you so much, and you are welcome! That's an awesome slogan!

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.


You do a very good job making it approachable. I'll make a PoC this year using Prolog in a specific application regarding contract generation (LawTech). It's surely thanks to your insights!

Now that I know your handle, I'll ping you when I have some news :)


Thank you a lot, I would greatly appreciate this!

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.


See also Mercury, FP logic programming like the love child of Prolog and Haskell https://en.wikipedia.org/wiki/Mercury_(programming_language)


PicoLisp also has a prolog in it.


Prolog look like it would be the correct tool for the job for a certain class of problems, I wish I had time to learn it. I always wonder why it doesn't get more attention.


I'm guessing because it's so fundamentally different from most of the other programming languages out there, which I sometimes think are just variations on the variable/function/control flow theme (and yes, I've gone fairly far in Lisp).

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!


ever seen Friedman and Byrd talk about kanren ?

    ? evalo(e, 6) 
    
    (+ 3 3)


I have seen a few *kanren posts now on HN, and they always have their operators ending in "o".

Is that just to distinguish them from normal "eval" (in this case), or is there a deeper meaning?


I think it's yet another typographic ~wonder. From what I recall it's a ° to denote relation (relat°) but made into an ascii 'o'.

So yeah, it's just to distinguish from the usual semantics.


Double nuts!


A related question is why do we still have SQL databases when everybody could be using Datalog?

https://en.wikipedia.org/wiki/Datalog


Some guesses, I have no skin in this game:

- 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)


Take a look at datomic, it uses datalog.


Seems awesome from the outset. I especially like "Datomic stores all history, and lets you query against any point in time."


The biggest limitation I find about prolog is that the model is limited to the vocabulary and knowledge of the author. If the author only speaks English, the prolog program only works in English. If the author doesn't know anything about medicine, it will be very hard to model all the medicinal knowledge in the world (which could even be in different language).

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.


This is what Im looking for in this thread - accessible critiques of prolog. Could your first issue be solved by a i8ln framework? Im not sure I accept your second issue - why would someone who doesnt know anything about medicine build a prolog program about medicine? But further to this, is there value in articulating the results of a machine learning algorithm as a prolog program?


Nowadays, ontology-management systems like Protégé and SPARQL can more or less solve all problems prolog can solve, while providing higher-level formalisms and with the guarantee your query will terminate.


For most queries, that might be true. However, the termination guarantees of Description Logic (OWL) reasoning and SPARQL (more precisely: the specific time complexity bounds) immediately imply that Prolog is more expressive. Even if we don't consider such ridiculously long-running queries, there's still limits to what can be expressed in DLs and SPARQL: since OWL doesn't have any variables, you're restricted to tree-shaped queries (indeed, this is a major part of why OWL reasoning is decidable), and SPARQL doesn't allow you to express any constraints on the intermediate nodes in a property path expression. Neither of these restrictions exist in Prolog.


i've never used prolog seriously despite having a few problems very well suited for declarative solutions - variants of job shop scheduling, rule based workflows, etc. most reasons for why prolog didn't take off in my job are non-technical - it looks weird, it's hard to debug, integration with python isn't obvious and one worry i had (never tested) was that while the idea is to tell the computer about the problem, the real art was placing cuts.


Doesn't guaranteed termination just mean it isn't Turing complete and thus by definition can't solve all problems prolog can solve?


Absolutely. But in practice, I can't think of a problem that coulnd't be solved with OWL (or some other formalism like answer set programming) and where prolog would be the best solution (rather than more "traditional" programming languages). There are certainly a few, but not enough IMO to draw a lot of attention to prolog.


Hmm programs terminating because Protege is guaranteed to slag your machine is a feature had overlooked.


> I wish I had time to learn it. I always wonder why it doesn't get more attention.

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.


I think the reason no one uses Prolog is simply because generalized backtracking problems (i.e. the problems you would use Prolog for) are too computationally expensive and infrequent enough that:

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 just posted https://news.ycombinator.com/item?id=22830791 in a cousin thread addressing this criticism. Prolog is about more than search, unification is a very very powerful tool for matching and transforming data.


Complementing this, neural nets shared the same fate in an AI winter, in fact in the AI winter preceding the one you mention, and yet they now attract significant attention. In large part because the hardware is better, and also because the approaches are now better.

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.


Personally I think Prolog is great* and I'm learning it for funsies but neural nets are a specific approach that people have been writing in Python, because they already know Python. Prolog is a whole thing. Kind of an apples and oranges problem.

* I mean seriously it's fantastically expressive: parsing, constraint logic, expert systems, database interaction-- all look and feel completely native, it's beautiful.


Absolutely, I fully agree!

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.


Unfortunately, it's not. There is almost no problem that requires searching through some complex enough space for a specialized language be worthy its use, and yet have a small enough search space for zero knowledge depth-first search to be viable. (Database querying may be the one large problem, there are some comments about Datalog already.)

There are some modern Prolog versions that try to use some better searching algorithms, but the language hinders that change.


> There is almost no problem that requires searching through some complex enough space for a specialized language be worthy its use

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 do risk saying that if you are not doing search, then Prolog gives you way too much power.

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.


I absolutely loved Prolog and CLP(R) back in the day.

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.)


I've always had difficulty debugging functional and formula based logic, and others have said similar. Imperative is just easier to "fractal-ly dissect" to me. Debugging seems to be a reoccurring theme of many "high abstraction" techniques that perhaps keep them out of the mainstream. I known many disagree, and this claim often triggers heated debates.


If anyone loves both Prolog and Python, I wrote a mini-prolog interpreter in Python just over a year ago which you can check out here: https://github.com/photonlines/Python-Prolog-Interpreter


snap, but mine is in javascript and references a couple of predecessor javascript mini-prolog interpreters: https://github.com/mattsouth/dprolog. I still need to read that WAM book. But I tell that to myself everytime it comes up here.


Just a conjecture, but I think the main drawback of Prolog is its hard to see it having popular support. Recursion, logic programming, and constraint satisfaction are challenging paradigms which doesn't lend well to doing something useful quickly, as opposed to something like Rails.

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.


has anyone here ever used prolog in production - like real world, making money, production? How about in real world research where it produced no-kidding actual value? From what I can tell it is only useful these days as a academic example of an alternative type of language. Is there something else that has carried the torch forward?



My dad wrote a multi-thousand line turbo-prolog expert system to do airline gate assignment at JFK in the 80s https://scholar.google.com/scholar?cluster=74202497920445652...


TerminusDB is used commercially and most of it is written in prolog, although the underlying storage engine is written in Rust.

Datalog is still a good idea imho!


I did write a library management program for a large insurance company in Prolog, around 1988.


https://www.metalevel.at/prolog/business

which is a chapter of the book


OT, but I was entertained by the fact that, as soon as I went to the page, the "Recursion" link was purple.


prolog should be used as a library DSL, embedded, within programs written in other languages




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: