I am still unable to wrap my head around Prolog, am a bit disheartened about it, and disappointed with myself, but I’m not going to give up.
Along those lines, is there any material which would teach me how to implement normally occurring data structures and algorithms, as in say the book The Algorithm Design Manual, but using Prolog to the best of it’s facilities?
Knowing how to work with simple algorithms as in the book above would probably prepare me to work with advanced algorithms as in the book Algorithms for Decision Making, which is of interest to me.
“Algorithms” is a very large topic; you cannot freely mix-and-match algorithms and programming languages. In the single most exhaustive textbook on the topic (that I know of), “The Art of Computer Programming” by Knuth, the author felt obliged to invent an assembler language for a hypothetical computer architecture. He did it partly because of the rigorous formal analysis of the algorithms presented there; it would have been impossible to do that otherwise. I suggest you find the time to at least read in his own words the justification for doing it like this. (And as he is trying to finish his book he decided to throw away the initial assembler language and architecture and use a new one…)
If we further simplify and assume that C is “portable assembler” and C++ is “C with classes” it is still okay to try and use one of these languages for general algorithms. Java is already not a language well suited for teaching and understanding algorithms. Using Python for that is a folly; some subset of modern Python might be a good formalism for replacing pseudo-code from days of old though.
This was a very long way to say that learning algorithms on a fundamental level is not something you do with Prolog, if your goal is to learn Prolog as a programming language; or, if your goal is to learn algorithm design. Things that are considered a given in most texts (constant-time access within an array, modifying a value “in place” etc) are all possible but clumsy. There are some obvious parallels between Prolog lists and singly linked lists, and Prolog terms and arrays, and Prolog logical variables and pointers, but you can’t push the analogy too far.
Scrolling very superficially through the second book you mention, “Algorithms for Decision Making”, some of it might benefit from being implemented in a high-level, general purpose programming language like Prolog. Some of it will be both painful and inefficient.
I don’t really know what advice to give you. Using and understanding a high-level languages really benefits from the lower-level understanding that you get from doing different things. On the other hand, there are quite a few examples in the existing SWI-Prolog codebase of algorithms and data structures. The topic is too large and you should probably have a narrower goal if you want to make visible progress.
First up, Prolog is often used as a declarative language with immutable data. In this mode, you will want to learn about functional data structures and algorithms. It requires different techniques than an imperative language would use.
Prolog also doesn’t have native loop constructs, so you will want to learn and master recursion in programming. Then you might also want to learn about higher-order functions and using those to construct algorithms.
All that said, if your aim is to understand program construction in Prolog, I recommend “The Craft of Prolog” by Richard O’Keefe.
I agree with the recommendation, but it assumes a certain amount of Prolog knowledge.
BTW, here’s Richard O’Keefe’s implementation of Fast Fourier Transforms in Prolog (and many other programming languages), if you want to compare:
Which shows that Prolog can be reasonably efficient for some algorithms that normally use mutable matrices.
On the other hand, you won’t find many examples of search algorithms with conventional code, whereas such things are pretty easy to write in Prolog. Here’s one, which gives Haskell and Prolog code (the Prolog code isn’t very good, though): Escape from Zurg: An Exercise in Logic Programming