8 Replies - 1837 Views - Last Post: 25 April 2010 - 05:35 PM Rate Topic: -----

#1 tmsewell2000  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 23-November 08

Prolog problem, finding subassemlies

Posted 23 April 2010 - 08:11 PM

I am new to Prolog, and logical programming languages in general. I need to write a predicate which finds all subassemblies of a certain assembly. Basically, an assembly is a subassembly of another if the number in its assembly name is a divisor of the other. An assembly has the rule format of 'assembly(assemblyName,addedPart,subassembly)'. I can get the subassemblies that are already listed in the rules, but I need to be able to find the subassemlies of each of those assemblies as well. I have tried several recursive calls for this with no positive results. Listed below are the rules and horn clauses I have so far. It works fine up to and including the line 'subassembly(S,A) :- assembly(A,X,S).', the next line is where I would like to recursively call subassembly to find all divisors of the original assembly. I have commented the code using the java, or '//' style as I don't know the prolog comment style.

assembly(a360,mem,a180).
assembly(a360,cpu,a120).
assembly(a360,pio,a72).
assembly(a180,mem,a90).
assembly(a180,cpu,a60).
assembly(a180,pio,a36).
assembly(a120,mem,a60).
assembly(a120,cpu,a40).
assembly(a120,pio,a24).
assembly(a90,mem,a45).
assembly(a90,cpu,a30).
assembly(a90,pio,a18).
assembly(a72,mem,a36).
assembly(a72,cpu,a24).
assembly(a60,mem,a30).
assembly(a60,cpu,a20).
assembly(a60,pio,a12).
assembly(a45,cpu,a15).
assembly(a45,pio,a9).
assembly(a40,mem,a20).
assembly(a40,pio,a8).
assembly(a36,mem,a18).
assembly(a36,cpu,a12).
assembly(a30,mem,a15).
assembly(a30,cpu,a10).
assembly(a30,pio,a6).
assembly(a24,mem,a12).
assembly(a24,cpu,a8).
assembly(a20,mem,a10).
assembly(a20,pio,a4).
assembly(a18,mem,a9).
assembly(a18,cpu,a6).
assembly(a15,cpu,a5).
assembly(a15,pio,a3).
assembly(a12,mem,a6).
assembly(a12,cpu,a4).
assembly(a10,mem,a5).
assembly(a10,pio,a2).
assembly(a9,cpu,a3).
assembly(a8,mem,a4).
assembly(a6,mem,a3).
assembly(a6,cpu,a2).
assembly(a5,pio,a1).
assembly(a4,mem,a2).
assembly(a3,cpu,a1).
assembly(a2,mem,a1).

subassembly(A,A). //Every assembly is a subassembly of itself
subassembly(a1,A). //a1 is a subassembly of every assembly
subassembly(S,A) :- assembly(A,X,S). //S is a subassembly of A                                 
subassembly(T,A) :- subassembly(assembly(A,X,S),assembly(S,X,T)).



Any direction would be much appreciated towards a solution to this problem. I have gotten part of the subassemblies by entering the query 'subassembly(X,a360).' after entering the code up to and including 'subassembly(S,A) :- assembly(A,X,S).'. Thanks, Tim

Is This A Good Question/Topic? 0
  • +

Replies To: Prolog problem, finding subassemlies

#2 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Prolog problem, finding subassemlies

Posted 24 April 2010 - 07:43 AM

well first of all this shouldn't have been posted in the function programming section, but that's ok :).. now let me make sure that i understood this correctly, lets say i want to find the subassemblies of a360, then i should get a360 (since its a subassembly of itself) a180, a120, a72, a90, a60, etc??.
Was This Post Helpful? 0
  • +
  • -

#3 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Prolog problem, finding subassemlies

Posted 24 April 2010 - 08:05 AM

i think this should do it for you, try it out

subassembly(A, A). %every assembly is a subassembly of itself

subassembly(A, S):- %subassembly(A, S) will be true if S is a subassembly of A
	assembly(A, _, S).

subassembly(A, S):- %subassembly(A, S) will be true if an assembly X is a subassembly of A and S is a subassembly of X
	assembly(A, _, X), subassembly(X, S).



hope this helps :)

NOTE: you comment your prolog code using "%" operator
Was This Post Helpful? 1
  • +
  • -

#4 tmsewell2000  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 23-November 08

Re: Prolog problem, finding subassemlies

Posted 24 April 2010 - 08:46 AM

View Postmostyfriedman, on 24 April 2010 - 06:43 AM, said:

