Re. Kowalski. Prolog is a very leaky abstraction of logic. Understanding ‘under the hood’ seems like a necessity.
Every new language involves kicking the wheels to find out why it works the way it does.
It would be helpful to find a Wiki/cookbook - an Effective Prolog in the same vein as effective C++
that shows best practices, and more importantly, why. I gained a much quicker mastery of C++, for example, once I understood that the compiler needs to see sufficient type information to be able to know about much memory to reserve on the stack for a variable - a surprisingly large number of language quirks just fall out from this this fact, which you could argue is an ‘implementation detail’, but is one that leaves you constantly fighting the language until you know it.
Most of tutorials and books seem to good on the ‘this is how you do…’ part, but thin on the why part. Which is the only way to truly learn.
I have so many questions:
Best practices for clean code (naming of implementation vs internal details). In the process of
system bring-up - readability matter to my because I want (need!) other to help in the full
implementation, otherwise I’ll be working evenings and weekends.
Why is the second unit test failing? How to write unit-tests|how to hard-undo? Global state is how a Prolog do, so to avoid global state? The first thing I want to do with any new system is write unit tests to capture what I think is true (and be a reference for my staff). Prolog is a messy eater - every test can make assertions - breadcumbs that interfere with subsequent tests. (Hence my long question on modules that Jan and Paulo answered).
Why are outputs generally the last parameter (when they exist)? Convention, or some stack-friendly consequences?
Why order of declarations matters. (Which is not true for logic). I know the answer, but it is in fact an essential under-the-hood implementation detail, without which I sure I’ll be forever fighting the language.
Can an expression have a value other than true or false. (Seems no. Why not? Are there counter examples? Can expressions be terms that evaluated later…) Prolog seems to want expressions to be always true or false. (X==Y+1) is an expression that is true false. But what is (Y+1)? It is also an expression \+(Y, 1) that is true or false. The variable value we see in program output is the thing that makes the expression true. This didn’t really click for me until I implemented a non-deterministic predicate in datalog, in which you must provide different implementations depends on whether the parameters are grounded or not AND always provide success or fail as the result. Its also the why of why named constants are not trivial.
What’s the complexity cost of matching predicates. (are all, any? arguments indexed, or just the first)?
Yes, it is called “The Craft of Prolog”. It is old but the language was getting old when it was written
EDIT: very recently Jan shared a reference to the paper that inspired him to implement SWI-Prolog the way that he did. I thought I bookmarked it but I didn’t. I planned to read it but I cannot find it easily. Can someone point me to the link again?
Several people recommended term_expansion. Thank you it is a useful tool.
I’m a little confused about how it works (more like, when it works).
My understand is that file directives are things that are executed while the file loaded (or when it is compiled?). An the rests of a .pl file is composed exclusively of database asserts.
term_expansion seems to behave like a directive though, right? Isn’t it executed at load (with the evidence of many things added to the database, and many exports registered to the module), and it doesn’t simply assert as single assert(A:-B) into the database as its syntax would suggest. What magic is happening here? If I defined:
My understanding is that doing term_expansion(A, B) :- ... is defining another clause for the multifile term_expansion predicate. The compiler then, when reading in terms, calls term_expansion on the read-in term and if it succeeds, acts as if it had read in the “return” value instead.
Sure, but just from my limited (chapter 1) experience:
f(X):- …, assert(X).
cuts (although I think its possible to rewrite this in pure logical terms).
side effects (e.g. the export-on-load) example in this thread.
rule ordering matters, and can mean the difference between termination and not-termination.
ordering of terms withing a body matters and can mean the difference between O(n) and O(2^n).
Input-only and output-only variables.
… pure logic is blind to these issues. An effective Prolog practitioner I’m certain is not.
Every language has its quirks. Understanding the ‘whys’ its the best way to discover what will work naturally within that language and what will not.
[Edit – deleted the append example – which seems fully implemented for all combinations of input and output]
What are Input/Output only variables. Do you mean Input/Output only arguments?
Assert. Ok, assert is a bit funny.
Now everything else, cuts, rule order, term order within body. It’s, as you probably already know, all about control and we need it for programming. We control because we have a search problem and our option set gets big fast. This isn’t actually specific to logic programming. Here are three quotes from Forbus and DeKleer in Building Problem Solvers:
Intelligence is possible because Nature is kind. However, the ubiquity of exponential problems makes it seem that Nature is not overly generous.
In N-queens, the exponential is inherent in the problem: there are simply an exponential number of solutions. In other problems, even when there is a single solution it can take exponential work to find it. No code optimization, no faster clock rate, no increment of parallel processing will overcome the computational demands of an exponential procedure in the long run. The best you can do is figure out how to formulate your problem so that you either eliminate the exponential (perhaps by settling for approximate solutions) or keep its growth as small as possible.
Representing “how” knowledge is often just as important as representing “what” knowledge.
Control enables us “keep its growth as small as possible”. The othr option - reformulation of problem - is a non-starter. Now Kowalski gave us:
Algorithm = Logic + Control
How these interplay was described well by Vijay A. Saraswat in Concurrent Constraint Programming:
the logic sanctions; the control prohibits.
In practice, how do we do this in programming languages? Here is Steve Gregory in Parallel Logic Programming in PARLOG:
Declarative programming language = declarative formalism + control strategy
Control strategy = evaluator + control language
The Prolog evaluator is SLD resolution, the control language is the search rule (clause order), the computation rule (goal order what you call term order), and the cut. That’s not the only way though. Our options in Prolog like languages from Patrice Boizumault’s The Implementation of Prolog:
classifying control according to four principle levels
Pragmatic control takes advantage of the depth-first left-to-right traversal strategy.
Explicit control incorporated in the program consists of modifying the standard control strategy by means of built-in predicates or variables annotation.
Explicit control separated from the program… Here we see emerging two levels of knowledge: the program itself (facts and rules) and the way to execute it (metarule).
Automatic control is also characterized by introducing strategies aimed at improving the efficiency of the control
This can lead to problems. Steve Gregory again:
It is likely that any practical logic programming language must sacrifice completeness in the interests of efficiency.
Basically, we need control. Othr languages do it to. You see it functional programming languages albeit the control tends to be implicit.
Sure. Cuts are one solution. Tabling another. There are others. The point is – if you come at from the point of view of ‘learn logic first’ and ‘do Prolog in a pure logical manner’, cuts are something of a dingleberry as they expose something that is necessary to understand about search implementation, and extra to the declarative logical model. So the model is leaky (as is true for almost every language, API, etc…).
I’m not against cuts - I understand the need. I’m against the idea that only declarative logic is sufficient to work with Prolog - its important to peek under the skirt to see ‘why cuts’ (or whatever). Its why books like Effective C++ are so popular.
Re: What are Input/Output only variables. Do you mean Input/Output only arguments?
Yes. Coming from a (brief introduction to…) datalog, it was my impression was that output-only variables are a notion that’s outside of a relational model. (In the relational model if you ask f(a,B) and it is true, you can always ask f(A,b) and find it true, right?). And so its sensible to want to know why some variables are ‘output-only’ Prolog and how it differs from the relational model to understand the constraints of the landscape.
You are correct. I mixed up things. I really should have referenced a good Prolog book like Bratko for learning Prolog. Declarative logic (and Kowalski’s book) alone is not sufficient. I cannot disagree with you. I do believe that sort of knowledge to be necessary though.
I mentioned Kowalski’s book because I thought your questions wouldn’t be asked by someone who had done a lot of translating into logic. Bringing Prolog into the mix was down to my muddy thinking. Sorry.