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.

(post deleted by author)

1 Like

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?

The code reviewers are supposed to be kind of advanced or expert level, but they can be also same level, like in pair programming variations. What also helps code reviewing if the coder uses some coding guidelines, so that the code reviewer has it more easily formally.

Here is an example of coding guidelines for Prolog:

Coding Guidelines for Prolog
https://arxiv.org/abs/0911.2899

This would make it also easier to post questions with code on stackoverflow and other Q&A sites, where the code reviewers are basically those trying to answer your question.

Edit 02.06.2021:
But choose your community wisely. Currently stackoverflow has a CLP(FD) and library(reif) are always better bias, because of the spamming by @false, @repeat, etc… Unfortunately code review can become communist tool of brain wash.

2 Likes

Declarative debugging can be hard for a computer. Replacing the human that sees a bug by a computer that automatically assures the lack of bugs, requires a lot. What proof assistants offer, when writing verified code, you combine step by step new routines from already verified routines.

Didn’t Boyer & Moore pioneer such a system?
https://en.wikipedia.org/wiki/Nqthm

But the whole venture is a little circular, since you need a specification for correctness etc… So if the specification is buggy, its garbage in garbage out. So you would possibly kind of specify certain aspects of the code that would be verified?

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:

Taking the example by mjano314. This would be the implementation:

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

And this would be the specification:

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

A theorem prover can possibly figure out that len2 does not implement len. In practice there are possibly more stricking examples, where there is a simple spec and a more complex implementation for some reason.

Take a spec of sort and an implementation of sort. A spec of sort could be, currently assuming that the elements of A are all distinct:

sort(A,B) :-
    permutation(A,B),
    sorted(B).

Edit 02.05.2021:
Failure slicing possibly doesn’t help so much in recursive calls, unless you can conditionally slice depending on number of iterations? If I inhibit the second clause of len and len2, they become the same:

len2([],0).

len([],0).

And now? LoL

Declarative debugging can mean the following. You don’t need a spec. Only test cases where the expected outcome doesn’t match the effective outcome of your current program. The computer is then supposed to help you tell why this is so.

There is a section about declarative debugging in John W. Lloyds foundation of logic programming book. In the 80’s it was figured out, that this declarative debugging is similarly complex like the view update problem of SQL respectively Datalog.

Edit 02.06.2021:
From John W. Lloyds book, page 121, via google book search:

content

1 Like

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?