Tracing prolog code

Question

So I am trying to trace this "sublist" code and I really need help...

This function basically check to see if second list is sublist of the first list where order DOES matter;

(1) isSublist([],[]).
(2) isSublist([H1|T1], [H1|T2]) :- isSublist(T1,T2),!.
(3) isSublist([_|T1], T2) :- isSublist(T1,T2).

What I am getting confused is that how is H1 being recognized? For example, if input was sublist [1,4,7,9],[4,7], and having same H1, does it overlap? or will it have [1|4,7,9],[4|7] ? Even though H1 does not get used in the conditions, taking them out or assigning H1 and H2 does effect the result...

Also second question is, after checking second condition (2), does it go down to the next condition with updated list? or does it go up go base case (1)" ?

Even if it goes to the base case (1) or (3), all I see it does is getting rid of the head until both of the list is empty... Can you explain how this code is working? Maybe hint of how to trace it even?

Answer 1

In Prolog I see tracing is as a method of last resort. Whenever I'm tempted to start up the tracer, I think of the endless hours I have spent tracing codes to no avail.

In retrospect I could have spent that time way better doing the following activities:

• Get away from the problem and then approach again.
• Think about the problem at hand.
• Formulate test cases. (big and small, general and specific)
• Use natural language to tilt my view to a different angle.
• Refactor existing code.
• Start with a clean sheet and recode the code I want to debug.

Note to self: read this post when feeling the urge to start the tracer:)

Answer 2

I'm not sure you have realy understood how prolog works. Perhaps you need to read a guide or something.

In you're case, Each time you call isSublist, prolog will choose the first definition maching the given parameters. It will choose between (2) and (3) until it reach the (1) statement that returns true. If prolog can't find a path to the (1) statement, it will return false.

You can also notice the '!' telling to prolog to stop backtracking form this point.

I hope this will help you but like I said, I think you need to read more about prolog and his special paradigm. It's not easy to understand by only reading code. If you want, I have found this book really good for a starting point, it's well explained : Learn Prolog Now!

---

Like said in comments, you can use ?- trace. to enter in trace mode. See the prolog documentation for more information about it.

Answer 3

You're on the right lines.

My suggestions:

1. reverse the order of your arguments to isSubList, i.e. isSublist(X,Y) means X is a subList of Y. That would be more legible to most Prolog readers (but hey, there's only a handful of us...). This makes most sense if you use the 'op' operator and define isSublist as an infix operator, so you could write "X isSublist Y" and that would be equally valid Prolog.
2. try and avoid the cut (!) - it's an extra-logical predicate and leads you down the rabbit hole of thinking all the time about the order Prolog will interpret your clauses. For such a simple relation you should be able to keep your code 'declarative'.
3. You really have TWO different matching situations - firstly matching a sublist anywhere in another list, and secondly exactly matching a list from the first element (i.e. this happens after you get the first match). I.e. you have a subList(X,Y) (I dropped the 'is') and frontList(X,Y) where frontList(X,Y) only succeeds if list X is the first part of list Y.

So you end up with the following code:

subList([H|T1],[H|T2]) :- frontList(T1,T2).
subList([H1|T1],[H2|T2]) :- H1 \= H2, subList([H1|T1],T2).

frontList([],_).
frontList([X|T1],[X|T2]) :- frontList(T1,T2).

For extra marks, you can see that frontList(X,Y) is actually the same as

append(X,_,Y)

Think about it... append a list to X and you get Y means that the elements of X must be the first elements of Y...