Declarative debugging too general programs

Hi!
I am quite familiar with the declarative debugging approach to locate the mistake when the program is too specific.

But I haven’t found any more deatailed materials about how to approach the situation, when the program is too general. Usually I came across this situation when the mistake is hidden somewhere quite a deep down in the calling tree. All the testing of the program predicates seems to work correctly, but actually it is not. There is some silly goal in some predicate which is used many times in the whole program. Something like instead of N #= N0 + 1 there is (N #= N0 + 1 ; N0 #> 10000, N #= N0 + 2). The mistake manifests itself only if the list longer than 10000 elements is processed and it gives wrong answer at another place as the strange result of some other complex computation.

Is there any good approach how to quickly locate misatakes like this with the declarative testig/debugging way?

Edit 3.6.2021:
@j4n_bur53 solved/answered my original question by directing to Shapiro’s book Algorithmic Program Debugging which describes methods for debugging several types of mistakes even mistakes in too general programs.

Thanks.

1 Like

What is the declarative testing/debugging way that you refer to?

Altogether using constraints opens up your program to a completely new class of problems.

I’m sorry, I didn’t realise that this my statement is pretty vague.

It is based on Markus Triska’s chapters for declarative debugging and declarative testing, as well as a lot of false’s stackowerflow posts about this, and some others as well.

It’s just about not using the trace right away (or at all), but trying to reason about the program more declaratively to locate the mistake. Non-termination can be handled by failure-slicing. Mistakes in too specific program could be quickly located by commenting out specific goals. But I have no idea, how to properly locate a mistake, when the predicate holds for more answers than it should and when the mistake is not clear right away.

The example is not any specific case, it’s just for the example. The mistake could be anything which causes the predicate not to causes the non-termination (so it can’t be located with failure-slicing by inserting false) and not to be too specific (so it can’t help to comment out some goals).

Those chapters are pretty slim. I almost get the feeling that the author might have hand-picked the examples to prove their point.

Failure slice, as presented by the user false on SO, is, at its core, “a concrete program-slicing technique.” (this quote is straight from the tag description on SO). Here “slicing” means simply, “figure out in which slice the error is hiding”. In yet other words, “do a binary search of your program to find your mistake”.

Just so that my message doesn’t get lost in the detail: those are valid techniques, but they require that you understand when to apply them. Same goes for using CLP(FD) instead of normal arithmetic: it requires understanding of when it is needed, and when it is just unnecessary luggage. Keep in mind you are also pulling in a whole lot of code by using CLP(FD), and, to quote Markus Triska from his “Declarative debugging” chapter:

One important reason is that tracers are programs and also contain mistakes.

Well, CLP(FD) is also a program… I guess it is of course possible that using the declarative debugging and testing techniques presented in the book, the CLP(FD) library is now completely free of mistakes.

1 Like

See:

which leads to the paper

“Localizing and explaining reasons for non-terminating logic programs with failure-slices” (PDF)

1 Like

I agree with this. Hopefully they will be extended one day. False has more posts about declarative debugging (or debugger free debugging as he calls it) on SO.

I understand your point and have already encountered situations where I switched to normal arithmetic. But as a general rule I almost always start with CLP(FD) until I came across some issue which am not able to resolve with CLP(FD). I just like the idea that the relationship between integer and his successor could be described like N #= N0 + 1 and it just holds. Instead of saying that it holds only if I know N0 in advance and if not it is an error. In real life N = N0 + 1 holds for every two successive integers and there really is no error.
And yes. Except for really really simple programs, there is almost no piece of software which doesn’t contain a single mistake.

Thanks. I had this one in my to-read list but lost it. But I don’t think this would help in too general programs.

Unfortunatelly I don’t remember the real example of the issue from the last time I came across this, so this is just an artifficialy created problem to show the point.

The naïve way to define list’s lenght could be like this, which is borrowed from Learn Prolog Now!:

len([],0).
len([_|T],N)  :-  len(T,X), N is  X+1.

It just works, terminates where it should and doesn’t terminate where it shouldn’t and give all the right answers.

Let’s pretend that there is some strange reason, why somebody makes a mistake and write another list/length predicate like this:

len2([],0).
len2([_|T],N)  :-  len(T,X),  (N  is  X+1; N is X + 2, N = 10000).

All the standard testing doesn’t reveal the mistake because it works just like len/2 except when it stumbles upon a list of length exactly 9999 elements where there are two possible answers. So this predicate is “successfully” tested and after that used in some complex program, where the mistake reveals one day on completely other part of the program with some strange answer from some other predicate.