well first of all this shouldn't have been posted in the function programming section, but that's ok :).. now let me make sure that i understood this correctly, lets say i want to find the subassemblies of a360, then i should get a360 (since its a subassembly of itself) a180, a120, a72, a90, a60, etc??.


Sorry for posting this in the wrong place, it was late last night and I was frustrated... You are correct that if you typed in subassembly(X,a360). in query mode then you should get a360 (since its a subassembly of itself) a180, a120, a72, a90, a60, ... , a2, a1.
Thanks for the reply,
Tim

View Postmostyfriedman, on 24 April 2010 - 07:05 AM, said:

i think this should do it for you, try it out

subassembly(A, A). %every assembly is a subassembly of itself

subassembly(A, S):- %subassembly(A, S) will be true if S is a subassembly of A
	assembly(A, _, S).

subassembly(A, S):- %subassembly(A, S) will be true if an assembly X is a subassembly of A and S is a subassembly of X
	assembly(A, _, X), subassembly(X, S).



hope this helps :)

NOTE: you comment your prolog code using "%" operator


I tried this, but when I enter 'subassembly(X,a360).' in query mode, all I get is a360 returning true and nothing else.
Thanks for the tip on prolog comments,
Tim
Also, I have been thinking of this as subassembly(S,A), I would read this as S is a subassembly of A. Is that correct?

This post has been edited by tmsewell2000: 24 April 2010 - 08:53 AM

Was This Post Helpful? 0
  • +
  • -

#5 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Prolog problem, finding subassemlies

Posted 24 April 2010 - 08:56 AM

oh i wrote the predicate so that you'd query is like this
subassembly(a360, X).

Quote

Also, I have been thinking of this as subassembly(S,A), I would read this as S is a subassembly of A. Is that correct?


it depends on how you write your rules, the way i wrote the rules, subassembly(S, A) will be read as A is a subassembly of S.
Was This Post Helpful? 1
  • +
  • -

#6 tmsewell2000  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 23-November 08

Re: Prolog problem, finding subassemlies

Posted 24 April 2010 - 09:14 AM

View Postmostyfriedman, on 24 April 2010 - 07:56 AM, said:

oh i wrote the predicate so that you'd query is like this
subassembly(a360, X).


That works! I tried it with the subassembly(a360,X). and I got a ton of truths, but that's fine. The next thing I need to write will make a setOf out of the results. So I may be posting here again... :bigsmile:
Thanks again,
Tim
Was This Post Helpful? 0
  • +
  • -

#7 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Prolog problem, finding subassemlies

Posted 24 April 2010 - 09:19 AM

View Posttmsewell2000, on 24 April 2010 - 06:14 PM, said:

View Postmostyfriedman, on 24 April 2010 - 07:56 AM, said:

oh i wrote the predicate so that you'd query is like this
subassembly(a360, X).


That works! I tried it with the subassembly(a360,X). and I got a ton of truths, but that's fine. The next thing I need to write will make a setOf out of the results. So I may be posting here again... :bigsmile:
Thanks again,
Tim


that's ok because of how backtracking works, and also because some assembly names were duplicated many times in the facts, so its natural to get duplicate truths, setOf will solve this problem by eliminating duplicates.
Was This Post Helpful? 0
  • +
  • -

#8 tmsewell2000  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 23-November 08

Re: Prolog problem, finding subassemlies

Posted 25 April 2010 - 09:47 AM

Ok, I got the divisors predicate working to make a set out of the subassemblies.
divisors(X,Y,S) :-
   setof(Sub,(subassembly(Sub,X),subassembly(Sub,Y)),S).
Now I am stuck on the next part, dominates. It should take an assembly and a list, dominates( E, L ). E is an assembly and L is a list of assemblies, dominates succeeds if each assembly in L is a subassembly of E.
Here is the code I have been working with, but I cant seem to get anything to return true.
dominates(E,[]).
dominates(E,L) :- 
   subassembly([Head],E),dominates(E,[Tail]).


Any direction would be much appreciated.
Thanks,
Tim
Was This Post Helpful? 0
  • +
  • -

#9 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Prolog problem, finding subassemlies

Posted 25 April 2010 - 05:35 PM

you're close
dominates(H, [X]):-
	subassembly(H, X).

dominates(X, [H|T]):-
	subassembly(X, H), dominates(X, T).



when working with prolog, always state the solution in plain English rather than thinking recursively or whatever.

the first predicate translates: assembly H dominates [X] if assembly X is a subassembly of H.
the second: assembly X dominates list [H|T] if H is a subassembly of X and X dominates the tail of the list ( which in turn means that the elements of the tail are subassemblies of X).

hope this helps
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1