Prolog Puzzle

[Cetra]

I have two questions. First, is Prolog widely used in the field of computer programming?

The second question is programming related. I'm a student working to become a programmer. My professor gave the class a Prolog assignment that baffles me. The assignment asks me to write a remove goal with 3 parameters. The first two parameters are lists, and the third is where to output the results. This goal is suppose to delete all occurrences of items in list two from list one.

Sample input and output would be:
remove([1,2,3,1], [1, 3], X).

Should produce:
X = [2]

I have been working on this for a few days and the progress I have made is the following:
% special condition for when list 2 is empty
remove(L,[],L).
% if the first item is the same on both lists delete it
remove([H|T],[H|S],Z) :- remove(T,S,Z).
% if the first item isn't the same put the first item from list one into Z
remove([R|T],[Q|S],[R|Z]) :- remove(T,[Q|S],Z).


In the case of the example input and output above this gives me the output of:
X = [2, 3, 1]

I understand that my program doesn't work because my third line moves the first item from the first list into Z if it isn't the same as the first item in the second list, and because of that it never gets evaluated. I just can't figure out a way to create a remove that would look at each element in the first list, compare it to all the elements in the second list, and then insert it into the third list if it wasn't contained in the second list.

 

[LuminaryJanitor]

First, is Prolog widely used in the field of computer programming?

It's popular in AI, and quite a few of researchers use it (or languages like it) for things like constraint satisfaction and other combinatorial problems. But your typical programmer will probably never encounter it - the vast majority of the software out there is written in procedural languages. That's not to say it's not worthwhile learning it. It's very well suited to some tasks, and it's always good to have another tool at your disposal, as long as you can recognise when it's the best one for a job.

Regarding your programming assignment, I suspect you're still stuck in a procedural way of thinking about it, and declarative programming is an uphill battle if you approach it this way. You're not writing a list of actions which will delete list B from list A - you're writing a list of facts about A, B and C which are true only when C is your result.

The best way I've found to tackle a logic program is to turn it into words as you read it. Translate every predicate into a statement - for example, read "remove(A,B,C)" as "removing list B from A gives C". Rules like "A :- B,C." become "A if B and C" (or "if B and C then A", whichever makes more sense). Rules without tails become simple statements of fact. Then it's just a matter of making sure that all these statements make sense, and that they say something about every possible case. If they don't, come up with a new statement - in words - and translate it back to Prolog code.

"remove(L,[],L)." = "removing the empty list from L gives L." - looking fine so far.

"remove([H|T],[H|S],Z) :- remove(T,S,Z)." doesn't make sense - you're saying, for example, that
"removing [1,2,3] from [1,1,1] gives Z if removing [2,3] from [1,1] gives Z.", which is clearly not what you want.

You probably want to say something like
"removing list [X|Xs] from Y gives Z if removing element X from Y gives A and removing list Xs from A gives Z."

Note that "removing element X from Y gives A" is not what remove(Y,X,A) is saying - this predicate only holds for a list X. You'll need to add another predicate (remove_element or something like that) to formalise this statement.

 

[Cetra]

After reading what you said, and looking at the member goal I was able to come to a more positive result.

My input now looks like: remove([1,2,3,1], [1,3], X).
My output has become: X = [2,3]

I consider this to be somewhat of an improvement. Going line by line my code is this:

% removing nothing from L outputs L.
remove(L, [], L).

% if H is a member of list A, and we can delete H from A and put the result into C, then
% call remove with our modified list C in A's position, with T as the rest of the items
% to get rid of, with no real care for what is in the last position of remove.
remove(A, [H|T], C) :- (member(H, A), delete(H, A, C), remove(C, T, _));

% or if H happens to not be a member, remove the head of the items to get rid of, and send
% the tail to remove()
remove(A, T, C).

If this doesn't sound right please feel free to correct me. We have been learning logical language for two weeks and I dare say I'm not very good at it. I kind of wish it was C, C++, or Java.

 

[LuminaryJanitor]

Getting there.

First up, I'd recommend writing member/2 and delete/3 yourself, rather than using the built-in versions. Writing a lot of these simpler predicates is a good way to pick up on the general ideas in logical programming (and aside from that, you're probably not going to get any marks for library functions...).

remove(A, [H|T], C) :- member(H, A), delete(H, A, C), remove(C, T, _)

says that deleting H from A gives the overall result C, which is not the case.
In your example, H=1, A=[1,2,3,1], deleting H from A gives C=[2,3], and [2,3] is returned as your result. You're correct in removing T from [2,3], but you don't want to discard the result - you want to return it.

A note about the "or" operator (";"): Remember that Prolog doesn't just find the first solution, it finds ALL solutions. Even if the first case is true (i.e. member(H, A) succeeds), it will eventually try the second case as well - and the result will be garbage, as the second case assumes that member(H,A) failed. ";" is not an if-else construct or a short-circuit operator - if you want the cases to be mutually exclusive, you need to do it explicitly, by specifying "\+member(H,A)" in your second case.

That said, have a think about what would happen if you removed the membership test and the second case entirely... What will the result be after you try to delete something that's not there?

