[SOLVED] Anyone know Prolog? Need halp

steve296 · 06-25-2010, 08:29 AM

Hello,

I just registered into this forum, been using linux (ubuntu) for over a year now - am happy with it too! -, and I'm trying to spend this summer to learn more* on programming right before I go to uni, where they would teach it anyways

...

*more than the basics of Pascal, which I was taught in secondary

So, my problem is that I've been reading a prolog introductory book, and in it was an exercise which I have failed to solve thus far - which continued for days, now.

Here's the riddle:

Quote:

Binary trees are trees where all internal nodes have exactly two childres. The smalles binary trees consist of only one leaf node. We will represent leaf nodes as leaf(Label). For instance, leaf(3) and leaf(7) are leaf nodes, and therefore small binary trees. Given two binary trees B1 and B2 we can combine them into one binary tree using the predicate tree: tree(B1,B2). So, from the leaves leaf(1) and leaf(2) we can build the binary tree tree(leaf(1), leaf(2)). And from the binary trees tree(leaf(1), leaf(2)) and leaf(4) we can build the binary tree tree(tree(leaf(1), leaf(2)), leaf(4)).

Now, define a predicate swap/2, which produces a mirror image of the binary tree that is its first argument. For example:

Code:

?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
T = tree(leaf(4), tree(leaf(2), leaf(1))).
yes

What I could achieve, is building the rules of a binary tree in a most complicated way; but prolog cannot follow those rules to generate binary trees by querying him like this:

Code:

?- tree(X, Y).

Instead it only writes 'yes' (or 'true', for I use SWI-Prolog). If I to do the swap/2 part, it would switch the leaf(4) with tree(leaf(2), leaf(1)), but not within tree(leaf(2), leaf(1)).

If there's a resident Prolog guru lurking around here, I'd appreciate his/her help. Thanks in advance.

steve296

EDIT: my problem, more specifically said, is that I cannot make the predicate for binary trees with 2 nodes and the predicate for the single leaf node, which still counts as a tree, count as equal. Namely, tree/2 and tree/1 are two different things for prolog. Which means that I can only represent complex trees using these specific rules:

Code:

tree(leaf(Label)).
tree(B1, B2) :-
	tree(B1),
	tree(B2).
tree(B1, B2) :-
	tree(B1),
	B2 = tree(B3, B4).
tree(B1, B2) :-
	B1 = tree(B3, B4).
	tree(B2).
tree(B1, B2) :-
	B1 = tree(B3, B4),
	B2 = tree(B3, B4).

But for some reason I believe there must be a better way to describe this.

paulsm4 · 06-26-2010, 02:07 AM

Wow - AFAIK, Prolog isn't exactly a great language for data structures and algorithms...

ANYWAY, a Google search of "prolog data structures trees queues" turned up this:

http://www.ece.uc.edu/~annexste/Cour...lognotes1.html

and this:

http://download.pdc.dk/vip/72/books/...gBeginners.pdf

'Hope that helps .. PSM

ArthurSittler · 06-26-2010, 10:45 AM

<edit> Please see following post </edit>
I have not used Prolog professionally. I had a brief encounter with it in school. That was a long time ago.
I have not tested this, but I think you could implement swap something like this:

Code:

