Programming Puzzle #2

[martinus]

x(a).
x(b).
x(c).
y([]).
y([H|T]):-y(T),x(H).

Q1: what is it?

Q2: what happens after entering

?- y(X).

Q3: what happens if you switch the last two terms around, ie.

x(a).
x(b).
x(c).
y([]).
y([H|T]):-x(H),y(T).

[hast]

looks like prolog

[Geo]

Originally posted by martinus

x(a).
x(b).
x(c).
y([]).
y([H|T]):-y(T),x(H).

Q1: what is it?

Q2: what happens after entering

?- y(X).

1) Its prolog. It checks the elements in a list for conformity to the x rules.
2) It will evaluate every element in the "list" X for x(a), x(b) and x(c), making sure each element is either a, b or c. If one of the elements is not it return "False". It will check them in reverse order and there will be the length of X many calls to Y.

Originally posted by martinus
Q3: what happens if you switch the last two terms around, ie.

x(a).
x(b).
x(c).
y([]).
y([H|T]):-x(H),y(T).

[/B]

3) It will check the first element in X, ensure that it is a, b or c before checking the rest of X.


NB: Its been a while since Ive done prolog so Im not sure if the terminology is right, or even the answer.

[martinus]

Hey, you are all right, it is Prolog. Geo, you are sort of re-describing the code in English. Perhaps I should have asked more precisely: what is the output - in simple terms? Whilst logically equivalent, there is a definite difference between the two versions...

[Geo]

heh, I cant even remember what prolog has as output.

Isn't the main difference that the first one checks the list in reverse order and the second one checks it in 'forwards' order?

[Nasher]

Prolog is confusing, though not nearly as confusing as other similar languages.

J, anyone?

[martinus]

OK then. I will describe the output only. That way there should be an incentive left for those who are willing to learn more about the semantics of prolog and the backtracking mechanism.

In fact, prolog is usually explained using two different semantics. In the logical semantic, the comma operator represent the logical "and", which makes both programs above equivalent. In everyday's language, the programs say:

"The letters (atoms) a, b and c have the property x"
"The empty list has the property y"
"A list has property y, if the first element (the head) has property x, and the remaining list (the tail) has propert y.

the query says: "does the variable X have property y?"

prolog will now go and find "solutions" for X that satisfy the query.

Obviously in a logical sense all lists (all finite strings) containing a,b and c fulfill the query.

Indeed the first program produces:

X = [] ;

X = [a] ;

X = [b] ;

X = [c] ;

X = [a, a] ;

X = [b, a] ;

X = [c, a] ;

X = [a, b] ;

X = [b, b] ;

X = [c, b] ;

X = [a, c] ;

X = [b, c] ;

X = [c, c] ;

X = [a, a, a] ;

X = [b, a, a]

Here the output of the second program:

X = [] ;

X = [a] ;

X = [a, a] ;

X = [a, a, a] ;

X = [a, a, a, a] ;

X = [a, a, a, a, a] ;

X = [a, a, a, a, a, a] ;

X = [a, a, a, a, a, a, a] ;

X = [a, a, a, a, a, a, a, a] ;

X = [a, a, a, a, a, a, a, a, a] ;

Btw, if you want to try it yourself, a free and highly reputed prolog interpreter/compiler is available at http://www.swi-prolog.org .

Right, no winner for the first price this time... I'll keep the slab.

[DRILL SGT]

What is the user of ProLog, is it an Array driven language or something. I being a 16 yo I have never head of it.

[martinus]

prolog stands for programming in logic. essentially you describe the problem and the prolog interpreter finds the solution(s) for you. there's more info on google.