What Hacker News says

YeGoblynQueenneJan 2026

And also "Prolog Programming for AI" by Bratko and "Programming in Prolog" by Clocksin and Mellish.

Although these days I'd recommend anyone interested in Prolog starts in at the deep end with "Foundations of Logic Programming" by George W. Lloyd, because I've learned the hard way that teaching Prolog as a mere programming language, without explaining the whole logic programming thing, fails.

thread

YeGoblynQueenneOct 2018

AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java, by George Luger, free from the author's personal page on Florida State uni, here:

https://www.cs.fsu.edu/~cap5605/Luger_0136070477_1.pdf

This is an excellent resource also for LISP (and Java!) and AI algorithms, particularly various search strategies.

I'd also recommend the standard Prolog textbtook, Prolog Programming for AI, by Ivan Bratko. You can most likely find an edition in most university libraries.

I've learned a lot from Adventure in Prolog, a Prolog tutorial on the Amzi! Prolog website (though I used a different Prolog to do the exercises, which is a very good sign of nice, basic and portable examples):

http://www.amzi.com/AdventureInProlog/advtop.php

Those are practical resources. On a more theoretical side, another commenter recommended Perreira & Shreiber, which I can't recommend enough. Also, for a more formal text on logic programming, with proofs and all, the classic reference is J. W. Lloyd, Foundations of Logic Programming. Again, you can probably find a copy in your friendly neighbourhood university library (or, er, google it for a very bad copy of dubious legitimacy, like).

thread

YeGoblynQueenneJul 2024

>> And Erlang. And Haskell. And OCaml. And F#. And..

Thanks, I didn't know that. I took the article to mean that this kind of one-sided pattern matching is unique in Elixir. My misreading.

From what I've seen it's true that most languages that have support for pattern matching have special constructs for it, whereas in Prolog it's baked in to the only data structure in the language, the term, which can be a single variable (a logic variable that can unify with ... anything).

I don't know how useful or not unification would be in a language other than Prolog to be honest. In Prolog it's an integral component of the Resolution-based theorem prover used as an interpreter of Prolog programs: resolution proceeds by unifying Horn goals to the heads of definite clauses, to produce new goals, recursively. More over, when one runs a Prolog "query" the result of the query itself is the substitution of the variables in the query, i.e. the substitution that makes the query true [1]; a substitution derived and propagated by unification.

I like how George W. Lloyd describes the use of unification in Prolog. Apologies in advance for the long-form quote:

The idea that first order logic, or at least substantial subsets of it, could be used as a programming language was revolutionary, because, until 1972, logic had only ever been used as a specification or declarative language in computer science. However, what [R. Kowalski, Predicate Logic as a Programming Language, 1974] shows is that logic has a procedural interpretation, which makes it very effective as a programming language. Briefly, a program clause A <- B1, ..., Bn is regarded as a procedure definition. If <- C1, ..., Ck is a goal, then each Cj is regarded as a procedure call. A program is run by giving it an initial goal. If the current goal is <- C1, ..., Ck, a step in the computation involves unifying some Cj with the head A of a program clause A <- B1, ... Bn and thus reducing the current goal to the goal <-(C1, ..., Cj-1, B1, ..., Bn, Cj+1, ..., Ck)θ, where θ is the unifying substitution. Unification thus becomes a uniform mechanism for parameter passing, data selection and data construction. The computation terminates when the empty goal is produced.

And that's first-order SLD-Resolution, with unification, in a nutshell! From George Lloyd: Foundations of Logic Programming, second Ed. 1993.

There's a copy of the book here:

https://archive.org/details/foundationsoflog0000lloy_o7l2

But it's a limited preview :/

________

[1] ... well, the substitution that makes the Horn goal that we call a "query" false, in reality, because Prolog proves things by refutation but we fudge it a bit.

thread

YeGoblynQueenneApr 2023

Btw, the reason I want to write to Kowalski is not just the history of meta-interpreters. There's a question that only he may be able to answer. The question is about the Subsumption Theorem in Inductive Logic Programming (ILP).

Briefly stated, the Subsumption Theorem, as it's known today, is that a clause D is entailed by a logic program S if there exists a clause C that can be derived from S and such that C subsumes D.

Similar statements are also found in the logic programming literature, for example in Lloyd's Foundations of Logic Programming.

There's a bit of a mystery about the origins of the Theorem.