swap( leaf(Leaf), leaf(Leaf) ).
swap( tree(Left,Right), tree( swap(Right), swap(Left) ).

steve296 · 06-26-2010, 11:02 AM

Quote:

Originally Posted by paulsm4

Wow - AFAIK, Prolog isn't exactly a great language for data structures and algorithms...

ANYWAY, a Google search of "prolog data structures trees queues" turned up this:

http://www.ece.uc.edu/~annexste/Cour...lognotes1.html

and this:

http://download.pdc.dk/vip/72/books/...gBeginners.pdf

'Hope that helps .. PSM

Ummm... the thing I posted here isn't something specific, like classes, polimorphism and other stuff I read when I skimmed through a C++ book; they are just predicates. Rules, facts, clauses. They're as fundamental as variables in imperative languages. What I'm trying to say, is that by searching for something like 'data structures', or 'trees', won't help me much, because these are just labels. One could name their predicates and their arguments anything, like cat(tom, bob), or tree(leaf(1), leaf(2)); they don't mean anything, even the logical link is only in your head (in the sense that mother(caroline, ryan) and mother(ryan, caroline) may mean the same in different programs, if used consistently). But thanks anyway

.

Sorry for going overboard about prolog, oh, and if a more adept initiated is reading this, feel free to smack me in the head for being so sloppy

.

I'll be thinking about this more later, and post the solution for those who may be reading the same (free&online) book and stumble onto the same problem.

paulsm4 · 06-26-2010, 12:56 PM

Hi, steve296 -

Quote:

the thing I posted here isn't something specific,

That's for sure

Quote:

stuff I read when I skimmed through a C++ book ... like classes ... variables ...

You're absolutely correct:

* "Imperative, object-oriented languages" like C++, Java and C# have classes, variables, operations, control structures and other fundamental "building blocks" from which you can build higher-level constructs like trees, queues and, ultimately, applications and systems.

* "Declarative languages" like Prolog, on the other hand, have predicates, variables, lists, etc as their "fundamental building blocks". From which you can ALSO build higher-level constructs like trees, queues and, ultimately, applications and - who knows - maybe even full-blown systems.

The point is that Googling for something like "prolog data structures trees queues" CAN give you concrete examples for how to use Prolog syntax to build a logical "tree" data structure.

Just like the examples I cited, or the example ArthurSittler gave you.

Good luck - and have fun!

Sincerely .. PSM

ArthurSittler · 06-26-2010, 01:51 PM

I looked at Clocksin & Mellish.
I think the swap should look a bit more like

Code:

swap( L, R ) :-
    L = leaf( X ),
    R = leaf( Y ),
    Y = X.
swap( L, R ) :-
    L = tree( LL, LR ),
    R = tree( RL, RR ),
    RL = swap( LR ),
    RR = swap( LL ).

This is also untested. I do not have Prolog installed on this machine.
I do have Prolog (gprolog) installed on another machine. I have never used it. I may need your help learning how to use it.

I do not remember if Prolog permits defining two different functors with the same name but different arity, as in the following:
tree( Leaf )
tree( LTree, RTree )

steve296 · 06-27-2010, 05:45 AM

Quote:

Originally Posted by paulsm4

The point is that Googling for something like "prolog data structures trees queues" CAN give you concrete examples for how to use Prolog syntax to build a logical "tree" data structure.

Just like the examples I cited, or the example ArthurSittler gave you.

Oh... sorry for being mean, then. I'll read through them thoroughly this time...

@ArthurSittler

Prolog does permit functors with the same name but with different arities, it's just that they count as different functors. I've tested the swap you posted, and after giving

Code:

    RL = swap( LR ),
    RR = swap( LL ).

one more variable as argument (prolog didn't have rules for swap/1):

Code:

    RL = swap( LR, LR2 ),
    RR = swap( LL, LL2 ).

it replied like this:

Code:

?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
T = tree(swap(leaf(4), _G305), swap(tree(leaf(1), leaf(2)), _G308)).

Btw, I'm trying to advance your idea of recursion (that's the whole purpose of this exercise in the book - I just couldn't find a way to make it recursive). I'll post my results shortly.

[1-2 hrs after I forgot to send this post:]

I found it, finally. It's not pretty, because it covers all possibilities of how could a tree look like (e.g. tree(leaf(1)) or tree(leaf(1), leaf(2))). Anyways, the source code is in the attachment. What the swap part does is that it first checks whether the tree() has any nodes which have even more nodes (first predicate becomes true when it's a simple tree, with no internal nodes; second and third predicate becomes true when either the first or the second node of the main tree has nodes; fourth when both nodes of main tree() have nodes of their own). Then it tries t swap the internal nodes (if any), and finally swaps the two nodes of the main tree(). And this is recursive.

Thanks for both of your help, I was taught a small lesson in both programming and ethics

EDIT: I made a slight change to the file, found a small error in it (size is 1.2KB now).

ArthurSittler · 06-27-2010, 02:35 PM

Thank you, steve296.
After I installed Prolog, I was unable to get my proposed solution to work. In my defense, my brush with Prolog was very brief, and it was a long time ago. You have inspired me to refresh my Prolog skills. Do not be surprised if you get a question or two from me about Prolog in the near future.

paulsm4 · 06-27-2010, 02:57 PM

Steve296 -

As ArthurSittler already mentioned, "Programming in Prolog", by Clocksin and Mellish is *the* resource for learning Prolog:

http://www.amazon.com/Programming-Pr...dp/3540006788/

IMHO .. PSM

steve296 · 06-27-2010, 05:00 PM

Quote:

Originally Posted by ArthurSittler

Thank you, steve296.
After I installed Prolog, I was unable to get my proposed solution to work. In my defense, my brush with Prolog was very brief, and it was a long time ago. You have inspired me to refresh my Prolog skills. Do not be surprised if you get a question or two from me about Prolog in the near future.

Cool

. I'm glad you found something to rediscover and cherish. Just don't let the notion vanish, though

. And I'll be welcoming any question or thought about prolog, or anything for that matter.

Quote:

Originally Posted by paulsm4

Steve296 -

As ArthurSittler already mentioned, "Programming in Prolog", by Clocksin and Mellish is *the* resource for learning Prolog:

http://www.amazon.com/Programming-Pr...dp/3540006788/

IMHO .. PSM

Thank you for the references, now I'll be sure to have more books on the list than I can read this summer

. Lets see.. C/C++, bash, python, prolog.....

Innar Made · 07-21-2010, 02:47 PM

I know this question is already solved, but I paste my solution too as I think it would be good for future reference.

Code:

swap(leaf(X),Y) :- Y = leaf(X).
swap(tree(X,Y),Z) :- swap(X,Xs), swap(Y,Ys), Z = tree(Ys,Xs).

Regards,
Innar