We have been learning logical language for two weeks and I dare say I'm not very good at it. I kind of wish it was C, C++, or Java.

No one is at first. I sure wasn't. Keep at it, and eventually it'll all fall into place. Previous programming experience is probably doing you more harm than good - the sooner you learn to ignore everything you know about C, the better.

 

[nameless_centurian]

...and I thought LISP was cryptic at first.

Kudos to LuminaryJanitor for not only knowing the language and helping with that but also offering great educational help. This is the model of what homework help should be.

 

[LuminaryJanitor]

Thanks

It's not that hard to get the gist if you know a little about formal logic, and how the syntax translates (":-" is a backwards implication (&#8656, "," is AND, ";" is OR).

Though it can be quite a headfuck once you get into it...
For example, you write a simple boolean function concat(A,B,C), which just tests whether C is the concatenation of A and B. So

concat([1,2],[3,4],[1,2,3,4])
returns "Yes".

But now you can leave the concatenated list undefined, and Prolog will figure it out for you:

concat([1,2],[3,4],X)
returns "X=[1,2,3,4]".

Or you can specify the result, and it will find all possible inputs which give that result:

concat(X,Y,[1,2])
returns
X=[],Y=[1,2];
X=[1],Y=[2];
X=[1,2],Y=[]

In fact, you can specify (or even partly specify) any combination of parameters, and you'll get a sensible answer:

concat([A,B],X,Y)
returns "Y=[A,B|X]"
- the tail of the result list stays undefined, as do A and B.

Now, if later on we were to say "A=1,B=2,X=[3]", Y will automatically get the value [1,2,3].
Even cooler than that, if we say "Y=[1,2,3]", it will automatically bind A to 1, B to 2, and X to [3].

(Sorry for getting a bit carried away with the Prolog lesson... Serves you right for showing interest )

 

[Cetra]

Well I have found a "solution". I say that loosely because it doesn't do exactly what I would like. Take a look:

% don't even check to see if the members are in the list, just call delete ether way.
remove(L, [], L).
remove(A,[H|T], C) :- delete(H, A, B), remove(B, T, C).

The only problem here is the variable B. My input and output look like this:
Input: remove([1, 2, 3, 1], [1, 3], X).
Output: X = [2]

This looks great but when I press the semicolon Prolog then spits out:
X = [2, 3];
X = [2, 1];
X = [2, 3, 1];
...
false.

As much as I would love to play with this more, I just don't feel this one program is worth the time. I thank LuminaryJanitor for your help, and I look forward to finding out the solution on Wednesday in class.

 

[ameoba]

I haven't been following too closely (my prolog's rusty as hell) but I get this sneaking suspicion that you need to drop some cuts in there.

 

[Cetra]

I'm not sure I follow what you mean by "drop some cuts", could you explain?

 

[LuminaryJanitor]

remove(L, [], L).
remove(A,[H|T], C) :- delete(H, A, B), remove(B, T, C).

Perfect.

I'm not sure I follow what you mean by "drop some cuts", could you explain?

A cut ("!") is an operator which stops Prolog from backtracking to find more solutions. They're kind of a hack for controlling execution flow - they leave you with a program which has no meaning as a logic expression, but gives you the right answer anyway... You should avoid them unless absolutely necessary, and in this case, they're not.

I suspect the problem is with the delete/3 predicate - it looks like it's the thing returning multiple solutions. Try delete(1,[1,2,1],X); I'm guessing you'll get X=[2],X=[2,1],X=[1,2]. If this is the case, try to write your own which always deletes all occurrences of the first argument. I suspect that this was supposed to be half the assignment anyway...

 

[Cetra]

The delete I have been using is one I found on the Internet.

delete(_,[],[]).
delete(Term, [Term|Tail], Result) :-
delete(Term, Tail, Result).
delete(Term, [Head|Tail], [Head|TailResult]) :-
delete(Term, Tail, TailResult).

You are right that this delete call does give me X = [2], X = [2,1], X = [1,2]. Perhaps I should use the built in delete function?

Wow, by using the built in delete function it looks great.
My input: remove([1, 2, 3, 4, 1], [1, 2], X).
My output: X = [3, 4]

Only thing that happens when I press the semicolon is the message false, but this is much better then a long string of other statements about X.

 

[LuminaryJanitor]

The problem with the delete implementation you posted is the same problem I mentioned with your "or" cases earlier - if you want two rules to be mutually exclusive, you need to state it explicitly.
In this case, you want the last delete rule to apply only if Head is not the term you want to delete, but there's nothing in there to enforce this. You're getting multiple results because both the second and third rules are valid when Head=Term, and so both are used, each giving a different result.

Only thing that happens when I press the semicolon is the message false

That's normal. When you hit the semicolon, it tells Prolog to search for more solutions; if it returns "False", it means that no other solutions exist, which is exactly what you want.

 

[Cetra]

Well then I have to tip my hat to you LuminaryJanitor, as well as ameoba, for all the help you have given me. I'm glad that there are friendly, knowledgeable professionals on this forum.