A series of similar papers by Ninenhuys-Cheng and de Wolf point out different definitions and apparent rediscoveries of the Theorem, and proofs of it, some of them mistaken, in the ILP literature. The paper I use as my reference is titled The Subsumption Theorem in Inductive Logic Programming: Facts and Fallacies. (http://homepages.cwi.nl/~rdewolf/publ/ilp/ilp95.pdf found in Ronald de Wold's webpage, here: https://homepages.cwi.nl/~rdewolf/).

That paper claims that the Theorem was probably first stated by R. C. T. Lee, in his 1967 doctoral thesis. It seems this information comes from Kowalski, in a paper that I can't access fully (cited in the Nienhuys-Cheng and de Wolf paper). However, the earliest statement, and proof, of a Subsumption Theorem that I could find is from Robinson's resolution paper, published in 1965, where subsumption is also defined. The Subsumption Theorem in Robinson's paper is slightly different than the one found in the ILP literature, in fact it looks to me like the modern version of the Subsumption Theorem is a corrolary of Robinson's one.

If I were to rephrase Robinson's Subsumption Theorem in more modern terms, what it says it as follows:

[Restated Subsumption Theorem] Let S be a finite set of clauses and C ≠ D be two clauses that are not in S and such that C ≼ D (C subsumes D). Then, S ∪ {C,D} is satisfiable if and only if S ∪ {C} is satisfiable.

So this statement is missing the explicit requirement for derivation of C from S, but if S ∪ {C} is satisfiable then C should be derivable from S by Resolution.

Now, R. C. T. Lee's thesis is not available anymore, it seems, and it wasn't available to Nienhuys-Cheng and de Wolf, either, so there's a lot of uncertainty around what, exactly, Lee stated and proved, and how it is similar or different to Robinson's Subsumption Theorem, and to subsequent statements of the Subsumption Theorem in ILP. Kowalski may be able to clarify the confusion.

I'm posting this in the very slim chance that you might have some intuition about all this, in which case I'd be grateful to hear it.

thread

TwisolJun 2018

So this is a bit of a tangent, but your Santa Claus example really clarified something I've been reading about recently. I'm reading Lloyd's "Foundations of Logic Programming", which essentially explains the fundamentals behind logic languages like Prolog. We write programs using uninterpreted functions[0] to represent our data, and define predicates to drive the program. The idea of using the Herbrand universe is that it gives a convenient universal starting point: if the program has a model in some universe, it will have a model in the Herbrand universe, and if the program does not have a model, it cannot have a model in the Herbrand universe.

Your Santa Claus example helped me understand why the Herbrand universe is only useful if you restrict yourself to clauses (disjunctions under universal quantification). The Herbrand universe consists of all objects one has named (and objects one can form with function symbols, but we have none of those here), so it must necessarily falsify "~E x. x = Santa Claus". It's easy to find a model where this statement is true (take the empty universe, or the universe which contains only the Tooth Fairy), but there is no model of this statement in the Herbrand universe.

[0] https://en.wikipedia.org/wiki/Uninterpreted_function

thread

YeGoblynQueenneMay 2018

>> This expects programmers to have a non-trivial understanding of Prolog's implementation. I was wrong to say that an understanding of the compiler was needed, but programmers do have to understand unification and the order of evaluation used by the language.

Actually, I'd go one step further and say that in order to make full use of Prolog you need to understand SLD resolution and definite clauses, otherwise you'll never really get what the hell is going on in there, or why the interpreter works the way it works. To program in Prolog you do need a non-trivial understanding not only of its implementation but also of the substantial theoretical work that led to its implementation as the prototypical logic programming language (e.g. see J. W. Lloyd, Foundations of Logic Programming).

The thing is, there is a lot more going on with Prolog than "here is a language that can be used to control a digital computer". Logic programming is the continuation of the work of the logicians of the early 19th century, the evolution if you like of mathematical logic. It has to be understood in that context- or not at all.

You make the point that there is an operational, or imperative, reading of Prolog code, that must be understood alongside the declarative one. That is correct, in my opinion, but I don't see why it's a problem. For one thing, programmers taught on imperative languages (i.e. the majority) should not really have a problem with the operational semantics of Prolog (e.g. what you see when you trace Prolog code in the four-port tracer, the order in which goals are called, succeed, fail and are retried etc). Understanding the semantics of the cut is maybe not trivial, but again that is a problem only if someone tried to sell you Prolog as an "easy" or "friendly" language; which it isn't.

More importantly, Prolog has its declarative reading also, which is something almost unique to it. So maybe Prolog is not a perfect, pure implementation of the declarative paradigm- so what? Should we throw the baby out with the bathwater and say, hey, Prolog is only 99% declarative, so I'll just stick with Java, which is 0% declarative? That doesn't make much sense! At least not if you somehow want to use declarative programming- if not, then Prolog is not an option anyway.

>> Finally, I believe that the cut operator also makes parallel processing implementations of Prolog very difficult.

You mean parallel execution of Prolog code? Not parallel implementations of the language? I don't see that the cut is a problem there, but then again I don't have any experience trying to parallelise Prolog code. There is again a promise that Prolog's execution scheme is uniquely disposed to parallel execution. Maybe it is, maybe it isn't. But that is not the most important characteristic of Prolog.

The most important characteristic, like my previous comment says, is that Prolog is an automated theorem prover for first-order logic theories. Anything else that it may do is by the by- and, conversely, any compromise it has to do on the way there, provided we're talking about pragmatic compromises necessary to get the language to work on limited resources (i.e. like the cut), is worth it.

Of the sources you quote I'm familiar with Clocksin & Mellish, Bratko and Sterling & Shapiro. Those are good books, although Bratko probably tries a bit too hard to make Prolog sound a bit like Pascal. I would also recommend Richard O' Keefe's The Craft of Prolog and George Lugger's "AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java", online here:

http://wps.aw.com/wps/media/objects/5771/5909832/PDF/Luger_0...

>> Perhaps Logic Programming will make a comeback aided by the new advances in automated theorem proving.

Nah, I don't think so. I think it will remain a niche thing, of interest primarily to academics and programmers who like obscure languages. But that's OK. Not every language needs to be Java or Python.

thread