Now there are several options what to do when there is a mistake discovered.
I can use trace and most of the time switch from declarative world to just procedural to locate this mistake.
I can use failure-slicing if I think there is some non-termination which shouldn’t be. But this is not the case with this example. It terminates where it should be and it doesn’t where it shouldn’t.
I can use declarative debugging - commenting out some of the goals. But this helps with programs which are too specific by making them more general to help locate the mistake.
But I don’t know what method to use (except of trace) to locate the mistake when the program terminates properly, gives all the right answers so it isn’t too specific, but it gives a little bit more answers than would expected, so it is just too general.

And it is not about this exact example, but about overal methodology in cases like this.

Here is a very loose collection of references related to debugging Prolog code not that it may be of value to your specific problem, it is nice to know for future needs.

Bug hunting toolbox

1 Like

There is another method. It is called “reading the code” :slight_smile:

I do it regularly, also at work, and with all the languages. Read the code, cross-check it with the specs, and with all the places where this code is used. (In some code bases I have had to work on, tracing can be absurdly difficult to set up, practically impossible.)

Does something look out of place? If you can figure out what the code is supposed to do, then reading through it should in theory catch most of the thinkos. (Figuring out what the code is supposed to do is non-trivial, sometimes also practically impossible.)

Side note: If you use a technique or a library that is not strictly necessary, this is also “out of place”. For example, if I see X1 #= X0 + 1, I would expect a good reason for it. On the other hand, as long as you are consistent with your mental model of your code, it is not a problem, it is just a style. In other words, as long as you know that using a constraint instead of arithmetic doesn’t have to mean that you are solving constraints, you are all good.

Aaah, the famous RTFM :slight_smile: In the ideal world where you would have an infinite amount of time and you have a years of experiences to just read the code and see the mistake right away, it would be the best way. I would like to live in world like this.

In the real world I’m not so experienced as I wish to be already and just trying to learn constantly as much as I can. But there are always some deadlines where it is needed to solve some problem which I am not experienced enough with and there is nobody else to do it. Sometimes I am stuck with some mistake I did in my own code about which I assumed it was mistakes free.It take a short period of time to locate the mistake in cases when there is an undesirable non-termination or the program is too specific, even in the quite comlex programs. It take me a lot longer when the program is just too general. I always feel like there should be some general method similar to failure-slicing (yes, binary searching the program) to quickly locate mistakes in just too general program, which I don’t know of yet.

I know. There is the group of “just read” solutions. Read the manual, read the code, etc. And probably the most famous abbreviation is RTFM about reading the * manuals, therefore I used it there as a sticker for all the “just read” category. I absolutely didn’t meant to insult Boris or something like that. It was just a joke. And I totally agree that reading the code, manuals or any piece of avaliable information is very important part of the process.

But although prolog seems to be very easy language at first, I think the exact opposite is true. Probably everybody is able to locate the mistake in program by just code reviewing if she/he has enough time to to just read and think about the code. But to do it in reasonably amount of time you have to be experienced enough, especially in prolog. Not enough experienced user in some procedural language would be able to locate a mistake by just code reviewing reasonable complex program a lot faster than about the same level unexperienced user of prolog. I often came across a few lines of code in prolog that solve something interesting and the code is just pure beauty. One have to be very experienced to came up with solution like that. But in case there is still some mistake one have to be reasonably experienced as well to notice this mistake.

So what is the solution for beginners and itermediate still not so experienced users? Just sit for few years and read the code and the manuals until you’ll be enough experienced and you’ll be able to reasonably quickly understand all of the code and locate the mistakes in them?
There is some beginner-friendly method for solving mistakes in non-terminating and too specific programs. But for too general programs there is non so simple method, just reading the code and mastering a lot of tools Eric mentioned and hopefully became so experienced to locate the mistake in reasonably amount of time?

Disclaimer: I try to avoid writing so many words without any code, but in this case it seems necessary.

Not sure about some of your claims. In my experience, Prolog is a high-level language, you get more done with less code. And I don’t mean Perl-style code, on the contrary, code with clear intentions, even if you are not on the wizard level quite yet. So this should in theory make reading and writing code easier, not more difficult.

The most common mistake by far that I have observed in the wild is: a beginner trying to follow religiously a specific Prolog programming style that doesn’t yet fit their experience level. Examples include trying to use constraints where they are not necessary without understanding the implications, or trying to program predicates that are true relations even if this is not necessary for their use case, or trying to maintain “logical purity” when this is not necessary. (I have made all these mistakes too!)

