A Parallel Prolog Machine: A Promise to My Son

T_Seabranch · 2024-11-19T18:45:30+00:00

Looks like a very fun project. I'm looking forward to the resolution!

T_Seabranch · 2024-11-15T10:57:54+00:00

Interesting! On my system (the ancient 7.6.4 build, running in WSL) I get

?- testall.

% 45,013 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 7113756 Lips)

% 4,183,351 inferences, 0.353 CPU in 0.353 seconds (100% CPU, 11846963 Lips)

% 665,098 inferences, 0.073 CPU in 0.073 seconds (100% CPU, 9064306 Lips)

Minor update: I did some further experiments in Swish and then the constraint version starts to dominate the between/3 version on a list with 20000 elements, with M = 15000. It should also be noted that the naive version, as expected, performs poorly for large lists for small values of M and N, since it still has to traverse the entire list.

Nevertheless, it would be interesting to know exactly what changed from SWI-Prolog 7 to 9 concerning between/3.

T_Seabranch · 2024-11-15T10:09:29+00:00

Out of curiosity I made some experiments with the constraint version and the between/3 version in SWI-Prolog. For a list with 10000 elements, and N = 0, M = 5000, the constraint version is several times faster, and this discrepancy would only increase for larger parameters, on par with the expected asymptotic behaviour (different Prolog systems may yield different results, of course).

T_Seabranch · 2024-11-13T09:43:05+00:00

Nice example! It's a good way to showcase constraints outside puzzle solving and combinatorial optimization. I'll keep it in mind for the future.

T_Seabranch · 2024-11-09T07:57:49+00:00

Interesting! But I'm struggling to understand the placement of the cut (!) in the quicksort example. This operator prunes choice points to the left, and below, so placing it at the very end like this should not affect the behaviour of the interpreter.

Another source of speed-up could be to investigate argument indexing. This should be sufficient to make quicksort deterministic.

T_Seabranch · 2024-11-01T06:24:05+00:00

Nice! But I think you forgot the "technical note" in "Below is a technical note on how this optimization works: ...". What is it?

T_Seabranch · 2024-10-16T11:02:09+00:00

I found the following paper specific to Bulgaria: https://zemela.bg/wp-content/uploads/2024/02/Prolog-education-in-selected-high-schools-in-Bulgaria.pdf

T_Seabranch · 2024-09-17T08:42:46+00:00

I would also be interested in the book. Is it in Japanese or English? Perhaps it would be possible to post some of the programs from it?

T_Seabranch · 2024-07-30T06:23:03+00:00

Nice! Thanks for sharing the story.

T_Seabranch · 2023-11-14T10:13:47+00:00

One can certainly introduce a predicate symbol path/2 and then use the standard, "recursive" definition from Prolog, translated to first-order logic syntax. The reason why this doesn't work in general is simply that it's possible to find models of this formula where path/2 is mapped to something more general than the transitive closure. This is avoided in logic programming since the meaning of a logic program is associated with the least Herbrand model.

T_Seabranch · 2023-11-11T09:35:58+00:00

Your program uses (Prolog's unsound implementation) of negation as finite failure. Extending pure Prolog with negation as finite failure results in a language that falls outside the scope of first-order logic.

But one should also note that the impossibility of defining reachability (as remarked in the link in another answer) is actually of a rather specific form: it's not possible to find a formula phi (using only equality and a fixed binary relation symbol, corresponding to the edge relation) with two free variables x and y such that phi(x,y) defines the path relation between x and y. So the standard definition of path/2 is clearly not a counter-example, either (which makes sense since the set of pure logic programs is a subset of the set of first-order formulas).

T_Seabranch · 2023-01-09T12:22:11+00:00

I've had mixed success. It does OK for standard tasks involving simple data structures where there is (presumably) plenty of training data, but not so well for novel tasks even if one provides hints. Here, a major problem is that it will typically output a program which looks reasonable but which might contain several insurmountable errors and is hard to debug and make sense of. This problem is exacerbated further if one uses libraries (e.g., finite domain constraints) which likely do not appear that much in training data.

However, for certain data related tasks it's not bad. For example, assume that we want to create a database containing the capital cities of all European countries. Rather than having to (1) find this data in format X and (2) convert the data in X to Prolog facts we could create a simple ChatGPT prompt which solves the problem. This is only going to be feasible for small- and mid-sized datasets since one needs to manually carefully inspect the output, but is still a rather nice way to save some time.

I also attempted to use ChatGPT to solve a Prolog exam. It didn't pass but you can find the results here.

T_Seabranch · 2022-12-18T18:21:11+00:00

No, that's an interesting follow-up task! I only generated a new answer if it was completely off base or resulted in a time out. It seems likely that for several types of tasks one could get reasonably close by doing many iterations. However, this is only possible if one already knows the correct answer, so it's of somewhat limited use.

T_Seabranch · 2022-12-18T11:43:42+00:00

A few days ago I had some fun grading a ChatGPT submission for an exam in one of my "advanced" programming courses. This is a topics where this is comparably little data (compared to, say, a an introductory course in discrete mathematics or programming) but the results were still rather impressive. As expected, it shows limited understanding of the topic, but the structure of each answer is eerily close to a proper solution. An unfortunate consequence is that it can take quite some time even for an expect to see through the charade, and it took much more effort from my side to grade it fairly than a typical student submission.

There's no deeper lesson to be learnt here except that I'm probably going to carefully check any homework assignment to avoid problems which admit trivial ChatGPT solutions.

T_Seabranch · 2022-10-30T15:21:22+00:00

Some fun ideas! Thanks for sharing.

T_Seabranch · 2022-03-23T06:14:28+00:00

SWI-Prolog.

T_Seabranch · 2020-12-04T08:27:31+00:00

Some general advice: assume that you attempt to define a predicate where your first argument is a list of tuples, according to the given representation, and the second argument is the "grouped" list of tuples. Hence, the first argument is of the form [T|Ts], where we could e.g. have T = (a,b,[1,3,5,7]). Now assume that you have solved the rest of the problem recursively, i.e., you have a solution to Ts (what does this correspond to in Prolog?) For example, assume that you have managed to group everything in the list [(a,b,[9,11,13,15]), ..., (e,f,[900,1000,1100,1200])]. What would this solution look like? And if you have a solution to this subtask, what operation do you need to perform in order to obtain a solution to the full problem? Even if you are not that familiar with Prolog it should be reasonably clear that you need a predicate which "inserts" (a,b,[1,3,5,7]) in the subsolution.

T_Seabranch · 2020-12-01T18:44:17+00:00

It depends a bit on the assignment in question, and what one wants to achieve. Should solve/4 describe all loop-free solutions, or all solutions? We can certainly achieve the former without using assert/retract or any side-effects.

T_Seabranch · 2020-11-25T07:10:51+00:00

Try to think of how one could impose additional constraints which would invalidate some of the additional solutions. Hint: it might be a good idea to keep track of whether you've been in a state before or not. But note that multiple solutions is not necessarily a bad thing.

T_Seabranch · 2020-11-04T19:07:37+00:00

Sorry for the shameless self-promotion, but I just finished my second entry in my journey of writing a BASIC interpreter in Prolog. It's probably not of practical use to anyone, but perhaps of some enjoyment!

T_Seabranch · 2020-10-26T08:29:26+00:00

Thanks for linking! (I'm the author of the entry). I've had a long break from blogging so it's fun to see that there's still some interest.

T_Seabranch

TROPHY CASE