Latest LQ Deal: Linux Power User Bundle
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org [SOLVED] Anyone know Prolog? Need halp
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

06-25-2010, 08:29 AM   #1
steve296
LQ Newbie

Registered: Jun 2010
Posts: 9

Rep:
Anyone know Prolog? Need halp

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.

Last edited by steve296; 06-25-2010 at 11:41 AM. Reason: specificism

 06-26-2010, 02:07 AM #2 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 Rep: 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 Last edited by paulsm4; 06-26-2010 at 02:09 AM.
 06-26-2010, 10:45 AM #3 ArthurSittler Member   Registered: Jul 2008 Distribution: Slackware Posts: 124 Rep: It was a long time ago Please see following post 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) ).``` Last edited by ArthurSittler; 06-26-2010 at 01:54 PM. Reason: Suggestion was way off base.
06-26-2010, 11:02 AM   #4
steve296
LQ Newbie

Registered: Jun 2010
Posts: 9

Original Poster
Rep:
Right...

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.

Last edited by steve296; 06-26-2010 at 11:03 AM. Reason: forgot quoting

06-26-2010, 12:56 PM   #5
paulsm4
LQ Guru

Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep:
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

 06-26-2010, 01:51 PM #6 ArthurSittler Member   Registered: Jul 2008 Distribution: Slackware Posts: 124 Rep: Oops 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 ) Last edited by ArthurSittler; 06-26-2010 at 07:35 PM. Reason: a bit more care
06-27-2010, 05:45 AM   #7
steve296
LQ Newbie

Registered: Jun 2010
Posts: 9

Original Poster
Rep:
Sorry...

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).
Attached Files
 binarytree.txt (1.2 KB, 59 views)

Last edited by steve296; 06-27-2010 at 06:28 AM.

1 members found this post helpful.
 06-27-2010, 02:35 PM #8 ArthurSittler Member   Registered: Jul 2008 Distribution: Slackware Posts: 124 Rep: If it isn't verified, it does not work. 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.
 06-27-2010, 02:57 PM #9 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 Rep: 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
06-27-2010, 05:00 PM   #10
steve296
LQ Newbie

Registered: Jun 2010
Posts: 9

Original Poster
Rep:
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.....

 07-21-2010, 02:47 PM #11 Innar Made LQ Newbie   Registered: Jul 2010 Location: Estonia, Tallinn Distribution: Debian Lenny Posts: 1 Rep: 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 1 members found this post helpful.

 Tags beginner, help, recursive

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Monkey Man Fedora 3 10-06-2006 08:10 PM malb Linux - Newbie 9 07-25-2005 06:52 PM magicvash Programming 1 05-27-2005 09:31 AM mrb Linux - Newbie 1 05-15-2004 01:12 PM

LinuxQuestions.org

All times are GMT -5. The time now is 05:21 PM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -