Now I wonder if I should write some code to do this dynamically, i.e. check whether a predicate is tabled and re-order its clauses in the database. Could the compiler do that as an optimisation?
I routinely run out of table space in my ILP stuff. Learning recursive predicates is even more dangerous than coding them by hand 
I think the original paper on bottom-up computation with Datalog was Bancilhon F., Ramakrishnan R. An amateur’s introduction to recursive query processing strategies. in: Proc. of ACM SIGMOD’86.
Here are a few open-source projects on Datalog that I know of; I don’t know which algorithms they use or how fast they are compared to Prolog tabling.
and I’ve skimmed some papers by Kristopher Micinski and his students, and there have been some discussions on Mathstodon
See also Yedalog: Exploring Knowledge at Scale
profile/1.
True. Activation is not the problem here. After activation it feeds edges into the continuation, which implies retrieving the continuation, calling it (guarded by delimited continuation as it may hit a new tabled call). On success, add the new result and again feed that into the continuation.
According to profile/1, 63% goes into `$tbl_wkl_add_answer’/4, a foreign predicate that adds an answer to the table and, if it is new, to the “worklist”, scheduling the new one to be pushed through the continuation as well. 24% goes to calling the continuation, about half of that to the actual edge/2 call.
Most (70%) of the time of `$tbl_wkl_add_answer’/4 goes to updating the trie. Still, if I recall correctly, comparing trie operations between SWI-Prolog and XSB show now big difference. Anyway, the goal of the tabling project was first of all to provide a second implementation of tabling including incremental tabling and well formed semantics as well as bunch of other unique features in XSB’s tabling. We never got to looking careful at optimizing the implementation. There is probably quite a bit of fairly low hanging fruit.
In some cases, probably yes. As you are doing ILP, you can optimize the generated clauses, no? If possible, when using tabling, make the recursive call first if that immediately triggers a variant goal. That has two advantages: it reduces the number of tables and it provides a small captured continuation, saving space and time.
Thanks, that’s a great tip. I’ll see if it can reduce the tabling overhead in my systems.
Well, I can inspect and modify a clause before it is added to a program, so yes, in that sense I can optimise. I usually refrain from it because that’d be done smack in the middle of a critical path of the learning system but if it ends up saving space then it’s an important optimisation. Without certain heuristics I have managed to bring a 256GB RAM server to its knees just with exploding tables.
Yes, but if you save a lot of runtime, you win anyway. Applying the heuristic to tabled clauses to try and get the recursive call as early as possible is probably worthwhile. Surely if your clauses are pure and thus swapping goals in the body as well as swapping clauses has no semantic consequences. For Prolog in general, that is harder.
Yeah, the programs my systems learn are datalog in fact, but anyway have no asserts, retracts or cuts and so on, so changing the order of clauses won’t change their semantics.
But I have confused myself and you with me. I didn’t mean I wanted to optimise the programs learned by my system. What I meant was I want to optimise the learning system itself.
The learning system includes some predicates that are tabled but there’s a flag to set tabling on or off, exactly because tabling takes up so much RAM. There’s an alternative way to avoid infinite left-recursions (depth limiting) and in some cases it’s better to use that, instead of tabling. In such cases I turn the tabling flag off.
So what I wanted to do is check the tabling flag and when it’s on, re-write my learning system’s code in the dynamic database so that it’s ordered like you say, with recursive clauses after the base clauses. Or I could assume the tabled version as default and re-order when the flag is off, it doesn’t really matter.
I don’t generally need to table the learned programs because they’re not particularly expensive to run once they’re learned. But the learning can be expensive unless recursion is kept in check. The learning system is a meta-meta-interpreter (i.e. a second-order Prolog interpreter written in first-order Prolog) and it learns by an SLD-Refutation proof of the training examples. Where it gets expensive is that it can easily attempt to construct a non-terminating recursion and prove it. This is where the tabling comes in.
In particular, what I table is the meta-meta-interpreter itself. I think this is a bit peculiar as a use of tabling. The alternative is to write my own SLG-Resolution meta-interpreter but it seems like that’d take me a couple of years and SWI-Prolog’s tabling seems mature, so I just table my meta-interpreter and let you do all the hard work 
Can’t you get away with time and/or depth limit for your case? I.e., simply reject non-terminating programs and let the ILP system figure out terminating alternatives?
Yes, I do use depth-limits as an alternative to tabling, but that requires the user to set the depth limit since it’s not always going to be the same in fact it can vary wildly depending on the program we’re trying to learn. If the depth limit is too large the learned program doesn’t change but it takes longer to learn it.
Time limits are much harder to estimate beforehand: if there’s a solution we can’t know how long it will take to reach it, but we know we want to reach it. So I don’t use time limits.
See, what’s going on here is that ILP has advanced to the point that it can learn arbitrary logic programs with recursion at any depth and between any number of clauses with any number of literals or arguments. Add predicate invention to that and we can basically learn predicates with arbitrary invented auxiliaries, nested arbitrarily deep and calling each other and the main predicate any which way, including in mutual recursion. In other words the learned programs can be as complex as system resources will allow. So the problem is to reduce the use of system resources without limiting the complexity of the learned programs. Traditional depth and time limits aren’t great for that because they cut off everything automatically and there’s no way to know how close or far we are from reaching the goal, at that point. Tabling is so much better because it doesn’t rely on “magic” cutoff points. But like you said it trades off time for space and that can make the RAM go boom.
As a historical note, earlier ILP, based on inverse entailment (like in Aleph, or Progol) was based on a principled sort of depth limiting (bottom clauses) but that still turned out to be incomplete and we couldn’t learn the kind of recursive programs we can learn now. See:
I understand. I’d expect recursion to happen over recursive structures in the input you are trying to learn, no? If that is true, there is a simple upper limit: number of “tokens” in the input times longest recursive path through the call graph. In most cases unbounded recursion gets deeper very quickly, so setting the depth limit a relatively high should not matter too much.
But, there are additional advantages to tabling such as performance that is less dependent on goal and clause ordering.
For curiosity, do people use LLMs to generate and debug candidate programs in the context of ILP these days?
In short, yes, but we can’t know the call graph before hand. The learning procedure is really just an SLD-Refutation, so we can’t know whether it will end in an empty goal clause, a non-empty goal, or not end at all, until the proof terminates… or doesn’t. If we could know that without carrying out the proof, well, then, I guess we wouldn’t need to carry out the proof in the first place. In any case any approach that can limit the call graph in an SLD-Refutation would also work in ILP (or in any case in Meta-Interpretive Learning, the specific approach I’m studying) but there’s no such thing.
What Inverse Entailment did with Bottom Clauses is that it tried to calculate exactly that kind of depth bound: the number of steps it takes to “walk over” the “background knowledge” (that’s a Prolog program that is given as input along with training examples usually in the form of ground facts). What I, personally, have learned from that period of ILP is to be very careful about trying to apply arbitrary limits, or even principled ones. This is not minimax with alpha-beta cutoff. We’re trying to prove a program that we don’t yet have, so we are in a state of very high uncertainty. It’s better to let Resolution do its thing (which comes down to eliminating uncertainty, if you think about it very hard) without intervening.
Resolution is hard core. I think it’s greatly overestimated. Did you know it’s also the basis of one of the two dominant branches of SAT-solving algorithms? That’s the Conflict-Driven Clause Learning approach, itself based on the older Hillary-Putnam approach that was almost pure resolution (although in the propositional case, not first-order).
I haven’t seen that, specifically, I don’t think. I know people generate Prolog with LLMs and say that they do ILP, though. I’m not sure how to react to that, to be honest. ILP essentially started as an attempt to “invert deduction” as a way to achieve induction. This is an old idea that probably goes all the way back to Aristotle and IIUC was popularised by William Stanley Jevons (the same Jevons as in Jevon’s Paradox and Jevon’s Number). Obviously LLMs don’t work that way.
Inverting deduction in a logic programming setting was I believe first proposed by Gordon Plotkin in his doctoral thesis in 1972 (https://era.ed.ac.uk/items/fa0309ce-00e7-4373-b39e-0d9ce45f0b21), just a few years after Robinson introduced resolution. In the Introduction to his thesis Plotkin describes a conversation with R. J. Popplestone (of Poplog fame) in which Popplestone remarked " that, just as the unification algorithm was fundamental
to deduction, so might a converse be of use in induction." In the context, “deduction” essentially meant Robinson’s recently-introduced Resolution. This motivated Plotkin to invert unification. Plotkin didn’t call his work “ILP”. The same line of investigation was picked up by Stephen Muggleton in the 1990’s who proposed Inverse Resolution and named the field in 1991. Inverse Resolution was followed by Inverse Implication and then Inverse Entailment. All those were essentially attempts to make Prolog, or in any case, Resolution-based deductive logic programming, work in an inductive manner.
What that means in practice, in ordinary logic programming we have a set of definite clauses, our logic program, and we prove a Horn goal (definite clauses without heads). To make Prolog inductive we also start with a logic program, call it B, that we call the “background knowledge” in ILP, but this time we have a set of Horn goals,our positive examples, or E+, that cannot be proved with B. So we need to extend B to prove those goals. If we can do that successfully, we end up with a new set of definite clauses, call it H (for “hypothesis”), that when added to B, proves E+ (more precisely, B and H entail E+). In the same way if we have negative examples E-, we want H added to B to not prove E-.
All that is quite different from generating Prolog code with an LLM, although it can achieve the same goal, if the goal is to automatically generate Prolog. What’s missing though is the ability to include “background knowledge” and to make sure that the generated code is consistent with it. LLMs can’t really do that very well at all.
And in any case, if you’re going to use an LLM to generate code, then why generate Prolog, an obscure language that very few people know or use? LLMs can genearte Pythoh, javascript, C#, Java, etc, just as well and probably better than Prolog. There’s very little incentive AFAICT to do “ILP with LLMs” then.
That’s how Meta-Interpretive Learning works. Those “higher-order hypotheses” (really, second-order definite clauses) are added to the “background knowledge” and used to prove examples by resolution. During the resolution proof, by unification, the second-order variables in those second-order definite clauses are bound to predicate symbols. If the proof complete successfully, a first-order hypothesis, H, is constructed by applying the resulting substitutions of the second-order variables back to the second-order clauses. So in your example L gets bound to “parent”, and R to “anc” etc. First order substitutions are discarded unless we want to learn a program with constants in which case there’s a special notation to do that.
The trick is to not have to define second-order definite clauses that match the program you’re trying to learn exactly, because then you’re just coding the answer by hand. There’s some work on that, particularly by myself, e.g. here:
I don’t think LLMs can do that very well. The example you give, ChatGPT sticking to arbitrary rules that have nothing to do with the task at hand, is typical but in general LLMs don’t do deductive reasoning, let alone resolution, so they can’t really tell you what are the logical consequences of a logic program, or do all the simple but powerfull things that resolution with unification can do.
? You generate a program. Next, you compute the call graph for that program and you find the longest cycle as well as the longest non-cyclic call chain. Now, for each test you set the depth limit to InputTokens * CycleLength + CallChainLength + SomeSafety.
Of course, this is overhead, but I think pretty small compared to all the work you are doing in an ILP iteration anyway.
Why not? You tell it “here is a background program, here are positive and here are negative examples, can you extend the background program to covert this test data as good as possible?”
That is not so clear. I once asked ChatGPT to do some formalization of natural language and it spontaneously suggested to use Prolog for that. Could of course be because I chatted before about Prolog. On the other hand, I mostly used (used as I switched to Claude since) it for C and only some tiny experiments with Prolog. Besides, a classification algorithm in Horn clauses is much easier to understand than most imperative code doing the same. If you turn this into an agent where the LLM can run the programs it generates I’d expect it to behave way better than the Aleph state-of-the-art (see below).
P.s. Thanks for summarizing the state. I did some work with Steve Moyle when he was doing his PhD on Aleph in Oxford. That is about what I know about ILP. Good to see how things progressed.
That was not my intend. It is intended as SLD with a protection that kills non-terminating SLD inference (assuming you check that the depth limit has been exceeded and you reject the program in that case).
Time limit is complicated. call_with_inference_limit/3 is better. I guess it is still hard in ILP context though, unless you state that programs above a certain complexity are not acceptable. Non-terminating programs are always unacceptable 
I consider that a dubious statement. Prolog inference is logically correct (within its limitations). With LLMs you never know. It is like asking an LLM to do arithmetic. For simple problems this actually works, for more complicated expressions it is between a little wrong and really very wrong. What an LLM can do is translate an NLP problem into an arithmetic expression and use a calculator. In the same sense, an LLM can generate a Prolog program. Actually, people are doing that
Hi all — first post here, thanks for having me
@Sean, I had exactly the same need recently and ended up building prolog-trace-viz (https://www.npmjs.com/package/prolog-trace-viz) for it. Might be worth a look.
Prolog has been a bit of a rediscovery for me lately — genuinely loving it. Happy to answer any questions about the tool.
Yes, but how? The reason I want to avoid infinite recursion is so that I can “generate” a program to begin with.
“Generate” is really not the right terminology. You can generate a program by starting with an empty clause and then adding one literal at a time to it, until the program passes some kind of test that says you have the right program. This has been tried exhaustively in ILP over 30 years and it doesn’t work.
One reason is efficiency: a logic program is a set of clauses and a clause is a set of literals, so if you generate all possible logic programs you are generating the set of sets of sets of literals: a powerset of a powerset. Obviously that blows up immediately. You can try to reduce combinatorial explosion by being clever with heuristics and pruning and whatnot, but at the end of the day you’re effectively searching a very large haystack (the set of all progams) for a tiny needle (the program you want). In fact, the larger the set of programs you can generate, the greater the probability of error, because there are many programs that look like the one you want, but aren’t exactly that. Then you need many, many examples to try and distinguish between similar-looking programs.
The alternative I’m discussing, and the approach I’m championing if you will, i.e. Meta-Interpretive Learning, instead casts the learning problem as an SLD-Resolution proof. This has many advantages, including efficiency (obviously you don’t need to search a powerset of a powerset to carry out an SLD-Resolution proof). But, exactly because it’s SLD-Resolution, you have to be careful to avoid infinite recursions.
But those infinite recursions happen during the SLD-Resolution proof that gives you the program you’re looking for. So you have to do whatever you do to avoid infinite recursion before you have a program, during the learning phase.
Well the reason is as you say below:
LLMs don’t do proofs by Resolution. At best they can approximate Resolution. But I guess I need to give you an example of what I mean by that. Stay tuned, it’s lunch time
The problem with this is that you have no guarantee that your agent setup will ever generate a correct program. What you’re proposing is basically a generate-and-test approach, but generate-and-test is only as good as its generator. If your generator can’t generate the programs you want, it doesn’t matter how you do the testing, you just won’t get what you want.
Aleph is no longer state-of-the art for ILP and it hasn’t been for about 10 years now, but because ILP is a very small field and most people outside it don’t keep up with developments, I often have this conversation. For many people Aleph is the same as ILP, or when they say “ILP” they really mean “Aleph”. That was incorrect even in the '90s because there were other systems and other approaches, besides Aleph, from the beginning of ILP.
Nowadays things have advanced to the point where it’s unfair to compare a system’s performance to Aleph because everyone (in ILP) understands there are things it can’t do that more modern systems can do. For example, recursion and predicate invention are well beyond Aleph’s capabilities, so more recent approaches like Meta-Interpretive Learning and Learning From Failures (as in Popper) that can do those things automatically will always “win” in comparison. Unfortunately reviewers in the mainstream AI conferences aren’t always aware of that so they often ask for comparisons to Aleph, so authors end up comparing their systems to Aleph anyway. That’s a bit sad because Aleph just can’t perform the same tasks as the systems it’s compared to, so it just looks bad and that’s unfair. It was state-of-the-art for its time. But we have better approaches now.
Really though if you want to know what happened in ILP in the last 30 years I have two papers to recommend. One is a retrospective of the first 20 years up to 2010, and the other one adds the next 10 years to date.
ILP Turns 20 - Biography and future challenges
Inductive Logic Programming at 30
I promised an example of the way Meta-Interpretive Learning works so that we have something more concrete to talk about. The following is from my own Meta-Interpretive Learning System, Louise:
58 ?- list_mil_problem(ancestor/2).
Positive examples
-----------------
ancestor(stathis,kostas).
ancestor(stefanos,dora).
ancestor(kostas,stassa).
ancestor(alexandra,kostas).
ancestor(paraskevi,dora).
ancestor(dora,stassa).
ancestor(stathis,stassa).
ancestor(stefanos,stassa).
ancestor(alexandra,stassa).
ancestor(paraskevi,stassa).
Negative examples
-----------------
:-ancestor(kostas,stathis).
:-ancestor(dora,stefanos).
:-ancestor(stassa,kostas).
:-ancestor(kostas,alexandra).
:-ancestor(dora,paraskevi).
:-ancestor(stassa,dora).
:-ancestor(stassa,stathis).
:-ancestor(stassa,stefanos).
:-ancestor(stassa,alexandra).
:-ancestor(stassa,paraskevi).
Background knowledge (First Order)
----------------------------------
parent/2:
parent(stathis,kostas).
parent(stefanos,dora).
parent(kostas,stassa).
parent(alexandra,kostas).
parent(paraskevi,dora).
parent(dora,stassa).
Background knowledge (Second Order)
-----------------------------------
(Identity) ∃.P,Q ∀.x,y: P(x,y)← Q(x,y)
(Tailrec) ∃.P,Q ∀.x,y,z: P(x,y)← Q(x,z),P(z,y)
true.
So what we have here essentially is a higher-order definite program that comes in two parts: one part is a set of first-order definite program clauses, which is basically a Prolog program. The other part is a set of second-order definite program clauses, which we can see as a second-order Prolog program. In practice the second-order program is datalog (no fucntion symbols) but the first-order program is really an unrestricted Prolog program. That’s in practice.
Unlike Prolog we also have two sets of training examples: positive and negative. The “:-” in the negative examples is just a reminder, they’re not meant to be executed as directives!
Now, with the above loaded in memory, we can ask Louise to learn a program:
61 ?- learn(ancestor/2).
ancestor(A,B):-parent(A,B).
ancestor(A,B):-ancestor(A,C),ancestor(C,B).
true.
And as you see it learns a bog-standard ancestor/2 definition based on parent. It’s a left-recursive definition though. So what’s going on here?
The version of Louise I use is the one that is bundled as an example with Vanilla:
Vanilla is a Meta-Interpretive Learning engine. If you navigate to the src/vanilla.pl module you 'll see that the main exported predicate is the called prove; and if you squint a bit and tune out the debug statemetns, you’ll start to discern the good, old, familiar structure of a “vanilla” Prolog meta-interpreter:
prove(true,_K,_MS,_Ss,_Os,Subs,Subs):-
!
,debug(prove_steps,'Reached proof leaf.',[])
,debug(prove_metasubs,'Metasubs so-far: ~w',[Subs]).
prove((L,Ls),K,MS,Ss,Os,Subs,Acc):-
debug(prove_steps,'Splitting proof at literals ~w -- ~w',[L,Ls])
,prove(L,K,MS,Ss,Os,Subs,Subs_)
,prove(Ls,K,MS,Ss,Os,Subs_,Acc).
prove((L),K,MS,Ss,Os,Subs,Acc):-
L \= (_,_)
,L \= true
,debug(prove_steps,'Proving literal: ~w.',[L])
,clause(Os,L,K,MS,Ss,Subs,Subs_,Ls)
,debug(prove_metasubs,'New Metasubs: ~w',[Subs_])
,debug(prove_steps,'Proving body literals of clause: ~w',[L:-Ls])
,prove(Ls,K,MS,Ss,Os,Subs_,Acc).
That’s what’s doing the learning! It’s a Prolog meta-interpreter. It’s equipped with a few extra arguments, mainly for book-keeping and for depth-limiting. Taking the arguments one by one from the left:
(L,Ls) is the set of positive examples.K is an upper limit on the number of substitutions in Subs, effectively limiting the number of clauses that can be added to a learning program.MS is a list of Second-Order Definite Clauses from the Second-Order Background Knowledge (we don’t write those to the dynamic database).Ss is a set of predicate symbols, that include the predicate symbols in the positive examples and the first-order background knowledge, and may include one or more invented predicate symbols (those are predicates that are not defined either in the background knowledge or the examples).Os is a list of options.Subs is an accumulator of substitutions of second-order variables in the Second-Order Background Knowledge.In the third clause of the prove/6 meta-interpreter, where you expect to find a call to clause/2, there’s this call to a predicate clause/8 instead:
,clause(Os,L,K,MS,Ss,Subs,Subs_,Ls)
This is a variant of clause/2 that allows fetching of the bodies of clauses not only from the first-order background knowledge, but also two other sets of clauses:
a) the second-order clauses stored in MS, and,
b) the substitutions of the second-order variables in MS, stored in Subs.
When a clause, M, is fetched from MS, then L, the literal we are trying to prove, is bound to the head of M and then the body literals of M (with some of their variables now bound by unification) are placed on top of the meta-interpreter stack and the proof continues.
When a substitution S is fetched from Subs, first it is expanded to a full clause by unification with the corresponding second-order clause in MS, and then its head is unified with L and its body placed on the meta-interpreter stack for the proof to continue.
So what this meta-interpreter is doing is carrying out an SLD-Resolution proof of the positive examples with both first- and second-order definite program clauses, and also with the clauses of a program that is being learned, as it is being learned.
There are two dangerous situations here that can cause infinite recursion:
a) A second-order definite clause in MS can infinitely resolve with itself.
b) A first-order definite clause expanded from a substitution in Subs can infinitely recurse with itself or another clause expanded from Subs.
To avoid the first danger, infinite self-recursion of second-order definite clauses, the argument K is used to limit the length of Subs. That happens in clause/8 and it stops infinite self-resolution.
To avoid the second danger, Vanilla uses two methods.
The first method is tabling. prove/6 can be tabled by switching a flag on or off, like I described above. When the flag is on, prove/6 will happily prove left-recursive programs like the ancestor/2 version I list above.
The second method is to prevent clause/8 from fetching clauses from the expanded substitutions in Subs. This is done with a flag in a configuration file. At that point we can also safely turn off tabling.
What happens if we switch the flag that fetches clauses from Subs and turn tabling off? This is what happens:
63 ?- learn(ancestor/2).
ancestor(A,B):-parent(A,B).
ancestor(A,B):-parent(A,C),ancestor(C,B).
true.
So now Louise learns a recursive definition of ancestor/2 but not a left-recursive one. This is the effect of the combination of depth-limiting provided by the argument K of prove/6 and the fact that the program we’re learning can’t resolve with itself until it’s fully learned.
OK. That’s a lot to take in and you have work to do, but I hope it helps better understand how Meta-Interpretive Learning works and why I don’t think it’s possible to apply the call-graph method you suggested. I also hope it explains where the depth limits and tabling come in.
I haven’t explained the use of negative examples, and how predicate invention works, to keep things short…er. Ask me if you are curious to know, I’m happy to explain.
Oh and, I forget to say: Happy Easter to those who celebrate it. I’m Greek so our Easter is later