Some of the easily available learning materials are indeed preachy, in the sense that they purposefully construct a narrative about what “good Prolog code” should look like. My best guess is, the authors are completely forgetting that while this style might be good for them, it doesn’t help a beginner pull themselves up to that level. On the contrary, it only perpetuates the myths that Prolog is a difficult language, that Prolog is a very different language, and so on.

A trick that I have learned to despise (and this is ubiquitous in the “Learn to Program” universe, not at all specific to Prolog) is providing “beautiful” solutions to hand-picked problems. This is very hard to avoid and certainly every person who has ever tried to teach programming has done that. I know I have done it, too. It is disingenuous at best and malicious at worse. We do it because it feels easier than telling a beginner, “listen up kid, this shit is hard, just start cracking and if you have the aptitude, in 10 years you will be as good as anyone who has been doing this for 10 years”.

Now, this one thing in particular:

Prolog is a very simple language; this is not the same as easy. I am not sure even what “easy” should mean in this context. Easy to write code without syntax errors? Easy to get a simple problem solved in a hurry? Easy to solve complex problems? Easy to write correct programs? Easy to write efficient programs?

It is definitely not easy to get to the “advanced beginner” stage in Prolog.

4 Likes

yes, that sounds about right :slight_smile:

yes, that sounds about right, too. But don’t you worry, we are working on systems that will eliminate the human element, so no more room for silliness and mistakes. Wait, who is going to write the specs for those?

We only allow capitalist tools of brain wash in these parts, buddy! :smiley:

I often struggle even with the English. Simple is the right word I should have use, not easy.

Anyway thanks a lot. It seems that I have a lot to think of right now.
Are there any more materials describing why using almost blindly the “logical purity” is not always the right way?

:slight_smile: I guess I can give you quite a few ad-hoc reasons for that. Maybe someone else can jump in with good references.

  • There is no “right way” in anything complex enough.
  • If aiming for logical purity prevents you from solving your problem here and now, you are probably better off forgetting about it for the moment.
  • Getting a bit philosophical, complex behavior requires state. State implies side effects, and this destroys logical purity. You can have regions of your program that are pure, but striving for logical purity everywhere is just as pointless as striving for functional purity everywhere.
  • Enforcing a style by technical means has been tried before, and it has always backfired. You cannot be creative with a straitjacket on. (Finding a balance between freedom of expression and adhering to a common vision is the other side of this argument, of course).
3 Likes

@Boris I think you are saying wise words. Prolog is a simple language. It has several different faces though. To name a few:

  • We can use it as a constraint system. Pure Prolog is a constraint system where an instantiation of logical variables that satisfies all constraints is searched for using basically generate-and-test. This quickly get hugely inefficient and is very sensitive to ordering. CLP (Constraint Logic Programming of which clp(fd) is one member) improves on that a lot. Such programs typically do a lot of backtracking, do not use cuts and are generally pretty close to pure. Great for puzzles (also useful for real problems).
  • We can use it as a Datalog style deductive database. This is often combined with tabling to reduce ordering impact and avoid non-termination. Also this code is pretty pure. Great for data science (data cleaning, joining, filtering, etc.) and knowledge representation.
  • We can use it as term rewrite system using unification for pattern matching. Parsers, term/list manipulation, etc. falls in this category. You can try to get a long way maintaining purity and make the code multi modal and dealing with partly instantiated terms. In most concrete cases this is IMO an overkill. You often need the “purists” non-defaulty data representation, the (IMO ugly) if_/3 and a lot of thought. All this effort is not worth the trouble for code that basically implements a function, i.e., a deterministic mapping from input to output. Use the new Head => Body rules instead :slight_smile: . I’m using them more and more and I might have regained the time implementing them by the bugs it caught that avoided me to have to use any debugger.
  • We can use it as a simple dynamically typed close-to-imperative language for general purpose scripting tasks. Most of such code is pretty much sequential. Some non-determinism can be used locally. Most I/O, glue code, etc. is of this style. As most applications contain a lot of this code that deals with the outside world, the bulk of the code falls often in this class.
  • More?

I always wonder why the majority of the Prolog classes is about the 3rd bullet. This barely shows the power of Prolog. Yes, you sometimes need to manipulate some data structure. Most of the useful stuff in this class is in libraries. Problems like the zebra puzzle and send+more=money are nice assignments that barely need any knowledge about data structures. The family trees and searching underground networks are good examples of the second class. Why would we like to pick every second element from a list though? Or translate a list into a run-length encoded form? Yes, you can do that in Prolog. The result varies between fairly elegant to pretty inelegant when compared to imperative or functional languages depending on the expertise and the problem. Try implementing “minimal edit distance” in Prolog :frowning:

5 Likes